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

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

<program>	::=	<expression>
		a-program (exp1)
<expression>	::=	<number>
		const-exp (num)
	|	<identifier>
		var-exp (var)
	|	( if <boolexp> <expression> <expression> )
		if-exp (exp1 exp2 exp3)
	|	( let ( { ( <identifier> <expression> ) }* ) <expression> )
		let-exp (vars exps body)
	|	( add <expression> <expression> )
		add-exp (exp1 exp2)
	|	( sub <expression> <expression> )
		sub-exp (exp1 exp2)
	|	( mul <expression> <expression> )
		mul-exp (exp1 exp2)
	|	( div <expression> <expression> )
		div-exp (exp1 exp2)
	|	( mod <expression> <expression> )
		mod-exp (exp1 exp2)
<boolexp>	::=	#t
		true-exp
	|	#f
		false-exp
	|	( equal <expression> <expression> )
		eq-exp (exp1 exp2)
	|	( lesser <expression> <expression> )
		lt-exp (exp1 exp2)
	|	( greater <expression> <expression> )
		gt-exp (exp1 exp2)
	|	( and <boolexp> <boolexp> )
		and-exp (exp1 exp2)
	|	( or <boolexp> <boolexp> )
		or-exp (exp1 exp2)
	|	( xor <boolexp> <boolexp> )
		xor-exp (exp1 exp2)

This language is a close relative to the LET language of EoPL Chapter 3, with more familiar Scheme syntax, and extensions corresponding to exercises 3.8 (comparison operators), 3.14 (Boolean expressions), and 3.16 (multiple let variables).

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&parse function.

Your scanner specification must accept Boolean literals "#t" and "#f"; note that these literals must scan into distinct tokens, or you will not be able to tell them apart later.

Interpreter

Modify the LET interpreter code in EoPL section 3.2, (particularly in Figures 3.7, 3.8, and 3.9) to interpret the μ_LET language. You will need the environment API from Homework #2, and the Expressed Value (ExpVal) data structures and functions detailed in Figure 3.7. Add an expval->schemeval function that converts any ExpVal into a printable Scheme value:

expval->schemeval : ExpVal → SchemeVal
Usage: (expval->schemeval e) = v, translates interpreter's representation of values back into equivalent, printable Scheme values.

Your interpreter should 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 "5")
5
> (run "(sub 10 3)")
7
> (run "(div 10 3)")
3
> (run "(if #f 10 3)")
3
> (run "(add (sub 1 2) (mul (div 20 7) (mod 101 10)))")
1
> (run "(if (lesser 1 2) (mul 3 4) (div 49 7))")
12
> (run "(let ((x 5) (y 6)) (if (and (greater x 10) (equal y 6)) 20 40))")
40