Assignment 8: Prolog - yes! [100 points]
Due Sunday, November 2 by 11:59 PM

Formatting and commenting... Please use the standard commenting convention of your name, file name, and date in each file. In addition, be sure to include a comment for each function that you implement. 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, open a terminal window (there should be a console-like icon in the dock)
• At the prompt, type cd Desktop, which should put you in the directory that is your desktop.
• Open the part1.pl file in a text editor. If you're not sure which one to use, you might try Smultron, which is available by clicking on the background, heading to the "Go" menu, and then clicking through "Applications" - "Additional Applications" - "Text" - "Smultron"
• Go back to your terminal window and, when in the directory containing part1.pl, type swipl at the prompt. This will start prolog.
• You can make sure it's working with Answer.
• You can load the part1.pl file by entering [part1]. (don't include the extension).
• Test it out with parent( X, bart ). Hitting enter stops the search for more variable-bindings that satisfy X. Hitting the semicolon continues the search.
• You're set! You should be able to change part1.pl, reload it as above, and test the results...
• Good luck!

Part 1: The Simpsons' family tree... [40 Points]

You should download that part1.pl file -- you will need to change its name to part1.pl from part1.txt. In that file, below the rules for the family tree, you will see a place to write the following rules: You may also add any additional helper rules that you wish, including anything that we looked at in class. However, please don't change the facts about parenthood/relationships among the Simpsons!

• grandparent(X, Y) is true if and only if X is a grandparent of Y.
  
  
• cousins(X, Y) is true if and only if X and Y are first cousins. Note that a person cannot be their own cousin. Also, do not consider brothers and sisters to be cousins for this problem.
  
  
• hasYS(X) is true if and only if X has a younger sister. (Consider "younger" to mean less-than-or-equal-to in age.)
  
  

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 excellent resource is Learn Prolog Now!, a site that explains the language concisely and with a number of examples.

Please submit your solutions as part1.pl under assignment #8.

Prolog 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

following the output, for example:

?- range(1, 50, X).

X = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] w

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]

Yes


To change the limit on the number of elements once and for all, copy the 
following into your source file:

:- set_prolog_flag(toplevel_print_options, 
     [quoted(true), portray(true), attributes(portray), 
     max_depth(999), priority(699)]).

You may use any other value for max_depth, including 0, which will 
place no limit on the depth of the expression. The default value of 
max_depth is set at 10. The values of the other attributes are just 
the default ones.


For longer term use, you may also put this incantation in your initialization 
file, which resides in a system-dependent place. See the manual for info on this:

http://gollem.science.uva.nl/SWI-Prolog/Manual/initfile.html

Part 2: Lists in Prolog [60 Points]

• reverse(X, Y) is true if and only if list Y is the reversal of list X. Notice that you can use this rule to now actually compute the reversal R of a list by typing, for example, reverse([1, 2, 3], R). Make sure this works. (Your rules do not have to work in the case that the first argument is a variable and the second argument is literal data.)
  
  
• occurs(X, L, N) is true if and only if item X occurs in list L exactly N times. Here is an example:

   | ?- occurs(spam, [oh, spam, spam, we, love, spam], X).
  
   X = 3 ;
   no
   

  When writing this predicate, be careful that it "computes" exactly the correct number of occurences (an easy pitfall is to write a version of this function that returns all values of X less than or equal to the number of occurences). Also, your occurs predicate should be able to generate the terms that occur a particular number of times, e.g.,

   | ?- occurs(T, [oh, spam, spam, we, love, spam], 3).
  
   T = spam ;
   no
   

• One-dimensional pattern matching is an important task in many applications such as cryptography and DNA sequencing. We'll encode a pattern as a list of items and we'll search for a pattern in another list called the "target". The rule find(Pattern, Target, Index) takes two lists Pattern and Target and a non-negative integer Index as input. This rule is true if and only if Pattern occurs inside list Target beginning at position Index. For example, here is a Prolog query and response:

   | ?- find([1, 2], [1, 2, 1, 2, 1], 0).
   yes
   

  Notice that pattern [1, 2] occurs in target [1, 2, 1, 2, 1] beginning at position 0 of the target (that is, the very beginning of the target list).

   [1, 2, 1, 2, 1]
    ^
    |
   The pattern [1, 2] appears beginning right here at location 0.
   I'm looking for a 1 followed immediately by a 2 and I find it
   beginning here!
   

  It also occurs again at position 2 of the target.

   [1, 2, 1, 2, 1]
          ^
          |
   The pattern [1, 2] appears beginning right here at location
   2.
   

  Thus, here's another Prolog query and response:

   | ?- find([1, 2], [1, 2, 1, 2, 1], 2). 
   yes
   

  In fact, these are the only two occurences as indicated by the following Prolog query and response:

   | ?- find([1, 2], [1, 2, 1, 2, 1], X). 
  
   X = 0 ;
   X = 2 ;
   no
   

  find(P,T,I) should also work when both P and I are unbound variables. Write the rules for find. 
   
• remove(F, List, NewList) is true if and only if F is an element of List and, List is a list - which you may assume contains no repeated elements - and NewList is a list identical to List except that F is not in Newlist. For example,

  | ?- remove(1, [2, 1, 3], [2, 3]).
  yes
  
  | ?- remove(1, [2, 1, 3], X).
  X = [2,3] ;
  no
  
  | ?- remove(1, [2, 3, 4], X).
  no
  
  | ?- remove(X, [1, 2, 3], [2, 3]).
  X = 1 ;
  no
  
  | ?- remove(X, [1, 2, 3], Y).
  X = 1,
  Y = [2,3] ;
  
  X = 2,
  Y = [1,3] ;
  
  X = 3,
  Y = [1,2] ;
  
  no
  

  Your remove rule must be able to work when either the first or last argument, or both, are variables, as demonstrated above. You don't need to worry about the case that the second argument is a variable. Note the requirement that F be a member of List -- we wrote a member predicate in class that you're welcome to use (it's built in to some versions of prolog, but not others):

  member( X, [X|_] ).
  member( X, [_|R] ) :- member( X, R ).
  

Extra credit: up to + 20 points

You may recall that in scheme we wrote a function called powerset which took as input a list S (imagined to be a set of distinct items) and then returned the powerset of S: the set of all subsets S. The scheme version used an algorithm based on "weirdo analysis" in its implementation.

For optional extra credit in prolog, implement an even-better version! Write a rule called subset(List1, List2) which takes two lists List1 and List2 as input and infers whether List1 is a subset of List2. (Notice that since we're using lists to represent sets, we're implicitly assuming that any given element appears at most once in a list. Keep in mind, however, that you should not assume anything about the order in which the elements are given in the lists.) No weirdo analysis is needed here... . Your predicate will simply describe to prolog how to infer that one set is a subset of another!

You may wish to use one or more helper rules. Your subset rule must work when it is given two actual lists and it must also work when the first argument is a variable and the second argument is an actual list. It need not work in the case that the second argument is a variable (although it's not hard to take care of that case either).

For example:

| ?- subset([1, 2], [2, 1, 3]).
yes

| ?- subset([1, 2], [1]).
no

| ?- subset(X, [1, 2]).
X = [] ;

X = [1] ;

X = [1,2] ;

X = [2] ;

X = [2,1] ;

Notice in the last example, the same subset appeared more than once (as [1, 2] and [2, 1]). This is fine, as long as your rule eventually stops and all correct answers are produced at least once. Moreover, the order in which the subsets are found and the order of the actual elements in the lists is unimportant. Submit your code at the bottom of your part2.pl file.