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

Submitting...    For this assignment, you'll submit the file: movies.pl or movies.pro. In order to write movies.pl, you'll need the helper file movies_db.pl. Starter versions of these files with examples and hints are available here. Be sure to rename these files to end in .pl or .pro, not .txt

• movies.txt (rename this to movies.pl)
• movies_db.txt (rename this to movies_db.pl)
• lists.txt (rename this to lists.pl)

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 starter files(s).

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

First, you will want to be sure you can run prolog -- either from your computer or from the CS lab machines. You can also run prolog from the LAC lab, but you will have to install it to your own space on the H: drive.

Instructions from your own machine (or at the LAC):

• 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 below). 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!

• First, open a terminal window - there should be a console-like icon in the dock. Or, use the searchlight finder (upper right) and seek Terminal.
• At the terminal's prompt, type cd Desktop, which should put you in the directory that is your desktop.
• Download movies.txt to your desktop and change its name to movies.pl. Then, open the movies.pl file in a text editor. If you're not sure which one to use, you might try Smultron, which is available on the lab Macs via clicking on the background, heading to the "Go" menu, and then clicking through "Applications" - "Additional Applications" - "Text" - "Smultron"
• Any text editor is OK, however. Smultron is available online for free.
• Go back to your terminal window and, when in the directory containing movies.pl, type swipl at the prompt. This will start prolog. If you're on your own Mac, then you may have to type /opt/local/bin/swipl, providing the full pathname so that your machine can find swipl.
• You can make sure it's working by entering Answer.
• You can load the movies.pl file by entering [movies]. (don't include the extension).
• You're set! You should be able to change movies.pl in your text editor, reload it as above, and test the results...
• Good luck!

Part 1: The movie-database predicates...

[ 100 points, pair or individual ]

This problem asks you to write 10 prolog predicates (worth +10 points each) whose descriptions are in the movies.pl file. We list them here for reference:

• directedBandits
• directedByBay
• actressAfter1970
• player
• bornInLondon
• playerAndDirector
• playedAndDirected
• playedMultiple
• playedInComedy
• playedNotDirected

Be sure that you have the movies_db.pl file in the same directory as your movies.pl file. The line at the top of movies.pl:

:- ensure_loaded('movies_db.pl').

A prolog aside ...

Although it seems that Prolog offers an interpreter and a file interface - similar to Scheme, keep in mind that Prolog is a bit different: you must define everything in a file. Prolog's command line can only be used to make queries based on the facts and rules loaded in from a file. Therefore, the following will NOT work:

?- [movies].   <-- Loads in the file  movies.pl
% movies compiled 0.42 sec, 4242 bytes
Yes

?- actor(zach_braff).

Part 2: Extra credit! Lists in Prolog

[ up to +10 points, pair or individual ]

Here, you have the chance to try writing two Prolog predicates that express relationships about lists. Please submit one or both of these rules in one file named 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 ).

Two extra credit predicates to try:

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






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