CS 441 Assignment 3: Semantics

This assignment is due thursday Feb 29 at 10:30am, by electronic submission.

Read Sections 5.5, 5.6, and 5.7 of EOPL for background. Feel free to use the parser from the model solution if you have trouble with yours.

Part 1: A meta-circular interpreter

Write a meta-circular interpreter that takes abstract syntax trees produced by your parser from the previous assignment and returns the value of the expression. Support the following subset of Scheme:

 e ::= n                  
     | #t                 
     | #f                 
     | ()                 
     | (quote x)          
     | x
     | (if e e e)         
     | (lambda (x ...) e) 
     | (let ((x e) ...) e)
     | (let* ((x e) ...) e)
     | (e e ...)

where n is a number, x is a variable, and ... means zero or more of the previous item. Interpret free variables from the following set as primitives:

+ * - / = not eq? symbol? number? cons car cdr pair?

(You may add to this set at your discretion.) Environments should map variables to values. Lambda-expressions should be represented as procedures.

The composition of your parser and this interpreter should be called eval1 (that is, eval1 takes an S-expression, parses it, and evaluates it).

Part 2: A first-order interpreter

Perform a first-order transform on your interpreter from part 1. The new interpreter should behave identically. Call the new interpreter eval2.

Part 3: Set! and Letrec

Working from the interpreter from Part 2, extend the language with the following forms:

 e ::= ...
     | (set! x e)
     | (letrec ((x f) ...) e)
     | (begin e e ...)

where f must be a lambda-expression. Environments should now map variables to boxes.

The composition of your parser and this interpreter should be called eval3.

Part 4: Dynamic Scoping

Add the following form to the interpreter of part 3:

 e ::= ...
     | (dynamic-let ((x e) ...) e)

Variables bound by dynamic-let should have dynamic extent (fluid binding). See EOPL 5.7.2.

There is no need to build a separate interpreter for part 4. Simply include dynamic-let in eval3.

Package all three interpreters together into one file for submission. Include only a single parser that can handle all of the language features.