Prolog - part 2

Backward chaining & resolution principle; equality and arithmetic in Prolog; subgoal ordering; and functions vs. predicates Material adapted from Mark Hills’ Organization of Programming Languages

Lesson plan

• Q&A for homework 2 + lecture outline

• Backward chaining & resolution principle

• ICE - goal resolution

• Equality and arithmetic in Prolog

• Subgoal ordering

• Lists

• Functions vs. predicates

• ICE - Fibonacci series

• Summary

Prolog

Prolog interpreter

• The interpreter works by what is called BACKWARD CHAINING

  • It begins with the thing it is trying to prove and works backwards looking for things that would imply it, until it gets to facts

• It is also possible in theory to work forward from the facts trying to see if any of the things you can prove from them are what you were looking for - that can be very time-consuming

  • Fancier logic languages use both kinds of chaining, with special smarts or hints from the user to bound the searches

Prolog interpreter

• The predicate you ask for is the interpreter’s original GOAL

  • In an attempt to SATISFY that goal, it looks for facts or rules with which the goal can be UNIFIED

    • Unification is a process by which compatible statements are merged

  • Any variables that do not yet have values but which correspond to constants or to variables with values in the other clause get INSTANTIATED with that value

  • Anyplace where uninstantiated variables correspond, those variables are identified with each other, but remain without values

Prolog interpreter

• The interpreter starts at the beginning of your database (this ordering is part of Prolog, NOT of logic programming in general) and looks for something with which to unify the current goal

  • If it finds a fact, great; it succeeds

  • If it finds a rule, it attempts to satisfy the terms in the body of the rule depth first

  • This process is motivated by the RESOLUTION PRINCIPLE, due to Robinson:

    • It says that if C1 and C2 are Horn clauses, where C2 represents a true statement and the head of C2 unifies with one of the terms in the body of C1, then we can replace the term in C1 with the body of C2 to obtain another statement that is true if and only if C1 is true

Prolog interpreter

• When it attempts resolution, the Prolog interpreter pushes the current goal onto a stack, makes the first term in the body the current goal, and goes back to the beginning of the database and starts looking again

• If it gets through the first goal of a body successfully, the interpreter continues with the next one

• If it gets all the way through the body, the goal is satisfied and it backs up a level and proceeds

Prolog interpreter

• If it fails to satisfy the terms in the body of a rule, the interpreter undoes the unification of the left hand side (this includes uninstantiating any variables that were given values as a result of the unification) and keeps looking through the database for something else with which to unify (This process is called BACKTRACKING)

• If the interpreter gets to the end of database without succeeding, it backs out a level (that’s how it might fail to satisfy something in a body) and continues from there

Prolog interpreter

• We can visualize backtracking search as a tree in which the top-level goal is the root and the leaves are facts, as shown in Figure 12.2 from Programming Language Pragmatics, by Michael L. Scott.

⊕
Figure 12.2. Prolog uses backtracking search as a tree, with the top-level goal as the root and the leaves as the facts. In this example, the query ?- path(a, a) will never terminate (the interpreter will never find the trivial branch).

• The children of the root are all the rules and facts with which the goal can unify

• The interpreter does an OR across them: one of them must succeed in order for goal to succeed

• The children of a node in the second level of the tree are the terms in the body of the rule

• The interpreter does an AND across these: all of them must succeed in order for parent to succeed

• The overall search tree then consists of alternating AND and OR levels

Prolog interpreter

• Prolog is NOT purely declarative

  • The ordering of the database and the left-to-right pursuit of sub-goals gives a deterministic imperative semantics to searching and backtracking

  • Changing the order of statements in the database can give you different results

    • It can lead to infinite loops

    • It can certainly result in inefficiency

Prolog interpreter

parent(a,b). % a is the parent of b

parent(a,d).

parent(a,k).

parent(k,l).

parent(k,m).

parent(b,e).

parent(b,f).

parent(f,g).

parent(f,h).

parent(f,i).

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

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

• Then the question

  ?- ancestor(U, h).

  generates the answers

  U = f ;

  U = b ;

  U = a ;

  false.

• The question generates all nodes in the subtree rooted in b

<<trace>>

Prolog interpreter

parent(a,b). % a is the parent of b

parent(a,d).

parent(a,k).

parent(k,l).

parent(k,m).

parent(b,e).

parent(b,f).

parent(f,g).

parent(f,h).

parent(f,i).

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

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

• If we change the order of the two ancestor rules, we get different execution orders:

  ?- ancestor(U, h).

  U = a ;

  U = b ;

  U = f ;

  false.

Prolog interpreter

parent(a,b). % a is the parent of b

parent(a,d).

parent(a,k).

parent(k,l).

parent(k,m).

parent(b,e).

parent(b,f).

parent(f,g).

parent(f,h).

parent(f,i).

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

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

• If we change the order of the subgoals in the compound rule we run into an infinite loop

ICE

How is this resolved?

?- mortal(jane). /* not in database */

Equality in Prolog is defined in terms of “unifiability”

• The goal =(A, B) succeeds if and only if A and B can be unified

For the sake of convenience, the goal may be written as A = B

?- a = a.

true. % constant unifies with itself

?- a = b.

false. % but not with another constant

?- foo(a, b) = foo(a, b).

true. % structures are recursively identical

?- X = a.

X = a. % variable unifies with constant

?- foo(a, b) = foo(X, b).

X = a. % arguments must unify

Equality in Prolog is defined in terms of “unifiability”

• It is possible for two variables to be unified without instantiating them; if we type

?- A = B.

A = B. % response from interpreter

• If, however, we type

?- A = B, A = a, B = Y.

% unifying A and B before binding a to A

% the interpreter will linearize the string of unifications and make it clear that all three variables are equal to a:

A = B, B = Y, Y = a.

Arithmetic via the is keyword

fact(0,1).

fact(N,X) :- M is N-1, fact(M,Y), X is Y * N.

?- fact(5,X).

• Unify fact(5,X) with fact(N,X).

fact(5,X) :- M is 5-1, fact(M,Y), X is Y * 5.

• Next compute M.

fact(5,X) :- 4 is 5-1, fact(4,Y), X is Y * 5.

• Recursive call sets Y to 24.

fact(5,X) :- 4 is 5-1, fact(4,24), X is 24 * 5.

• Compute X

fact(5,120) :- 4 is 5-1, fact(4,24), 120 is 24 * 5.

Subgoal ordering

Order of sub-goals is important! Why does this happen?

badfact(0,1).

badfact(N,X) :- badfact(M,Y), M is N-1, X is Y * N.

?- badfact(5,X).

ERROR: Arguments are not sufficiently instantiated

^ Exception: (8) 0 is _G278-1 ?

badfact(5,X) :- badfact(M,Y), M is 5-1, X is Y * 5.

badfact(5,X) :- badfact(0,1), 0 is 5-1, X is 1 * 5.

%oops

Subgoal ordering

Order of sub-goals is important, as shown in Figure 12.1 from Programming Language Pragmatics, by Michael L. Scott. Why does this happen?

⊕
Figure 12.1. Backtracking search in Prolog. The tree of potential resolutions consists of alternating AND and OR levels. An AND level consists of subgoals from the right-hand side of a rule, all of which must be satisfied. An OR level consists of alternative database clauses whose head will unify with the subgoal above; one of these must be satisfied. The notation _C = _X is meant to indicate that while both C and X are uninstantiated, they have been associated with one another in such a way that if either receives a value in the future it will be shared by both.

badfact(0,1).

badfact(N,X) :- badfact(M,Y), M is N-1, X is Y * N.

?- badfact(5,X).

ERROR: Arguments are not sufficiently instantiated

Exception: (8) 0 is \_G278-1 ?

badfact(5,X) :- badfact(M,Y), M is 5-1, X is Y * 5.

badfact(5,X) :- badfact(0,1), 0 is 5-1, X is 1 * 5.

%oops

Structures and patterns

Lists

Prolog lists are very similar to Python lists

• Empty list: []

• Singleton list: [x]

• List with multiple elements: [x,y,[a,b],c]

• Head and tail representation [H|T]

• With this notation [a, b, c] same as [a | [b, c]], [a, b | [c]], or [a, b, c | []]

Lists

The vertical-bar notation is particularly handy when the tail of the list is a variable:

member(X, [X | _]). % _ is a placeholder for a variable that is not needed anywhere in the clause

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

sorted([]). % empty list is sorted

sorted([_]). % singleton is sorted

sorted([A, B | T]) :- A =< B, sorted([B | T]). % built-in =< predicate operates on numbers

Functions vs. predicates

Prolog resolution does not distinguish between “input” and “output” arguments

append([], A, A).

append([H | T], A, [H | L]) :- append(T, A, L).

?- append([a, b, c], [d, e], L).

L = [a, b, c, d, e].

?- append(X, [d, e], [a, b, c, d, e]).

X = [a, b, c] ;

false.

?- append([a, b, c], Y, [a, b, c, d, e]).

Y = [d, e].

Functions vs. predicates

This example highlights the difference between functions and Prolog predicates:

• Functions have a clear notion of inputs (arguments) and outputs (results)

  • In an imperative or functional language we apply functions to arguments to generate results

• Prolog predicates do not

  • In a logic language we search for values for which a predicate is true

List example: mylength

The length predicate is built in.

mylength([],0).

mylength([H|T],X) :- mylength(T,Y), X is Y + 1.

?- mylength([2,3,4,5],X).

X = 4 ;

No

This example looks like badfact, in that the is clause happens after the recursion. Why is this safe?

List example: sum list

sumlist([],0).`

sumlist([H|T],X) :- sumlist(T,Y), X is Y + H.

?- sumlist([2,3,4,5],X).

X = 14

List example: append

myappend([],X,X).

myappend([H|T],X,[H|Z]) :- myappend(T,X,Z).

?- myappend([2,3,4],[5,6,7],X).

X = [2, 3, 4, 5, 6, 7] ;

No

26 ?- myappend(X,[2,3],[1,2,3,4]).

No

27 ?- myappend(X,[2,3],[1,2,3]).

X = [1] ;

No

List example: reverse

Accumulator recursion works in Prolog, too!

myreverse(X,Y) :- myrevaux(X,Y,[]).

myrevaux([],Y,Y).

myrevaux([HX|TX],Y,Z) :- myrevaux(TX,Y,[HX|Z]).

?- myreverse([2,3,4],Y).

Y = [4, 3, 2]

myreverse([2,3,4],Y) \(\rightarrow\) myrevaux([2,3,4],Y,[])

\(\rightarrow\) myrevaux([3,4],Y,[2])

\(\rightarrow\) myrevaux([4],Y,[3,2])

\(\rightarrow\) myrevaux([],Y,[4,3,2])

\(\rightarrow\) myrevaux([],[4,3,2],[4,3,2])

\(\rightarrow\) myreverse([2,3,4],[4,3,2])

Pairs

• The term socrates is a pattern. But patterns can have structure….

pair((X,Y)).

key((X,Y),X).

value((X,Y),Y).

assoc(X,Y,[H|T]) :- key(H,X), value(H,Y).

assoc(X,Y,[H|T]) :- assoc(X,Y,T).

?- assoc(2,X,[(3,hi),(4,there),(2,guys)]).

X = guys

?- assoc(X,there,[(3,hi),(4,there),(2,guys)]).

X = 4

Activity!

ICE

• Write the Fibonacci predicate. Let \(F_0 = 0\) and \(F_1 = 1\).

• Make sure you can write it the exponential way.

• Can you write it the linear way?

Logic programming in perspective

• In the abstract, logic programming is a very compelling idea: it suggests a model of computing in which we simply list the logical properties of an unknown value, and then the computer figures out how to find it (or tells us it doesn’t exist)

• Unfortunately, reality falls quite a bit short of the vision, for both theoretical and practical reasons

• Horn clauses do not capture all of first-order predicate calculus

• In particular, they cannot be used to express statements whose clausal form includes a disjunction with more than one non-negated term

• Execution order - one must often consider execution order to ensure that a Prolog search will terminate. Even for searches that terminate, naive code can be very inefficient

Summary

• Backward chaining & resolution principle

• Equality and arithmetic in Prolog

• Subgoal ordering

• Lists

• Functions vs. predicates

Models of computing

• Imperative: iteration + side effects

• Logic: resolution of logical statements + unify variables and terms

• Functional: recursion + substitution of parameters into function

  Next time: Haskell programming language, part 1 of 4

Reminders:

• Provide feedback/unofficial course evaluation (any time)

• Submit questions for quiz 3 by Thursday, August 27 at 11:59 PM

  
  Back to course home