CS 131 Homework 8

1. Study this week's class notes on continuation-passing style (CPS).

2. Convert the following ten programs to CPS. Use the function init-k as your initial continuation when testing your code.

   • (define init-k (lambda (v) (pretty-print v) 'done))
     

   • (define remove-all
       (lambda (x lst)
         (cond
           ((null? lst) '())
           ((list? (car lst))
            (cons (remove-all x (car lst)) (remove-all x (cdr lst))))
           ((equal? (car lst) x) (remove-all x (cdr lst)))
           (else (cons (car lst) (remove-all x (cdr lst)))))))
     

     Name your CPS program remove-all-cps. Examples:

     (remove-all-cps 'a '((a b (a)) ((a) c)) init-k) => ((b ()) (() c)) done
     (remove-all-cps 'd '((a b (a)) ((a) c)) init-k) => ((a b (a)) ((a) c)) done
     

   • (define occurs-in
       (lambda (x lst)
         (cond
           ((null? lst) #f)
           ((list? (car lst))
            (if (occurs-in x (car lst))
     	 #t
     	 (occurs-in x (cdr lst))))
           ((equal? (car lst) x) #t)
           (else (occurs-in x (cdr lst))))))
     

     Name your CPS program occurs-in-cps. Examples:

     (occurs-in-cps 'c '((a b (a)) ((a) c)) init-k) => #t done
     (occurs-in-cps 'd '((a b (a)) ((a) c)) init-k) => #f done
     

   • (define remove-first
       (lambda (x lst)
         (cond
           ((null? lst) '())
           ((list? (car lst))
            (if (occurs-in x (car lst))
     	 (cons (remove-first x (car lst)) (cdr lst))
     	 (cons (car lst) (remove-first x (cdr lst)))))
           ((equal? (car lst) x) (cdr lst))
           (else (cons (car lst) (remove-first x (cdr lst)))))))
     

     Name your CPS program remove-first-cps. Examples:

     (remove-first-cps 'a '((a b (a)) ((a) c)) init-k) => ((b (a)) ((a) c)) done
     (remove-first-cps 'd '((a b (a)) ((a) c)) init-k) => ((a b (a)) ((a) c)) done
     

   • (define depth
       (lambda (lst)
         (cond
           ((null? lst) 1)
           ((not (list? (car lst))) (depth (cdr lst)))
           ((> (depth (cdr lst)) (+ 1 (depth (car lst)))) (depth (cdr lst)))
           (else (+ 1 (depth (car lst)))))))
     

     Name your CPS program depth-cps. Examples:

     (depth-cps '((a b (c)) ((d) e ((f) g h))) init-k) => 4 done
     (depth-cps '((a b ((c (d)))) (e (f g))) init-k)   => 5 done
     

   • (define depth-with-let
       (lambda (lst)
         (cond
           ((null? lst) 1)
           ((not (list? (car lst))) (depth-with-let (cdr lst)))
           (else (let ((dfirst (+ 1 (depth-with-let (car lst))))
     		  (drest (depth-with-let (cdr lst))))
     	      (if (> drest dfirst)
     		drest
     		dfirst))))))
     

     Name your CPS program depth-with-let-cps. Examples:

     (depth-with-let-cps '((a b (c)) ((d) e ((f) g h))) init-k) => 4 done
     (depth-with-let-cps '((a b ((c (d)))) (e (f g))) init-k)   => 5 done
     

   • (define map
       (lambda (f lst)
         (if (null? lst)
           '()
           (cons (f (car lst)) (map f (cdr lst))))))
     

     Name your CPS program map-cps. Assume that its first argument will be an ordinary non-CPS function. Example:

     (define square (lambda (n) (* n n)))
     (map-cps square '(1 2 3 4 5) init-k) => (1 4 9 16 25) done
     

   • (define map2
       (lambda (f lst)
         (if (null? lst)
           '()
           (cons (f (car lst)) (map2 f (cdr lst))))))
     

     Transform map to CPS again, except this time assume that its first argument will be a function written in continuation-passing style. Name your CPS program map2-cps. Example:

     (define square-cps (lambda (n k) (k (* n n))))
     (map2-cps square-cps '(1 2 3 4 5) init-k) => (1 4 9 16 25) done
     

   • (define every
       (lambda (pred lst)
         (cond
           ((null? lst) #t)
           ((pred (car lst)) (every pred (cdr lst)))
           (else #f))))
     

     Name your CPS program every-cps. Assume that its first argument will be an ordinary non-CPS predicate function. Example:

     (define gt5 (lambda (n) (> n 5)))
     (every-cps gt5 '(6 7 8 9) init-k) => #t done
     

   • (define every2
       (lambda (pred lst)
         (cond
           ((null? lst) #t)
           ((pred (car lst)) (every2 pred (cdr lst)))
           (else #f))))
     

     Transform every to CPS again, except this time assume that its first argument will be a predicate function written in continuation-passing style. Name your CPS program every2-cps. Example:

     (define gt5-cps (lambda (n k) (k (> n 5))))
     (every2-cps gt5-cps '(6 7 8 9) init-k) => #t done
     

   • (define make-scaled
       (lambda (scale f)
         (lambda (x)
           (* scale (f x)))))
     

     Name your CPS program make-scaled-cps. Assume that its second argument (the function to be scaled) will be in continuation-passing style. The function returned by make-scaled-cps should also be in CPS. Example:

     (define square-cps (lambda (n k) (k (* n n))))
     (make-scaled-cps 2 square-cps (lambda (v) (v 3 init-k))) => 18 done
     

3. Add an (abort) primitive to the interpreter, using

   • interpreter-with-define.ss
   • parser-with-define.ss
   • environments-with-references.ss

   as your starting point. When the interpreter evaluates an (abort) expression, it should simply abort the current computation in progress and return the symbol aborted to top level, without exiting from the read-eval-print loop. You may implement abort however you like, either as a primitive function or as a special form. For example:

   > (start)
    
   Welcome to the CS 131 Ploy interpreter
    
   ==> (2 + (100 * (4 + (abort))))
   aborted
   ==> (2 + 3)
   5
   ==>
   

Turning in your homework

Put your ten CPS function definitions into a single Scheme file named cps-functions.ss. Files to submit:

• cps-functions.ss
• interpreter-with-define.ss
• parser-with-define.ss
• environments-with-references.ss

If you have questions about anything, just ask!