COSC 3410 Programming Languages

Homework Assignment #4

μ_LET

(Updated) Due: Friday, February 21 @11:59PM

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

NOTE: The turnin command overwrites old submissions. Thus, you must submit both files at the same time: turnin -c cosc3410 hw4.scm hw4-test.scm

This (updated) SLLGEN example will be useful.

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 hw4.scm, please include the line:

(provide scan&parse run)

Your hw4-test.scm file should be a SchemeUnit testsuite

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