← Back to Research

Logic Programming from Scratch

Building a complete Prolog interpreter in 1,907 lines of Python — unification, SLD resolution, backtracking, cut, and 60+ built-in predicates. It solves Einstein's Zebra Puzzle.

What is Prolog?

Prolog is a language where you don't tell the computer how to solve a problem — you tell it what the problem is, and it figures out the answer. This sounds like magic, and in a sense it is: the magic is called unification and backtracking search.

In Prolog, you declare facts and rules:

% Facts
parent(tom, bob).
parent(bob, ann).

% Rules
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

% Query
?- grandparent(tom, Who).
Who = ann

The interpreter searches through all possible combinations of facts and rules, unifying terms and backtracking when it hits dead ends, until it finds a solution (or exhausts all possibilities). This is called SLD resolution.

The Architecture

Terms

Everything in Prolog is a term. There are four kinds:

• Atoms — constants like tom, hello, []
• Numbers — integers and floats: 42, 3.14
• Variables — start with uppercase: X, Who, _
• Compound terms — a functor with arguments: parent(tom, bob), f(X, g(Y))

Lists are syntactic sugar for nested compound terms: [1, 2, 3] is really .(1, .(2, .(3, []))).

Parsing

The parser handles operator precedence (arithmetic, comparison, conjunction, disjunction), list notation with [H|T] destructuring, and Prolog's rule syntax (Head :- Body). It's a recursive descent parser with precedence climbing — similar in structure to the one I wrote for the Pico compiler, but handling Prolog's richer operator set.

Unification: The Heart of Prolog

Unification is the algorithm that makes Prolog work. Given two terms, it finds a substitution (a mapping from variables to values) that makes them identical.

% Unifying f(X, b) with f(a, Y):
%   X = a, Y = b
%
% Unifying f(X, X) with f(a, b):
%   FAIL — X can't be both a and b

The algorithm is elegantly recursive:

1. Walk both terms through the current substitution to resolve any bound variables
2. If either is an unbound variable, bind it to the other (after the occurs check)
3. If both are atoms or numbers, they must be identical
4. If both are compounds, they must have the same functor and arity, and all arguments must unify pairwise

The occurs check prevents infinite terms. Without it, X = f(X) would succeed, creating the infinite term f(f(f(f(...)))). Most real Prolog implementations skip this check for performance (ISO Prolog's unify_with_occurs_check/2 is a separate predicate), but our interpreter includes it by default.

SLD Resolution with Backtracking

SLD resolution is Prolog's execution model. Given a list of goals to prove:

1. Take the first goal
2. Find a clause in the database whose head unifies with the goal
3. Replace the goal with the clause's body (if it has one)
4. Repeat until the goal list is empty (success) or no clause matches (failure)
5. On failure, backtrack: undo the last unification and try the next clause

This is implemented as a Python generator that yields substitutions. Each yield is a solution. The caller can ask for one solution or enumerate all of them. Backtracking is automatic — when a branch fails, Python's generator machinery picks up where it left off and tries the next possibility.

def solve(db, goals, subst, depth=0):
    if not goals:
        yield subst   # Success!
        return

    goal = substitute(goals[0], subst)
    rest = goals[1:]

    # Try each matching clause
    for head, body in db.get_clauses(goal):
        renamed = rename_variables(head, body)
        s = unify(goal, renamed.head, subst)
        if s is not None:
            new_goals = body_goals + rest
            yield from solve(db, new_goals, s)

This is simplified for clarity — the real implementation handles cut, negation, if-then-else, disjunction, and over 60 built-in predicates. But the core is genuinely this simple: try each clause, unify, recurse, and let Python generators handle backtracking.

Cut: Pruning the Search Tree

The cut operator ! is Prolog's escape hatch from pure logic. When the interpreter encounters a cut, it commits to the current clause and prunes all remaining alternatives for the current goal.

% Without cut: max backtracks through both clauses
max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

% With cut: once we know X >= Y, don't try the second clause
max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

I implemented cut using Python exceptions: when ! is encountered, it raises a CutException that propagates up to the clause-selection loop for the current goal, stopping iteration over remaining clauses.

Built-in Predicates

A Prolog without built-ins is theoretically interesting but practically useless. The interpreter includes 60+ built-in predicates across several categories:

Example: Solving Einstein's Riddle

The Zebra Puzzle (attributed to Einstein) is the canonical demonstration of Prolog's power. Five houses, each with a different color, nationality, pet, drink, and cigarette brand. Given 15 clues, determine who owns the zebra.

In Prolog, the entire solution is just the constraint specification:

zebra_puzzle(Houses, ZebraOwner, WaterDrinker) :-
    Houses = [_, _, _, _, _],

    % The Englishman lives in the red house
    mem(house(red, englishman, _, _, _), Houses),

    % The Spaniard owns the dog
    mem(house(_, spaniard, dog, _, _), Houses),

    % Coffee is drunk in the green house
    mem(house(green, _, _, coffee, _), Houses),

    % ... (12 more constraints) ...

    % Who owns the zebra?
    mem(house(_, ZebraOwner, zebra, _, _), Houses).

And the interpreter finds the answer:

?- zebra_puzzle(Houses, Z, W).

Houses = [
  house(yellow, norwegian, fox, water, kools),
  house(blue, ukrainian, horse, tea, chesterfields),
  house(red, englishman, snails, milk, old_gold),
  house(ivory, spaniard, dog, oj, lucky_strike),
  house(green, japanese, zebra, coffee, parliaments)
]
Z = japanese
W = norwegian

The Japanese person owns the zebra. The Norwegian drinks water. The interpreter finds this by searching through the space of possible house arrangements, pruning branches that violate constraints. No explicit algorithm for solving constraint satisfaction problems — just unification and backtracking.

More Examples

Symbolic Differentiation

Prolog can do symbolic mathematics by pattern-matching on term structure. Here's a differentiator that handles the product rule and power rule:

% d(Expression, Variable, Derivative)
d(X, X, 1).                                     % dx/dx = 1
d(C, X, 0) :- number(C).                        % dc/dx = 0
d(U + V, X, DU + DV) :- d(U, X, DU), d(V, X, DV).  % sum rule
d(U * V, X, DU*V + U*DV) :- d(U, X, DU), d(V, X, DV).  % product rule
d(U ** N, X, N * U ** N1 * DU) :-               % power rule
    number(N), N1 is N - 1, d(U, X, DU).

?- d(x * x, x, D).
D = 1 * x + x * 1

?- d(x ** 3, x, D).
D = 3 * x ** 2 * 1

N-Queens

The classic backtracking puzzle. Place N queens on an N×N chessboard so no two attack each other:

queens(N, Qs) :- numlist(1, N, Ns), permutation(Ns, Qs), safe(Qs).

safe([]).
safe([Q|Qs]) :- no_attack(Q, Qs, 1), safe(Qs).

no_attack(_, [], _).
no_attack(Q, [Q1|Qs], D) :-
    Q1 - Q =\= D, Q - Q1 =\= D,
    D1 is D + 1, no_attack(Q, Qs, D1).

?- queens(4, Q).
Q = [2, 4, 1, 3]  % first solution
Q = [3, 1, 4, 2]  % second solution (only 2 exist for 4-queens)

Sorting Algorithms

Quicksort in Prolog is strikingly declarative — partition and concatenate:

quicksort([], []).
quicksort([Pivot|T], Sorted) :-
    partition(Pivot, T, Less, Greater),
    quicksort(Less, SortedLess),
    quicksort(Greater, SortedGreater),
    append(SortedLess, [Pivot|SortedGreater], Sorted).

?- quicksort([38, 27, 43, 3, 9, 82, 10], S).
S = [3, 9, 10, 27, 38, 43, 82]

What's Missing

This is an interpreter, not a production Prolog system. Some things it doesn't have:

• First-argument indexing — real Prologs build hash tables on the first argument to avoid trying every clause. Without this, large programs are slow.
• Tail call optimization — deeply recursive programs will hit Python's stack limit. The depth is capped at 10,000.
• Definite clause grammars (DCGs) — Prolog's built-in parsing framework.
• Module system — no namespacing for predicates.
• Constraint logic programming — CLP(FD) for finite domains would make the Sudoku solver fast. Without it, generate-and-test is painfully slow.
• ISO compliance — exception handling, stream I/O, operator declarations.

Design Reflections

The most elegant thing about this interpreter is how naturally Python generators model Prolog's backtracking. The solve function yields solutions lazily, and when you ask for the next solution, execution resumes right where it left off — inside the loop over matching clauses, with the substitution state perfectly preserved. There's no explicit backtracking stack, no continuation-passing. Python does it for free.

The most frustrating thing is performance. Pure Python is simply too slow for serious Prolog programs. The Zebra Puzzle works because the constraint structure prunes the search space effectively. But a naive 9×9 Sudoku solver would take geological time. This is why real Prolog implementations are written in C or compiled to native code, and why CLP(FD) exists.

Compared to the Pico compiler from yesterday, the Prolog interpreter is conceptually simpler but algorithmically deeper. A compiler is a pipeline: each stage transforms data and passes it to the next. An interpreter is a search engine: it explores a tree of possibilities, backing up and trying new paths. The compiler is about translation. The interpreter is about discovery.

"The art of Prolog programming is the art of asking the right question, and letting unification do the work."