You already have background in several programming languages, e.g., Racket, Python, and Picobot! This week you will add Prolog to that list... .
Part 1 this week should be done on your own; parts 2 and 3, you're invited to work on with a partner -- or individually, if you prefer. Overall, you will submit 2 files and one sentence for this week's problems:
First, you will want to be sure you can run prolog -- either from
your computer or on the CS lab machines. Here
is a note on using prolog on the CS lab Macs.
Instructions from your own machine:
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 - we can't add rules here...
This is attempting to define a new fact inside Prolog's query environment
and prolog will, to use a technical term, "barf."
Formatting and commenting...
Please use the standard commenting
convention of your submission site id/login, 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
largely 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 will need to change its name to hw3pr1.pl from hw3pr1.txt. We provide it as text to keep some browsers happy - they interpret files ending in .pl as 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 code after :- with rules that define each of the predicates described in detail below. The predicates to write are
Tests and testing...
For each predicate you write and the three provided functions, be sure to add at least
one additional test case. These test cases should be clearly labeled, for example by including
them
in the blank provided.
To run all of the tests for a particular predicate, e.g., child (provided), you
can use the command
run_tests(child).
run_tests.
:- begin_tests(child).
test(childT1) :- child(bart, marge), !.
test(childT2) :- child(lisa, marge), !.
test(childT3) :- child(bart, homer), !.
test(childT4) :-
setof(OneKid, child(OneKid, marge), AllKids),
AllKids == [bart, lisa, maggie].
test(childT5) :-
setof(OnePar, child(marge, OnePar), AllParents),
AllParents == [jackie, john].
test(childT6) :- \+child(marge, homer).
test(childT7) :- \+child(jackie, _).
% add additional tests below:
%% here's where you'd add another test (or more...)
:- end_tests(child).
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 or false
cousins( bart, terpsichore ). % yes or true
setof( C, cousins(C,lisa), Answer ). % lisa has 2 cousins here
Answer = [millhouse, terpsichore]
hasDaughterAndSon( homer ). % yes or true
hasDaughterAndSon( esmerelda ). # no or 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 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)]).
Pair or individual problem You may work on the Racket code this week either individually or in a pair. If you work in a pair, be sure to follow the CS 60 pair-programming guidelines.
(1) Racket warm-up (and helper) function
Write the greatest-common-divisor
function:
(gcd a b)
You're welcome to write this however you want; in particular, feel free to use the psuedocode (there's even a functional version -- it's the third one) in The Euclidean Algorithm Wikipedia page - it's remarkably concise!
Here are several check-expect tests for you to try -- be sure to include at least one
of your own tests (as always) -- and comment it as such:
(check-expect (gcd 18 20) 2)
(check-expect (gcd 18 7) 1)
(check-expect (gcd 18 60) 6)
(check-expect (gcd 18 33) 3)
(check-expect (gcd 99 33) 33)
(check-expect (gcd 99 117) 9)
(check-expect (gcd 117 99) 9)
(check-expect (gcd 51 34) 17)
(check-expect (gcd 51 1023) 3)
(2) Racket UIOLI function
Next, implement a Racket function named
(most-multiples L)
Note - this is a clarification from the earlier problem statement: it's not
true that all pairs of elements have to have a gcd bigger than 1 -- it's only
true that all of the elements of the output list have to have a gcd greater than 1 with respect to the
first element of that output list. (Thanks to Eric and Ellen, who caught this!)
In class on Tuesday, we implemented the most-last-digit function -- use that as an example! It's not identical, but it's in the same spirit as this one.
In particular, you might try a use-it-or-lose it approach. After all, either the first element will be part of the solution -- or it won't be. If it is, i.e., if you're using "it", then you'll need to ensure that it's only used with other elements with which it has a gcd > 1. In particular, filter and gcd will help!
Here are a few tests to try -- and include one of your own, as well:
(check-expect (most-multiples '(10 25 121 42)) '(10 25 42)) ;; all share a gcd>1 wtih 10!
(check-expect (most-multiples '(25 33 18 115 5)) '(25 115 5))
(check-expect (most-multiples '(25 33 18 115 5 6 81 72)) '(33 18 6 81 72))
(check-expect (most-multiples '(25 33 18 115 5 6 81 72 32 256 10)) '(18 6 81 72 32 256 10))
Want more use-it-or-lose-it? This week's three extra-credit problems (5 pts each) are additional opportunities to practice UIOLI... . See the descriptions at the end of this asisgnment of
(3) Unicalc!
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 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.
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 hw3pr2.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 (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 (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 (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)
;; be sure to have a description here...
(define (simplify QL)
(let* ((q (get-quant QL))
(N (get-num QL))
(D (get-den QL))
(u (get-unc QL))
)
(define (multiply QL1 QL2)
q1*q2*( (u1/q1)**2 + (u2/q2)**2 )**0.5
(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)
;; be sure to have a description here...
(define (multiply QL1 QL2)
(let* ((q1 (get-quant QL1)) (q2 (get-quant QL2))
(N1 (get-num QL1)) (N2 (get-num QL2))
(D1 (get-den QL1)) (D2 (get-den QL2))
(u1 (get-unc QL1)) (u2 (get-unc QL2))
)
(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 8000000.0 '(euro euro euro) '() 120000.0)
(power (make-QL 200.0 '(euro) '() 1.0) 3))
#t)
(define (divide QL1 QL2)
(q1/q2)*( (u1/q1)**2 + (u2/q2)**2 )**0.5
(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)
;; norm-unit: normalizes a single unit
;; in: a unit
;; out: a NORMALIZED quantity list equivalent to that unit
;; key: mutual recursion with norm-QL
(define (norm-unit unit)
(if (not (assoc unit UDB))
(make-QL 1.0 (list unit) '() 0.0)
(norm-QL (second (assoc unit UDB)))))
(check-expect (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)
(check-expect (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! Later on, you will extend this prototype implementation into a full-fledged language... in Java. For the moment, however, there's still a bit more Java to get used to!
We have six additional Java problems this week, worth a total of 10 points. This week, look over how Java handles loops and arrays:
With this background, head to the Warmup-2 set of JavaBat problems, and write the solutions to these functions:
I'm loopy for Java!
Be sure to submit everything on the submission site!
For up to +15 points, there are three additional use-it-or-lose-it challenges this week.
Include these functions with your most-multiples function inside your hw3pr2.rkt file (above Unicalc):
(check-expect (closest-change 42 '(2 5 10 25 50)) '(2 5 10 25))
(check-expect (closest-change 38 '(2 5 10 25 50)) '(2 10 25))
(check-expect (closest-change 39 '(2 5 10 25 50)) '(5 10 25))
(check-expect (closest-change -474 '(2 5 10 25 50)) '())
(check-expect (LESSS '(50 200 100 42 3)) '(200 100 42 3))
(check-expect (LESSS '(50 42 200 30 25 100 3)) '(50 42 30 25 3))
(check-expect (LESSS '(50 42 200 30 25 100 3 90 80 70 60 55 42))
'(200 100 90 80 70 60 55 42))
(check-expect (length (most-pairwise-multiples '(10 25 121 42))) 2) ;; different than before!
(check-expect (most-pairwise-multiples '(25 33 18 115 5)) '(25 115 5))
(check-expect (most-pairwise-multiples '(25 33 18 115 5 6 81 72)) '(33 18 6 81 72))
(check-expect (most-pairwise-multiples '(25 33 18 115 5 6 81 72 32 256 10)) '(18 6 72 32 256 10))
;; note that the final example no longer includes the 81...