Study the class notes from last week and this week. Use the following parser and environment code for this assignment:
Use cps-interpreter-with-exceptions-and-resume.ss for the next three questions. Modify the interpreter to raise an exception when a user-defined function is called with the wrong number of arguments. For example:
> (start)
Welcome to the CS 131 Ploy interpreter
==> (define f
(fun (a b) ->
(print "executing f")
((a * a) + (b * b))))
ok
==> (print "answer is: "
(try (f 1 2 3)
except (fun (e resume) ->
(print "caught " e " exception")
42)))
caught wrong number of arguments exception
answer is: 42
ok
==>
Modify the interpreter's division primitive to raise an exception on division by zero. For example:
==> (define g
(fun (x y z) ->
(print "executing g")
(x * (y / z))))
ok
==> (print "answer is: "
(try (g 10 3 0)
except (fun (e resume) ->
(print "caught " e " exception")
42)))
executing g
caught division by zero exception
answer is: 42
ok
==>
An alternative to letcc and invoke is to add a single primitive function called call/cc to the language, which stands for "call with current continuation". Call/cc takes a 1-argument function f as input and binds the parameter of f to a function that behaves like the current continuation. For example:
(2 + (call/cc (fun (k) -> (100 * (k 3)))) => 5
Notice that k is an ordinary function. Applying k to 3 sends the 3 to the continuation of the call/cc expression, avoiding the multiplication by 100. We could actually define call/cc in terms of letcc and invoke as follows:
(define call/cc
(fun (f) ->
(letcc cont (f (fun (v) -> (invoke cont v))))
Add call/cc directly to the interpreter as a primitive function in the environment, without using letcc or invoke. What does the expression (call/cc call/cc) represent? What about ((call/cc call/cc) (call/cc call/cc))?
Use cps-interpreter-with-threads.ss for the next two questions. Add to the defined language a primitive function (yield) that causes the current thread to yield the remainder of its time slice. The value returned by yield is the symbol ok.
The algorithm used for acquire is called a spin lock. This can be wasteful if the lock may be held for a long time, because the waiting thread will continually retry the lock. Avoid this by associating a queue of waiting threads with each lock. (This is sometimes called a sleep queue.) If a thread attempts to acquire a closed lock, it places itself on the queue for that lock. When a lock is released, it wakes up the first thread on its queue.
Transform the following first-order-tail-form version of remove into a trampolined register machine. Your top-level remove function should still take two arguments as before, for testing purposes. You do not need to get rid of define-datatype, although you can if you like. Make sure your register machine behaves exactly like the original code. Examples:
(remove 'x '(a b x c x)) => (a b c)
(remove 'a '((a (b ((a)))) c (d (a b)) a)) => (((b (()))) c (d (b)))
(define-datatype continuation continuation?
(cont0)
(cont1
(x symbol?)
(lst list?)
(k continuation?))
(cont2
(k continuation?)
(v1 list?))
(cont3
(k continuation?)
(lst list?)))
(define remove
(lambda (x lst)
(remove-cps x lst (cont0))))
(define remove-cps
(lambda (x lst k)
(cond
((null? lst) (apply-cont k '()))
((list? (car lst)) (remove-cps x (car lst) (cont1 x lst k)))
((equal? (car lst) x) (remove-cps x (cdr lst) k))
(else (remove-cps x (cdr lst) (cont3 k lst))))))
(define apply-cont
(lambda (k value)
(cases continuation k
(cont0 () value)
(cont1 (x lst k) (remove-cps x (cdr lst) (cont2 k value)))
(cont2 (k v1) (apply-cont k (cons v1 value)))
(cont3 (k lst) (apply-cont k (cons (car lst) value)))
(else (error 'apply-cont "bad continuation: ~s" k)))))
Files to submit:
You don't need to submit the environment or parser code. If you have questions about anything, just ask!