Submit: Turn in two Scheme source files called hw6.scm and hw6-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 hw6.scm, please include the line:

(provide scan&parse run)

Your hw6-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>	::=	( let* ( { ( <identifier> < expression> ) }* ) <expression> )
		let*-exp (vars exps body)
	|	( letrec ( { ( <identifier > ( lambda ( { <identifier > }* ) <expression> )) }* ) < expression> )
		letrec-exp (p-names b-varss p-bodies letrec-body)

Add primitive operators cons, car, cdr, null?, emptylist, and list.

This language is a close relative to the LETREC language of EoPL Chapter 3, with more familiar Scheme syntax, and extensions corresponding to exercises 3.9 (list processing), 3.10 (list operator), and 3.33 (multiple letrecs).

Interpreter

Augment your μ_λ interpreter code from the previous assignment with code from the LETREC interpreter in EoPL section 3.4, (particularly page 86) to interpret the μ_REC language.

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 "(letrec ((fact (lambda (x) (cond ((equal 0 x) 1) (else (mul x (fact (sub x 1)))))))) (fact 5))")
120


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

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.

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 (mul x 2)) (z (mul y 2)))
      (if (lesser y z)
        (div 100 y)
        (sub 100 x))))")
> 20