CSC 270
Homework 7 in Prolog

Assigned Nov 17, due Dec 8

The Last Homework Assignment

As in homework 6, all programs should come with test cases, either automated or in comments.

Warm-up Exercises (ungraded unless you specifically ask)

Adventure in Prolog chap. 8 exercises 3 and 4: improve the genealogical database

Dates

Define a predicate dayInYear with three parameters: a month number (1-12), a day in the month (1-31), and a day in the year (1-365); it succeeds iff all three numbers are in the legal range and the day in the year correctly reflects the specified date. For example,
```
dayInYear(2,5,36).
```
should succeed because February 5th is the 36th day of the year, and
```
dayInYear(2,30,61).
```
should fail because Feburary has no 30th.
Hint: you may want to use recursion on numbers, but you don't have to. Don't worry about leap years (since you don't even know what year it is).
Your predicate should work correctly if all three parameters are bound; if any one of the three parameters is unbound; or if both the month and the dayInMonth are unbound. That is,
```
dayInYear(2,5,What).
```
should return What=36;
```
dayInYear(2,What,36).
```
should return What=5;
```
dayInYear(What,5,36).
```
should return What=2; and
```
dayInYear(Month,Day,36).
```
should return Month=2, Day=5.

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

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

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. Then try to get it to work for any degree, using recursion.

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?

Operating on structures

In the following problems, we'll define a data structure posn representing an (x,y) coordinate pair. Define the following predicates:

posn+ which takes in three posns and succeeds iff the third is the coordinate-wise sum of the first two (for example,
```
posn+(posn(3,4),posn(5,-1),posn(8,3)).
```
should succeed). You don't have to handle the case that either or both of the first two are unbound variables, but your definition should work whether the third is either bound or unbound.
posn- which takes in three posns and succeeds iff the third is the coordinate-wise difference of the first two. As before, you may assume the first two are bound, but not whether the third is bound.
posn* which takes in a number and two posns, and succeeds iff the second posn is the number times the first posn. As before, you may assume the number and the first posn are bound; for extra credit, handle any one of the arguments being unbound.
Now suppose you want to do some serious arithmetic on posns: for example, 2 * posn(3,4) - 3 * (posn(5,2) - posn(2,1)). We can do this with the above predicates, but it's a pain:
```
posn*(2,posn(3,4),Answer1),
posn-(posn(5,2),posn(2,1),Answer2),
posn*(3,Answer2,Answer3),
posn-(Answer1,Answer3,FinalAnswer).
```
It would be much nicer to write things in the more reasonable notation above. We can: remember that Prolog "knows" about infix operators like +, -, *, etc. It only knows what they "mean" as applied to numbers with the is built-in rule, but you can define your own rule that allows you to write algebraic expressions on posns too.
Write an evalPosn rule that takes in an "expression" and a posn, and succeeds if the expression "evaluates to" the posn. An "expression" can be either
- a posn, in which case it evaluates to itself,
- ( expression ), which evaluates to the same thing as the expression does,
- expression + expression, which is evaluated by evaluating each of the expressions to a posn and then adding their values coordinatewise,
- posn - posn, similarly,
- number * posn, which does what you think it does
So by the time this is over you should be able to write
```
evalPosn(2*posn(3,4)-3*(posn(5,2)-posn(2,1)), What).
```
and get the answer
```
What = posn(-3,5)
```
I think it's not much more difficult to also handle mixed-type expressions, i.e. each expression can be either a posn or a number. But I haven't done this yet, so I won't promise that it's easy; call it extra credit.

More Warm-up Exercises (ungraded unless you specifically ask)

Adventure in Prolog chap. 10 "nonsense Prolog" exercises
Adventure in Prolog chap. 11 exercises 3 and 4

Lists

Write a predicate listLength which succeeds iff its first parameter is a list, and its second is the length of the list. (There's a built-in named length already; your job is to build an equivalent from scratch without using length.) It only needs to work if the list is completely bound.
(Extra credit: it works even if the list is partially or completely unbound.)
Write a predicate elementAfter which succeeds iff its second parameter is a list, and its third is the element after the first occurrence of the first parameter in that list. (If the first parameter doesn't occur, or if it occurs only at the end, elementAfter should fail.) It only needs to work if the list is completely bound.
(Extra credit: it works even if the list is partially or completely unbound.)
Write a predicate countMatches which succeeds iff its second parameter is a list and its third parameter is the number of times the first parameter occurs in that list. It only needs to work if the list is completely bound.
(Extra credit: it works even if the list is partially or completely unbound.)
Write a predicate convertReversed which succeeds iff its first parameter is a list of integers in the range 0-9 and its second parameter is the number they represent in decimal, interpreting the first digit as the least significant. (For example,
```
convertReversed([3,2,7], 723).
```
should succeed.) It only needs to work if the list is completely bound.
(Extra credit: it works even if the list is partially or completely unbound; used this way, it essentially converts numbers to decimal.)
Write a predicate largest which succeeds iff its first parameter is a non-empty list of numbers and the second parameter is the largest number in the list. It only needs to work if the list is completely bound.
(Extra credit: it works even if the list is partially or completely unbound.)
Write a predicate substitute which succeeds iff its third and fourth parameters are lists, equal to one another except that all occurrence of the first parameter appearing in the third are replaced in the fourth parameter by the second. It only needs to work if the first list is completely bound.
(Extra credit: it works even if the first list is partially or completely unbound.)

Six Degrees of Kevin Bacon, revisited

Based on your degrees predicate from above, write a path predicate that takes in two actors' names and binds the third parameter to a list showing a link from one to the other. At a minimum, this list should indicate each actor's name along the way; it would be cooler if it showed not only each actor's name but what movie they were both in, at each step. For example, you could do it as a list of alternating actors' names and movie names, e.g.
```
path('Harrison Ford', 'Kevin Bacon', Path)
```
might produce
```
Path = ['Harrison Ford', 'Star Wars', 'Carrie Fisher', 'The Blues Brothers', 'John Belushi', 'Animal House', 'Kevin Bacon']).
```

Cut and higher-order predicates

We've been writing test predicates that throw a bunch of bound values at a predicate and check whether it succeeds or fails. But sometimes you want to test a predicate on unbound parameters to see whether it generates the right answer. Here's a step in that direction.

Write a firstResult predicate which takes in a question, a variable name (which presumably appears in the question), and a value; it asks the question with the variable unbound, and then checks whether the variable was bound to the specified value. For example,
```
firstAnswer(convertReversed(Digits,30150), Digits, [0,5,1,0,3]).
```

Last modified:

Stephen Bloch / sbloch@adelphi.edu

CSC 270 Homework 7 in Prolog