(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. )
Prolog is the Fortran of logic programming: it was the first of its kind, it was much criticised, 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."
Everything is a term. 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 maleThe other atomic terms are numbers (integers or floats).
Think of them as tree structures:
emp(tim, 23, male)
emp(tim, 23, male)
emp/3
tim
23
male
2+3
2+3
(+)/2
2
3
10-10*3
10-10*3
-/2
10
* / 2
10
3
- x
-x
-/1
x
+ y
+y
+/1
y
age(Dob,Age) :- now(Now), Age is Now - Dob.
age(A, B):-now(C), B is C-A
:-/2
age/2
A
B
,/2
now/1
C
is/2
B
-/2
C
A
:- now(Now), print(Now))
:-now(A), print(B)
:-/1
,/2
now/1
A
print/1
B
Terms are used to build predicates.
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.
(Adapted from Robert F. Rossa: rossa@csm.astate.edu).
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.
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 bondings 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
?-
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. ?-
Condiser the following Prolog program.
part(a). part(b). part(c). red(a). black(b). color(P,red) :- red(P),!. color(P,black) :- black(P),!. color(P,unknown).
The cut predicate "!" prunes away all the choice points active at the time of reaching that predicate. The cut goal succeeds whenever it is the current goal, AND the derivation tree is trimmed of all other choices on the way back to and including the point in the derivation tree where the cut was introduced into the sequence of goals.
(So it is called "cut" since it prunes away sections of the possible proof tree.) The intention is to determine a color for a part based upon specific stored information, or else conclude that the color is 'unknown' otherwise. A derivation tree for goal ?- color(a,C) is
which corresponds with
?- color(a,C). C = redand a derivation tree for goal ?- color(c,C) is
which corresponds with
?- color(c,C). C = unknown
The Prolog cut is a procedural device for controlling goal satisfaction. The use of cut affects the meanings of programs. For example, in the 'color' program, the following program clause tree says that 'color(a,unknown)' should be a consequence of the program:
The cut in the program enables Prolog to "avoid" this answer. It would be difficult to modify the program clause tree definition (for program consequences) to reflect the procedural meaning of cut.
Cut is evil, sometimes a ncesseary evil, but it is still evil. It makes it harder to reason about a program. One way to reduce using it is the "once" predicate that finds the first solution, then stops.
once(X) :- call(X), !.
We will use "once", below.
The negation-as-failure 'not' predicate could be defined in prolog as follows:
not(P) :- call(P), !, fail. not(_).
The goal ?-call(P) forces an attempt to satisfy the goal P. Most Prolog interpreters have a built-in version of this predicate. Quintus, SWI, and many other prologs use '\+' rather than 'not'.
Another way one can write the 'not' definition is using the Prolog implication operator '->' :
not(P) :- (call(P) -> fail ; true)
The body can be read "if call(P) succeeds (i.e., if P succeeds as a goal) then fail, otherwise succeed". The semicolon ';' appearing here has the meaning of exclusive logical-or.
There will be numerous uses of 'not' in subsequent programs in the chapter.
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.
In procedural systems, you write lottsa forloops.
In logic programming, you write a predicate that returns ONE solution, then call that in a special way to get ALL the solutions.
findall/3 succeeds if List can be unified with the list of all instances of Instance making Goal provable. For example, findall(X, a(X), [1, 2, 3]) is true if the logicbase contains the following clauses for a:
a(1). a(2). a(3).If Goal cannot be proved for any values of Instance, then List is unified with the empty list []. findall/3 is generally used to generate lists from logicbase entries, so for example it might be used as follows (with the logicbase shown above):
?- findall(X, a(X), L). L = [1, 2, 3]
Consider these facts in the logicbase:
fact(bird, duck). fact(sound, quack). fact(color, white).The terms in the list take the form of the first argument, as in this example:
?- findall(Name:Value, fact(Name, Value), List). List = [bird:duck, sound:quack, color:white]
Returning to the above example:
finds(A, B, D) :-
findall(C, find(A, 0, B, C), D).
?- demo1(X), finds(numberp,X,L).
X = emp(tim, 23, male),
L = [23] ;
X = [a, b, c],
L = [] ;
X = 2+3,
L = [2, 3] ;
X = 10-10*3,
L = [10, 10, 3] ;
X = -x,
L = [] ;
X = +y,
L = [] ;
X = (age(_G284, _G285):-now(_G290), _G285 is _G290-_G284),
L = [] ;
X = (:-now(_G286), print(_G286)),
L = [].
For the geeks amongst you, see also bagof/3 and setof/3: http://www.amzi.com/manuals/amzi7/pro/ref_execution.htm.
Prolog lists have heads and tails (think "car" and "cdr").
[a, b, c]
[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 bactrack 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:
?- 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.
Before we look at more PROLOG list processing, lets recall the general structure of any recursive traversal:
(defun addr (l)
(cond ((null l) 0) ; termination
((numberp x) x) ; base case
(t (let ((sum 0))
(dolist (one x sum)
(incf sum (addr one)) ; recursive case
)))))
Prolog version
addr(L,Out) :- % helper function. initialize a counter to zero addr(L,0,Out). addr([],Out,Out). % base case: empty list so return the accumulator addr([H|T],In,Out) :- addr(H,In,Tmp), % recurse on the head addr(T,Tmp,Out). % recurse on the tail addr(X,In,Out) :- % base case number(X), Out is In + X.
Note the is/2 predicate: used for maths. E.g.
?- X is 1 + 2 / 3 * 4. X = 3.6667 ?- X is random(3) X = 2 . % some random number from 0 .. (3-1) ?- 0 is 22 mod 2. true. % standard test for even numbers
Demo
?- addr([1,[2,[3,4],5],6,7],X). X = 28 .
More complex example: extracting any random item from a list.
oneLess(L,One,Less) :-
length(L,N0), % e.g. ?- length([a,b,c],N). N = 3.
N is random(N0), % some random number 0 ... N0 - 1
oneLess1(N,L,One,Less). % split the list on item N
oneLess1(0, [One|Less],One,Less). % termination
oneLess1(N0, [H|T],One, [H|Rest]) :- % base case handled in the head
N0 > 0,
N is N0 - 1,
oneLess1(N,T,One,Rest). % recursive case
oneLess/1 is like a rocket countdown. Each recursive call decrements "N" by one. At zero, we stop to form "One" and "Less" from the head and tail of the list.
So now we can shuffle a list in the usual way.
shuffle([],[]). % termination
shuffle([H|T], [One|Rest]) :-
oneLess([H|T], One, Less), % base case: head of list is anything
shuffle(Less,Rest). % recusive case: shuffle what's left
For example, we can can rearrange "prolog" into another random order as follows:
shuffle("prolog",X), format('~s\n',[X]).
X = golorp
(Exercise for the reader: what does the above say about how Prolog stores double quoted strings?).
Remember that name: "golorp". We'll use it later.
Prolog is a natural tool for recursive descent parsing. Every term is a nested set of terms. Remember these:
demo1(emp(tim,23,male)). demo1([a,b,c]). demo1(2+3). demo1(10 - 10 * 3). demo1(- x). demo1(+ y). demo1((age(Dob,Age) :- now(Now), Age is Now - Dob)). demo1((:- now(Now), print(Now))).
How can we run over these to find (e.g.) all the numbers found in the above terms? Prolog has a nifty predicate =.. that is hammer that breaks up terms. E.g.
?- emp(tim,23,male) =.. L. L = [emp,tim,23,male]. ?- 10 - 10 * 3 =.. L. L = [-, 10, 10*3].
So, to recurse over any Prolog term, just convert all terms to lists using =.. and write a recursive list traversal. That is, we convert the problem of recursively parsing terms (hard!) to one of recursively parsing lists (easy!).
find(What,N,Term,Found) :-
call(What,N,Term,Found).
find(What,N,Term,Found) :-
nonvar(Term),
Term =.. [H1,H2|T], % lists must be at least two items long.
member(Next,[H1,H2|T]),
find(What,N+1,Next,Found).
(Exercise for the reader: why do we only recurse on lists with at least two items?)
There are a few tricks in the above. The call/4 command performs double duty:
For example, here's a predicate that checks for numbers and, if they exist, just returns them unmodified:
numberp(_,N,N) :- number(N).
Demo:
?- demo1(X),find(numberp,0,X,Y). X = emp(tim, 23, male), Y = 23 ; X = 2+3, Y = 2 ; X = 2+3, Y = 3 ; X = 10-10*3, Y = 10 ; X = 10-10*3, Y = 10 ; X = 10-10*3, Y = 3 ; fail.
And, of course, we could modify the stuff we find:
mult(M,_,N,NtimesM) :- number(N), NtimesM is M * N. ?- demo1(X),find(mult(10),0,X,Y). X = emp(tim, 23, male), Y = 230 ; X = 2+3, Y = 20 ; X = 2+3, Y = 30 ; X = 10-10*3, Y = 100 ; X = 10-10*3, Y = 100 ; X = 10-10*3, Y = 30 ; fail
We could use this to print all the contents:
blurt(N,Term,Term) :-
tab(4*N),
numbervars(Term,1,_),
print(Term),nl.
?- demo1(X),write('----------------------------\n'),
find(blurt,0,X,_),fail.
----------------------------
emp(tim, 23, male)
emp
tim
23
male
----------------------------
[a, b, c]
.
a
[b, c]
.
b
[c]
.
c
[]
----------------------------
2+3
+
2
3
----------------------------
10-10*3
-
10
10*3
*
10
3
----------------------------
-x
-
x
----------------------------
+y
+
y
----------------------------
age(B, C):-now(D), C is D-B
:-
age(B, C)
age
B
B
now(B), C is B-D
,
now(B)
now
B
B is C-D
is
B
B-C
-
B
B
----------------------------
:-now(B), print(B)
:-
now(B), print(B)
,
now(B)
now
B
print(B)
print
B
fail.
Now just pause here and think: how would we do this is a standard parsing paradigm? Scanner, lexical analysis, tree traversal, etc etc etc. You gotta say, this is all pretty succinct.
How would we find all the LHS symbols in the following grammar?
sentence --> nounphrase,verbphrase. nounphrase --> [the, boy]. nounphrase --> [the,girl]. verbphrase --> verb,modlist,adverb. verb --> [runs]. verb --> [walks]. modlist --> []. modlist --> [very],modlist. adverb --> [quickly]. adverb --> [slowly].
One methd, which is WRONG is to use clause to walk over all the rules reachable from "sentence", and print the functor of their heads. This crashes, for interesting reasons:
lhs(N,X,Lhs) :-
nonvar(X),
mine(X,_,Body),
lhs1(N,X,Body,Lhs).
mine(X,F,Body) :-
not(builtIn(X)),
clause(X,Body),
X =.. [F|_].
builtIn(X) :-
predicate_property(X,built_in).
lhs1(_,Head,_,Lhs) :-
Head =.. [Lhs|_].
lhs1(N,_,Body,Lhs) :- % recursive call to fund
find(lhs,N+1,Body,Lhs).
?- find(lhs,0,sentence(_,[]),X).
X = sentence ;
X = nounphrase ;
X = nounphrase ;
X = verbphrase ;
X = verb ;
X = verb ;
X = modlist ;
X = modlist ;
X = modlist ;
X = modlist ;
X = modlist ;
X = modlist ;
X = modlist ;
X = modlist ;
X = modlist ;
X = modlist
See the problem? The Modlist rule references itself so the code loops forever.
The solution is two-fold:
sentence --> nounphrase,verbphrase.
nounphrase --> [the, boy]
| [the,girl].
verbphrase --> verb,modlist,adverb.
verb --> [runs]
| [walks].
modlist --> []
| [very],modlist.
adverb --> [quickly]
| [slowly].
find(What,N,Term,W0,W,Found) :-
call(What,N,Term,W0,W,Found).
find(What,N,Term,W0,W,Found) :-
nonvar(Term),
Term =.. [H1,H2|T],
member(Next,[H1,H2|T]),
find(What,N+1,Next,W0,W,Found).
lhs(N,X,W0,W,Lhs) :-
nonvar(X),
mine(X,Functor, Body),
not(member(Functor,W0)),
lhs1(N,X,Body,[Functor|W0],W,Lhs).
lhs1(_,Head,_,W,W,Lhs) :- Head =.. [Lhs|_].
lhs1(N,_,Body,W0,W,Lhs) :- find(lhs,N+1,Body,W0,W,Lhs).
The above machinery lets us do the obvious thing:
finds(What,N,Term,W,Founds) :-
findall(Found,
find(What,N,Term,W,_,Found),
Founds).
?- finds(lhs,0,sentence(_,[]),[],F).
F = [sentence, nounphrase, verbphrase, verb, modlist, adverb].
What is wrong with this grammar?
s --> np, vp. np --> det, n. np --> pro. vp --> v, np. vp --> v. det --> [the]. det --> [a]. n --> [woman]. n --> [man]. v --> [shoots]. pro --> [he]. pro --> [she]. pro --> [him]. pro --> [her].
Seems to work ok...
?- s([she,shoots,him],[ ]). yes ?- s([a,woman,shoots,him],[ ]). yes
But these sentences are odd...
?- s([a,woman,shoots,he],[ ]). yes ?- s([her,shoots,a,man],[ ]). yes s([her,shoots,she],[ ]). yes
The DCG ignores some basic facts about English
It is obvious what we need to do:
How do we do this? Version 1 (verbose, naive):
s --> np_subject, vp. np_subject --> det, n. np_object --> det, n. np_subject --> pro_subject. np_object --> pro_object. vp --> v, np_object. vp --> v. det --> [the]. det --> [a]. n --> [woman]. n --> [man]. v --> [shoots]. pro_subject --> [he]. pro_subject --> [she]. pro_object --> [him]. pro_object --> [her].
Nice way using extra arguments:
s --> np(subject), vp. np(_) --> det, n. np(X) --> pro(X). vp --> v, np(object). vp --> v. det --> [the]. det --> [a]. n --> [woman]. n --> [man]. v --> [shoots]. pro(subject) --> [he]. pro(subject) --> [she]. pro(object) --> [him]. pro(object) --> [her].
Better:
?- s([she,shoots,him],[ ]). yes ?- s([she,shoots,he],[ ]). no ?-
What is really going on? Recall that the rule:
s --> np,vp.is really syntactic sugar for:
s(A,B):- np(A,C), vp(C,B).The rule
s --> np(subject),vp.translates into:
s(A,B):- np(subject,A,C), vp(C,B).so, in effect, we have added a guard to the computation.
It turns out that tree-traversal and computation are closely linked. E.g. descending into a tree based on a certain symbol is the same a conditional block with a guard.
PROLOG adds a {X} construct to its grammar rules that let you do primitive computations.
number(0) --> [zero].
number(N) --> digit(H), [hundred],
and_tens(T), {N is H * 100 + T}.
number(N) --> sub_tens(N).
and_tens(0) --> [].
and_tens(N) --> [and], sub_tens(N).
sub_tens(N) --> digit(N).
sub_tens(N) --> teen(N).
sub_tens(N) --> tens(T), and_digit(D), {N is T + D}.
and_digit(0) --> [].
and_digit(N) --> digit(N).
digit(1) --> [one]. teen(10) --> [ten].
digit(2) --> [two]. teen(11) --> [eleven].
digit(3) --> [three]. teen(12) --> [twelve].
digit(4) --> [four]. teen(13) --> [thirteen].
digit(5) --> [five]. teen(14) --> [fourteen].
digit(6) --> [six]. teen(15) --> [fifteen].
digit(7) --> [seven]. teen(16) --> [sixteen].
digit(8) --> [eight]. teen(17) --> [seventeen].
digit(9) --> [nine]. teen(18) --> [eighteen].
teen(19) --> [nineteen].
tens(20) --> [twenty].
tens(30) --> [thirty].
tens(40) --> [forty].
tens(50) --> [fifty].
tens(60) --> [sixty].
tens(70) --> [seventy].
tens(80) --> [eighty].
tens(90) --> [ninety].
The associated program now responds to queries of the following type:
[user] ?- number(Value, [ two, hundred, and, twenty, three ], []). Value = 223 yes
Besides performing this syntactical analysis and calculating the value, the program is also capable of providing an appropriate verbal expression for a given value (synthesis).
[user] ?- number(101, X, []). X = [one,hundred,and,one]
Prolog has four database manipulation commands:
Suppose we now give this command:
?- assert(happy(mia)).It succeeds (assert commands always succeed). If we now give the command:
?- listing(happy).
we get the listing:
happy(mia).
That is, the database contains the fact we asserted. Suppose we then made four more assert commands:
?- assert(happy(vincent)). ?- assert(happy(marcellus)). ?- assert(happy(butch)). ?- assert(happy(vincent)).Suppose we then ask for a listing:
?- listing(happy). happy(mia). happy(vincent). happy(marcellus). happy(butch). happy(vincent). yes
So far, we have only asserted facts into the database, but we can assert new rules as well. Suppose we want to assert the rule that everyone who is happy is naive. That is, suppose we want to assert that:
naive(X) :- happy(X).
We can do this as follows:
?- assert( (naive(X) :- happy(X)) ).
To remove all of our assertions we can use a variable:
retract(happy(X)). X = mia ; X = butch ; X = vincent ; No
If we want more control over where the asserted material is placed, there are two variants of assert, namely:
For example, suppose we start with an empty database, and then we give the following command:
assert( p(b) ), assertz( p(c) ), asserta( p(a) ).
Then a listing(p) reveals that we now have the following database:
p(a). p(b). p(c).
Like cuts, assert is evil. Try to avoid using them. Having said that, sometimes evil is necessary. For example, here is the standard definition of findall/3:
findall( X, Goal, Xlist) :-
call( Goal), % Find a solution
assertz( queue(X) ), % Assert it
fail; % Try to find more solutions
assertz( queue(bottom) ), % Mark end of solutions
collect( Xlist). % Collect the solutions
collect( L) :-
retract( queue(X) ), !, % Retract next solution
( X == bottom, !, L = [] % End of solutions?
;
L = [X | Rest], collect( Rest) ). % Otherwise collect the rest
(If you do not understand this code, that is because of the evils of "cut".)
For example, and this example comes from above, suppose we have these facts for "a":
a(1). a(3). a(2).
Then
:- findall(X,a(X),L). L= [1,3,2].
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.
Finally, here is a larger version of the above system that handles some other cases such as not/2 and disjunctions. It also complains if we try to prove an unbound goal (which is an error in Prolog):
% golorp.pl
golorp(X) :- once(look(X,Y)), leap(Y).
look(X, barph(var)) :- var(X).
look(true, skip).
look((X;Y), or(L)) :- or2List((X;Y),L0), shuffle(L0,L).
look((X,Y), and(X,Y)).
look(X, do(X)) :- predicate_property(X,built_in).
look(\+ X, not(X)).
look(X, anybody(X,L)) :- clauses(X,L).
leap(skip).
leap(barph(Why)) :- format('% ERROR: ~p.~n',Why),fail.
leap(do(X)) :- call(X).
leap(and(X,Y)) :- golorp(X), golorp(Y).
leap(not(X)) :- \+ golorp(X).
leap(or(L)) :- member(X,L), golorp(X).
leap(anybody(X,L)) :- member(X/Body,L), golorp(Body).
or2List((X;Y),[X|Rest]) :- !,or2List(Y,Rest).
or2List(Y, [Y]).
We execute it on the following grammar:
% english.pl sentence --> nounphrase,verbphrase. nounphrase --> [the, boy]. nounphrase --> [the,girl]. verbphrase --> verb,modlist,adverb. verb --> [runs]. verb --> [walks]. modlist --> []. modlist --> [very],modlist. adverb --> [quickly]. adverb --> [slowly].
And, here is our example:
demo :- forall(between(1,10,_),demo1).
demo1 :-
sentence(Sentence1,[]),
golorp(sentence(Sentence2,[])),
format('\n1 : ~p\n2 : ~p\n',[Sentence1,Sentence2]).
Which produces this output:
% :- [english,golorp]. % :- demo. 1 : [the, boy, runs, quickly] 2 : [the, boy, walks, very, very, very, very, very, very, slowly] 1 : [the, boy, runs, quickly] 2 : [the, boy, walks, very, slowly] 1 : [the, boy, runs, quickly] 2 : [the, boy, runs, slowly] 1 : [the, boy, runs, quickly] 2 : [the, girl, walks, slowly] 1 : [the, boy, runs, quickly] 2 : [the, boy, walks, very, very, slowly] 1 : [the, boy, runs, quickly] 2 : [the, boy, walks, very, quickly] 1 : [the, boy, runs, quickly] 2 : [the, girl, runs, very, very, quickly] 1 : [the, boy, runs, quickly] 2 : [the, boy, walks, slowly] 1 : [the, boy, runs, quickly] 2 : [the, girl, runs, very, very, slowly] 1 : [the, boy, runs, quickly] 2 : [the, boy, walks, very, slowly]
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:
:- 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:
run((First; Second), EnvI, O, Ret) :- run(First, EnvI, M, _), run(Second, M, O, Ret).
Do assignment.
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).