Harvey Mudd College
Computer Science 60
Assignment 02

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

The problems in this assignment exercise low-level functional programming concepts, in conjunction with high-level ones, as well as more on data representation. Recursion, including mutual recursion, will be useful in this assignment.

Reading

This assignment covers material through Chapter 4 in the text.

To be done in lab:

Commenting

Comment your .  Be sure your comments indicate what each function does, including what the inputs and outputs are, and how the function does what it does.

Testing your code

As with assignment 1, there are tests you can run in the /cs/cs60/a/02 directory to try out your functions. They are Test1.in through Test25.in. Each problem tells you which tests you can run to test that problem's code. However, you can also test ALL of the problems in this assignment with 

   rex a02.rex < /cs/cs60/a/02/AllTests.in


Do 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 a single file named a02.rex using 

   cs60submit a02.rex

The Unicalc Application

“Unicalc” is the name we give to a unit-conversion application. The purpose of this application is to convert one type of unit (e.g. a physical unit, such as “miles per hour”) into another (such as “meters per second”). Below is an example of how a version of Unicalc (not exactly the one that you will construct) runs on turing. The boldface parts are what the user types. The rest is done by the program.

turing> unicalc




To convert from units of: miles / hour   
 
to units of: meters / second
 
Multiply by: 0.447032
or 
Divide by: 2.23698

Unicalc is limited in the kinds of expressions it will accept: Conversions and expressions must be “multiplicative” rather than, say, “additive”. Unicalc will thus not convert degrees Farenheit to degrees Celsius, which entails addition. Mulitiplicative includes division and raising to a power. For example:

To convert from units of: pounds / meter^3       
 
to units of: tons / acre foot
 
Multiply by: 0.616707
or 
Divide by: 1.62151
 

Here / indicates division and ^ represents exponentiation, or raising to a power. Juxtaposition (placing strings next to each other) indicates multiplication. Exponentiation binds the most tightly, then multiplication, then division. Only integer powers are allowed, so exponentiation is really just a shorthand for repeated multiplication.

The Unicalc application converts quantities expressed in one type of unit to those of another. The end result will be able to do conversions such as the following:

Unicalc works on multiplicative conversions only, so it does not perform conversions such as Fahrenheit to Celsius.

For illustration, there is also a web version of Unicalc at:

                       http://www.cs.hmc.edu/~keller/unicalc/

(The display may be somewhat broken right now, as Java on browsers keep the way screen widgets.)

Unicalc’s Database

Unicalc conversions are based on a stored database that expresses some units in terms of others. For example, a minute might be expressed as 60 seconds, a mile as 5280 feet, etc.. For each unit, there is at most one conversion. This can be regarded as an equation:

mile = 5280 foot
In general, every conversion gives, for the unit on the left-hand side, a multiplicative expression on the right hand side consisting of a numeric factor, a numerator product, and denominator product. Here are some more equations from a typical database:
coulomb = 1 ampere second

cup     = 0.5 pint
lux     = 1 lumen / meter^2
watt    = 1 joule / second

In Unicalc, the database used for conversions is completely decoupled from the application itself, to permit revision by an administrator without reprogramming. You can view the exact database used by the command-line version of Unicalc on turing in this file:

/cs/cs60/bin/unicalc.db

How do all the conversions get accomplished then? Unicalc chains together single conversions to perform compound conversions. This makes maintenance of the database extremely simple.

What if no conversion is given for a unit? In this case, the unit is considered to be primitive, so no further conversions are considered. The choice of primitive units is up to the database administrator. They are simply left out of the list of the database conversions. So Unicalc can perform conversions on entailing units it has never even seen before (below fish is such a unit):

To convert from units of: fish / acre foot
 
to units of: fish / liter
 
Multiply by: 8.10757e-07
or 
Divide by: 1.23341e+06

What if the units are not inter-convertible? The way Unicalc handles this is to note that all units are inter-convertible. It is just a matter of allowing scale factors other than numbers: 

To convert from units of: watt
 
to units of: joule
 
Multiply by: 1 / second
or 
Divide by: 1 second

The units are above are not inter-convertible in the every day sense, since watt is a unit of power whereas joule is a measure of energy. But power is energy per unit time. Unicalc says if we have N watts, we can convert it to joules by multiplying by 1/second, i.e. N watts = N joules/second. I realize this may seem counter-intuitive at first, but it simplifies the problem of dealing with such units.

Unicalc in rex

The objective of this assignment is to implement a version of Unicalc in rex. This version will not have to provide nice input and output formatting. Rather, we will provide the input in the form of rex lists, and expect that output to be in that form as well. An example, the interpretation of which will be explained presently, is

rex >  convert( [1, ["mile"], ["hour"]], 




                [1, ["meter"], ["second"]], db);  




 [0.447032, [], []]

Here db is a variable bound to the database, which is expressed as an association list

Data Representation

When solving any problem of this sort, one of the key issues to be addressed is how the data are going to be represented in the computer. Normally this would be decision that is totally up to the designer. However, for this assignment we are going to dictate a specific one. This will help everyone maintain sanity as we progress toward a working application. We will justify the decisions that went into this choice of data representation.

The simplest data item in Unicalc will be called a Unit. A Unit is simply a string with no embedded blanks to which we humans assign an interpretation. Examples of units are “meter”, “second”, “foot”, and so on. Units will typically be equated to combinations of other units in the database, unless the unit is basic, in which case no conversion is specified.

The most general data item in Unicalc will be called a Quantity. It consists of three components:

·          A floating-point numeric factor

·          A numerator representing a product of Units.

·          A denominator also representing a product of Units.

In the rex implementation, we will use a list of three items. The numerator and denominator will be a sorted lists of strings. Examples of Quantities in this representation are:

[1., ["meter"], ["second"]]

stands for 1 meter per second. Similarly,

[2.5, ["meter"], ["second", "second"] ]

represents 1 meter per second^2, while

[12., [“inch”], []]

represents 12 inches. (An empty numerator or denominator is equated to 1.)

The reason for keeping the strings will become apparent when we consider algorithms for implementing Unicalc. The sorted assumption is an example of a representation invariant for the data. This means that all Quantities are to be maintained in this form, so simplify the attendant algorithms.

rex Unicalc Database

An association list is an appropriate representation for the database in the rex implementation. Each equation in the database is represented as a pair:

·          Unit

·          Quantity

An example of a small database is:

      [          
 ["foot",    [12.0, ["inch"], []]],

 ["watt",    [1.0,  ["joule"],  [“coulomb”]]],

 ["coulomb", [1.0,  ["ampere", "second"], []]]

]

It would be a good idea to make sure you understand what the purpose of each of the brackets above, because there are three distinct uses: to form the association list, to form the pairs, and to form the numerators and denominators.

Implementing Unicalc

We are going to walk through some functions deemed useful in implementing Unicalc, taking you up to a design that will work for the general conversion problem.

1.          (IN LAB) The representation of a Quantity is called simplified if there is no element common to its numerator and denominator lists. One way to convert a Quantity to an equivalent simplified form is to "cancel" any pairs of elements common to its numerator and denominator. This can be done in two steps: canceling from the numerator and canceling from the denominator. Define a function simplify in rex one argument, a Quantity, that yields an equivalent simplified representation.

It is strongly suggested that you adopt the merge technique for canceling (/cs/cs60/a/02/merge.rex), which exploits the assumption that the numerator and denominator lists are sorted.

Some example of simplify are shown: 

rex >  simplify([3, 
                ["kg", "meter", "second", "second"],

                ["kg", "kg", "second"]]);    




[3, ["meter", "second"], ["kg"]]    
 
rex >  simplify([3.14, 

                ["meter", "second"],  

                ["meter", "second", "second"]]);   
[3.14, [], ["second"]]

2.        (IN LAB) Construct rex functions multiply and divide that respectively multiply and divide two Quantities, yielding a simplified Quantity. Again, you may increase your code's efficiency by using merge (as discussed in class) to to combine two sorted lists into a single sorted list. However, as with simplify, any technique is OK. Also, you may assume that the first element of a quantity list will never be 0.

Some examples are:

rex >  multiply([2.0, ["kg"], ["second"]],

                [3.0, ["meter"], ["second"]]);   




[6.0, ["kg", "meter"], ["second", "second"]]    









rex >  divide([12.5, ["meter"], ["second"]],

              [0.5, ["meter"], []]);   
[25.0, [], ["second"]]

3.         (IN LAB) The Unicalc database is represented as an association list, that is, a list of pairs in which each pair consists of a single unit and an equivalent Quantity for that unit. Essentially, these pairs define equations for various units, and we can refer to the elements of the pairs as the LHS (left-hand side) and RHS (right-hand side) for this reason. For example, a sample database might be defined as: 

db = [["foot",    [12.,       ["inch"],   []]],
      ["mile",    [5280.,     ["foot"],   []]],   
      ["inch",    [0.0253995, ["meter"],  []]],   
      ["hour",    [60.,       ["minute"], []]],
      ["minute",  [60.,       ["second"], []]],   
      ["mph",     [1.,        ["mile"],   ["hour"]]],   
      ["coulomb", [1,         ["ampere", "second"],     []]],
      ["joule",   [1,         ["kg", "meter", "meter"],
                              ["second", "second"]]],   
      ["ohm",     [1,         ["volt"],  ["ampere"]]], 
      ["volt",    [1,         ["joule"], ["coulomb"]]],  
      ["watt",    [1,         ["joule"], ["second"]]] ];

which happens to be the current contents of 

/cs/cs60/a/02/unicalc_mini_db.rex

If this were the entire database under consideration, note that "ampere", "meter", and "second" are all basic quantities, since they are not the LHS of any definition.

You can have this database loaded into your program at execution by including in your a02.rex file:

sys(in,"/cs/cs60/a/02/unicalc_mini_db.rex");

There is a substantial database of elements that you are also welcome to try out in the file

/cs/cs60/a/02/unicalc_db.rex .

Note: You may make the assumption that the database is consistent, in the sense that it does not contain any circular definitions of units.

Construct a rex function conv_unit that takes a string u representing a unit and the database association list as arguments. If the unit is defined in the database, it returns that unit's equivalent Quantity, otherwise it returns a standard Quantity representing the unit: [1.0, [u], []]. For example, if db is the database consisting of the list of the pairs above, then:

   rex >  conv_unit("hour", db);   




          [60, [minute], [] ]    









   rex >  conv_unit("meter", db);   




          [1, [meter], [] ]

Hint: When you use assoc to look up an element that's not in a database, it returns [].

4.        This and the next problem go together, in the sense that the two functions prescribed are to be used in a mutually recursive fashion.

A Quantity is called normalized (with respect to a database) if it is simplified and furthermore the numerator and denominator lists within a quantity list contain only basic units. Again, basic units are those that do not appear on the left-hand side of any entry in the unit database.

In order to convert one unit to another, we can first express those units in a common form. This common form will be normalized Quantities.

For this problem, construct a function norm_unit that returns a normalized Quantity representing its first argument, a unit, with respect to its second argument, a database.  Thus norm_unit has the same type as conv_unit, but does more. It is suggested that you not try use conv_unit in norm_unit, but rather test the result of doing assoc on the database for being [] (not found). Then react accordingly:

·    If [] is returned, synthesize a Quantity as with conv_unit.

·    If a pair is returned, use the second element of the pair, which is a Quantity. Recursively normalize the units in the numerator and denominator, then combine them. You will want to use some auxiliary functions to make this simple and readable.

Here are some example runs of norm_unit, using the database in unicalc_mini_db.rex
 

rex >  sys(in,"/cs/cs60/a/02/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]]    

5.        Construct a function norm that takes as input any Quantity and a database and returns an equivalent normalized quantity.  (The difference between norm and norm_unit is that norm_unit works only on a single unit, whereas norm works on an arbitrary quantity.

Some examples of norm in action: 

rex >  norm([20.0, ["hour"], []], db);   

[72000, ["second"], [] ]    



rex > norm([15.0, ["ohm"], ["volt"]], db);   

[15, [], [ampere]]

6.        Construct the user function convert such that convert(A, B, DB) will return the conversion factor fromQuantity A to Quantity B with respect to the database DB. An example of convert was given in the introduction to this assignment.