Prolog

History

The existence of a de facto language standard and widely available, efficient implementation was very important for language acceptance (compare with functional languages).

Fifth Generation project in Japan - 1984 - adopted logic programming

currently Quintus is a commercial Prolog vendor

Lots of offshoots of Prolog:

Running Prolog

To run prolog on lynx: (the license doesn't seem to let it run on wolf or grizzly)

Try turning on debugging to get a better feel for the operation of Prolog.

You can also use the clpr system (a constraint logic programming language), which offers most of the features of Prolog plus constraints.

Program Structure

A Prolog program is a collection of facts and rules (like axioms). A query is like a theorm to be proved. two modes: enter assertions; make queries Suppose we have the following Prolog program in a file likes.pl : 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,george_bush). politically_correct(X) :- likes(X,yogurt), likes(X,noam_chomsky). low_life(X) :- likes(X,cheap_cigars). File these in by saying | ?- consult(likes). Make queries: | ?- likes(fred,beer). yes. | ?- likes(fred,X). X = beer | ?- likes(fred,X). X = beer ; X = cheap_cigars ; X = monday_night_football ; no | ?- likes(Y,jogging). Y = sue ; Y = mary ; no | ?- politically_correct(A). A = sue ; no

Key concepts in Prolog

Prolog data types

lists could be represented using structures: cons(4,cons(5,cons(6,nil))) point, line, cons are unevaluated function symbols

vertical bar -- item after that is the remainder of the list

A = [4,5,6], B=[3|A]. /* then B =[3,4,5,6] */ A = [4,5,6], B=[3,A]. /* then B =[3,[4,5,6]] */

Some sample list manipulation programs

append([],Ys,Ys). append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs). | ?- append([1,2],[3,4,5],Q). Q = [1,2,3,4,5] | ?- append([1,2],M,[1,2,3,4,5,6]). M = [3,4,5,6] | ?- append(A,B,[1,2,3]). A = [], B = [1,2,3] ; A = [1], B = [2,3] ; A = [1,2], B = [3] ; A = [1,2,3], B = [] ; no | ?- | ?- append(A,B,C). A = [], B = C = _3278 ; A = [_3443], B = _3278, C = [_3443|B] ; A = [_3443,_3447], B = _3278, C = [_3443,_3447|B] ; A = [_3443,_3447,_3451], B = _3278, C = [_3443,_3447,_3451|B] ; A = [_3443,_3447,_3451,_3455], B = _3278, C = [_3443,_3447,_3451,_3455|B] ; | ?- member(X,[X|Xs]). member(X,[Y|Ys]) :- member(X,Ys). | ?- member(3,[1,2,3,4]). yes | ?- member(X,[1,2,3,4]). X = 1 ; X = 2 ; X = 3 ; X = 4 ; no | ?- member(1,X). X = [1|_3502] ; X = [_3501,1|_3504] ; X = [_3501,_3503,1|_3506] ; X = [_3501,_3503,_3505,1|_3508] ; X = [_3501,_3503,_3505,_3507,1|_3510] ; X = [_3501,_3503,_3505,_3507,_3509,1|_3512]
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=

Prolog warts

Arithmetic

X is 3+4, Y is X*X. (compare with X = 3+4.) factorial(0,1). factorial(N,F) :- N>0, N1 is N-1, factorial(N1,F1), F is N*F1.

Cut

Cut prunes the search tree examples: compile(Source,Code) :- Parse(Source,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.

Negation in Prolog

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

Other Features

assert(X) -- asserts a clause in the database retract(X) -- retracts a clause from the database evaluable predicates: read(X). write(Y). meta-logical predicates: var(X) nonvar(X)

Some Prolog programming techniques

Simple Prolog Meta-Interpreter for Pure Prolog

goal(true). goal(A,B) :- goal(A), goal(B). goal(A) :- clause(A,B), goal(B).

Difference Lists (example of incomplete data structures)

represent a list S as the difference of two lists X and Y
define a new infix operator \ ...
write the difference list as X\Y

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

[1,2,3]\[] [1,2,3,4,5]\[4,5] [1,2,3,4,5,6,7,8]\[4,5,6,7,8] [1,2,3|M]\M Notice that the first 3 examples are all substitution instances of the last one! cheap_append( X\Y , Y\Z , X\Z). example: ?- cheap_append( [1,2,3|M]\M , [8,9,10|N]\N , A\P ) succeeds with A = [1,2,3,8,9,10]\N , P = N ?- cheap_append( [1,2,3|M]\M , [8,9,10|N]\N , A\[] ) succeeds with A = [1,2,3,8,9,10] Example of using difference lists: /* Naive flatten: /* flatten([],[]). flatten([X|Xs],Y) :- flatten(X,XF), flatten(Xs,XsF), append(XF,XsF,Y). flatten(X,[X]). ---------------------------------------- /* Flatten using difference lists: /* /* declare "\" as a new infix operator */ :- op(400,xfx,\). flatten(S,F) :- flatten_dl(S,F\[]). flatten_dl([],X\X). flatten_dl([X|Xs],Y\Z) :- flatten_dl(X,Y\T), flatten_dl(Xs,T\Z). flatten_dl(X,[X|Z]\Z). By using difference lists, we can write an efficient flatten routine (comparable in efficiency to one in an imperative language), while still retaining a declarative programming style.