CSC 372, Fall 2022 Assignment 6 Due: Friday, October 28, 2022 at 23:59:59

The Usual Stuff

Use SWI Prolog!

We'll be using SWI Prolog for the Prolog assignments. On lectura that's swipl.

About the 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 372f22 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.

Easy Money!

Due to the time frame for this assignment and not wanting to underweight problems on assignment 9, I think you'll find that the time required to do this assignment is a bit low with respect to the points assigned.

Problem 1. (14 points, 1 point each) 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, a6/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 a6/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 a6/things.pl; the rest use the facts in a6/fcl.pl. Begin by copying a6/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.

The :-QUERY. construct

You'll see that a6/queries-starter.pl ends like this: 

:-[a6/fcl].
:-[a6/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 a6/fcl.pl and a6/things.pl to be consulted, providing the facts to be used by this problem's queries.

Grading

When grading I'll use altered versions of a6/things.pl and a6/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 a6/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.

A note about the tester

You'll see that the tester uses a Prolog query with several goals for the rules in 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.

Problem 2. (2 points) sequence.pl

Write a predicate 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:

Problem 3. (7 points) rect.pl

In this problem you are to implement several simple predicates that work with 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:

  1. If R1 is instantiated and R2 is not, rotate instantiates R2 to the rotation of R1.
  2. If R2 is instantiated and R1 is not, rotate instantiates R1 to the rotation of R2.
  3. If both are instantiated, 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.

Problem 4. (6 points) mp.pl

Write a predicate 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".

Problem 5. (3 points) bases.pl

Write a predicate 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.

Problem 6. (16 points) grid.pl

Write a predicate 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.
a6/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.
a6/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 or Python program to turn the text in that file into Prolog facts. (Note to self: A version in Haskell might be a nice little exam problem! Have it be String -> IO () and take a string like "one 1\ntwo 2\nthree 3\n...".)

Problem 7. (18 points) 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 function
If 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 a6/buyfacts.pl. Include the line 

:-[a6/buyfacts].
in your buy.pl to consult the file. For grading I may test with other sets of facts, too.

Problem 8. Extra Credit 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.5
There 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.

Turning in your work

Use a6/turnin to submit your work. You can run a6/turnin as often as you want. We'll grade your final pre-deadline submission.

My solutions

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 a6/plsize
for i in $*
do
    echo $i: $(tr -dc "(," < $i | wc -c)
done
Here's what I see for my solutions at the moment, with comments stripped: 
$ a6/plsize $(grep -v txt a6/delivs)
queries.pl: 129
sequence.pl: 17
rect.pl: 46
mp.pl: 24
bases.pl: 13
grid.pl: 131
buy.pl: 89

Miscellaneous

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 six hours into this assignment and don't seem to be close to completing it, or you're simply worried about your "slope", email us! Give us a chance to speed you up!