Principles of Programming Languages
Mar. 22, 2005
Due Apr. 5
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.