Harvey Mudd College
Computer Science 60
Assignment 04

Unicalc in Java

Due Dates: Due by midnight on the morning of your next lab:

• For sections 3 and 6 this means before Wed. Oct. 2.
• For sections 1, 2, 4, and 5 this means before Oct. 7.

In this assignment, you will implement a version of Unicalc in Java. In so doing, you will make use of, and add to, your OpenList class. You will use a class UnicalcParser that I have provided, which parses free-form expressions and returns a syntax tree as an OpenList. (Later on, you will learn how to construct such a parser yourself.) You will need to convert syntax trees to Unicalc Quantities using recursion, and implement the other functions operating on Quantities need to do conversion.

This assignment will likely be a little more time-consuming than previous ones, so please don’t get caught short. It will probably require 200-300 lines of Java coding.

Reading: This assignment covers material through Chapter 5 in the text.

To be done in lab:

• Read the assignment over.
  
  
• Copy the class files/cs/cs60/a/04/*.class to your working directory. These contain a pre-compiled expression parser for Unicalc expressions. Some .class files will get overlaid with ones compiled from your sources.
  
  
• Complete and test as many of the definitions as possible, starting with your Quantity class.
  
  
• Try to use RCS (Revision Control System), which I will explain in class, to help manage your development process. It can save much effort in the long run.

Who Provides What? The following files are involved:

File	Purpose	Provider
Quantity.java	Unicalc Quantity class with methods	You
OpenList.java	OpenList class	You (or me)
Unicalc.java	Shell Unicalc application	Me
UnicalcParser.class	Parser that reads input stream and produces syntax trees as OpenLists.	Me
LineBufferInputStream.class	Buffer stream for use in reading input and file.	Me
Function1.java, Function2.java, NormalizeUnit.java	Various auxiliary files	Me or you

You will need to augment your OpenList class with some additional methods, such as the assoc function. If you are not happy with your OpenList class, ask me if you can use mine, provided that you have already submitted your a03.

A distinction from a02.rex is that you are advised to define a class implementing Quantity, rather than simply use an OpenList of three elements. This will provide more valuable experience in defining classes. A Quantity will thus have three components: a floating number representing the multiplicative factor, and two OpenLists of units. Functions simplify, multiply, divide, etc. will thus become static methods of Quantity.

It is strongly recommended that you transcribe your a02.rex code to Java to do most of Quantity.java. That’s what I did. You will still need to provide a toString method for Quantity.

.class files are produced from .java source files upon compilation. In one case, I provide only the .class file, because coding the Unicalc parser may be the subject of a future assignment.

Commenting

Comment your code. Be sure your comments indicate what each method does, including what the inputs and outputs are. For non-obvious methods, comment how it works as well.

Testing your code

You will be provided with one or more test files. Use them as:

java Unicalc < testfile

once your files have been compiled. Test your code before submitting it to be sure there are no typos, misspellings, etc. and that it works as expected. Failure to do so may cost you points.

Submitting your code

You should submit your rex functions in two files: Quantity.java and OpenList.java using

cs60submit Quantity.java OpenList.java . . .

where . . . represents any other supported.java files needed. Do NOT submit .class files. The .class files I provided will be available automatically when we grade your assignment.

Unicalc in Java

A good way to begin is create your Quantity.java file with an empty class Quantity. Copy your a02.rex file inside but make every line a comment. If you did not do well on the Unicalc in rex assignment, then copy the sample solution instead.

The idea is that you will transcribe your rex definitions, now in the form of Java comments, into Java.

Defining Unicalc Quantities

Slightly different from our rex implementation, we are going to implement Quantity as its own class. This will provide better compile-time type checking. The main constructor for Quantity will be one that takes a float and two OpenLists as arguments, which replaces the list of three elements that we used in rex. You may wish to define other constructors for convenience.

Define the static methods simplify, multiply, divide, etc. on Quantity using the rex code as a guide. For the database, use an OpenList association list of pairs, with the first element of each pair being a String and the second being a Quantity. You will need to code the assoc function and various other functions.

Code the map and reduce methods in Java, using the Function1 and Function2 interfaces as we discussed in class, or you may instead code specific uses of map and reduce without using higher-order functions. Later I provide some code to help with the former.

A Better Interface

The rex interface that we’ve been using would not be considered user-friendly to an average user. So in this assignment, we are going to use a free-form interface, similar to the one provided by executing:

java -classpath /cs/cs60/a/04/ Unicalc

The -classpath incantation tells the java interpreter where to look for the .class files it needs. If you have not checked out running the above program, please do so at this time. You will want your results to be identical, so that we can use automation to check them.

I provide a parser for you in the form of a set of class files. This parser will use your OpenList class. It reads one Unicalc expression per line and returns a syntax tree representing that expression. A syntax tree shows the intended structure of the input very nicely. The idea of a syntax tree is explained in the lecture. Non-atomic input will be returned by the Parser as an OpenList. Atomic input, representing a single tree, will be either a Float or a String, depending on whether the atom is numeric or not.

Use the Java built-in instanceof to determine what kind of Object is in each node of the tree. It will always be one of: Float, Integer, String, OpenList, or null. null is used to indicate that the input could not be correctly parsed.

Below are some concrete examples of the trees that UnicalcParser will create for you. Note that numerals are really members of class Float or Integer and that other atoms are members of class String. Integer is only used as the second argument of a ^ (raise-to-power) operator, and Float is used in all other cases. The strings “*”, “/”, “^” represent the operators multiply, divide, and raise-to-power respectively.

Free-Form Input	Tree returned from UnicalcParser
5	5.0 (a Float)
foot	foot (a String)
5 foot pound	[*, 5.0, foot], pound] (an OpenList)
5 foot pound / second	[/, [*, [*, 5.0, foot], pound], second]
3.4 meter / second ^2	[/, [*, 3.4, meter], [^, second, 2]]
(3.4 foot pound / second) ^2	[^, [/, [*, [*, 3.4, foot], pound], second], 2]

The parser is pretty liberal about what input it will accept. Conversion of trees to Quantitys is not really hard when you have recursion do the work for you, in conjunction with your methods in class Quantity.

Summary of Key Steps:

1. Create skeletal Quantity.java file.
   
   
2. Copy rex Unicalc definitions into class Quantity as comments. You may use your rex code or mine, but state which.
   
   
3. Define methods that work on Quantity and database, transcribing from rex. This will entail augmenting your OpenList.rex slightly. Keep functions that are not particular to Quantity in OpenList; do not put generic list functions into Quantity. You will also need to construct a toString method for Quantity.
   
   
4. Construct a method makeQuantity that converts a syntax tree into a Quantity. This will be called by my UnicalcParser.
   
   
5. Check that your Quantity class works with the Unicalc class provided, and produces the same results on the test data.

Notes:

1. While it could be done, we are not suggesting the creation of additional classes, such as Database, UnitsList, etc. at this time, even though a complete object-oriented design might start with these things. Rather use your time to get to an effective solution using the existing OpenList class.
   
   
2. You can run the UnicalcParser stand-alone, to see what trees are produced for a given expression:
   java -classpath /cs/cs60/a/04/ UnicalcParser
   
   
3. If you declare a class to be public, it must be in a file by itself, with the filename stem being the same as the class.
   
   
4. Some other suggested methods to implement for OpenList:

Method	Purpose
public static OpenList list(Object x0)	Returns a list of one element
public static OpenList list(Object x0, Object x1)	Returns a list of two elements
public Object second()	Returns the second element of a list
public Object third()	Returns the third element of a list
public static OpenList assoc(Object x, OpenList L)	Look up x in association list
public static OpenList map(Function1 f, OpenList L)	Map f over a list
public Object reduce(Function2 b, Object u)	Reduce this list using b and unit u.
public static OpenList merge(OpenList L, OpenList M)	Merge sorted lists.

5. In merge, use A.compareTo(B) to compare two Strings for <. If the result is < 0 then A is earlier than B.

Reference Information: These are already implemented for you.

Relevant methods of UnicalcParser:

Method	Purpose
UnicalcParser(String input)	Constructor
Object parse()	Returns syntax tree, using OpenList for non-leavees. Leaves are either String, Floating, or Integer.

Relevant methods of LineBufferInputStream:

Method	Purpose
LineBufferInputStream(InputStream in)	Constructor
String getString()	Gets next String in input.
String getNonBlankLine()	Gets next non-blank line of input.

Relevant methods of Unicalc:

Method	Purpose
void readDB(String DBfilename)	Read database into association list from file.
static Quantity getQuantity(LineBufferInputStream in, PrintStream out)	Get Quantity from input stream. This uses your makeQuantity method.
void loop(InputStream inStream, PrintStream out)	Implement interactive shell loop.
static public void main(String arg[])	Implement Unicalc application.

How to do map and reduce:

Except for OpenList.java and Quantity.java, these are given to you in files. They are also shown given in file /cs/cs60/a/04/higherOrder.

In Function1.java: interface Function1 { Object apply(Object x); }

In Function2.java: interface Function2 { Object apply(Object x, Object y); }

In OpenList.java (among other stuff that you write):
 
 /**
 * Map a Function1 over an OpenList.
 */
 
 public static OpenList map(Function1 f, OpenList L)
 {
 if( L.isEmpty() )
 return nil;
 else
 return cons(f.apply(L.first()), map(f, L.rest()));
 }
 
 /**
 * Map a Function1 over this OpenList.
 */
 
 public OpenList map(Function1 f)
 {
 return map(f, this);
 }
 
 
 /**

 * reduce this OpenList using Function2 with unit u

 */
 
 public Object reduce(Function2 b, Object u)
 {
 OpenList L = this;
 Object result = u;
 while( L.nonEmpty() )
 {
 result = b.apply(result, L.first());
 L = L.rest();
 }
 return result;
 }

In Quantity.java (among other stuff that you write):
 
 /**
 * Multiply Quantities in an OpenList to get a Quantity.
 */
 
 static Quantity multiplyAll(OpenList L)
 {
 return (Quantity)L.reduce(new Multiply(), one);
 }
 
 
 /**
 * Create a normalized Quantity from an OpenList of units.
 */
 
 static Quantity normalizeAll(OpenList L, OpenList DB)
 {
 return multiplyAll(L.map(new NormalizeUnit(DB)));
 }

In Multiply.java:
 
 /**
 * Multiply is a Function2 object, for use with reduce, for example
 * Its apply multiplies two Quantities, returning a Quantity.
 */
 
 public class Multiply implements Function2
 {
 
 /**
 * constructor
 */
 
 Multiply()
 {
 }
 
 public Object apply(Object A1, Object A2)
 {
 return Quantity.multiply((Quantity)A1, (Quantity)A2);
 }
 }

In NormalizeUnit.java
 
 /**
 * NormalizeUnit is a Function1 object, for use with map.
 * It normalizes a Unit with respect to a database given 

 * in the constructor.
 */
 
 public class NormalizeUnit implements Function1
 {
 private OpenList DB;
 
 /**
 * constructor
 */
 
 NormalizeUnit(OpenList DB)
 {
 this.DB = DB;
 }
 
 public Object apply(Object Unit)
 {
 return Quantity.normalizeUnit((String)Unit, DB);
 }
 }

The File Unicalc.java

// file: Unicalc.java
// author: Robert Keller
// purpose: Shell for Unicalc application
 
import java.io.*;
import OpenList;
import Quantity;
import UnicalcParser;
import LineBufferInputStream;
 
/**
 * Unicalc defines one Unicalc application, with database readable from
 * a file. Unicalc derives the conversion factor for converting one
 * kind of Quantity to another. Quantities are multiplicative and
 * conversions are defined by a database of equations.
 *
 * Class Quantity does most of the work. Class Unicalc is primarily a
 * shell for using Quantities.
 */
 
class Unicalc
{
/** the default name of the database file */
 
static String defaultDBfilename = "/cs/cs60/bin/unicalc.db";
 
 
/** the first prompt string */
 
static String promptString1 = "convert from: ";
 
 
/** the second prompt string */
 
static String promptString2 = "convert to: ";
 
 
/**
 * the Unicalc database in association list form
 *
 * Each element of the list is a list of two objects: a String and
 * a Quantity, denoting the left- and right-hand sides of a conversion
 * equation.
 */
 
OpenList DB;
 
/**
 * Read a database from the named file. Each line of the file is a
 * string defining the left-hand unit and a corresponding expression
 * to which the unit is converted.
 */
 
void readDB(String DBfilename)
 {
 DB = OpenList.nil; // Initialize database.
 
 FileInputStream filein = null;  // to keep compiler happy
 
 try
 {
 filein = new FileInputStream(DBfilename); // Open databasefile.
 }
 catch( FileNotFoundException e )
 {
 System.out.println("*** Database file " + DBfilename + " not found.");
 System.exit(1); // Exit if no DB.
 }
 
 LineBufferInputStream in = new LineBufferInputStream(filein);
 
 while( !in.eof() )
 {
 String LHS = in.getString(); // Read LHS of equation.
 
 String line = in.getNonBlankLine(); // Read RHS of equation.
 
 Object input = new UnicalcParser(line).parse(); // Parse the RHS
 
 Quantity RHS = Quantity.makeQuantity(input); // Make Quantity from RHS.
 
 DB = OpenList.cons(OpenList.list(LHS, RHS), DB); // cons eqn to A-list.
 }
 }
 
/**
 * Parse a Quantity from the input/
 */
 
static Quantity getQuantity(LineBufferInputStream in, PrintStream out)
 {
 // Parse input to a tree, constructed using OpenList
 
 Object input;
 
 do
 {
 String line = in.getNonBlankLine(); // Get something to parse.
 input = new UnicalcParser(line).parse(); // Parse it to a tree.
 if( input == null )
 {
 out.println("Invalid input, please try again");
 }
 }
 while( input == null ); // Make sure it is sensible.
 
 return Quantity.makeQuantity(input); // Make Quantity from tree.
 }
 
 
/**
 * Provide shell loop, reading from inStream and printing to out.
 * On each iteration, the user is prompted for "to" and "from"
 * Quantity expressions, which are parsed to create trees, and then
 * Quantities. One Quantity is converted to the other and the result
 * printed.
 */
 
void loop(InputStream inStream, PrintStream out)
 {
 LineBufferInputStream in = new LineBufferInputStream(inStream);
 
 while( true )
 {
 prompt(promptString1, out); // First prompt.
 if( in.eof() ) break; // Make sure we have input.
 
 Quantity fromQuantity = getQuantity(in, out); // Get "from" Quantity.
 
 prompt(promptString2, out); // Second prompt.
 if( in.eof() ) break; // Make sure we have input.
 
 Quantity toQuantity = getQuantity(in, out); // Get "to" Quantity.
 
 Quantity conversion = // Convert "from" to "to"
 Quantity.convert(fromQuantity, toQuantity, DB);
 
 out.println("multiply by: " + conversion); // Display results
 out.println("or divide by: " + Quantity.invert(conversion));
 out.println();
 }
 out.println();
 }




 
/**
 * Prompt with a string on the output stream.
 */
 
static void prompt(String promptString, PrintStream out)
 {
 out.print(promptString);
 out.flush();
 }
 
 
/**
 * the Unicalc application program
 */
 
static public void main(String arg[])
 {
 String DBfilename = defaultDBfilename; // Use default database.
 
 Unicalc unicalc = new Unicalc(); // Create Unicalc instance.
 
 unicalc.readDB(DBfilename); // Populate database.
 
 unicalc.loop(System.in, System.out); // Run shell.
 }
 
}
 
 

P.S. Even though I am giving you a fair amount of code, you should still understand what everything does.

Resist the urge to do your own re-design until you have everything working using the suggested model.