In this lab assignment, you will work with a Java program that serves as an interpreter for a simple functional programming language. The first section describes the interpreter that I am providing you. The remaining sections describe six possible extensions to the interpreter, which are numbered 1-6. You are required to do Extension 1 and you are also required to do at least two of the extensions numbered 2 through 5. Thus, everyone should submit the code for at least three extensions. However, for extra credit, you can also submit the code for a fourth or even fifth or sixth extension. The only limitation is that you can't do Extension 6 unless you have done Extension 5. For grading, you should turn in the code you have written or modified.
The interpreter consists of 3 Java interfaces and 10 Java classes (one of which is just a main program for testing). Your first step should be to orient yourself using the documentation. In looking over the documentation, start by reading about the three interfaces, because they provide the main organizing principle for the interpreter. Once you understand the role each plays, you can drill down into the classes that implement them.
After you have browsed the documentation, you are ready to look more closely at the actual source code. You can download all thirteen source files together in either a zip file, interpreter.zip, or a jar file, interpreter.jar. Be sure to look at FactorialTest.java (the main program for testing), because it illustrates how the other classes are used.
In a realistic interpreter, we would have code that reads in expressions in some particular syntax (such as that for Scheme or ML) and constructs the corresponding nested objects of the various Expression classes, such as those constructed in the FactorialTest code. However, to allow you to focus on the core of the interpreter, I'm leaving out this lexical analysis and parsing code. As such, each expression to be evaluated needs to be manually constructed in Java.
If you compile all the java files in the interpreter directory using
javac *.java
and then run the test program with
java FactorialTest
you should see 120 printed out as the factorial of 5.
Even if the expressions are not read in using a human-oriented format, it would be nice if they could be printed out in such a format. That way you could see the expression the test program uses for the function's body and the expressions that it evaluates to compute 5 and then to compute the factorial of 5.
Add a toString method to each of the classes implementing
Expression. Each of these methods should take no arguments and
produce a String result. (By following this convention, the methods
will automatically be used whenever Java needs to convert an
Expression into a String, for example to print it out or to add it to
another String.) Your methods should produce something similar to
Scheme or ML syntax for the Expressions, though the details need not
be identical so long as the format is intelligible and
unambiguous.
To test your work, add three more lines to FactorialTest in order to print out the function's body and the two expressions that are directly evaluated. When you run FactorialTest, you should now see an intelligible printout of what is producing the result of 120.
Add another class of Expression, LetVal, such that the following ML expression
let val five = 6-1 in f(five) end
could be constructed in Java as
new LetVal("five", sixMinusOne, fFive)
assuming that sixMinusOne and fFive have
the definitions given in FactorialTest.java.
Test this by modifying FactorialTest. First, remove the definition
of env2. Then replace the evaluation
of fFive in env2 by an evaluation
in env1 of the LetVal shown above. (These
instructions assume you haven't previously done Extension 3. If
you did Extension 3, see its instructions regarding testing the two
extensions together.)
Add another class of Expression, LetFun, such that the following ML expression
let fun f n = if n = 0 then 1 else f(n-1)*n
in f(five)
end
could be constructed in Java as follows:
new LetFun("f", "n", fBody, fFive)
assuming that fBody and fFive have
the definitions given in FactorialTest.java.
Test this by modifying FactorialTest. Assuming you haven't done
Extension 2, your first step would be to remove the definition
of env1 and change env2 to be linked
directly to env0. Then replace the evaluation
of fFive in env2 by an evaluation
in env2 of the LetFun shown above.
If you have done both Extension 2 and Extension 3, you can
eliminate the definitions of both env1
and env2 and directly in env0 evaluate a
nested combination of LetFun and LetVal.
Add another class of Expression, Lambda, such that the following ML expression
fn y => x + y
could be constructed in Java as follows:
new Lambda("y",
new Application(new Application(new Variable("+"),
new Variable("x")),
new Variable("y")))
Write a testing program analogous to FactorialTest to verify that your new kind of expression works correctly.
So far, the only values are Integers and Functions. Add support
for lists of integers. You can start from Webber's version of IntList, one
of the variants we discussed (which are linked from the course web
page), or something else. You will need to provide an appropriate method
for toString.
Modify the InitialEnvironment to include a cons
or :: operation.
Try your new feature out by writing a testing program analogous to
FactorialTest but doing the equivalent of your previous lab's
definition of the intsFromTo function. To make sure your
code works with different size lists, your test program
should print out the result of evaluating several different
expressions, such as
intsFromTo 5 1 intsFromTo 5 5 intsFromTo 1 5
Add methods to your list implementation to test for emptiness and for finding the head and tail of a nonempty list. Add the appropriate functions to the InitialEnvironment in order to access these new features.
You should extend your test program from Extension 5 to include a
definition of map. (Note: this is not another primitive
in the InitialEnvironment. This is something that you would write in
the style of FactorialTest.) Try out the equivalent of
fun square x = x * x; map square (intsFromTo 1 5);
or, if you've done Extension 4,
map (fn x => x * x) (intsFromTo 1 5);