This assignment has two parts, each worth 90% and 10% of the grades, respectively. Suggestions for how to proceed are given at the end. The assignment is due before class on Tuesday April 5. Please submit your file(s) as a single attachment (made using tar or zip if necessary) in an email to cse526ATcsDOTsunysbDOTedu.

Part 1. Implementation.

Write an interpreter for IMP-+Alias+IO, a simple imperative language that has I/O and aliasing. The language is IMP modified as follows.

1. It does not have boolean expressions; nor does it bother to include subtraction and multiplication in arithmetic expressions. Instead, it has two additional kinds of expressions: read and a after c. In another word, expressions have the syntax a ::= n | X | a1+a2 | read | a after c.

Expression read is a function, in the C sense, which returns the next value of the input stream, and moved the input pointer one place forward. It is very much like the C getchar() function.

Expression a after c execute command c and then evaluate expression a.

2. In if and while commands, the conditions are arithmetic expressions, using 0 for false and everything else for true. Also, there are three additional kinds of commands: write a, let X:=a in c, and alias Y to X in C.

Command write a writes the value of a on the output stream.

Command let X:=a in c declares variable X, initializes its value to the value of a and then executes c. All variables must be declared before used.

Command alias Y to X in c declares a local alias of the global variable X inside command c, so an update to Yalso updates the other and vice versa.

Part 2. Related requirements.

Language. You must do the implementation using Python.

Tests. Test your interpreter on the examples below and at least one more small example that does something more interesting. As in Homeworks 2 and 7, you are not asked to do parsing; directly build these examples into your internal representation. For each example, build a particular input stream for it too. For each example, turn in a printout of the example program and the input, output, and error streams.

name   program

err0   write X
err1   let X:=X in write X
err2   alias Y to X in write Y
err3   X:=1; write X

skip   skip

if0    if 0 then write X else write 0      should write 0
if1    if 1 then write 1 else write X      should write 1

while0 while 0 do write X                  should write nothing
while1 while 1 do skip                     should loop forever,
                                           until you kill it

seq    write 1; write 2                    should write 1,2

let    let X:=1 in write(X)                should write 1

assign let X:=12 in (write(X); X:=X+13; write(X))
                                           should write 12, 25

lets   let X:=0 in (write(X); let X:=1 in write(X); X:=X+2; write(X))
                                           should write 0,1,2

alias  let X:=0 in (alias Y to X in (Y:=1; write(X); X:=3; write(Y);
                                     let X:=5 in (write(X); write(Y));
                                     write(X); write(Y)))
                                           should write 1,3,5,3,3,3

after  let X:=0 in (write(X); write(X after(write(X);X:=1)); write(X))
                                           should write 0,0,1,1

read   write(read)                         should copy one value
                                           from input to output

reads  let X:=read; while X do (write(X+X); X:=read)
                                           should double input 
                                           until a 0 is read

First, define internal representation of expressions and commands, as in Homework 2. Then, define the evaluation and execution operations, similar to those in Homework 2, but with the following two major differences.

1. In IMP, identifiers are directly interpreted as locations, so different identifiers corresponds to different locations, and hence IMP does not support aliasing. Since IMP-+Alias+IO has aliasing, it is reasonable that identifiers be bound to locations, which are addresses of the store in some abstract machine. If X and Y are aliases for each other, then the they are bound to the same location. The binding of identifiers to locations is called an environment. The only commands that change the environment are let and alias. Updating the value of an identifier changes the contents of the store, as in Homework 2, but not which location the identifier is bound to. Looking up the value of an identifier is a two-step process: first look in the environment to see what location the identifier is bound to, and then look at the store what value is in that location.

2. In IMP, the configuration includes only the expression/command and the store. Since IMP-+Alias+IO has I/O, it is reasonable to include I/O stream in the configuration. I/O stream consists of input stream, output stream, and error stream. The input and output stream can be simple a list of numbers, and the error stream can be a list of string.

The evaluation and execution operations can be written to take arguments (Environemnt e, Store s, IOStream io) in addition to the argument expression and command, respectively.

Write your program using objected-oriented styles. As an indication of the amount of work, my ML code for this interpreter is (dense but) less than 100 lines. I'd say that your Java code would be at least two to three times as long.

NOTE: Consult Homework 2 solution to save work and avoid repeating errors.