Harvey Mudd College
Computer Science 60
Assignment 4, Due Sunday, February 15, by 11:59 pm


Link to the CS 60 submission site
Back to the top-level assignments page
Back to the top-level CS 60 page

Rex in Java and Java in Rex?

This homework highlights the similarities and differences between the computational styles of an object-oriented language (Java) and a functional language (Rex). In a sense, this hw implements a bit of Rex in Java and vice versa!

The Problems

Files for getting started

You'll probably want to develop your functions in a hw4 subdirectory within your cs60 directory. There will be three files to submit this week. They are

  • OpenList.java -- a Java implementation of Rex's list structures
  • Quantity.java -- a Java implementation of Unicalc's quantity lists and of the Unicalc algorithm itself!
  • parse.rex -- a single file that contains this week's three rex functions: tokenize, parse, and Evaluate.
You can copy starter files for all of these from the directory /cs/cs60/hwfiles/a4/.

Style

From this assignment onward, some of the points will be awarded based on your programs' commenting, formatting, and design -- under the heading of style.

Any readable and well-commented style is OK. These are some of the things to look out for when writing programs for yourself (or others) to read:

  • Design
  • Use small, clear functions -- with helper functions of your own design, as needed or desired. Large, convoluted functions are difficult to read and understand -- more importantly, however, they're very difficult for the original programmer to modify and debug!


  • Formatting
  • Please use ample whitespace: blank lines between functions, spaces within expressions to make them readable and separate component parts.
  • This also includes a clear and clear structure to your code, and indenting that indicates that structure.
  • You should use meaningful variable names. One-letter variable names are OK if they are a common idiom, e.g., f and R for first and rest or i for an index variable.
  • You should keep your lines of code to less than 80 characters -- this helps to make it readable from within all kinds of programs, and avoids wrapping issues.


  • Comments
  • We ask you to include a top-of-file comment with your name, partner (if any), time spent, and any other comments for the graders (or instructors)
  • Each function, even your own helper functions, should have at least a short top-of-function comment documenting its purpose, inputs, and outputs.
  • Comments within functions are welcome, but not required unless something tricky is going on. Many people find them helpful to write because they keep the flow of the program in mind.

OpenList.java    Individual problem, #1

[30 points, individual]

There is one individual-only problem this week: the OpenList data structure, to be implemented in Java. An "open list" is a recursively-defined linked list of cons cells whose data and strucure are not modified so that data-sharing is encouraged and safe. Instead of modifying data, each function returns a newly created OpenList -- or whatever other type of data is appropriate.

This problem introduces the implementation of functional-style data structures in Java. In addition, it is a chance to either extend your introducton or your review of what Java looks like and how java code is structured. We will talk in class about the OpenList class, as well as some of the details that are provided in the starter file, OpenList.java.

Write your OpenList class in a file called OpenList.java. You should start with the OpenList.java file available at /cs/cs60/hwfiles/a4/.

The provided main method of this OpenList.java contains a couple of tests. Compile and run the file before adding code. Read it over in order to get a sense of what it is doing and how it is organized. There are many more tests available for copy-and-paste at this link and from the top-level assignments page.

Writing the OpenList class

First, in your OpenList class, you will want to indicate the data that constitute a list. There are two non-static data members (first and rest) and one static data member (emptyList) in an OpenList: 

          
    // two private data members
    private Object first;
    private OpenList rest;

    // one public data member: the emptyList is static (owned by the class)
    public static OpenList emptyList = new OpenList(null, null);

These are the only data members you will need in your list implementation -- and they're already there for you. You may use other data members, if you would like -- in fact, there is considerable leeway in how you want to implement OpenList. However, it does have 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 these types: 

int
double
float
boolean
byte
char
long
We will use only objects of type String and of type OpenList for this assignment. The next problem, on the other hand, will put your OpenList class to work... .

In your OpenList class, be sure to implement the following methods. Some are in the file already; for those, read them over as they provide a useful guide to the others:

  • OpenList, the CONSTRUCTOR

    • This method is provided, and it will be covered in detail in class in order to motivate the use and syntax of constructors. Constructors are always named for the type of the objects they construct.

    • public OpenList(Object f, OpenList R) is a constructor that returns an OpenList with f as its first element and R 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 non-static 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 = new OpenList( "Hi!", emptyList ); // an example of using the constructor
System.out.println("List L is " + L);
      The above code should output 
      List L is [ Hi! ]
  • cons   

    • public static OpenList cons(Object f, OpenList R) is a static list-constructing method that takes a string f and an OpenList R. Then cons returns an OpenList in which f is the first element and R is the rest of the list. It simply delegates to the constructor!

    • public OpenList cons(Object f) is a non-static 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 very Rex-style approach to handling data.

  • isEmpty

    • public static boolean isEmpty(OpenList L) is a static predicate returning true if the input list is the empty list and false otherwise. In Java, 0 and 1 are not boolean values; true and false are.

    • public boolean isEmpty() is a non-static predicate that returns true if the invoking list is empty and false otherwise.

  • 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. Read those over as an example of how OpenLists can be used.

    • public OpenList assoc(Object o) is a non-static version of assoc. It is also already present in the 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 then exit completely. To exit a Java program immediately, use the line 
      System.exit(0);

      Compiler complaints about return not being present?    Watch out -- if the compiler sees 

      if (this.isEmpty()) {
  System.exit(0);
}
else {
  return this.first
}
      it will complain, saying that the method needs to return an Object in all paths through the code. The compiler doesn't realize that System.exit(0) is as final as it is. So, you'll need to include a dummy return null in the if block or get rid of the else keyword entirely.

      That said, we won't test this method on non-empty lists! Note: the basic idea here is simply to return L.first!

    • public Object first() which is a non-static 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) 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() is a non-static method that returns the rest of the invoking list. If the invoking list is empty, your function should print out an error and exit.

  • length

    • public static int length(OpenList L) is a static length method that returns the length of the input list.

    • public int length() is a non-static length method that returns the length of the invoking list.

  • list

    • public static OpenList list(Object o1) is a static method that returns an OpenList of one element, o1. Note that there is no non-static version of the list method, because there might not be a list around to invoke it!

    • public static OpenList list(Object o1, Object o2) is a static method that returns an OpenList of two elements (in the order they're input). Again, there's no non-static version.

    • public static OpenList list(Object o1, Object o2, Object o3) is a static method that returns an OpenList of three elements (in the order they're input). Again, there's no non-static version.

  • append

    • public static OpenList append(OpenList L, OpenList M) is a static append method that takes two OpenLists and returns an OpenList that is their concatenation.

    • public OpenList append(OpenList M) is a non-static 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" in the result of append. Again, the invoking list is not changed -- because this OpenList 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) 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() is a non-static 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. Thus, the result is like appending, but the sorted order is preserved.

      As a brief review, 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, which 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 the invoking string is before the input-argument string in terms of dictionary order.

      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 each one 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 non-static method that takes an OpenList as input and does the same thing as the static 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.


Other methods...

The above list are the required methods for your OpenList class -- we will test those. However, if you would like to implement one or more additional methods in order to help with the subsequent problem, Quantity, feel free!




Quantity.java and parse.rex    Pair or individual problems, #2-3

You're welcome to work on the balance of this week's problems on your own, but we'd encourage you to do so with a partner, if you'd like. If you do work in a pair, be sure to work at the same physical place and to trade off at the keyboard/debugging roles, as described in the syllabus.

Whether you work on your own or with a partner, you should submit your files as named above: Quantity.java and parse.rex. Also, please be sure to name your Java methods and Rex functions as specified -- this helps the graders immensely!


Problem 2:    Quantity.java a Quantity List class

[20 points, individual or pair]

Keeping everything in one directory...

Because the .java files you write this week will be interdependent, keep them all in a single folder/directory. That way, java will be able to find classes as it needs to.

At the terminal window (on Mac or on PC), you can compile everything in the current directory with 


javac *.java
The asterisk means "everything" at the command prompt.

This problem asks you to implement the Unicalc application in Java by building a class named Quantity. A starting Quantity.java file is available the top-level assignments page in and from the directory /cs/cs60/hwfiles/a4.

The Quantity class

Objects of type Quantity will represent quantity lists, that is, something of the form 
     { 9.8, [meter], [second, second] }
Note that a Quantity is delimited by curly braces. It will always contain three elements: a quantity, followed by a numerator unit-list, followed by a denominator unit-list. Here are two more Quantitys: 
     { 10.0, [kg, meter], [] }

     { 42.0, [ ], [ ] }
In these examples we are illustrating the provided toString method, which relies on OpenList's toString method, as well. The curly braces are used to distinguish objects of type Quantity from objects of type OpenList.

Here is an overview of what capabilities Quantity.java should have

  • Data members: 
          private double m;    // the multiplier
      private OpenList N;  // the numerator, an OpenList of Strings (units)
      private OpenList D;  // the denominator, also an OpenList of Strings (units)
  • Methods: 
          public Quantity(double m, OpenList N, OpenList D) ...  // constructor
      public toString() ...                // prints objects of type Quantity
      public static OpenList getDB() ...   // gets a pre-prepared database of units
			
      // you may augment these with additional methods, if you like
      public static Quantity simplify(Quantity Q);                 // simplifies the input, Q
      public static Quantity multiply(Quantity Q1, Quantity Q2);   // multiplies the inputs
      public static Quantity divide(Quantity Q1, Quantity Q2);     // divides the inputs
      public static Quantity conv_unit(String unit, OpenList DB);  // looks up unit in DB
      public static Quantity norm_unit(String unit, OpenList DB);  // normalizes unit in DB
      public static Quantity norm(Quantity Q, OpenList DB);        // normalizes Q in DB
      // we don't bother with convert, since it's just divide
  • and main: 
          public static void main(String[] args);     // for testing your code!

Presuming the numerators and denominators are sorted    We will test your code only with Quantity lists whose numerators and denominators have units in sorted order.

How do I compare two Strings in Java?    As in the merge method that is part of this week's OpenList class, you will want to use the method compareTo 

  String s1 = "apple";
  String s2 = "zebra";
  if (s1.compareTo(s2) < 0) ... // this will be true!
compareTo returns a negative value if this (the calling object) is earlier in the dictionary (i.e., ASCII order) than the input argument s2. If they're equal 0 is returned. If s2 is earlier, a positive number is returned. The compareTo method is fully documented at this link. There is also a compareToIgnoreCase, but to be consistent with our tests, please use compareTo here (everything is lower case anyway).

Like OpenLists, objects of type Quantity are not meant to be changed. Rather, the methods above return new objects of type Quantity based on their inputs. Indeed, six of the methods above are based on last week's Unicalc assignment, a solution to which is posted at the top-level assignment page, if you'd like to use it. The reason that these six are all static is to more closely resemble their Rex counterparts.

Also, there is no need to write convert itself, as it is an application of divide.

Testing your code    You should write your main method so that it constructs several objects of class Quantity and tests all of your class's methods. There are a few tests (commented out) that are already in the provided main. We will run those and a few additional tests of our own.

Problem 3:    tokenize, parse, and Evaluate: recursive descent parsing in Rex

[50 points, individual or pair]

In this part of the assignment you will be writing a recursive descent parser and an evaluator for arithmetic expressions with a number of operators and parenthesization.

In particular, we will use the unambiguous context-free grammar that we saw in class: 

S -> P + S | P - S | P
P -> E * P | E / P | E
E -> U ^ E | U
U -> ( S ) | - V | V
V -> a nonnegative integer
As you work with it, you'll note that this language is right-associative, which is different than the left-associative basic operators customary in arithmetic. This is OK -- you will be able to get right-associative behavior with parentheses. Keep in mind that arithmetic conventions - usual or unusual - need to be explicitly considered when writing a language. This problem employs an unusual one - at least in its right-associativity - in this case.

Your task is to write a recursive descent parser for this grammar. You may certainly use a number of functions to help you in this effort, but the three primary functions (that we will test!) are as follows:

tokenize( s )

   One of the functions in your file should be called tokenize( s ), which takes in a string s. It should output a list of tokens, i.e., "pieces" of the arithmetic language. Those tokens should be strings. In addition, your tokenizer should be able to handle spaces appropriately -- that is, the input string should be tokenized regardless of whether and how much whitespace there is around the operators or integers. For instance, 
test( tokenize( "1+2" ),  [ "1", "+", "2" ] );
test( tokenize( "1 +   2" ),  [ "1", "+", "2" ] );
test( tokenize( "11+31^1" ),  [ "11", "+", "31", "^", "1" ] );
test( tokenize( "11   +31 ^1" ),  [ "11", "+", "31", "^", "1" ] );
test( tokenize( "(11+-31)^1" ),  [ "(", "11", "+", "-", "31", ")", "^", "1" ] );
test( tokenize( "( 11   +-31) ^1" ),  [ "(", "11", "+", "-", "31", ")", "^", "1" ] );

Some people want to use make_string in order to create a large list of integers -- but as strings. make_string does not work in Rex! You can use this function, however: 

DIGITS = ["0","1","2","3","4","5","6","7","8","9"];
toString( x ) => is_string(x) ? x;
toString( x ) => x <  0 ? concat( "-", toString(-x) );
toString( x ) => x < 10 ? DIGITS(x); // subscripting
toString( x ) => concat( toString( x/10 ), toString( x%10 ) );
toString( x ) => "I didn't understand the input to toString.";

//test( toString( -424242 ), "-424242" );
//test( toString( 24242 ), "24242" );
//test( toString( -3 ), "-3" );
//test( toString( -2 ), "-2" );
//test( toString( -1 ), "-1" );
//test( toString( 0 ), "0" );
//test( toString( 1 ), "1" );
//test( toString( 2 ), "2" );
//test( toString( 3 ), "3" );

parse( TL )

   Another of the functions in your file should be called parse( TL ), whose input is a list of tokens -- presumably, this token list will be the output of tokenize! Parse should proceed to return a list of two things:
  1. A parse tree, which is a tree of operations and variables that reflects the computational structure of the input expression as we demonstrated in class.
  2. A residue list, a list of characters (tokens) that have not yet been parsed.
Note that the first element in each case will be a parse tree, and the second element will be the residue list. If the parsing was successful, the residue will be the empty list.

From our experience, a good way to approach this problem is to first build a parser for a simplified version of this grammar. For example, in the starter file, parse.rex, a limited grammar is implemented: 

S -> P + S | P
P -> V
V -> a single-digit nonnegative integer
A first step might be to implement the slightly larger grammar: 
S -> P + S | P
P -> E * P | E
E -> V
V -> a single-digit nonnegative integer
Once you get the parser working for this grammar, you can continue to extend it to the full parser (and tokenizer and Evaluator) for this problem. Do not use your parser to convert strings to integers - this step is better left to the Evaluator (below) for two reasons: one, it will make it easier to test parsing if all tokens are strings; two, that conversion from string to integer is, in fact, part of the expression-evaluation process, not the parsing one. By the same token, do not use your parser to tokenize -- combine digits into integers with your tokenize function.

To encourage an incremental approach, this problem will be scored based on the features your language implements:

  • addition and subtraction: already complete
  • 10 points: tokenizing multidigit integers and whitespace
  • 10 points: multiplication and division (parsing)
  • 10 points: exponentiation (parsing)
  • 10 points: parens and negation (parsing)
  • 10 points: evaluation of parse trees
Thus, getting your language to work fully without parens or negation is a good first step. If you have time for the U rule, all the better!

Here are some examples of how your parse function should work after implementing the whole grammar. Please run the appropriate subset of these tests as you build your parser -- that way you'll know you're on the right track. 

// note that spaces and multi-digit integers are not
// used in these tests, but they will be when graded

// addition and subtraction
test( parse( [ "1" ] ),  [ "1", [] ] );
test( parse( [ "1", "+", "2" ] ),  [ ["+", "1", "2"], [] ] );
test( parse( [ "1", "+", "2", "+", "3" ] ),  [ ["+", "1", ["+", "2", "3"]], [] ] );
test( parse( [ "1", "-", "2" ] ),  [ ["-", "1", "2"], [] ] );
test( parse( [ "1", "-", "2", "-", "3" ] ),  [ ["-", "1", ["-", "2", "3"]], [] ] );

// multiplication and division
test( parse( [ "1", "*", "2", "+", "3" ] ),  [ ["+", ["*", "1", "2"], "3"], [] ] );
test( parse( [ "1", "*", "2", "*", "3" ] ),  [ ["*", "1", ["*", "2", "3"]], [] ] );
test( parse( [ "8", "/", "2", "+", "3" ] ),  [ ["+", ["/", "8", "2"], "3"], [] ] );
test( parse( [ "6", "/", "4", "/", "2" ] ),  [ ["/", "6", ["/", "4", "2"]], [] ] );

// exponentiation
test( parse( [ "1", "*", "2", "^", "5", "+", "3" ] ),  [ ["+", ["*", "1", ["^", "2", "5"]], "3"], [] ] );
test( parse( [ "2", "+", "3", "^", "2" ] ),  [ ["+", "2", ["^", "3", "2"]], [] ] );
There are also tests of the U rule, below - but it's probably better to make sure the binary operators are working first, and the continue on to Evaluate, next. After those pieces work for the rest of the grammar, then return to implement the U rule.

Getting started    Take a look at (and feel free to use any part of) the file parse.rex which is in the directory /cs/cs60/hwfiles/a4/. It shows a recursive descent parser (with an initial tokenizer and Evaluator) for expressions using only addition, single-digit integers, and no whitespace.

Evaluate( PT )

   Once you have successfully written at least some of your recursive descent parser, implement an Evaluate( PT ) function and whatever other helper functions you need. Evaluate( PT ) takes as input a parse tree of the sort output by parse. It then returns the value of that parse tree. Warning: Rex does have a built-in function named eval -- avoid using that name in your file!

We will only call Evaluate on well-formed parse trees! For example, here are some tests for your Evaluate function - you might try these incrementally, as well: 

// tests of Evaluate

// addition and subtraction
test( Evaluate( "1" ),  1 );
test( Evaluate( ["+", "1", "2"] ),  3 );
test( Evaluate( ["+", "1", ["+", "2", "3"]] ),  6 );
test( Evaluate( ["-", "1", "2"] ),  -1 );
test( Evaluate( ["-", "1", ["-", "2", "3"]] ),  2 );


// multiplication and division
test( Evaluate( ["+", ["*", "1", "2"], "3"] ),  5 );
test( Evaluate( ["*", "1", ["*", "2", "3"]] ),  6 );
test( Evaluate( ["+", ["/", "8", "2"], "3"] ),  7 );
test( Evaluate( ["/", "6", ["/", "4", "2"]] ),  3 );

// exponentiation
test( Evaluate( ["+", ["*", "1", ["^", "2", "5"]], "3"] ),  35 );
test( Evaluate( ["+", "2", ["^", "3", "2"]] ),  11 );

The Evaluate function will need to convert some of its strings (those that aren't operators) to integers. Rex has a built-in function make_number which does this, e.g., make_number("42") yields 42.

What about U?

It is probably a good idea to get the rest of the language working before handling the U rule of the grammar. However, once "U" get to it, these tests will help verify that U is working correctly, both reagarding the parse and Evaluate functions: 

// parentheses and negation - parse tests
test( parse( [ "(", "1", ")" ] ),  [ "1", [] ] );
test( parse( [ "(", "1", "*", "2", ")", "^", "(", "5", "+", "3", ")" ] ),  [ ["^", ["*", "1", "2"], ["+", "5", "3"]], [] ] );
test( parse( [ "(", "2", "+", "3", ")", "^", "2" ] ),  [ ["^", ["+", "2", "3"], "2"], [] ] );
test( parse( [ "-", "1" ] ),  [ ["-", "1"], [] ] );
test( parse( [ "-", "1", "+", "2" ] ),  [ ["+", ["-", "1"], "2"], [] ] );
test( parse( [ "1", "+", "2", "+", "-", "3" ] ),  [ ["+", "1", ["+", "2", ["-", "3"]]], [] ] );

// parentheses and negation - Evluation tests
test( Evaluate( "1" ),  1 );
test( Evaluate( ["^", ["*", "1", "2"], ["+", "5", "3"]] ),  256 );
test( Evaluate( ["^", ["+", "2", "3"], "2"] ),  25 );
test( Evaluate( ["-", "1"] ),  -1 );
test( Evaluate( ["+", ["-", "1"], "2"] ),  1 );
test( Evaluate( ["+", "1", ["+", "2", ["-", "3"]]] ),  0 );
Unlike S, P, and E, the U rule should probably check its first token right off the bat: if it's a left-paren, the rule will do one thing; if it's a minus sign, it will do another thing; otherwise, it will delegate to v.





Totally gratuitous but cool extra credit:    Java's mergesort, duperreverse, and anylist

[up to +10 points, pair or individual]

These problems ask you to write additional methods in your OpenList.java file (that is, your OpenList class). You don't need to submit any other files. Note, however, that these won't be part of next week's assignment (as has been the case in the past).

  • Optional Extra credit of up to +3 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 non-static version.


  • Optional Extra credit of up to +3 points    duperreverse in Java!

    Write public OpenList duperreverse(), which is a non-static method that takes no inputs and should return a list that is the fully-recursive-reverse of the invoking OpenList, this. This is the Java version of duperreverse that you wrote in hw #1.

    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 +4 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.

    How mergesort works

    Mergesort delegates almost all of the work of sorting the input list to the merge subroutine. It first handles its base cases: when the input list has 0 or 1 element, it's done, because such a list is already sorted! On the other hand, if the input list has more than 1 element, the idea is to first split that input list into two lists that are within one element of being the same size. After obtaining two lists from that split, a recursive call to mergesort is made on each piece, and then they're merged! For reference, here is the Rex code (although split is not built-in to Rex): 

    mergesort( L ) => length(L) < 2 ? L;
mergesort( L ) => [ F, S ] = split(L),      // split it in half
                     Fsorted = mergesort(F),
                     Ssorted = mergesort(S),
                     merge( Fsorted, Ssorted );
    I always find it remarkable that this works!

    No non-static 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. You can create an array as follows: 

    // this creates an array of two OpenList references. 
// both are initially null!
OpenList[] ourOpenListArray = new OpenList[2];
// at this point, you have 
// ourOpenListArray[0] == null   and
// ourOpenListArray[1] == null
// but they are both ready to be assigned to other (real!) OpenLists...
    It works equally well to write split to returns an object of your own newly-defined class type that holds the two resulting OpenLists.




Submitting your work

Be sure to submit your OpenList.java, Quantity.java, and parse.rex files at the CS 60 submission site under "Week 4." If you worked on the extra credit, those functions will be in your OpenList.java file, as well.

Submitting pair programs:    Partners who have created one file together should each submit that file, under their own names. You may have to close the browser and then re-open it, in order to log in as the other person.

A link to hw#1's directions for moving files from machine to machine and for using the submission site.

Problems with submission? Drop me an email at dodds - AT - cs.hmc.edu.




Link to the CS 60 submission site
Back to the top-level assignments page
Back to the top-level CS 60 page