MCS-287 Lab 2 (Spring 2009)

Due April 6, 2009

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

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,, or a jar file, interpreter.jar. Be sure to look at (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.

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 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.

Extension 2: Adding let val expressions

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

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.)

Extension 3: Adding let fun expressions

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)

could be constructed in Java as follows:

new LetFun("f", "n", fBody, fFive)

assuming that fBody and fFive have the definitions given in

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.

Extension 4: Adding lambda expressions

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.

Extension 5: Consing up lists

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

Extension 6: Fancier list processing

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);