Extra Credit Programming
Assignment 4xc: |
|
Preparation Create a programs/4xc directory within your comp411 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.
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
creates a new variable x that is synonymous y if y is a ref (box) (synonomy means both variables are bound to the same box); otherwise, it boxes the value of y and binds that box to x. So variables declared as refs are always bound to boxes.
An assignment expression
x <- y
"left-hand" evaluates x, confirms that x is 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,
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.
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
Make sure that your README file is structured correctly:
| 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 comp411/programs/4xc on CLE@R and type the command
/coursedata/courses/comp411/bin/turnin411 4xc
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.