A recursive version of Ackermann's function is given below. Rewrite ackermann and superorder in full continuation-passing style (i.e., the functions returned by superorder-cps should also be in CPS). Calling (ackermann-cps 3 (lambda (v) (pretty-print v) 'done)) should print 27.
(define ackermann
(lambda (n)
((superorder n) n n)))
(define superorder
(lambda (n)
(cond
((= n 1) (lambda (x y) (+ x y)))
((= n 2) (lambda (x y) (* x y)))
(else (lambda (x y)
(if (= y 0)
1
((superorder (- n 1)) x ((superorder n) x (- y 1)))))))))
Study the CPS interpreter we developed in class this week:
Use this code as your starting point for the next two problems.
Add support for escaping functions to the interpreter, with the following syntax:
(escfun (<var> ...) -> <body> <body> ...)
An escaping function is just like a regular function, except that when it is applied, it returns the resulting value to top level and aborts any remaining computation in progress, without exiting from the interpreter. For example:
> (start)
Welcome to the CS 131 Ploy interpreter
==> (let ((square (escfun (n) -> (n * n))))
(100 * (2 + (square 5))))
25
==>
If the interpreter encounters an unbound variable, Scheme's error handler is called, which terminates everything. For example:
> (start) Welcome to the CS 131 Ploy interpreter ==> (list 1 2 3 a) Error in empty-environment: variable a is unbound. Type (debug) to enter the debugger. >
What we really want is for the interpreter to abort the computation with an appropriate error message and return to top level, without terminating the read-eval-print loop. Suppose we redefine apply-env so that instead of calling error, the empty environment invokes the REP-k continuation, like abort does:
(define apply-env
(lambda (this-env symbol)
(cases environment this-env
(empty-environment () (REP-k `(error: ,symbol is unbound)))
...)))
> (start)
Welcome to the CS 131 Ploy interpreter
==> (list 1 2 3 a)
(error: a is unbound)
==> (2 + 3)
5
==>
This seems to work fine. However, a strange thing happens next if we try to exit the system:
==> (exit) (1 2 3 goodbye) ==>
What's going on here? In a comment in your code, explain in detail exactly what causes this behavior. To fix the problem, you'll need to convert lookup-value, lookup-ref, lookup-ref-in-first-frame, and apply-env to CPS. Changing the other functions in environments.ss is not necessary. You'll also need to rewrite the calls to these functions wherever they appear in the code, including in the parser.
CPS versions of the factorial and fibonacci functions are shown below. In this code, continuations are represented as Scheme functions. Transform this code to first-order tail form.
(define fact
(lambda (n)
(fact-cps n (lambda (v) v))))
(define fact-cps
(lambda (n k)
(if (= n 0)
(k 1)
(fact-cps (- n 1) (lambda (v) (k (* n v)))))))
(define fib
(lambda (n)
(fib-cps n (lambda (v) v))))
(define fib-cps
(lambda (n k)
(cond
((= n 0) (k 0))
((= n 1) (k 1))
(else (fib-cps (- n 1)
(lambda (v1)
(fib-cps (- n 2)
(lambda (v2)
(k (+ v1 v2))))))))))
The CPS Challenge: Transform the expression below into full continuation-passing style. This expression, when evaluated in your interpreter, returns 120. Your equivalent CPS expression should likewise return 120. For this problem, use (fun (v) -> v) as the initial continuation.
(((fun (g) ->
((fun (f) -> (g (fun (a) -> ((f f) a))))
(fun (f) -> (g (fun (a) -> ((f f) a))))))
(fun (r) ->
(fun (n) ->
(if (n = 0)
1
(n * (r (n - 1)))))))
5)
Hint: You can check whether or not your answer is correct by changing all of the fun's to escfun's in your CPS expression. If the resulting expression still evaluates to 120, then congratulations, you've CPS'ed correctly!
Breakpoints: In class we added a simple breakpoint facility to our interpreter. Calling (rep) suspends execution and immediately enters a new read-eval-print loop. When we call (exit value), we return to the previously suspended computation, passing back value as the value of the (rep) expression. For example:
==> (define fact
(fun (n) ->
(if (n = 0)
(rep)
(n * (fact (n - 1))))))
ok
==> (fact 5)
Entering new REP loop
(1)==> (3 + 4)
7
(1)==> n
(error: n is unbound)
(1)==> (exit 10)
Returning to previous level
1200
==>
Using the notes as a guide, add support for breakpoints to your interpreter. Unfortunately, we do not have access in the new REP loop to the environment that existed when the computation was suspended. It would be nice to run the new REP loop in that environment, so that we could examine or change the values of local variables, such as n above. For example:
==> (fact 5) Entering new REP loop (1)==> n 0 (1)==> (exit 10) Returning to previous level 1200 ==>
Modify your interpreter so that the new REP loop uses the local environment that exists at the breakpoint, instead of the top-level environment. Hint: change read-eval-print so that it takes an environment as an argument. This will require making some modifications to your representation of functions, and possibly continuations as well (or at least one of them).
Put your code from parts 1 and 5 into a single Scheme file named assign9.ss. Files to submit:
For the extra credit problems, put your CPS challenge answer in a file named ec-challenge.ploy and your breakpoint interpreter code in separate files named ec-interpreter.ss, ec-parser.ss, and ec-environments.ss. Files to submit:
If you have questions about anything, just ask!