CSC 270
Homework 8

Standards for Prolog programs

Each predicate you write should be accompanied by documentation telling what types its arguments are supposed to be, which arguments should be input/output/either, and giving several examples with their correct answers (which you should write down before writing and testing the program!)

You should turn in a Prolog program, documented as described above, and a sample run showing the outcome of a good selection of test cases.

Six Degrees of Kevin Bacon

The game "Six Degrees of Kevin Bacon" goes like this: you pick the name of a movie actor, and try to find a chain of connections from that actor to Kevin Bacon. A "connection" consists of two actors appearing in the same movie. For example, Harrison Ford was in "Star Wars" with Carrie Fisher, who was in "The Blues Brothers" with John Belushi, who was in "Animal House" with Kevin Bacon, so Harrison Ford is three degrees away from Kevin Bacon.

More generally, one could pick the names of any two movie actors (or directors or producers or whatever), and try to find how closely they are related to one another. Two actors who were in the same movie are one "degree" apart; two actors who were not in the same movie together, but they were each in a movie with the same other actor, are two "degrees" apart; and so on.

(If you're not interested in movies, you can do the same thing with rock bands, or even classes at Adelphi University.)

  1. Write a predicate named in/2 expressing that a particular person was in a particular movie (or band, or Adelphi class, or whatever). Represent the person's name, and the name of the movie, both as Prolog atoms. Give at least half a dozen examples, including at least one pair of people who are one degree apart, at least one pair of people who are two degrees apart, and at least one pair of people who are not related at all. (If you'd like, you can also add some facts about relationships other than appearing in movies, e.g. "these two actors are married to one another".)

    (This part of the assignment should be extremely easy; it doesn't require any actual programming, only coming up with examples.)

    Test your examples by asking a variety of queries: some with both arguments bound, some with only the person bound (i.e. "list all the movies this person was in"), some with only the movie bound ("list all the people who were in this movie"), etc.

  2. Write a predicate named related/2 expressing that two actors were in a movie together (or married, or whatever), i.e. they are one "degree" apart.

    Test your definition by asking a variety of queries: some with both arguments bound ("are these two people related?"), some with one argument bound ("who is related to this person?"), etc. Check that there are no asymmetries, situations in which Joe is related to Mary but Mary isn't related to Joe.

  3. Write a predicate named degrees/3 expressing that two actors are a specified number of degrees apart.

    For your first attempt, get this to work for degree 1, and then degrees 1 and 2. Once we've discussed arithmetic and recursion in Prolog, try to get it to work for any degree.

    Test your definition by asking a variety of queries: some with all three arguments bound ("are these two people 2 degrees apart?"), some with both actors bound but the number unbound ("how far apart are these two people?"), some with one actor and the number bound ("who is one degree apart from this person?"), etc.

    What happens when both actors in the query are the same? What happens when you ask Prolog for further answers after the first? What do you think should happen in these cases?

Last modified:
Stephen Bloch / sbloch@adelphi.edu