| [ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
(Credits: This material comes from Markus Triska and Thorsten Joachims and John Fisher, with extensions by Tim Menzies. We also use material from www.dataminingtools.net. )
The language Prolog is the Fortran of logic programming: it was the first of its kind, it was much criticized, and it is still widely used.
George Santayana: "Those who do not remember the past are condemned to repeat it."
Tim Menzies: "Those who do not study Prolog are condemned to repeat it."
In LISP, everything is a lambda body and computation is evaluation within the environment of the current lambda.
In Smalltalk, everything is an object (even Object) and computation is message sends between objects.
In OCAML, everything is a type and computation is a process of converting between types.
In Prolog, everything is a predicate and computation is a process of recursively matching to predicates (possibly, with side-effects).
While functions map inputs to outputs...
And while functions return some output, predicates only return yes or no. If "yes", then as a side effect, they may add bindings to variables.
Predicates are build from terms:
Terms are are either variable or nonvar. Nonvars are either compound or atomic (and these divide into atoms or numbers).
Term
Variable
NonVar
Compound
Atomic
Atom
Number
Variables are empty slots- boxes, waiting to be filled.
Terms have an functor and an arity. E.g. the following term has a functor/arity of emp/3:
emp(tim,30,male).
Terms contain terms (recursively), one for each arity; e.g.
emp(name(tim), age(30), sex(male))
Here:
Terms with an arity of zero are atoms. For example, in the above, the atoms are:
emp name tim age sex male
The other atomic terms are numbers (integers or floats).
emp(tim, 23, male)
emp/3
tim
23
male
2+3
(+)/2
2
3
(note : some unary and binary functors can be written in a
prefix or infix notation. e.g. 2+3 is shorthand
for +(2,3).)
10-10*3
-/2
10
* / 2
10
3
- x
-/1
x
+ y
+/1
y
age(Dob,Age) :- now(Now), Age is Now - Dob.
:-/2
age/2
A
B
,/2
now/1
C
is/2
B
-/2
C
A
:- now(Now), print(Now))
:-/1
,/2
now/1
A
print/1
B
(Adapted from Robert F. Rossa: rossa [at] csm.astate.edu).
Prolog programs as databases
We show below a Prolog program consisting entirely of simple clauses or facts. This set of facts is a database about a family. Note that all the gender facts are grouped together, then all the father facts, then all the mother facts. Many versions of Prolog demand that similar clauses be grouped together.
/* family.pl - a simple database for a family */ gender(al,male). gender(anne,female). gender(arthur,male). gender(amber,female). gender(boris,male). gender(barbara,female). gender(betty,female). gender(buck,male). gender(carla,female). gender(charles,male). gender(cora,female). gender(cuthbert,male). gender(cecilia,female). gender(calvin,male). father(arthur,buck). father(al,buck). father(amber,buck). father(anne,boris). father(barbara,charles). father(betty,cuthbert). father(boris,charles). father(buck,calvin). mother(al,barbara). mother(anne,betty). mother(arthur,barbara). mother(amber,barbara). mother(boris,carla). mother(barbara,carla). mother(betty,cora). mother(buck,cecilia).
We can load this database into a Prolog interpreter.
swipl -f family.pl
The interpreter waits for queries. Every query must end with a period. When we query the interpreter, it will give us the first answer it finds, based on the facts in the database. If we want more answers, we enter a semicolon. If we don’t want any more answers to that query, we just enter a carriage return. Thus consider the sequence that follows.
?- father(X,Y). X=arthur, Y=buck; X=al, Y=buck; X=amber, Y=buck; X=anne, Y=boris; X=barbara, Y=charles; X=betty, Y=cuthbert; X=boris, Y=charles; X=buck, Y=calvin no ?-
The "no" simply indicates that there were no more answers. Prolog will answer "yes" or "no" depending on the truth or falsehood of a simple query. Thus:
?- mother(al,betty). no ?- mother(al,barbara). yes ?-
We can build more complex queries like the following, to find a grandmother of al.
?- mother(al,X),mother(X,Y). X=barbara, Y=carla yes ?-
By now you have observed that identifiers that start with an upper case letter are variables, and those that start with lower case letters are constants. Rules
We can add some intelligence to our facts by adding a clause that tells how to figure out from the simple clauses whether Y is a parent of X. The rules we add are
parent(X,Y) :- father(X,Y). parent(X,Y) :- mother(X,Y).
The symbol ’:-’ should be read as "if". Now we can query as follows.
?- parent(al,Y). Y=buck; Y=barbara yes ?-
We can now build a rule that uses the parent rules. grandfather(X,Y) :- parent(X,Z),father(Z,Y). and ask questions like
?- grandfather(anne,Y). Y=charles; Y=cuthbert; no ?-
The scope of variables is one clause; there is no such thing as a global variable.
When Prolog tries to answer a query, it goes through a matching process. It tries to match the predicates on the right-hand side of the rule from left to right, binding variables when it finds a match. If a match fails, it may be because of the bindings in matches to the left. In that case, the interpreter backtracks - it returns to the nearest previous binding and tries to find a different match. If that fails, it backtracks some more.
Now we can use the builtin trace predicate to see what happens as one of our rules is matched.
% swipl -f family.pl -g true /Users/timm/svns/wisp/var/timm/10/310/src/prolog/4/a/family.pl compiled 0.00 sec, 4,872 bytes ?- spy(grandfather). % Spy point on grandfather/2 true. [debug] ?- grandfather(al,X). Call: (7) grandfather(al, _G313) ? creep Call: (8) parent(al, _L175) ? creep Call: (9) father(al, _L175) ? creep Exit: (9) father(al, buck) ? creep Exit: (8) parent(al, buck) ? creep Call: (8) father(buck, _G313) ? creep Exit: (8) father(buck, calvin) ? creep Exit: (7) grandfather(al, calvin) ? creep X = calvin ; Redo: (8) parent(al, _L175) ? creep Call: (9) mother(al, _L175) ? creep Exit: (9) mother(al, barbara) ? creep Exit: (8) parent(al, barbara) ? creep Call: (8) father(barbara, _G313) ? creep Exit: (8) father(barbara, charles) ? creep Exit: (7) grandfather(al, charles) ? creep X = charles. [debug] ?-
Note that rules in the database are tried in the order they appear in the database.
We can make Prolog print out all the answers to a question by deliberately making it fail, using the fail predicate.
?- grandfather(X,Y),write('X='),write(X),write(', Y='),write(Y),nl,fail.
X=arthur, Y=calvin
X=al, Y=calvin
X=amber, Y=calvin
X=anne, Y=charles
X=al, Y=charles
X=anne, Y=cuthbert
X=arthur, Y=charles
X=amber, Y=charles
fail
?-
It is important to realize that in a goal ?-not(g), if g has variables, and some instance of these variables lead to satisfaction of g, then ?-not(g) fails. For example, consider the following ’bachelor program:
bachelor(P) :- male(P), not(married(P)). male(henry). male(tom). married(tom).
Then
?- bachelor(henry). yes ?- bachelor(tom). no ?- bachelor(Who). Who= henry ; no ?- not(married(Who)). no.
The first three responses are correct and as expected.
The answer to
the fourth query might have been unexpected at first.
But consider that
the goal ?-not(married(Who)) fails because for the
variable binding
Who=tom, married(Who) succeeds, and so the negative
goal fails. Thus,
negative goals ?-not(g) with variables cannot be
expected to produce
bindings of the variables for which the goal g fails.
Prolog lists have heads and tails (think "car" and "cdr").
[a, b, c]
. / 2
a
. / 2
b
. / 2
c
[]
So we can write a list member predicate as follows:
member(A, [A|_]).
member(A, [_|B]) :-
member(A, B).
So, of course,...
?- member(a,[c,b,a]). true
But Prolog can backtrack to find all repeated members of a list:
?- member(a,[c,a,b,a]). true ; true
Also, we can find all members of a list:
?- member(X,[a,b,c]). X = a; X = b; X = c
Also, Prolog is a relational language. Variables are not inputs and outputs but concepts woven together by constraints. Also, we only need to partially specify the I/O to query those constraints:
?- member(name=What, [age=20,shoesize=12,name=tim]). What = tim .
(If this is causing stress, just chant to yourself: in Prolog, we don’t code; rather, we draw the shape of the solution.)
This can get really funky. Here’s the standard definition of how to append two lists:
append([], A, A).
append([A|B], C, [A|D]) :-
append(B, C, D).
Which works in the expected way:
@verbatim
?- append([a,b,c],[d,e,f],Out).
Out = [a, b, c, d, e, f].
But any of these arguments can be left unspecified to achieve neat results:
; find the third thing in a list ?- append([ _, _, Third], _, [alice,john,mike,tim,veronica,wendy]). Third = mike ; find the list before "tim" ?- append(Before, [tim | _], [alice,john,mike,tim,veronica,wendy]). Before = [alice, john, mike] ; find the list after "tim" ?- append(_, [tim | After], [alice,john,mike,tim,veronica,wendy]). After = [veronica, wendy]
You can even write "member" using "append":
member1(X,L) :- append(_,[X|_],L). ?- member1(a,[b,c,a]). true . ?- member1(X,[b,c,a]). X = b ; X = c ; X = a ; fail.
Prolog has a shorthand for writing grammar rules:
sentence --> nominal_phrase, verbal_phrase. verbal_phrase --> modlist,verb. nominal_phrase --> article, noun. article --> [the]. noun --> [dog]. verb --> [runs]. verb --> [barks]. modlist --> []. modlist --> [sadly], modlist.
(Note that modlist is zero or more "sadly"s.).
If we load this into PROLOG, we get
swipl -f english.pl ?- listing(sentence). sentence(A, C) :- nominal_phrase(A, B), verbal_phrase(B, C). true. ?- listing(verb). verb([runs|A], A). verb([barks|A], A). true. ?-
That is, PROLOG interprets grammars as rules. Terminals (like runs) are assumed to be members of a list.
We can ask PROLOG now, what sentences are valid in this grammar:
?- sentence(X,[]). X = [the, dog, runs] ; X = [the, dog, barks]; no ?-
We can also ask, is a sentence valid:
?- sentence([the,dog,runs],X). X = [] . ?- sentence([the,dog,sadly,sadly,sadly,runs],X). X = [] . ?- sentence([the,dog,flies],X). false. ?-
Informally, an interpreter is a program that evaluates programs. An interpreter for a language similar or identical to its own implementation language is called meta-interpreter (MI). Prolog is well-suited for writing MIs: Prolog programs can be naturally represented as Prolog terms and are easily inspected and manipulated using built-in mechanisms.
Consider a Prolog program:
natnum1(0).
natnum1(s(X)) :-
natnum1(X).
Prolog can evaluate Prolog code dynamically:
?- Goal = natnum1(X), Goal.
Goal = natnum1(0)
X = 0 ;
Goal = natnum1(s(0))
X = s(0)
Yes
You can make the call explicit using the built-in call/1 predicate, yielding the equivalent query "?- Goal = natnum1(X), call(Goal).". The call/n (n > 1) family of predicates lets you append additional arguments to Goal before it is called.
Note that The definition of natnum1/1 consists of two clauses, the first of which degenerated into a fact that is implicitly treated as if it were stated as
natnum1(0) :- true.
The Prolog built-in clause/2 allows inspection of the predicate’s definition:
?- clause(natnum1(Z), Body). Z = 0 Body = true ; Z = s(_G254) Body = natnum1(_G254) ; No
The two solutions found on backtracking correspond to the two clauses of the predicate’s definition.
Another example:
complicated_clause(A) :-
goal1(A),
goal2(A),
goal3(A).
?- clause(complicated_clause(Z), Body).
Z = _G187
Body = goal1(_G187), goal2(_G187), goal3(_G187) ;
No
The body of complicated_clause/1 is represented by a compound term with functor "," and arity 2, whose arguments are either goals or compound terms of the same structure.
We can thus define an meta-interpreter for pure Prolog programs:
prolog(true).
prolog((A,B)) :-
prolog(A),
prolog(B).
prolog(Goal) :-
Goal \= true,
Goal \= (_,_),
clause(Goal, Body),
prolog(Body).
This is often called the vanilla Prolog meta-interpreter because there’s nothing special to it. They serve as skeletons for extensions.
We can use this MI to run our example program:
?- prolog(natnum1(X)). X = 0 ; X = s(0) ; X = s(s(0)) Yes
We had to guard the third clause from matching true/0 or conjunctions to prevent run-time errors resulting from calling clause/2 with these arguments. This is ugly.
Another problem with the above is that, at least in SWI Prolog, calling clause/2 on certain builit-in predictess (like the maths predicate is/2, or the true predicate true/0) causes a crash.
To fix both these problems, we need to look before we leap.
prolog(Goal) :- once(look(Goal,How)), leap(How). look(true, skip ). look((X,Y), and(X,Y)) look(X, call(X) ) :- predicate_property(X,built_in). look(X, do(X) ). leap(skip ). leap(and(X,Y)) :- prolog(X), prolog(Y). leap(call(X) ) :- call(X). leap(do(X) ) :- clause(X,Body), prolog(Body).
The once/1 predicate returns the top-most result and never backtracks to anything else.
This works, in the expected way:
demo :-
s(Sentence1,[]),
prolog(s(Sentence2,[])),
format('1 : ~p\n2 : ~p\n',[Sentence1,Sentence2]).
1 : [the, woman, shoots, the, woman]
2 : [the, woman, shoots, the, woman]
Ok, so what? All we’ve achieved is to write an interpreter of Prolog that does the same thing as raw Prolog. Well, the power of this method is that we can change how Prolog executes. For example, suppose we wanted to return random sentences from our grammar? First, we need something that can randomly shuffle the contents of a list. And we have that (see shuffle/2, above).
Next, we need something that can find all the different ways we can prove a clause, and then jumble up that order:
clauses(Head,Bodies) :- findall(Head/Body, clause(Head,Body), Bodies0), shuffle(Bodies0,Bodies).
With all that in place, we only need adjust the intepreter such that when we interpret a clause body, we use a randomly selected body. We call that interpreter "golorp" since it rearranges things into a random order:
golorp(Goal) :- once(look(Goal,How)), leap(How). look(true, skip). look((X,Y), and(X,Y)). look(X, call(X)) :- predicate_property(X,built_in). look(X, do(X,L)) :- clauses(X,L). leap(skip). leap(and(X,Y)) :- golorp(X), golorp(Y). leap(call(X)) :- call(X). leap(do(X,L)) :- member(X/Body,L), golorp(Body).
Now, when we run the demo code, we get as many random sentences as we like:
demo :- forall(between(1,10,_), demo1).
demo1 :-
s(Sentence1,[]),
golorp(s(Sentence2,[])),
format('\n1 : ~p\n2 : ~p\n',[Sentence1,Sentence2]).
% :- demo.
1 : [the, woman, shoots, the, woman]
2 : [the, woman, shoots]
1 : [the, woman, shoots, the, woman]
2 : [she, shoots, him]
1 : [the, woman, shoots, the, woman]
2 : [she, shoots]
1 : [the, woman, shoots, the, woman]
2 : [she, shoots]
1 : [the, woman, shoots, the, woman]
2 : [he, shoots, the, man]
1 : [the, woman, shoots, the, woman]
2 : [he, shoots]
1 : [the, woman, shoots, the, woman]
2 : [she, shoots, her]
1 : [the, woman, shoots, the, woman]
2 : [he, shoots, the, woman]
1 : [the, woman, shoots, the, woman]
2 : [the, man, shoots, a, man]
1 : [the, woman, shoots, the, woman]
2 : [the, woman, shoots]
Note the power of knowledge-based programming. We did not change the structures we were interpreting (the natural language grammar). Rather, we only change the interpreter.
Here is an embedded ALGOL-like language in Prolog. By Maud Dib.
Managing state:
change_member(_, N, [], [N]). change_member(O, N, [O|XS], [N|XS]). change_member(O, N, [X|XS], [X|YS]) :- change_member(O, N, XS, YS). Define the language: @verbatim :- op(900, xfy, :=). :- op(100, fx, [if, then, else]). :- op(125, fx, [while, return]). :- op(125, yfx, do).
Running a block:
run({Block},EnvI, O, Ret) :-
run(Block, EnvI, O, Ret).
Do things, return the result of doing the last one:
@verbatim
run((First; Second), EnvI, O, Ret) :-
run(First, EnvI, M, _),
run(Second, M, O, Ret).
Do assignment.
@verbatim
run(Place := Expr, EnvI, O, void) :-
eval(Expr, Value, EnvI),
change_member(Place = _, Place = Value, EnvI, O), !.
Do if-then-else..
run(if(Cond) then {This} else {That}, EnvI, O, Ret) :-
eval(Cond, Value, EnvI),
( Value = true -> Body = This ; Body = That ),
run(Body, EnvI, O, Ret).
Do while.
run(while(Cond) do {Body}, EnvI, O, Ret) :-
eval(Cond, Value, EnvI),
( Value = true ->
run(Body, EnvI, M, _),
run(while(Cond) do {Body}, M, O, Ret)
; O = EnvI, Ret = void
).
Do a return value.
run(return Value, EnvI, O, Ret) :- eval(Value, Ret, EnvI), O = EnvI.
Evaluate stuff
eval(Var, Val, Env) :- member(Var = Val, Env), !. eval(Num, Num, _ ) :- number(Num), !. eval(true, true, _ ). eval(false, false, _ ). eval(X + Y, Z, Env) :- eval(X, XV, Env), eval(Y, YV, Env), Z is XV + YV. eval(X - Y, Z, Env) :- eval(X, XV, Env), eval(Y, YV, Env), Z is XV - YV. eval(X * Y, Z, Env) :- eval(X, XV, Env), eval(Y, YV, Env), Z is XV * YV. eval(X / Y, Z, Env) :- eval(X, XV, Env), eval(Y, YV, Env), Z is truncate(XV / YV).
eval(X = Y, B, Env) :- eval(X, XV, Env), eval(Y, YV, Env), ( XV = YV -> B = true ; B = false ). eval(X < Y, B, Env) :- eval(X, XV, Env), eval(Y, YV, Env), ( XV < YV -> B = true ; B = false ). eval(X > Y, B, Env) :- eval(X, XV, Env), eval(Y, YV, Env), ( XV > YV -> B = true ; B = false ). eval(not(P), B, Env) :- eval(P, PV, Env), ( PV = true -> B = false ; B = true ).
factorial
factorial(N, {i := 1;
n := N;
while(n > 0) do {
i := i * n;
n := n - 1
};
return i}).
%% ?- factorial(5, P), run(P, [], _, X).
%% X = 120
fibonacci
fibonacci(F, {i := 1; a := 1; b := 1;
while(not(i = F)) do {
a := a + b;
b := a - b;
i := i + 1
};
return b}).
%% ?- fibonacci(7, P), run(P, [], _, X).
%% X = 13
pow2
pow2(N, {i := N;
n := 1;
while(not(i = 0)) do {
i := i - 1;
n := n * 2
};
return n}).
%% ?- pow2(8, P), run(P, [], _, X).
%% X = 256
gcd
gcd(X, Y,
{x := X;
y := Y;
while(not(x = 0)) do {
if(x < y) then {
y := y - x
}
else {
x := x - y
}
};
return y}).
%% ?- A is 2*2*5*7*13, B is 5*13*7*7, gcd(A, B, P), run(P, [], _, X).
%% A = 1820,
%% B = 3185,
%% X = 455
isqrt
isqrt(N, {q := N; p := (q + N / q) / 2;
while(q > p) do {
q := p;
p := (q + N / q) / 2
};
return p}).
%% ?- isqrt(81, P), run(P, [], _, X).
| [ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This document was generated on April 19, 2011 using texi2html 5.0.