Due: Before the start of D-term (negotiable if
necessary). Submit by email to Kathi
Collaboration Policy: Individual
In class, we looked at programming with continuations, but we did not try to implement them. Implementing continuations (without let/cc) relies on a technique known as continuation-passing style (CPS, for short). In CPS, we rewrite a program so that all functions take a (manually-constructed) continuation as an extra argument. The CPS algorithm (covered in the text) shows you how to construct these continuations (if you took cs1102, you saw this when we converted to "script position"). Chapter 17 works through several examples of the construction to develop your intuition for the process.
Implementing continuations involves applying the CPS algorithm to an interpreter, then adding a let/cc-like construct that exploits the continuation argument. The text (chapter 20) works through this construction and the resulting interpreter. For this assignment, I want you to understand the CPSed interpreter and extend it with constructs that implement the essence of stack inspection, a technique that underlies some forms of security in Java.
Stack inspection builds on two operations:
<E> ::= ...
| {bless <E>}
| {check}
The bless primitive creates a blessed stack frame for
the duration of evaluating its sub-expression. The check
primitive traverses the run-time stack; if it finds a blessed frame it
evaluates to 0 (so you can, for instance, use it inside
sums without affecting the outcome), otherwise it terminates the
program's execution (with an error).
Extend the cps interpreter presented in the text (fig
20.2) with these two new language constructs. You may not add any new
arguments to the interpreter. You should not change the type,
behavior, or use of the environment. The k-argument must continue to
be a function (rather than some expanded data structure that would
effectively add a new argument to the interpreter). Feel free to ask
me if your proposed approach is in the spirit of the assignment as you
go.
Note: Java lacks tail-call optimization ostensibly because this hurts the ability to implement stack inspection. In fact, this claim is entirely false. But we're stuck with the result of this decision, making the JVM a poor target for other language compilers. Unfortunately, .NET has also adopted this mistake, as the linked paper explains.
I will grade these through an oral code review (aka "codewalk"). During the codewalk, you'll be asked to present your implementation and to explain how it solves the problem. I'll also ask questions to ascertain that you understand the CPSed interpreter as presented in the book (how it works, at the level I'd have expected if you'd written it yourself). We will schedule codewalks after you are done with the assignment.
As this assignment has no bearing on your undergrad course grade, I can be flexible with the due date. However, I'd rather it not extend too far out. Talk to me to work out something mutually agreeable.
Submit a single Scheme file with your final interpreter and test cases. Testing will count, as it has on all other assignments.
Nothing yet ...