MCS-287 Lab 2 (Spring 2007)

Due March 23, 2007

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 provided interpreter

The interpreter consists of 15 Java source files; you can download them all at once in the file, 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:

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:

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.

Extension 1: Displaying expressions

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.

Extension 2: Adding let expressions

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)

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)

Extension 3: Consing up lists

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

Extension 4: Fancier list processing

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)