Interpretation

Matthias Felleisen

Here is an extension of Lambda with a few constructs:

  Lambda is one of: 
    Identifier     
    (lambda (Identifier ...) Lambda)
    (let (Identifier Lambda) Lambda)
    Number
    (+ Lambda Lambda)
    (if0 Lambda Lambda Lambda)
    (letrec ((Identifier Identifier ...) Lambda) Lambda)
    (set! Identifier Lambda)
    (Lambda Lambda ...)

 Identifier is a: 
    Symbol

Develop an interpreter for Lambda. The interpreter consumes an S-expression. It first checks that the S-expression belongs to Lambda and produces an abstract syntax tree (ast); if not, it annotates the abstract syntax tree with error messages and produces the annotated ast. Its second task is to check that the given Lambda expression is closed, that is, all variable occurrences are bound via a surrounding lambda, let, or letrec construction. If a variable is free, it is replaced with a string of the format

"free variable occurrence: <variable name>" where <variable name> is replaced with the variable name. Finally, the interpreter determines the value of the given expression. The value is either a number or the representation of a function. The evaluation of these expressions proceeds like those of similar Scheme expressions. For an if0-expression, the interpreter compares the result of the first subexpression to 0; if the result is 0, the interpreter determines the value of the second subexpression, otherwis that of the third subexpression.

Develop a Lambda expression that computes the product of 2 to 10. (Yes, the answer is 20, but once you have the expression you can easily compute other products.)

Develop the interpreter proper in two stages. The first version processes all forms of expressions except for set!-expressions and letrec-expressions. Simply use error to abort the program if the ast contains either one of these expressions. The second version copes with the entire language. In contrast to Scheme, a set!-expression produces a value, namely the old value of the identifier. Your solution must contain two definitions of the core function. High-light the differences.

Optional: Develop an interactive Lambda processor, which reads an expression (from standard input), interprets it, and prints the result. Print a number as a number, a closure as "<closure>", and an (annotated) ast as a pretty-printed expression.

The first stage is due on Monday 22 October 2001 before class.

The second stage is due on Monday 29 October 2001 before class.

Expected size: 500 lines