COSC 3410 Programming Languages

Fall 2011

Homework Assignment #8

Recursion and S-Expressions

Due: Wednesday, Nov 09, 11:00am CST
Submit: Turn in Scheme source files called "hw8.scm" (your interpreter) and "hw8-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 #7 to include the following productions:

<expr>	::=	( let* ( { ( <id> <expr> ) }* ) <expr> )
<expr>	::=	( letrec ( { ( <id> ( lambda ( { <id> }* ) <expr> )) }* ) <expr> )

Pull all primitive operators out of your grammar and into a default environment.

Get your S-expressions to work properly if you have not done so already.

Parser

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

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

Interpreter

Modify your interpreter to operate over the new syntax, with special attention to the nested and recursive binding properties of let* and letrec.

Provide a top-level function run that takes a string of concrete syntax in our language, scan&parses it, and runs it through your interpreter with the correct default environment.

Example:
> (run "(letrec ((fact (lambda (x) (cond ((equal 0 x) 1) (else (mul x (fact (sub x 1)))))))) (fact 5))")
> 120

Notes:

• Your interpreter should be creating an internal representation of S-expressions based on a define-datatype of your design. The primitive operators cons, cdr, and so forth, should be operating over your internal representation, not Scheme's native representation. For this to work out properly, there must be judicious "unwrapping" of your S-expressions whenever it is necessary to translate back to Scheme's native representation.
• 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.