One decomposition of the Unicalc problem

However, if you do implement these functions, you will have a chance to practice mutual recursion, and we will grade each of the helper functions described below for partial credit, in case the complete unit calculator application does not fully work.

1. simplify
   
   The representation of a quantity is said to be 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. Define a scheme function (simplify QL) of one argument (i.e., one quantity list) that yields a corresponding simplified representation. I would suggest using the merge technique from class in order to take advantage of the fact that the numerator and denominator lists are sorted (and to keep them that way)! Recall that (string-ci<? s1 s2) returns #t if s1 is earlier than s2 in the dictionary (ignoring case). Similarly, (string-ci=? s1 s2) returns #t iff s1 and s2 are the same string (ignoring case).

   Some examples:

   > (simplify  '(3 ("kg" "meter" "second" "second") ("kg" "kg" "second"))) 
     (3 ("meter" "second") ("kg"))
   
   > (simplify  '(3.14 ("meter" "second") ("meter" "second" "second")))
     (3.14 () ("second"))
   



2. mulitply and divide
   
   Construct Scheme functions (multiply QL1 QL2) and (divide QL1 QL2) that multiply and divide two quantity lists and yield a simplified result. Again, you may increase your code's efficiency by using the merge technique to combine two sorted lists into a single sorted list, although any technique is OK. Also, you may assume that the numeric element of a quantity list will never be 0.

   Some example runs include

     
   > (multiply '(2.0 ("kg") ("second")) '(3.0 ("meter") ("second")))
     (6.0 ("kg" "meter") ("second" "second"))
   
   > (divide '(12.5 ("meter") ("second")) '(0.5 ("meter") ()))
     (25.0 () ("second"))
   



3. getting a database...
   
   As mentioned, 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 list 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:

   (define mini-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")))
     ))
   

   This association list, named mini-db, as well as a much larger one, named db, are both available from the top-level assignments page in files named unicalc-db.scm and unicalc-mini-db.scm.
   
   Using assoc    In order to access units in one of these association-list databases, you will want to use the assoc function that is built-in to Scheme. When (assoc element AssociationList) is called, it returns the sublist of AssociationList whose first element is equal? to element. If element is not present as the first element of any sublist, then #f is returned. For example,

   (assoc "foot" mini-db)    ==>   ("foot"  (12.       ("inch")   ()))
   
   (assoc "meter" mini-db)   ==>   #f
   

   This assoc function will do almost all of the work of the next Unicalc piece, conv-unit.



4. conv-unit
   
   

   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. Indeed, these three units are, in fact, basic units in the international system (SI)

   Write a Scheme function (conv-unit unitname DB) that takes a string 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 list, otherwise it returns a standard quantity list representing the unit: (1.0 ("unit") ()). For example, if mini-db is the database consisting of the list of the pairs above, then:

     
   >  (conv-unit "hour" mini-db)
     (60.0 ("minute") () )
   
   >  (conv-unit "meter" mini-db)
     (1.0 ("meter") () )
   

   Thus, conv-unit "recognizes" basic, irreduceable units because they are the ones that can only be defined in terms of themselves, as in the latter "meter" example. Here, you'll want to use assoc to do most of the work.



5. norm-unit
   
   

   When the numerator and denominator lists within a quantity list contain only basic units, we'll say that that quantity list is normalized. Again, basic units are those which do not appear on the left-hand side of any entry in the unit database. That is, they are irreducible.

   In order to convert one unit to another, we must express those units in a common form. This common form will be simplified, normalized quantity lists. To this end, write a function (norm-unit s DB) that returns a normalized quantity list that represents the unit whose name is s. Again, a normalized quantity list is one in which the numerator and denominator lists contain only basic units. Here, s is the string name of a unit and DB is a database of units, as above.

   Here's how norm-unit will work: in the case that s is a basic unit, norm-unit will return the same thing that conv-unit does: (1.0 (s) ()). In the case that s is not a basic unit, you should use conv-unit to "look up" s's definition in the database. Then, you will need to normalize that resulting quantity list -- probably by calling norm, below.

   Here are some example runs of norm-unit. There are two unicalc database files available from the top-level assignment page: one is called unicalc-mini-db.scm (which defines mini-db) and a much larger one is called unicalc-db.scm (which defines db). To use them, download them to the same directory as your homework file, and simply put the following two lines at the top:

   (load "unicalc-db.scm")     ;; defines mini-db
   (load "unicalc-mini-db.scm")   ;; defines db
   

     
     >  (norm-unit "second" mini-db)
     (1.0 ("second") ())
   
     >  (norm-unit "hour" db)
     (3600.0 ("second") ())
   
     >  (norm-unit "ohm" db) 
     (1.0 ("kg" "meter" "meter") ("ampere" "ampere" "second" "second" "second"))    
   

   Hint: read the next part before solving this one!


6. norm
   
   Ths function does almost the same thing as norm-unit. The difference is in the form of the input: the function norm(QL, DB) takes as input any quantity list QL and a unicalc database DB. norm(QL, DB) outputs the normalized equivalent to the quantity list QL with respect to the database DB.

   Hint: notice that norm does the same thing as norm-unit, only with a slightly different first input. Because of this, norm and norm-unit are most concisely written as mutually recursive functions, i.e., each calls the other at one or more points. The key to writing mutually recursive functions is being sure you have a clear sense of what each function does at an abstract level -- that way, you can use either as appropriate.

   How to think about mutual recursion? Well, for norm, you might consider the following three cases:

   • If the input quantity list has a null? numerator and a null? denominator. No problem!
   • If the input quantity list has a null? numerator and a non-null? denominator. The idea here would be to peel off one of the elements in the denominator, call norm-unit on that unit, call norm on the rest of the original input quantity list, and then divide appropriately.
   • Finally, if the input quantity list has a non-null? numerator, you can peel off an element similar to in the previous case, handle it and the rest of the original quantity list apprpriately, and then combine with multiply.
   
   Scheme (as well as Java) can handle mutual recursion, so you may want to take advantage of that. (To write norm and norm-unit without mutual recursion is possible, but more difficult.)

   Some examples of norm in action:

     >  (norm '(20.0 ("hour") ()) db)
     (72000.0 ("second") ())
   
     > (norm '(15.0 ("ohm") ("volt")) db)
     (15.0 () ("ampere"))
   

   
   
   
7. convert
   
   The conversion process from the quantity list QL1 to the quantity list QL2 can now be seen as simply

   (define (convert QL1 QL2 DB)
     (divide (norm QL1 DB) (norm QL2 DB)))
   

   Try it out with the original examples...

   > (convert  '(1 ("mile") ("hour")) '(1 ("meter") ("second")) db)
   (0.447032 () ())  
   

   This result is indicating that 1 mile-per-hour == 0.447032 * 1 meter-per-second

   Precision of your answers...
   
   Do not worry if your answer is slightly off from the above - for example, less than a few hundredths. For example, you might have an output of

   (0.447031923888 () ())
   

   When evaluating your Unicalc, we will not worry about small differences that can arise due to different levels of precision being used (or different orders of the operations being performed).

   Here is an example with some units left over, because it's not possible to convert miles-per-hour to feet:

   > (convert  '(1 ("mile") ("hour")) '(1 ("foot") ()) db)
   (1.466666 () ("second"))
   

   where this time the result is showing that 1 mile-per-hour == 1.46666 feet-per-second. Since there were no time units in the denominator and there should have been, the result shows the basic (irreduceable) time units there. In both of these examples, only the first few significant figures have been shown.

   If you made it to here, congratulations, you have completed Unicalc!