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).