?- sat([-20, 10, 0, -3, 13, 12],L).
L = [-10,10,0,-3,10,10]
sat is short for saturate: these rules alter a list of positive integers so that any element whose abs. val. is > 10 keeps its sign but its abs. val is set to 10.
saturate([], []).
% too big
saturate([H|T], [X|Y]) :-
H>10, X is 10, saturate(T,Y).
% too small
saturate([H|T], [X|Y]) :-
H< -10, X is -10, saturate(T,Y).
% everything else
saturate([H|T], [X|Y]) :-
X is H, saturate(T,Y).
...
Perhaps surprisingly, hitting ; here will find more copies of your solution, as prolog does the matches in a different order: the number of repetitions is is 2^{N}, where N is the number of elements > 10 or < 10. This is a job for... a (green) CUT!!.
Yes, rule order matters. For instance, the base case has to be at the top, as usual.
More interestingly, if the last rule is moved up to be the second rule, the first answer generated is that the list is just copied with no changes since it's a default-copy rule and will be used first, before the non-default cases that need attention. Originally, it's the last resort after rules 1,2,3 fail. If it's moved to 2nd place, hitting ; generates 2^{N} solutions, not all the same (!!) as backtracking selects different rules.
mammal(namu).
animal(Smthng) :- mammal(Smthng).
In Gprolog,
Errors give line:column where compiler barfed. E.g.
Animal(X) :- ... gives
.../src/namu.pl:2:7: syntax error: . or operator expected after expression
Common Errors:
Logic is one of the canonical formalisms for reasoning, thought, language, knowledge, mathematics, meta-mathematics etc. etc. Huge literature.
Prolog is for "programming in logic", and so inherits some of the paradigmicity of its formal inspiration. It also is a paradigmatical declarative language. That is, it has no control structure, at least ideally.
Clocksin and Mellish don't mention the logical basis of Prolog until the very last chapters of their text, so one doesn't need even to know formal logic exists to be a Prolog expert.
A prolog program states facts and rules, and asks a question. "It" (in the Zen sense) computes to produce an answer. Ideally the programmer doesn't care how. (Reality's another story, sadly). Under the hood there's an automatic theorem prover that does backtracking search to answer the question. That search involves another powerful search, a two-way pattern matcher that implements unification. Prolog statements are Horn Clauses, a slightly restricted but fast version of First Order Predicate Calculus.
As of 2011, the most recent SWI prolog is called swipl.
An older version that may be around is pl. The former is
recommended, so any stray pls in the overheads should be
interpreted as swipl.
/u/brown 560 swipl
Welcome to SWI-Prolog
(Multi-threaded, 32 bits, Version 5.7.11)
. . .
For help, use ?- help(Topic).
or ?- apropos(Word).
?- help(nb_setval).
[bounced to web page of help]
true.
halt.
/u/brown 561
Locally produced: Prologomena.
Another of many sets of Prolog lectures, tutorials, etc on the web: Prolog Introduction: Endriss, KCL.
Locally produced, highly telegraphic and probably no use Scattered basics.
No Prolog lets you insert facts or rules at top level! Must
create file, consult it.
| ?- [tst].
compiling ....
.. tst.pl compiled, 32 lines read ....
(1 ms) yes
| ?- dalter([i ,hate, you],X).
X = [i,hate,i]
yes
| ?- halt.
No ?- help(foo).? Maybe not the most user-friendly documentation, either.
?- append([1,2], [3,4,5], Z).
Z = [1, 2, 3, 4, 5] ;
No
?- append([1,2], Y, [1,2,3,4,5]).
Y = [3, 4, 5] ;
No
?- append(X, Y, [1,2,3,4,5]).
X = []
Y = [1, 2, 3, 4, 5] ;
X = [1]
Y = [2, 3, 4, 5] ;
X = [1, 2]
Y = [3, 4, 5] ;
X = [1, 2, 3]
Y = [4, 5] ;
X = [1, 2, 3, 4]
Y = [5] ;
X = [1, 2, 3, 4, 5]
Y = [] ;
No
?- append([1], Y, Z).
Z = [1|Y] ;
No
?- append(X, [1], Z).
X = []
Z = [1] ;
X = [_G271]
Z = [_G271, 1] ;
X = [_G271, _G277]
Z = [_G271, _G277, 1] ;
?- append(X, Y, Z).
X = []
Y = Z ;
X = [_G277]
Z = [_G277|Y] ;
X = [_G277, _G283]
Z = [_G277, _G283|Y] ;
...
ch(b,a). desc(X,Y) :- ch(X,Y).
ch(c,b). desc(X,Y) :- ch(X,Mid),
desc(Mid,Y).
ch(d,c). /* not a legal file!*/
consult('rec.pl').
?- desc(d,a).
Call: (7) desc(d, a) ? creep
Call: (8) ch(d, a) ? creep
Fail: (8) ch(d, a) ? creep
Redo: (7) desc(d, a) ? creep
Call: (8) ch(d, _L192) ? creep
Exit: (8) ch(d, c) ? creep
Call: (8) desc(c, a) ? creep
Call: (9) ch(c, a) ? creep
Fail: (9) ch(c, a) ? creep
Redo: (8) desc(c, a) ? creep
Call: (9) ch(c, _L203) ? creep
Exit: (9) ch(c, b) ? creep
Call: (9) desc(b, a) ? creep
Call: (10) ch(b, a) ? creep
Exit: (10) ch(b, a) ? creep
Exit: (9) desc(b, a) ? creep
Exit: (8) desc(c, a) ? creep
Exit: (7) desc(d, a) ? creep
Yes
Not a logic concept: it controls backtracking search. So you need to have a good picture of how Prolog control is operating behind the scenes. Sad! The whole ideal of insulating us from "It" crumbles into dust....
Cut is a goal whose effects go back to the parent goal, the rule with the cut on its RHS. Its common uses are:
The cut-fail trick shows the principle of "Negation as Failure:"
If P can be shown, first rule is applicable,
second otherwise. If P can't be proved, backtracking gets to the 2nd rule.
not(P) :- P, !, fail.
not(P).
Without the cut in the rule, get:
| ?- not(true).
yes
| ?- not(fail).
yes
Without the cut, if P is true, the first rule applies, and fails (as
it should). But instead of returning fail and giving up (due to the
cut),
Prolog looks
for another rule or fact to apply and finds the 2nd line. Oops.
Generally: ``to prove ans if you can prove
condgoal then prove thengoal else
prove elsegoal.'' is
ans:- condgoal, !, thengoal.
ans:- elsegoal.
We want h(A,B): "if A<3 set B=0 else set B=2". Two candidates, f/2 and g/2.
f(X,0) :- X<3, !. % if f's first arg <3, % 2nd arg is 0. % NO MORE SEARCH f(X,2). % f's 2nd arg is 2 % for any 1st arg. g(X,0) :- X<3. % as above % but will look for % another rule % if fail (X>=3). g(X,2). % like f(X,2). ------------- *unix*:swipl ?- [cut]. Warning: Singleton variables: [X] % cut compiled 0.00 sec, 6 clauses true. ?- f(1,X). X = 0. ?- f(2,X). X = 0. ?- f(3,X). X = 2. ?- g(1,X). X = 0 ; %aha! X = 2. ?- g(2,X). X = 0 ; X = 2. ?- g(3,X). X = 2. ?- halt.
Check SWI documentation first!
new clauses: consult(S), reconsult(X), also
?- [f1, -f2, 'fred'].
true, fail
classifying terms: var(X), novar(X), atom(X), integer(X), atomic(X)
clauses as terms: listing(A), clause(X,Y), asserta(X), assertz(X),
retract(X)
complex structures: functor(T,F,N), arg(N,T,A),
name(A,L)
backtracking: repeat.
complex goals: X,Y [and], X;Y [or], call(X), not(X)
equality:
X=Y, X \= Y, X == Y, X \== Y, X =:= Y, X =\= Y
I/O: get0(X), get(X), skip(X), read(X), put(X), nl, tab(X), write(X),
display(X), op(X,Y,Z)
files: see(X), seeing(X), seen, tell(X), telling(X), told
arithmetic: ``X is Y'', +,-,*,/,mod, =, \=, <, >, >=, =<
spying: trace, notrace, spy P, debugging, nodebug, nospy
hanoi(N) :- move(N, left, center, right).
move(0,_,_,_) := !. % nothing to do, quit.
move(N,A,B,C) :-
M is N-1,
move(M,A,C,B),
inform(A,B),
move(M,C,B,A).
inform(X,Y) :-
write([move, disc, from, X,
peg, to, Y, peg]),nl.
Note _ the anonymous ("don't care") variable.
last(X,[X]).
last(X,[ _ | Y] :- last(X,Y).
nextto(X,Y, [X,Y | _ ]).
nextto(X,Y, [ _ | Z ]) :- nextto(X,Y,Z).
append([],L,L).
append([X | L1], L2, [X | L3]) :-
append (L1, L2, L3).
Fun with instantiation:
last(E, List) :- append(_,[E], List).
nextto(E1, E2, List) :-
append( _, [E1, E2 | _ ], List).
member(E, List) :=
append(_, [E1 | _ ], List).
Recursive:
rev([],[]).
rev([H | T] , L) :- rev(T,Z), append(Z, [H],L).
Accumulator:
2nd arg is ans so far
rev2(L1, L2) := revzap(L1, [], L2).
revzap([X|L],L2,L3) :- revzap(L,[X|L2],L3).
revzap([],L,L).
at end, copy 2nd to 3rd arg.
Delete one matching elt:
efface(_, [],[]).
efface(A, [A|L], L) :- !.
efface(A, [B|L], [B|M]) :- efface(A,L,M).
Delete all matching elts: new base case (keep on deleting!).
mydelete(_,[],[]).
mydelete(X, [X|L], M) :- ! , mydelete(X,L,M).
mydelete(X, [Y|L], [Y|M]) :- mydelete(X,L,M).
efface(A, [A|L], L) :- ! . /*base case*/
efface(A, [B|L], [B|M]) :- efface(A,L,M).
efface(_,[],[]).
?- efface(a, [b,a,c,a,d],X).
Call: (8) efface(a, [b, a, c, a, d], _G332) ? creep
Call: (9) efface(a, [a, c, a, d], _G416) ? creep
Exit: (9) efface(a, [a, c, a, d], [c, a, d]) ? creep
Exit: (8) efface(a, [b, a, c, a, d], [b, c, a, d]) ? creep
X = [b, c, a, d] ;
Redo: (8) efface(a, [b, a, c, a, d], _G332) ? creep
No
bugefface(A, [A|L], L). % no cut
bugefface(A, [B|L], [B|M]) :- bugefface(A,L,M).
bugefface(_,[],[]).
?- bugefface(a, [b, a,c, a, d],X).
Call: (8) bugefface(a, [b, a, c, a, d], _G332) ? creep
Call: (9) bugefface(a, [a, c, a, d], _G413) ? creep
Exit: (9) bugefface(a, [a, c, a, d], [c, a, d]) ? creep
Exit: (8) bugefface(a, [b, a, c, a, d], [b, c, a, d]) ? creep
X = [b, c, a, d] ;
Redo: (9) bugefface(a, [a, c, a, d], _G413) ? creep
Call: (10) bugefface(a, [c, a, d], _G416) ? creep
Call: (11) bugefface(a, [a, d], _G419) ? creep
Exit: (11) bugefface(a, [a, d], [d]) ? creep
Exit: (10) bugefface(a, [c, a, d], [c, d]) ? creep
Exit: (9) bugefface(a, [a, c, a, d], [a, c, d]) ? creep
Exit: (8) bugefface(a, [b, a, c, a, d], [b, a, c, d]) ? creep
X = [b, a, c, d] ;
Redo: (11) bugefface(a, [a, d], _G419) ? creep
Call: (12) bugefface(a, [d], _G422) ? creep
Call: (13) bugefface(a, [], _G425) ? creep
Exit: (13) bugefface(a, [], []) ? creep
Exit: (12) bugefface(a, [d], [d]) ? creep
Exit: (11) bugefface(a, [a, d], [a, d]) ? creep
Exit: (10) bugefface(a, [c, a, d], [c, a, d]) ? creep
Exit: (9) bugefface(a, [a, c, a, d], [a, c, a, d]) ? creep
Exit: (8) bugefface(a, [b, a, c, a, d], [b, a, c, a, d]) ? creep
X = [b, a, c, a, d] ;
Redo: (12) bugefface(a, [d], _G422) ? creep
Redo: (11) bugefface(a, [a, d], _G419) ? creep
Redo: (10) bugefface(a, [c, a, d], _G416) ? creep
Redo: (9) bugefface(a, [a, c, a, d], _G413) ? creep
Redo: (8) bugefface(a, [b, a, c, a, d], _G332) ? creep
No
Given a structure (like a list or tree), traverse it and produce a new, similar structure with elements that are transformations of the original elements.
Example with lists: alter a list by changing certain items in it by a set of rules.
Or... Altering a list with head H and tail T gives a list with head X
and tail Y if:
changing item H gives item X, and
altering the list T gives the list Y.
If we want to substitute terms (which happen to be spelled like
English
words) in a list, we could see:
%change rules:
change(you,i).
change(are, [am, not]).
change(french, dutch).
change(do, no).
change(X,X). /* the catchall rule...no change */
% the list-altering program:
alter([],[]).
alter([H|T], [X|Y]) :- change(H,X), alter(T,Y).
So get
-? alter([pretend you are french],Z).
Z = [pretend i [am not] dutch]
member(X, [X | _ ]).
member(X, [ _ | Y]) :- member(X,Y).
subset([],Y).
subset([A|X], Y) :- member(A,Y),
subset(X,Y).
disjoint(X,Y) :-
not (( member(Z,X), member(Z,Y))).
No duplicated elts in set.
intersection([],X,[]).
intersection ([X|R], Y, [X|Z]) :-
member(X,Y), !,
intersection(R,Y,Z).
intersection([X|R],Y,Z):- intersection(R,Y,Z).
perm1([],[]).
perm1(List, [Head | Tail]) :-
append(V, [Head|U], List),
% find me a (new) V, U such that...(!!)
append(V,U,W),
perm1(W,Tail).
LHS: To generate a permutation, successively (recursively) generate the next element to be head of the "output" list at this level. RHS: (1) To do that, pick it from somewhere in the list -- there is a leading sublist V in front of it and a trailing sublist U behind it. (2) Compose V and U into the new list from which to pick the next "head" element (in the next recursive level). (3) Permute that list, and put it at the tail of the "head" element at this level of recursion.
If you don't like this permutation, just hit ";" and Prolog will go find a different V (thus) U at all levels... N! times. "Nondeterministic programming".
Quicksort is
(9 1 6 2 5 8 3 7 4 0)
pivot
V
(9 8 7) 6 (1 2 5 3 4 0)
V V
qsort qsort
||
\/
(9 8 7 6 5 4 3 2 1 0)
Bubble Sort:
bubble (L,S) :- append(U,[A,B|V],L),
B < A, !,
append(U, [B,A|V],M),
% !! find me some U, V such that...
bubble(M,S).
% above succeeds only if need swap
bubble(L,L). % so need this(!)
Quicksort:
qsort1 ([H|T],S) :- split(H,T,U1, U2),
qsort1(U1, V1),
qsort1(U2,V2),
append (V1, [H | V2], S).
qsort1([],[]).
Split maps L = [H|T] to U1, U2. U1's elts
≤
H, U2's > H, order in
split(H,[H1|T], [H1|U1],U2) :-
H1 < H, split(H,T, U1, U2).
split(H,[H1|T], U1, [H1|U2]) :-
H1 > H, split(H,T, U1, U2).
split(_,[],[],[]).
Beware,
from
Prolog by Example, VERY typo-ridden book. Very!
qsort2(L,S) :- sort2(L,S,[]).
sort2([H|T],S,X) :- split(H,T,U1,U2),
sort2(U1,S, [H|Y]),
sort2(U2, Y, X).
sort2([],X,X).
Use list difference:
qsort3 ([H|T],S-X) :- split(H,T,U1,U2),
qsort3(U1, S-[H|Y]),
qsort3(U2, Y-X).
qsort3([],X-X).
split(H,[H1|T], [H1|U1],U2) :-
H1 < H, split(H,T, U1, U2).
split(H,[H1|T], U1, [H1|U2]) :-
H1 > H, split(H,T, U1, U2).
split(_,[],[],[]).
}
Accumulators can reduce copying and structure-building in recursive
routines (see the assignment). They're common. Straightforward
recursive List length:
listlen([],0).
listlen([H|T],N) :- listlen(T,Nb4),
N is Nb4 +1.
To use accumulator, always introduce second functor with
extra argument that accumulates
a partial answer: when done its other args match args of the
original functor you wanted. Here:
listlen(L,N) :- lenacc(L,0,N).
/* new 3-arg func*/
lenacc([],A,A).
/*copy accum. to 'output'
(2nd arg to 3rd)*/
lenacc([H|T],A,N) :- A1 is A + 1,
lenacc(T, A1,N).
N just gets carried along and is instantiated w/ special
'copy 2nd arg to 3rd' rule, then 2nd arg tossed out by first rule.
Subgoals look like
lenacc([a,b,c],0,N)
/* all N's co-refer*/
lenacc([a,b],1,N)
lenacc([a],2,N)
lenacc([],3,N)
There are two numbers M and N, 1 < M, N, < 100. I tell Mr. S their sum, and I tell Mr. P their product. S knows P knows the product, P knows S knows the sum.
Mr. P: I don't know the numbers.
Mr. S: Yeah, I knew you didn't. Neither do I.
Mr. P: Oh, now I know them!
Mr. S: Oh yeah? Well then so do I.
. . .
So, what are M and N?
Also very much to the point... How translate this English into Prolog?
Declaring Operators:
Operators have:
Operator has descriptive atom: for infix:
xfx, xfy, yfx, yfy, for prefix: fx, fy,
for postfix: xf, yf. f is the operator, and
x,y are the arguments. In the absence of brackets, the y argument can have
operators of the same or lower precedence class than operator
f;
x means any operators in the argument must have strictly
lower
precedence than f. So with + declared as yfx,
you can't have a + b + c interpreted as {a + (b + c)
since the arg after + constains arg of same precedence: thus
yfx
means left associativity, and
xfy
means right associativity. E.g.---.
:- op(650,yfx,'::').
:- op(675,xfy,'::=').
Z ::= X :: Y :- append(X,Y,Z).
?- MyList ::= [a,b] :: [x,y,z].
MyList = [a, b, x, y, z]
Yes