Harvey Mudd College
Computer Science 60
Assignment 3, Due Thursday, Feb. 10, 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. Also, some other data structures in rex are considered, as well as a prelude of what's to come: 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. When you submit with

cs60submit hw3.rex

You will also need to create a file named OpenList.java . To submit this part of the assignment, use

cs60submit OpenList.java

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.

Testing your code

Test cases for each of these problems appear in the directory /cs/cs60/as/a3 . The names of the test-case files for rex are Test#.in, where # is 1 - 5. To test a particular rex function in hw3.rex, use

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

To test your java class, OpenList, you can copy the test code in /cs/cs60/as/a3/OpenList.examples (in the main function) to your OpenList class's main function and then run it. The correct output is in /cs/cs60/as/a3/OpenList.out and you can be sure that your output is the same with the unix diff command (from the directory with your compiled java code):

% java OpenList | diff - /cs/cs60/as/a3/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 into your hw3.rex file, so that they are available for the dramatic conclusion (the following three problems). If you don't have or don't want to use your code, on Sunday there will be a file /cs/cs60/as/a2/hw2.sols from which you can take the working functions: simplify, multiply, divide, and conv_unit .

   When the lists in a quantity list (see assignment 2 for the definition of a quantity list) contain only basic units, we'll say that the quantity list is normalized. Recall that basic units are those which do not appear on the left-hand side of any entry in the unit database. That is, they are irreducible.

   In order to convert one quantity to another, we must both normalize and simplify the quantities. Using your function conv_unit, create a function called norm_unit(s,DB) that returns a normalized representation of the unit s. 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 conv_unit finds the unit as some left-hand side of an entry in the database, you want to go through the numerator and denominator lists of the right-hand side of that entry (quantity list). As you go through the numerator and denominator, normalize each unit that appears and multiply them together. Since your multiply function always yields a simplified result, you are guaranteed that the product of a list of units is simplified and sorted. Once you have normalized both the numerator and denominator, use your function divide to get the overall result of normalization and then combine with the multiplier. If conv_unit doesn't find s in the database, norm_unit should return the same thing conv_unit does -- namely, [1.0, [s], []].

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

   
   
   
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) outputs the normalized equivalent to the quantity list QL with respect to the database DB.

   Recall that a quantity list always has the form [Amount, N, D], and N and D consist of lists of units (strings). So, to normalize a quantity list, you would apply norm_unit to the elements in N and D, and then multiply and divide as necessary. It turns out that norm and norm_unit can be expressed mutually recursively, with each calling the other (and perhaps itself, too). 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 difficult.)

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

   Follow the form 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.
   
   
4. Congratulations! You've completed unicalc [ or at least decided not to work on it any more :) ]. This problem and the following one ask you to write rex functions that operate on another data structure -- graphs -- in particular, graphs that are represented as binary relations, i.e., a list of [parent, child] pairs.

   Create the function biggestFan(G) that takes a graph G (as a binary relation) as input and outputs the node of G that has the biggest fan-in. The fan-in of a node is simply the number of parents of that node, so biggestFan returns the node with the most parents.

   If there is a tie for the biggest fan-in, you may return any one of the correct nodes. For example:

       rex >  biggestFan([ ["A","D"], ["B","D"], ["C","D"], ["A","E"], 
   	                ["D","E"], ["E","F"], ["F","A"]  ]);
       D
       
       rex >  biggestFan([ ["A","B"], ["B","C"] ]);
       B
       

   where the last answer could also have been C.
   
   
5. Write a predicate reachable(a,b,G) that determines (in essence) whether you can get from point a to point b. Specifically, the first two inputs are nodes in the graph G, which is the third input. reachable returns a 0 if there is no path from a to b, and it returns 1 if there is a path (possibly through other nodes) from a to b.

   NOTE Your predicate will only be given ACYCLIC graphs as input. Thus, you don't have to worry about "running around in circles" searching for whether there is a path from a to b, because there will be no cycles in the graph. Also, remember the graphs are directed. For example,

       rex >  reachable("A", "F", [ ["A","D"], ["B","D"], ["C","D"], ["A","E"], 
   	                ["D","E"], ["E","F"] ]);
       1
       
       rex >  reachable("C", "A", [ ["A","B"], ["B","C"] ]);
       0
       
       

   
   
   
6. This 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 list data structure. Write your class in a file called OpenList.java. Open lists are the type of linked list that rex uses. Open lists should never be modified (so that there is no worry about side effects) -- instead, each function returns a newly created list (or whatever data is appropriate).

   There is an example implementation of a Stack data structure in the file /cs/cs60/as/a3/Stack.java. Feel free to use it as a model for your OpenList class. In order to test the Stack class, copy the Stack.java file mentioned above to the directory in which you're working on this assignment. The command

        javac Stack.java
        

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

        java Stack
        

   will execute the code in the main function of Stack.java that tests some of the Stack data structure's abilities. Running your OpenList code works in the same way.

   For your OpenList class, implement the following functions (often called methods in Java):
   
   

   • CONSTRUCTORS
     
     
     • (A couple of these will be covered in detail in class in order to motivate the use and syntax of constructors.)
       
       
     • OpenList(Object first, OpenList rest) which is a constructor that returns an OpenList with first as its first element and rest as its rest.
       
       
     • OpenList() which is a constructor that takes no arguments and returns the empty list, i.e., an object with all data members equal to null.
       
       
     • OpenList(Object o1) which is a constructor that takes one argument and returns an open list with one element (the object o1).
       
       
     • OpenList(Object o1, Object o2) which is a constructor that takes two arguments and returns an open list with two elements.
       
       
     • OpenList(Object o1, Object o2, Object o3) which is a constructor that takes three arguments and returns an open list with those three elements, in the order they are input.
       
       
   • 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... .)
       
       
     • static OpenList cons(Object F, OpenList R) which is a static cons method that takes an object and an OpenList and returns an OpenList in which F is the first element and R is the rest of the list.
       
       
     • OpenList cons(Object F) which is a nonstatic cons method that takes an object as input and returns an OpenList in which F is the first element and the invoking OpenList is the rest.
       
       
   • APPEND
     
     
     • 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.
       
       
     • 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.
       
       
   • LENGTH
     
     
     • static int length(OpenList L) which is a static length method that returns the length of the input list.
       
       
     • int length() which is a nonstatic length method that returns the length of the invoking list.
       
       
   • FIRST
     
     
     • 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.
       
       
     • 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
     
     
     • 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.
       
       
     • 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.
       
       
   • IS_EMPTY
     
     
     • static boolean is_empty(OpenList L) which is a static predicate that returns true if the input list is the empty list and false otherwise.
       
       
     • boolean is_empty() which is a nonstatic predicate that returns true if the invoking list is empty and false otherwise.
       
       
   • TOSTRING
     
     
     • public String toString() which is a nonstatic method that returns a String representation of the invoking list. (This will be discussed in detail in class, and an example toString method will be provided in /cs/cs60/as/a3/OpenList.examples. You will only need to make sure that the data member names match your choices. Also, you do not need to create a static version of toString.
   
   
   To test your code (and please test as you go along!!), you will want to also write a method with the familiar signature

        public static void main(String[] arg)
        

   that creates some OpenLists, performs some operations on them and the prints out the results. If you can run all of the test code in the main method in the file OpenList.examples mentioned above, you should feel confident that your methods are correct. See the "Testing your code" section for more detailed instructions on how to test your Java code.
   
   
   
7. For optional bonus credit (up to 20%), improve your reachable predicate by creating a function named broadReach(G) that returns a list of all pairs [a,b], such that b is reachable from a in the input graph G. In this case, you will also need to handle input graphs that potentially have cycles; the order of the pairs, however, within the output list does not matter. For example,

          broadReach([ ["A", "B"], ["B","B"], ["B","C"], ["B","D"] ]);
          [ ["A","B"], ["A","C"], ["A","D"], ["B","B"], ["B","C"], ["B","D"] ]
   
          broadReach([ ["A", "B"], ["B","C"], ["C","A"] ]);
          [ ["A","A"], ["A","B"], ["A","C"], ["B","A"], ["B","B"], 
            ["B","C"], ["C","A"], ["C","B"], ["C","C"] ]