Project #5: μλ

Submit: Turn in two Scheme source files called hw5.scm and hw5-test.scm using the turnin command on morbius.mscsnet.mu.edu or one of the other Systems Lab machines.

Work is to be completed in teams of two. Be certain to include both teammates names in the file. You may submit multiple times, but only the last turnin will be kept. The automatic submission system will not accept work after the deadline. (If both partners are submitting work to TA-Bot -- which isn't a bad idea to get twice as much automated testing done during the week -- please be sure that one partner overwrites with a blank submission, or at least that the versions are identical. If the TA has to grade two separate versions of the project from a team, she is authorized to enter the lower of the two grades into the gradebook for that team!)

Include a comment block at the very top of each file that contains the following:

  ; COSC 3410 - Project [#]
  ; Explain briefly the functionality of the program.
  ; @authors [your names]
  ; Instructor [your instructor]
  ; TA-BOT:MAILTO [your email addresses]

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 hw4-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 new 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.


[back]

[Revised 2021 Mar 05 13:52 DWB]