Harvey Mudd College
Computer Science 60
Assignment 03

Java implementation of rex abstractions

Due Dates: Due by midnight on the morning of your next lab:

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

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.

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.

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

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.

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.

 
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 Object first()

This non-static 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;
 
 
 
public Object first()

This non-static 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;
 
 
 
public OpenList rest()

This non-static 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 non-static 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 non-static 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 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 int length()

returns the length of this list. Use your judgement; which is better, iteration or recursion?

 
 
public Object nth(int n)

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

 
 
public OpenList prefix(int n)

returns the length-n prefix of this list.

Where there are both static and non-static methods with the same name, it is generally best to define the non-static one first and use that method in the static version.

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.

The following skeletal file containing toString and main may be found in /cs/cs60/a/03/OpenList.java.

class OpenList
{
public static String defaultLeftParen  = "[";
public static String defaultRightParen = "]";
public static String defaultSpacer     = ", ";
 
public static OpenList nil = cons(null, null);  // dummy
 
 
///////////////   Your methods go in here. ///////////////
 
 
// 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();
  }
 
 
// 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.

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.

 

Extra Credit: Handling Exceptions:

It is easy to make the mistake of applying first() or rest() to an empty list. If you decide to provide checks for this within your methods, 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 main error handling mechanism.