MCS-287 Lab 2 (Spring 2014)

Due April 9, 2014

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 4 Java interfaces and 14 Java classes (one of which is just for testing). Your first step should be to orient yourself using the documentation. In looking over the documentation, start by reading about the 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. I have packaged this as an Eclipse project that you can download in a zip file, After you download this file, you can go into Eclipse's File menu, select Import, then from the General category select "Existing Projects into Workspace". This should allow you to select the downloaded Interpreter project to import. Be sure to look at, the JUnit test class, 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 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 run the Interpreter project's FactorialTest as a JUnit test, you should see that the first test case, fFiveInEnv2, passes. This confirms that 120 was calculated 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 results that are formatted as shown within FactorialTest's fFiveToString, sixMinusOneToString, and fBodyToString test cases. Thus, when you are done these three test cases should pass.

Extension 2: Adding let val expressions

Fill in the LetVal class (which I provided as a stub) such that the letValInEnv1 and letValToString test cases pass. (This assumes you've already done Extension 1. If not, you'll only get letValInEnv1 to pass now and should get letValToString to pass once you've also completed Extension 1.)

Extension 3: Adding let fun expressions

Fill in the LetFun class (which I provided as a stub) such that the letFunInEnv3 and letFunToString test cases pass. (This assumes you've already done Extension 1. If not, you'll only get letFunInEnv3 to pass now and should get letFunToString to pass once you've also completed Extension 1.)

If you do both Extension 2 and Extension 3, then once they are both completed you should also get the nestedLetsInEnv0 test case to pass and (with Extension 1 also complete) the nestedLetsToString test case.

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 anoter JUnit test class, LambdaTest, analogous to FactorialTest to verify that your new kind of expression works correctly and that it has a toString method that returns a result like "(fn y => ((+ x) y))".

Extension 5: Consing up lists

So far, the only values are Integers and Functions. Add support for lists of integers. You can start with the variant of Webber's IntList that we discussed in class. (In Eclipse, create a new class called IntList. Then copy the code from my web page and paste it into your newly created class.)

Modify the InitialEnvironment to include a cons or :: operation.

Try your new feature out by writing a JUnit test class 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 class should contain test cases for 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 class 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 the function f in 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);

Submitting your work

The simplest way to submit your work is as follows. Use Apple's Mail program to create a mail message addressed to me. In Eclipse's Package Explorer, select all the .java source files that you created or modified and drag and drop them into the mail message before sending it to me.