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]