C311 Assignment 7 -- The CPS Transformation

Due Monday, February 26, 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 dupla
  (lambda (a ls)
    (cond
      ((null? ls) '())
      (else
	(cons a (dupla a (cdr ls)))))))

(define duplicate
  (lambda (n i)
    (cond
      ((zero? n) '())
      (else
	(cons i (duplicate (sub1 n) i))))))

(define multtup
  (lambda (tup)
    (cond
      ((null? tup) 1)
      (else
	(* (car tup) (multtup (cdr tup)))))))

(define intersection
  (lambda (a b)
    (cond
      ((null? a) '())
      ((memq (car a) b)
       (cons (car a) (intersection (cdr a) b)))
      (else
	(intersection (cdr a) b)))))

(define subst
  (lambda (new old ls)
    (cond
      ((null? ls) '())
      ((equal? (car ls) old)
       (cons new (subst new old (cdr ls))))
      (else
	(cons (car ls) (subst new old (cdr ls)))))))

(define snoc
  (lambda (ls i)
    (cond
      ((null? ls) (cons i '()))
      (else
	(cons (car ls) (snoc (cdr ls) i))))))

(define reverse-it
  (lambda (ls acc)
    (cond
      ((null? ls) acc)
      (else (reverse-it (cdr ls)
	      (cons (car ls) acc))))))

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

7

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 "7" c311@lakshmi.cs.indiana.edu < asgn.ss

Back to the c311 page

ehilsdal@cs.indiana.edu