COSC 3410 Programming Languages

Homework Assignment #6

μ_REC

Due: Thursday, March 26 @11:59PM

Submit: Turn in two Scheme source files called "hw6.scm" and "hw6-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 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

<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