Compendium

Prolog — Reference

14 min read

Prolog — Reference

Source: https://www.swi-prolog.org/

Prolog

  • Created: 1972 by Alain Colmerauer with Philippe Roussel at Aix-Marseille II University, France. Name = “Programmation en logique.” Based on first-order predicate logic (Horn clauses) + SLD resolution.
  • Latest stable: SWI-Prolog 10.0.0 (released 2025-12-03; the dominant FOSS implementation). ISO standard: ISO/IEC 13211-1:1995 (core), ISO/IEC 13211-2:2000 (modules — adoption uneven across implementations).
  • Paradigms: Logic / declarative; first-order, with constraint logic programming (CLP) extensions, definite clause grammars, and meta-programming as first-class features.
  • Typing: Dynamically typed, untyped at the language level. Terms are atoms, numbers, variables, compound terms, strings, lists. Mode/determinism declarations (Mercury-style) provide optional static checking; SWI’s library(typedef) is experimental.
  • Memory: GC for general terms (mark-sweep + generational in modern SWI). Stack-based execution: local stack (bindings), global stack (compound terms), trail (backtrack record), control stack (choice points). Tabling adds a memoization table.
  • Compilation: Compiled to a WAM (Warren Abstract Machine) variant — SWI uses ZIP, an extended WAM; SICStus uses standard WAM; Scryer compiles to Rust-hosted WAM. Most have an interactive REPL + ahead-of-time compilation to standalone executables. Mercury is a statically-typed Prolog descendant compiling via C/LLVM/Java/Erlang.
  • Primary domains: Symbolic AI, expert systems, NLP / parsing (DCGs), constraint satisfaction (scheduling, planning), program analysis & verification, knowledge graphs, theorem proving, semantic web (RDF), interactive logic teaching (SWISH).
  • Official docs: https://www.swi-prolog.org/ (SWI), https://www.metalevel.at/prolog (Markus Triska’s The Power of Prolog), https://www.iso.org/standard/21413.html (ISO/IEC 13211-1).

At a glance

Prolog is the only major language where you write what is true rather than how to compute it, and ask the runtime to derive answers. The runtime is a depth-first SLD-resolution engine with backtracking and unification. This is not a niche academic gimmick — it is unbeatable for combinatorial search (CLP(FD) for scheduling/timetabling), grammar-based parsing (DCGs), graph reasoning, and rule-based expert systems. Pure Prolog is logically beautiful; real Prolog is a mix of pure code and impure constructs (!, assert, side effects). Modern style (Markus Triska’s school) prefers staying as pure as possible and using CLP(FD) instead of arithmetic-with-cut whenever feasible.

Getting started

Install:

  • SWI-Prolog (recommended): https://www.swi-prolog.org/Download.html. macOS: brew install swi-prolog. Linux: sudo apt install swi-prolog. Windows: installer. Docker: docker run -it swipl.
  • Scryer Prolog (purist, ISO-conformant, Rust): cargo install scryer-prolog.
  • GNU Prolog: sudo apt install gprolog.
  • SICStus (commercial, used in industry): https://sicstus.sics.se/.
  • Tau Prolog (browser/Node.js): npm install tau-prolog.

Hello world (hello.pl):

:- initialization(main).
 
main :-
    write('Hello, world!'), nl,
    halt.

Run: swipl hello.pl (executes initialization then drops into REPL — halt exits). Or in REPL: ?- write('Hello, world!').

Project layout (typical SWI):

myproj/
  pack.pl              -- pack.pl declares it as a SWI package
  prolog/
    main.pl
    lib_foo.pl
  test/
    test_main.plt      -- plunit tests

Pack manager: ?- pack_install(some_pack). (SWI’s built-in package system). Browse: https://www.swi-prolog.org/pack/list.

REPL. First-class. swipl opens the interactive prompt. ?- consult('myfile.pl'). (or [myfile].) loads a file. ?- listing(my_pred/2). shows source. ?- trace. enables step debugger; ?- spy(my_pred). sets a spy point. SWISH (https://swish.swi-prolog.org/) is a browser-hosted SWI for sharing examples.

Build to executable: swipl --goal=main --stand_alone=true -o myapp -c main.pl.

Basics

Terms (the only data type). Everything is a term:

  • Atoms: foo, 'hello world' (quoted if non-alphanumeric), [], +.
  • Numbers: 42, 3.14, 0xff, 0'a (the character code for ‘a’).
  • Variables: X, _X, _ (anonymous). Start with uppercase or underscore.
  • Compound terms: point(1, 2), parent(tom, bob). The functor is point/2 (name + arity).
  • Lists: syntactic sugar over '.'(Head, Tail) ending in []. [1, 2, 3] = [1 | [2, 3]] = '[|]'(1, '[|]'(2, '[|]'(3, []))).
  • Strings: by default in SWI, "hello" is a string type; in ISO mode, it’s a list of char codes. set_prolog_flag(double_quotes, codes). reverts.

Facts, rules, queries.

% Facts
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
 
% Rule
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
 
% Query (typed at REPL):
?- grandparent(tom, Who).
Who = ann.

:- reads “if.” Comma , is conjunction; semicolon ; is disjunction; arrow -> is if-then.

Unification, not assignment. X = 5 unifies X with 5 (succeeds if X is unbound or already 5; fails otherwise). Once bound, a variable is bound — no reassignment in pure Prolog. =:= is arithmetic equality (2 + 3 =:= 5); == is structural identity.

Arithmetic. is/2 evaluates the right side: X is 2 + 3 * 4. binds X to 14. The right side must be ground (no unbound vars). >/</>=/=</=:=/=\= for comparison. CLP(FD) (use_module(library(clpfd))) replaces is with #=, #>, etc., works bidirectionally, and handles search.

Control flow. Implicit via clause order + backtracking.

  • Conjunction: , (and).
  • Disjunction: ; (or).
  • If-then-else: (Cond -> Then ; Else).
  • Negation as failure: \+ Goal succeeds if Goal fails.
  • Cut: ! commits to choices made so far (no backtracking past it).
  • Failure-driven loop: member(X, List), do_something(X), fail ; true.
  • forall(Cond, Action) — succeeds if Action succeeds for every solution of Cond.

“Procedures” (predicates).

factorial(0, 1) :- !.                   % base case (cut commits)
factorial(N, F) :-
    N > 0,
    N1 is N - 1,
    factorial(N1, F1),
    F is N * F1.

But that’s old-style. Modern Prolog with CLP(FD) and tabling:

:- use_module(library(clpfd)).
:- table fact/2.
 
fact(0, 1).
fact(N, F) :-
    N #> 0,
    N1 #= N - 1,
    F #= N * F1,
    fact(N1, F1).

Strings. SWI defaults to a string type with string_codes/2, string_concat/3, split_string/4. Or atom_string/2, atom_codes/2 to convert. format('~w + ~w = ~w~n', [A, B, C]) is the printf-equivalent.

Collections. Lists are the primary collection. length(L, N), append([1,2], [3,4], L), member(X, L), nth0(I, L, X), msort(L, Sorted) (stable), sort(L, Sorted) (dedup), maplist(Goal, L), foldl(Goal, L, V0, V). Assoc lists (balanced binary trees in library(assoc)), rbtrees, and dicts (SWI extension: _{key: val}) for keyed lookup.

Intermediate

Modules. :- module(my_mod, [exported_pred/2, other/1]). declares the module and its export list. Import: :- use_module(library(lists)). or :- use_module('myfile.pl').. SWI’s modules are robust; SICStus also; ISO module standard exists but is less universally adopted than core ISO.

Error handling. throw(error(type_error(integer, foo), _)). catch(Goal, Catcher, Recovery) catches via unification with Catcher term. ISO standard error terms: type_error/2, domain_error/2, instantiation_error, existence_error/2. Idiomatic: throw structured terms, not strings.

Concurrency primitives. SWI has threads: thread_create(Goal, Id, []), thread_join(Id, Status). Mutexes: mutex_create, with_mutex. Message queues: thread_send_message/thread_get_message — Erlang-style. Engines (engine_create/3) are lightweight coroutines for incremental answer streaming. Most pure-Prolog code is naturally re-entrant; impure code (assert/retract on shared dynamic predicates) needs locking.

I/O. Stream-based: open(File, Mode, Stream), read(Stream, Term) (reads a single Prolog term + period), write/1, format/2, read_string/5, with_output_to/2. SWI’s HTTP library is comprehensive: :- use_module(library(http/http_server)). then http_server([port(8080)]) and define handlers as predicates.

Stdlib highlights (SWI).

  • library(lists) — list ops.
  • library(apply) — maplist, foldl, partition.
  • library(clpfd) — finite-domain constraints (the killer library).
  • library(clpr) / library(clpq) — constraint LP over reals/rationals.
  • library(clpb) — Boolean constraints.
  • library(chr) — Constraint Handling Rules.
  • library(tabling) — memoization (handles left recursion).
  • library(dcg/basics), library(dcg/high_order) — DCG helpers.
  • library(http/...) — HTTP server + client + JSON + REST.
  • library(semweb/...) — RDF triple store, SPARQL.
  • library(plunit) — unit testing.
  • library(pengines) / library(janus) — Python and JS bridges.

Advanced

Memory model. Bindings live on the local stack; compound terms on the global (heap) stack; choice points on the control stack; trail records bindings to be undone on backtrack. GC reclaims unreachable terms on the global stack. garbage_collect/0 triggers manually. Stack overflow on deep recursion → use tail-call optimization (last-call optimization is automatic when you write tail-recursive predicates) or tabling.

Concurrency deep dive. SWI threads share atom + clause databases. Dynamic predicates (:- dynamic(counter/1)) shared across threads need either thread_local (per-thread copies) or external synchronization. Engines are powerful: engine_create(X, between(1, inf, X), E), engine_next(E, A1), engine_next(E, A2). — produces values on demand, like generators. Mutexes + message queues for actor-style code.

FFI. SWI’s C interface: write C code that uses term_t, PL_unify_*, PL_get_*, register foreign predicates. Compiled as shared library, loaded with load_foreign_library/1. For Java: JPL (bidirectional). For Python: Janus (modern, both directions, lets you call Python from Prolog and Prolog from Python). For JS: Pengines + Tau-Prolog for browser. SWI also bundles SDL, OpenGL, RocksDB, Berkeley DB bindings.

Reflection / meta-programming. Prolog’s killer trait. assertz(Clause) / asserta / retract modify the program at runtime. functor(T, Name, Arity) decomposes a term. T =.. [Name | Args] (“univ”) same. copy_term(T, Copy) for fresh variables. call/N invokes a goal-term: call(Goal, X) adds X as argument. term_to_atom/read_term_from_atom for serialization. Operators: :- op(700, xfx, =>). declares custom infix/prefix/postfix operators with precedence — used heavily by DSLs.

Performance tools. ?- profile(Goal). runs SWI’s built-in profiler. ?- statistics. dumps runtime stats. ?- garbage_collect.. Index analysis via ?- jiti_list. (JIT indexing report). set_prolog_flag(optimise, true) enables compile-time optimizations. Tabling transforms exponential queries into polynomial ones — apply judiciously. Compile to QLF (?- qcompile(file).) for fast loading of large libraries.

God mode

Cut (!) — green vs red. ! commits to the current clause and discards alternative choices. Green cut: doesn’t change solutions, only prunes redundant search — purely an optimization. Red cut: changes which solutions are produced (typically because earlier clauses overlap and you rely on order). Red cuts make code harder to reason about; experts prefer if-then-else ((Cond -> Then ; Else)) and once/1 (commits to first solution) to express the same intent more clearly.

DCG (Definite Clause Grammars). Syntactic sugar for parsing/generation:

greeting --> [hello], name.
name --> [world].
name --> [prolog].
 
?- phrase(greeting, [hello, world]).
true.

The --> desugars to predicates with two extra “difference list” arguments threading the input. pushback ({Goal} in a DCG body runs Goal without threading), semantic actions, and call//N make DCGs a serious parser-combinator system. Used for command parsers, log analyzers, even for generating output (run “in reverse” — same grammar parses and unparses).

CLP(FD) — Constraint Logic Programming over Finite Domains. Replaces brute-force generate-and-test with constraint propagation:

:- use_module(library(clpfd)).
 
sudoku(Rows) :-
    length(Rows, 9), maplist(same_length(Rows), Rows),
    append(Rows, Vs), Vs ins 1..9,
    maplist(all_distinct, Rows),
    transpose(Rows, Cols), maplist(all_distinct, Cols),
    Rows = [A,B,C,D,E,F,G,H,I],
    blocks(A, B, C), blocks(D, E, F), blocks(G, H, I),
    maplist(label, Rows).

Solves a 9x9 sudoku in milliseconds. Used in production for scheduling (rail, airline crew), resource allocation, configuration, theorem proving. CLP(R) (reals via simplex), CLP(Q) (rationals exact), CLP(B) (Booleans via BDD).

Tabling (a.k.a. SLG resolution). :- table p/2. makes p/2 memoize answers and detect cycles. Transforms queries that would loop forever (left-recursive) into terminating ones. Foundational for XSB, supported in SWI (since 7.6+) and Yap. Use cases: graph reachability, parsing left-recursive grammars, model checking. Mode-directed tabling (:- table p(_, lattice(min/3))) implements aggregation (shortest path, etc.).

Attributed variables. Hooks the unification machinery: put_attr(Var, Module, Value) attaches data to a variable; attr_unify_hook in your module fires when the variable unifies with anything. This is how CLP(FD), CHR, and freeze/2 are implemented. Lets you build custom constraint systems on top of pure Prolog.

assert/retract for meta-programming. Build code at runtime: assertz((my_pred(X) :- X > 0)). Useful for compiling DSLs, caching computed rules, building lookup tables incrementally. Avoid using as mutable state — it’s slow, breaks logical purity, and is shared across backtracking (changes survive failure). Use arguments + recursion for state instead.

CHR (Constraint Handling Rules). A separate logic for declaratively transforming a constraint store. simpler @ leq(X,Y), leq(Y,X) <=> X = Y. reduces two leq constraints into an equality. Built on attributed variables. Powerful for term rewriting, type inference, constraint propagation custom systems.

Foreign Language Interface — Janus. :- use_module(library(janus)). then ?- py_call(math:sqrt(2), R). calls Python from Prolog. From Python: from janus_swi import query; for r in query("member(X, [1,2,3])"): print(r['X']). Bidirectional, fast (shared address space), opens Prolog to scientific Python ecosystems.

Mercury / Picat / λProlog as descendants. Mercury: statically typed (Hindley-Milner-ish), with mode (input/output) and determinism (det/semidet/nondet/multi/failure/erroneous) declarations. Compiles to fast native via C/LLVM/Java/Erlang. Picat: Prolog + functions + tabling + planner. λProlog: higher-order Prolog with lambdas, used in proof assistants (Twelf, Abella).

Idioms & style

  • Prefer pure code. Pure predicates work in all argument modes (append([1,2], [3], X) and append(X, Y, [1,2,3]) both work). Cuts, side effects, and assert break this.
  • CLP(FD) over is. X #= Y + 1 is bidirectional and constraint-propagating; X is Y + 1 requires Y bound and goes one way. Use CLP(FD) for any integer arithmetic involving search.
  • if-then-else over red cuts. ( Cond -> Then ; Else ) makes the disjunction explicit and unambiguous.
  • once(Goal) when you only want the first solution — clearer than a cut.
  • maplist/foldl/include/exclude over hand-written recursion when the structure fits.
  • Naming: lower_snake_case for predicates and atoms, UpperCase for variables. pred_name/Arity notation when discussing predicates.
  • Argument order convention: (+Input, -Output, ?Bidir) mode prefixes in docs. Conventionally: input args first, output last. Predicates that update a state thread it as (+S0, -S1).
  • DCG over append-heavy code. If you’re doing append(A, B, C), append(C, D, E), you want a DCG.
  • assertion/1, must_be/2 for runtime checks.
  • Formatter/linter: portray_clause for pretty-printing (built-in). library(check) runs static checks. prologmode-emacs + swi-prolog-vscode. No widely-adopted formatter equivalent to gofmt.
  • Expert review focus: (1) Does the predicate work in all argument modes the docs claim? (2) Cuts: red or green — and necessary? (3) Tail-call position for the recursive call — otherwise stack blows up on long lists. (4) Use of assert/retract for state — usually a smell. (5) findall/3 (logical, returns [] on no solutions) vs bagof/3 (fails on no solutions, groups by free vars) vs setof/3 (sorted+deduped) — picking the right one. (6) Indexing — does the predicate’s first arg discriminate clauses (SWI’s JIT indexer relies on this)? (7) Catching too broad: catch(G, _, true) swallows bugs.

Ecosystem

  • Implementations: SWI-Prolog (FOSS, dominant, batteries-included), SICStus (commercial, fastest), Scryer (Rust-hosted, ISO-pure), GNU Prolog (compiles to native via gplc), YAP (Yet Another Prolog, performance-focused), B-Prolog, XSB (tabling pioneer), Tau-Prolog (browser/Node), Trealla.
  • Libraries: CLP(FD) (every serious impl), CHR, DCG, HTTP server stack (SWI is a complete web framework), RDF/SPARQL (library(semweb)), Pengines (run Prolog in browser via JSON-RPC), JPL (Java bridge), Janus (Python bridge), plunit (testing).
  • IDEs / editors: SWI-Prolog IDE (?- prolog_ide), VS Code with vscode-prolog, Emacs prolog-mode, SWISH (browser-based notebook).
  • Notable users: IBM Watson (NLP pattern matching), Erlang’s roots (Joe Armstrong started prototyping in Prolog), Microsoft Office’s grammar checker (historically), NASA clear-air turbulence prediction, Windows NT TCP/IP install was scripted in Prolog, expert-system shops in finance/healthcare, Logtalk (OO layer over Prolog), ZX Spectrum’s “Prolog interpreters” still active.

Gotchas

  • Operator precedence can yield surprising parses. a, b ; c, d is (a, b) ; (c, d) because ; binds looser than ,. Parenthesize when in doubt.
  • is/2 requires ground RHS. X is Y + 1 with unbound Y throws instantiation_error. Use CLP(FD) for symbolic arithmetic.
  • String types vary. SWI’s "hello" is a string by default; ISO/Scryer treat it as a list of char codes. Set set_prolog_flag(double_quotes, codes/chars/atom/string) consistently or use atom_codes/string_codes defensively.
  • assert/retract semantics under backtracking. Asserted clauses persist across backtracking; retracted ones stay retracted even on failure. Confusing for newcomers expecting logical-update semantics. Use bagof/setof/explicit state instead.
  • Cut + disjunction. (a ; b), ! cuts choice points outside the disjunction; (a, !) only cuts within. Subtle. Test both branches.
  • findall returns [] on no solutions; bagof and setof fail. Switching can introduce silent bugs.
  • Singleton variable warnings. foo(X, Y) :- bar(X). warns “Singleton variable: Y” — usually means a typo. Prefix with _ (_Y) to silence intentionally.
  • Tabling and side effects don’t mix. A tabled predicate must be pure; otherwise the cached answers reflect one execution’s side effects. SWI raises permission_error if you table a non-pure predicate, but only if it can detect it.
  • ==/2 vs =/2. = unifies (binds variables); == tests structural identity (no binding, fails if not already identical). X == 5 fails when X is unbound; X = 5 succeeds and binds X.
  • List append-of-bound is O(n) in the first list’s length. Building a list by repeatedly appending is O(n²); use difference lists or DCGs (or accumulator + reverse at the end).
  • Module conflicts. Two modules exporting a same-named predicate require explicit qualification (mod1:foo(X)) when both are imported. SWI usually warns; some impls silently shadow.
  • Indexing only on first argument (in most implementations, by default). For lookup by second arg, SWI’s JIT indexer (set_prolog_flag(jiti, true) — default since 7.x) builds multi-arg indices automatically; older code may have manually transposed args for performance.

Citations

Graph View