Harvey Mudd College
Computer Science 60
Assignment 03

Java implementation of rex abstractions

Due Date: Due by midnight on the morning of Monday Feb. 17

Purpose

In this assignment, you will implement a subset of rex information structures as a library in the Java language. Ultimately, everything you learned in rex will then be transferable to Java. You will then be able to simply transcribe rex applications to Java. The same technique is applicable to transferring the techniques to other languages you may encounter in the future. The library you build is yours to keep forever, and could help you solve certain kinds of problems in the future. In the next assignment, you will use your library to port the application of the previous assignment to Java.

In addition to having practical value, this exercise is one example of abstraction vs. implementation. In rex we can reason with concepts involving lists without a great deal of regard to how they happened to be implemented. This assignment shows a specific, relatively efficient, implementation of the ideas in the Java language. It is a library, rather than an interpreter, so one does not literally write rex expressions in the Java language, but rather transcribes them into equivalent Java notation. For example, […] is used to represent lists in rex. In Java, the brackets are reserved for array indexing, so we have to come up with another way to represent the same idea.

Why didn’t  we just do everything in Java in the first place, you might ask? Because Java does not display the ideas of functional programming nearly as succinctly as rex does. Some of the ideas are much clearer in purely functional form. Other ideas take considerable “engineering” to implement   in Java.

Reading

This assignment covers material through Chapter 5 in the text, although we are going to do lists slightly differently than described in the text. The OpenLists in this assignment correspond closely to Polylists in the text.

To be done in lab:

Commenting

Comment your code.  Be sure your comments indicate what each method does, including what the inputs and outputs are. For non-obvious methods, comment how it works as well. For functions that can be defined in rex, consider including the rex definition itself in the comment, since this definition often gives a succinct statement of purpose (assuming the reader can read rex).

Testing your code

You are provided with a skeleton file that contains a method main. This is the standard way of including tests in Java classes.

Do test your code before submitting it to be sure there are no typos, misspellings, etc. and that it works as expected. Failure to do so may cost you points.

Submitting your code

You should submit your rex functions in a single file named OpenList.java using 

   cs60submit OpenList.java

Open Lists in Java

I assume that you have heard about “open lists” in the lecture. Ideally you would also have read about them in Chapter 5 of the text.

You are to implement a Java class OpenList. The elements of an OpenList are any Java Objects, such as Strings, wrapped numbers, and OpenLists themselves. When converted to Strings, as in output from your program, OpenLists get treated specially: they are presented just like rex lists are.

I provide the toString method for you, which will enable the lists to be printed like rex lists. Your task is to implement other methods and functions (static methods) in this class. We will not be dealing with input of lists in this assignment. All lists are constructed within the program.

In order to put numbers into lists, they have to be “wrapped” as Objects. Numbers by themselves are not Objects in Java. For example, to wrap an int x, we would use new Integer(x) which yields an Object, specifically an Integer. To wrap a float y, use new Float(y). In this way, lists can be mixtures of Strings and Numbers just as in rex.

In Java, Objects are manipulated through references to the objects themselves. Thus, when an Object argument is passed to a method, it is really a reference being passed. This saves the effort that would have gone into copying large objects, which can be considerable.

In our implementation, an OpenList is identified with the first “cell” of the list. A cell is a pair consisting of a data Object which is the true first of the list, and a (reference to) an OpenList which is the rest of the list.

The empty list, designated as nil, will be a special cell that is not used for its value but rather for the identity of the cell. That is, we will compare a reference to an OpenList to the reference to the empty list for equality to determine if the list is empty. So the first and rest parts of the empty list will be completely ignored in our uses. Further rationale is given below.

Caution: In the textbook, we used the null reference for the empty list. This works, but is not as nicely when it comes to issues involving printing. So in the current implementation, we don’t use the null reference for this purpose. The null reference can still be passed for an OpenList, but that will not be equated to the empty list. It is thus available for some other purposes, but we won’t need such usage in this assignment. So don’t confuse nil with null. The former is a constant we define; the latter is the null reference built into Java.

Note on Static vs. Instance Methods:

Static methods are like ordinary functions: they don’t depend on any particular object for their meaning. They can use static variables and other static methods in their definition. If you try to use non-static-methods or variables, the compiler will give an error message.

Non-static methods (also called “instance methods”) can depend on a particular object. More specifically, they can depend on instance variables and instance methods. They can also depend on static variables and static methods as well.

Required Methods:

Here are the methods you will need to implement. These are in the skeletal file as a comment and you can use them as headers for your methods.

Where there are both static and instance methods with the same name, it is often best to define the static one first and use that method in the instance version, although there are exceptions to this approach.

 
public static OpenList cons(Object _First, OpenList _Rest)

creates a new OpenList out of a first and a rest. In rex this would be equivalent to the definition:

cons(First, Rest) = [First | Rest];

This definition is actually built in to rex. In Java, cons will call the true constructor OpenList which does the actual list creation.

 
 
public OpenList cons(Object _First)

creates a new OpenList out of a first and this OpenList: For example, if L is an OpenList with elements “beta” and “gamma”, then L.cons(“alpha”) will create a list with elements “alpha”, “beta” and “gamma” in that order. The returned value is simply cons(_First, this), where cons is the static method in the previous box and this is the keyword representing the current OpenList object.

 
 

      final public static OpenList nil = cons(null, null);

nil is the name of the single, one, true, and only empty list. While this list might not look empty, it will be treated as such. Emptiness will be tested using reference equality (==) to this object, rather than content equality. We can avoid various troubles later by having only one empty list in one place. Note that here we deviate from the textbook, which uses null as the empty list. The reason why this is not preferred is that null is not an object. So we can’t, for example, call a print method on it as we can with the proposed empty list. 

 
public Object first()

This instance method returns the first element of its OpenList. It would be applied as L.first() where L is an OpenList.

 
 
public static Object first(OpenList List)

This static method is applied to an OpenList like a function. It is equivalent to the function first in rex:

first([First | Rest]) => First;
 

It would be applied as first(L) where L is an OpenList.

 
 
public OpenList rest()

This instance method returns the rest of its OpenList. It would be applied as L.rest() where L is an OpenList.

 
 
public static OpenList rest(OpenList List)

This static method is applied to an OpenList as a function. It is equivalent to the function rest in rex:

rest([First | Rest]) => Rest;
 
 
 
public boolean isEmpty()

This instance method tells whether its OpenList is empty or not. It would be applied as L.isEmpty() where L is an OpenList.

 
 
public static boolean isEmpty(OpenList List)

This method is equivalent to the function null in rex, which tests whether a list is empty. It is equivalent to the definition:

isEmpty([]) => 1;
isEmpty(_)  => 0;
 
 
public boolean nonEmpty()

This instance method tells whether its OpenList is non-empty or not. It would be applied as L.nonEmpty() where L is an OpenList.

 
 
public static boolean nonEmpty(OpenList List)

This method is equivalent to the definition:

nonEmpty([]) => 0;
nonEmpty(_) => 1;
 
 
 
public static OpenList append(OpenList L1, OpenList L2)

This method is equivalent to the function append in rex, which creates a list containing the elements of L1 followed by those of L2.

It is advised that you use recursion to implement this function.

 
 
public OpenList append(OpenList L2)

Append L2 to this OpenList.

 
 
public static OpenList reverse(OpenList L1)

This method is equivalent to the function reverse in rex, which creates a list containing the elements of L1 in reverse order.

Although reverse can be done with recursion, please try using iteration for this one, since the resulting list is built from the inside out.

 
 
public OpenList reverse()

Create the reverse of this OpenList object.

 
 
public static int length(OpenList L)

returns the length L? Use your judgment; which is better, iteration or recursion?

 
 
public int length()

returns the length of this OpenList. 

 
public Object nth(int n)

returns the nth element of this OpenList, counting the first element as 0.

 
 
public static boolean member(Object ob, OpenList L)

returns true or false, depending on whether Ob is a member of L. Be sure to use equals rather than == in checking for equality.

 
 
public boolean member(Object ob)

returns true or false, depending on whether Ob is a member of this OpenList. 

 
public OpenList prefix(int n)

returns the length-n prefix of this list.

 

public static OpenList list(Object First, Object Second, Object Third)

Create a list of three elements. This is a convenience, so that you don’t have to use cons(…, cons(, …, cons(…, nil))) which is hard to read.

Create similar convenience functions for 0 through 7 elements, at least.

 
 
public boolean equals(OpenList L2)

Check whether this list is equal in content to L2.

 

Handling Exceptions:

It is easy to make the mistake of applying first() or rest() to an empty list. Provide checks for this within your methods, but please do not put print statements inside the methods.

The proper thing to do is define a class of exceptions and thrown an exception in the event that such an error is committed. Exceptions will be explained in class. If the application program wants to print something as a result of an exception being thrown, that is up to it. But print statements should not be used as the error handling mechanism within inner methods.

Use the file OpenListException.java to define the type of exception you will be throwing.

Below we give the toString method for class OpenList, which shows how some of the functions might be used. We also give a test program main to show how others might be used.

class OpenList
{
public static String defaultLeftParen  = "[";
public static String defaultRightParen = "]";
public static String defaultSpacer     = ", ";
 
public static OpenList nil = cons(null, null); 
 
// Convert this OpenList to a String, using default punctuation.
 
public String toString()
  {
  return toString(defaultLeftParen, defaultSpacer, defaultRightParen);
  }
 
 
 
// Convert this OpenList to a String, 
// using the arguments as punctuation
 
public String toString(String leftParen, 

  

  
  
                       String spacer, 

  

  
  
                       String rightParen)
  {
  StringBuffer buffer = new StringBuffer();
 
  buffer.append(leftParen);
 
  if( nonEmpty() )
    {
    buffer.append(first().toString());
    OpenList remainder = rest();
 
    while( remainder.nonEmpty() )
      {
      buffer.append(spacer);
      buffer.append(remainder.first());
      remainder = remainder.rest();
      }
    }
 
  buffer.append(rightParen);
  return buffer.toString();
  }
 
 
// Sample test program
 
public static void main(String arg[])
  {
  OpenList L0 = nil;
 
  System.out.println("L0 = " + L0);
 
  OpenList L1 = cons("a", cons("b", cons("c", nil)));
 
  System.out.println("L1 = " + L1);
 
  OpenList L2 = cons(cons("b", cons("c", nil)), cons("d", nil));
 
  System.out.println("L2 = " + L2);
 
  OpenList L3 = cons(L1, cons(L2, nil));
 
  System.out.println("L3 = " + L3);
 
  OpenList L4 = cons(L1, L2);
 
  System.out.println("L4 = " + L4);
 
  OpenList L5 = cons(L2, L1);
 
  System.out.println("L5 = " + L5);
 
  OpenList L6 = cons(new Integer(1), nil);
 
  System.out.println("L6 = " + L6);
 
  OpenList L7 = cons(new Integer(1),
                     cons(new Integer(2),
                          cons(new Integer(3),
                               cons(new Integer(4),
                                    nil))));
 
  System.out.println("L7 = " + L7);
 
  System.out.println("append(L1, L2) = " + append(L1, L2));
 
  System.out.println("reverse(L5) = " + reverse(L5));
 
  System.out.println("append(reverse(L7), reverse(L1)) = "
                    + append(reverse(L7), reverse(L1)));
 
  System.out.println("reverse(append(L1, L7)) = "
                    + reverse(append(L1, L7)));
 
  System.out.println("L5.length() = " + L5.length());
 
  System.out.println("L5.nth(2) = " + L5.nth(2));
 
  System.out.println("L5.prefix(3) = " + L5.prefix(3));
  }
 
}

The result of the test program is:

L0 = []
L1 = [a, b, c]
L2 = [[b, c], d]
L3 = [[a, b, c], [[b, c], d]]
L4 = [[a, b, c], [b, c], d]
L5 = [[[b, c], d], a, b, c]
L6 = [1]
L7 = [1, 2, 3, 4]
append(L1, L2) = [a, b, c, [b, c], d]
reverse(L5) = [c, b, a, [[b, c], d]]
append(reverse(L7), reverse(L1)) = [4, 3, 2, 1, c, b, a]
reverse(append(L1, L7)) = [4, 3, 2, 1, c, b, a]
L5.length() = 4
L5.nth(2) = b
L5.prefix(3) = [[[b, c], d], a, b]

 

Compiling java on turing

There should be three commands pre-defined in your turing setup: jc, je, and jx for your convenience. The eliminate the need to put .java after the filename, and allow for recalling the previous command with the same file using !jc, !je, or !jx. This cannot be done with !java, because both the compiler and the interepreter have the same prefix (javac vs. java) and will thus get confused.

jc filename

compiles file filename.java

je classname

executes the main program defined in file classname.java

jx classname

compiles, then executes the main program defined in file filename.java

Normally filename and classname will be the same, until you get into multi-class solutions.

(jc calls the program javac, je calls the program java, and jx calls both javac and java.)

You would use jx after you get the file to a point where you know it will compile using jc and you just want to recompile and execute.

Note that if your file previously compiled, and now has errors, jx will run the previous version. So don’t continue to use jx if you are getting errors; go back to jc.