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.


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.


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.

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


[Revised 2011 Nov 01 18:15 DWB]