a5
symlink that references /cs/www/classes/cs372/spring23/a5
.
a5/tester
(or a5/t
).
swipl
.
if-then-else
structure (->
) and disjunction (;
)
To encourage thinking in Prolog, you are strictly prohibited from using the if-then-else
structure,
which is represented with ->
. (Section 4.7 in Covington talks about it.)
Disjunction, represented with a semicolon (;
), is occasionally very appropriate but it's easy to misuse
and make a mess. Section 1.10 in Covington talks about it. Here's the rule for us: If you think you've found a good
place to use disjunction, write to 372s23
to see what we think about it; but unless I grant you a specific exemption, you are not allowed to use disjunction. My general rule is this: don't use disjunction unless it avoids significant repetition.
queries.pl
For this problem you are to write a number of queries, packaged up as rules. Some are easier than others but all are each worth one point.
Following an opening comment,
a5/queries-starter.pl
looks like this:
% What foods are green? q0(Food) :- thing(Food,green,yes). % What are all the things? q1(Thing) :- true. % What are the colors of non-foods? q2(Color) :- true. ...
q0
above is a completed example.
The comment just prior specifies a question, "What foods are green?"
Following that comment is a query that will answer that question. Let's load up the file and try q0
:
$ swipl a5/queries-starter.pl [...lots of singleton warnings due to the uncompleted queries...] ... ?- q0(F). F = broccoli ; F = lettuce.Your task is to replace the dummy bodies (just
true
) for all the rules.
The first few use the facts in a5/things.pl
; the rest use the facts in a5/fcl.pl
.
Begin by copying a5/queries-starter.pl
to queries.pl
, and then edit queries.pl
.
When your queries.pl
is complete, you should see behavior like this:
$ swipl queries.pl ... ?- q1(T). T = apple ; T = broccoli ; ... T = stopsign ; T = bagel. ?- q2(NF). NF = brown ; NF = green ; NF = blue ; NF = red.Leave the sample rule
q0
in place—the tester uses it.
:-QUERY.
construct
You'll see that a5/queries-starter.pl
ends like this:
:-[a5/fcl]. :-[a5/things].When consulting a file, Prolog assumes that it contains clauses that constitute the knowledge base but sometimes we want to execute queries when consulting a file. The construct
:-QUERY.
indicates
that QUERY
is to be performed.
The two lines above cause a5/fcl.pl
and a5/things.pl
to be consulted, providing the facts to be used by this problem's queries.
When grading I'll use altered versions of a5/things.pl
and a5/fcl.pl
, with facts added, deleted,
and changed. Write queries to be general, rather than "wired" for current data. For example, if something involves the cost of an orange, use a goal like cost(orange, OC)
to get the cost of an orange rather than visually inspecting a5/fcl.pl
, seeing cost(orange,3)
, and using 3
for the cost of an orange.
Important: The usual guarantee of 75% of the points for passing all supplied test cases does not apply for this problem.
queries.pl
:
findall(X,q1(X),L), sort(L,Results), writeln('Results:'), member(X,Results), writeln(X), fail.We'll be learning about
findall
, sort
, and member
soon, but briefly, here is
what's happening: findall
makes a list of all results produced by q1(X)
and then sort sorts them, removing duplicates. The member(X,Results), writeln(X), fail
sequence causes the results
to be written out, one per line.
sequence.pl
sequence/0
that outputs the sequence below.
?- sequence. 10101000 10101001 10101010 10101011 10111000 10111001 10111010 10111011 true.Be sure that
sequence
produces true
when done, as shown above.
Two notes:
writeln(10101000)
, writeln(10101001)
,
...—that'll be a zero!
rect.pl
rect(Width,Height)
structures that represent position-less rectangles having only a width and height.
square(+Rect)
asks whether a rectangle is a square.
?- square(rect(3,4)). false. ?- square(rect(5,5)). true.
landscape(+Rect)
is true iff (if and only if) a rectangle is wider than it is high.
portrait(+Rect)
tests the opposite—whether a rectangle is higher than wide. A square is neither landscape nor portrait.
?- landscape(rect(16,9)). true. ?- landscape(rect(3,4)). false. ?- portrait(rect(3,4)). true. ?- portrait(rect(10,1)). false. ?- landscape(rect(3,3)). false. ?- portrait(rect(3,3)). false.
classify(+Rect,-Which)
instantiates Which
to portrait
, landscape
or square
, depending on the width and height. If Rect
is not a two-term rect
structure,
then Which
is instantiated to wat
.
?- classify(rect(3,4),T). T = portrait. ?- classify(rect(10,1),T). T = landscape. ?- classify(rect(3,3),T). T = square. ?- classify(rect(3),T). T = wat. ?- classify(10,T). T = wat.You may need to use some "cuts" (slide 123+) to prevent
classify
from producing bogus alternatives. Here is an example of BUGGY behavior:
?-
classify(rect(5,7),T).
T = portrait ; % First answer is correct but there should be no alternatives!
T = square ;
T = wat.
Needless to say, use your portrait/1
, landscape/1
, and square/1
predicates to
write classify/2
.
rotate(?R1,?R2)
has three distinct behaviors:
R1
is instantiated and R2
is not, rotate
instantiates R2
to the rotation of R1
.
R2
is instantiated and R1
is not, rotate
instantiates R1
to the rotation of R2
.
rotate
succeeds iff R1
is the rotation of R2
.
Examples:
?- rotate(rect(3,4),R). R = rect(4, 3). ?- rotate(R,rect(3,4)). R = rect(4, 3). ?- rotate(rect(5,7),rect(7,5)). true. ?- rotate(rect(3,3),R). R = rect(3, 3).
rotate
should also handle cases like these:
?- rotate(rect(3,4),rect(W,H)). W = 4, H = 3. ?- rotate(rect(3,X),rect(Y,4)). false.
smaller(+R1,+R2)
succeeds iff both the width and height of R1
are respectively less than the width and height of R2
. Rotations are not considered.
?- smaller(rect(3,5), rect(5,7)). true. ?- smaller(rect(3,5), rect(7,5)). false.
add(+R1, +R2, ?RSum)
imagines the "sum" of two rectangles A
and B
to be a rectangle
whose width is the sum of the widths of A
and B
, and likewise for its height.
?- add(rect(3,4),rect(5,6),R). R = rect(8, 10). ?- add(rect(3,4),rect(5,6),rect(W,H)). W = 8, H = 10. ?- add(rect(3,4),rect(5,6),rect(10,10)). false. ?- X = 10, add(rect(3,4),rect(5,6),rect(X,X)). false.Assume both terms of
rect
structures are non-negative integers.
If you need more than ten mostly short clauses to implement all the above, you're probably not making good use of unification.
mp.pl
mp(?A, ?B, ?C)
that expresses the relationship that the number B
is the
midpoint between numbers A
and C
. mp
requires that at least two of the three terms are
instantiated and assumes that the instantiated terms are numbers or are structures that can be evaluated with is/2
.
?- mp(3, X, 7). X = 5. ?- mp(3, 3.875, X). X = 4.75. ?- mp(X,3,1.5). X = 4.5. ?- mp(-e,X,pi). X = 0.211655412565374. ?- X is 7/2, mp(0,X,X*2). X = 3.5.My solution uses
ground/1
and "cut".
bases.pl
bases/2
such that bases(+Start,+End)
prints the integers from Start
through End
in decimal, hex, and binary. Assume that Start
is non-negative and that
End
is greater than Start
. Examples:
?- bases(0,5). Decimal Hex Binary 0 0 0 1 1 1 2 2 10 3 3 11 4 4 100 5 5 101 true. ?- bases(1022,1027). Decimal Hex Binary 1022 3FE 1111111110 1023 3FF 1111111111 1024 400 10000000000 1025 401 10000000001 1026 402 10000000010 1027 403 10000000011 true.Below is a predicate
fmttest/0
that shows almost exactly the specifications to use with format/2
.
However, you'll need to do help(format/2)
and figure out how to output numbers in hex and binary.
?- listing(fmttest). fmttest :- format('~tDecimal~t~10|~tHex~t~20|~tBinary~t~35|\n'), format('~t~d~6|~t~d~16|~t~d~30|\n', [10, 20, 30]). true. ?- fmttest. Decimal Hex Binary 10 20 30 true.
grid.pl
grid(+Rows,+Cols)
that prints an ASCII representation of a grid based on a
specification of rows and columns in English.
Here's an example of a grid with three rows and four columns:
?- grid(three,four). +--+--+--+--+ | | | | | +--+--+--+--+ | | | | | +--+--+--+--+ | | | | | +--+--+--+--+ true.The grid is built with plus signs, minus signs, vertical-bars ("or" bars), and spaces. Lines have no trailing whitespace.
Here are two more examples:
?- grid(three,twenty-one). +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | | | | | | | | | | | | | | | | | | | | | | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | | | | | | | | | | | | | | | | | | | | | | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | | | | | | | | | | | | | | | | | | | | | | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ true. ?- grid(one,one). +--+ | | +--+ true.Widths and heights, in English, from one through ninety-nine are recognized; numbers are one word or two hyphen-separated words.
If a number is used for either dimension instead of an English specification, the user is reminded to use English:
?- grid(3,four). Use English, please! true.Hint: Use
number/1
to see if a value is a number rather than a structure.
Invalid specifications produce "Huh?
":
?- grid(testing,this).
Huh?
true.
?- grid(one-hundred,twenty-five). (one-hundred is out of range)
Huh?
true.
?- grid(---,+++).
Huh?
true.
Be careful not to accept invalid combinations of words representing numbers, like ten-four
,
twenty-twenty
, and one-fifty
; they, too, should produce the "Huh?
" diagnostic. Example:
?- grid(ten-four,twenty-twenty). Huh? true.a5/grid-hint.html shows a solution for a simplified version of this problem, a predicate
box/2
that prints a rectangle of asterisks. To provide a little extra challenge for those who want it, I'm not showing that code here but please don't hesitate to take a look if you're stumped by grid
.
Note that terms like ninety-nine
, thirty-seven
, fifty-two
are simply two-atom
structures with the functor '-'. Here's a predicate that prints the terms of such a structure:
parts(First-Second) :- format('First word: ~w; second word: ~w\n', [First,Second]).Usage:
?- parts(twenty-one). First word: twenty; second word: one true.a5/numbers.txt might save you a little typing. Maybe take a few minutes and learn how to use a keyboard macro/keystroke recorder in your editor to automate repetitive editing tasks. Here's some how-to for Sublime, Notepad++, and Vim.
And/or maybe write a Haskell, Java, or Python program to turn the text in that file into Prolog facts.
buy.pl
Your task in this problem is to print a bill of sale for a collection of items. Several predicates provide information about the items. The first is item/2
, which associates an item name with a description:
item(toaster, 'Deluxe Toast-a-matic'). item(antfarm, 'Ant Farm'). item(dip, 'French Onion Dip'). item(twinkies, 'Twinkies'). item(lips, 'Chicken Lips'). item(hamster, 'Hamster'). item(rocket, 'Model rocket w/ payload bay'). item(scissors, 'StaySharp Scissors'). item(rshoes, 'Running Shoes'). item(tiger, 'Sumatran tiger'). item(catnip, '50-pound bag of catnip').The second predicate is
price/2
, which associates an item name with a price in dollars:
price(toaster, 14.00). price(antfarm, 7.95). price(dip, 1.29). price(twinkies, 0.75). price(lips, 0.05). price(hamster, 4.00). price(rocket, 12.49). price(scissors, 2.99). price(rshoes, 59.99). price(tiger, 749.95). price(catnip, 19.95).The third is
discount/2
, which associates a discount percentage with some, possibly none, of the items:
discount(antfarm, 20). discount(lips, 40). discount(rshoes, 10).Finally, Arizona state law prohibits same-day purchase of some pairs of items.
dontmix/2
specifies prohibitions. Here are some examples:
dontmix(scissors,rshoes). dontmix(hamster,rocket). dontmix(tiger,catnip).You can only ensure that any prohibited pairings are not included in a single purchase; the well-considered prohibitions can be thwarted by making multiple trips to the store!
For this problem you are to write a predicate buy(+Items)
that prints a bill of sale for the specified items.
If any mutually prohibited items are in the list, that prohibition should be noted instead of printing the bill of sale.
Some examples of using buy
follow.
As you'll see, the cons list structure developed on slide 115+ is used for Items
.
?- buy(hamster:twinkies:hamster:toaster:empty). Hamster.............................4.00 Twinkies............................0.75 Hamster.............................4.00 Deluxe Toast-a-matic...............14.00 ---------------------------------------- Total $22.75 true. ?- buy(lips:lips:lips:dip:empty). Chicken Lips........................0.03 Chicken Lips........................0.03 Chicken Lips........................0.03 French Onion Dip....................1.29 ---------------------------------------- Total $1.38 true. ?- buy(scissors:dip:rshoes:empty). State law prohibits same-day purchase of "Running Shoes" and "StaySharp Scissors". true.You may assume that all items named in a
buy
are valid and that a price exists for every item.
Prohibited items are shown in alphabetical order. We'll soon see sort/2
and you're free to use
it but figuring out how to order the pair of prohibited items
with a simple predicate is good practice. If you want to directly compare atoms,
use @<
rather than <
. Example:
?- down @< up. true. ?- down < up. ERROR: </2: Arithmetic: `down/0' is not a functionIf several mutually prohibited items are named in the same
buy
call only the first conflict is noted
Here's the format/2
specification I use to produce the per-item lines:
'~w~`.t~2f~40|~n'The backquote-period sequence causes the enclosing tab to fill with periods.
My solution uses member_cl/2
, shown on slide 121.
A set of facts for testing is in a5/buyfacts.pl
. Include the line
:-[a5/buyfacts].in your
buy.pl
to consult the file. For grading I may test with other sets of facts, too.
observations.txt
Submit a plain text file named observations.txt
with...
(a) (1 point extra credit) An estimate of how many hours it took you to complete this assignment. Put that estimate on a line by itself, like this:
Hours: 3.5There should be only one
"Hours:"
line in observations.txt
. (It's fine if you care to provide per-problem times, and that data is useful to us, but report it in some form of your own invention that doesn't contain the string "Hours:"
. Thanks!)
Feedback and comments about the assignment are welcome, too. Was it too long, too hard, too detailed? Speak up! I appreciate all feedback, favorable or not.
(b) (1-3 points extra credit) Cite an interesting course-related observation (or observations) that you made while working on the assignment. The observation should have at least a little bit of depth. Think of me thinking "Good!" as one point, "Excellent!" as two points, and "Wow!" as three points. I'm looking for quality, not quantity.
Use a5/turnin
to submit your work. You can run a5/turnin
as often as you want. We'll grade your final pre-deadline submission.
Line counts are often reasonable ballpark measurements of program size for many languages but they can be
particularly misleading with Prolog.
For example, I'll sometimes write a complex Prolog procedure with only one goal per line.
Therefore, instead of using wc
to count lines, "words", and characters, let's use
a different measure: a count of left parentheses and commas. The following Bash
script computes that number by using tr
to delete everything except left parentheses and commas, and
counting the remaining characters.
$ cat a5/plsize for i in $* do echo $i: $(tr -dc "(," < $i | wc -c) doneHere's what I see for my solutions at the moment, with comments stripped:
$ a5/plsize $(grep -v txt a5/delivs) queries.pl: 129 sequence.pl: 17 rect.pl: 46 mp.pl: 24 bases.pl: 13 grid.pl: 131 buy.pl: 89
Aside from ->
and ;
you can use any elements of Prolog that you desire, but the assignment is written with the intention that it can be completed easily using only the material presented on Prolog slides 1-131.
Point values of problems correspond closely to the "assignment points" mentioned in the syllabus. For example, a 10-point problem would correspond to about 1% of your final grade in the course.
Feel free to use comments as you see fit, but no comments are required in your code.
In Prolog, %
is comment to end of line.
Multi-line comments with /* ... */
, just like in Java, are supported, too.
Remember that late assignments are not accepted and that there are no late days; but if circumstances beyond your control interfere with your work on this assignment, there may be grounds for an extension. See the syllabus for details.
My estimate is that it will take a typical CS junior from 6 to 8 hours to complete this assignment.
Our goal is that everybody gets 100% on this assignment AND gets it done in an amount of time that is reasonable for them.
Assignments are not take-home tests! We hope you'll make use of Piazza, email, Discord and office hours if problems arise. If you're getting toward the hours I estimate above and don't seem to be close to completing it, or you're simply worried about your progress, email us! Give us a chance to speed you up!