Programming Assignment 4xc: Imperative Jam

Offered: Friday, October 9, 2009 Due: 12:00 noon, Wednesday, October 21, 2009

Files

Some Simple Test Inputs

Overview

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

Teamwork   You are required 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.

Task   Your task is to extend and modify the call-by-value/eager interpreter from Assignment 3 to support an assignable variable'' model of mutability that is more general than the standard Algol model. Algol-like Jam is call-by-value/eager Jam from Assignment 3 augmented by i a binary assignment operator <-, and optional ref modifiers in front of map parameters and let variables and (ii) compound statements consisting of sequences of expressions called {\em blocks}. (Blocks have the same syntax and semantics as in Assignment 4.) The only assignable variables in Algol-like Jam are those let variables and procedure parameters that are explicitly declared as ref variables. As in Algol, no dereference operator is required because assignable variables (boxes) are coerced to their contents in right-hand'' contexts.

We suggest that you use your lexer and parser from Assignment 4 as the basis for building the lexer and parser for this assignment. In contrast to the Imperative Jam language introduced in Assignment 4, the unary operators ref and ! do not exist in Algol-like Jam. There are no ref values other than ref variables appearing in left-hand contexts.

Adding assignable variables, assignment, and blocks

The binary operation e <- E "left-hand" evaluates the expression e to produce a value v that must be a box, "right-hand" evaluates E to produce an unboxed value V, stores the value V in the box v, and returns the special value unit which is distinct from the undefined'' value used in call-by-value recursive let. This value cannot be stored as the contents of a box, but may otherwise appear anywhere in a computation.

The block {e1; ... ; en}, n > 0, evaluates e1, ..., en in left-to-right order and returns the value of en. Note that any of 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 operation unless it is enclosed in parentheses. The "empty" block is a syntax error.

Testing   You are expected to write unit tests for all of your non-trivial methods or functions. For more information, refer back to Assignment 1.

Testing Interface   The interface used by our test code is identical to that in Assignment 3.

Left and Right Hand Evaluation

The Algol-like dialect of Jam avoids the need for a explicit dereferencing operator (the unary ! operator used in ML to get the contents of a ref) by coercing boxed values to their contents when they occur in right-hand contexts.

Right-hand contexts include (i) the arguments to primitive operations and operators other than the first argument to <- as described above, (ii) argument expressions bound to non-ref parameters in map applications, (iii) the right-hand sides of definitions of non-ref variables in let constructions, (iv) test expressions in conditionals, and (v) top-level expressions (expresssions initially passed to the interpreter).

A left-hand context is any context that is not a right-hand context. Left-hand contexts include (i) the right-hand sides of definitions of ref variables in let constructions, (ii) argument expressions bound to ref parameters, (iii) the left-hand sides of assignments, (iv) the bodies of let constructions and procedures, (v) the consequent and alternative expressions in conditionals and (vi) each of the expressions forming a block. Note that the bodies of compound expressions (like {\tt let} construction and procedure ({\tt map}) applications are effectively be right-hand evaluated when the containing compound expressions appear in right-hand contexts.

This set of left-hand contexts is more extensive than in Pascal. In particular, the last last three contexts give above ((iv)-(vi)) are not treated as left-hand contexts in Pascal. In Algol-like Jam, a procedure call can return an assignable variable to a left-hand context---which is impossible in Pascal.

In this Jam dialect, a ref variable definition

  ref x := y


makes x and y synonymous if y is a ref (box); otherwise, it stores the value of y as the contents of the ref.

An assignment expression

  x <- y


"left-hand" evaluates x, confirms that x be bound to a ref (box), "right-hand" evaluates y, (i.e. "left-hand" evaluates y, then coerces it to a non-reference if necessary), and stores this result in the box x. Note that it impossible for a ref (box) to have a ref (box) as its value because the value stored into a ref is always dereferenced!

The following program illustrates the intended syntax for this language.

let
ref x := 20;
ref y := 5;
z := 10;
swap := map ref x, ref y to
let z := x;
in {x <- y; y <- z}
in
{x <- x + y;
swap(x,y);
swap(x,z);
x * y * z}


In the body of the let,

• x is assigned the value 25,
• the values of x and y are swapped leaving x with the value 5 and y with the value 25,
• the values of x and the box ref z (since z is not a box, it is coerced to one by wrapping it in a ref) are swapped leaving x with the value 10, and
• the value 10*25*10 = 2500 is returned.

Note that the binding of a variable never changes; only the contents of boxes change. The values'' of x and y change because they are both bound to boxes and the contents of those boxes are changed by assignments. In contrast, the value of z cannot change because z is not bound to a box. To perform a swap involving z, the program places z inside a box (which becomes inaccessible once the call on swap returns).

Hint Left-hand evaluation is the fundamental mode of evaluation. This form of evaluation does not necessarily produce a ref as its result. Given an implementation of left-hand evaluation, it is trivial to generate a corresponding right-hand evaluator by coercing the result, if it is a ref, to its contents (which cannot be a ref).

Extending Algol-like Jam to a more realistic language Algol-like Jam does not include any mutable data structures like arrays or mutable records. When these are added, Jam must be able distinguish the components that are assignable fields and those that are not. Assignable fields should behave exactly like assignable variables. Such an extension is beyond the scope of this assignment.

Testing and Submitting Your Program

The directory tests contains the test file Assign4xcTest.java with some very simple unit tests for your program. These tests are far from comprehensive.

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/4xc 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.

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. ~/comp311/programs/4xc
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/4xc 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 comp311/programs/4xc on CLE@R and type the command

/coursedata/courses/comp311/bin/turnin311 4xc

from within the comp311/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.