CSE 341 Lecture Notes - Prolog

Language Metaphors:

Prolog history:

roots in predicate calculus and theorem proving
Alain Colmerauer (Marseilles) invented Prolog in the early 70's
David Warren - University of Edinburgh - implemented compiler for DEC PDP-10

Fifth Generation project in Japan - 1984
Quintus Prolog
lots of offshoots: constraint logic programming: CLP languages, CHIP, Prolog III, Trilogy, HCLP, etc.
concurrent logic programming: FCP, Strand, etc etc.

A Prolog program is a collection of facts and rules (like axioms). A query is in effect a theorem to be proved.

Two modes: enter assertions; make queries

Suppose we have the following Prolog program in a file named "likes":

likes(fred,beer).
likes(fred,cheap_cigars).
likes(fred,monday_night_football).

likes(sue,jogging).     
likes(sue,yogurt).     
likes(sue,bicycling).     
likes(sue,noam_chomsky).

likes(mary,jogging).     
likes(mary,yogurt).     
likes(mary,bicycling).     
likes(mary,newt_gingrich).

health_freak(X) :-
   likes(X,yogurt),
   likes(X,jogging).

left_wing(X) :-
   likes(X,noam_chomsky).

low_life(X) :-
  likes(X,cheap_cigars).

File these in by saying

| ?- consult(likes).
Make queries:
| ?- likes(fred,beer).
(CLP(R)'s silence here indicates "yes".)
| ?- likes(fred,yogurt).
no

| ?- likes(fred,X).
X = beer
However, Fred likes other things besides beer. We can reject an answer by typing a semicolon, and get more by backtracking:
| ?- likes(fred,X).
X = beer ;
X = cheap_cigars ;
X = monday_night_football ;
no

| ?- health_freak(Y).
Y = sue ;
Y = mary ;
no

/* is there anyone who is both left wing and a lowlife (known in our
   database, that is)? */
| ?- left_wing(X), low_life(X).
no

Recursive Rules


prerequisite(cse142,cse143).

prerequisite(cse143,cse321).

prerequisite(cse321,cse322).

prerequisite(cse143,cse341).

prerequisite(cse143,cse378).

prerequisite(cse326,cse401).
prerequisite(cse341,cse401).
prerequisite(cse378,cse401).

prerequisite(cse321,cse403).
prerequisite(cse341,cse403).
prerequisite(cse378,cse403).


take_before(X,Z) :- prerequisite(X,Z).
take_before(X,Z) :- prerequisite(X,Y),
                    take_before(Y,Z).

Key concepts in Prolog:

Prolog data types:

The list notation is just shorthand for a set of structures, where "." plays the role of cons
  .(4, .(5, []))
is the same as [4,5]

point, line, . are unevaluated function symbols


Unification

two terms unify: examples:

fred unifies with fred
X unifies with fred (by substituting fred for X)
X unifies with Y (by substituting Y for X, or substituting 3 for X and 3 for Y)
point(A,10) unifies with point(B,C)
foo(X,X) unifies with foo(Y,3)

When prolog unifies two terms, it picks the most general unification
point(A,A) unifies with point(B,C) by substituting A for B and A for C

Unification algorithm

to unify S and T, Note that if you substitute T for S, the substitution must be carried out throughout the structure.

Nit: the logical definition of unification also includes the "occurs check": a variable is not allowed to unify with a structure containing that variable. For example, X is not allowed to unify with f(X). However, most practical implementations of Prolog skip the occurs check for efficiency.

Unification can also be viewed as constraint solving, where the constraints are limited to equations over Prolog's data structures. Note also that Miranda's type inference mechanism uses unification!


Prolog programs have both a declarative and a procedural meaning: Prolog clauses are either facts and rules.

Declarative meaning

a rule such as
   P :-  Q1, Q2, Q3.
means: if Q1 and Q2 and Q3 are true, then P is true.

a fact such as:
    P.
means P is true.

A goal G is satisfiable if there is a clause C such that

In the declarative meaning of a Prolog program, the order of the clauses, and the order of the goals in the body of a rule, doesn't matter.

another way of describing this:

variables in rules are UNIVERSALLY QUANTIFIED:
  low_life(X) :- likes(X,cheap_cigars).

means for every X,
  if likes(X,cheap_cigars) is true, then low_life(X) is true

variables in goals are EXISTENTIALLY QUANTIFIED:
 ?- likes(fred,X)
means prove that there exists an X such that likes(fred,X)

A goal is satisfiable if it can be proven from the clauses.

Procedural meaning

Prolog has a list of goals G1, ... Gm

If the list is empty, terminate with success
Otherwise look for the first clause in the program whose head matches G1.
If none, terminate with failure.
If yes, replace G1 with the goals in the body of the clause, making the same unifications that were done to make G1 match the head of the clause. Recursively try to satisfy the list of goals. If this fails, look for another clause whose head matches G1.

Notice that for the procedural meaning, the order of clauses in the program, and the order of goals in the body of a rule, affects the execution of the program.


Dangers of infinite search (infinite looping):

the take_before rule was written as:

take_before(X,Z) :- prerequisite(X,Z).
take_before(X,Z) :- prerequisite(X,Y),
                    take_before(Y,Z).


Suppose instead it was written as:
take_before(X,Z) :- take_before(Y,Z),
                    prerequisite(X,Y).

Declaratively this is fine, but procedurally a take_before goal would get stuck in an infinite search.

Some sample list manipulation programs:

/* DEFINITION OF APPEND */
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

/* SAMPLE GOALS */
| ?- append([1,2],[3,4,5],Q).

| ?- append([1,2],M,[1,2,3,4,5,6]).

| ?- append(A,B,[1,2,3]).

| ?- append(A,B,C).

/* DEFINITION OF MEMBER */
member(X,[X|Xs]).
member(X,[Y|Ys]) :- member(X,Ys).


/* SAMPLE GOALS */
| ?- member(3,[1,2,3,4]).

| ?- member(X,[1,2,3,4]).

| ?-  member(1,X).


/* SUBLIST */

sublist(S,Z) :- append(A,S,X), append(X,Y,Z).


/* CLAUSES TO FIND ALL PERMUTATIONS OF A LIST */

permute([],[]).

permute([H|T],L) :-
  permute(T,U),
  insert(H,U,L).

/* insert an element X somewhere in list L */

insert(X,L,[X|L]).

insert(X,[H|T],[H|U]) :-
  insert(X,T,U).

/* inefficient sort */

sort(L,S) :- permute(L,S), sorted(S).

sorted([]).
sorted([X]).
sorted([A,B|R]) :-
  A=<B,
  sorted([B|R]).


Prolog warts:

Arithmetic

In Prolog you have to do arithmetic using the "is" operator. For example:
X is 3+4, Y is X*X.
However, in CLP(R) = works just fine:
X = 3+4, Y = X*X.
Some simple arithmetic examples in CLP(R):
fahrenheit(C,F) :- F = 1.8*C+32.0.

max(X,Y,X) :- X>=Y.
max(X,Y,Y) :- X<Y.

length of a list:

length([],0).
length([_|Xs],N) :- length(Xs,N-1).

Cut

Cut prunes the search tree

examples:

compile(Source,Code) :- 
   lex(Source,Tokens), 
   parse(Tokens,Tree), 
   !, encode(Tree,Code).

member(X,[X|Xs]) :- !.
member(X,[Y|Ys]) :- member(X,Ys).

| ?- member(1,[1,2,3,1]). /* will succeed twice */

but: member(X,[1,2,3]) will only give one answer: X=1.


Using Cut to Define Not

"Not" in Prolog is weird -- it means "I can't prove this" as opposed to "I can prove this is false". It also doesn't work quite right even so if the goal includes unbound variables.

not(X) :- call(X), !, fail.
not(X).


| ?- not(3=4).
yes

| ?- not(3=3).
no

| ?- not(X=3), X=4.
no

| ?- X=4, not(X=3).
yes

Some Prolog Programming Techniques

Difference Lists (example of incomplete data structures)

represent a list S as the *difference* of two lists X and Y

express the difference list as dl(X,Y)

these all represent the list [1,2,3]:

   dl( [1,2,3] , [] )

   dl( [1,2,3,4,5] , [4,5] )

   dl( [1,2,3,4,5,6,7,8] , [4,5,6,7,8] )

   dl( [1,2,3|M] , M )
Notice that the first 3 examples are all substitution instances of the last one!

examples:

cheap_append( dl(X,Y) , dl(Y,Z) , dl(X,Z)).

example:  ?- cheap_append( dl([1,2,3|M],M) , dl([8,9,10|N],N) , dl(A,P) )
succeeds with A = dl([1,2,3,8,9,10],N) , P = N

 ?- cheap_append( dl([1,2,3|M],M) , dl([8,9,10|N],N) , dl(A,[]) )
succeeds with A = [1,2,3,8,9,10]


/* Naive flatten: /*

flatten([],[]).

flatten([X|Xs],Y) :-
   flatten(X,XF),
   flatten(Xs,XsF),
   append(XF,XsF,Y).

flatten(X,[X]).


----------------------------------------
/* Flatten using difference lists: /*


flatten(S,F) :-
  flatten_dl( S , dl(F,[]) ).


flatten_dl( [] , dl(X,X) ).

flatten_dl( [X|Xs] , dl(Y,Z) ) :-
   flatten_dl( X , dl(Y,T) ),
   flatten_dl( Xs , dl(T,Z) ).

flatten_dl( X , dl([X|Z],Z) ).