PPS-07-Logic-Programming-and-Prolog

1. The Logic Programming Paradigm

Logic Programming (LP) uses mathematical logic as a declarative representation language and a theorem-prover for problem-solving. It is the third major programming paradigm alongside imperative/OOP and functional programming.

Key idea

Computation is about establishing in how many ways a goal can be solved — producing a stream of solutions through trial-and-error exploration of a search space. A goal is a relation over data elements, which are essentially "untyped trees with holes" (terms with logic variables).

Historical Context

Prolog was created by Alain Colmerauer in 1972, evolving from knowledge representation languages (Planner, QA-4). It started as a theorem prover and is now the reference language for LP. ISO Prolog (1995) remains the standard. After an initial hype cycle, Prolog is now fundamental to "symbolic AI" and specific niches where its search-oriented nature shines.

Comparison Across Paradigms

Paradigm	Computation is...	Key mechanism
Imperative (C, Java)	Step-by-step state transformation	Assignment, loops, procedures
Functional (Scala, Haskell)	Expression evaluation	Function application, recursion, pattern matching
Logic (Prolog)	Search for solutions	Resolution + Unification, backtracking

A Preview: Permutations

Compare imperative, functional, and logic implementations of list permutations:

static boolean nextPerm(int[] a) {
  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;
}

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

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).

Editor's note

The Prolog version is the most concise and directly captures the relational essence: "permutation(L, [H|TP]) holds if H is any element of L, T is the rest, and TP is any permutation of T". The member/3 predicate intrinsically generates multiple solutions through backtracking.

2. Resolution (Without Unification)

We start with a simplified resolution system using propositional (0-ary) goals, then extend it with unification. This core abstract syntax is the foundation:

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

A clause with empty body is a fact, written simply as G.
A clause with non-empty body is a rule, written G :- G1,..,Gn.
A list of goals is called a resolvent.

Resolution Step

Given initial resolvent R₀ = G₁, G₂, ..., G_n, a valid computation step is:

G1, G2, ..., Gn  ->  G'1, ..., G'm, G2, ..., Gn

...if there exists a clause G' :- G'1, ..., G'm in the Program and G' = G1.

Resolution Tree

For each resolvent, its first goal may match the head of many clauses (considered top to bottom), so many child resolvents may exist. A resolution succeeds if there is a leaf with an empty resolvent. Going up the tree to find a new solution is called backtracking.

The examiner will ask

Given a small program with facts and rules, draw the resolution tree and identify which branches lead to success and which to failure. What happens when a rule recursively calls itself (like c :- a, c.)?

3. Terms and Unification

To make resolution practical, goals need structure. Prolog introduces terms as the data values and unification as the matching mechanism.

Prolog Terms

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

Predicate and functor names start with a lowercase letter.
Variable names start with an uppercase letter or underscore _.
A term with no variables is called ground.

Terms are trees: cons(10, cons(20, cons(30, nil))) is a compound ground term, while student(X, Y, Z) is a compound non-ground term.

Substitution

A substitution θ = {X₁/T₁, ..., X_n/T_n} maps variables to terms. For example: {X/10, Y/hello}. Applying it to a term replaces variables: p(X, a, Y){X/10, Y/hello} = p(10, a, hello).

Most General Unifier (MGU)

The MGU of two terms T₁ and T₂ is a substitution θ such that θT₁ = θT₂ (they become identical) and it is the most general such substitution.

T₁	T₂	MGU
`a(1, 2)`	`a(X, Y)`	{X/1, Y/2}
`a(1, 2)`	`a(X, X)`	⊥ (no unifier)
`a(1, b(X))`	`a(Y, b(Z))`	{X/Z, Y/1}
`a(X, Y, A, b(W))`	`a(Z, Z, B, b(1))`	{X/Z, Y/Z, W/1, A/B}

Unification is symmetric pattern matching

Unlike pattern matching in FP (which is directional), unification works both ways. It can bind variables on either side, which enables Prolog's distinctive "multiple modes" for the same predicate.

4. Full Prolog Resolution

Combining resolution with unification gives us the full Prolog computation model. The computation state is a pair of resolvent + substitution:

State = <Resolvent : Substitution>

Resolution Step (with Unification)

If G' :- G'1, ..., G'm is a clone of a clause in the program (with fresh variables), and θ' = mgu(G', G₁) exists, then:

<G₁, G₂, ..., G_n : θ> → <(G'₁, ..., G'_m, G₂, ..., G_n)θ' : θθ'>

A solution is the substitution θ at a leaf with an empty resolvent.

Prolog Resolution in Scala

The course slides include an elegant Scala implementation of the Prolog resolution engine that makes the algorithm explicit:

5. Basic Programming: Facts, Rules, Queries

Program as Database

A Prolog program with ground facts acts like a database. A single ground goal queries for a specific tuple:

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

?- plus(2, 3, 5).          % Yes
?- plus(0, 0, 0).          % No

Existential Queries

If the goal has variables, Prolog finds instantiations (substitutions) making it true:

?- plus(0, X, Y).          % {X/0, Y/5}
?- plus(X, Y, 5).           % {X/2, Y/3}; {X/0, Y/0}

When multiple goals are combined, Prolog inherently explores combinations, similar to a for-comprehension:

?- plus(X, Y, Z), plus(W, K, Z).

Universal Facts

Variables in facts are universally quantified. A fact like plus(0, X, X). means "0 plus X equals X for all X":

plus(0, X, X).     % universal fact
?- plus(0, 5, R).  % {R/5}
?- plus(0, 0, X).  % {X/0} (two solutions from cloning)

Wildcard Variables

The anonymous variable _ matches anything and each occurrence is independent. It is good practice to use _ for variables used only once in a clause, avoiding copy-paste errors.

p(_, 1).
p(1, 2).

?- p(X, 1).   % Yes (uses first clause, X unbound)
?- p(1, Y).   % {Y/1}; {Y/2}

Working with Records

Facts can relate structured terms (records), combining predicate names with functors:

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

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

6. Algebraic Data Types in Prolog

Prolog has no type system, but we model data types using functors (constructors) and predicates (functions converted to relations). A function f: I₁,...,I_n → O becomes predicate p(I₁,...,I_n, O).

Booleans

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(B1, B2, B) :- b_not(B1, NB1), b_not(B2, NB2), b_and(NB1, NB2, NB), b_not(NB, B).
b_implies(B1, B2, B) :- b_not(B1, NB1), b_or(NB1, B2, B).

Peano Numbers

Natural numbers encoded as zero, s(zero), s(s(zero)), ... using functors s/1 and zero/0:

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).

factorial(zero, s(zero)).
factorial(s(X), Y) :- factorial(X, Z), mul(s(X), Z, Y).

greater(s(_), zero).
greater(s(N), s(M)) :- greater(N, M).

?- 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))))
?- factorial(s(s(s(zero))), N).        % N / s(s(s(s(s(s(zero))))))

Relational interpretation

"The sum of X and successor of Y is the successor of Z provided the sum of X and Y is Z." This reads as a logical statement, not an algorithm — the same predicate can compute sum, check sum, or find decompositions.

Lists with cons/nil

% Find element in list
find(cons(E, _), E).
find(cons(_, T), E) :- find(T, E).

% Position of element (Peano)
position(cons(E, _), zero, E).
position(cons(H, T), s(N), E) :- position(T, N, E).

% Concatenation
concat(nil, L, L).
concat(cons(H, T), L, cons(H, M)) :- concat(T, L, M).

% Count 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).

7. Built-in Predicates and List Syntax

Standard List Notation

Instead of cons/nil, Prolog uses built-in list syntax with [] for empty list and [H|T] for list construction:

[H1, H2, ..., Hn | T]   % instead of '.'(H1, '.'(H2, ...))
[H1, H2, ..., Hn]       % instead of [H1, H2, ..., Hn | []]

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

position([E|_], zero, E).
position([H|T], s(N), E) :- position(T, N, E).

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

Full Relationality

A predicate is fully relational if all arguments can be either input or output. find/2 can: check membership, enumerate elements, or generate lists containing an element:

?- find([a,b,c], E).       % E/a; E/b; E/c (enumerate)
?- find(L, a).              % L/[a|_]; L/[_,a|_]; ... (generate)
?- join(L, M, [a,b,c]).     % L/[], M/[a,b,c]; L/[a], M/[b,c]; ...

Math Operators

Operator	Meaning	Example
`=/2`	Unification	`?- p(1,2) = p(X,Y). % X/1, Y/2`
`\=/2`	Non-unification	`?- a(1,2) \= a(1,3). % Yes`
`=:=/2`	Numeric equality	`?- 10 =:= 5+5. % Yes`
`=\=/2`	Numeric inequality	`?- 10 =\= 20. % Yes`
`is/2`	Evaluate arithmetic expression	`?- X is 10+20. % X/30`
`>/2, =/2, =`	Numeric comparisons	Both args must be ground (not relational)

Warning

is/2 evaluates the right argument as an arithmetic expression and unifies the result with the left argument. It does not perform unification of terms. Using it where unification is intended is a common beginner mistake.

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

% Non-tail recursive version creates nested is expressions
% ?- sum([10,20,30], S).  -->  S/60

8. Building Algorithms: Tail Recursion, Combinations

Tail Recursion in Prolog

A recursion is tail if the recursive call is the last goal in the body. Prolog, like FP, can optimise tail calls, but with an important difference: Prolog supports tail-recursive foldright-like list construction (using [H|T] unification), which is not possible in FP with immutable structures.

	Non-tail recursive	Tail recursive
sum/2	`sum([],0). sum([H\|T],N) :- sum(T,N2), N is H+N2.` Builds stack, then computes on return	`sum(L,S) :- sum(L,0,S). sum([],S,S). sum([H\|T],N,S) :- N2 is H+N, sum(T,N2,S).` Computes during recursion
join/3	Not shown (less idiomatic)	`join([],L,L). join([H\|T],L,[H\|T2]) :- join(T,L,T2).` Constructs output while recurring (foldright-like but tail!)

Prolog's unique advantage

Foldright-like construction in join/3 is tail recursive because the output list is built incrementally through [H|T2] unification — the variable T2 becomes bound to the tail as the recursion depth increases. This is impossible in pure FP.

Immutability and Sharing

Prolog terms are immutable: they never change. The only declarative "side effect" is unifying a variable (binding it to a term). Structure sharing means the output list in update/4 shares unchanged suffixes with the input:

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

After ?- update([10,20,30,40], 20, 21, L). → L/[10,21,30,40], the output list's tail [30,40] is shared with the input list.

Generating Combinations

The combination of multiple goals inherently generates Cartesian products of solutions:

?- 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

This is the Prolog equivalent of a monadic for-comprehension — member/2 acts like flatMap, generating all combinations.

9. The Cut Predicate

The pervasive branching and backtracking of Prolog is a feature, but sometimes it creates spurious solutions or unnecessary computation. The cut (!) is a zero-ary predicate that prunes the search tree.

Motivation: Merge

% Without cut: spurious solutions
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 identical solutions!)
?- merge([10,20], [5,35], L). % L/[5,10,20,35]; No (spurious failure)

% With cut: clean solutions
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).

What Cut Prunes

Green: successive matching clauses below the current one
Red: pending alternative solutions in goals to the left of ! in the body

Applications

% Computing first index of an element
first_index_of([E|_], E, 0) :- !.
first_index_of([_|T], E, N) :-
    first_index_of(T, E, N2), N is N2 + 1.

% Alternative: separate predicate with cut
first_index_of2(L, E, N) :- index_of(L, E, N), !.

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

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).

The examiner will ask

Given a program with cuts, identify which branches are pruned when a goal is executed. Explain the difference between green cuts (which only prune spurious branches) and red cuts (which change the logical meaning of the program).

10. Term Inspection and Manipulation

Beyond unification, Prolog provides library predicates for inspecting and constructing terms programmatically:

Type Checking

?- var(X).        % Yes (X is unbound)
?- atom(a).       % Yes
?- number(10).    % Yes
?- compound(a(10,20)). % Yes
?- ground(a(10,X)). % No (X is unbound)

Term Comparison

Predicate	Meaning	Example
`T1 = T2`	Unification (binds variables)	`?- a(X,b) = a(10,b). % X/10`
`T1 \= T2`	Non-unification (never binds)	`?- a(X,b) \= a(Y,c). % Yes`
`T1 == T2`	Equality (no binding)	`?- a(X,b) == a(X,b). % Yes`
`T1 \== T2`	Inequality	`?- a(X,b) \== a(10,b). % Yes`
`copy_term(T1, T2)`	Copy with fresh variables	`?- copy_term(a(10,X), Y). % Y/a(10,X1)`

Term Structure

% =.. (univ) converts between term and list
?- p(10, q(20)) =.. L.      % L/[p, 10, q(20)]
?- X =.. [p, 10, q(20)].    % X/p(10, q(20))

% functor and arg extraction
?- functor(p(10,20,30), F, A).  % F/p, A/3
?- arg(2, p(10,20,30), Y).     % Y/20
?- functor(T, p, 3).            % T/p(_, _, _)

String Handling

?- atom_chars(hello, L).       % L/[h, e, l, l, o]
?- atom_codes(hello, L).       % L/[104, 101, 108, 108, 111]
?- atom_concat(aa, bb, X).     % X/aabb
?- number_chars(100, X).       % X/['1','0','0']

Algorithms on Other ADTs

Binary trees using tree/3 and nil/0:

search(tree(_, E, _), E).
search(tree(L, _, _), E) :- search(L, E).
search(tree(_, _, R), E) :- search(R, E).

leaves(nil, []).
leaves(tree(nil, E, nil), [E]) :- !.
leaves(tree(L, _, R), O) :-
    leaves(L, OL), leaves(R, OR), append(OL, OR, O).

N-ary trees using tree/2 with a list of subtrees, or variable-argument tree/1 through =..:

searchV(T, E) :- T =.. [tree, E | _].
searchV(T, E) :- T =.. [tree, _ | L], member(T2, L), searchV(T2, E).

DB-like tables modelled as lists of compound terms:

get_ids([], []).
get_ids([user(ID, _, _)|T], [ID|L]) :- get_ids(T, L).

query([user(ID, N, C)|_], ID, user(ID, N, C)).
query([_|T], ID, Tuple) :- query(T, ID, Tuple).

update([user(ID, _, _)|T], ID, Tuple, [Tuple|T]).
update([H|T], ID, Tuple, [H|Table]) :- update(T, ID, Tuple, Table).

11. Metaprogramming and Metainterpretation

Prolog's metaprogramming capabilities are exceptionally powerful because everything is a term — programs, goals, and data all share the same representation.

Everything is a Term

Prolog syntax is just surface notation for standard terms:

Surface syntax	Internal term
`[A, B, C]`	`'.'(A, '.'(B, '.'(C, '[]')))`
`(A, B, C)`	`','(A, ','(B, C))`
`X = 1`	`'='(X, 1)`
`{ A, B }`	`'{}'(','(A, B))`

Operators and DSLs

Custom operators can be defined with op/3 to create domain-specific notations:

:- op(100, xfx, '~').
N1 ~ N2 :- N1 > N2, !, Delta is N1 - N2, Delta < 0.1.
N1 ~ N2 :- N2 ~ N1.

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

Dynamic Theories

Prolog has a dynamic theory where clauses can be added or removed at runtime:

assert(P).        % Add clause P (on top with asserta, bottom with assertz)
retract(P).       % Remove clause that matches P
retractall(P).    % Remove all matching clauses
clause(Head, Body). % Query for existing clauses

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)).

% First call: caches factorial(3,6)
% Subsequent calls: uses cached result directly

The Vanilla Metainterpreter

A metainterpreter is an interpreter for Prolog written in Prolog. The simplest one captures the core resolution algorithm:

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

This is already functional for user-defined predicates! For built-ins, we extend it:

builtins(['is', '=', '\\=', '==']).

solveB(true) :- !.
solveB((A, B)) :- !, solveB(A), solveB(B).
solveB(G) :- functor(G, F, _), builtins(B), member(F, B), !, call(G).
solveB(once(G)) :- !, once(solveB(G)).
solveB(not(G)) :- !, not(solveB(G)).
solveB(G) :- clause(G, B), solveB(B).

Why metainterpretation matters

Metainterpreters give us control over the execution strategy. We can reorder solutions (by inverting clause order), add tracing, impose resource bounds, implement debugging, or change the search strategy entirely:

% Metainterpreter that inverts solution order
solveI(true) :- !.
solveI((A, B)) :- !, solveI(A), solveI(B).
solveI(G) :-
    findall(c(G, B), clause(G, B), L),
    reverse(L, L2),
    member(c(G, B), L2),
    solveI(B).

% Metainterpreter that tracks computation trace and bounds depth
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).

The examiner will ask

You should be able to explain the vanilla metainterpreter, extend it to handle built-in predicates and control constructs, and describe how to modify it to alter the order of solutions or to track computation traces. Challenge question: how would you implement the cut in a metainterpreter?

Check Your Understanding

Explain the difference between resolution with and without unification. Why is unification necessary for practical Prolog programming?

Without unification (propositional resolution), goals are atomic symbols that either match or don't. With unification, goals have structure (terms with variables), and matching produces a substitution that makes the goals identical. Unification is necessary for expressing relationships between data elements, implementing pattern matching, and producing result bindings.

What is the MGU of a(1, b(X)) and a(Y, b(Z))? Walk through the Martelli-Montanari algorithm.

MGU = {X/Z, Y/1}. The algorithm: decompose a(1,b(X)) = a(Y,b(Z)) gives equations 1=Y and b(X)=b(Z). Decompose b(X)=b(Z) gives X=Z. The resulting substitution is {Y/1, X/Z}.

Given the program: a. b :- z. c :- a, c. Draw the resolution tree for ?- c.

?- c has two matching clauses: c. (fact) gives immediate success. c :- a, c. gives resolvent [a, c]. a. gives resolvent [c], which loops (c matches c :- a, c again). So the tree has a solution (from the fact) and an infinite branch (from the recursive rule).

What does it mean for a Prolog predicate to be "fully relational"? Give an example where this property holds and one where it does not.

A predicate is fully relational if all arguments can serve as either input or output. Example: join/3 is fully relational — it can concatenate two known lists, split a list into all possible pairs, or verify a concatenation. Counter-example: is/2 is not — the right argument must be a ground arithmetic expression; ?- X is 10+Y. throws an error.

Why is join/3 tail-recursive even though it constructs the output list from head to tail (foldright-style)?

Because the output [H|T2] is built through unification: T2 is a fresh variable that becomes bound as the recursion proceeds. The recursive call is the last goal in the body. In FP, this would not be tail-recursive because the "hole" in the output list structure would require a stack frame. Prolog's logical variables make it possible through a mechanism similar to Haskell's lazy evaluation but driven by unification.

Explain what the cut (!) does to the resolution tree. Give an example where a cut changes the logical meaning (red cut) vs only pruning spurious branches (green cut).

The cut prunes all pending branches below the node that generated the clause containing the cut. Green cut example: merge/3 with cut only prunes impossible branches (when one case succeeds, no other case can). Red cut example: first_index_of/2 with cut changes the meaning — without cut it would find multiple positions of the element, with cut it only finds the first one.

Describe the Vanilla metainterpreter and how you would extend it to handle built-in predicates and negation as failure.

solveV(true) succeeds. solveV((A,B)) decomposes conjunctions. solveV(G) looks up a clause with clause(G,B) and recurses. To handle built-ins, we check if the goal's functor is in a list of built-in predicates and use call/1 directly. To handle negation as failure, we use not/1 or implement it as "call the goal, if it fails then succeed (with no bindings)".

What are the three Prolog interpretations (logic, relational, procedural)? Which is the most useful for idiomatic Prolog programming?

Logic interpretation: a program is a logic theory, computing is proving a goal is a theorem. Relational interpretation (most useful): a program is a set of predicates over terms, querying is asking for a relation. Procedural interpretation: a program is a set of procedures, computing is calling predicates. The relational interpretation is most productive because it emphasizes the declarative, multi-directional nature of Prolog predicates.

In this lesson

1. The Logic Programming Paradigm

Historical Context

Comparison Across Paradigms

A Preview: Permutations

2. Resolution (Without Unification)

Resolution Step

Resolution Tree

3. Terms and Unification

Prolog Terms

Substitution

Most General Unifier (MGU)

4. Full Prolog Resolution

Resolution Step (with Unification)

Prolog Resolution in Scala

5. Basic Programming: Facts, Rules, Queries

Program as Database

Existential Queries

Universal Facts

Wildcard Variables

Working with Records

6. Algebraic Data Types in Prolog

Booleans

Peano Numbers

Lists with cons/nil

7. Built-in Predicates and List Syntax

Standard List Notation

Full Relationality

Math Operators

8. Building Algorithms: Tail Recursion, Combinations

Tail Recursion in Prolog

Immutability and Sharing

Generating Combinations

9. The Cut Predicate

Motivation: Merge

What Cut Prunes

Applications

10. Term Inspection and Manipulation

Type Checking

Term Comparison

Term Structure

String Handling

Algorithms on Other ADTs

11. Metaprogramming and Metainterpretation

Everything is a Term

Operators and DSLs

Dynamic Theories

The Vanilla Metainterpreter

Check Your Understanding