Programming Assignment 4: Imperative Jam

Points: 100

Files

Some Simple Test Inputs

Overview

Preparation   Create a programs/4 directory within your comp411 directory. All of your files for this assignment should be stored in the programs/4 subdirectory.

Teamwork   You are strongly encouraged to do this assignment and all other programming assignments using pair programming. When you submit your assignment, indicate the composition of your team (names, student ids, and email addresses) in your README file.

If you cannot find a partner and would like one, post a message to our Piazza page and we will try to find one for you. Teams of more than two members are not permitted.

Task   Your task is to extend and modify the nine interpreters from Assignment 3 (using either your solution or the posted class solution) from Assignment 3 to support imperative programming by adding ML-style reference cells and blocks. In particular, you will add the unary operators ref and ! and the binary assignment operator <-, and blocks consisting of a non-empty sequence of expressions enclosed in braces ({ and }) and separated by semicolons (i.e., the final expression in the sequence does NOT have a semicolon following it). In other words

Exp           ::= ...
                | Block
Block         ::= '{' PropStatList '}'
PropStatList ::= Exp { ; Exp}*
Unop          ::= ... | ref | !
Binop         ::= ... | <-
Prim          ::= ... | ref?

Note that a PropStatList is identical to a PropExpList except for the separator symbol ; instead of ,. You may want to exploit the commonality in your parser. We use the phrase "Stat" instead of "Exp" because with the addition of mutable cells, evaluating an expression can modify program state (the contents of mutable cells). From a strictly syntactic viewpoint, there is no difference between statemens and expressions. But we stil try to use the term statement to refer to an expression where mutation is possible and the term expression (more accurately pure expression) where no mutation is possible.

You must modify your lexer and parser to accept Blocks as well as the new unary operators ref and !, the new binary operator <-, and the new primitive function ref?. The supporting code for this assignment includes a class solution to Assignment 3. In future assignments, there will be no additional supporting code.

Adding ref cells and assignment   The unary operation ref E evaluates the expression E to produce an arbitrary value V, creates a new box b holding V and returns the box b.

The unary operation ! E evaluates the expression E to produce a value which must be a box and returns the contents of the box. If the value of E is not a box, the interpreter generates a run-time error (EvalException).

The binary operation E1 <- E2 evaluates the expression E1 to produce a value V1 that must be a box, evaluates E2 to produce an arbitrary value V2, stores V2 in box V1, and returns the special value unit (which is a legal Jam value, unlike the "undefined" value used in call-by-value recursive let). If V1 is not a box, then the interpreter generates a run-time error. The unit value can appear anywhere in a computation, but many primitive operations (those for which it makes no sense) reject it as an illegal input; it is analogous to the value (void) in Scheme.

A box is a Jam value and can be returned as the result of an expression. When converted to a string, the output of a box shoud be (ref <value>). This expression

let x := ref 10; in {x <- ref 17; x}

should evaluate to the JamVal that is displayed as the string

(ref (ref 17))

in call-by-value and call-by-need. In call-by-name evaluation, your interpreter should display the string

(ref 10)

since x the binding of x is re-evaluated for every occurrence.

You will have to modify your "toString" function to support the correct display of boxes. Equality for boxes is based on the address of the box, not the contents, i.e. the expression

let x := ref 10; y := ref 10; in x = y

evaluates to false regardless of the semantics for let (call-by-value, call-by-name, call-by-need).

The primtive function ref? acts like all other something? primitive functions in that it accepts one argument, which can be of any type, but only returns true if that argument is a box, and false in all other cases.

Adding blocks   The block { e1; ...; en }, n > 0, evaluates e1, ... , en in left-to-right order and returns the value of en. The expressions e1, ... , en may evaluate to the unit value without aborting the computation. In the Jam grammar, a Block is a an additional form for an expression analogous to map, if, and let. Hence, it cannot appear as the first argument in a binary expression unless it is enclosed in parentheses. The “empty block” is a parser error (ParseException).

Optional extra credit (10 points)   Devise a Jam program that exhibits different behavior for eight of the nine modes of interpretation. It should not generate a run-time error in any of the nine cases, but it may diverge in one case.

Testing   You are expected to write unit tests for all of your non-trivial methods or functions and submit your test code as part of your program. For more information, refer back to Assignment 1.

All versions   The interface of all versions remains identical to that in Assignment 3.

Testing and Submitting Your Program

The directory tests contains a test file Assign4Test.java with some very simple unit tests for your program.

Your program directory should only contain the files that you want to submit. We will subsequently provide you with test scripts similar to the ones we provided for Assignment 3. Running these scripts will alert you to any problems with your directory configuration. We will also place a few addtional test programs in the directory tests.

Make sure that your program passes the sample unit tests and works with our grading script before submitting it. Create a README file in the your directory program/4 that

• contains nothing but the user names of the team members in lines 1 and 2 and a blank line as line 3,
• outlines the organization of your program, and
• specifies what testing process you used to confirm the correctness of your program.

We have provided a sample README for your reference. Make sure that your README file is structured correctly:

1. It has to be named README (all upper case, no .txt or anything)
2. It has to be in the assignment's "root directory", e.g. ~/comp411/programs/4
3. The first two lines should only contain your usernames and nothing else. The third line should be blank (if you're working alone, leave lines 2 and 3 blank), e.g.:
   

   mgricken dmp This is where the readme text starts.

Any test data files for your program must be stored in the programs/4 directory. Please make sure you submit your unit tests! You cannot get credit for parts not submitted!

Each procedure or method in your program should include a short comment stating precisely what it does. For routines that parse a particular form of program phrase, give grammar rules describing that form.

Please make sure to remove or disable all debug output before submitting. Excessive use of print statements considerably slows your interpreter and thus testing your project down. If your interpreter generates a timeout error because debug output slows it down, you may not get credit for the test cases that took too long.

To submit your program, make sure that everything that you want to submit is located in the directory comp411/programs/4 on CLE@R and type the command

~comp411/bin/turnin411 4

from within the comp411/programs directory.

The command will inform you whether or not your submission succeeded. Only submit one copy of your program per team. If you need to resubmit an improved version your program, submit it from the same account as the original so that the old version is replaced.