Assignment 8: Prolog - yes! [100 points]
Due Monday, November 2 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 linked from the main assignment page.

Formatting and commenting...

Please use the standard commenting convention of your name, file name, and date at the top of each file. THIS WEEK WE WILL TAKE OFF POINTS IF THIS COMMENT IS MISSING!  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 cause our scripts to "barf."

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

First, you will want to be sure you can run prolog -- either from your computer or from knuth.

Instructions from knuth:

• Log in to knuth. Create a new folder (probably) for your hw #8 files. Copy the starter files, named simpsons.pl and lists.pl to your directory using WinSCP or some equivalent program.


• You can start prolog and try out its interface by simply typing

    pl
    

  at the command prompt.


• You can load a file with

    pl -f simpsons.pl
    

  or any other file name you'd like.


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


• 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 either Windows or Mac OS X. The Mac version requires you to have X11 (for the graphical interface) installed (if you have a recent enough Mac, you probably do). The location of the program after it installs on a Mac is /opt/local/bin/swipl. On the Mac, you'll need to run it from the command line (similar to the instructions above). On a PC, you'll have a window that opens for the Prolog "command line" and others 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...

Unlike programming languages we've considered so far: 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, minibart).

      

Part 1: The Simpsons' family tree...

[40 points (10 points each), 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 four 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
• cousins
• hasYS
• 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)!



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




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




• hasFirstGC(X) should be true if and only if X has both a parent P and a child C, such that C is P'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: notoldest that we looked at in class won't help outright on this problem, but consider writing a variant, perhaps named notoldestgrandchild( GP, GC ), which is true if GC is not GP's oldest grandchild. Then the negation example we looked at in class will serve as a good template!

  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

Prof. Keller has found some of the 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 into your source file, or copy everything but the first two characters at the Prolog prompt:

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

In this section you will implement 4 predicates: 3 of which are specified, and the last is your choice of 3 possibilties.  In other words you will implement:

• ALL of: removeOne, count, and find
• ONE of (your choice): depth, insert, or path

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

  Here are three 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
  

  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!

  The removeOne predicate requires no more than two rules. If you're writing more than three (or even 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! After all, the rules should simply fail when passed an empty list (directly or through recursion); that is, there should be no such rule at all.




• 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 non-variable (bound to a value) with the nonvar or var predicates. Either is ok.  Since we didnt' get a chance to talk about var and nonvar, don't worry about them, unless you feel like playing around with them on your own.

  hen 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. (You might re-design things if your code is extending much beyond that... .)




• 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).
  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( Pair, P^N^(find( P, [a,c,a,c], N ), Pair=[N,P]), 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 caret ^ acts as a "there exists" operator, i.e., the set of Pair values such that there exists a P and an N that satisfies the expression

      (find( P, [a,c,a,c], N ), Pair=[N,P])
  

  Yes - crazy, but true.

  The find predicate requires no more than three rules. (You might re-design things if your code is extending much beyond that... .)

• 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 no more than three rules. (You might re-design things if your code is extending much beyond that... .)




• 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. 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. (You might re-design things if your code is extending much 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 nodes, beginning with A and ending with B that connects those two with edges from Graph. You should assume that Graph is acyclic. Also, you should assume that every node A is reachable from A itself using the path [A].

  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 -- again, it will not contain any cycles.

  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, w, x, z] ;   % any more?
  
  G1 = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  P = [a, b, z] ;         % any more?
  
  No
  
  
  
  % HUGE example ~ A, B, and P are all unbound
  graph1(G1), path( A, B, G1, P ).  % user query
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = B,
  P = [B] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = a,
  B = b,
  P = [a, b] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = a,
  B = c,
  P = [a, b, c] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = a,
  B = d,
  P = [a, b, c, d] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = a,
  B = w,
  P = [a, b, w] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = a,
  B = x,
  P = [a, b, w, x] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = a,
  B = z,
  P = [a, b, w, x, z] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = a,
  B = z,
  P = [a, b, z] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = b,
  B = c,
  P = [b, c] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = b,
  B = d,
  P = [b, c, d] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = c,
  B = d,
  P = [c, d] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = b,
  B = w,
  P = [b, w] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = b,
  B = x,
  P = [b, w, x] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = b,
  B = z,
  P = [b, w, x, z] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = w,
  B = x,
  P = [w, x] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = w,
  B = z,
  P = [w, x, z] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = x,
  B = z,
  P = [x, z] ;
  
  G = [[a, b], [b, c], [c, d], [b, w], [w, x], [x, z], [b, z]],
  A = b,
  B = z,
  P = [b, z] ;
  
  No
  

  The path predicate requires no more than two rules! (Well, you need the kid predicate we almost wrote in class:

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

  (You might re-design things if your code is becoming much longer than that... .)

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