Programming in Prolog: built-ins, idioms, metaprogramming

1. What do built-in lists and numbers add?

List syntax

Library predicates assume that lists are built with the functor '.'/2 in place of cons and the atom [] in place of nil. Since right-nested terms are verbose, there is a special syntax, the one to use always: [H1,H2,…,Hn|T] stands for '.'(H1,'.'(H2,…,'.'(Hn,T)…)) and [H1,…,Hn] for [H1,…,Hn|[]]. [H|T], [], [E1,E2], [_|T] and [E1,_|_] are the common shapes. The library also offers member(Elem, List) (our find), append/3, reverse/2 and many others.

?- append('.'(a,'.'(b,[])), '.'(c,[]), '.'(a,'.'(b,'.'(c,[])))).   % yes
?- append([a,b], [c], L).            % L = [a,b,c]
?- append([a,b], [c], [H|T]).        % H = a, T = [b,c]
?- append([a,b], [c], [_|_]).        % yes
?- append([a,b], [c], [_,_,_]).      % yes
?- append([a,b], [c], [_,_,_,_]).    % no
?- append([a,b], [c], [_,_,E]).      % E = c
?- append([a,b], [c], [_,_|T]).      % T = [c]
?- append([a,b], [c], [_,_,_|T]).    % T = []

find([E|_], E).                                   % relates a list with one of its elements
find([_|T], E) :- find(T, E).
position([E|_], zero, E).                         % ... with an element and its Peano position
position([H|T], s(N), E) :- position(T, N, E).
join([], L, L).                                   % relates two lists with their concatenation
join([H|T], L, [H|M]) :- join(T, L, M).

?- find([a,b,c], b).            % yes ; no
?- find([a,b,c], 40).           % no
?- position([a,b,b], P, b).     % P = s(zero) ; P = s(s(zero)) ; no
?- join([a,b], [c], L).         % L = [a,b,c]

Full relationality

A predicate is fully relational if each of its arguments can be used as input or as output: called with a variable in some argument, resolution enumerates all the values that satisfy the relation. Often this holds for groups of arguments rather than all of them, and for complex algorithms it is often out of reach; when it holds, one predicate gives you several functions. find searches, iterates and generates:

?- find([a,b,c], E).          % E = a ; E = b ; E = c ; no
?- find(L, a).                % L = [a|_] ; L = [_,a|_] ; L = [_,_,a|_] ; ... forever
?- position([a,b,c], N, E).   % N = zero, E = a ; N = s(zero), E = b ; N = s(s(zero)), E = c ; no
?- join(L, M, [a,b,c]).       % L = [], M = [a,b,c] ; L = [a], M = [b,c] ; L = [a,b], M = [c] ; L = [a,b,c], M = []

Documentation marks the intended use of each argument with a convention that is not Prolog syntax: + input, - output, ? either, @ input that must be ground. Examples: member(?E, ?L), permutation(+LI, -LO), append(?L1, ?L2, ?L), is(-O, @Expression). How to document several modes is not clear.

Operators and arithmetic

An operator is a predicate or functor that can be written in infix (binary) or prefix (unary) notation: '='(p(1,2), p(X,Y)) and p(1,2) = p(X,Y) are the same goal. Numbers like 10, -20.1, 1.3e-4 are ground terms, and + - * / are ordinary binary functors, so 10+20 is the term '+'(10,20): the syntax tree of an expression. The comparisons =:=, =\=, >, <, >=, =< (not <=) evaluate both sides, which must be ground. is/2 evaluates its right side and unifies the number with its left side.

?- '='(p(1,2), p(X,Y)).   % X = 1, Y = 2     standard notation
?- p(1,2) = p(X,Y).       % X = 1, Y = 2     infix notation
?- p(1,2) = p(_,3).       % no
?- 20 > 10.               % yes
?- 10 =:= 20.             % no               number equality
?- 10 =\= 20.             % yes              number inequality
?- X = 10 + 20.           % X = '+'(10,20)   + is just a functor
?- X is 10 + 20.          % X = 30           evaluation
?- 30 is 10 + 20.         % yes
?- 10 is p(20).           % error: p(20) is not an arithmetic expression
?- 10 is X + 5.           % error: X is unbound

The two errors abort the whole query (the slides call it "HALT!"). Arithmetic predicates are very often not relational, and is/2 must not be used to unify terms. A typical recursion:

sum([], 0).                                % relates a list with the sum of its elements
sum([H|T], S) :- sum(T, N), S is H + N.

?- sum([10,20,30], S).    % S = 60
?- sum([], S).            % S = 0
?- sum([10,20,30], 60).   % yes
?- sum(L, 0).             % L = [] ; then error: the second clause reaches "0 is H + N" with H unbound

2. How do you write efficient recursive predicates?

Prolog has a reputation for being slower than C; professional implementations are rather fast, while tuProlog is not (the JVM layer, and speed is not its goal). As always in the course, deal with performance only when a requirement is not met, but know the cost of your choices. The first measure of a predicate's cost is its number of resolution steps. Each step finds a matching clause, computes an mgu and updates the resolvent: roughly constant, though it grows with the numbers of clauses, variables and goals.

Tail recursion

A recursion is tail if the recursive call is the last thing executed: nothing is left to do when the base case is reached, so the work is done on the way down and activation records can in principle be avoided. In Prolog it means the head predicate occurs only as the last goal of the body. It usually needs extra arguments that carry the state, and the non-tail version is often more idiomatic.

sum([], 0).
sum([H|T], N) :- sum(T, N2), N is H + N2.

% sum([10,20,30], S)
% sum([20,30], S'), S is 10 + S'
% sum([30], S''), S' is 20 + S'', S is 10 + S'
% sum([], S'''), S'' is 30 + S''', S' is 20 + S'', S is 10 + S'
% S'' is 30 + 0, S' is 20 + S'', S is 10 + S'
% S' is 20 + 30, S is 10 + S'
% S is 10 + 50
% S = 60

sum(L, S) :- sum(L, 0, S).
sum([], S, S).
sum([H|T], N, S) :- N2 is H + N, sum(T, N2, S).

% sum([10,20,30], S)
% sum([10,20,30], 0, S)
% N2' is 10 + 0, sum([20,30], N2', S)
% sum([20,30], 10, S)
% N2'' is 20 + 10, sum([30], N2'', S)
% sum([30], 30, S)
% N2''' is 30 + 30, sum([], N2''', S)
% sum([], 60, S)   -->   S = 60

Prolog goes beyond FP here: it builds lists foldright-style with a tail recursion. In join/3 the output [H|T2] is created by unification when the clause is chosen, with a hole T2 that the recursive call, the last goal, will fill:

join([], L, L).
join([H|T], L, [H|T2]) :- join(T, L, T2).

% join([10,20], [30,40,50], L)
% join([20], [30,40,50], T2')     : {L/[10|T2']}
% join([], [30,40,50], T2'')      : {L/[10|T2'], T2'/[20|T2'']}
% yes                             : {..., T2''/[30,40,50]}  ≡  {L/[10,20,30,40,50]}

With immutable data in Scala, a cons cell can be built only after its tail exists, so the same function is not tail recursive.

Immutability and sharing

Computation happens only by resolution and unification, so terms are never modified: a term, once built, never changes, and its parts can be shared with other terms. The only "declarative side effect" is that a variable inside a non-ground term gets bound. update/4 relates a list with the list where the first occurrence of E1 is replaced by E2:

update([], _, _, []).
update([E1|T], E1, E2, [E2|T]).
update([H1|T1], E1, E2, [H1|T2]) :- update(T1, E1, E2, T2).

?- update([10,20,30,40], 20, 21, L).
% L = [10,21,30,40] ; L = [10,20,30,40]
% update([20,30,40], 20, 21, T2') : {L/[10|T2']}
% yes : {L/[10|T2'], T2'/[21|[30,40]]}  ≡  {L/[10,21,30,40]}

The output shares the tail [30,40] with the input. The slide shows only the first answer; tuProlog finds a second, [10,20,30,40], because the third clause can also skip the matching element and copy the whole list, down to the first clause at []. With [10,20,30,20] you get three answers. This is the kind of spurious solution the cut removes (Section 4).

3. How does Prolog search a space of solutions?

Even if a predicate is designed with inputs and outputs in mind, a goal may put variables anywhere, and resolution then looks for every substitution that satisfies the relation: for free in simple cases, by explicit programming in others. Prolog is naturally suited to searching tree-shaped spaces. With join/3 the goal matches both clauses, and thanks to tail recursion each answer is built while exploring:

join(L1, L2, [a,b,c])
├─ {L1/[], L2/[a,b,c]}
└─ join(T', L2, [b,c])        : {L1/[a|T']}
   ├─ {L1/[a], L2/[b,c]}
   └─ join(T'', L2, [c])      : {L1/[a,b|T'']}
      ├─ {L1/[a,b], L2/[c]}
      └─ join(T''', L2, [])   : {L1/[a,b,c|T''']}
         └─ {L1/[a,b,c], L2/[]}

Permutations, and a pitfall

% member2(List, Elem, ListWithoutElem)
member2([X|Xs], X, Xs).
member2([X|Xs], E, [X|Ys]) :- member2(Xs, E, Ys).

% permutation(Ilist, Olist)
permutation([], []).
permutation(Xs, [X|Ys]) :- member2(Xs, X, Zs), permutation(Zs, Ys).

?- permutation([a,b,c], L).   % L = [a,b,c] ; L = [a,c,b] ; L = [b,a,c] ; L = [b,c,a] ; L = [c,a,b] ; L = [c,b,a] ; no
?- permutation(L, [a,b]).     % L = [a,b] ; then runs forever

For permutation([a,b,c], L) the tree first binds L/[X'|Ys']; each choice of member2 fixes the head (a, then b, then c) and recurses on the remaining list, so the answers appear while descending. In the other direction, the first answer [a,b] arrives, but then member2(Zs', b, Zs'') is called with an unknown list and keeps generating longer lists such as [a, X', b | Ys''], none of which is a permutation of [a,b]: an infinite branch.

Fully relational predicates are hard to write when the solutions are infinite or the enumeration is not "directional": checking that a list contains 10, 20 and 30 is easy, enumerating all lists that contain them is not. In principle one could visit the tree breadth-first: all solutions would eventually be found, at a very high cost in memory and time.

Chained goals are a for-comprehension

If goal G_i of a resolvent has k_i solutions and does not constrain the next goals, the resolvent has k₁·k₂·…·k_n solutions, all the combinations. This is exactly what a for-comprehension with flatMap does, a monadic computation: in a sense every Prolog computation is potentially a for-comprehension.

?- member(X,[10,20,30]), member(Y,[1,2]), Res is X+Y.
% Res = 11 ; Res = 12 ; Res = 21 ; Res = 22 ; Res = 31 ; Res = 32 ; no   (X and Y shown too)

The slides use the pattern to generate the links of an N×M grid:

interval(A, B, A).
interval(A, B, X) :- A2 is A+1, A2 < B, interval(A2, B, X).

neighbour(A, B, A, B2) :- B2 is B+1.
neighbour(A, B, A, B2) :- B2 is B-1.
neighbour(A, B, A2, B) :- A2 is A+1.
neighbour(A, B, A2, B) :- A2 is A-1.

gridlink(N, M, link(X, Y, X2, Y2)) :-
    interval(0, N, X),
    interval(0, M, Y),
    neighbour(X, Y, X2, Y2),
    X2 >= 0, Y2 >= 0, X2 < N, Y2 < M.

?- gridlink(3, 3, L).
% L = link(0,0,0,1) ; L = link(0,0,1,0) ; L = link(0,1,0,2) ; L = link(0,1,0,0) ; ...
% ... ; L = link(2,2,2,1) ; L = link(2,2,1,2) ; no      (24 links)

Two generators pick a cell, a third picks a neighbour, and the tests act like if guards in a for-comprehension. Unlike interval/3 of the slides, range/3 of Lesson 9 includes its upper bound; here A2 < B excludes it, so X and Y range over 0, 1, 2.

4. What does the cut prune, and what is negation as failure?

Branching and backtracking are Prolog's features, but sometimes they are a bug: some predicates produce spurious solutions, and handling the branches can violate DRY and waste time. Prolog offers extra-relational predicates to control how many or which solutions a goal gives. The most important one is the cut, the 0-ary predicate !; it is used very often and must be mastered.

% merge(List1, List2, OutList): merge two sorted lists
merge(Xs, [], Xs).
merge([], Ys, Ys).
merge([X|Xs], [Y|Ys], [X|Zs]) :- X < Y, merge(Xs, [Y|Ys], Zs).
merge([X|Xs], [Y|Ys], [Y|Zs]) :- X >= Y, merge([X|Xs], Ys, Zs).

?- merge([], [], L).            % L = [] ; L = []          two equivalent solutions
?- merge([10,20], [5,35], L).   % L = [5,10,20,35] ; no    a spurious, costly "no"

Both facts match merge([],[],L), hence the duplicate. In the second query, whenever X < Y succeeds, the fourth clause is still pending even though its test must fail, and at the end the non-empty patterns are still to be tried against []. Asking for another answer revisits all of them, and they all fail: the no is not a wrong result but useless work. Once one of the three cases has succeeded, the others need not be checked.

What the cut does

The cut is a goal in the body of a rule. It always succeeds, and as a side effect it discards local pending branches: the following clauses of the predicate whose clause contains the cut, and the pending alternatives of the goals to its left in the same body. Precisely: when ! is executed, all pending branches below the node that first generated that cut (the node where its clause was selected) are pruned. Nodes above are not touched.

go :- p, a.
go :- ...
r.
r.
p :- q.
p :- r, !, t, u.
p :- v.
p :- z.

tuProlog confirms it. Make every predicate print its name (q then fails) and let the second clause of go print go2: ?- go. answers yes ; yes and prints q t u a go2. Neither v nor z is ever called.

With cuts, merge keeps only the useful search. The first cut prunes the second fact when the second list is empty. The second prunes the fourth clause once X < Y has succeeded, so the fourth clause no longer needs its own test:

% merge(+List1, +List2, -OutList)
merge(Xs, [], Xs) :- !.
merge([], Ys, Ys).
merge([X|Xs], [Y|Ys], [X|Zs]) :- X < Y, !, merge(Xs, [Y|Ys], Zs).
merge([X|Xs], [Y|Ys], [Y|Zs]) :- merge([X|Xs], Ys, Zs).

?- merge([], [], L).            % L = []
?- merge([10,20], [5,35], L).   % L = [5,10,20,35]

The slide and 11-code.txt write the second clause as merge([], Ys Ys)., with a comma missing; tuProlog rejects the whole theory with a syntax error.

Cut for a single result

first_index_of([E|_], E, 0) :- !.
first_index_of([_|T], E, N) :- first_index_of(T, E, N2), N is N2 + 1.

index_of([E|_], E, 0).
index_of([_|T], E, N) :- index_of(T, E, N2), N is N2 + 1.
first_index_of2(L, E, N) :- index_of(L, E, N), !.

?- first_index_of([a,b,b,c], b, N).    % N = 1
?- index_of([a,b,b,c], b, N).          % N = 1 ; N = 2 ; no
?- first_index_of2([a,b,b,c], b, N).   % N = 1

In first_index_of, when the resolvent !, N is 0 + 1 becomes N is 0 + 1, all pending branches below the node first_index_of([b,b,c], b, N2') are pruned: the second clause is excluded. In first_index_of2 the cut prunes the pending solutions of index_of, the goal to its left. The second style keeps a relational core and adds the cut in a thin wrapper. The same idea partitions a list for quicksort:

quicksort([], []).
quicksort([X|Xs], Ys) :-
    partition(Xs, X, Ls, Bs),
    quicksort(Ls, LOs),
    quicksort(Bs, BOs),
    append(LOs, [X|BOs], Ys).

% partition(Ilist, Pivot, Littles, Bigs)
partition([], _, [], []).
partition([X|Xs], Y, [X|Ls], Bs) :- X < Y, !, partition(Xs, Y, Ls, Bs).
partition([X|Xs], Y, Ls, [X|Bs]) :- partition(Xs, Y, Ls, Bs).

?- partition([10,3,20,5,30,9,40], 10, L1, L2).   % L1 = [3,5,9], L2 = [10,20,30,40]
?- quicksort([60,10,20,50,30,40], L).            % L = [10,20,30,40,50,60]

Negation as failure

The library predicate not(G) (ISO writes it \+ G) solves G and gives the opposite result, without binding any variable: it succeeds if G has no solution and fails if G has one. It is negation as failure: "not provable" stands for "false", which is sound only under the assumption that the program says everything that is true (the closed-world assumption).

bird(tweety).
bird(pingu).
penguin(pingu).
flies(X) :- bird(X), not(penguin(X)).
flies2(X) :- not(penguin(X)), bird(X).

?- flies(tweety).              % yes
?- flies(pingu).               % no
?- flies(X).                   % X = tweety ; no
?- flies2(X).                  % no
?- not(member(X, [a,b])).      % no
?- not(not(member(X, [a,b]))). % yes     succeeds, but X is still unbound

The stepper of Lesson 9, with cut and not/1. Pruned branches are struck through; pick an example:

5. How do you inspect and build terms?

So far unification was the only way to handle terms, both to inspect inputs and to build outputs. The library adds predicates that are "extra-relational" like the cut: they look at the current state of a term. The families are shape tests (var/1, nonvar/1, number/1, float/1, integer/1, atom/1, compound/1, ground/1), comparisons (=/2, \=/2, ==/2, \==/2, copy_term/2), terms as strings (atom_chars/2, atom_codes/2, atom_concat/3, char_code/2, number_chars/2, number_codes/2), term structure (=../2, functor/3, arg/3), and I/O (write/1, nl/0, …). Shape tests typically check the correctness of inputs.

?- atom(a).              % yes
?- atom(10).             % no
?- atom(a(1)).           % no
?- var(X).               % yes
?- var(a).               % no
?- nonvar(X).            % no
?- number(10).           % yes
?- float(10.1).          % yes
?- integer(10.1).        % no
?- compound(10).         % no
?- compound(a).          % no
?- compound(a(10,20)).   % yes
?- ground(a(10,20)).     % yes
?- ground(a(10,X)).      % no

Comparing terms

% unification
?- a(X,b) = a(10,b).         % X = 10
?- a(X,b) = a(Y,c).          % no
% non-unification: never binds
?- a(10,b) \= a(10,b).       % no
?- a(X,b) \= a(10,b).        % no
?- a(X,b) \= a(Y,c).         % yes
% identity: no binding
?- a(10,b) == a(10,b).       % yes
?- a(X,b) == a(10,b).        % no
?- a(X,b) == a(X,b).         % yes
% non-identity
?- a(X,b) \== a(10,b).       % yes
?- a(X,b) \== a(X,b).        % no
% cloning
?- copy_term(a(10,X), Y).          % Y = a(10,_)   with a fresh variable
?- copy_term(a(10,X), a(10,Y)).    % yes
?- copy_term(a(10,X), a(11,X)).    % no

Since copy_term clones before unifying, it checks that a term has a given "shape" without binding the pattern:

% all(+Term, +List): are all elements in List of the kind of Term?
all(_, []).
all(X, [Y|T]) :- copy_term(X, Y), all(X, T).

?- all(p(X), [p(a), p(b), p(a)]).   % yes   (a plain X = Y would bind X to a and then fail on p(b))

Strings and structure

?- atom_chars(hello, L).          % L = [h,e,l,l,o]
?- atom_chars(X, [h,e,l,l,o]).    % X = hello
?- atom_codes(hello, L).          % L = [104,101,108,108,111]
?- atom_codes(X, [95,48,32,49]).  % X = '_0 1'
?- atom('_0 1').                  % yes
?- atom_concat(aa, bb, X).        % X = aabb
?- number_chars(100, X).          % X = ['1','0','0']
?- number_codes(100, X).          % X = [49,48,48]

?- p(10, q(20)) =.. L.            % L = [p,10,q(20)]     compound term to list ("univ")
?- X =.. [p, 10, q(20)].          % X = p(10,q(20))
?- functor(p(10,20,30), X, Y).    % X = p, Y = 3
?- functor(T, p, 3).              % T = p(_,_,_)
?- arg(2, p(10,20,30), Y).        % Y = 20

For debugging by logging, write/1 and nl/0 print on the console:

sum([], 0).
sum([H|T], N) :- sum(T, N2), write(N2), nl, N is H + N2.
?- write('start'), nl, sum([10,20,30], N).   % N = 60, printing: start 0 30 50 (one per line)

With var/1 and a cut a predicate can choose its algorithm by the mode it is called in, which gives a fully relational size/2:

size(L, N) :- var(L), !, generate(L, N).
size(L, N) :- length(L, N).

generate([], 0) :- !.
generate([_|T], N) :- N2 is N-1, generate(T, N2).

length([], 0).
length([_|T], N) :- length(T, N2), N is N2 + 1.

?- size([10,20,30], N).   % N = 3
?- size(L, 3).            % L = [_,_,_]

6. How do you model other data types?

The same recipe as for lists applies: choose functors for the values, write relational operations by matching on them, and add cuts where one answer is enough. A database table is a list of compound terms, with select, insert and update written as expected (performance may be an issue):

% get_ids(+Table, -List)
get_ids([], []).
get_ids([user(ID, _, _)|T], [ID|L]) :- get_ids(T, L).
% query(+Table, +Id, -Tuple)
query([user(ID, N, C)|_], ID, user(ID, N, C)).
query([_|T], ID, Tuple) :- query(T, ID, Tuple).
% update(+Table, +Id, +NewTuple, -NewTable)
update([user(ID, _, _)|T], ID, Tuple, [Tuple|T]).
update([H|T], ID, Tuple, [H|Table]) :- update(T, ID, Tuple, Table).

?- update([user(100,a,b), user(101,c,d)], 101, user(101,c,e), DB).   % DB = [user(100,a,b),user(101,c,e)] ; no

Trees

% binary trees: tree(Left, Elem, Right) and nil
search(tree(_, E, _), E).                        % search(+Tree, ?Elem)
search(tree(L, _, _), E) :- search(L, E).
search(tree(_, _, R), E) :- search(R, E).

leaves(nil, []).                                  % leaves(+Tree, -ListLeaves)
leaves(tree(nil, E, nil), [E]) :- !.              % a leaf
leaves(tree(L, _, R), O) :- leaves(L, OL), leaves(R, OR), append(OL, OR, O).

leftlist(nil, []).                                % leftlist(+Tree, -List): the left-most branch
leftlist(tree(nil, E, _), [E]) :- !.
leftlist(tree(T, E, _), [E|L]) :- leftlist(T, L).

?- search(tree(tree(nil,10,nil), 20, tree(tree(nil,30,nil), 40, nil)), E).     % E = 20 ; E = 10 ; E = 40 ; E = 30 ; no
?- leaves(tree(tree(nil,10,nil), 20, tree(tree(nil,30,nil), 40, nil)), L).     % L = [10,30]
?- leftlist(tree(tree(nil,10,nil), 20, tree(tree(nil,30,nil), 40, nil)), L).   % L = [20,10]

The slide gives L/[30,40] for leaves; the leaves of that tree are 10 and 30, and tuProlog answers [10,30]. N-ary trees can hold their children in a list, tree(Elem, Children), or as extra arguments of a functor of variable arity, tree/1, tree/2, tree/3…, taken apart with =..:

% searchN(+Tree, ?Elem)
searchN(tree(E, _), E).
searchN(tree(_, L), E) :- member(T, L), searchN(T, E).
?- searchN(tree(20, [tree(10, []), tree(40, [tree(30, [])])]), E).   % E = 20 ; E = 10 ; E = 40 ; E = 30 ; no

% searchV(+Tree, ?Elem)
searchV(T, E) :- T =.. [tree, E | _].
searchV(T, E) :- T =.. [tree, _ | L], member(T2, L), searchV(T2, E).
?- searchV(tree(20, tree(10), tree(40, tree(30))), E).               % E = 20 ; E = 10 ; E = 40 ; E = 30 ; no

The slide and 11-code.txt call search(T, E) in the second clause of searchN, the binary-tree predicate. With that typo the query answers only E = 20; the recursive call must be searchN.

Bidirectional lists and partial structures

A list with a cursor that moves in constant time can be two lists, the elements to the left of the cursor in reverse order and those to the right: bilist([1],[2,3,4,5,6]); move right: bilist([2,1],[3,4,5,6]); move left: back to bilist([1],[2,3,4,5,6]); add 0 on the left: bilist([0],[1,2,3,4,5,6]); add 10 on the right: bilist([0],[10,1,2,3,4,5,6]).

A non-ground term is a partially completed structure: [1,2,3|_] is a list that starts with 1, 2, 3 and can still be completed. Could that model lazy lists? The slides build an expanding cache of factorials that is both input and output:

% factorial(+N, -Out, ?Cache): Cache is a partial list of factorials, e.g. [1,1,2,6,24|_]
factorial(N, Out, Cache) :- factorial(N, Out, Cache, 0).

factorial(N, Res, [Res|_], N) :- !, nonvar(Res).          % position N reached: the value must be known
factorial(N, Out, [H, V|T], I) :-                          % next cell is a hole: fill it
    var(V), !, I2 is I + 1, V is H * I2,
    factorial(N, Out, [V|T], I2).
factorial(N, Out, [_, V|T], I) :-                          % next cell is known: move on
    I2 is I + 1, factorial(N, Out, [V|T], I2).

?- C = [1,1,2,6|_], factorial(5, Res, C).   % C = [1,1,2,6,24,120|_], Res = 120
?- C = [1,1,2,6|_], factorial(2, Res, C).   % C = [1,1,2,6|_], Res = 2

7. Why does "everything is a term" matter?

Metaprogramming is the ability of a program to treat programs as data: to read and reason about them, update or synthesise them, and execute them, possibly under different conditions. Java has reflection (and libraries for code instrumentation); Scala 3 has macros and inline metaprogramming. In Prolog it is simple and direct, because clauses are terms, even syntactically. That is why AI uses Prolog as a component for symbolic reasoning. The ingredients are: everything is a term, predicates that "call" terms, dynamic theories, and meta-interpretation.

?- {0,1,2+3} = '{}'(A), A =.. L.   % A = (0,1,'+'(2,3)), L = [',',0,(1,'+'(2,3))]
?- (p(X) :- q(X)) =.. L.          % L = [':-',p(X),q(X)]      a clause is a term too

Operators and DSLs

An operator is a predicate or functor declared to have a different syntax: infix if binary, prefix if unary. It can be a symbol written without quotes. It is declared by executing op(Priority, Type, Name) before it is used: the priority sets its precedence with respect to other operators, and the type is xfx, xfy, yfx (infix: non-associative, right-, left-associative), fx, fy (prefix) or xf, yf (postfix); a y marks the side that may hold an operator of the same priority.

% use as predicate
:- op(100, xfx, '~').
N1 ~ N2 :- N1 > N2, !, Delta is N1 - N2, Delta < 0.1.
N1 ~ N2 :- N2 ~ N1.
?- 10 ~ 10.01.                        % yes

% use as functor
:- op(100, xfy, '::').
to_list(A :: B, [A|B2]) :- to_list(B, B2).
to_list(nil, []).
?- to_list(10 :: 20 :: 30 :: nil, L). % L = [10,20,30]

% use as DSL
:- op(100, fx, person).
:- op(100, fx, name).
:- op(100, fx, age).
:- op(100, fx, nationality).
:- op(100, fx, married).
person { name 'Rossi Marco', age 30, nationality italy, married false }.
?- person { name NM, age A, nationality N, married M }.   % NM = 'Rossi Marco', A = 30, N = italy, M = false

The slides warn that operators "apparently work in tuProlog 3.3, and have bugs in tuProlog 4". On 4.0.3 the first two examples work. The DSL works too if each operator is declared separately, as above. The slides' single declaration with a list, :- op(100, fx, [person, name, age, nationality, married])., makes tuProlog 4.0.3 reject the theory with a syntax error at {.

Calling terms, collecting solutions

G can be any term with the syntax above; if it is (G1,…,Gn) it is solved as a resolvent. Passing a predicate name and building the goal with =.. gives "higher-order" predicates. findall simplifies algorithms that need all results up front, to have a broad view of them; in filter the pair X, P acts like a lambda:

% map(+L, +P, -LO)
map([], _, []).
map([H|T], P, [H2|T2]) :- G =.. [P, H, H2], once(G), map(T, P, T2).
inc(N, N2) :- N2 is N+1.
?- map([10,20,30], inc, L).                                    % L = [11,21,31]

?- findall([X,Y], (member(X,[1,2,3]), member(Y,[1,2,3])), L).  % L = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

% filter(+L, X, P, -LO)
filter(L, X, P, LO) :- findall(X, (member(X, L), once(P)), LO).
?- filter([10,21,30,40,50], X, X > 25, LO).                    % LO = [30,40,50]

Lab 12 passes a whole "lambda" instead: a term mapper(I, O, Op) that is cloned with copy_term before each use, so that its variables are fresh every time:

% map(+L, +Mapper, -Lo) where Mapper = mapper(I, O, UNARY_OP), e.g. mapper(X, Y, Y is X+1)
map([], _, []).
map([H|T], M, [H2|T2]) :- map(T, M, T2), copy_term(M, mapper(H, H2, OP)), call(OP).

?- map([10,20,30], mapper(X, Y, Y is X+1), L).                 % L = [11,21,31]
?- copy_term(mapper(X,Y,Y is X+1), mapper(10,R,OP)).           % OP = is(R,'+'(10,1)), then call(OP) gives R = 11

Disjunction

Anywhere in a body, (G ; G') says that either G or G' (or both) should be solvable. Formally, H :- G1, …, Gk, (G ; G'), G1', …, Gk' means: add two clauses C(X1,…,Xn) :- G. and C(X1,…,Xn) :- G'., where X1,…,Xn are all the variables of G and G', and replace (G ; G') with C(X1,…,Xn). So ; introduces a branch:

neighbour(X, Y1, X, Y2) :- Y1 is Y2+1 ; Y1 is Y2-1.
neighbour(X1, Y, X2, Y) :- X1 is X2+1 ; X1 is X2-1.
?- neighbour(A, B, 0, 0).   % A = 0, B = 1 ; A = 0, B = -1 ; A = 1, B = 0 ; A = -1, B = 0

Other control predicates exist (->, repeat, …). The slides call them "a step too far": you would not need them, and if you use them you will be asked their exact semantics.

8. How can a program change itself?

A Prolog program is made of two theories: the static one, given at the start of the session (the one written in the IDE), and a dynamic one, initially empty, to which clauses can be added and from which they can be removed. Some Prologs, tuProlog 3.3 and 4.0 among them, have a single theory, and it is dynamic. Since clauses are terms, the API is simple, and the theory can also be inspected:

• assert(+Clause) adds a clause; it always succeeds and never binds: assert(p(1)), assert((p(X) :- q(X))). asserta and assertz add it at the top or at the bottom.
• retract(+Clause) removes a matching clause if there is one, and may bind variables; retractall(+Clause) removes all matching clauses, always succeeds and never binds.
• clause(?Head, ?Body) looks a clause up, possibly with many solutions and bindings; Body is true for a fact and (G1,…,Gn) in general.

The slides cache factorials in the theory itself (queries run in order on the same engine):

factorial(0, 1).
factorial(X, Y) :- Xm is X-1, factorial(Xm, Y2), Y is Y2*X.

withcache(P) :- cached(P), !.
withcache(P) :- once(P), assert(cached(P)).

?- cached(X).                     % no
?- factorial(3, N).               % N = 6
?- cached(X).                     % no
?- withcache(factorial(3, N)).    % N = 6      computed, then stored
?- cached(X).                     % X = factorial(3,6)
?- clause(cached(X), B).          % X = factorial(3,6), B = true
?- withcache(factorial(4, N)).    % N = 24
?- findall(C, cached(C), L).      % L = [factorial(3,6),factorial(4,24)]
?- retract(cached(factorial(3, X))).   % X = 6
?- findall(C, cached(C), L).      % L = [factorial(4,24)]

The once is not decoration. factorial/2 has no test X > 0, so after answering N = 6 it can backtrack into the second clause with X = 0 and recurse through negative numbers forever: in tuProlog, asking for a second answer to ?- factorial(3, N). never returns. The first clause of withcache answers from the cache, and its cut avoids recomputing. The slides note that withcache can be read as a meta-interpreter for single-result predicates that adds caching to the standard interpretation.

9. How do meta-interpreters work?

An interpreter reads and executes a program; a meta-interpreter is an interpreter written in the same language as the programs it runs, usually to change the interpretation strategy. In Prolog it is easy, since programs are terms and resolution is "substitute a head with its body". Programmers use it for debugging, profiling and changing the resolution strategy; AI planners use it to explore the space of a DSL in their own way.

As a first step, write the clauses as facts rule(Head, BodyList) and simulate resolution. Calling rule/2 does the unification, its several clauses do the branching, and append/3 substitutes the head with the body:

rule(a, []).    % means: a.
rule(b, []).    % means: b.
rule(d, []).    % means: d.
rule(d, []).    % means: d.
rule(c, []).    % means: c.
rule(c, [c]).   % means: c :- c.
rule(search(E, [E|_]), []).
rule(search(E, [_|T]), [search(E, T)]).

solve([]).
solve([Goal|Rest]) :- rule(Goal, Body), append(Body, Rest, NewGoals), solve(NewGoals).

?- solve([a]).                         % yes
?- solve([d]).                         % yes ; yes
?- solve([e]).                         % no
?- solve([c]).                         % yes ; yes ; yes ; ... forever
?- solve([search(X, [10,20,30])]).     % X = 10 ; X = 20 ; X = 30 ; no     full resolution!

The vanilla meta-interpreter does the same on ordinary clauses, read with clause/2:

solveV(true) :- !.
solveV((A, B)) :- !, solveV(A), solveV(B).
solveV(G) :- clause(G, B), solveV(B).

search(E, [E|_]).
search(E, [_|T]) :- search(E, T).

?- solveV(search(X, [10,20,30])).   % X = 10 ; X = 20 ; X = 30 ; no

Its defects may be features. It cannot run built-in predicates, which are not defined by clauses: solveV(sum([10,20], S)) with the sum/2 of Section 1 stops with an error at is/2. And control predicates must be re-implemented, which lets you pick explicitly what to support:

builtins(['is', '=', '\\=', '==']).    % possibly more
solveB(true) :- !.
solveB((A, B)) :- !, solveB(A), solveB(B).
solveB(G) :- functor(G, F, _), builtins(B), member(F, B), !, call(G).   % built-ins are called as such
solveB(once(G)) :- !, once(solveB(G)).                                 % handling once/1
solveB(not(G)) :- !, not(solveB(G)).                                   % handling not/1
solveB(G) :- clause(G, B), solveB(B).

sum([], 0).
sum([H|T], N) :- sum(T, N2), N is N2 + H.

?- solveB(sum([10,20,30], S)).          % S = 60 ; no
?- solveB(not(sum([10,20,30], 50))).    % yes
?- solveB(not(sum([10,20,30], 60))).    % no

The slides leave a challenge: how would you implement the cut?

Changing the strategy

Collecting the matching clauses first with findall gives a view of all the branches, to analyse, prioritise or discard them. Reversing the list reverses the order of the solutions:

solveI(true) :- !.
solveI((A, B)) :- !, solveI(A), solveI(B).
solveI(G) :-
    findall(c(G, B), clause(G, B), L),
    reverse(L, L2),                 % inverting solutions!
    member(c(G, B), L2),
    solveI(B).

?- solveI(search(X, [10,20,30])).   % X = 30 ; X = 20 ; X = 10 ; no

Extra arguments can track the computation, returning with each solution the goals it resolved (for debugging), and bound it, decrementing a counter at each step and failing when it runs out (to prune long computations):

% solveT(+Goal, -Trace, +SizeBound)
solveT(G, T, B) :- solveT(G, T, B, _).
solveT(true, [], N, N) :- !.
solveT((A, B), L, IN, ON) :- !,
    solveT(A, LA, IN, ON1),
    findall((X, B), member(X, LA), LL),
    solveT(B, LB, ON1, ON),
    append(LL, LB, L).
solveT(G, [G|T], I, O) :-
    I > 0, !, clause(G, B), I2 is I-1, solveT(B, T, I2, O).

?- solveT(search(X, [10,20,30]), T, 2).
% X = 10, T = [search(10,[10,20,30])] ;
% X = 20, T = [search(20,[10,20,30]),search(20,[20,30])] ;
% no                                    X = 30 would need a third step

Check your understanding