Submitting... For this assignment, you'll submit the two files: lists.pl and simpsons.pl. Starter versions of these files are within this zip file:
If you'd like to browse the two starter files, they're linked from here in text format (you'd need to change their names so that their file extensions are .pl to use these):
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 simpsons.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!
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 hw8
/opt/local/bin/swipl -f simpsons.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:
?- [simpsons]. <-- Loads in the file simpsons.pl
% 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 simpsons.pl.You should download that simpsons.pl file -- you may need to change its name to simpsons.pl from simpsons.txt, depending on how you get the file. If it's already simpsons.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 simpsons.pl file under assignment #8.
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)]).
[60 points, pair or individual]
Here, you will write a few Prolog predicates that express relationships about lists (and trees and graphs, expressed as lists). Please submit these rules in one file called lists.pl. This link has a starting point with placeholders. As before, you'll need to change the extension from .txt to .pl.
You may create and use any helper rules that you like. In particular,
some of the rules that we saw in class may be helpful here! For example,
we wrote the member predicate:
member( X, [X|_] ).
member( X, [_|R] ) :- member( X, R ).
The Prolog list predicates to write:
Here are some example queries and their resulting Prolog interactions:
removeOne( a, [a,b,c,a], R ).
R = [b, c, a] ;
R = [a, b, c] ;
No
removeOne( d, [a,b,c,a], R ).
No
removeOne( E, [a,b,c,a], R ).
E = a,
R = [b, c, a] ;
E = b,
R = [a, c, a] ;
E = c,
R = [a, b, a] ;
E = a,
R = [a, b, c] ;
No
% this summarizes the above more succinctly
setof( [E,R], removeOne( E, [a,b,c,a], R ), Answer ).
Answer = [[a,[a,b,c]],[a,[b,c,a]],[b,[a,c,a]],[c,[a,b,a]]]
Use no more than two rules for the removeOne predicate!
If you're writing more than two, take a step back and reconsider!
In particular, remember that
in Prolog, negation is expressed through failure of its search.
Thus, you don't
want a base case involving the empty list as the second argument!
Then, the rules will simply fail when
passed an empty list as a second argument (directly or through recursion) --
this is what you'll want.
So, what rules should there be? For this one, you will want one base-case rule that handles the case when E and the first element of List are identical. Then, you'll want a recursive rule, using the rest of List. That's it!
More hints: If you're stuck on how to write removeOne, here are English descriptions of the two rules you'll want:
count(spam, [oh, spam, spam, we, love, spam], N). % user query
N = 3 ; % prolog reply
No % no more possibilities
count(X, [oh, spam, spam, we, love, spam], N). % user query
X = oh,
N = 1 ; % any more?
X = spam,
N = 3 ; % any more?
X = we,
N = 1 ; % any more?
X = love,
N = 1 ; % any more?
no % no more possibilities
N = 0
When writing the count predicate, be careful that it "counts" exactly the correct number of occurences. One pitfall is to write a version of this function that returns all values of X less than or equal to the correct count.
The count predicate requires no more than three rules. Try re-designing things if your code is going beyond that! Here is a guide to the three rules you'll want:
Thus, for this problem write the rule find(Pattern, Target, Index) which takes two lists Pattern and Target and a non-negative integer Index as input. This find rule should be true if and only if Pattern occurs inside list Target beginning at position Index. The find predicate should not be true in the case that Pattern is the empty list -- so your base case will need to be bigger than the empty list!
For example, here is a Prolog query and response:
find([1, 2], [1, 2, 1, 2, 1], 0). % user query
More? % this prompt is prolog-dependent
Yes % the user hit return (not a semicolon)
Nonessential aside on prolog internals
If you'd like an immediate Yes-or-No answer, you can cut off Prolog's future
searching with the cut operator, the exclamation point: !. Thus,
find([1, 2], [1, 2, 1, 2, 1], 0), !. % user query ~ one search only!
Yes % prolog succeeded
set_prolog_flag( prompt_alternatives_on, groundness ).
End of nonessential aside
Here are two more examples:
setof( N, find( [1,2], [1,2,1,2,1], N ), Answer ).
Answer = [0, 2]
find([], [1, 2, 1, 2, 1], N).
No.
For full credit, your find predicate should work when either or
both of Pattern and Index are Variables. We will only
test your code when Target is bound to a value (it's a non-variiable).
find( Pattern, [a,c,a,c], N ).
Pattern = [a],
N = 0 ;
Pattern = [a, c],
N = 0 ;
Pattern = [a, c, a],
N = 0 ;
Pattern = [a, c, a, c],
N = 0 ;
Pattern = [c],
N = 1 ;
Pattern = [c, a],
N = 1 ;
Pattern = [c, a, c],
N = 1 ;
Pattern = [a],
N = 2 ;
Pattern = [a, c],
N = 2 ;
Pattern = [c],
N = 3 ;
No
setof( [N,P], find( P, [a,c,a,c], N ), Answer ).
Answer = [[0, [a]], [0, [a, c]], [0, [a, c, a]], [0, [a, c, a, c]],
[1, [c]], [1, [c, a]], [1, [c, a, c]], [2, [a]],
[2, [a, c]], [3, [c]]]
The find predicate requires only three rules. Here is a rough guide:
For full credit, your depth predicate should work in the case that
either or both E and/or N are variables or bound values.
You should assume that Tree is, in fact, a binary search tree --
your code should not try to check this.
You'll be able to use the tree below by including in your code the tree1
predicate, as follows:
tree1( [ 42, [ 20, [10, [5, [], []], [18, [], []]], [] ],
[ 100, [67, [50, [], []], []], [150, [], [2009, [], []]] ] ] ).
Here are some example queries and their resulting Prolog interactions:
tree1( T1 ), depth( 42, T1, N ). % user query
T1 = [42, [20, [10, [5, [], []], ... % prints the tree
N = 0 ; % user asks for more with the semicolon
No % no more depths for 42
tree1( T1 ), setof( E, depth( E, T1, 3 ), Answer ). % user query
T1 = [42, [20, [10, [5, [], []], ...
Answer = [5, 18, 50, 2009]
The depth predicate requires only three rules: a base case and two recursive cases. Remember that if you get "singleton" warnings, you may be using a variable only one time in a prolog statement. You can replace that variable with the "don't care" symbol, an underscore: _.
Warning It's better not
to use the "cons bar" (the vertical bar) anywhere in this depth
predicate or the insert predicate below. Remember that the
general form of a binary serach tree is three elements:
[ Root, Left, Right ]
For this predicate, the only input that needs to be handled as a variable (or value) is the last one, NewTree. You should assume that both E and Tree are already bound.
Again, use this tree1 predicate:
tree1( [ 42, [ 20, [10, [5, [], []], [18, [], []]], [] ],
[ 100, [67, [50, [], []], []], [150, [], [2009, [], []]] ] ] ).
Here are two example queries and their resulting Prolog interactions.
The spacing has been adjusted to make it clear what's happening, but Prolog
will simply print the full tree out. (See the note between the Simpsons and
list-based problems to tell Prolog to always print all of its data.)
tree1( T1 ), insert( 43, T1, NewTree ).
T1 = [42, [20, [10, [5, [], []], [18, [], []]], []],
[100, [67, [50, [], []], []],
[150, [], [2009, [], []]]]],
NewTree = [42, [20, [10, [5, [], []], [18, [], []]], []],
[100, [67, [50, [43, [], []], []], []],
[150, [], [2009, [], []]]]]
tree1( T1 ), insert( 41, T1, NewTree ).
T1 = [42, [20, [10, [5, [], []], [18, [], []]], []],
[100, [67, [50, [], []], []], [150, [], [2009, [], []]]]],
NewTree = [42, [20, [10, [5, [], []], [18, [], []]], [41, [], []]],
[100, [67, [50, [], []], []], [150, [], [2009, [], []]]]]
The insert predicate requires no more than four rules: two base cases (if E is there or not there) and two recursive cases. You might re-design things if your code is extending beyond that... .
For full credit, your path predicate should work when A, B, and/or Path are variables. However, you may assume that Graph is a fully-instantiated list of edges -- not a variable.
This time, you might use this graph1 predicate:
graph1( [ [a,b], [b,c], [c,d], [b,w], [w,x], [x,z], [b,z] ] ).
Here are two example queries and their resulting Prolog interactions.
% small example ~ just finding P
graph1(G1), path( a, z, G1, P ). % user query
G1 = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
P = [[a,b],[b,w],[w,x],[x,z]] ;
% our implementation had lots of identical answers...
Here is a means to get all distinct answers:
?- graph1(G1), setof( P, path( a, z, G1, P ), Answer).
G1 = [[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]], % prints G1
Answer = [[[a,b],[b,w],[w,x],[x,z]],[[a,b],[b,z]]] % prints all 2 answers
% HUGE example ~ A, B, and P are all unbound
graph1(G1), path( A, B, G1, P ). % user query
G1 = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
A = B,
P = [] ;
G1 = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
A = a,
B = b,
P = [[a,b]] ;
The path predicate requires no more than three rules (though
it's OK to use slightly more). It can be done very naturally
in only two! You might want to use
the kid predicate we wrote in class:
kid( X, Graph, K ) :- member( [X,K], Graph ).
Submitting... Submit the two files: lists.pl and simpsons.pl.
These problems, minpath and genpath, generalize the path predicate from this week. Depending on how you wrote path, you may have very little to change (other than the name...)!
[up to +10 points, pair or individual]
Submitting... Submit these problems in your lists.pl file.
(This one is worth up to +5 points.)
Write a predicate minpath(A, B, Graph, Path), whose arguments are identical
in format to the path predicate above. However, minpath should
only succeed when Path is a minimal-length path from
A to B. Again, Graph will be acyclic. Keep in mind that
there may be more than one minimal-length path; in that case, minpath
should find them all -- just as you'd expect from Prolog!
(This one is worth up to +5 points.)
Write a predicate genpath(A, B, Graph, Path), whose arguments are identical
in format to the path and minpath predicates above. However, genpath should
work for completely general graphs, i.e.,
even when the graph Graph contains cycles!
For example, you might try graphGen(G), genpath( a, d, G, Path ) with
graphGen( [ [a,b], [b,a], [a,d] ] ).
While genpath should generate paths from start to goal (when they exist, it need not generate only the shortest path. Nor does it need to "know" that a particular path is shortest.