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 four possible extensions to the interpreter, which are numbered 1-4. You are required to do extension 1 and you are also required to do either extension 2 or 3. Thus, everyone should submit the code for at least two extensions. However, for extra credit, you can also submit the code for a third or even fourth extension. The only limitation is that you can't do extension 4 unless you have done extension 3. Thus, your possibilities for full credit are {1,2} or {1,3} and your possibilities for extra credit are {1,2,3}, {1,3,4}, or {1,2,3,4}. Regardless which options you select, you should just turn in the code for the classes that you have modified or added.
The interpreter consists of 15 Java source files; you can download them all at once in the file interpreter.zip, which you can then unzip to provide an interpreter directory containing the 15 files.
The most important of the 15 files for you to understand are the three containing the basic organizational interfaces of the interpreter:
Environment, a mapping
from variable names to their values. (Different environments come
into play as scopes are entered and functions are invoked.) The
get method is passed a variable name and returns the
value associated with that variable in this environment.
Function, used as the
runtime representation of a function. (As an example, the initial
environment maps the name + to a value of type Function.)
The apply method is used to apply the function to an
argument and returns the value computed by the function. As in ML,
all functions are applied to exactly one argument.
Expression, the
representation of an expression to be interpreted. The
eval method takes as its argument the Environment in
which the expression should evaluate itself and returns the value that
results. (The environment is relevant because the expression might
contain variables whose values depend on the environment.)
The notion of an interface in Java isn't explained by Webber until section 15.2, but I hope won't be too much of a stumbling block for you. If you are having trouble, please read ahead that one section and/or ask me for help.
Eleven of the Java source files contain classes that provide specific implementations of the three basic interfaces. You may not need to read or understand all of these. One of the most important skills to learn for real-world software development is the ability to confine your attention to relevant portions of a program. (Do you think the developers adding features to Microsoft Office really read and understand the whole proram first?) The classes are listed here under their respective interfaces:
Of the various classes implementing the Environment interface,
the Primitives class is used for the initial
environment, which binds the names such as + and - to the
corresponding primitive functions. The Binding class is used to
extend a parent environment with one additional binding of a name to a
value. It is used for the parameters of user-defined functions and could also be used for the equivalent of
val declarations in ML. The FunctionBinding class is
used for the equivalent of fun declarations in ML. Like
a normal Binding, it adds one more name to a parent environment. The
difference is that the value is always formed by evaluating a
lambda expression in a way
that allows the function to be recursive. (As
described later, the representation of a lambda expression is called an
Abstraction.)
The variable named + has an instance of IntPrim as its
value, as do the other primitive
arithmetic operations. As in
ML, each function is applied to exactly one argument. So as to avoid
the need for tuples, the primitive functions are defined in curried
form. For example, + takes one Integer argument and returns a second
function which, when given another Integer argument, produces the sum
as its value. The class IntComparison is quite similar; the only
difference is that these primitive Functions produce Boolean results.
Finally, the Closure class is used to represent functions produced
within the functional program being interpreted. That is, evaluating
an Abstraction results in a Closure.
To understand the various classes implementing the Expression interface, consider the following five ML expressions:
5 n f(5) if p then x else y fn f => f(5)
The Java objects to represent these expressions in our interpreter would be constructed as follows:
new Constant(new Integer(5))
new Variable("n")
new Application(new Variable("f"), new Constant(new Integer(5)))
new Conditional(new Variable("p"), new Variable("x"),
new Variable("y"))
new Abstraction("f", new Application(new Variable("f"),
new Constant(new Integer(5))))
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 shown in the immediately preceding example. 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, just as the preceding five expressions were. For testing, I have provided you with a main program written in Java, FactorialTest, which laboriously constructs the equivalent of
fun f n = if n = 0 then 1 else f(n-1)*n; f 5;
Therefore, if you compile all the java files using
javac *.java
and then run the test program with
java FactorialTest
you should see 120 printed out--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 what expressions the test program is evaluating.
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 two more lines to FactorialTest, one which
prints out the Expression named fun and one that prints
out fFive. When you run FactorialTest, you should now
see an intelligible printout of what it is evaluating to produce the
result of 120.
Add another class of Expression, Let, such that the following ML expression
let val x = 5 in f(x) end
could be constructed in Java as:
new Let("x", new Constant(new Integer(5)),
new Application(new Variable("f"), new Variable("x")))
Test this in FactorialTest as a new definition for
fFive.
Next, add another class of Expression, Letrec, such that the following ML expression
let fun f n = if n = 0 then 1 else f(n-1)*n
in f(5)
end
could be constructed in Java as follows:
new Letrec("f", new Abstraction("n", ...),
new Application(new Variable("f"),
new Constant(new Integer(5))))
More realistically, rather than nesting everything in this one big
Java construction, you should modify FactorialTest to make use of its
existing definitions of fun and fFive, so
that all you have to construct is the following
new Letrec("f", fun, fFive)
So far, the only values are Integers and Functions. Add a class
List. I don't particularly care for Webber's version and would
instead suggest an interface with two implementation classes,
EmptyList and NonEmptyList. Whichever approach you take, you need to
write appropriate methods for toString. You may find
this easier if you also add some other helper method.
Now augment the Primitives class with the cons (or ::) operation;
if you take my suggested approach, this can work using the constructor
for NonEmptyLists.
Try your new features 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 classes to test for emptiness and to your NonEmptyList class for finding the head and tail. (Or, if you use Webber's style of List, add similar methods there.) Add the appropriate functions to the Primitives in order to access these new features.
You should extend your test program from Extension 3 to include a
definition of map. (Note: this is not another primitive.
This is something that you would write in the style of FactorialTest.)
Try out the equivalent of
map (fn x => x * x) (intsFromTo 1 5)