Harvey Mudd College
Computer Science 60
Assignment 4, Due Sunday, September 28, by midnight

From Scheme to Java...

This homework introduces Java, a language designed for creating and using data structures. The first part of the assignment is to implement an OpenList data structure, which is a list of the type Scheme uses for programs and data. The OpenList "shows off" Java's data-structuring capabilities without sacrificing the generality of Scheme.

The second part of this assignment is a Scheme "unit-calculator" application. This will be followed up (next week) with a Java version of that calculator... .

Submitting your code

You will want to submit your two files

• OpenList.java and
• Unicalc.scm

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.

Working with Java

• Dr. Java
  
  Simple and available for Mac OS X, Windows, and in Java itself:
  • The drjava website
  • A local copy of the 09/04/2008 Windows version
  • A local copy of the 09/04/2008 Mac OS X version


• 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

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 file 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, add tests to your OpenList class's main method that exercise each of your methods. 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!

Reminder    Again, the command

     % javac OpenList.java
     

     % java OpenList
     

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

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 problem, 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"]
                

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

Problem 2: Unicalc, a unit-calculator in Scheme

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

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

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.