Assignment 5

Harvey Mudd College
Computer Science 60
Assignment 5, Due Monday, Oct. 8, by 11:59pm

Unicalc and Unilang

This homework asks you to use Java to implement the Unicalc application (that you completed in Scheme in the previous homework) by writing a Quantity class.

You'll then be able to leverage this work in order to implement a language based on that unit-conversion capability. Implementing the language will require you to use the Tokenizer class (provided), to write a Parser class, and to write an Evaluator class. Examples and starting points for the Parser and Evaluator are provided in links at the top-level assignment page.

Submitting your code

You will want to submit your four files

OpenList.java (which you might make changes to), and
Quantity.java (Problem 1) and
Parser.java (Problem 2) and
Evaluator.java (Problem 3)

in the usual way, under a HW5 subfolder.

Reading

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

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

You can compile everything in the current directory with


> javac *.java

The asterisk means "everything" at the command prompt.

Part 0: Changes to OpenList

0 points

While it's not required, I found it very helpful to add the methods

public Object second() ...
public Object third() ...

to the OpenList class, because the second and third elements of lists get accessed lots of time in what follows!

Part 1: Unicalc in Java via `Quantity`

40 points

This problem asks you to implement the Unicalc application in Java by building a class named Quantity. A starting Quantity.java file is available here and the top-level assignments page. Please start with this file, because it implements toString in a way that will make everyone's Quantity lists consistent to check!

The `Quantity` class

Objects of type Quantity will represent quantity lists, that is, something of the form

     { 9.8, [meter], [second, second] }

An object of type Quantity can also hold only a value - and it will always be a double value:

     { 42.0, [], [] }

Here, we are using the provided toString function, along with the OpenList class you wrote last week. ÿhe curly braces help distinguish objects of type Quantity from objects of type OpenList. We encourage you to use your own OpenList class again in this assignment (and to augment it with any functions that may be helpful!), you may also use our OpenList solution, which is linked at the top-level assignment page.

Here is an overview of Quantity.java:

Data members provided:

      private double quant;    // the multiplier
      private OpenList num;  // the numerator, an OpenList of Strings (units)
      private OpenList dem;  // the denominator, also an OpenList of Strings (units)

Methods provided:

      public Quantity(double q, OpenList n, OpenList d) ...  // constructor
      public toString() ...                // prints objects of type Quantity
      public static OpenList getDB() ...   // gets a pre-prepared database of units

Methods to write: (all static, except the first three, which are provided)

      public double getQuant();     // returns the multiplier
      public OpenList getNum();   // returns the numerator
      public OpenList getDem();   // returns the denominator
			
      // These six are translations from last week's Scheme code...
      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
      			
      // These next two are new for this week... ! See the notes below.
      public static Quantity negate(Quantity q);                   // returns negative of q
      public static Quantity plus(Quantity q1, Quantity q2, OpenList db);   // norm(q1) + norm(q2)

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. You're welcome to add a sort routine to the OpenList class and use it in the constructor of a Quantity, if you'd like but you don't need to do so.

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.scm 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 Scheme counterparts. Feel free to write nonstatic versions, but that is not required. We will test your code for the static versions, however. Also, there is no need to write convert itself, as it is an application of divide.

Two new methods There are two new methods that were not part of the Scheme unicalc application:

public static Quantity negate(Quantity q) This method should return a new object of type Quantity with the same numerator and denominator as q, but with a multiplier of opposite sign.

public static Quantity plus(Quantity q1, Quantity q2, OpenList db) This method should return a new object of type Quantity that represents the sum of q1 and q2 after normalizing each one in the database db. If, after normalizing both inputs, their units are identical, addition is straightforward. On the other hand, if the units are not identical, a warning message should be printed out and an error list such as { 0.0 ["error"] ["ERROR"] } should be returned. This will allow the unicalc-language interpreter to avoid crashing while still alerting the user to an error.

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 main. If you use your own OpenList class, you might not be able to run all of the tests provided (that's OK). We will also run some additional tests of our own. We will only test your code on valid, commensurate inputs, for example, for the plus method.

Part 1.5: `Tokenizer`

This is already provided for you in the code at the top-level assignment page.

Part 2: Parsing the Unicalc language via `Parser`

30 points

This problem asks you to implement a Parser for the Unicalc language, whose grammar is as follows:

Technical note on the grammar

The rule for Q uses the asterisk, not as "times," but meaning "zero or more of the preceding symbol. It also uses the plus sign, not as addition, but meaning "one or more of the preceding symbol. Both of these are implemented in the provided Q method in Parser.java.

The Parser class To do this, you should write a Parser class in a file named Parser.java. This should implement a recursive-descent parser for the above grammar, yielding an OpenList that represents the parse tree for a provided set of valid tokens. There is a starting point for such a class available in the startingFiles.zip archive at the top-level assignment page. In particular, that provided code already implements a number of methods for checking if there are remaining tokens (and what they are). In addition, it provides an implementation of Q(), for the Q nonterminal symbol.

Overview of parsing The method that will begin all the work (though all of that work will be delegated recursively) is parse:

public OpenList parse(String[] tokens) This method should return a new object of type OpenList that represents the parse tree for that set of tokens. We will not test your code on invalid sets of tokens. Here is a simple example of each one - keep in mind that they can be composed, as well. Also, double quotes have been added to highlight strings, but they will not be printed by Java.

USER INPUT            PARSE TREE
----------            ----------
def x 42              ["def", "x", [{ 42.0, [], [] }]]

# 1 joule             ["#", [{ 1.0, ["joule"], [] }]]

1 foot + 1 inch       ["+", [{ 1.0, ["foot"], [] }], [{ 1.0, ["inch"], [] }]]

1 foot - 1 inch       ["-", [{ 1.0, ["foot"], [] }], [{ 1.0, ["inch"], [] }]]

1 second * 2 hz       ["*", [{ 1.0, ["second"], [] }], [{ 2.0, ["hz"], [] }]]

1 second / 2 hz       ["/", [{ 1.0, ["second"], [] }], [{ 2.0, ["hz"], [] }]]

(1 cm)                [{ 1.0, ["cm"], [] }]    // note - no extra nesting!

(- 1 cm)              ["-", [{ 1.0, ["cm"], [] }]]

42.42 meter           [{ 42.42, ["meter"], [] }]

meter                 [{ 1.0, ["meter"], [] }]

42                    [{ 42.0, [], [] }]

2+3*4                 [+, [{ 2.0, [], [] }], [*, [{ 3.0, [], [] }], [{ 4.0, [], [] }]]]

and here is a concise summary of the resulting parse tree from each expression in the grammar:

Other methods for Parser Recursive-descent parsing uses a method for each nonterminal in the grammar - except for D and V in the case of this problem. One way to build up to the full grammar is to implement one nonterminal method at a time, for example, from the bottom towards the top. So, you would implement and test U(), and then P(), and then E(), and finally S().

Testing your code The main method is already written to make this easy - you should be able to try out all of the above inputs (and many more of your own) to be sure that your Parser is working correctly.

Part 3: Evaluating the Unicalc language via `Evaluator`

30 points

This part completes the unicalc language. Here, you should build an Evaluator class that has at least the following four things:

Data members:

      private OpenList env;  // the environment - a unit-database association list!

Methods:

      public Evaluator(OpenList env) ...                        // constructor
      public static Quantity evaluate(OpenList parseTree) ...   // returns the result, a Quantity
      public static void main(String[] args) ...                // for testing

There is a starting file for Evaluator.java, which evaluates Quantitys; it is available from the startingFiles.zip archive at the top-level assignment page.

What does everything evaluate to? Well, every valid statement in the Unicalc language evaluates to an object of type Quantity, that is, a quantity list. For example, the parse tree which is simply a list of a Quantity naturally evaluates to that Quantity object.

Some of the others are clear: addition, subtraction, negation, multiplication, division, and normalizing. Some of these operations (addition and normalizing) require a database of units... this database is the environment in which each expression is evaluated. The data member env (already at the top of Evaluator.java is provided for this purpose. This environment env starts out empty -- meaning that every unit is a basic, irreduceable unit. However, as you define units with def, conversions become possible. These are considered next.

The two parse trees whose evaluations may not be clear are these:

[ "def" V E ] This parse tree should evaluate to the value of E. After all, because of Java's strong typing, it will complain if your code does not return an object of type Quantity, and the value of E will be of exactly that type. However, the much more important function of def is that it should add to the front of environment's association list! This is probably best explained by example. Suppose that the Evaluator's association list env is at first
```
[ 
  ["mile", { 5280.0 ["foot"] [] }]
]
```
with the quotes and spacing added only for emphasis. Then, after the statement def league 0.125 mile, whose parse tree will be
```
[
  ["league", { 0.125, ["mile"], [] }],
  ["mile", { 5280.0 ["foot"] [] }]
]
```
We could even redefine "mile" - for example, after def mile 1760 yard, the new value of env would be
```
[
  ["mile", { 1760.0, ["yard"], [] }],
  ["league", { 0.125, ["mile"], [] }],
  ["mile", { 5280.0 ["foot"] [] }]
]
```
and assoc should "do the right thing" by taking the first match at the top. The data member env, already provided in the Evaluator, is the natural place to store the environment... .

[ "#" E ] This parse tree should evaluate to the normalized equalivalent of E within the current environment. # is simply the operator for normalizing.

Testing your code The main method is already written to make this easy - you should be able to try out all of the inputs below (and many more of your own) to be sure that your Evaluator is working correctly. Here are some examples, including the printout of the tokens, parse tree, value, and environment each time. To get all of this information to print, run "java Evaluator -debug" at the command prompt (if you leave off the -debug flag, you will only see the final returned value).

def mile 5280 foot
The tokens are < def, mile, 5280, foot >
The parseTree is [def, mile, [{ 5280.0, [foot], [] }]]
The value is { 5280.0, [foot], [] }
The current env is
[[mile, { 5280.0, [foot], [] }]]


def yard 3 foot
The tokens are < def, yard, 3, foot >
The parseTree is [def, yard, [{ 3.0, [foot], [] }]]
The value is { 3.0, [foot], [] }
The current env is
[[yard, { 3.0, [foot], [] }], [mile, { 5280.0, [foot], [] }]]


1 mile + 2 yard
The tokens are < 1, mile, +, 2, yard >
The parseTree is [+, [{ 1.0, [mile], [] }], [{ 2.0, [yard], [] }]]
The value is { 5286.0, [foot], [] }
The current env is
[[yard, { 3.0, [foot], [] }], [mile, { 5280.0, [foot], [] }]]


def x 2 mile - 1 foot
The tokens are < def, x, 2, mile, -, 1, foot >
The parseTree is [def, x, [-, [{ 2.0, [mile], [] }], [{ 1.0, [foot], [] }]]]
The value is { 10559.0, [foot], [] }
The current env is
[[x, { 10559.0, [foot], [] }], [yard, { 3.0, [foot], [] }], [mile, { 5280.0, [foot], [] }]]


x / 1 foot
The tokens are < x, /, 1, foot >
The parseTree is [/, [{ 1.0, [x], [] }], [{ 1.0, [foot], [] }]]
The value is { 1.0, [x], [foot] }
The current env is
[[x, { 10559.0, [foot], [] }], [yard, { 3.0, [foot], [] }], [mile, { 5280.0, [foot], [] }]]


# x / 1 foot
The tokens are < #, x, /, 1, foot >
The parseTree is [#, [/, [{ 1.0, [x], [] }], [{ 1.0, [foot], [] }]]]
The value is { 10559.0, [], [] }
The current env is
[[x, { 10559.0, [foot], [] }], [yard, { 3.0, [foot], [] }], [mile, { 5280.0, [foot], [] }]]


3 yard yard + 1 foot * 2 foot
The tokens are < 3, yard, yard, +, 1, foot, *, 2, foot >
The parseTree is [+, [{ 3.0, [yard, yard], [] }], [*, [{ 1.0, [foot], [] }], [{ 2.0, [foot], [] }]]]
The value is { 29.0, [foot, foot], [] }
The current env is
[[x, { 10559.0, [foot], [] }], [yard, { 3.0, [foot], [] }], [mile, { 5280.0, [foot], [] }]]

Optional extra credit

Personalizing For up to +5 points, improve the unicalc-language with whatever features you would like! Here are the rules, however:

do not change or break valid statements in the language as specified in the assignment (so we can still grade it!)
in a comment at the top of Evaluator.java document what you did and how we can test it. Give the graders a couple of examples to try.

Tokenizing For up to +5 points, improve the Tokenizer so that users do not have to place a space between a numeric value and a unit name. But make sure that users can still use numbers within an identifier, as long as that identifier begins with a lower- or upper-case letter. For example,


42cm                  // user's input
{ 1.0, ["42cm"], [] } // old ... needs improvement
{ 42.0, ["cm"], [] }  // new ... better!

def x1 20             // user's input - OK
3 x1                  // user's input 
{ 3.0, [x1], [] }     // make sure this is still OK!

Lambda! For up to +15 points, implement functions in the Parser and Evaluator of the unicalc language. You may choose how you do this, but for full credit, you should make sure (similar to the add-your-own-feature option, above) that you

do not change or break valid statements in the language as specified in the assignment (so we can still grade it!)
document in a comment at the top of Evaluator.java what you did and how we can test it, including how you handle input parameters and unbound symbols in the body of a function. Give the graders a couple of examples to try.
describe how you had to change your Parser and Evaluator to make this work

Harvey Mudd College Computer Science 60 Assignment 5, Due Monday, Oct. 8, by 11:59pm