Assuming you took CS5, at this point in CS60 youve worked with (at least) three programming languages: Python, HMMM, and Racket. This week - and in the coming weeks - we will add Prolog to that list (if it's not already there).
This semester you'll build your own task-specific language that will be able to handle arbitrary multiplication-based conversions from one unit to another -- and account for error propagation, too. To do this, your application will be able to navigate within arbitrarily large graphs of unit-conversion data. We're calling this application a unit-calculator, or unicalc.
You'll prototype your application in Racket this week. When we begin to focus on Java you'll build the fundamental data structure for a Java implementation of unicalc. This data structure will be the OpenList class, in which you'll create Racket-like linked lists that can be naturally handled recursively. Thus, OpenList "shows off" Java's data-structuring capabilities without sacrificing the generality and power of Racket/Scheme.
Parts 1 and 3 this week may be done in pairs -- or individually, if you prefer. Parts 2 should be completed individually and will consist of completing exercises on codingbat.com. Overall, you will submit 2 files for this week's three problems:
First, you will want to be sure you can run prolog -- either from
your computer or on the CS lab machines.
Instructions from the CS lab machines -- or from a Mac once Prolog is installed:
% cd Desktop
% cd hw3
/opt/local/bin/swipl -f hw3pr1.pl
parent(X, bart).
Prolog is in some ways like Racket. However, there are a couple of important differences to keep in mind: Racket allows you to define functions and data in a file and/or at the command line (the interpreter). However, prolog is different: you must define everything in a file. The prolog command line can only be used to make queries based on the facts and rules in the file. Therefore, the following will NOT work:
?- [hw3pr1]. <-- Loads in the file hw3pr1.pl with Simpsons stuff
% simpsons compiled 0.42 sec, 4242 bytes
Yes
?- parent(bart, bartjr). % this will not work!
This is attempting to define a new fact inside the prolog environment
and prolog will "barf."
[40 points (5 points each), pair or individual]
This part asks you to write predicates that define family relationships and answer questions about the Simpsons' family tree -- or, at least, the version of the family tree that appears in hw3pr1.pl.
Formatting and commenting...
Please use the standard commenting
convention of your name, file name, and date at the top of each file.
In addition, be sure to include a comment for each function
that you implement. Examples appear through the hw3pr1.pl starter file.
Finally, please be sure to name your files and functions
as noted by the problems.... The grading procedure for this assignment is
partially automated and files and functions whose spellings differ from
those below will help the graders a lot!
You should download that hw3pr1.txt file -- you may need to change its name to hw3pr1.pl from hw3pr1.txt, depending on how you get the file. If it's already hw3pr1.pl, it's OK. (This is because some browsers believe that files ending in .pl are Perl scripts.)
In that file, there are rules for a (fictional) Simpsons' family tree. These rules define, from scratch, the predicates
Finally, at the very top of the file, there are eight placeholders where you should replace the fail. with rules that define each of the predicates described in detail below. The predicates to write are
The Simpsons' Family-tree predicates to write:
grandparent( john, bart ). % yes!
grandparent( lisa, bart ). % no.
grandparent( X, bart ). % there will be four answers
setof( P, grandparent( P, bart ), Answer ).
Answer = [homericus, jackie, john, matilda]
siblings( bart, lisa ). % yes or true
siblings( bart, terpsichore ). % no or false
setof( S, siblings(S,lisa), Answer ). % lisa has 2 siblings
Answer = [bart,maggie]
cousins( bart, lisa ). % no
cousins( bart, terpsichore ). % yes
setof( C, cousins(C,lisa), Answer ). % lisa has 2 cousins here
Answer = [millhouse, terpsichore]
hasDaughterAndSon( homer ). % yes/true
hasDaughterAndSon( esmerelda ). # no/false
setof( P, hasDaughterAndSon(P), Answer ).
Answer = [cher,glum,homer,jackie,john,marge]
setof( X, hasOlderSibling(X), Answer ).
Answer = [atropos,glum,homer,homericus,lachesis,lisa,maggie,marge]
setof( P, hasYS(P), Answer ). % everyone with a younger sister
Answer = [atropos, bart, klotho, lisa, patty, selma]
setof( [X,GP], hasOlderCousin(X,GP), Answer ).
Answer = [[gomer,helga],[gomer,olf],[homer,helga],[homer,olf],[maggie,jackie],[maggie,john],[millhouse,jackie],[millhouse,john],[terpsichore,jackie],[terpsichore,john]]
Hint: The negation examples we looked at in class won't help outright on this problem, but consider using hasOlderCousin as a helper predicate. Then the negation example we looked at in class will serve as a good template! Remember that the "not" operator in prolog is \+, as in the construction \+predicate(...).
You should check this with some of your own queries;
in addition, you can check for all of the people with first grandchildren via
setof( P, hasFirstGC(P), Answer ).
Answer = [esmerelda, homer, marge, matilda, skug]
Prolog reminders
Recall that "," is the symbol for AND, ";" is the SYMBOL for OR, and
"\+" is the symbol for NOT, while \== is the symbol for "not equal."
Please look at the class notes for other
(admittedly, sometimes crazy) Prolog syntax. Another good resource is Learn Prolog Now!,
a site that explains the language concisely and with a number of examples.
Please submit your solutions in your hw3pr1.pl file under assignment #3.
Note on Prolog's output formatting
There are several settings that control how Prolog
formats its output: the following describes a few of those settings
you may want to change.
You may have noticed that when answer variables get bound to long lists,
swipl shows the list with '...' after about 10 elements,
which can be annoying.
To see the entire list, simply type
w
range(L,H,[]) :- L > H.
range(L,H,[L|R]) :- M is L+1, range(M,H,R).
?- range(1, 50, X).
X = [1, 2, 3, 4, 5, 6, 7, 8, 9|...]
X = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36, 37, 38,
39, 40, 41, 42, 43, 44, 45, 46, 47,
48, 49, 50]
To change the limit on the number of elements once and for all, copy the
following at the top of your source file (we have done this
for the two source files this week).
:- set_prolog_flag(toplevel_print_options, [quoted(true),
portray(true), attributes(portray), max_depth(999), priority(699)]).
Head back to CodingBat to drink up some Java (10 points)
Pair or individual problem You may work on this one either individually or in a pair. If you work in a pair, be sure to follow the CS 60 pair-programming guidelines.
30 Points
This problem asks you to write several Racket functions: together, they will implement a "unit-calculator" or unicalc application. A complete application will be able to convert any unit quantity to any compatible quantity by using an association list as a database of known conversions.
Here is a zip file with both hw3pr3.rkt and
two files with "databases" of units as association lists:
unicalc_symbols_include.zip
The first you will modify to implement unicalc; the second holds the unicalc
unit-conversion database.
Quantity Lists The fundamental structure used in unicalc is called a Quantity List. As a data structure, a Quantity List is a 4-element Racket list in which
'(9.8 (meter) (second second) 0.01)
Generally speaking, a data structure is rather low-level: it specifies the particular way that language-specific and/or machine-specific constructs are used to organize data, as the above example indicates. An information structure, on the other hand, provides problem-specific capabilities that are independent of a particular application. To reinforce this distinction, we provide a make-QL function in Racket that creates a Quantity List. In addition, we provide the accessor functions get-quant, get-num, get-den, and get-unc, which return the individual pieces of a Quantity List. In order to compare and sort lists of symbols, we provide functions sym<? and sortsym.
In Racket, the difference between data structure and information structure is almost entirely one's point of view. After all, the different ways of organizing data are relatively limited!
The unit database
In the file unicalc-db.rkt is a
unit-conversion database in the form of an association list - here
are a few of its conversions:
(define unicalc-db
(list
(list 'A (make-QL 1.0 '(ampere) '() 0.0))
(list 'faraday (make-QL 96490.0 '(coulomb) '() 0.0))
(list 'farad (make-QL 1.0 '(coulomb) '(volt) 0.0))
(list 'fathom (make-QL 6.0 '(foot) '() 0.0))
(list 'hour (make-QL 60.0 '(minute) '() 0.0))
(list 'inch (make-QL 0.02539954113 '(meter) '() 0.0))
... ))
When a quantity is normalized, it is converted entirely into basic units. Also, the database does not contain conversions from everything to everything: that would make it very large and difficult to maintain! Instead, the database can be used multiple times, e.g., to convert furlongs to miles to feet to inches to meters.
A note on uncertainty-propagation: there are many online references that indicate how to propagate uncertainty through various functions. We used this reference from Harvard and this error-propagation calculator as a check for our results. Our uncertainties represent the size of one-standard-deviation within a Gaussian distribution around the quantity in our quantity list - note that we're not tracking relative uncertainties here, though the formulas below do compute them, as needed.
(define (merge L1 L2)
(check-expect (merge '(m m s) '(kg m s s)) '(kg m m m s s s))
(define (n-merge L n)
(check-expect (n-merge '(kg m s) 0) '())
(check-expect (n-merge '(kg m s) 1) '(kg m s))
(check-expect (n-merge '(kg m s) 2) '(kg kg m m s s))
(define (cancel L1 L2)
(check-expect (cancel '(m m s) '(kg m s s)) '(m))
(check-expect (cancel '(m s) '(kg m s s)) '())
(check-expect (cancel '(m s s s) '(kg m s s)) '(s))
(check-expect (cancel '(kg m s s) '(m m s)) '(kg s))
(define (simplify QL)
(check-expect (equal-QLs? (make-QL 1.0 '(m) '(s) 0.0)
(simplify '(1.0 (m m s) (m s s) 0.0)))
#t)
(check-expect (equal-QLs? (make-QL 1.0 '(m) '(kg) 0.0)
(simplify '(1.0 (kg m m s) (kg kg m s) 0.0)))
#t)
(define (multiply QL1 QL2)
(check-expect (equal-QLs? (make-QL 1764.0 '(m) '(s) 59.39696962)
(multiply (make-QL 42.0 '(kg m m) '(s s) 1.0)
(make-QL 42.0 '(s) '(kg m) 1.0)))
#t)
(check-expect (equal-QLs? (make-QL 1.0 '(kg meter x) '(amp s w) 0.02061553)
(multiply (make-QL 2.0 '(meter) '(amp w) 0.01)
(make-QL 0.5 '(kg x) '(s) 0.01)))
#t)
(define (power QL p)
(check-expect (equal-QLs? (make-QL 1.0 '() '() 0.0)
(power (make-QL 200.0 '(euro) '() 1.0) 0))
#t)
(check-expect (equal-QLs? (make-QL 0.005 '() '(euro) 2.5e-005)
(power (make-QL 200.0 '(euro) '() 1.0) -1))
#t)
(check-expect (equal-QLs? (make-QL 8000000.0 '(euro euro euro) '() 120000.0)
(power (make-QL 200.0 '(euro) '() 1.0) 3))
#t)
(define (divide QL1 QL2)
(check-expect (equal-QLs? (make-QL 1.0 '(m) '(s) 0.03367175)
(divide (make-QL 42.0 '(kg m m) '(s s) 1.0)
(make-QL 42.0 '(kg m) '(s) 1.0)))
#t)
(check-expect (equal-QLs? (make-QL 4.0 '(meter s) '(amp kg w x) 0.08246211)
(divide (make-QL 2.0 '(meter) '(amp w) 0.01)
(make-QL 0.5 '(kg x) '(s) 0.01)))
#t)
(define (norm-unit unit)
;; The reason there is an "or" here is because the (old)
;; databases had two different definitions for weber
;; this will allow either one to work for these tests...
;; physically, 1 weber = 1 volt * second
(check-expect (or (equal-QLs? (make-QL 1.0 '(kg meter meter)
'(ampere second second) 0.0)
(norm-unit 'weber))
(equal-QLs? (make-QL 1.0 '(kg meter meter)
'(ampere second second second second) 0.0)
(norm-unit 'weber)))
#t)
(check-expect (equal-QLs? (make-QL 1.0 '(ampere) '() 0.0)
(norm-unit 'ampere))
#t)
(define (norm-QL QL)
;; see note for weber in norm-unit
(check-expect (or (equal-QLs? (make-QL 42.0 '(second) '(ampere) 1.0)
(norm-QL (make-QL 42.0 '(weber) '(ampere volt) 1.0)))
(equal-QLs? (make-QL 42.0 '() '(ampere second) 1.0)
(norm-QL (make-QL 42.0 '(weber) '(ampere volt) 1.0))))
#t)
(check-expect (equal-QLs? (make-QL 4.3890407 '(meter) '() 0.09143834)
(norm-QL (make-QL 14.4 '(foot) '() 0.3)))
#t)
(check-expect (equal-QLs? (make-QL 0.010159816 '(meter) '(second) 0.0005079908)
(norm-QL (make-QL 2.0 '(foot) '(minute) 0.1)))
#t)
(define (add QL1 QL2)
(list 'error 'add QL1 QL2)
(check-expect (equal-QLs? (make-QL 2.13356145 '(meter) '() 0.03592037)
(add (make-QL 42.0 '(inch) '() 1.0)
(make-QL 42.0 '(inch) '() 1.0)))
#t)
(check-expect (equal? (add (make-QL 42.0 '(inch) '() 1.0)
(make-QL 42.0 '(s) '() 1.0))
(list 'error 'add
(make-QL 42.0 '(inch) '() 1.0)
(make-QL 42.0 '(s) '() 1.0)))
#t)
(define (subtract QL1 QL2)
(list 'error 'subtract QL1 QL2)
(check-expect (equal-QLs? (make-QL 0.0 '(meter) '() 0.03592037)
(subtract (make-QL 42.0 '(inch) '() 1.0)
(make-QL 42.0 '(inch) '() 1.0)))
#t)
(check-expect (equal? (subtract (make-QL 42.0 '(inch) '() 1.0)
(make-QL 42.0 '(s) '() 1.0))
(list 'error 'subtract
(make-QL 42.0 '(inch) '() 1.0)
(make-QL 42.0 '(s) '() 1.0)))
#t)
Where's convert?
With this toolkit of functions in place,
unit-conversion turns out to be an application of division:
(define (convert from to)
(norm-QL (divide from to)))
More tests... Here are
a few more tests you might try. These combine your unit-calculation
functions into composite operations:
(check-expect (equal-QLs? (make-QL 0.38735983 '(second) '() 0.030581039)
(divide (norm-QL (make-QL 3.8 '(m) '(s) 0.3))
(norm-QL (make-QL 9.81 '(m) '(s s) 0.0))))
#t)
(check-expect (equal-QLs? (norm-QL (make-QL 0.48 '(cm) '() 0.6327716))
(let* ((w (make-QL 4.52 '(cm) '() 0.02))
(x (make-QL 2.0 '(cm) '() 0.2))
(y (make-QL 3.0 '(cm) '() 0.6)))
(subtract (add (norm-QL x) (norm-QL y)) (norm-QL w))))
#t)
(check-expect (equal-QLs? (norm-QL (make-QL 18.04 '(cm cm) '() 3.7119827))
(let* ((w (make-QL 4.52 '(cm) '() 0.02))
(x (make-QL 2.0 '(cm) '() 0.2))
(y (make-QL 3.0 '(cm) '() 0.6)))
(norm-QL (add (multiply w x) (power y 2)))))
#t)
(check-expect (equal-QLs? (make-QL 5.1 '(meter) '() 0.360555127)
(subtract (norm-QL (make-QL 14.4 '(meter) '() 0.3))
(norm-QL (make-QL 9.3 '(meter) '() 0.2))))
#t)
(check-expect (equal-QLs? (make-QL 23.7 '(meter) '() 0.360555127)
(add (norm-QL (make-QL 14.4 '(meter) '() 0.3))
(norm-QL (make-QL 9.3 '(meter) '() 0.2))))
#t)
Congratulations! on creating an error-propagating unit calculator! You will extend this prototype implementation into a full-fledged language in a later assignment... (in Java!)
Submitting Be sure to submit unicalc.rkt to the submission site; you do not need to submit your database file.