COSC 3410 Programming Languages

Homework Assignment #5

μλ

Deadline Extended: Tuesday, March 3 @11:59PM

Submit: Turn in two Scheme source files called "hw5.scm" and "hw5-test.scm" using the turnin command on the Systems Lab machines.

Work is to be completed in teams of two. Your source file should be in the EoPL dialect ("#lang eopl" at top of file) supported by DrRacket, and should not make use of non-standard features like comment boxes that produce an XML file rather than a flat text .scm file.

At the bottom of your hw5.scm, please include the line:

(provide scan&parse run)

Your hw5-test.scm file should be a SchemeUnit testsuite, as shown in class.

The Grammar

Extend your grammar from the previous assignment to include the following productions:

<expression>    ::=    ( cond { ( <expression> <expression> ) }* ( else <expression> ) )
    cond-exp (ifs thens else-exp)
     |    ( lambda ( {<symbol>}* ) <expression> )
    proc-exp (vars body)
     |    ( <expression> {<expression>}* )
    call-exp (rator rands)

Remove the productions for the eleven built-in operators (add, sub, mul, div, mod, equal, lesser, greater, and, or, and xor,) and add these as primitive operators in your default environment.

This language is a close relative to the PROC language of EoPL Chapter 3, with more familiar Scheme syntax, and extensions corresponding to exercises 3.11 (simplifying operators), 3.12 (cond expressions), 3.21 (multiple arguments), and 3.22 (unified call syntax).

Parser

Use the SLLGEN parser generator system to specify your lexical and syntax rules, and to automatically build your abstract syntax tree types and scan&parsefunction.

Your scanner should not require alterations from the previous assignment. Your grammar specification will actually become much shorter, even though it will be more powerful.

Interpreter

Augment your μLET interpreter code from the previous assignment with code from the PROC interpreter in EoPL section 3.3, (particularly pages 79 and 80) to interpret the μλ language. Remove the interpreter code for all of the built-in primitive operators; these should all now be executable call-exps referencing primitive methods stored in your interpreter's default environment.

Your interpreter should still be executed with the run function:

run : String → SchemeVal
Usage: (run "pgm") = v, the Scheme value that is the result of running the program "pgm" in your interpreter.

Examples:
> (run "((lambda (x y) (add x y)) 10 3)")
13
> (run "(cond (#t 10) (else 20))")
10
> (run "((lambda (x) (cond ((lesser x 0) (sub 0 x)) (else x))) 10)")
10
> (run "((lambda (x) (cond ((lesser x 0) (sub 0 x)) (else x))) (sub 0 10))")
10

All of your testcases from the previous assignment should still work.

Note that as a side-effect of the changes for exercises 3.11 and 3.22, it is no longer practical to have the grammar differentiate between <boolexp> and <expression>. This means that your parser may accept some grammatically correct testcases that will cause run-time interpreter errors when a non-Boolean expression appears where a Boolean should be. We will address this shortcoming in a future assignment.