Programming
Assignment 4: |
|
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, send an email to comp411@rice.edu 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 or one of the solutions for 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 sequence of expressions enclosed in { 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 ::= "{" StatementList "}"
StatementList ::= Exp | Exp ; StatementList
Unop ::= ... | ref | !
Binop ::= ... | <-
Prim ::= ... | ref?
You must modify your lexer and parser to accept this extended syntax 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 solutions to the previous assignment. In future assignments, there will be no 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 distinct from the “undefined” value used in call-by-value recursive let. If E1 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 be displayed as the string
(ref (ref 17))
in call-by-value and call-by-need. Call-by-name will display the string
(ref 10)
You will have to modify your "to string" 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.
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 > 1, 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 operation unless it is enclosed in parentheses. The “empty block” is a parser error (ParseException).
Optional extra credit (10%) 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. For more information, refer back to Assignment 1.
All versions The interface of all versions remains identical to that in Assignment 3.
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
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/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
/coursedata/courses/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.