Programming
Assignment 3: |
|
Preparation Create a programs/3 directory within your comp411 directory. All of your files for this assignment should be stored in the programs/3 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 your interpreter from Assignment 2 or the class solution for Assignment 2 (which has been refactored to facilitate writing Assignment 3) to:
The details of the each of these extensions is described in the following paragraphs.
The arithmetic unary and binary operators may only be applied to integer constants, otherwise the application of an arithmetic operator is an evaluation error.
Context-Sensitive Checking The context sensitive constraints on Jam syntax are most easily by performing a separate "checking pass" over the abstract syntax right after it has been constructed. There are two context-sensitive conditions that Jam programs must satisfy to be well-formed:
If you find either of these errors, throw a SyntaxException with a descriptive error message and abort execution.
The context-sensitive checker should be run before the expression is evaluated. Note that the context-sensitive checker does not care which unary or binary operator was used, or how many arguments were passed to a primitive function.
Safety Make your interpreter responsible to catching all Jam run-time errors. Do not rely on the run-time checking performed in executing Java/Scala code (meta-errors). All Jam run-time error messages should be of type EvalException generated directly by your interpreter.
Note: It is not enough to just wrap the entire interpreter in a try { ... } catch(Throwable t) { ... } block. The exception must be thrown where the Jam run-time error occurs.
Insufficient machine resource errors such as StackOverflow or OutOfMemory (heap overflow) are not classified as meta-errors. But you are welcome to catch the corresponding exceptions and report your own errors.
Recursive Let The recursive version of the let construct introduces a collection of recursive bindings just as we discuseed in class. We will not restrict the right hand sides of recursive let constructions to maps because many useful recursive definitions in Jam with lazy cons violate this restriction. Hence, the implementation of recursive let closely follows the implementation of the generalized version of rec-let construct in LC.
The only difference is that Jam recursive let may introduce several mutually recursive definitions where the corresponding closures all close over the new environment. Since we want invalid forward references in a Jam program to produce a meaningful error message rather than diverging, we will use an explicit list to represent the environment of bindings and destructively update it to create the self-references.
In a call-by-value application, we will initially bind each variable introduced in a let to a special value (such as Java null or a Scala Undefined object extending JamList) that is not a legal Jam value representation and will abort the computation if it is used as the input to any Jam operation. The interpreter evaluates the right-hand sides of the definitions in a recursive let in left-to-right order and destructively modifies each new binding in the environment as soon as the right-hand side has been determined.
In a call-by-name application, we bind each variable to a suspension (a closure of no arguments or thunk) for each right-hand side. Since a suspension wraps the right hand side of each let binding inside a lambda, the recursive environment can be constructed directly using a recursive binding construction (letrec or define in Scheme). No mutation is required.
Note that the validity of definitions in a recursive let depends on which semantics is used for Jam. Definitions that are valid for call-by-name or call-by-need lazy evaluation may be invalid in other evaluation modes. By this measure, lazy evaluation is better than conventional ("eager") evaluation and call-by-name/call-by-need is better than call-by-value.
Lazy cons For all three of your interpreters from Assignment 2, you will add two lazy cons evaluation options ("name lazy" and "need lazy") that defer the evaluation of both arguments of a cons construction. The data object representing the deferred evaluation is called a suspension. Given a cons node, the first and rest operations evaluate the corresponding argument expression in the environment where the expression would have been evaluated without laziness.
Lazy cons obeys the following equations:
first(cons(M,N)) = M rest(cons(M,N)) = if list?(N) then N else error
for all Jam expresions M and N, including expressions that diverge or generate run-time errors. Recall that list? is simply the disjunction of empty? and cons?.
The lazy versions of cons postpone evalution of argument expressions until they are demanded by a first or rest operation. You can use exactly the same suspension mechanism to support call-by-name and call-by-need lazy cons that you used to support call-by-name and call-by-need bindings in the previous assignment. In this case, the suspensions are stored in a cons structure rather than a binding slot in the environment. An embedded suspension is not evaluated until it is "probed" by a first or rest operation. Call-by-name lazy evaluation re-evaluates suspensions every time that they are probed. Call-by-need lazy evaluation evaluates a given suspension only once and caches the resulting value in the data constructor (cons cell in the case of Jam).
Please change the function that converts Jam values to a string representation (toString, string_of_value, etc.) so that lists are still displayed as lists in the form (1 2 3) as before, regardless of the cons mode used. You may want to abort processing lists longer than, say, 1000 elements and have them displayed ending in 998 999 1000 ...). However, we will not test this behavior. We will just require that lists up to 200 elements are displayed the same way as in the last assignment.
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.
In Assignment 2, the Interpreter supported three evaluation methods
callByValue() callByName() callByNeed()
In this assigment, the Interpreter class must support nine evaluation methods:
valueValue() nameValue() needValue() valueName() nameName() needName() valueNeed() nameNeed() needNeed()
where the first word in the method name specifies the policy for evaluating program-defined procedure applications (Jam maps) and the second word specifies the policy for evaluating applications of the data constructor cons. Hence the first three methods in the preceding list correspond to the three evaluation methods in Assignment 2.
As in Assignment 2, the Interpreter class must support two constructors: Interpreter(filename: String) which takes input from the specified file and Interpreter(inputStream: Reader) which takes input from the specified Reader. A given Interpreter object should support the repeated invocation of any of the nine public evaluator methods. As a result, the same Interpreter object can be used to test all forms of evaluation (as long as none of the evaluations diverges).
In summary:
/** Interpreter.scala **/
class EvalException(msg: String) extends RuntimeException(msg)
class SyntaxException(msg: String) extends RuntimeException(msg)
class Interpreter(reader: Reader) {
def this(fileName: String) { ... }
def valueValue: JamVal
def nameValue: JamVal
def needValue: JamVal
def valueName: JamVal
def nameName: JamVal
def needName: JamVal
def valueNeed: JamVal
def nameNeed: JamVal
def needNeed: JamVal
}
To produce intelligible output for computations involving lazy cons, your interpreter must force the complete evaluation of the answer up to a large depth bound (which is a constant in your program). In Scala, your toString() method for your lazy cons classes should use this depth bound to determine what to print.
If a computation produces an infinite answer, the large bound (on the order of 1000) on forcing depth prevents the forcing computation from diverging. An interactive user interface that allowed the user to request the expansion of an unevaluated node (to some depth) in an answer would be more satisfactory, but building such an interface is beyond the scope of a routine programming assignment.
For call-by-need lazy evaluation, the forcing operation can be implemented simply as a traversal that inspects the first and rest fields of every lazy cons node up to the specified depth and then returns its (modified) input. For call-by-name lazy evaluation, however, you will have to construct a new list using conventional "strict" (call-by-value) cons nodes.
The directory tests contains the Scala test file Assign3Test.scala containing some very simple unit tests for your program. We also suggest that you can make minor modifications to the test file Assign2Test.scala to create corresponding (and exceedingly incomplete) test files for this assignment.
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 2. 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/3 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/3 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/3 on CLE@R and type the command
/coursedata/courses/comp411/bin/turnin411 3
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.