C311 Assignment 9 -- CPS and Representation

Due Monday, March 18, at 9 AM

Submit via email

This assignment consists of taking a number of fairly simple procedures and

converting them to CPS, with the standard procedural representation of continuations,
making the treatment of continuations representation independent, and
providing a record representation of continuations.

For each problem, you will be handing in a record-based CPSed version of the given procedure, but when we hand grade we will substitute other continuation representations (by changing the definitions of init-k, apply-k, and make-??-k).

The autograder will not be as discerning as it was for the last assignment, so it will be easier to get an incorrect assignment through the autograder with a perfect score. So let me reiterate that the autograder merely provides an indication of correctness -- in this case, a very basic one -- but your final grade will be based on a human banging on the code.

Instructions

For each of the procedures below, first convert the procedure to CPS as in assignment eight. Then make the treatment of continuations representation-independent (without handing in a procedural representation), and tack an ``-ri'' suffix to the (already ``-cps''-suffixed) procedure name. Finally, represent your continuations with records.

For example, if we asked you to perform these transformations on our old friend, fact,

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

You would first convert to CPS.

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

Then, you would convert to representation-independent treatment of continuations (leaving the continuations represented as procedures, for now), and change the name of the procedure to ``fact-cps-ri''. Instead of using the traditional ``apply-k'' and ``init-k'', you should use ``apply-foo-k'' and ``init-foo-k'' when you are working with the procedure ``foo''.

(define fact-cps-ri
  (lambda (n k)
    (if (zero? n)
        (apply-fact-k k 1)
        (fact-cps-ri (sub1 n)
          (make-mult-k n k)))))

(define make-mult-k
  (lambda (n k)
    (lambda (v)
      (apply-fact-k k (* n v)))))

(define init-fact-k (lambda (v) v))
        
(define apply-fact-k
  (lambda (k v)
    (k v)))

You would not hand these definitions of apply-fact-k, make-mult-k and init-fact-k. Instead -- first making sure the previous transformation worked -- you would then choose an alternate representation for the continuations; the record model used in class:

(load "record.ss")

(define fact-cps-ri
  (lambda (n k)
    (if (zero? n)
        (apply-fact-k k 1)
        (fact-cps-ri (sub1 n)
          (make-mult-k n k)))))

(define-record mult-k (n k))
(define-record init-fact-k ())

(define init-k (make-init-fact-k))

(define apply-fact-k
  (lambda (k v)
    (variant-case k
      (init-fact-k () v)
      (mult-k (n k)
        (apply-fact-k k (* n v)))
      (else
        (error 'apply-k
          "Bad continuation ~s" k)))))

(Note that the definition of fact-cps-ri was not changed in this transformation).

Assignment

Perform the transformations on these procedures:

(define depth
  (lambda (ls)
    (cond
      ((null? ls) 1)
      ((list? (car ls))
       (max (add1 (depth (car ls))) (depth (cdr ls))))
      (else (depth (cdr ls))))))

You may assume that list? and max are simple procedures.

(define substq
  (lambda (new old ls)
    (cond
      ((null? ls) '())
      ((eq? (car ls) old)
       (cons new (substq new old (cdr ls))))
      (else
        (cons (car ls) (substq new old (cdr ls)))))))

(define ack
  (lambda (x y)
    (cond
      ((= y 0) 0)
      ((= x 0) (* 2 y))
      ((= y 1) 2)
      (else
        (ack (sub1 x)
          (ack x (sub1 y)))))))

This is the Ackerman function, famed in song and legend. When you test it, test it with small numbers: it gets big very fast.

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

9

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

Back to the c311 page

ehilsdal@cs.indiana.edu