Logic Programming Practice

So You Want to Learn Prolog

Most people approach Prolog expecting it to work like Python with a different syntax. It doesn't. You're not writing algorithms. You're defining a knowledge base and asking it questions. The machine figures out the execution path, which means if your definitions are wrong, it will confidently give you answers that make sense to it and are completely wrong for what you actually need. I spent about three weeks fighting a predicate that returned inconsistent results before I realized the issue wasn't in the query at all. It was in the rule ordering combined with a missing variable binding in a recursive ancestor chain. The program compiled fine. The queries ran fine. The results were wrong about thirty percent of the time depending on the input size. Once I restructured the base case to anchor on ground terms instead of unifying variables, the problem vanished. That kind of thing happens constantly in Logic Programming Practice, and recognizing it as a structural issue rather than a syntax issue is the hard part.

Logic Programming Practice

The core model is simpler than it sounds. You have facts, which are statements that are unconditionally true. You have rules, which are conditional statements expressed as logical implications. You have queries, which ask whether something follows from your knowledge base. The engine uses resolution and unification to traverse your facts and rules to find answers. Here is a minimal family tree. Save this as family.pl: parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(ann, jim).

mother(X, Y) :- parent(X, Y), female(X).
father(X, Y) :- parent(X, Y), male(X).
female(ann).
female(liz).
male(bob).
male(tom).
male(pat).
male(jim).

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

Start the interpreter and load the file, then query: ?- ancestor(tom, X). The engine returns all values of X that satisfy the query by unifying against the facts and traversing the recursive rule. Each press of semicolon requests the next solution through backtracking. This is the fundamental loop. Everything else is variation on this pattern.

For installation, SWI-Prolog is the most accessible option and works on Linux, macOS, and Windows. On Debian-based systems, apt install swi-prolog gets you a working environment in about two minutes. The command-line REPL is fine for learning. For anything serious, use swipl -g consult(file) -t halt for scripting, or the Eclipse IDE if you want debugging and tracing tools built in.

How Unification Actually Works

Unification is the operation that makes logic programming possible, and it is also where most beginners lose track of what the program is doing. It is not assignment. It is pattern matching with side effects on variables. When you write X = hello, X is bound to the atom hello. When you write f(X, a) = f(b, Y), X becomes b and Y becomes a. If the terms cannot be made identical, unification fails and Prolog backtracks to the last choice point. The critical detail is that once a variable is bound, it stays bound within that branch of execution unless you explicitly cut or reuse it. This leads to a counter-intuitive behavior that trips up people coming from imperative languages. Consider this rule:

swap(A, B) :- A = 1, B = 2. If you query swap(X, Y), you get X = 1, Y = 2. If you then query swap(1, Y), you get Y = 2. But if you query swap(X, 2), you also get X = 1. The same rule works bidirectionally because unification goes both ways. This is powerful and it is also dangerous because a predicate that works in one direction may behave unpredictably in another. In practice, I've seen production code fail because someone wrote a predicate that only handled the query direction they tested, not the reverse direction that arose when another predicate called it with different variable binding patterns. The workaround is to think about each predicate in terms of which arguments are inputs and which are outputs. Document that mentally if not in code. Test all four combinations of ground and variable arguments before considering a predicate complete. I usually write a small test block at the bottom of the file and run it with listing/1 to verify all branches.

Backtracking and the Cut

Backtracking is automatic. When a query fails, Prolog rewinds to the most recent choice point and tries the next available clause. This is why you get multiple solutions from a single query without writing any loop constructs. It is also why your program can be orders of magnitude slower than it needs to be, because Prolog is exploring branches you didn't intend it to explore. The cut operator (!) removes choice points. Once a cut is passed, Prolog commits to the decisions made up to that point and will not backtrack across it. This is useful for pruning unnecessary computation, but it is also one of the most misused features in Prolog. Here is the classic mistake. You write a factorial predicate:

factorial(0, 1) :- !.
factorial(N, F) :- N > 0, N1 is N - 1, factorial(N1, F1), F is N * F1. The cut on the first clause prevents the engine from trying the second clause when the input is zero. Without it, Prolog would succeed on the first clause, then backtrack and attempt the second clause with N = 0, fail the N > 0 test, and backtrack further. The cut saves that wasted work. This is the correct use of cut, and it is relatively safe because the two clauses are mutually exclusive by design. Here is the mistake I made early on. I had a predicate that classified items into categories:

classify(X, 'large') :- size(X, S), S > 100, !.
classify(X, 'medium') :- size(X, S), S > 50, !.
classify(X, 'small') :- size(X, S), S =50. It looked correct. It worked for every test case I threw at it. Then I used the predicate in a context where X was a variable and size(X, S) could bind S to different values through backtracking on a different branch. The cuts locked in the first classification and prevented re-evaluation. The predicate returned wrong results silently because the cut committed to a classification before all possibilities were considered. I replaced the cuts with explicit conditions: classify(X, Cat) :- size(X, S), S > 100, !, Cat = 'large'.
classify(X, Cat) :- size(X, S), S > 50, !, Cat = 'medium'.
classify(X, Cat) :- size(X, S), S =50, Cat = 'small'.

Actually no, that still has the same problem in different form. The real fix was to restructure the predicate so the category was determined in a single pass without cuts, using a conditional construct or simply relying on clause ordering with properly constrained goals. The lesson: cuts are a performance optimization, not a logic tool. If your program is wrong without cuts, fix the logic first.

Infinite Recursion and Termination

This is the problem that consumes the most time in my experience. A recursive rule without a proper base case or without structural progress toward the base case will run until the stack overflows or the machine runs out of memory. The ancestor predicate I showed earlier is safe because each recursive call operates on a strictly smaller subproblem: the parent relationship reduces the generational distance. But change it to: related(X, Y) :- parent(X, Y).
related(X, Y) :- parent(X, Z), related(Z, Y).
related(X, Y) :- related(Y, X). This is symmetric, so it should work for finding relatives in either direction. It doesn't. Query related(tom, X) and the engine enters an infinite loop because the third clause keeps generating new goal states that the first two clauses keep satisfying in alternating directions without any ground anchor to terminate the recursion.

The fix is to track visited nodes to prevent cycles: related(X, Y) :- related(X, Y, []).

related(X, Y, Visited) :- parent(X, Y), \+ member(Y, Visited).
related(X, Y, Visited) :- parent(X, Z), \+ member(Z, Visited), related(Z, Y, [Z|Visited]).
related(X, Y, Visited) :- related(Y, X, Visited). Wait, the symmetry clause still creates a cycle through the visited list check. The actual fix requires removing the symmetric clause entirely and instead querying with both argument orders, or restructuring to a directed graph traversal that handles symmetry at the query level, not the rule level. I've seen experienced Prolog programmers miss this distinction because the rule looks logically correct even though it is computationally broken.

Performance Patterns That Matter

Prolog evaluates clauses in order and goals within a clause from left to right. This means the order of literals in a rule body has real performance consequences, not just logical ones. Consider: member(X, [X|_]).
member(X, [_|T]) :- member(X, T). If you query member(a, List), Prolog finds a in the list efficiently. If you query member(X, [a, b, c]), it generates all three elements. Both work correctly. But swap the order of goals in a rule like this:

best_route(Start, End, Route) :- route(Start, End, Route), length(Route, Len), min_len(Len, Route, Best). If route/3 can generate many candidates and min_len/3 filters them, computing length/2 before the filter is wasted work. Putting the cheaper constraint first: best_route(Start, End, Route) :- route(Start, End, Route), length(Route, Len), ...

should come after filtering or computing the metric only on viable candidates. In my own code, reordering goals in a graph traversal predicate reduced query time from about forty seconds to under three seconds on a moderately sized dataset. The logic was identical. Only the evaluation order changed. Another pattern that matters: use \+ (negation as failure) sparingly and only when you are certain the negated goal is fully instantiated. \+ member(X, List) where X is a variable behaves differently than you might expect. It succeeds if X cannot be unified with any element in List, but if X is unbound, the behavior depends on the Prolog implementation and can produce confusing results. I replaced ambiguous negation with explicit checks using ground/1 and conditional constructs in most of my production predicates.

Practical Exercise Structure

Start with small knowledge bases and query them until you understand what the engine is doing. Add one predicate at a time. Trace each query with trace. in SWI-Prolog to watch the proof search step by step. This is not optional if you want to understand why your program behaves the way it does. The trace output is verbose, but it shows you exactly which clauses are being tried, which unifications succeed or fail, and where backtracking occurs. Build a simple database. Family relationships work, but so do routing tables, parsing rules, or constraint satisfaction problems. The domain doesn't matter as much as understanding the mechanism. Once you can write a predicate that correctly handles all four argument binding combinations, you understand more than most people who finish a beginner tutorial. When you are ready for something more substantial, try implementing a Datalog engine. It strips away Prolog's full first-order logic power and gives you a cleaner model for understanding what logic programming actually does under the hood. The constraints are tighter, the semantics are clearer, and the implementation is short enough to write in a single sitting. I found that writing a simple Datalog interpreter taught me more about logic programming than six months of writing increasingly complex Prolog predicates.