Assignment 8: Prolog - true! [100 points]
Due Monday, March 28 by 11:59 PM

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:

• hw8.zip, including lists.pl and simpsons.pl

• lists.txt
• simpsons.txt

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!

Part 0: Getting started... [0 points]

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:

• You'll want to log in and download the HW files: they will unzip into a folder named hw8. We'll suppose it's on the Desktop.
• Next, open a terminal window. You can use the Searchlight feature (upper right) to look for terminal. You'll see a command-line interface open up.
• Next, change directory to the hw8 folder. This will use cd as follows:

    % cd Desktop
    % cd hw8
    

  You should see simpsons.pl and lists.pl when you type ls, which is the command to list all the files in the directory.
• Next, you can open prolog with the command /opt/local/bin/swipl
• Then, you can load a file, e.g., the simpsons.pl file at the prolog prompt with [simpsons]. - the period at the end is important!
• You may see warnings about "Singleton variables" - don't worry about these for now.
• You can also load a file upon starting with

    /opt/local/bin/swipl -f simpsons.pl
    

  or any other file name you'd like. Remember that you can use the up arrow to repeat a command you've typed earlier (so that there's no need to retype it).
• You might try predicates such as

    parent(X, bart).
    

  once the simpsons.pl file is loaded. Recall that the semicolon means OR, and asks for more possible solutions. Hitting return stops the search for possible solutions to a predicate query.
• To edit the simpsons.pl file, you might use any text editor at all. I use the Max OS built-in editor, named TextEdit, which can be found in Applications.
• You will notice that the simpsons.pl file, as written, will cause Prolog to warn you about "singleton" variables. These warnings will (or, at least should) disappear when you write the predicates that are described for this week's hw, below.

• You can obtain a version named SWI prolog from for Windows (32 or 64 bit), Mac OS X (various versions), and Linux.
• On a Mac, the location of the program after it installs is /opt/local/bin/swipl. Also, on the Mac, you'll need to run prolog from the command line -- see the instructions above describing how to use Prolog on the CS lab machines, which are Macs. As above, you can use the Mac built-in text editor, called TextEdit to edit your prolog files. Under Windows, there is a graphical user interface for the Prolog "command line" and other windows for editing your Prolog source files.


• Warning: the SWI prolog versions noted above use true and false instead of yes and no in repsonding to queries. This decreases Prolog's joke-making ability by several orders of magnitude!

One important note before you get started...

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!

Part 1: The Simpsons' family tree...

[40 points (5 points each), pair or individual]

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

• person
• parent
• female
• male
• age

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

• grandparent
• siblings
• cousins
• hasDaughterAndSon
• hasOlderSibling
• hasYS (younger sister)
• hasOlderCousin
• hasFirstGC

The Simpsons' Family-tree predicates to write:

• grandparent(X, Y) should be true if and only if X is a grandparent of Y.
  You can test this out with

      grandparent( john, bart ).  % yes!
      grandparent( lisa, bart ).  % no.
      grandparent( X, bart ).     % there will be four answers
      

  In fact, you can check all four of the answers to the last query above using the setof predicate. Try this -- it will be useful throughout using Prolog!

      setof( P, grandparent( P, bart ), Answer ).     
      
      Answer = [homericus, jackie, john, matilda]
      

  Thus, setof is a three-input predicate whose first input is a variable and whose second input is a predicate using that variable. Then, setof tries to find all of the values for that variable that satisfy the predicate. Those values are collected into a list and bound to the name that is the third and final input to setof. Crazy (but helpful)!



• siblings(X, Y) should be true if and only if X and Y are siblings Note that for the sake of this problem (and perhaps in general), a person cannot be their own sibling.
  
  You can test this out with

      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(X, Y) should be true if and only if X and Y are first cousins. Note that for the sake of this problem (and perhaps in general), a person cannot be their own cousin. Similarly, do not consider brothers and sisters to be cousins for this problem.
  
  You can test this out with

      cousins( bart, lisa ).            % no
      cousins( bart, terpsichore ).     % yes
  
      setof( C, cousins(C,lisa), Answer ).    % lisa has 2 cousins here
      Answer = [millhouse, terpsichore]
      




• hasDaughterAndSon(P) should be true if and only if P is a parent of a daughter and a parent of a son.
  
  For example, you can test this out with

      hasDaughterAndSon( homer ).            % yes/true
      hasDaughterAndSon( esmerelda ).        # no/false
  
      setof( P, hasDaughterAndSon(P), Answer ).    
      Answer = [cher,glum,homer,jackie,john,marge]
      




• hasOlderSibling(X) should be true if and only if X has an older sibling (half-sibling is OK). (Consider "older" to mean strictly greater-than in age.)
  You should check this with some queries of your own devising; in addition, you can check for all of the people with older siblings with

      setof( X, hasOlderSibling(X), Answer ).      
  
      Answer = [atropos,glum,homer,homericus,lachesis,lisa,maggie,marge]
      




• hasYS(X) should be true if and only if X has a younger sister. (Consider "younger" to mean strictly less-than in age.)
  You should check this with some queries of your own devising; in addition, you can check for all of the people with younger sisters with

      setof( P, hasYS(P), Answer ).      % everyone with a younger sister
  
      Answer = [atropos, bart, klotho, lisa, patty, selma]
      




• hasOlderCousin(X,GP) should be true if and only if X has an older cousin through the particular grandparent GP. That is, X is a grandchild of GP and GP has another grandchild who is strictly older than X.
  You should check this with some queries of your own devising; in addition, you can check for all of the people with older cousins (and the grandparents through which this occurs) with

      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]] 
      

  There are lots of answers in this case!
  Note: using six clauses to define hasOlderCousin is completely OK -- and may, in fact, be necessary. (The notes at one point said 5.)



• hasFirstGC(X) should be true if and only if X has a parent GP and a child C, such that C is GP's oldest (hence "first") grandchild. The predicate hasFirstGC(X) should be false if X has no parent or has no child (or does not have a child that matches the criterion above).

  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)]).

Part 2: Lists in Prolog

[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:

• removeOne(E, List, NewList) should be true if and only if E is an element of list List one or more times, and the list NewList should be identical to List except that the element E is removed once. Note that the element may appear more than once, and so it can be removed from different parts of the list List.

  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]]]
  

  For full credit, your removeOne predicate must be able to work when either the first or last argument, or both, are variables, as demonstrated above. You should assume that the middle argument is bound to a list value (that is, it's not a variable). Keep in mind the requirement that E be a member of List!

  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:

  1. Rule 1    This should be a base case that expresses the fact that when you remove an item from a list that has that item as its initial element, then the result is the rest of that list. (One rule: no need for the :- sign at all.)
  2. Rule 2    This should be a recursive rule that expresses the fact that when you remove an item from a list that has some initial element, then the result will have that same initial element, but a different "rest" And the "rest" of the result will be obtained by calling removeOne on the "rest" of the original list. (One rule with only one recursive clause after the :- sign.)




• count(X, L, N) should be true if and only if item X occurs in list L exactly N times. For full credit, your predicate should work when X and/or N are variables (or both). It does not need to work when L is a variable.
  
  Here are two examples:

      count(spam, [oh, spam, spam, we, love, spam], N).  % user query
      N = 3 ;    % prolog reply
      No         % no more possibilities
  

  and a case where both X and N are variable:

      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
  

  It's OK to get one more result in the latter case, above, with

      N = 0      
  

  and either no X at all or an unnamed variable X. Whether or not you get this final possibility depends on where (if at all) your code forces things to be bound to a value. Any of these is ok.

  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:

  1. a base case for when the count is zero
  2. a case where X is NOT the first element of L
  3. a case where X is the first element of L.




• One-dimensional pattern matching is an important task in many applications such as cryptography and DNA sequencing. For this problem we encode a 1d pattern as a list of items (named Pattern) and we'll search for that pattern within another list called the Target.

  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)
  

  The extra More? can be annoying when trying to test to see if a fully-instantiated query succeeds or not. By printing that More? Prolog is saying that it did succeed at the query -- it's then asking if you'd like it to try to succeed again through a different line of reasoning. You're probably not worried about that, so you can simply hit return.

  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
  

  Using ! is not required, but it's there if you'd like to. Alternatively, you can tell Prolog to stop being ridiculous via the line

  set_prolog_flag( prompt_alternatives_on, groundness ).
  

  and it will stop the extra-prompting (unless there are variables present). We have done this for you in this week's starter files.
  End of nonessential aside

  Here are two more examples:

      setof( N, find( [1,2], [1,2,1,2,1], N ), Answer ).
      Answer = [0, 2]
  

  and

      find([], [1, 2, 1, 2, 1], N).
      No.
  

  Remember that find should not succeed for the empty Pattern.

  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
  

  You can coax setof to give you all of these at once, if you'd like:

      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:

  1. a base case when the Pattern is a list of a single element and when that same element is the first element of a potentially longer Target list. In this case, Index should be 0.
  2. a recursive case when the Pattern has a first and a rest (and so does the Target), but when the Index is still 0.
  3. a recursive case when the Pattern is any list, the Target has a first and a rest, and the Index is a variable (and will end up being something greater than 0).
  
  
  
• depth(E, Tree, N) should be true if and only if E is an element of the binary search tree Tree at a depth of N. The root of the tree is defined to be at depth 0. The children of the root are all at depth 1, their children at depth 2, and so on.

  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, [], []]] ] ] ).
  

  Then you can use this to bind a variable to the above data before testing. The examples below illustrate this.

  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 ]
  

  which requires only commas, no "cons"es.




• insert(E, Tree, NewTree) should be true if and only if NewTree is a binary search tree identical to Tree, except that the element E is now present in NewTree in an appropriate place. It is OK if E is already in Tree -- in that case, NewTree and Tree will be identical.

  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, [], []]] ] ] ).
  

  Then you can use this to bind a variable to the above data before testing.

  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... .




• path(A, B, Graph, Path) should be true if A and B are both nodes in the graph Graph and if Path is a list of edges from Graph, with the first beginning with A and the last ending with B that connects those two nodes. You may assume that Graph is acyclic. (But see the extra credit.) Also, you may assume that every node A is reachable from A itself using the empty path [].

  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] ] ).
  

  Then you can use this to bind a variable to the above data before testing.

  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]] ;
  

  and too many more to iterate through by hand...

  The path predicate requires no more than three rules (though it's OK to use slightly more). You might want to use the kid predicate we wrote in class:

  kid( X, Graph, K ) :- member( [X,K], Graph ).
  

  But it's not required! An alternative is to employ a use-it-or-lose-it approach similar to how you solved graph-based problems in Racket.

Submitting...    Submit the two files: lists.pl and simpsons.pl.

Totally optional extra credit: up to +10 points

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.