COSC 152 Programming Languages
Fall 2007
Homework Assignment #7
Recursion and S-Expressions
Due: Friday, Nov 02, 12:00PM CDT
Submit: E-mail electronic
copy to professor, with a subject header "COSC 152 HW#7".
Work may be completed in pairs. Each team should submit only once. Be
certain to put both team member names on work submitted. It would be
courteous to carbon-copy your partner when e-mailing the final
submission.
The Grammar
For this assignment, extend the grammar from
HW #6
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
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,
with special attention to the nested and recursive binding properties of
let* and
letrec.
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 2007 Oct 26 11:55 DWB]