COSC 152 Programming Languages

Fall 2006

Homework Assignment #7

Bindings and Closures
Due: Friday, Oct 27, 2:00PM CDT
Submit: E-mail electronic copy to professor, with a subject header "COSC 152 HW#7".
Work may be completed in groups of up to three students. Each group should submit only once. Be certain to put all team member names on work submitted. It would be courteous to carbon-copy your team mates 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> )

Add primitive operators cons, car, cdr, list, empty-list, and empty?.
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, and enable lambda expressions and applications.

Notes:

  • Introduce an abstract data type to represent closures, as discussed in lecture. Check for proper numbers of parameters when applying a closure to its arguments.
  • Introduce an abstract data type to represent general S-Expressions of the type manipulated by cons, car, cdr, and list. The empty-list primitive takes no arguments, and should return your abstract data type for an empty list. The empty? predicate evaluates to true if and only if its argument is an empty list, false otherwise.
  • The letrec construct is discussed extensively in EoPL 3.6, and in lecture. Nevertheless, this is our most challenging addition to the Interpreter thus far, and you should allocate time appropriately to tackle letrec after you have everything else working.
  • Check rigorously for errors in the input, or for invalid expressions. Include your testcases; part of the credit for this assignment will go for proof of rigorous testing.
  • 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.

    • Here's an excellent testcase once your interpreter is fully functional:
    > (run "((car (car (cdr (list (lambda (x) (add x 1))
              (cons (lambda (y) (mul y 2))
                  (lambda (z) (mod z 3))) ))))
        (let ((x 5) (y 10) (z 20))
          (if (lesser y z)
            (div 100 y)
            (sub 100 x))))")
    > 20

    Back