Harvey Mudd College
Computer Science 60
Assignment 4, Due Sunday, Feb. 17, by midnight

From Scheme to Java...

This homework introduces Java, a language designed for creating and using data structures. The first part 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. There is also a Scheme "unit-calculator" application, which will lead to a Java version (next week).

Submitting your code

You will want to submit your two files

• OpenList.java and
• Unicalc.scm

Reading

This assignment uses material through Chapter 5 in the text, though the material needed to handle this assignment will be presented in class also.

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 command line (similar to Python).

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

Setup on the Mac    Type javac -version at the command line in the Terminal application; it should already be built-in. We are using version 1.5.0_11, though 1.4 might well be good enough, too.

Setup on the PC (Windows)    You might have java, but might _not_ have java software development kit (JDK) which includes the compiler. To find out, look for the folder C:\Program Files\Java\jdk1.5.0_11\ - the jre folder, which stands for java runtime environment can run software but can not compile it and so is not sufficient. If you don't have the JDK, download it from the references page.

Installation should be straightforward. After installing the JDK, you will want to set up your "path" so that you can simply type javac at the command line to compile. To do this, click the Start Menu and go through the following steps:

 - Control Panel
 - System
 - "Advanced" Tab
 - "Environment Variables" button at bottom
 - Under "System variables," scroll to
 - "Path" and select it
 - click "Edit"
 - a one-line textbox will appear
 - go to the right-hand end and paste the following:

;C:\Program Files\Java\jdk1.5.0_11\bin

 Then enter and click on OK a couple of times to finish.

To check that it's working, open a cmd window and type javac -version. You should see javac 1.5.0_11 and then lots of additional lines.

OK, but the command java to actually run the programs isn't working!

This may or may not be happening to you (it depends on earlier interactions of your computer with Java, some of which you might not have realized because it gets used behind the scenes in lots of web-browsing situations).

However, if javac, the compiler, is working, but java is not working (be sure you're typing java CLASSNAME without the .class extension!), then it's almost certainly the so-called "classpath". The classpath is where Java looks for the classes whose main method it will run. You need to have the current directory in your classpath, and this is done by setting the CLASSPATH environment variable. Here's what to do (almost identical to augmenting the Path environment variable, above:

 - Control Panel
 - System
 - "Advanced" Tab
 - "Environment Variables" button at bottom
 - Under "System variables," scroll to
 - "CLASSPATH" and select it IF PRESENT
 - click "Edit"
 - a one-line textbox will appear
 - go to the right-hand end and paste the following:

;.

 Then enter and click on OK a couple of times to finish.

 - if CLASSPATH was NOT PRESENT
 - click "New" (in the lower, "System variables" part of the window)
 - name the new variable CLASSPATH
 - enter the value

.

  Then click on OK a couple of times to finish.

Working remotely at the CS lab    You can login remotely to your CS lab account by using a secure shell login program. A very popular one that you can download for free is named Putty.

Editing your code

Again, you may use your favorite text editor. A free editor that has worked well on any OS is JEdit. For some people, the development release has installed more readily than the "stable" release. A much faster (to load) editor is Crimson Editor, but it is for Windows only. Regardless of your specific editor, do be sure to use a text editor, not a word processor - word processors (like Microsoft Word) insert invisible control characters into their documents that will interfere with writing and compiling code.

Getting around the command line

Unlike Scheme and Python, running Java source code is a two-step process.

From within the directory containing the code, you need to first compile the code. This converts it from source (what you wrote) to byte code (which will get executed). For example, if your source file is named OpenList.java you would type

prompt> javac OpenList.java

prompt> java OpenList

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.
    
    
• 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).
    
    
  • 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.
    
    
• 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.)
    
    
  • 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.
    
    
• 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.
    
    
• assoc
  
  
  • public static OpenList assoc(Object o, OpenList db) which is a static assoc method that takes an Object and an association list (db). This assoc method should return an empty OpenList if o does not appear as the first element of any of the elements of db (you may assume all of those elements will be OpenLists.) If o does appear as the first element of one of db's sublists, return the first such sublist.
    
    Important: be sure to use .equals to compare Objects, not ==.
    
    
  • public OpenList assoc(Object o) which is a nonstatic assoc method that takes an Object as input and does the same thing as the nonstatic assoc, using this as the association list (db).
    
    
• 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.
  
  
  • 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.
  
  
  
• 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 associate 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.