Harvey Mudd College
Computer Science 60
Assignment 3, Due Friday, Feb. 15, by midnight

Unicalc (part 2) and Starbucks Menus Java Lists

The problems in this assignment finish up the Unit Calculator application in rex with a mutually recursive pair of functions. In addition, we transition from rex to Java by implementing rex's list structure (called OpenList) in Java.

Submitting your code

You are asked to construct several function definitions in rex and test them. You should submit your rex functions in a single file named hw3.rex. Your Java class (problem 4) should be in a file named OpenList.java . If you do the extra-credit rex problem, it should be in your hw3.rex file. Similarly, the extra-credit Java methods would go into the OpenList.java file. Submit with

cs60submit hw3.rex
cs60submit OpenList.java

Reading

This assignment uses material through Chapter 5 in the text. Most of the material needed to handle this assignment will be presented in class also. If you are not familiar with Java, however, you may want to catch up a bit -- there are several references from the references page.

Testing your code

REX

Test cases for each of the Unicalc (rex) problems are in the directory /cs/cs60/as/a3 . The names of the test-case files for rex are Test#.in, where # is an integer, 1-10. To test a particular rex function in hw3.rex, use

% rex hw3.rex < /cs/cs60/as/a3/Test1.in

JAVA

To test your java class, OpenList, you should simply run the main method in your class with some testing code present. If you start with the file /cs/cs60/as/a3/OpenList.java (highly recommended), all the test code you'll need is already in main. It's commented out, but as you write methods, you can comment more an more of it back in and see if the output matches the expected answers in /cs/cs60/as/a3/OpenList.out . Of course, you can write your own testing code, as well. The commands you'll need to compile and run are these:

  javac OpenList.java
  java OpenList

An alternative is the way the test scripts will interact with your code. Here are the steps:

• Copy one of the Test#.java files and one of the Test#.out files (the expected output) from /cs/cs60/as/a3 to the directory with your compiled OpenList.class. In both cases, # can range from 1 to 10. For example, if you're in your code's directory, this command will do the copying:

         cp /cs/cs60/as/a3/Test1.* .
         

• Compile the Test#.java file with

         javac Test#.java
         

• Run the resulting Test#.class file with

         java Test#
         

• Compare the output you see with that in Test#.out. You can certainly use emacs to look at the expected output, or use diff, as described below.

You can be sure that your output is the same with the unix diff command (from the directory with your compiled java code):

% java Test# | diff - Test#.out

% java OpenList | diff - OpenList.out

The Problems

1. Continuing the Unit-conversion calculator, we pick up from the point at which you have code that successfully handles simplifying, multiplying, dividing, and unit-lookup (conv_unit). You should copy those functions (simplify, multiply, divide, and conv_unit) into your hw3.rex file, so that they are available for Unicalc's dramatic conclusion (the following three problems). If you don't have or don't want to use your code, by Monday (2/11) there will be a solutions file available online from the assignments page. You may take the necessary functions: simplify, multiply, divide, and conv_unit from there.

   Just as a reminder of the data structures in the Unicalc problem,

   • units ("meters", "ohms", etc.) are represented by strings
     
     
   • a quantity list is a list of three elements following the pattern

            QL = [ amt, N, D ]
            

     where amt is simply a number (floating-point), N is a list of units in the numerator, and D is a list of units in the denominator. For example, the unit "mhz" could be represented by either of these quantity lists:

            [ 1.0, ["mhz"], [] ]
            [ 1000000.0, [], ["second"] ]
            

     
     
   • a unit database is a list of pairs like the following:

            [  [ "hour",     [ 60.0, ["minute"], [] ] ],
               [ "minute",   [ 60.0, ["second"], [] ] ]  ]
            

     If a unit does not appear on the left side of the database, it is considered a basic unit, that is, it is irreduceable.
   
   

   When the numerator and denominator lists within a quantity list contain only basic units, we'll say that that quantity list is normalized. Again, basic units are those which do not appear on the left-hand side of any entry in the unit database. They are irreducible.

   In order to convert one unit to another, we must express those units in a common form. This common form will be simplified, normalized quantity lists. Recall that in the last problem of Assignment 2, you wrote conv_unit( s, DB ), which takes a unit s and a unit database DB and returns a quantity list that it finds after "looking up" the unit in the database. If the unit is a basic unit, conv_unit returns the default quantity list [ 1.0, [<unit name here>], [] ] .

   For this problem, write a function norm_unit(s,DB) that returns a normalized quantity list that represents the unit s. Again, a normalized quantity list is one in which the numerator and denominator lists contain only basic units. The inputs to norm_unit(s,DB) are a string s representing a unit and a unicalc database DB.

   Here's how norm_unit(s,DB) will work: in the case that s is a basic unit, norm_unit will return the same thing that conv_unit does: [1.0, [s], []]. In the case that s is not a basic unit, you should use conv_unit to "look up" s's definition in the database. Then, you will need to normalize by going through the resulting numerator and denominator lists, looking up the units found there (and so on) until only basic untis remain. By multiplying (or dividing) as appropriate, the final result will be simplified. (Recall that multiply and divide simplify their results.)

   Here are some example runs of norm_unit. There are two unicalc database files in /cs/cs60/as/a3/ : one is called unicalc_mini_db.rex and a much larger one is called unicalc_db.rex. Both files define the variable db, so only include one of the two files as you test... .

     rex >  sys(in,"/cs/cs60/as/a3/unicalc_mini_db.rex");
     
     rex >  norm_unit("second",db);
     [1, [second], []]
   
     rex >  norm_unit("hour", db);
     [3600, [second], []]
   
     rex >  norm_unit("ohm", db); 
     [1, [kg, meter, meter], [ampere, ampere, second, second, second]]    
   

   
   
   Critical Hint: read the next problem before solving this one, and use norm when writing norm_unit.
   
   
2. The next problem extends norm_unit: construct a function norm(QL, DB) that takes as input any quantity list QL and a unicalc database DB. norm(QL, DB) should output the normalized equivalent to the quantity list QL with respect to the database DB.

   Notice that norm does the same thing as norm_unit, only with a slightly different first input. Because of this, norm and norm_unit are most concisely written as mutually recursive functions, i.e., each calls the other at one or more points. The key to writing mutually recursive functions is being sure you have a clear sense of what each function does at an abstract level -- that way, you can use either as appropriate.

   Rex (as well as Java) can handle mutual recursion, so you may want to take advantage of that. (To write norm and norm_unit without mutual recursion is possible, but more painful!)

   Some examples of norm in action:

     rex >  norm([20.0, ["hour"], []], db);
     [72000, ["second"], [] ]
   
     rex > norm([15.0, ["ohm"], ["volt"]], db);
     [15, [], [ampere]]
   

   
   
   
3. The conversion process from the quantity list A to the quantity list B can now be seen as simply

   rex >  divide(norm(A, db), norm(B, db))
   

   If direct conversion is possible, the numerator and denominator of the result above should both be empty lists. If there is a mismatch, the numerator or denominator or both will not be empty. Write a user interface function convert such that convert(A, B, DB) will perform the conversion and output the units if a direct conversion is possible, or will output "There is a mismatch in units." when a direct conversion is not possible. The inputs to convert are two quantity lists and a unit database. Note: be sure to output exactly the right strings both when unit conversion succeeds and fails, so that the grading program gives you credit for it!

   Follow the format of these two examples:

    
     rex >  convert([1, ["mile"], []], 
                    [1, ["inch"], []], db);
     multiply by 63360 or divide by 1.57828e-05
   
     rex >  convert([1, ["mile"], ["second"]], 
                    [1, [], []], db);
     There is a mismatch in units.
   

   For converting numbers to strings, you may wish to use the rex built-in function make_string that makes a string of its argument, and concat that concatenates an arbitrary number of string arguments. Do not do any number formatting, such as adjusting the number of significant figures shown; rex will do it for you.
   
   

4. Congratulations! You've completed unicalc [ or at least decided not to work on it any more :) ].

   This next problem is meant to introduce the implementation of data structures in Java (without abandoning all of the good features of rex). In addition, it is a chance to 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. There is example java code in /cs/cs60/as/a3 and there are lots of on-line references 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 gently transition from Java to rex, you will be implementing lists in the same way rex does. In fact, this problem is, essentially, the first step in writing the rex programming language in Java.

   Write your class in a file called OpenList.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).

   There is a start of an OpenList class in the file /cs/cs60/as/a3/OpenList.java. I would recommend that you simply copy that file to your directory and then modify it and add to it to create the whole class.

   The main method of /cs/cs60/as/a3/OpenList.java contains lots of commented-out tests. You should uncomment each line as you write the method that it tests and then try it out! It's much easier to make small syntactic errors in Java than in rex... .

   The command

        javac OpenList.java
        

   will create a file named OpenList.class in your directory. Then running

        java OpenList
        

   will execute the code in the main method of the OpenList class. For those who dislike even typing that much (as I do), there are shortcuts to these two steps:

        jc OpenList
        je OpenList
        

   compile and execute the code, respectively.

   Writing the OpenList class

   First, in your OpenList class, you will want to indicate the data that comprises 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();
        

   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 your OpenList class, implement the following functions (often called methods in Java):
   
   

   • CONSTRUCTORS
     
     
     • (These 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.
       
       
     • private OpenList() which is a constructor that takes no arguments and returns the empty list. The empty list is not itself a null reference, but it is an OpenList with its first and rest both equal to null, the null reference. This constructor is private to reinforce the notion that lists can be shared... !
       
       
   • toString
     
     
     • In fact, do not write this method -- instead, merely use the one provided in the file /cs/cs60/as/a3/OpenList.java. Why? -- 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 public String print(), as well.

       This method is a nonstatic method that returns a String representation of the invoking list. A static version isn't needed. This method is used internally whenever adding a String to an OpenList, e.g., in code like this:

                   OpenList L = OpenList.list("Hello","World");
                   System.out.println("List L is " + L);
                   

   • cons
     
     
     • (These two functions will also be covered in detail in class to distinguish between static and nonstatic methods, as well as a review of writing Java code... .)
       
       
     • 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.
       
       
   • 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 need 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. 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). It returns 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: 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).
       
       
   
   
   General Hint: for length, append, reverse, and assoc (and maybe others), using recursion will make your life much simpler... . Java supports recursion to the same extent that rex does.