C311 Assignment 8 -- The CPS Transformation (continued)

Due Monday, March 4, at 9 AM

Submit via email

This assignment consists of converting a number of procedures to continuation-passing style. The continuation argument should be the last argument of the new procedure. The name of the procedure you convert should be the name of the original procedure plus the suffix ``-cps''. So, for example, if you were asked to convert the following procedure into continuation-passing style,

(define fact
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (sub1 n))))))

your answer would be

(define fact-cps
  (lambda (n k)
    (if (zero? n)
        (k 1)
        (fact-cps (sub1 n)
          (lambda (v)
            (k (* n v)))))))

To check whether your procedures work correctly, you might want to test them with the initial continuation

(define init-k
  (lambda (v)
    (printf "The answer is ~s~n" v)
    (reset)))

which is somewhat like the continuation used by the grader.

Assignment

Convert the following procedures to CPS.

(define f
  (lambda (l)
    (cond
      ((null? l) 0)
      ((g l) (+ 1 (f (car l))))
      (else (+ (f (car l)) (f (cdr l)))))))

(define mystery
  (lambda (n)
    (letrec
      ((mystery-helper
	 (lambda (n s)
	   (cond
	     ((zero? n) (list s))
	     (else
	       (append
		 (mystery-helper (sub1 n) (cons 0 s))
		 (mystery-helper (sub1 n) (cons 1 s))))))))
      (mystery-helper n '()))))

(define deep-recur
  (lambda (seed item-proc list-proc)
    (letrec
      ((helper
	 (lambda (ls)
	   (if (null? ls)
	       seed
	       (let ((a (car ls)))
		 (if (or (pair? a) (null? a))
		     (list-proc (helper a) (helper (cdr ls)))
		     (item-proc a (helper (cdr ls)))))))))
      helper)))

In this problem, you must also CPS the procedures item-proc and list-proc because they could be recursive.

EOPL Exercise 8.5.4 (a) Write map-cps, the procedure map in CPS. Its first argument, a procedure, must also be written in CPS.

EOPL Exercise 8.5.4 (c) Write the procedure add>n that takes a list of numbers and a number n and returns the sum of all the numbers in the list that are greater than n. Now CPS this procedure as add>n-cps. You need to hand in both the non-CPSed and CPSed versions for this assignment.

(define what-happens
  (lambda (x1 x2 f)
    (cond
      [(null? x1) x2]
      [(symbol? (car x1)) (cons x1 x2)]
      [else
	(f (let ([f (car x1)])
	     (cons f
	       (let ([f (lambda (x) (cons x 'a))])
		 (cons (what-happens (car x1) x2 f) (what-happens (cdr x1) x2 f))))))])))

Remember that f needs to be CPSed as well.

Submission

Write your answers to the exercises in a file (with comments, following the proper indentation rules), and send that file to

c311@lakshmi.cs.indiana.edu

with the subject line

8

Assuming you've saved your homework in the file ``asgn.ss'' in the current directory, one way to submit is with the command:

Mail -s "8" c311@lakshmi.cs.indiana.edu < asgn.ss

Back to the c311 page

ehilsdal@cs.indiana.edu