C311 Spring 1997 -- Programming Languages

C311 Spring 1997 Assignment 5: Recursion and Dynamic Scope

Due Tuesday, February 25, 11:59pm.

Start with your solution to assignment 4 (or our solution).

1. Use Scheme syntax and semantics to implement letrec as an extension to your interpreter's functionality (and not as a macro expansion exercise). Add this functionality by making the letrec form behave like the syntax expansion method (which uses let and set!), but create the environments and mutate them yourself.
2. Extend the interpreter of the last assignment with a new form that has the same syntax as the lambda form, but with the keyword delta instead of lambda. References to variables that occur free in a delta form are resolved in the environment in which the procedure created by evaluation of the delta form was invoked. Thus in a program that used only delta binding forms (no let, letrec, or lambda forms) variable references would all be resolved according to the dynamic scope rule. Of course a program that did not use the delta form would use entirely static scope. (See EOPL Exercise 5.7.4 for an implementation hint.)
3. Invent a program in this language that is as small as possible, uses both lambda and delta forms, and gives a different answer than it would if all its uses of lambda (not from let or letrec expansion) were replaced by delta, and a different answer than it would if all its uses of delta were replaced by lambda, and a different answer that it would if the uses of lambda and delta were swapped. Bind the datum representing this program to the top-level variable strange.

The preliminary remarks of the third assignment apply.

It is suggested that you use the new grammar checker.

Test Cases

For a list of test cases, take a look at this sample scheme interaction output.

Submission