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.
Back
[Revised 2011 Nov 01 18:15 DWB]