Logic programming: the paradigm and its computational model

1. What is logic programming?

Logic programming (LP) uses mathematical logic for programming: logic is the declarative language in which you describe the problem, and a theorem prover is the machine that solves it. It is Turing complete and the most declarative of the paradigms; modern functional languages borrow some of its techniques. It is used for planning, search, rules and symbolic reasoning. For efficiency and pragmatism, some imperative-like mechanisms are available to control execution (the cut and friends, Lesson 10). Two features set LP apart:

1. computing means establishing in how many ways a goal can be solved: the result is a stream of solutions, found by trial-and-error exploration of a search space;
2. a goal is a relation (0-ary, unary, binary, …) over data that are essentially untyped trees with holes.

Where Prolog comes from. In the late 1960s AI researchers asked how to represent plans. The Stanford school chose declarative representations, which led to knowledge representation; the MIT school chose procedural ones, which led to the functional paradigm. Knowledge-representation languages such as Planner and QA-4 evolved into Prolog (Alain Colmerauer, 1972). Prolog started as a theorem prover and is now the reference LP language; ISO Prolog (1995) is still the standard language and library. After a hype phase it faded from general-purpose programming, but it is back as a basis of symbolic AI, and some of its ideas shaped databases, XML and pattern matching.

Why it is in this course. It covers the paradigm left after OOP and FP, and it feels completely different from Java or Scala: programming becomes searching a space of solutions. It is also a chance to practise polyglot programming: Java or Scala handle the software "in the large" (organisation, operating system, libraries), and Prolog is the engine for data and algorithms that need reasoning or exploration (Lesson 11). The course uses tuProlog, a Java-based Prolog developed at the University of Bologna; the version used in the labs and for every answer in these notes is tuProlog 4.0.3.

A preview: permutations in three paradigms

The imperative version updates the array in place at each call. The Prolog version states what a permutation is: the empty list is a permutation of itself, and a list L has as permutation any list starting with an element H of L followed by a permutation of the rest. The Scala version, a stream of permutations, is directly inspired by the Prolog one.

% member(List, Elem, Rest): Elem is in List, Rest is List without it
member([H|T], H, T).
member([H|T], E, [H|T2]) :- member(T, E, T2).

permutation([], []).
permutation(L, [H|TP]) :- member(L, H, T), permutation(T, TP).

?- permutation([1,2,3], L).
% L = [1,2,3] ; L = [1,3,2] ; L = [2,1,3] ; L = [2,3,1] ; L = [3,1,2] ; L = [3,2,1] ; no

def member[A](l: List[A]): List[(A, List[A])] = l match
  case a :: Nil => List((a, Nil))
  case a :: t => (a, t) :: (for (a2, l2) <- member(t) yield (a2, a :: l2))

def permutations[A](l: List[A]): Iterable[List[A]] = l match
  case Nil => Iterable(List())
  case _ =>
    for
      (a, l2) <- member(l)
      p <- permutations(l2)
    yield a :: p

permutations(List(1, 2, 3)).toList
// List(List(1, 2, 3), List(1, 3, 2), List(2, 1, 3), List(2, 3, 1), List(3, 1, 2), List(3, 2, 1))

// swap(a, i, j) exchanges a[i] and a[j] (not shown in the slides)
static boolean nextperm(int[] a) {   // next permutation in lexicographic order, in place
  int i, k;
  for (i = a.length - 2; i >= 0 && a[i] > a[i + 1]; i--);
  if (i < 0) {
    return false;
  }
  for (k = a.length - 1; a[i] > a[k]; k--);
  swap(a, i, k);
  k = 0;
  for (int j = i + 1; j < (a.length + i) / 2 + 1; j++) {
    swap(a, j, a.length - k - 1);
    k++;
  }
  return true;
}
// from {1,2,3}: [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

A first program

father(abraham, isaac).
father(terach, abraham).
grandfather(GF, GS) :- father(GF, F), father(F, GS).

?- father(abraham, isaac).     % yes
?- father(abraham, terach).    % no
?- grandfather(terach, isaac). % yes
?- father(A, isaac).           % A = abraham
?- grandfather(terach, S).     % S = isaac
?- father(F, S).               % F = abraham, S = isaac ; F = terach, S = abraham

The program is a small logic theory: two axioms and a general rule. A query is a candidate theorem. When it contains variables, Prolog answers with the values that make it true, one per solution. Answers in these notes are written as tuProlog prints them: ; separates the answers you get by asking for another one, and a final no means that asking once more failed. Without that no, tuProlog knew there was nothing left and did not offer to continue.

2. How does resolution work on plain goals?

The course builds the engine in two steps. First, resolution with goals that are bare symbols (no arguments, no variables), like propositions in propositional logic:

Clause  ::= Goal :- Goal1, ..., Goaln      (n ≥ 0)
Program ::= Clause1 ... Clausek            (k > 0)

A clause has the form head :- body. With an empty body it is a fact, written G.; otherwise it is a rule, G :- G1, ..., Gn. A list of goals still to prove is a resolvent.

One step: replace the first goal by a body. From the input resolvent G1, G2, …, Gn, a step is legal if the program has a clause G1 :- G'1, …, G'm; the new resolvent is G'1, …, G'm, G2, …, Gn. With the clauses a. and a :- b, c. the resolvent a, c, d has exactly two successors: c, d (the list shrinks) and b, c, c, d (it grows).

The resolution tree. The first goal may match the heads of several clauses, always considered from top to bottom, so each resolvent can have several children. A resolution succeeds at every leaf with an empty resolvent. The tree may be infinite; Prolog explores it depth-first and left to right, and going back up to try an alternative is called backtracking.

a.           % a clause with empty body is called a "fact"
b.           % multiple copies of rules/facts can occur
b.
b :- z.      % b is the rule "head", z is the "body"
c.           % different clauses can have same "head"
c :- a, c.   % a sort of recursive rule
c :- b.
d :- d.      % .. recall the order of clauses is relevant

?- a.   % yes
?- b.   % yes ; yes ; no
?- c.   % yes ; yes ; yes ; ... forever
?- d.   % never answers

Follow ?- b. by hand. Clause 2 is a fact: the resolvent becomes empty, first solution. Prolog remembers that clauses 3 and 4 were not tried. Asking again, it takes clause 3: second solution. Asking again, clause 4 rewrites b into z, and no clause has head z: that branch fails, and the final answer is no.

Now ?- c. Clause 5 gives a solution at once. On backtracking, clause 6 rewrites c into a, c, clause 1 removes a, and the resolvent is c again: the same situation as at the root. So solutions keep coming forever, and clause 7 (c :- b), which would give two more, is never reached. The set of logical consequences does not depend on the order of the clauses, but which answers you see, and whether the search ends, does.

What can we ask of a resolution? Whether it has a solution (predicative use: we stop at the first); how many solutions it has (stream-like use); whether it terminates (undecidable in general); and what the output of a solution is, and in which order solutions come. With bare symbols the last question has no answer yet.

What is still missing. Facts are like propositional symbols: knowledge taken as true. A rule gives a name (its head) to a composition of goals (its body): name-based abstraction, with recursion. But with bare symbols the family example becomes father_abraham_isaac., father_terach_abraham. and grandfather_terach_isaac :- father_abraham_isaac, father_terach_abraham.: one symbol per fact, no general grandfather rule, no way to ask "who is Abraham's father?". Goals need structure and relations between elements, results need to be explicit, and the language must become Turing complete. The course does it in three moves: structured goals, a stronger matching between goal and head, and a computation state richer than the resolvent. It is the passage from propositional to first-order logic.

% Part 0a
a.
a.
a :- d.
b.
c :- a, b.
c :- c.
?- b.      % yes
?- a.      % yes ; yes ; no
?- c.      % yes ; yes ; yes ; ... forever (first through c :- a, b, then c :- c)
?- a, b.   % yes ; yes ; no
?- c, d.   % never answers: c has infinitely many solutions and d fails after each

% Part 0b
a(1).
a(X) :- b(X), b(X).
b(1).
b(2).
c(X) :- b(X).
c(X) :- b(X), c(X).
?- b(Y).        % Y = 1 ; Y = 2
?- a(1).        % yes ; yes
?- a(Y).        % Y = 1 ; Y = 1 ; Y = 2
?- a(2).        % yes
?- c(1).        % yes ; yes ; yes ; ... forever
?- c(Y).        % Y = 1 ; Y = 2 ; Y = 1 ; Y = 1 ; ... forever
?- b(Y), b(Z).  % Y = 1, Z = 1 ; Y = 1, Z = 2 ; Y = 2, Z = 1 ; Y = 2, Z = 2

3. What are terms, substitutions and unifiers?

In full Prolog, goals are relations between terms, the values of the language. Terms are finite trees with logic variables allowed in the leaves; goals are matched by unification; and the computation evolves a pair, the resolvent plus the substitution collected so far, which is the result.

Goal ::= Predicate | Predicate(Term1, ..., Termn)
Term ::= Variable | Number | Functor | Functor(Term1, ..., Termn)

Predicate and functor names start with a lowercase letter, variables with an uppercase letter or _; both predicates and functors have an arity. The syntax of goals is a subset of that of terms. A term without variables is ground. a is an atom, 21 a number, X a variable; cons(10,cons(20,cons(30,nil))) and student(mario,rossi,1990) are compound ground terms, student(X,Y,Z) a compound non-ground one.

pred(cons(H, nil), H).               % cons/nil as functors
pred(cons(H, T), L) :- pred(T, L).   % what does pred define?
odd(1).                               % 1 is odd
sum(2, 3, 5).                         % 2,3,5 are in the sum relation

?- pred(cons(a, cons(b, cons(c, nil))), X).   % X = c ; no  (pred relates a list with its last element)

Three ways to read a program

Substitutions

A substitution θ = {X₁/T₁, …, X_n/T_n} maps variables to terms, and no T_j may contain one of the X_k. So {X/a(1,Z), Y/10, W/Z} is valid, while {X/a(1,Z), Y/10, Z/W} is not and must be rewritten as {X/a(1,Z), Y/10, W/Z}. The related notions:

• application: p(X,a){X/10} is p(10,a); p(X,a){Y/X} is p(X,a), equivalent to p(Y,a) under that substitution;
• equivalence: {X/Y, Z/10} ≡ {Y/X, Z/10};
• generality: {X/10} is more general than {X/10, Y/2};
• composition: {X/10}{Y/X} ≡ {X/10, Y/10}, while {X/10}{X/5} is impossible;
• instance: p(10,b) is an instance of p(X,b);
• cloning: clone(p(10,X,X,Y)) = p(10,X2,X2,Y2) with X2, Y2 fresh. A clause is cloned every time it is used, so its variables never clash with those of the goal.

The most general unifier

mgu(T₁, T₂) is a substitution θ that is a unifier (θT₁ = θT₂) and is most general: less general unifiers are excluded. It may not exist (⊥); when several seem to exist, they are equivalent. In Prolog you can test it with =, and its opposite with \=:

?- a(1,2) = a(X,Y).                % X = 1, Y = 2
?- a(1,2) = a(X,X).                % no
?- a(1,b(X)) = a(Y,b(Z)).          % Y = 1, Z = X
?- a(X,Y,A,b(W)) = a(Z,Z,B,b(1)).  % Y = X, W = 1, Z = X, B = A
?- p(X,1) = p(2,Y).                % X = 2, Y = 1
?- p(X,1) \= p(2,Y).               % no

The slides write the third mgu as {X/Z, Y/1} and the fourth as {X/Z, Y/Z, W/1, A/B}; tuProlog prints equivalent substitutions with the variables in the other direction. Unification is a symmetric pattern matching: it binds variables to non-variable terms and groups variables together. In the fourth case it binds W to 1 and makes two groups, (X, Y, Z) and (A, B). Pattern matching in Scala binds variables on one side only; this symmetry is what later lets one predicate work in several directions.

Work the fourth one by hand. Same functor a, same arity 4, so unify argument by argument (different functors or arities would fail at once). X with Z: two variables, bind one to the other. Y with Z: now X, Y and Z are one variable under three names. A with B: another group. b(W) with b(1): same functor, descend, W/1. In the second case, a(1,2) = a(X,X), the first argument gives X/1; the second then compares 1 with 2 and fails. Bindings accumulate, and each argument must respect the ones already made.

4. How does Prolog resolution put the two together?

The computation state becomes a pair ⟨resolvent : substitution⟩, starting from ⟨R₀ : {}⟩. A step is legal if G' :- G'1, …, G'm is a clone of a program clause and θ' = mgu(G', G₁) exists:

⟨G₁, G₂, …, G_n : θ⟩ → ⟨(G'₁, …, G'_m, G₂, …, G_n)θ' : θθ'⟩

As before, the transitions form a possibly infinite tree, and a solution is the substitution found at a leaf with an empty resolvent. Of θ only the part that mentions variables of the current resolvent or of the input resolvent needs to be kept: bindings of clone variables that no longer occur anywhere can be dropped.

% with father/2 and grandfather/2 of Section 1
1)  <father(terach, X) : {}>                  -->  <yes : {X/abraham}>
2)  <father(terach, X), father(X, Y) : {}>    -->  <father(abraham, Y) : {X/abraham}>
3)  <grandfather(terach, X) : {}>             -->  <father(terach, F'), father(F', X) : {}>

In (1) the clause is the fact father(terach, abraham), θ' = {X/abraham}, and the resolvent becomes empty. In (2) the same θ' is applied to the rest of the resolvent, giving father(abraham, Y), and must be kept because X occurs in the input. In (3) the clone is grandfather(GF', GS') :- father(GF', F'), father(F', GS'), θ' = {GF'/terach, GS'/X}, and nothing of it needs to be remembered afterwards. Prolog prints the minimal substitution, restricted to the query's variables: here X = isaac.

The engine in a few lines of Scala

The slides make the algorithm explicit with an abstract Scala engine (types and helper operations are left abstract):

trait PrologResolution:
  type Goal
  type Substitution
  type Resolvent = List[Goal]

  case class Clause(head: Goal, body: Resolvent)
  type Program = List[Clause]

  extension (p: Program) def clone: LazyList[Clause]                    // clauses with fresh variables
  extension (r: Resolvent) def apply(s: Substitution): Option[Resolvent]
  def join(s1: Substitution, s2: Substitution): Option[Substitution]    // composition θθ'
  def mgu(g1: Goal, g2: Goal): Option[Substitution]

  case class State(resolvent: Resolvent, substitution: Substitution)

  extension (program: Program)
    def solve(state: State): LazyList[Substitution] = state match
      case State(goal :: goals, subs) =>
        for
          clause <- program.clone
          mgu <- mgu(goal, clause.head).toSeq
          subs2 <- join(mgu, subs).toSeq
          goals2 <- (clause.body ++ goals).apply(subs2).toSeq
          result <- solve(State(goals2, subs2))
        yield result
      case State(Nil, subs) => LazyList(subs)

Every piece of the model is there. The first generator tries the clauses top to bottom, so each clause is a branch of the tree. toSeq turns a missing mgu into an empty branch. The recursion goes deep before moving to the next clause, which is depth-first search. Because the result is a LazyList, solutions are produced on demand, and backtracking is just asking for the next element. An empty resolvent yields the substitution as one solution.

Try it: an SLD stepper

The stepper below runs the same algorithm (it is called SLD resolution) with real unification. Step expands the first pending resolvent; each edge shows the clause used (c3 is clause 3; lib is the library's append or member) and the new bindings of the parent's variables. Clone variables get primes, as in the slides. The program and the query can be edited. The stepper supports pure clauses, lists, arithmetic, comparisons, =, \=, cut and not/1, and stops after 300 steps. Its answers were checked against tuProlog 4.0.3 on the examples of Lessons 9 and 10.

5. How do you query facts?

A program made only of ground facts is a database: the facts of one predicate (name plus arity) form a table, and a ground goal asks whether a tuple is in it. In the trees of the slides, "yes" marks the empty resolvent and "no" a node with no children.

male(isaac).
plus(2,3,5).
plus(1,6,7).
plus(0,0,5).

?- plus(2,3,5).                  % yes
?- male(isaac).                  % yes
?- plus(0,0,0).                  % no
?- plus(2,3,5), plus(1,6,7).     % yes

Existential queries. A goal with variables asks whether there is a substitution that makes it equal to some facts, like a query that selects several tuples. Each fact that unifies with the goal opens one branch, and its unifier is the solution. Composing goals makes Prolog explore combinations, much like several generators in a for-comprehension:

?- plus(0,X,Y).     % X = 0, Y = 5
?- plus(X,Y,5).     % X = 2, Y = 3 ; X = 0, Y = 0
?- plus(X,Y,Y).     % no
?- plus(X,Y,Z), plus(W,K,Z).
% X = 2, Y = 3, Z = 5, W = 2, K = 3 ; X = 2, Y = 3, Z = 5, W = 0, K = 0 ; X = 1, Y = 6, Z = 7, W = 1, K = 6 ;
% X = 0, Y = 0, Z = 5, W = 2, K = 3 ; X = 0, Y = 0, Z = 5, W = 0, K = 0

Universal facts. Variables in a fact are universally quantified, so a fact with variables stands for infinitely many facts. Unifying with it creates bindings for variables of the clone, which are not shown in the answer: plus(0,5,R) internally gives {R/5, X'/5}.

plus(0,X,X).
plus(X,0,X).

?- plus(0,3,3).   % yes
?- plus(0,5,R).   % R = 5
?- plus(3,0,X).   % X = 3        no clash: the clause's X is a fresh clone variable
?- plus(0,0,X).   % X = 0 ; X = 0  one answer per matching clause

Records. Facts can relate structured terms. Here manager, clerk and chief are predicates (unary and binary relations), while person is a functor used as a record:

manager(person(john,smith,1283)).
clerk(person(jim,white,3475)).
clerk(person(george,red,8765)).
chief(person(john,smith,1283), person(george,red,8765)).

?- chief(X, person(Y,Z,8765)).   % X = person(john,smith,1283), Y = george, Z = red

The wildcard _. In a clause it is a variable used only once; in a goal it is a variable whose value we do not want in the answer. Every _ is a different variable. Good practice: never leave a variable that occurs once in a clause (a singleton), write _ instead; it catches copy-and-paste errors in variable names.

p(_,1).
p(1,2).
q(_,a(1,_)).     % the two _ are different variables
r(X,a(1,X)).     % the two X are the same variable

?- p(X,1).         % yes         (X stays unbound, so it is not shown)
?- p(1,Y).         % Y = 1 ; Y = 2
?- p(1,_).         % yes ; yes
?- q(1,a(1,2)).    % yes
?- r(1,a(1,2)).    % no

6. How do you turn functions into relations?

An algebraic data type has a name, a set of values given as "sums of products", and pure functions over them, often recursive. Prolog has no types, so nothing is enforced and the type's name survives only in the names you choose. The values are given by a set of functors, like cons/2 and nil/0. A function f: I₁, …, I_n → O becomes a predicate p(I1,...,In,O) with the output last. Composition becomes a conjunction of goals: h(X) = f(g(X)) becomes h(X,Y) :- g(X,Z), f(Z,Y). Clauses should match on functors where possible.

Booleans

Two atoms (functors of arity 0) are the values; a unary function becomes a binary predicate, a binary one a ternary predicate, and universal facts avoid repeating cases:

b_not(b_true, b_false).
b_not(b_false, b_true).
b_and(B, b_true, B).
b_and(B, b_false, b_false).
b_or(B, b_false, B).
b_or(B, b_true, b_true).

?- b_not(b_false, B).          % B = b_true
?- b_and(b_false, b_true, B).  % B = b_false
?- b_or(b_false, b_true, B).   % B = b_true
?- b_or(b_true, B2, B).        % B2 = b_false, B = b_true ; B2 = b_true, B = b_true
?- b_or(B1, B2, B).            % B2 = b_false, B = B1 ; B2 = b_true, B = b_true

The last two goals are the slide's open questions: they run "backwards" and enumerate the table. Rules then derive the other connectives from b_not and b_and:

b_or(B1, B2, B) :-          % (a or b) = !(!a and !b)
    b_not(B1, NB1), b_not(B2, NB2), b_and(NB1, NB2, NB), b_not(NB, B).
b_implies(B1, B2, B) :-     % a --> b = !a or b
    b_not(B1, NB1), b_or(NB1, B2, B).

?- b_implies(b_true, b_false, O).
%  b_not(b_true, NB1'), b_or(NB1', b_false, O)
%  b_or(b_false, b_false, O)
%  b_not(b_false, NB1''), b_not(b_false, NB2''), b_and(NB1'', NB2'', NB''), b_not(NB'', O)
%  b_not(b_false, NB2''), b_and(b_true, NB2'', NB''), b_not(NB'', O)
%  b_and(b_true, b_true, NB''), b_not(NB'', O)
%  b_not(b_true, O)
%  O = b_false

Peano numbers

Naturals in unary notation: zero, s(zero), s(s(zero)), … Successor is the functor s/1 itself; sum follows a + 0 = a, a + s(b) = s(a + b); product follows a · 0 = 0, a · s(b) = a + a · b. (Prolog also has built-in numbers, Lesson 10.)

succ(X, s(X)).
sum(X, zero, X).
sum(X, s(Y), s(Z)) :- sum(X, Y, Z).
mul(X, zero, zero).
mul(X, s(Y), Z) :- mul(X, Y, W), sum(W, X, Z).
dec(s(X), X).
factorial(zero, s(zero)).
factorial(s(X), Y) :- factorial(X, Z), mul(s(X), Z, Y).

?- succ(s(s(zero)), N).                  % N = s(s(s(zero)))
?- sum(s(s(s(zero))), s(s(zero)), N).    % N = s(s(s(s(s(zero)))))
?- mul(s(s(zero)), s(s(zero)), N).       % N = s(s(s(s(zero))))
?- dec(s(s(zero)), N).                   % N = s(zero)
?- dec(zero, N).                         % no
?- factorial(s(s(s(zero))), N).          % N = s(s(s(s(s(s(zero))))))
?- sum(N, M, s(s(s(zero)))).
% N = s(s(s(zero))), M = zero ; N = s(s(zero)), M = s(zero) ; N = s(zero), M = s(s(zero)) ; N = zero, M = s(s(s(zero)))

Read the rules relationally: "the successor of X is s(X)"; "the sum of X and zero is X"; "the sum of X and the successor of Y is the successor of Z, provided the sum of X and Y is Z". The resolution of the sum shows the answer being built a piece at a time, each binding refining the previous one:

sum(s(s(s(zero))), s(s(zero)), N)
sum(s(s(s(zero))), s(zero), Z')    : {N/s(Z')}
sum(s(s(s(zero))), zero, Z'')      : {N/s(Z'), Z'/s(Z'')} ≡ {N/s(s(Z''))}
yes                                : {N/s(s(Z'')), Z''/s(s(s(zero)))} ≡ {N/s(s(s(s(s(zero)))))}

The same predicate that adds also decomposes, as the last query above shows. The slides also ask about mul(N1, N2, s(s(s(s(zero))))): tuProlog answers N1 = s(s(s(s(zero)))), N2 = s(zero), then N1 = s(s(zero)), N2 = s(s(zero)), and then searches forever. It never reaches 1 · 4: while trying N2 = 2, an inner sum/3 called with two unknown arguments keeps proposing ever larger values for N1, and each is rejected. Relations do not always run in every direction.

enum Nat:
  case Zero
  case S(n: Nat)

object Nat:
  def succ(n: Nat): Nat = S(n)
  def sum(n1: Nat, n2: Nat): Nat = n2 match
    case Zero => n1
    case S(n) => S(sum(n1, n))
  def mul(n1: Nat, n2: Nat): Nat = n2 match
    case Zero => Zero
    case S(n) => sum(n1, mul(n1, n))

@main def mainPeano() =
  import Nat.*
  val one = S(Zero)
  val two = S(S(Zero))
  val three = S(S(S(Zero)))
  println(succ(one))          // S(S(Zero))
  println(sum(two, three))    // S(S(S(S(S(Zero)))))
  println(mul(two, three))    // S(S(S(S(S(S(Zero))))))

Three mapping idioms

A function returning a boolean becomes a predicate with no extra argument: the result is whether the call succeeds. You program only the positive cases.

greater(s(_), zero).
greater(s(N), s(M)) :- greater(N, M).
?- greater(s(zero), s(zero)).      % no
?- greater(s(s(zero)), s(zero)).   % yes

Several outputs need no pair type: f: I → O₁ × O₂ becomes p(I,O1,O2). In general a predicate has many inputs and many outputs.

nextprev(s(N), N, s(s(N))).
?- nextprev(s(s(zero)), Prev, Next).   % Prev = s(zero), Next = s(s(s(zero)))
?- nextprev(zero, Prev, Next).         % no

Several results need no lazy list: a function returning a stream becomes a predicate with many solutions. Always expect a goal to have many solutions.

range(N1, N2, N1).
range(N1, N2, N) :- greater(N2, N1), range(s(N1), N2, N).
?- range(zero, s(s(s(zero))), N).
% N = zero ; N = s(zero) ; N = s(s(zero)) ; N = s(s(s(zero))) ; no

7. How do you program with lists?

A list is built with the functors cons/2 (head and tail) and nil/0: cons(a, cons(b, nil)) is a tree. Predicates match on the functors in separate clauses; the base cases are facts and the recursive cases are rules.

% relates an element E with a list that contains it
element(E, cons(E, _)).
element(E, cons(_, T)) :- element(E, T).

?- element(b, cons(a, cons(b, cons(c, nil)))).    % yes ; no
?- element(a, cons(a, cons(b, cons(c, nil)))).    % yes ; no
?- element(40, cons(a, cons(b, cons(c, nil)))).   % no

Relationally: E is in a list whose head is E; E is in a list whose tail is T, provided E is in T. In the tree of the first query, the root has one child through clause 2, element(b, cons(b, cons(c, nil))). That node has two: clause 1 gives yes, and clause 2 goes on to element(b, cons(c, nil)) and then element(b, nil), where no clause matches: no. The trailing no is the price of the second clause, which stays open after the first answer.

% relates a list with one of its elements
find(cons(E, _), E).
find(cons(_, T), E) :- find(T, E).

% relates a list with one of its elements and its Peano position
position(cons(E, _), zero, E).
position(cons(H, T), s(N), E) :- position(T, N, E).

% relates two lists with their concatenation (similar to append)
concat(nil, L, L).
concat(cons(H, T), L, cons(H, M)) :- concat(T, L, M).

% relates a list and an element with its occurrences
count(nil, E, zero).
count(cons(E, L), E, s(N)) :- count(L, E, N).
count(cons(E, L), E2, N) :- E \= E2, count(L, E2, N).

?- find(cons(a, cons(b, cons(c, nil))), b).                   % yes ; no
?- find(cons(a, cons(b, cons(c, nil))), d).                   % no
?- position(cons(a, cons(b, cons(c, nil))), zero, a).         % yes
?- position(cons(a, cons(b, cons(c, nil))), s(zero), b).      % yes
?- position(cons(a, cons(b, cons(b, nil))), P, b).            % P = s(zero) ; P = s(s(zero)) ; no
?- concat(cons(a, cons(b, cons(c, nil))), cons(d, nil), L).   % L = cons(a,cons(b,cons(c,cons(d,nil))))
?- count(cons(a, cons(a, cons(b, cons(a, nil)))), a, N).      % N = s(s(s(zero))) ; no

The third clause of count needs the test E \= E2, "E and E2 do not unify". Without it, every occurrence could also be skipped, and the predicate would return wrong counts on backtracking.

One predicate, several uses

Because unification is symmetric, the same clauses answer different questions depending on which arguments are variables. The first lab calls this "one code, many purposes":

search(X, cons(X, _)).
search(X, cons(_, Xs)) :- search(X, Xs).

% query
?- search(a, cons(a,cons(b,cons(c,nil)))).   % yes ; no
?- search(a, cons(c,cons(d,cons(e,nil)))).   % no
% iteration
?- search(X, cons(a,cons(b,cons(c,nil)))).   % X = a ; X = b ; X = c ; no
% generation
?- search(a, X).   % X = cons(a,_) ; X = cons(_,cons(a,_)) ; X = cons(_,cons(_,cons(a,_))) ; ... forever
?- search(a, cons(X,cons(b,cons(Y,cons(Z,nil))))).   % X = a ; Y = a ; Z = a ; no
?- search(X, Y).   % Y = cons(X,_) ; Y = cons(_,cons(X,_)) ; ... forever

The tree of search(a, cons(X,cons(b,cons(Y,cons(Z,nil))))) is a single path down the list. At each level clause 1 tries to unify a with the current head: it binds X, fails on b, binds Y, binds Z, and at nil nothing matches. Depth-first order gives the answers X/a, Y/a, Z/a. Generation, with the list unknown, produces ever longer partial lists whose unbound tails are the "holes" of the trees. The same property, called full relationality, is studied in Lesson 10 with the built-in list syntax.

Tail recursion with an accumulator

The lab rewrites count with an extra argument, the count so far. The call to count/4 is the last goal of each rule, so all the work is done on the way down:

count(List, E, N) :- count(List, E, zero, N).
count(nil, E, N, N).
count(cons(E, L), E, N, M) :- count(L, E, s(N), M).
count(cons(E, L), E2, N, M) :- E \= E2, count(L, E2, N, M).

?- count(cons(a,cons(b,cons(c,cons(a,cons(b,nil))))), a, N).   % N = s(s(zero)) ; no
%  count(cons(a,cons(b,cons(c,cons(a,cons(b,nil))))), a, zero, N)
%  count(cons(b,cons(c,cons(a,cons(b,nil)))), a, s(zero), N)
%  count(cons(c,cons(a,cons(b,nil))), a, s(zero), N)
%  count(cons(a,cons(b,nil)), a, s(zero), N)
%  count(cons(b,nil), a, s(s(zero)), N)
%  count(nil, a, s(s(zero)), N)   -->   N = s(s(zero))

It is the same schema as an accumulator loop in Java or a @tailrec helper in Scala. The lab's Scala version does not compile as printed (the accumulator parameter is also called count, which hides the helper); with the parameter renamed it counts correctly.

% Ex 1.2  search2(Elem, List): two consecutive occurrences of Elem (given)
search2(X, cons(X, cons(X, _))).
search2(X, cons(_, Xs)) :- search2(X, Xs).
?- search2(a, cons(c,cons(a,cons(a,cons(d,cons(a,cons(a,nil))))))).   % yes ; yes ; no
?- search2(a, cons(c,cons(a,cons(a,cons(a,nil))))).                   % yes ; yes ; no
?- search2(a, cons(c,cons(a,cons(a,cons(b,nil))))).                   % yes ; no
?- search2(a, L).                % L = cons(a,cons(a,_)) ; L = cons(_,cons(a,cons(a,_))) ; ... forever
?- search2(a, cons(_,cons(a,cons(_,cons(a,cons(_,nil)))))).           % yes ; yes ; yes ; yes ; no

% Ex 4.1  seq(N, E, List): List is N copies of E (given)
seq(zero, _, nil).
seq(s(N), E, cons(E, T)) :- seq(N, E, T).
?- seq(s(s(s(zero))), a, L).     % L = cons(a,cons(a,cons(a,nil)))

Check your understanding