The problems in this assignment exercise high- and low-level functional programming concepts, and functional decomposition of a problem.
This assignment covers much of the material up to Chapter 4 in the text. This assignment is significantly more comprehensive than previous ones, so it is advisable to start as early as possible, giving yourself time to work out problems that inevitably arise.
Place your answers in a file named assign3.rex. To receive credit for your answer, the functions must have exactly the names specified. You may define other functions to be used by your code, if this seems useful. Your file must be loadable into into the rex system without generating any errors, so make sure you have comments around all the non-rex parts of your answers. As before you should run
cs60submit assign3.rex
As always, commenting your functions and your file are important. As you write functions to solve these problems, however, it is a good idea (and very much the spirit of functional programming) to try to devise programs that are as elegant and concise as possible.
Test cases for each part appear in the file
/cs/cs60/assign/3/unicalcTest.rex
To test a particular function that has been written in the file
assign3.rex, the following command will work: % rexassign3.rex </cs/cs60/assign/3/unicalcTest.rex
Caution regarding testing: This application uses floating point number representations. Since rex overloads arithmetic to be either integer or floating point, it is advised to make all input quantities floating point (i.e. include a decimal fraction or exponent). Secondly, equality tests on floating point numbers will generally fail if there is a fraction and the two values compared are not derived in exactly the same way. Also beware of the system not printing all significant digits of a floating point number; two numbers that look the same when printed might not be the same in memory.
The HMC Unicalc application converts quantities expressed in one type of unit to those of another. The name "Unicalc" is also used for other commercial products, ones that you might not encounter, but that are nevertheless out there. Here it means a specific application as described below.
Here's an example of the command-line version of Unicalc, which is accessible on turing. What the user types is shown in bold. The expression ^2 means squared, and in general, ^n means raised to the nth power.
% /cs/cs60/bin/unicalc
To convert from units of: pound/in^2
to units of: kg/meter^2
Multiply by: 703.095
or
Divide by: 0.00142228
To convert from units of: light_year meter
to units of: acre
Multiply by: 2.32458e+12
or
Divide by: 4.30185e-13
The version of Unicalc shown above parses free-form input. Parsing will not be done in the current assignment. Instead, we will use pre-parsed input in the form of rex lists.
Unicalc uses a database of fundamental unit conversions, but not all conversions. Possible conversions not obtained directly from the database must be inferred from it.
Consider this unusual example:
To convert from units of: tadpole/meter^3
to units of: tadpole/liter
Multiply by: 0.001
or
Divide by: 1000
If Unicalc doesn't know anything about a unit, such as
"tadpole", it can still pass the unit on as basic (see later explanation for the meaning of "basic").
Solution Approach
If starting from scratch on a problem such as this, figuring out the data representation would be up to the programmer. However, in this case we are going to specify the representation, for two reasons: to help you get a head start and because our database uses a specific representation. Also, it will help us help you when you have problems if everyone is using the same representation. Similarly, we have phrased and phased the questions so that the functions lead you to a decomposition of the problem, with the solution to the last problem being the nearest to the top.
Data Representation
In general, you will need to be able to represent quantities of the form F * N / D where
Note that quantities are only multiplicative in nature. Unicalc does not try to deal with additive conversions, as would be required in converting Farenheit to Celsisus, for example.
By a "unit list" we mean a sorted list of strings, each of which represents a unit. The interpretation of this list is that it is the product of the units. For example, in representing the quantity
0.001 tadpole/meter^3
F would be 0.001, N would be
["tadpole"], and D would be ["meter", "meter", "meter"]. We list the factors in the latter way, rather than electing a more compact representation, for two reasons: we don't expect that the same factor will be listed very many times in typical cases, and we want to keep the necessary functions as simple as possible. The reason for insisting that each list be sorted is also to simplify functions that will be described.
Represent a Quantity as a list of three elements,
[F, N, D] as described above, for example:[0.001, ["tadpole"],
["meter", "meter", "meter"]]
Problem 1: A Quantity is said to be simplified if there is no unit that appears in both
N and D. So the above Quantity is simplified, but [0.001, ["meter", "newton", "second"],
["meter", "meter", "second"]]
is not. The simplified equivalent can be obtained by cancelling units common to both
N and D to get[0.001, ["newton"], ["meter"]]
Note that a numerator or denominator of
1 would be represented by the empty list [ ] and a dimensionless number 1 would thus be represented by [1., [ ], [ ]].
Construct a function
simplify that will accept a Quantity as its argument and return an equivalent simplified Quantity.
(Hint: Use the assumption that lists are sorted. Create an auxiliary function
cancelFrom such that cancelFrom(L, M) will produce a new list that is like L but with any units also in M removed. More precisely, one copy of a unit in L is removed for each copy in M (so you cannot simply use the built-in function drop to do this). Then use cancelFrom in the definition of simplify.)
Problem 2: Construct a function
multiply that will accept two Quantities and return a simplified Quantity representing the product of the original Quantities. For example:multiply([ 3.0, ["foot"], ["second"]],
[12.0, ["inch"], ["foot"]])
would return
[36.0, ["inch"], ["second"]]
(Hint: Take advantage of the built-in function
merge that merges two lists that are sorted. For example, merge(["a", "d", "f", "i"], ["b", "e", "h"])
yields
["a", "b", "d", "e", "f", "h", "i"]
Problem 3: Construct a function
divide that will accept two Quantities and return a simplified Quantity that represents the first Quantity divided by the second. For example:divide([3.0, ["foot"], ["second"]],
[4.0, ["foot"], ["acre"]])
would return
[0.75, ["acre"], ["second"]]
Problem 4: A Unicalc conversion database is an association list (please review this topic from the notes and text, if necessary). The first of each pair in the database is a single unit. The second of each pair is a Quantity to which the unit converts. A small database might be as follows:
[ ["acre", [43560, ["foot", "foot"], []]], ["centimeter", [0.01, ["meter"], []]], ["coulomb", [1., ["ampere", "second"], []]], ["foot", [12., ["inch"], []]], ["hour", [60., ["minute"], []]], ["inch", [0.0253995, ["meter"], []]], ["joule", [1., ["kg", "meter", "meter"], ["second", "second"]]], ["light_year", [9.40691e+15, ["meter"], []]], ["liter", [1000, ["centimeter", "centimeter", "centimeter"], []]], ["mile", [5280., ["foot"], []]], ["minute", [60., ["second"], []]], ["mph", [1., ["mile"], ["hour"]]], ["ohm", [1., ["volt"], ["ampere"]]], ["pound", [0.453592, ["kg"], []]], ["volt", [1., ["joule"], ["coulomb"]]], ["watt", [1., ["joule"], ["second"]]] ]
This database happens to be bound to the identifer
db in file /cs/cs60/assign/3/unicalc_mini_db.rex
A more extensive database is similarly bound in
/cs/cs60/assign/3/unicalc_db.rex
Not every unit will be the first of some pair in a database. Those that are not are called basic units.
Construct the function
convertUnit that takes two arguments: a single unit argument and a database and which returns a Quantity that is either the second of the pair corresponding to the unit from the association list or, if it is a basic unit, the Quantity representing the unit itself.
For example, assuming tadpole is not in the database, the Quantity
[1, ["tadpole"], []]
will be returned. You may assume that the right-hand-side entries in the database are all well-formed Quantities.
Problem 5: A Quantity is said to be normalized with respect to a database if it is simplified and its numerator and denominator contain only basic units.
Construct a function normalize that will normalize a Quantity with respect to a given database, its second argument. For example, suppose that db stands for the database given above. Then
normalize([1, ["mile"], ["second"]], db)
would return
[1609.31, ["meter"], ["second"]]
Also consider constructing a specialized version,
normalizeUnit, that operates on a single unit along with the database. The purposes of this function is for use within other functions.
Problem 6: Construct the function
convert that takes two arbitrary Quantities and a database and returns an equivalent normalized Quantity representing the conversion factor. That is, if the conversion is possible because the units are of appropriate type, the Quantity returned will have the form:[F, [ ], [ ]]
where
F is the conversion factor. If either the numerator or denominator is not [ ], then this represents a deficit in some type of unit, knowledge of which can be used to adjust the original quantities so that direct conversion is possible.
Explanation of how conversion could work overall:
There are several different ways of composing functions to solve this problem. Normalization could recursively expand units until every unit is basic, then simplify. It could expand the numerator and denominator lists by recursively calling
normalize on each unit, then multiplying the results together, or the multiplication can be done along the way.
Given two quantities, one of which is to be converted to the other, we can normalize both quantities, then assuming that the results have the same numerators and denominators, divide the factor of one by the factor of the other.
With respect to the database given, here is how we might convert
[1, ["foot", "pound", "meter"],
["hour", "hour"]]
to
[1, ["joule"], []]
Normalizing the first Quantity would call for the conversion of
"foot", "pound", "meter", and "hour", of which only "meter" is basic; "foot" converts to [12, ["inch"], []], and "inch" converts to [0.0253995, ["meter"], []], which is normalized; "hour" converts to [60, ["minute"], []], and "minute" to [60, ["second"], []]. So the net normalization of "hour" will be [3600, ["second"], []]. The overall result of normalizing the first Quantity would then be[1.06676e-08 , ["kg", "meter", "meter"],
["second", "second"]]
The overall result of normalizing the second Quantity would be
[1, ["kg", "meter", "meter"],
["second", "second"]]
The Quantities are therefore inter-convertible.
The attached diagram attempts to show the process as a pair of trees, the leaves of which match up.
Extra Credit Problem: Develop one or more user-friendly interface functions for conversion. For example,
convertUnits(A, B, db) might try to convert a single unit A into a single unit B (without requiring the user to type bracketed expressions) and report the result. Include some test cases that demonstrate your interface.