Assignment 4

Harvey Mudd College
Computer Science 60
Assignment 4, Due Monday, September 28, by 11:59pm

From Scheme to Java...

Assuming you took CS5, at this point in CS60 you know (at least) four programming languages: Python, HMMM, Scheme, and Java (or at least a little Java). However, although all of these languages can do some useful and powerful stuff, in some ways they fall short. Namely, they cannot help you solve "unit arithmetic" problems of the type that you might encounter in your physics class, for example.

So... over the next two weeks, you are going to be implementing your own "unit arithmetic" language. This language will be surprisingly powerful, letting its user store values in variables, and then carry out computation using these values. For example:

def mile 5280 foot
{ 5280.0, [foot], [] }

def x 1 mile
{ 1.0, [mile], [] }

def yard 3 foot
{ 3.0, [foot], [] }

def y 5 yard
{ 5.0, [yard], [] }

y + x
{ 5295.0, [foot], [] }

#y
{ 15.0, [foot], [] }

Notice that the second to last operation has to first convert y and x into their basic units (foot) in order to add them. Similarly, "#" is the "normalizing operator" that converts an expression into its simplest form.

In this week's homework we will build some basic building blocks for this new language. In part 1 (the individual part), you will build a data structure in Java that mimic's scheme's List data structure, called OpenList. The OpenList "shows off" Java's data-structuring capabilities without sacrificing the generality of Scheme. In part 2 (the pair option part), you will build the unit conversion capabilities in scheme. Although our final language will be implemented in Java, you'll work first in scheme and then port your scheme code to Java next week.

Submitting your code

You will submit 3 files this week.

OpenList.java andOpenListTester.java-- To be completed individually
Unicalc.scm -- To be completed with a partner or individually

in the usual way.

Getting started with Java

There are many, many environments in which you might write Java code. Because CS 60 seeks to get at the fundamentals of computation (and not focus on a particular toolset like Eclipse, JCreator, Visual Studio, NetBeans, etc.) our default setup will use Java from the Dr Java environment.

However, if you have a different favorite environment, you're welcome to use it, but please be sure that you are submitting only your plain-text .java source files so that we will be able to compile and run them!

Setting up Java on the Mac Type javac -version at the command line in the Terminal application; it should already be built-in. The lab Macs are using version 1.5.0_13, though pretty much any version will be fine. We will be concentrating on the core of the language, not the small differences among versions 1.4, 1.5, and 1.6, for example.

Setting up Java on the PC (Windows) You might have java, but might _not_ have java development kit (JDK) which includes the compiler. You will need the compiler to run your code! To find out if you have it, look for the folder C:\Program Files\Java\jdk1.5.0_11\ - or some other version, perhaps jdk1.6.0_07 - the key is that the jdk letters are at the start of the folder name. The jre folder, which stands for java runtime environment can run software, but can not compile it. Thus, you'll need the JDK. If you don't have the JDK and are on a Windows machine, download it from Sun's Java standard edition downloads page.

Installing JUnit

For both Macs and Windows, you will also need to download JUnit from the following link: http://sourceforge.net/projects/junit/files/junit/. Choose version 4.7. The file you want is junit-4.7.jar. After you have downloaded this file, you need to set your CLASSPATH variable to include this file.

On a PC (Windows) From the Start menu, right click on "Computer" (or "My Computer") and select Properties. Choose "Advanced" or "Advanced System Settings". Then click the "Environment Variables" button. You might have a variable called CLASSPATH. If you do, select it and Edit this variable. At the end of its current value, add a semi-colon, and then the full path to the .jar file you just downloaded. For example, ";C:\Program Files\Java\junit-4.7.jar" (modify this path depending on where you saved the .jar file, but be sure to include the name of the file in the classpath.). If you do not have a CLASSPATH variable already, select New... to create one, and give it the value which is the path to the .jar file you downloaded.

On a Mac This is a little trickier. You have several options. First, you can add the line:

export CLASSPATH = ".:PATH_TO_junit.jar_FILE"

Note that PATH_TO_junit.jar_FILE should be replaced with the full path to the file you just downloaded INCLUDING the file name.

Option 2 applies if you are running from Dr. Java. In Dr. Java, go to Edit->Preferences. Next to Extra Classpath click Add. Then navigate to the junit.jar file you just downloaded, select it, and click OK.

Finally, a third option involves simply setting the classpath as you call Java. When you

Working with Java

Integrated development environments (IDEs) automate some of this process for you. There are many Java IDEs, some are described at this excellent documentation page. I would recommend one of the following three choices for working with Java:

Dr. Java

Simple and available for Mac OS X, Windows, and in Java itself:

Eclipse

A professional IDE with lots of bells and whistles (and a much steeper learning curve):
- The Eclipse website

no IDE at all!

You don't need an integrated development environment. Instead, you can call the compiler javac and the run-time system java at the command line for Windows or Mac OS X.
- This page has instructions on how to do so.

The Problems

Problem 1: OpenList (Individual)

70 points

This problem is meant to introduce the implementation of data structures in Java. In addition, it is a chance to either introduce yourself (or review) what Java looks like and how java code is structured. If you haven't used Java before, you may need to review a bit about the language. In particular, there is a starting point for your OpenList.java andOpenListTester.java files on the top-level assignments page. Also, there are on-line references and tutorials available from the references page.

Write a java class named OpenList that implements an (open) linked list data structure. Since the goal of this problem is to transition from Scheme to Java, you will be implementing lists in the same way Scheme does. In fact, this problem is, essentially, the first step in writing the Scheme programming language in Java. Open lists are not modified in the computer's memory (so that there is no worry about side effects) -- instead, each function returns a newly created list (or whatever data is appropriate).

Write your class in a file called OpenList.java. You should start with the OpenList.java file located at the top-level assignments page.

The main method of this OpenList.java contains a couple of tests. You might want to try out the file to begin with and read over the code in order to get a sense of what Java is doing (and how it's organized).

Testing your code! Just as with your Scheme programming, you should test each of your methods as you write it. To do this, we will be using the JUnit test framework. Write your tests in the provided OpenListTester.java file. It's much easier to make small syntactic errors in Java than in Scheme (all those semicolons!) Be sure to try out base cases, as well as recursive ones! You should include one method in this class for each test you write.

Reminder Again, the command

 % javac OpenList.java OpenListTester.java
or
 % javac *.java

On knuth you will need to run:
 % javac -cp ".:/usr/share/junit-4/lib/junit.jar" OpenList.java OpenListTester.java
or
 % javac -cp ".:/usr/share/junit-4/lib/junit.jar" *.java

[If you are on a mac and chose CLASSPATH option 3 above, you will also need to use the
-cp option as above, but giving it the correct path to your junit.jar file.  Be sure
to include the .: at the beginning!]

will create a files named OpenList.class and OpenListTester.class in your directory. After that, running

 % java org.junit.runner.JUnitCore OpenListTester

or on knuth:

  % java -cp ".:/usr/share/junit-4/lib/junit.jar" org.junit.runner.JUnitCore OpenListTester

or on a mac:
 
  % java -cp ".:/PATH_TO_junit.jar" org.junit.runner.JUnitCore OpenListTester
where PATH_TO_junit.jar is the complete path to the junit.jar file you downloaded above.

will run all of the tests in the OpenListTester class.

In Dr. Java, all of this is much simpler. Make sure you have both files open, then click "Compile" and then "Test" to run your tests.

Writing the `OpenList` class

First, in your OpenList class, you will want to indicate the data that constitute a list. There are two nonstatic data members (first and rest) and one static data member (emptyList) in an OpenList:

 private Object first;
 private OpenList rest;

 public static OpenList emptyList = new OpenList(null, null);

These are the only data members you will need in your list implementation. You may use others, if you would like -- in fact, there is considerable leeway in how you want to implement OpenList. However, it has to have all of the methods indicated below, and they need to behave as specified!

Notice that because the data member named first is of type Object, this OpenList implementation will be able to create lists of any Java Objects. Everything in Java is an Object except the types int, double, float, boolean, byte, char, and long. We will use only Strings and OpenLists for this assignment. The next assignment, on the other hand, will put your OpenList class to work... .

In Java and other object-oriented languages, functions that are members of a class are often called methods.

So, in your OpenList class, implement the following methods:

CONSTRUCTORS
- (This will be covered in detail in class in order to motivate the use and syntax of constructors.)
- public OpenList(Object first, OpenList rest) which is a constructor that returns an OpenList with first as its first element and rest as its rest.
toString
- In fact, do not write this method -- instead, merely use the one provided in the starter file OpenList.java linked at the assignments page.
  
  Why do we ask you not to write this? Because this method is how we will test all of your other methods -- and we need a consistent way of displaying OpenLists to do that testing. You will need the helper method private String printItems(), as well. It is also provided.
  
  This toString method is a nonstatic method that returns a String representation of the invoking list. A static version isn't needed. The toString method is used internally by Java whenever your code adds a String to an OpenList, e.g., in code like this:
```
 OpenList L = OpenList.list("Hello","World");
 System.out.println("List L is " + L);
 
```
  This code should output
```
 List L is ["Hello", "World"]
```
  You will also use this method quite a bit when writing your unit tests, so you can assume it's working correctly.
cons (Note that these and several other methods will be covered in detail in class as an introduction to creating data structures in Java. Feel free to use that code from class when writing these methods.)
- public static OpenList cons(Object F, OpenList R) which is a static list-constructing method that takes a string F and an OpenList R and returns an OpenList in which F is the first element and R is the rest of the list.
- public OpenList cons(Object F) which is a nonstatic list-constructor method that does the same thing, but uses the invoking OpenList as the "rest" of the result. If you're already familiar with C++ or Java data structures, this method might seem a bit odd: it does not change the invoking list at all! Instead, it returns a new list that uses the invoking OpenList as its rest. Notice that this is a "Scheme-style" approach to data.
isEmpty
- public static boolean isEmpty(OpenList L) which is a static predicate that returns true if the input list is the empty list and false otherwise.
- public boolean isEmpty() which is a nonstatic predicate that returns true if the invoking list is empty and false otherwise.
length
- public static int length(OpenList L) which is a static length method that returns the length of the input list.
- public int length() which is a nonstatic length method that returns the length of the invoking list.
assoc
- public static OpenList assoc(Object o, OpenList DB) and public OpenList assoc(Object o) are both already written in the OpenList.java starter file.
first
- public static Object first(OpenList L) which is a static method that returns the first object in the input list. If the input list is empty, the method should print an error message and exit. To exit a Java program immediately, use the line System.exit(0). Note: the idea here is simply to return L.first !
- public Object first() which is a nonstatic method that returns the first element of the invoking list. If the invoking list is empty, the method should print out an error message and exit.
rest
- public static OpenList rest(OpenList L) which is a static method that returns the rest of the input list. If the input list is empty, your function should print out an error and exit.
- public OpenList rest() which is a nonstatic method that returns the rest of the invoking list. If the invoking list is empty, your function should print out an error and exit.
equals
- public boolean equals( Object o )
  
  This equals method is a nonstatic method. We will not write the static version.
  
  It is very important that you keep this signature, because it overrides the built-in .equals method for objects in general. This method returns true if o is an OpenList object with all the same elements as the calling object in the same order, and false otherwise. You will likely want to also create a method:
  
  public boolean equals( OpenList L )
  
  that you call from your equals method above if the object passed in is an instance of OpenList.
list
- public static OpenList list(Object o1) which is a static method that returns an OpenList of one element, o1. Note that there is no nonstatic version of the list method, because there might not be a list around to invoke it!
- public static OpenList list(Object o1, Object o2) which is a static method that returns an OpenList of two elements (in the order they're input). Again, there's no nonstatic version.
- public static OpenList list(Object o1, Object o2, Object o3) which is a static method that returns an OpenList of three elements (in the order they're input). Again, there's no nonstatic version.
append
- public static OpenList append(OpenList L, OpenList M) which is a static append method that takes two OpenLists and returns an OpenList that is their concatenation.
- public OpenList append(OpenList M) which is a nonstatic append method that takes an OpenList as input and returns an OpenList that is the concatenation of the invoking list and M. Thus, the invoking list "goes first." Again, the invoking list is not changed -- because this data structure is an open list, it does not allow existing data to be changed, only new data to be created.
reverse
- public static OpenList reverse(OpenList L) which is a static method that returns the reverse of the input list. (Remember - this does not actually change the input argument L.) Hint: use append.
- public OpenList reverse() which is a nonstatic method that returns the reverse of the invoking list. Again, as with all of the methods in this class, the invoking list is not changed.
merge
- public static OpenList merge(OpenList L, OpenList M), which is a static method that takes in two OpenLists, both of which you should assume are lists of lower-case-only Strings in sorted order from early-to-late in the alphabet. Then, merge should use the merge technique discussed in class to return a list of all of the elements in both of the input lists, but still fully in order. (So append will not work in general!)
  
  Briefly, merging is the process of looking at the first two elements in both lists and deciding on what to do with one of them. In the end, each element gets handled once, making this big-O(n), where n represents the number of elements in both lists together. This is faster than calling any general-purpose sorting routine!
  
  You will want to cast the elements to type String and then use String objects' compareTo method. Here's an example of how compareTo works:
```
 String m1 = "mudd";
 String m2 = "mit";
 if ( m2.compareTo(m1) < 0 ) ... // this test will evaluate to true
 
```
  Basically, if compareTo is less than zero, then this is before the input argument in the dictionary.
  
  Warning! Java is picky about types!
  
  This is no surprise, but note that compareTo needs to be called by a String with a String as input. If L is an OpenList, however, Java thinks that L.first or the result from L.first() is only of type Object, as stated at the top of the OpenList class, but not necessarily of type String!
  
  At times like this, the programmer (you) know that data is of a certain type (a String in this case), but Java does not. The mechanism for "coaxing" Java to recognize data as a certain type is called casting and looks like this:
```
 String firstOfL = (String)L.first(); // we cast the Object returned by first()
 String firstOfM = (String)M.first(); // into the String we know it to be...
 
```
  Thus, you'll want to use lines like these two in order to grab the two strings you'll need to implement the merge function.
- public OpenList merge(OpenList M) which is a nonstatic assoc method that takes an OpenList as input and does the same thing as the nonstatic merge, using this as the other OpenList to be merged. Again, the two lists, this and M will contain zero or more strings in sorted order.
Note: these three extra-credit problems won't return as standard problems next week...
Optional Extra credit of up to +5 points anylist

Write public static OpenList anylist(Object ... elements), which should be a function of any number of arguments that does essentially the same work as the list methods, i.e., create an OpenList out of those input Objects.

The trick here will be to find how Java handles arbitrarily many inputs. I used this reference http://today.java.net/pub/a/today/2004/04/19/varargs.html. Note that instead of ints, you will be using Objects. You don't need to write a nonstatic version.
Optional Extra credit of up to +5 points duperreverse

Write public OpenList duperreverse(), which is a nonstatic method that takes no inputs and should return a list that is the fully-recursive-reverse of the invoking OpenList, this. That is, the output will have the elements of this in reverse order, but will also have any recursively-nested sublists of this in reverse order, as well. You will have to use the instanceof operator in Java to determine what class-type a particular element is, in order to know whether or not to continue. For example,
```
 Object s = new String("I'm a string.");
 if ( s instanceof String ) ... // this test will evaluate to true
 if ( s instanceof OpenList ) ... // this test will evaluate to false
 
```
No static version is required. Remarkably, Java's compiler checks if an instanceof expression can possibly be true - the code won't compile if it can't! In this case, s is of type Object, which could be a String or a OpenList. (The compiler doesn't actually read the code, it just checks the types....)
Optional Extra credit of up to +10 points mergesort

Write public static OpenList mergesort(OpenList L), which is a static method that takes in one OpenList (which will contain ONLY Strings) and then mergesort should return a sorted OpenList with the same elements that L contained. No nonstatic version is required, but you may certainly (as always) create small, helper functions of whatever type you like - for example, our solution used a method named split, which returned an array of two OpenLists.

Again, remember that you need at least one test for each of your functions in your OpenListTester.java file!

Problem 2: Unicalc, a unit-calculator in Scheme (Pair optional)

30 Points

This problem asks you to write a Scheme function, convert, which implements a "unit-calculator" application. A complete application will be able to convert any unit quantity to any compatible quantity by using an association list of known conversions. Incompatible conversions will result in a set of extra units "left over."

For example, the following call is asking "how would you convert from 1 mph (mile per hour) to 1 meter per second?" The third input argument to convert, named db is a "database" of unit conversions. This "database" is simply an association list.

> (convert '(1 ("mile") ("hour")) '(1 ("meter") ("second")) db)
(0.447032 () ())

This result is indicating that 1 mile-per-hour == 0.447032 * 1 meter-per-second.

Here is an example with some units left over, because it's not possible to convert miles-per-hour to feet:

> (convert '(1 ("mile") ("hour")) '(1 ("foot") ()) db)
(1.466666 () ("second"))

This time the result is showing that 1 mile-per-hour == 1.46666 feet-per-second.

Since there were no time units in the denominator and there should have been, the result shows the basic (irreduceable) time units there. Basic units are simply those which do not appear on the left-hand side of the association list. In both of these examples, only the first few significant figures have been shown.

As these examples suggest, your convert function needs only to handle multiplicative conversions - it will not handle more complicated conversions, such as the one from Fahrenheit to Celsius.

Here are the key representations used in Unicalc:

A Quantity list or "Quantity" is a list of three elements representing some quantity of a designated unit. Here are four quantity lists:
```
 (1.0 ("mile") ("hour")) represents 1 mile per hour
 (2.5 ("meter") ("second" "second")) represents 1 meter per second squared
 (60.0 ( ) ("second")) represents 60 hertz
 (3.14 ( ) ( )) represents about pi radians
 
```
To summarize, a Quantity list is a list of three elements: the first is the quantity (a floating point number), the second is a list of units in the numerator, and the third is the list of units in the denominator. Empty lists are required when no units are present. Note You may assume that the lists of units within the numerator and within the denominator, if any, are initially in alphabetical order. Your code needs to make sure this property is maintained!

A Conversion Database is an association list of unit-name strings with Quantity lists that define them. Here is an example, with additional spaces added.
```
 (define small-db
 '(
 ("foot" (12.0 ("inch") ()))
 ("inch" (2.54 ("cm") ()))
 ("hertz" (1.0 () ("second")))
 ("mile" (5280.0 ("foot") ()))
 ("coulomb" (1.0 ("ampere" "second") ()))
 ("cm" (0.01 ("meter") ()))
 ("hour" (60.0 ("minute") ()))
 ("minute" (60.0 ("second") ()))
 )
 )
 
```
Each line in the database is thus a list of two elements -- the first element is a string that names some unit and the second element is a Quantity List that is equivalent to that named unit.

There are two databases that you can try from the top-level assignment page. They are unicalc-db.scm, which defines the large association list named db, and unicalc-mini-db.scm, which defines a much smaller list named mini-db.

Not every unit is defined in terms of others in the database. Some are intentionally left undefined. We'll call the latter basic units. In the above example, ampere, meter, and second are basic units.

A database does not need to contain conversions for everything to everything; that would tend to make it very large and maintenance would be error-prone. Instead, all conversions done by Unicalc are derived from basic ones in the database.

Individual functions You are welcome to decompose this unit-calculator into smaller functions on your own. If you do so, we will simply test your convert function. However, you are also welcome to write the functions described on this page, which will lead you to a full implementation of the unit-calculator. If you use this decomposition, we will grade each function separately.

Harvey Mudd College Computer Science 60 Assignment 4, Due Monday, September 28, by 11:59pm