COSC 3410 Programming Languages

Fall 2011

Homework Assignment #7

Bindings and Closures

Due: Wednesday, Nov 02, 11:00am CDT
Submit: Turn in Scheme source files called "hw7.scm" (your interpreter) and "hw7-test.scm" (a SchemeUnit testsuite for your interpreter) using the turnin command on the Systems Lab machines. Include the names of all authors at the top of the files in a comment block.
Work may be completed in pairs. Each team should have only one member turnin.

The Grammar

For this assignment, ammend the grammar from HW #6 to include the following production:

<expr>

::=

( let ( { ( <id> <expr> ) }* ) <expr> )

Add primitive operators cons, car, cdr, list, empty-list, and empty?.

Parser

Use the SLLGEN parser generator system to specify your lexical and syntax rules, and automatically build your parse function.

Modify your existing unparse function to work with the new abstract syntax and parse function.

Interpreter

Modify your evaluate function to operate over the new syntax, and enable lambda expressions and applications.

Notes:

Introduce an abstract data type to represent closures, as discussed in lecture. Check for proper numbers of parameters when applying a closure to its arguments.

Introduce an abstract data type to represent general S-Expressions of the type manipulated by cons, car, cdr, and list. The empty-list primitive takes no arguments, and should return your abstract data type for an empty list. The empty? predicate evaluates to true if and only if its argument is an empty list, false otherwise.

Check rigorously for errors in the input, or for invalid expressions.

Appropriate errors should be thrown if your interpreter encounters any trouble. See the eopl:error construct used in the text. Think carefully about what kinds of errors the interpreter can encounter.

Here's an excellent testcase once your interpreter is fully functional:
> (run "((car (car (cdr (list (lambda (x) (add x 1))
          (cons (lambda (y) (mul y 2))
              (lambda (z) (mod z 3))) ))))
    (let ((x 5) (y 10) (z 20))
      (if (lesser y z)
        (div 100 y)
        (sub 100 x))))")
> 20