Blog › ICP guides

Prolog developer on retainer: SLD resolution, cut semantics, clause ordering, and Prolog on monthly retainer

October 3, 2026 · ~14 min read

A Prolog developer was maintaining a natural language processing library for a university linguistics research system in SWI-Prolog. The library’s central parsing predicate, parse_noun_phrase/2, recognized noun phrase structures in tokenized sentence input. The predicate had three clauses: the first matched simple noun phrases (a determiner followed by a noun), the second matched noun phrases with a prepositional phrase complement (determiner, noun, then a parse_pp/2 subcall), and the third was a bare-noun catch-all for pronouns and proper nouns. The second clause ended with a cut (!) to commit after a successful prepositional phrase parse — preventing redundant backtracking to the third catch-all clause when a full NP-PP structure had already been found. This structure had been in production for two years without issue.

The developer added support for noun phrases with embedded relative clauses — a pattern the existing clauses did not cover, needed for processing complex academic text. The new clause was inserted above the existing three, making it the first clause Prolog would try for every parse_noun_phrase/2 call. The clause attempted to match the relative-clause pattern; if it succeeded, it returned the parse result; if it failed, Prolog should backtrack and try the next clause in order. The expected behavior: try relative-clause NP first, fall through to the original three patterns on failure.

What actually happened: for inputs that were ambiguous between the relative-clause pattern and the NP-PP pattern, the new first clause would sometimes fail (producing a slightly different parse tree), Prolog would backtrack to the second original clause (NP-PP), and that clause would succeed and execute its ! — cutting off the third clause and any alternatives below it. For inputs where the correct parse was the bare-noun catch-all (clause 3), but the NP-PP clause (clause 2) could partially unify with the input before ultimately failing further down the call stack, the cut was never exercised, so those worked correctly. But for five specific relative-clause inputs, the interaction between the new first clause failing and the cut in the second clause committing produced parse failures that returned false for sentences the grammar check downstream knew were well-formed. Parse failures: 5 → 0 after restructuring parse_noun_phrase/2 using Prolog’s if-then-else construct (-> ;) to express the mutual exclusion explicitly, removing the implicit cut dependency.

The reason this class of bug is systematically invisible in Prolog is that the cut operator is a control-flow primitive whose effect spans the entire parent goal’s choice context. Adding a new clause above an existing cut-bearing clause does not change the cut’s semantics within its clause, but it changes the clause ordering context in which that cut executes — altering the set of alternatives the cut eliminates and the set of inputs for which those alternatives were reachable. There is no static warning, no type error, and no runtime diagnostic: the cut simply commits and the missing alternative does not surface unless a test case specifically exercises the new clause’s failure path in a context where the cut-bearing clause also succeeds.

Prolog: logic programming, SLD resolution, and the Edinburgh lineage

Prolog (Programming in Logic) was designed by Alain Colmerauer and Philippe Roussel at the University of Marseille in 1972, building on work by Robert Kowalski at the University of Edinburgh on the logical foundations of automated theorem proving. The name expresses the core idea: a Prolog program is a logical theory expressed as Horn clauses, and running the program is performing proof search over that theory. The Edinburgh Prolog system, implemented by David Warren (who also designed the WAM, the Warren Abstract Machine, the standard compilation target for Prolog systems), established the syntax and operational semantics that became ISO Prolog in 1995. SWI-Prolog, developed by Jan Wielemaker at the University of Amsterdam, is today’s most widely used open-source Prolog implementation, with a large library ecosystem and native support for constraint logic programming, multi-threading, and a module system.

The execution model is SLD resolution (Selective Linear Definite clause resolution). A Prolog program consists of facts — unconditional assertions such as parent(tom, bob). — and rules — conditional assertions such as ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).. A query is a goal presented to the interpreter: ?- ancestor(tom, Who). Execution proceeds by selecting the leftmost unsolved goal, finding a clause whose head unifies with that goal, substituting variables according to the unifier, and replacing the goal with the clause body. When multiple clause heads unify with the current goal, Prolog creates a choice point and tries the first matching clause; if execution fails, Prolog backtracks to the most recent choice point and tries the next matching clause. This is depth-first, left-to-right search: depth-first because Prolog fully explores each clause body before trying alternative clauses, and left-to-right because goals within a body are solved in order from left to right.

Unification is the operation that drives this search. When Prolog tries to unify goal foo(X, b) with clause head foo(a, Y), it produces the substitution {X = a, Y = b}, which is the most general unifier. Variables in Prolog are logic variables: they start unbound and become bound when unified; a bound variable cannot be rebound (within the same branch of search). Backtracking undoes bindings by restoring the variable state from the choice point. The WAM implements unification using a trail: when a variable is bound during forward execution, the variable is pushed onto the trail so that backtracking can unbind it.

The cut operator (!) is Prolog’s escape from the search. When Prolog executes a !, it discards all choice points created since the parent predicate was first called — specifically, the choice points between the current clause and the parent goal’s initial choice point. After a cut, backtracking past the cut causes the parent predicate to fail immediately rather than trying the next clause. This makes cut powerful for expressing deterministic predicates (predicates where only one answer is correct and trying alternatives would be redundant or incorrect), for preventing unwanted search, and for encoding mutual exclusion between clause patterns. The if-then-else construct (Cond -> Then ; Else) is equivalent to: try Cond; if it succeeds, commit to Then (implicitly cutting the Else branch); if it fails, use Else. The -> is a soft cut that only cuts the choice points within the conditional, not the parent predicate’s clause choice points — which is the key difference between replacing a bare ! with -> ;.

DCG rules, dynamic predicates, and constraint logic programming

Definite Clause Grammars (DCG) are a syntactic shorthand for writing parsers directly in Prolog. The DCG notation np --> det, noun expands to a pair of standard Prolog clauses that thread a difference list through the parser, connecting the input token sequence before parsing with the sequence remaining after parsing, without explicit list arguments in the rule body. DCG rules compile to Prolog clauses with two extra hidden arguments: np(S0, S) :- det(S0, S1), noun(S1, S). where S0 is the input list before the NP and S is the remainder after. DCG rules are directly debuggeable using SWI-Prolog’s tracer because they are just Prolog clauses with a regular clause structure. The interaction of DCG rules with cut is identical to the interaction of regular Prolog clauses with cut: a ! inside a DCG rule prevents backtracking to the next DCG alternative for the same non-terminal, and adding a new DCG alternative above an existing cut-bearing rule produces the same class of ordering bug as adding a new regular clause.

Left recursion in DCG rules is a structural bug, not a data-dependent one. The rule np --> np, pp (a noun phrase is a noun phrase followed by a prepositional phrase) is left-recursive: the first goal in the body is the same non-terminal as the head. When Prolog tries to solve np, it calls the left-recursive rule, which immediately tries to solve np again, which calls the left-recursive rule, which immediately tries to solve np again — infinite recursion before consuming any input, ending in a stack overflow. Left recursion is a fundamental incompatibility between Prolog’s top-down, depth-first search and left-recursive grammars. The fix is to eliminate left recursion by rewriting as right recursion (np --> det, noun, opt_pp where opt_pp --> pp and opt_pp --> []) or by using operator-precedence parsing techniques. Left-recursive DCG bugs produce immediate, reproducible stack overflows on any input, making them easier to diagnose than cut-ordering bugs but equally time-consuming to fix because the grammar restructuring must preserve the original parse-tree semantics.

The assert/retract family of predicates (assertz/1, asserta/1, retract/1, abolish/1) allows Prolog programs to modify the clause database at runtime. assertz(Clause) adds a clause at the end of the predicate’s clause list; asserta(Clause) adds it at the beginning. This is used for memoization (caching computed results to avoid redundant recomputation), for accumulating results across backtracking points, and for building knowledge bases dynamically. In multi-threaded SWI-Prolog, the global dynamic predicate database is shared across threads, and retract/retractall operations are not automatically atomic with the predicate calls that read the clauses they retract. A retainer bug in this category: thread A calls a predicate, thread B retracts a clause from that predicate between thread A’s clause selection and its execution, and thread A holds a reference to the now-retracted clause via an internal clause reference. SWI-Prolog’s database operations are individually atomic (a single assert or retract is not interleaved with another), but sequences of operations are not, and thread A may execute a clause that thread B has concurrently retracted.

Constraint Logic Programming extends Prolog by adding constraint solvers over specific domains. CLP(FD) — constraint logic programming over Finite Domains, the standard in SWI-Prolog via the clpfd library — allows arithmetic constraints such as X + Y #= 10, X #> 3 to be stated declaratively and solved by constraint propagation rather than generate-and-test. A retainer bug in CLP(FD): a constraint set is underconstrained, producing a residual constraint network rather than a unique solution; the developer expects a single integer binding but receives a domain-constrained variable; downstream code that checks X =:= Expected (arithmetic equality) fails because X is still a domain variable rather than a ground integer. The fix is adding a labeling step (label([X])) to trigger search over the domain, or adding a tighter constraint. Work log entry: “solve_assignment/3: CLP(FD) constraints underconstrained; Worker variable retained domain 1..5 rather than ground value; Worker =:= ExpectedID threw type_error(evaluable, ...); fix: added label([Worker]) after constraints; exceptions: 4 → 0; 2h.”

Typical Prolog retainer work and what it looks like in a work log

Clause ordering bugs are the largest category of Prolog retainer work that produces no visible artifact. The pattern always follows the same shape: a predicate has multiple clauses; one clause contains a cut to commit after a successful match; a developer adds or moves a clause; the cut’s implicit commitment now eliminates an alternative that was previously reachable. The predicate compiles without error. The tests that existed before the change still pass, because they were written for the pre-change clause ordering. The new test cases for the new clause pass or fail based on whether the new clause’s inputs also happen to trigger the cut-bearing clause. The regression only surfaces for inputs that (a) fail the new clause and (b) succeed the cut-bearing clause and (c) would have succeeded a clause eliminated by the cut, which is a three-way conjunction that may be infrequent in the test suite. Work log entry: “parse_noun_phrase/2: new clause 1 (relative-clause NP) inserted above existing clause 2 (NP-PP with cut); for inputs matching relative-clause NP pattern that then fail (tokenizer boundary mismatch), Prolog falls to clause 2 (NP-PP), which succeeds and executes !, cutting clause 3 (bare-noun catch-all); five inputs with relative-clause NPs returned false; fix: replaced ! in clause 2 with parse_pp(S,R) -> result(NP, S, R) ; fail; parse failures: 5 → 0; 2.5h.”

Cut misuse producing incorrect determinism is the second category. A predicate is written with a cut after the first clause to express mutual exclusion — “if the first clause matches, do not try the others.” But the first clause is not actually exclusive: there exist inputs for which both the first clause and a later clause should produce correct results, and the downstream consumer can use either. The cut eliminates the second correct answer. This manifests as a predicate that returns one correct answer when asked for all solutions via findall or bagof, but the caller expected two or more. Work log entry: “classify_token/2: cut after first clause prevents returning second match for tokens that are valid both as keyword and identifier; findall(C, classify_token(Token, C), Cs) returns [keyword] when caller expected [keyword, identifier]; 7 classification errors in multi-match contexts; fix: removed cut from first clause; classifications: 7 wrong → 0; 3h.”

Negation-as-failure bugs are the third category. The \+ (not provable) operator succeeds if its argument fails and fails if its argument succeeds. This is not classical logical negation: \+ member(X, [a,b,c]) does not mean “X is not a member of [a,b,c]” for an unbound X; it means “the call member(X, [a,b,c]) fails”. If X is unbound, member(X, [a,b,c]) succeeds by binding X to a, so \+ fails, and X is still unbound after the call because \+ does not propagate bindings made inside its argument. A developer who writes \+ violates_constraint(X), process(X) expecting X to be bound inside process/1 will find X is unbound. Work log entry: “validate_entry/1: uses \+ invalid_format(Entry) with Entry partially bound; invalid_format/1 instantiates a subterm that \+ then discards; downstream predicate receives partially unbound term and throws instantiation_error; 6 validation exceptions; fix: moved format check to after full instantiation; exceptions: 6 → 0; 1.5h.”

SWI-Prolog module system visibility bugs are the fourth category. SWI-Prolog uses a module system where each file is optionally a module with an explicit export list. A predicate defined in module A and not exported is not visible to module B by default; calling it from B requires the qualified call syntax a:predicate(Args). Retainer bugs in this area: a helper predicate is defined without being added to the module’s export list; a refactor moves a predicate from one module to another without updating all call sites; a module redefines a library predicate with the same name (creating a local definition that shadows the library import). In each case, the symptom is an existence_error(procedure, Name/Arity) exception at runtime, which is clear to diagnose but can require searching across module boundaries to locate the missing export or the call site that needs the qualified form. Work log entry: “util:normalize_term/2: moved from common.pl to util.pl but common.pl module export list not updated to import from util; three call sites in parser.pl and checker.pl receive existence_error(procedure, normalize_term/2); fix: added :- use_module(util, [normalize_term/2]) to common.pl; errors: 3 → 0; 1h.”

How HourTab tracks Prolog developer retainer hours

Prolog retainer work is invisible by the same mechanism that makes clause ordering bugs dangerous: the Prolog compiler sees no inconsistency between a predicate with three clauses and one cut, and the same predicate after a new first clause is inserted. The clause list is syntactically valid. The cut is syntactically valid. The SWI-Prolog type checker has nothing to flag. The WAM generates correct bytecode for each individual clause. The bug only manifests during execution, for specific inputs, when the combination of clause ordering and cut placement produces an unexpected pruning of the search tree. The symptom — a parse failure for a small fraction of inputs — is easy to misattribute to the input itself being grammatically ambiguous or malformed, which delays diagnosis.

The work log needs to name the mechanism: which predicate, which clause, where the cut was, which alternative was eliminated, what the observable symptom was (parse failure count, exception type, wrong answer returned), and what the fix was. A log entry that says “fixed Prolog parsing bug, 2.5h” is not auditable. A log entry that says “parse_noun_phrase/2: cut in clause 2 (NP-PP pattern, after parse_pp/2 subcall) committed on NP-PP success, cutting clause 3 (bare-noun catch-all) and any alternatives inserted below; new clause 1 (relative-clause NP) added above without repositioning cut; five inputs with relative-clause NP pattern returned false; fix: replaced ! in clause 2 with -> ; conditional; parse failures: 5 → 0; 2.5h” is auditable.

HourTab gives Prolog developers a public retainer-hours URL they send to clients — university natural language processing labs, legal-tech companies building contract analysis tools in Prolog, knowledge graph platforms using Prolog as their inference engine, and configuration management systems that use Prolog for constraint satisfaction. For Prolog retainers, each work log entry should name the mechanism: which predicate, which clause, where the cut was placed, which choice points it eliminated, what inputs triggered the regression. Comparative context: Prolog retainer work has structural overlap with other logic and functional paradigms — Scheme retainers share the characteristic that both Scheme closures and Prolog cuts encode implicit control-flow commitments that interact unexpectedly with code insertions: a Scheme closure captures a binding cell rather than a value, and a Prolog cut commits a choice point rather than a clause — in both cases, the semantics of the existing code change when new code is inserted nearby without updating the commitment; Erlang retainers cover pattern-matching clause ordering in function definitions, where adding a new pattern clause above an existing catch-all changes which inputs reach the catch-all, an ordering sensitivity directly analogous to Prolog’s clause-ordering semantics; and Haskell retainers involve type class instance resolution ordering, where an overlapping instance added to a module can silently shadow an existing instance in a way that the compiler may or may not warn about, depending on the language extension in use — a resolution-ordering sensitivity that is structurally analogous to Prolog’s clause-ordering sensitivity, expressed at the type level rather than the term level.

FAQ: Prolog developer retainers