Prolog Projects

Individual Work

Aside from 1.1, all these exercises are individual. That is: no joint efforts, no code-sharing.

Turn in (to Blackboard) your code, README, and PDF (not .doc or anything else) writeup. Don't use rar, either, please.

As usual the writeup should have plenty of annotated output to convince us your code runs and to demonstrate its power, range, limitations, cutenesses, etc. Also your writeup as always should explain exactly what problem you're solving, what goes beyond the assignment, what experiences you had that you think we should know about, etc.

Week 1. Code+Readme: 80%, Writeup 20%

Copy some of the early examples from tutorials into Prolog, use trace to follow what happens on execution. Definitely explore some of the list-handling 2-liners like append and member. Your goal is to grok the backtracking control structure and generally the syntax and semantics of Prolog. Look through the list of built-in functions. Read example code (like Chapter 7 of Clocksin and Mellish 5th Ed. on reserve).

Do other examples and exercises that appeal to you (or you may want to jump ahead and start work on later exercises in this set). Anyway stay busy, create and answer your own questions, work in groups to understand general issues. Your classmates, the Prolog mailing list, Google, the TA, or whoever you can find who knows this stuff are legal resources for general questions.

Personal styles vary. Use yours and learn Prolog.

Exercises Follow -- use the guidelines for submission and guidance below.

Reminder: Do NOT submit materials that need proprietary products. In other words, nothing from Microsoft. No .doc, NO .docx, no .rar, etc. (zip and tar work fine.) Make sure your code works under linux, make sure your prose submissions are in PDF (.pdf). If you have trouble finding the necessary utilities, consult Google(TM), a classmate, or a TA.

1.2. Given two lists, interleave them from the front as much as possible to get a third list that is their ``shuffle''. So ([a,b,c,d],[1,2]) goes to [a,1,b,2,c,d]. Just code is fine, no commentary needed,

1.3. Using an accumulator (see Clocksin and Mellish 3.7). Let's look at the reverse/2 predicate, which is true if its 2nd list argument is the reversal of the first list argument. It's a system function but you can't use that one for scientific technical purposes made clear below. Instead, first write (or copy from a book) the two-line definition of the predicate append, only call it paste. We don't want it getting mixed up with the system's append. (Note: Prolog's append is usually the first example you see in any Prolog tutorial when you get to lists, and has some really cute behaviour (nondeterministic programming) it's important to understand.) Now use your own paste function to write backwards, a 2-argument predicate that is true when the second list argument is the reverse of the first list argument.

Now consider this:

backwards2(L1, L) :- revpaste(L1, [], L).
revpaste( [H|T], L, M) :- revpaste(T, [H | L], M).
revpaste( [], L, L).

Verify that backwards and backwards2 do the same thing. Convince yourself experimentally if you like, but convince me by explaining what each one does in prose. (Hint: revpaste uses an accumulator, the middle argument, to keep the results so far.) The second clause is the base case that copies the accumulator (arg2) to the answer (arg3) so in turn in backwards2's definition, revpaste can pass arg3 (the answser) over to backwards2 (which doesn't want to know about the accumulator).). So for this you'll probably want to copy these, run, see that they work, trace, whatever, but all we want is the English description of how they compute the same thing.

Now suppose you have a file that defines these four functions paste, revpaste, backwards, backwards2. Let's do some timing analysis. First we need some data. Write a goal r1 that's satisfied if backwards is used to reverse some list you make up, which for definiteness let's say contains 25 atomic elements, like the integers 0-24, the atoms a - y, etc.... just some 25-long list whose reverse is easy to recognize. Now write a goal r1_10 that's satisfied if r1 is satisfied 10 times. You can either brute-force the reversal operations into a single statement with a long boring right-hand side, or (much better) you can do something clever with recursion and is to repeat the reversal operation 10 times (or any number you say).

Then do a similar thing for backwards2 and to create r2 and r2_10. Then ask Prolog ?- time(r1_10). and ?- time(r2_10). You'll see the number of inferences and CPU time: now you have a source of data to work with...MWAH HAH HAhaha!. Avoiding the system implementation of append just removes an unknown factor from the situation. (But a good scientist might want to check to see what difference append makes over paste in the experiments!). Make a graph of inferences versus problem size for enough cases to demonstrate what's going on. (I'd probably create r1_20 and r2_20, r1_40 and r2_40,..., until I got bored or something broke. You should be able to get prolog to do these cases for you rather than you doing a lot of typing).

Another experiment would be to compare times on longer lists, not on more iterations. Could be more fun. Do either, but tell us what you did and...

Present and explain your results. Use what you've learned in data structures and analysis of algorithms. Hint: convince yourself that backwards applied to an n-long list does about 1 + 2 + 3 +...+ n+2 logical inferences. This sum = (1/2)(n^2+3n+2). Can you write a formula for how many inferences it takes for an n-long list using backwards2?

Here we'd like to see your programs, an explanation, and your data and its explanation. We need that experimental data and your analysis.

Thanks to Peter Stoeckl for wording suggestions (2012).

Week 2: A Choice!

Cryptarithmetic. Code+Readme 80%, Writeup 20%

2A.1. Check whether a word is a palindrome, and write a program to ask you for words and tell you if your input is palindromic. For this you'll want your predicate backwards or backwards2, which reverses a list. (Yes, reverse/2 is a system predicate and No, you can't use it this time either). You'll also want the pre-defined predicate name/2, which decomposes a name into a list of ASCII codes, and read/1, which reads a term and decomposes it into a list. Unification makes comparing two lists easy, and so once the list-reverser is written, this code can literally be a one-liner. CB's version is 36 characters long (my reverser is named rev,) and returns the palindromic list or false.

So what does the head of the Palindrome Society drive? ?- p(Car). |: infiniti. false. ?- p(Car). |: jeep. false. ?- p(Car). |: atoyota. Car = [97, 116, 111, 121, 111, 116, 97].

2A.2 Optional Warmup:
Write a rule that succeeds if its second argument is equal to the sum of the first two elements of a list. In crass imperative terms, it assigns a name to both the first and second elements of an input list of integers (hint: this happens through 'structure matching' and unification when the rule is first matched), and returns (in its second argument) their sum. OR you can have it suceed if the first element is greater than the second. OR if their sum is 10. The idea is the naming of the list elements (useful below).

2A.3: A Cryptarithmetic Problem: Scott Kim proposed this rather elegant (in some ways) Cryptarithmetic problem: ABC + DEF = GHIJ. It's elegant for no repeated letters, but it's not perfect since (I claim) there's more than one solution. Use prolog's built-in backtracking to find all the solutions. A couple of hints: First, G = 1 since it's less than 2 and we choose not to start numbers with a leading zero. Second, one good way to generate all permutations of a list is
perm([],[]).
perm(L,[H|T]) :-
append(V, [H|U],L),
append(V,U,W),
perm(W,T).

In your writeup, explain why perm/2 works.

Further hints: my top-level code is a 5-liner that creates a list with a permutation of 9 integers, tests it for being a correct solution, and if so writing out the summands and sum. If the test fails, its rule fails and prolog goes back for another permutation using its built-in backtracking. My test is another 5-liner: a rule that deconstructs the input list and gives each element a name (i.e. assigns a variable). (Hint: just like in the warm-up). It then assembles the cryptarithmic summands and checks to make sure that they add up to what they should.

If one solution is found, typing ; at top level finds another. Or you can put a fail. at the end and generate all the solutions. There are lots. So finally, how many are there? Problem: can't do I++ in Prolog!! Not easy to "update a variable" the way we need to. I was stumped so went to SWIPL forum, a very helpful place: Here's what I got back (in part): :- dynamic num_solutions/1. count_solutions(Goal,NumSolutions) :- retractall(num_solutions(_)), assert(num_solutions(0)), find_all_solutions(Goal), retract(num_solutions(NumSolutions)). find_all_solutions(Goal) :- call(Goal), retract(num_solutions(NumSolutions0)), NumSolutions is NumSolutions0 + 1, assert(num_solutions(NumSolutions)), fail. find_all_solutions. -- Killian

Plus:
If you prefer to stick to the basic solution already suggested by Killian, consider using nb_setval,nb_getval, instead of assert/retract, for (a small) efficiency gain. -- Carlo

I also got a good reminder that the number of proofs may not be equal to the number of desired solutions. For instance, here the solution ABC + DEF = GHIJ may not be considred different from DEF + ABC = GHIJ. So mention your assumptions and then see if you can count the 'different' solutions.

Week 2: Family Matters. Code+Readme 80%, Writeup 20%

Please do this section or the last one for your week 2 assignment.

2B. Kinship Relations. We all know Queue Luu Breeze (for example Charge it to the Game), the Canadian rapper whose stark and gritty lyrics capture the vitriolic rage and anarchic violence of forty-something Episcopalians in exclusive Torontonian gated communities. You recall his biggest hit, I'm My Own Grandpa: (we all downloaded the ringtone.) In case you missed some of the trenchant lyrics due to Queue Luu's strong Canadian accent, here they are, eh?.

As you see the song tells a story that amounts to a set of kinship facts: (e.g. I'm married to a woman. The woman has a child, etc.). Most of these facts are in the first stanza, and my version of them is given just below. The song also makes some claims (e.g. that my father is my son-in-law) that presumably follow from the facts. They follow from the facts because of the rules defining family relationships here in North America. There are also irrelevant facts in the song, like hair color, child behaviour, etc.

Write Prolog to verify the claims in the song (one version given below) by proving them from the facts in the song (one version given below) and the relevant kinship definition rules (you must write these) Minimize the number of facts and maximize the number of rules. I didn't use the cut (!). I used 17 kinship rules (no idea what's optimal) and the following facts (again, probably not a necessary and sufficient set).

The predicates are simply the standard US kinship relations: father(james, chris) would say james is chris's father, for instance. The domain is people, and all the individuals (arguments to the predicates) have made-up names based on the song: so i is "I, the singer", widow is the pretty widow I married, her daughter with hair of red is redhair, etc.

male(i).
spouse(i,widow).
spouse(widow,i).
female(widow).

child(redhair,widow).
female(redhair).

child(i,dad).
male(dad).

spouse(dad,redhair).
spouse(redhair,dad).

child(onrun,dad).
male(onrun).

child(baby,i).
male(baby).

Here's a very appropriate quote from Clocksin and Mellish, 5th ed., pp. 55-56:

However, you must be careful that you do not write "circular" definitions, for example:
parent(X,Y) :- child(Y,X).
child(A,B) :- parent(B,A).

What claims need proving? Again, I'll give you my set, but you should feel free to formulate your own. I figure the kinship-relevant claims of the song are represented by the RHS of the following goal (which returns Yes for me, showing that prolog proves their AND, so all of them are true, so I'm done). Thus one way to build and debug your rule set is to write the most elegant set of kinship rules that take your facts and generate ``Yes'' answers for each of the claims on the right-hand-side.

runit :- daughter(redhair,i), mother(redhair,i), son_in_law(dad,i), brother(baby, dad), uncle(baby,i), brother(baby,redhair), grandchild(onrun,i), mother(widow,redhair), grandmother(widow,i), grandchild(i,widow), grandfather(i,i).

You can ignore differences between the types of mother (step, natural). Likewise brother-types. I did.

There is a (kinship) bug in the claims of the song, I think! What is it and how are you dealing with it?

After you've got your rules powerful enough to agree with the song, you have another source of data. MWAH-HAH-Hah ahahaha...*wheeze*. So exploit it a bit and expand your writeup. I'm thinking of asking questions like uncle(X,Y). and explaining the results. Maybe you can use such unexploited surprising relationships to write your own lyrics, put 'em on 4chan, and get famous.

Weeks 3-4: Parsing into FOPC

2014: Code+Readme 60%, Writeup 40%
post-2014: Code+Readme 50%, Writeup 50%

Read Chapter 9 (esp. 9.2 -- 9.5) of Clocksin Mellish 5th Edition (it's scanned into the e-reserves, listed as number 2, "Clocksin. Programming in Prolog").

Here's the assignment, with more details on grading