Assignment 1


Due Date:  January 31, 2012

For this assignment, you will examine how to use continuations to build co-routines.
The assignment will use Racket and its programming environment

Part I

The traditional coroutining example is that of producers and consumers. The producer (or producers) and consumer (or consumers) share a common buffer. Producers add values to the buffer and consumers remove values from the buffer.

In Racket (i.e., Scheme), we might model a buffer as an object.


(define make-buffer
  (lambda (_capacity)
    (let ((contents (make-vector _capacity))
          (front 0)
          (back 0)
          (capacity _capacity)
          (size 0))
      (lambda (command . params)
        (cond
          ((eq? command ':empty?)
           (<= size 0))
          ((eq? command ':full?)
           (>= size capacity))
          ((eq? command ':get!)
           (let ((tmp (vector-ref contents front)))
              (set! front (modulo (+ front 1) capacity))
              (set! size (- size 1))
              tmp))
          ((eq? command ':put!)
           (vector-set! contents back (car params))
           (set! back (modulo (+ back 1) capacity))
           (set! size (+ size 1)))
          ((eq? command ':dump)
           (display "capacity: ") (display capacity) (newline)
           (display "size: ") (display size) (newline)
           (display "front: ") (display front) (newline)
           (display "back: ") (display back) (newline)
           (display "contents: ") (display contents) (newline))
          (else
            (error "Undefined command")))))))


Here is a generalized consumer.  A consumer takes four arguments: (1) a buffer buffer, (2) a procedure done? that is
true when the consumer should no longer remove items from the buffer, (3) a procedure suspend that suspends
the consumer (e.g., when the buffer becomes empty), and (4) a procedure consume that calls get to remove
an element from the buffer, along with the number of operations performed thus far, and performs some
computation on the element.

(define consumer
  (lambda (buffer done? suspend consume)
    (let kernel ((count 0))
       (cond
         ((done? count))
         ((buffer ':empty?)
          (suspend)
          (kernel count))
         (else
          (consume count (buffer ':get!))
          (kernel (+ count 1)))))))



Here is a generalized producer.  A consumer takes four arguments: (1) a buffer buffer, (2) a procedure done? that is
true when the producer should no longer insert items into the buffer, (3) a procedure suspend that suspends
the producer (e.g., when the buffer is full), and (4) a procedure create that calls put in the buffer implementation to
insert a new element into the buffer.  The create procedure takes the current count of operations
performed by the producer as its argument.

(define producer
  (lambda (buffer done? suspend create)
    (let kernel ((count 0))
       (cond
         ((done? count))
         ((buffer ':full?)
          (suspend)
          (kernel count))
         (else
          (buffer ':put! (create count))
          (kernel (+ count 1)))))))



Here is a sample use of the producer and consumer in which we print out a message instead of suspending. We also use a random number generator to decide whether or not we're done (otherwise, we might loop forever).


(define pc
  (lambda ()
    (let ((buf (make-buffer 10)))
      (producer buf
                (lambda (num) (= (random 20) 0))
                (lambda () (display "Suspending producer") (newline))
        (lambda (val) (random 100)))
      (consumer buf
                (lambda (num) (= (random 20) 0))
                (lambda () (display "Suspending consumer") (newline))
        (lambda (count val)
          (display (list 'consume count val))
          (newline))))))



If we put the producer first, as in the above, the producer will fill the buffer (which we won't see) and then repeatedly note that it is suspending itself (since the suspend operation does not work). It will then eventually give up. The consumer will then read from the buffer and print out the values. It will then repeatedly note that it is suspending itself and eventually give up.

You need to implement suspend so that the producer and consumer can act as coroutines.  The behavior you should expect to see is 10 elements of the buffer being added and consumed at a time.  Your implementation should use continuations to capture the state of the producer and consumer as appropriate.

Part 2

For this part of the assignment, you will reimplement the samefringe problem discussed in class in Scheme.  Much of the necessary code is already provided below.  You will need to fill in the code bracketed by "[.....]".

(define sameFringe
  (lambda (tree1 tree2)
    (let ((gen1 (make-generator tree1))
          (gen2 (make-generator tree2)))
      (driver gen1 gen2))))

(define driver
  (lambda (gen1 gen2)
    (let ((leaf1 (gen1))
          (leaf2 (gen2)))
      (if (= leaf1 leaf2)
          (if (zero? leaf1)
              #t
              (driver gen1 gen2))
      #f))))

(define make-generator
  (lambda (tree)
    (letrec ((caller '*)
             (generate-leaves
               (lambda ()
                 (letrec ((loop (lambda (tree)
                                  (if (leaf? tree)
                                      (call/cc [....])
                                      (begin (loop (car tree))
                                             (loop (cadr tree)))))))
                   (loop tree)))))
      (lambda ()
        (call/cc [....])

(define leaf? number?)
(define subtree? pair?)
(define tree1 '(((((((((((((1 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14))
(define tree2 '(1 (2 (3 (4 (5 (6 (7 (8 (9 (10 (11 (12 (13 14))))))))))))))
(define tree3 '(2 (1 (3 (4 (5 (6 (7 (8 (9 (10 (11 (12 (13 14))))))))))))))

Your implementation should yield #t for (sameFringe tree1 tree2) and #f for
(sameFringe tree2 tree3)
and (sameFringe tree1 tree3).