Harvey Mudd College
Computer Science 60
Assignment 3, Due Friday, Sep. 22, 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. Your Java class (problem 6) should be in a file named OpenList.java . Submit with 

cs60submit 3
from the directory that contains these two files.

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 an integer, 1-10. To test a particular rex function in hw3.rex, use 

% rex hw3.rex < /cs/cs60/as/a3/Test1.in
where Test1.in can be replaced wih any of the rex test files.

To test your java class, OpenList, you might want to write your own main method that tries out your OpenList methods. An alternative is the way the test script will interact with your code. Here are the steps:

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 - /cs/cs60/as/a3/Test#.out
If you see nothing (that is, no "differences" occur), you know your code is producing the correct output. If you do see lines beginning with "<", they are output lines that your program printed , but do not appear in the Test#.out file. Lines beginning with ">" appear in the solutions, but not your program's output; lines beginning with "<" appear in your program's output, but not the solutions.

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 (9/18) there will be a solutions file from Homework2 in the /cs/cs60/as/a2/ directory 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,


    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. That is, 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]]


    Hint: read the next problem befor solving this one.

  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.

    Hint: 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 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 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 submit 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 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. You may assume that biggestFan will only receive graphs that do have edges as input.

    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
    Your function should acknowledge that any node can be reached from itself (by not moving along any edges at all).

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

    First, in your OpenList class, you will want to indicate the data that comprises a list. That data should include two Objects: 

              Object first;
          OpenList rest;
    In fact, these are the only data members you will need in your list implementation, though you may use others, if you wish. 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, though the next assignment will put your OpenList class to use... .

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



    To test your code (and please test as you go along!!), you may want to write a method with the familiar signature 
         public static void main(String[] arg)
    In that method you can create OpenLists, perform some operations on them and then print out the results. In addition, the test files in /cs/cs60/as/a3 check that portions of your code are working. See the "Testing your code" section for detailed instructions on how to test your Java code.



    Hint: for append and reverse, using recursion will make your code much simpler... . Java supports recursion to the same extent that rex does, though the syntax looks a bit different.

  7. For optional bonus credit (up to 10%), 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. In addition, the order of the pairs within the output list should be sorted. For example, 
           broadReach([ ["A", "B"], ["B","B"], ["B","C"], ["B","D"] ]);
       [ ["A", "A"], ["A","B"], ["A","C"], ["A","D"], ["B","B"], 
         ["B","C"], ["B","D"], ["C", "C"], ["D", "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"] ]


    Note that, again, any node is reachable from itself.

  8. For additional and completely optional bonus credit (up to 10%), add methods with signatures 
            static OpenList duperreverse(OpenList L);
        OpenList duperreverse();
    that implement the duperreverse function from assignment 1 for your OpenList class.

    Hint: you may want to read about the getClass method of the Object class and the getName method of the Class class (!) from the Sun Java Docs. Remember you need to use the nonstatic method equals(String s) to compare strings. (At least I used all this stuff... there are probably better ways.)