Prolog 2

• How does Prolog work?
• Unification
• The goal stack
• Numbers in Prolog
• Prolog in Scala

How Does Prolog Work?

• Informal example. Procedure

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

  Goal

  member(mary, [john, mary, pat]).

• Match goal with head of first clause
• Match fails: X can't be both mary and john
• Match goal with head of second clause
• Match succeeds: X = mary, _ = john, T = [mary, pat]
• Replace goal with right hand side

  member(mary, [mary, pat])

• This is the goal now. Match with head of first clause
• Match succeeds: X = mary, _ = pat
• First clause is a fact. Report true.
• Not done yet—also match with second clause...

Unification

• Given: Two terms
• Want: Definitions for variables that make the terms identical
• Example: Terms member(X,[_|T]) and member(mary, [john, mary, pat])
• Solution X = mary, _ = john, T = [mary, pat]
• Can have variables in both terms
• Unification algorithm provides “most general” variable assignment

Unification Algorithm

• Start with a pair of terms
• As the algorithm progresses, we will get a set of pairs
• Each pair has the form L = R, where L, R are either a term or a variable
• Keep choosing an equation until failure occurs or no further change is possible

  Equation	Action
  f(s1, ..., sn) = f(t1, ..., tn)	Replace with s1 = t1, ..., sn = tn
  f(s1, ..., sn) = g(t1, ..., tn) where f ≠ g	Halt with failure
  X = X	Delete the equation
  t = X where t is not a variable	Replace with X = t
  X = t where X does not occur in t and it occurs elsewhere	Apply the substitution X = t to all other terms
  X = t where X occurs in t (but t ≠ X)	Halt with failure

Unification Example

• member(X,[_|T])= member(mary, [john, mary, pat])
• Write [ | ] as cons
• member(X, cons(Z, T))= member(mary, cons(john, cons(mary, cons(pat, nil))))
• Apply rule 1:
  • X = mary
  • cons(Z, T) = cons(john, cons(mary, cons(pat, nil)))
• Do it again:
  • X = mary
  • Z= john
  • T = cons(mary, cons(pat, nil))
• We are done

The Goal Stack

• The initial goal is the first goal on the stack
• New goals are pushed on the stack
• Yields depth-first search
• Example: Clauses

  parent(james1, charles1).
  parent(james1, elizabeth).
  parent(charles1, charles2).
  parent(charles1, catherine).
  parent(charles1, james2).
  
  grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

  Query: grandparent(james1, G)

• Unify query with head of matching clause: X = james1, Y = G
• Push new goals on stack (leftmost on top)

  parent(james1, Z)
  parent(Z, G)

• Unify top query with head of matching clause: Z = charles1
• Pop off matched goal, apply substitution. Goal stack is now

  parent(charles1, G)

• Actually, easier to store original terms + substitutions

  parent(Z, Y) / X = james1, Y = G, Z = charles1

Choice Points

• When picking a match for query head, have choices
• Goal: parent(charles1, G)
• 5 choices

  parent(james1, charles1).
  parent(james1, elizabeth).
  parent(charles1, charles2).
  parent(charles1, catherine).
  parent(charles1, james2).

• First two don't match (Unification fails because charles1 ≠ james1)
• Next one is applied, yielding G = charles2
• Goal stack now empty. Report result (bindings of variables in original query)
• Still two choices to go.
• Backtrack to the next one. Yields G = catherine
• Etc.

Variable Renaming

• Can have name clashes with variables
• Example:

  ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).
  ancestor(X, Y) :- parent(X, Y).

  Query: ancestor(james1, X)

• Unify ancestor(james1, X) with ancestor(X, Z)
• Each term has variable X
• Rename rule variable: ancestor(james1, X) and ancestor(X1, Z)
• Unifying substitution: X1 = james1, X = Z
• Goal stack:

  parent(X1, Y) / X1 = james1, X = Z
  ancestor(Y, Z) / X1 = james1, X = Z

• Match for topmost goal: Y = charles1
• Now top goal is ancestor(Y, Z). Unify with ancestor(X, Z).
• More name clashes. Rename to ancestor(X2, Z1)

Summary of Prolog Algorithm

• Unification: Yields substitution that makes terms match
• Goal stack: Depth-first search
• Choice points: Backtracking

Numbers in Prolog

• Prolog has integer type
• Three of the comparison operators look weird

  > >= < =< =:= =\=

• = is unification, not “evaluate and assign”. The query X = 3 + 4. (or 3 + 4 = X.) yields X = 3 + 4. How helpful!
• Use is operator to force arithmetic evaluation.

  X is 3 + 4.
  X = 7

• Right hand side of is can contain variables, but they must already be bound to numbers
• Prolog cannot solve equations.

  7 = 3 + X.
  false

• Factorial predicate: factorial(N, F) means F equals N!

  factorial(0, 1).
  factorial(N, F) :- N > 0, N1 is N - 1, factorial(N1, F1), F is N * F1.

• Note that factorial(N - 1, F1) would not work. (See the lab).

Lab

• Check into eCampus in the usual way
• Scribe puts in report
• Buddy puts in comment with scribe's name

Step 1: Unification

1. Consider the terms

   member(X, cons(john, cons(mary, nil)))
   member(X17, cons(X17, T))

   Compute a unifying substitution (by hand). What is it?

2. Consider the goal

   member(X, cons(john, cons(mary, nil)))

   and the clause

   member(X, cons(X, T)) :- member(X,T).

   Compute a unifying substitution of the goal and the head of the clause after renaming variables in the clause. What is it?

3. Apply the substitution to the body of the clause. What term do you get?

Step 2: How Prolog Works

Save this Prolog.scala file. In a shell window, type

scala -i Prolog.scala

When you get a prompt, type these commands:

import Prolog._
val member = new Predicate
member('X, 'X::'Xs)!
member('X, 'Y::'Ys) :- member('X, 'Ys)
member('X, 'john :: 'mary :: 'nil)?
more
more

As you can see, the implementor of this interpreter cleverly overloaded operators ! (fact), :- (provided that) and ? (query).

Note the single quote that is used for variables.

Now type

showMatches = true
member('X, 'john :: 'mary :: 'nil)?
more
more

What output do you get?

Step 2 Part 2

Now comes the hard part: Put together a complete trace of what the interpreter does. In each step, you can choose from

• Push goal on goal stack
• Choose next matching rule
• Use unification to compute new substitution
• Rename variables in a rule
• Pop goal off goal stack
• Display result

Use the same substitution that the Scala interpreter uses. When I ran it, the trace output started with

unify 'X with 'john = true
unify 'X16 with 'john = true
unify 'Xs17 with 'mary :: 'nil = true

My solution would be

Step 1. Push member(X, cons(john, cons(mary, nil))) on goal stack

Step 2. Choose rule member(X, cons(X, Xs)).

Step 3. Rename into member(X16, cons(X16, Xs17)).

Step 4. Use unification: X = X16, john = X16, Xs17 = cons(mary, nil) solves as X = john, X16 = john, Xs17 = cons(mary, nil).

Step 5. Unification with fact was success. Display result.

Step 6. Choose rule member(X, cons(Y, Ys)) :- member(X, Ys).

...

Step 3: Arithmetic

1. Consider this definition of a factorial predicate. FAC(N,M) means that M = N!. (Remember, we need a predicate, not a function, at the top level in Prolog.)

   factorial(0, 1).
   factorial(N, F) :- N > 0, factorial(N-1, F1), F is N * F1.

   Try it out. What is the result of fac(3,X)?

2. Use the text-based tracer to trace to the step

   3-1-1-1 > 0? 

   Does it succeed? Does it fail? If so, why? What happens next?

3. When you are done tracing, issue the query

   3-1-1-1 > 0.

   at the Prolog interpreter. What result do you get?

4. Ok, so why did the recursive factorial fail? (Hint: Try unifying factorial(3-1-1-1,X), that is, factorial(sub(sub(sub(3, 1), 1, 1), X) with factorial(0, 1).)
5. Fix factorial by forcing evaluation of the arithmetic. What is your code for factorial now? Confirm that factorial(3, X) works.
6. Try factorial(X,6). What happens?
7. That's disappointing, but if you think about it, there is no way Prolog could have figured out the answer. Except...
8. ...by trying all the possible answers. Here is how that works:

   solvefac(N,M) :- numlist(1, M, L), member(N, L), factorial(N, M).

   Try out solvefac(X,6). Explain why it works. (To see what numlist does, just run numlist(1, 6, X).)

Step 4: The Game of Nim

1. In the game of Nim, two players alternately remove marbles from a pile of marbles. In each turn, a player must remove at least one marble, and at most half the marbles. The player who is left with one marble loses. We will represent the game state by a list of o functors, such as [o,o,o,o,o]. Your task is to write a predicate move(F, T) that checks whether one can legally move from game state F to game state T. For example,

   move([o,o,o,o,o],Y).
   Y = [o,o,o] ;
   Y = [o,o,o,o] ;
   fail

   Hint: It is very easy to check whether T at least one less than F:

   append(S, _, F), append(T, [o], S)

   It is also easy to check that T is at most half as long as F. Append it to itself and check that you can still append more to get F.

   What is your move predicate?

2. A position is a winning position if the player can force a win, no matter what the opponent does. In Prolog, this is very easy to check:

   win(X) :- move(X,Y), not(win(Y)).

   For example,

   win([o,o,o,o,o]).
   true ;
   fail.

   Try out marble lists of length 1 to 10. Which ones are winning positions?