Chapter 3: The Engine Room — Unification, Backtracking, and Recursion
Overview
The two previous chapters were concerned with what we write in Prolog — the syntax of facts, rules, and queries, and the way those constructs combine to form a useful knowledge base. This chapter turns attention to how the engine executes what we write. Understanding the execution model is not optional background reading. It is the difference between a programmer who can write Prolog and a programmer who can debug it, optimise it, and reason confidently about why it produces the results it does.
The three mechanisms we examine here — unification, backtracking, and recursion — are not independent features. They are deeply interwoven aspects of a single coherent execution model. Unification is the engine's fundamental operation: the process by which it determines whether two terms can be made identical, and if so, what variable bindings are required to achieve that. Backtracking is what the engine does when a proof attempt fails: it undoes the most recent choice it made and tries a different path. Recursion is how Prolog expresses repetition: instead of loops, a rule refers to itself, and the combination of unification and backtracking ensures the recursion terminates correctly when a base case is reached.
We will also introduce two control predicates that give us direct influence over backtracking: the cut (!) and fail. These are the tools we reach for when the engine's default exhaustive search behaviour is more than the problem requires, and understanding them correctly requires a solid mental model of backtracking first. By the end of this chapter, the execution model will be genuinely clear, and the knowledge base will have grown to include a recursive directory tree mapper and a firewall rule validator — both of which run correctly on the Mint VM.
3.1 Unification: The Engine's Fundamental Operation
Unification is the operation that the Prolog engine performs every time it tries to match a query against a fact or a rule head. It is not assignment, and it is not equality testing in the sense that most languages use those terms. It is something more general than both: the process of finding a substitution — a set of variable bindings — that makes two terms structurally identical.
Two terms unify if they are the same atom, the same number, or if one or both is an uninstantiated variable that can be bound to make them identical, or if they are compound terms with the same functor and arity whose corresponding arguments all unify recursively. That definition is precise but abstract, so let us work through it concretely in the REPL using the unification operator =/2.
Open a fresh REPL session — swipl with no file argument — and try the following:
?- foo(X, bar) = foo(hello, bar).
X = hello.
The engine unifies foo(X, bar) with foo(hello, bar). Both are compound terms with functor foo and arity 2. The engine works through the arguments pairwise. First argument: X (uninstantiated variable) against hello (atom). An uninstantiated variable unifies with anything, so X is bound to hello. Second argument: bar against bar. Identical atoms unify trivially. The overall unification succeeds, and the binding X = hello is reported.
?- foo(X, X) = foo(hello, world).
false.
Here the engine attempts to unify foo(X, X) with foo(hello, world). First argument: X against hello. X is uninstantiated, so it binds to hello. Second argument: X against world. But X is now bound to hello, so the second unification is hello = world, which fails. The constraint that both occurrences of X must represent the same value is automatically enforced by the fact that binding is a global operation within a proof branch — once X is bound to hello, it is hello everywhere in that branch.
?- point(X, Y) = point(3, 4).
X = 3,
Y = 4.
?- point(X, X) = point(3, 3).
X = 3.
?- f(g(X), X) = f(g(2), 2).
X = 2.
That last example is worth pausing on. The engine unifies f(g(X), X) with f(g(2), 2). First argument: g(X) against g(2). These are compound terms with the same functor and arity, so the engine recurses: X against 2. X binds to 2. Second argument: X against 2. X is now bound to 2, so this is 2 = 2, which succeeds. The whole unification succeeds with X = 2. The engine has simultaneously solved two constraints — one nested inside a compound term and one at the top level — and found the single value that satisfies both.
UNIFICATION TRACE: f(g(X), X) = f(g(2), 2)
─────────────────────────────────────────────────────────────────
Step 1: Compare top-level functors
f( ... ) = f( ... ) ✓ same functor, same arity
Step 2: Unify argument 1 — recursively
g(X) = g(2)
└─ g( ... ) = g( ... ) ✓ same functor, same arity
└─ X = 2
X is uninstantiated → X binds to 2 ✓
Step 3: Unify argument 2
X = 2
X is now bound to 2 → 2 = 2 ✓
Result: SUCCESS { X = 2 }
─────────────────────────────────────────────────────────────────
The binding X = 2 was established once (Step 2) and
reused automatically (Step 3). No explicit check required.
One important thing unification does not do is perform arithmetic evaluation. The query ?- X = 1 + 2. does not bind X to 3. It binds X to the compound term +(1, 2), which is how Prolog represents the expression 1 + 2 structurally. Arithmetic evaluation requires the is/2 predicate: ?- X is 1 + 2. binds X to 3. This distinction matters practically and we will return to it in Chapter 4 when we compute values in the context of our knowledge base rules. For now, the key insight is that = is purely structural matching, not evaluation.
Unification underlies every single interaction between the engine and the knowledge base. When we write a query like app(git, Version, _, _), the engine is attempting to unify app(git, Version, _, _) with each app/4 fact in turn. The first fact it tries is app(swi_prolog, '10.2.1', open_source, language_runtime). The engine tries to unify git with swi_prolog — two different atoms, unification fails. It moves to the next fact. Eventually it reaches app(git, '2.45.0', open_source, version_control). It unifies git with git (success), Version with '2.45.0' (success, Version binds), the anonymous variables with open_source and version_control (success, anonymous variables are discarded). The whole unification succeeds. This is exactly the same mechanism, operating at the scale of individual argument positions, that drives every query we have written so far.
3.2 Backtracking: Exploring Every Path
Backtracking is the engine's response to failure. When a proof attempt reaches a point where it cannot proceed — because a unification fails, or because a predicate has no matching clause — the engine does not simply give up. It retreats to the most recent choice point: the last place where it had multiple alternatives and chose one of them. It undoes all the variable bindings made since that choice point and tries the next alternative. If that also fails, it retreats further. If all alternatives at a choice point are exhausted, the choice point is removed and the engine retreats to the one before it. This continues until either a complete proof is found or all possibilities are exhausted.
A choice point is created every time the engine encounters a predicate with more than one matching clause, or more than one fact that could unify with a goal. It is the mechanism that makes multi-solution queries work — when we press ; in the REPL to ask for the next solution, we are instructing the engine to backtrack from the current (successful) state and find the next alternative.
To make this concrete, let us trace through a query against the mint_library.pl knowledge base manually. Consider:
?- depends_on(App, git).
The engine searches the depends_on/2 facts for any fact whose second argument unifies with git. It finds depends_on(vscode, git) — App binds to vscode, second argument git unifies with git, success. This is the first solution: App = vscode. A choice point is left behind, marking the position in the depends_on fact list. When we press ;, the engine backtracks through this choice point, unbinds App, and continues scanning. It finds depends_on(golang, git) — App binds to golang, success. Second solution: App = golang. Another press of ;, another backtrack, depends_on(hypothetical_tool, git) — App binds to hypothetical_tool. Third solution. One more ;, no further matching facts, the query fails, and the REPL reports false to indicate the search space is exhausted.
Now consider a slightly deeper example: the full execution of dependency_status(vscode, Status). The engine attempts the first clause of dependency_status:
dependency_status(App, all_satisfied) :-
installed(App),
\+ dependency_missing(App, _).
App unifies with vscode. The engine must now prove installed(vscode). It attempts app(vscode, _, _, _), finds app(vscode, '1.89.0', proprietary, ide), succeeds. Now it must prove \+ dependency_missing(vscode, _). To evaluate this negation, the engine attempts to prove dependency_missing(vscode, _). It calls depends_on(vscode, Dep), finds depends_on(vscode, git), then checks \+ installed(git). git is installed, so installed(git) succeeds, and \+ installed(git) fails. Backtrack: try depends_on(vscode, curl). curl is installed, \+ installed(curl) fails. No more depends_on(vscode, ...) facts. dependency_missing(vscode, _) has completely failed to find a proof. Therefore \+ dependency_missing(vscode, _) succeeds. The entire first clause succeeds: Status = all_satisfied.
BACKTRACKING TRACE: dependency_status(vscode, Status)
─────────────────────────────────────────────────────────────────
GOAL: dependency_status(vscode, Status)
│
├─ TRY clause 1: dependency_status(App, all_satisfied)
│ App = vscode ✓
│ │
│ ├─ PROVE installed(vscode)
│ │ └─ app(vscode,'1.89.0',proprietary,ide) ✓
│ │
│ └─ PROVE \+ dependency_missing(vscode, _)
│ │
│ │ (engine attempts to PROVE dependency_missing)
│ ├─ depends_on(vscode, git) → \+ installed(git)
│ │ installed(git) succeeds → \+ fails ✗
│ │ BACKTRACK
│ ├─ depends_on(vscode, curl) → \+ installed(curl)
│ │ installed(curl) succeeds → \+ fails ✗
│ │ BACKTRACK
│ └─ no more depends_on(vscode,_) facts
│ dependency_missing FAILS completely
│ therefore \+ dependency_missing SUCCEEDS ✓
│
└─ clause 1 SUCCEEDS: Status = all_satisfied
─────────────────────────────────────────────────────────────────
Backtracking here is in the SERVICE of proving a negative.
The engine exhausts every path before concluding "not provable."
This is backtracking in the service of negation as failure. The engine exhaustively searches for a proof of the negated goal. Only when that search is completely exhausted — every alternative tried and failed — does the negation succeed. This is why \+ is called "negation as failure" rather than logical negation: it is success defined through the absence of proof, not through the presence of a disproof.
The SWI-Prolog graphical tracer provides a visual representation of this search tree. Launch it with gtrace/0 instead of trace/0, then run a query. A window will appear showing the call stack as a tree, with each node representing a goal and the ability to step forward, back, or skip through the execution. For readers who are new to Prolog's execution model, spending twenty minutes stepping through dependency_status in the graphical tracer is one of the most efficient investments of time in the early learning curve.
?- gtrace.
true.
[gtrace] ?- dependency_status(vscode, Status).
Turn off the graphical tracer with nodebug/0 when finished.
3.3 Recursion: The Infinite Mirror
Prolog has no loop constructs. There is no for, no while, no do...until. Repetition in Prolog is expressed through recursion: a rule that calls itself, with a base case that terminates the recursion when the desired condition is reached. This is not a limitation — it is a consequence of the declarative nature of the language, and once the pattern is internalised it becomes natural.
The canonical structure of a recursive predicate in Prolog has two clauses: the base case, which handles the simplest possible input and succeeds without making a recursive call, and the recursive case, which reduces the problem by one step and then calls the predicate on the reduced input. The order matters: the base case must be written first, or at least must be reachable before the recursive case causes infinite regression.
We are going to build a predicate that maps the directory tree of the VM's home folder. This is a genuine recursive problem: a directory contains files and subdirectories, and each subdirectory contains further files and subdirectories, to an arbitrary depth. The only natural way to express this in Prolog is recursively.
Create a new file ~/logic-lab/prolog/directory_tree.pl:
% directory_tree.pl
% Recursive directory tree traversal using SWI-Prolog's filesystem predicates.
% Part I, Chapter 3 - Modern SWI-Prolog (2026 Edition)
:- module(directory_tree, [
list_tree/1,
list_tree/2,
find_files_by_ext/3,
tree_depth/2
]).
:- use_module(library(filesys)).
% list_tree(+RootDir)
% Prints a textual representation of the directory tree rooted at RootDir.
list_tree(Root) :-
list_tree(Root, 0).
% list_tree(+Dir, +Depth)
% Worker predicate: prints the tree with indentation reflecting depth.
list_tree(Path, Depth) :-
exists_directory(Path),
!,
indent(Depth),
file_base_name(Path, Name),
format("[dir] ~w~n", [Name]),
NextDepth is Depth + 1,
directory_files(Path, Entries),
forall(
(member(Entry, Entries), \+ member(Entry, ['.', '..'])),
(
directory_file_path(Path, Entry, FullPath),
list_tree(FullPath, NextDepth)
)
).
list_tree(Path, Depth) :-
exists_file(Path),
indent(Depth),
file_base_name(Path, Name),
format("[file] ~w~n", [Name]).
% indent(+Depth)
% Prints Depth*2 spaces to create visual indentation.
indent(0) :- !.
indent(Depth) :-
Depth > 0,
write(' '),
Depth1 is Depth - 1,
indent(Depth1).
% find_files_by_ext(+RootDir, +Ext, -FilePath)
% True for each file under RootDir with the given extension.
find_files_by_ext(Root, Ext, FilePath) :-
exists_directory(Root),
directory_files(Root, Entries),
member(Entry, Entries),
\+ member(Entry, ['.', '..']),
directory_file_path(Root, Entry, FullPath),
(
exists_directory(FullPath)
-> find_files_by_ext(FullPath, Ext, FilePath)
; file_name_extension(_, Ext, Entry),
FilePath = FullPath
).
% tree_depth(+RootDir, -MaxDepth)
% Computes the maximum depth of the directory tree rooted at RootDir.
tree_depth(Root, MaxDepth) :-
aggregate_all(max(D), path_depth(Root, Root, D), MaxDepth).
path_depth(Root, Path, Depth) :-
exists_directory(Path),
directory_files(Path, Entries),
member(Entry, Entries),
\+ member(Entry, ['.', '..']),
directory_file_path(Path, Entry, FullPath),
exists_directory(FullPath),
path_depth(Root, FullPath, SubDepth),
Depth is SubDepth.
path_depth(Root, Path, Depth) :-
exists_directory(Path),
atomic_list_concat(RootParts, '/', Root),
atomic_list_concat(PathParts, '/', Path),
length(RootParts, RootLen),
length(PathParts, PathLen),
Depth is PathLen - RootLen.
Load this and test it against the ~/logic-lab directory we created in Chapter 1:
?- list_tree('/home/logicdev/logic-lab').
[dir] logic-lab
[dir] prolog
[file] mint_library.pl
[file] vm_optimizer.pl
[file] directory_tree.pl
[file] system_status.pl
[dir] go
[dir] shared
[dir] logs
[dir] knowledge-bases
true.
The find_files_by_ext/3 predicate uses a different recursive structure, one that introduces the -> (if-then) operator. The expression ( Cond -> ThenGoal ; ElseGoal ) is the if-then-else construct in Prolog. If Cond succeeds, only ThenGoal is attempted; if Cond fails, only ElseGoal is attempted. Crucially, the if-then construct commits to one branch — it does not create a choice point for the other. This is a controlled form of the cut behaviour we will examine in section 3.4.
To find all .pl files under the logic lab directory:
?- findall(F, find_files_by_ext('/home/logicdev/logic-lab', pl, F), Files),
length(Files, Count).
Files = ['/home/logicdev/logic-lab/prolog/mint_library.pl',
'/home/logicdev/logic-lab/prolog/vm_optimizer.pl',
'/home/logicdev/logic-lab/prolog/directory_tree.pl',
'/home/logicdev/logic-lab/prolog/system_status.pl'],
Count = 4.
The findall/3 predicate collects all solutions to a goal into a list. Its three arguments are: the template (what to collect), the goal (which is solved for all solutions), and the result list. It is one of the most commonly used predicates in practical Prolog programming and it is worth memorising the argument order: template, goal, list.
The recursion in list_tree/2 and find_files_by_ext/3 terminates because each recursive call is made on a subdirectory that is strictly deeper than the current one, and directory trees are finite. The base cases — exists_file(Path) for list_tree and the ; file_name_extension(...) branch for find_files_by_ext — are reached when the current path is a file rather than a directory. This is the standard recursive pattern: reduce the problem, and stop when the problem has been reduced to its simplest form.
3.4 The Cut and Fail: Taking Control of the Search
The cut operator, written !, is a control predicate with a very specific and precise meaning: when the engine executes a cut, it permanently commits to all the choices made since the parent goal was called. All choice points between the cut and the parent goal are removed. The engine cannot backtrack past a cut — if a goal after the cut fails, the engine will not try alternative clauses for the predicate containing the cut.
This is easier to understand through a concrete example than through the formal definition. Consider a predicate that classifies an application by urgency for a security update:
% security_priority(+App, -Priority)
% Classifies an application's priority for security updates.
security_priority(App, critical) :-
app(App, _, _, system_service),
!.
security_priority(App, high) :-
app(App, _, _, language_runtime),
!.
security_priority(App, normal) :-
app(App, _, _, _).
Add this to mint_library.pl and reload. Now query it:
?- security_priority(openssh, Priority).
Priority = critical.
?- security_priority(swi_prolog, Priority).
Priority = high.
?- security_priority(vscode, Priority).
Priority = normal.
Without the cuts, querying security_priority(openssh, Priority) would return critical as the first solution (from the first clause), but pressing ; would then backtrack and attempt the second clause — since openssh has category system_service but the second clause only checks language_runtime, it would fail, and the third clause would then match (since app(openssh, _, _, _) is true regardless of category), returning normal as a second solution. That would be incorrect. openssh is critical; it is not also normal. The cut after the first clause prevents this: once the engine has determined that openssh is a system_service and committed to critical, the cut removes the choice points for the remaining clauses. No backtracking into this predicate is possible.
THE CUT IN ACTION: security_priority(openssh, Priority)
─────────────────────────────────────────────────────────────────
WITHOUT CUT WITH CUT
─────────────────────── ───────────────────────────
clause 1: system_service? clause 1: system_service?
openssh → YES openssh → YES
Priority = critical ✓ ! ← choice points REMOVED
[choice point left] Priority = critical ✓
[no further search possible]
press ; to continue...
clause 2: language_runtime?
openssh → NO Result: exactly one answer.
FAIL Backtracking into this
clause 3: app(openssh,_,_,_)? predicate is now impossible.
YES
Priority = normal ✓ ← WRONG second answer
Result: critical, then normal.
Logically incorrect.
─────────────────────────────────────────────────────────────────
A GREEN CUT removes logically redundant alternatives.
The meaning of the predicate is unchanged; only the
unnecessary search is eliminated.
This pattern — where the cut is used to say "if this condition matched, we are done, do not try the other clauses" — is called a green cut. It does not change the logical meaning of the predicate (the other clauses would not have produced correct results for this input anyway), it only improves efficiency by preventing unnecessary backtracking. Green cuts are generally safe and beneficial. They are the kind of cut we use throughout this book.
A red cut is one where removing the cut would change the logical meaning of the predicate — where the cut is doing essential logical work, not just pruning redundant search. Red cuts are more dangerous because they make the predicate order-dependent and harder to reason about in isolation. We avoid them where possible and always comment them clearly when they are unavoidable.
The fail/0 predicate is simpler: it always fails. Its primary use is to force backtracking in combination with side-effecting predicates like write/1 or assert/1. We saw the fail-loop pattern in Chapter 1 when we printed all online VMs from the command line. The combination Goal, write(Result), nl, fail drives the engine to find every solution to Goal, print it, and then backtrack to find the next one. When all solutions are exhausted, fail has nothing to backtrack into and the overall goal fails — which is why we add ; true at the end, to ensure the whole expression succeeds.
The cut and fail together create another useful pattern: !, fail in combination is equivalent to forcing overall failure for the current predicate regardless of what other clauses might match. Consider a validation guard that should flatly reject any attempt to query a dependency status for an application that is not in the knowledge base:
% dependency_status_safe(?App, ?Status)
% Like dependency_status/2, but fails with a clear error for unknown apps.
dependency_status_safe(App, _) :-
\+ app(App, _, _, _),
!,
format("Error: '~w' is not a known application.~n", [App]),
fail.
dependency_status_safe(App, Status) :-
dependency_status(App, Status).
?- dependency_status_safe(docker, Status).
Error: 'docker' is not a known application.
false.
?- dependency_status_safe(vscode, Status).
Status = all_satisfied.
The first clause checks whether App is unknown. If it is, the cut commits us to this clause (preventing fallthrough to the second), format/2 prints the error message, and fail forces the predicate to fail overall. This is a controlled, explicit failure with a diagnostic message — a pattern that becomes the foundation of the validation guard systems we build in later chapters when user input and LLM-generated goals need to be checked before execution.
3.5 The Firewall Rule Validator: Bringing It Together
To close this chapter, we build a complete, practical example that exercises everything introduced so far: unification, backtracking, recursion, and the cut. The subject is a firewall rule validator for the Mint VM's network configuration.
A firewall policy can be expressed naturally as a knowledge base: a set of rules defining what traffic is permitted and what is denied, with a recursive evaluation that checks each packet against the rule set in order. The logic is genuinely recursive because rules can have dependencies on other rules (rule groups, named policies, inherited permissions), and the cut is genuinely necessary because firewall rule evaluation is first-match — once a matching rule is found, we commit to its verdict and stop searching.
Create ~/logic-lab/prolog/firewall.pl:
% firewall.pl
% A logic-based firewall rule validator for the Mint VM.
% Part I, Chapter 3 - Modern SWI-Prolog (2026 Edition)
:- module(firewall, [
evaluate_packet/5,
audit_policy/0,
policy_violations/1
]).
:- use_module(library(aggregate)).
% firewall_rule(Priority, Direction, Protocol, Port, Action)
% Rules are evaluated in ascending Priority order (lower number = higher priority).
firewall_rule(10, inbound, tcp, 22, allow). % SSH
firewall_rule(20, inbound, tcp, 5900, allow). % VNC console
firewall_rule(30, inbound, tcp, 443, allow). % HTTPS (for package updates)
firewall_rule(40, inbound, udp, 53, allow). % DNS responses
firewall_rule(900, inbound, tcp, _, deny). % Default deny all other TCP inbound
firewall_rule(910, inbound, udp, _, deny). % Default deny all other UDP inbound
firewall_rule(10, outbound, tcp, 443, allow). % HTTPS outbound
firewall_rule(20, outbound, tcp, 80, allow). % HTTP outbound (for apt)
firewall_rule(30, outbound, udp, 53, allow). % DNS queries
firewall_rule(900, outbound, tcp, _, deny). % Default deny other outbound TCP
firewall_rule(910, outbound, udp, _, deny). % Default deny other outbound UDP
% evaluate_packet(+Direction, +Protocol, +Port, -Action, -MatchedPriority)
% Evaluates a packet against the firewall rules and returns the action
% taken by the highest-priority (lowest number) matching rule.
evaluate_packet(Direction, Protocol, Port, Action, MatchedPriority) :-
findall(
Priority-Act,
firewall_rule(Priority, Direction, Protocol, Port, Act),
Matches
),
Matches \= [],
sort(Matches, Sorted),
Sorted = [MatchedPriority-Action | _].
% reachable_port(+Direction, +Protocol, +Port)
% True if a packet with these attributes would be allowed through.
reachable_port(Direction, Protocol, Port) :-
evaluate_packet(Direction, Protocol, Port, allow, _).
% blocked_port(+Direction, +Protocol, +Port)
% True if a packet with these attributes would be denied.
blocked_port(Direction, Protocol, Port) :-
evaluate_packet(Direction, Protocol, Port, deny, _).
% known_service(Port, Name)
% Human-readable names for well-known ports used in audit output.
known_service(22, ssh).
known_service(53, dns).
known_service(80, http).
known_service(443, https).
known_service(5900, vnc).
known_service(8080, http_alt).
known_service(3306, mysql).
known_service(5432, postgresql).
% audit_policy/0
% Prints a summary of all explicitly named allowed services.
audit_policy :-
format("~n=== Firewall Policy Audit ===~n~n"),
forall(
(known_service(Port, Name),
reachable_port(inbound, tcp, Port)),
format(" ALLOWED inbound tcp/~w (~w)~n", [Port, Name])
),
forall(
(known_service(Port, Name),
blocked_port(inbound, tcp, Port)),
format(" DENIED inbound tcp/~w (~w)~n", [Port, Name])
),
format("~n").
% policy_violations(-Violations)
% Checks for a set of known-risky ports that should never be open inbound.
% Returns a list of any that are currently allowed.
policy_violations(Violations) :-
RiskyPorts = [3306, 5432, 8080, 23, 21],
findall(
violation(Port, Service),
(
member(Port, RiskyPorts),
reachable_port(inbound, tcp, Port),
(known_service(Port, Service) -> true ; Service = unknown)
),
Violations
).
Load the file and run the audit:
?- audit_policy.
=== Firewall Policy Audit ===
ALLOWED inbound tcp/22 (ssh)
ALLOWED inbound tcp/5900 (vnc)
ALLOWED inbound tcp/443 (https)
DENIED inbound tcp/80 (http)
DENIED inbound tcp/3306 (mysql)
DENIED inbound tcp/5432 (postgresql)
true.
Check for policy violations:
?- policy_violations(Violations).
Violations = [].
An empty list means none of the risky ports are currently open inbound — which is exactly what we configured in the Proxmox firewall in Chapter 1.
Now let us test the evaluator directly for a port that is not explicitly named:
?- evaluate_packet(inbound, tcp, 8080, Action, Priority).
Action = deny,
Priority = 900.
The default-deny rule at priority 900 catches port 8080. The engine found all matching rules via findall/3, sorted them by priority, and took the first (lowest priority number) match. ```
FIRST-MATCH FIREWALL EVALUATION: inbound tcp/8080
─────────────────────────────────────────────────────────────────
findall collects ALL matching rules for tcp/8080 inbound:
firewall_rule(10, inbound, tcp, 22, allow) port≠8080 skip firewall_rule(20, inbound, tcp, 5900, allow) port≠8080 skip firewall_rule(30, inbound, tcp, 443, allow) port≠8080 skip firewall_rule(900, inbound, tcp, _, deny) _ unifies MATCH → 900-deny firewall_rule(910, inbound, udp, _, deny) proto≠tcp skip
Collected: [ 900-deny ]
sort/2 on Key-Value pairs sorts by Key (Priority): Sorted: [ 900-deny ]
Head of sorted list: 900-deny MatchedPriority = 900, Action = deny
Result: DENY (default-deny rule, priority 900) ───────────────────────────────────────────────────────────────── All rules are pure data. No cuts, no clause ordering tricks. Priority is expressed as data and resolved by sort/2. Adding a new rule requires only a new firewall_rule/5 fact.
This is first-match semantics implemented declaratively — no cuts required, because we used `findall` to collect all matches and then selected the winner by sorting. This is often a cleaner approach than using cuts for priority-based selection, particularly when the number of rules is large, because it keeps the rule facts as pure data rather than mixing control flow into them.
The `audit_policy/0` predicate introduces `forall/2`. The call `forall(Condition, Action)` succeeds if `Action` succeeds for every solution of `Condition`. It is the natural way to express "for every X satisfying condition C, do action A" without building an explicit list. Its implementation is equivalent to `\+ (Condition, \+ Action)` — there is no X satisfying C for which A fails — which is a neat example of how negation as failure can be combined to express universal quantification.
The `policy_violations/1` predicate demonstrates a practical security audit pattern that will recur throughout this book. We define a list of known-risky ports as a simple Prolog list literal, iterate over it with `member/2`, check each against the current policy, and collect the results with `findall/3`. The result is a machine-readable list of violation terms that a Go process could parse, log, and alert on. In Chapter 6, we will build exactly that connection.
## 3.6 Chapter Summary and What Comes Next
The three mechanisms introduced in this chapter — unification, backtracking, and recursion — are not three separate features of SWI-Prolog. They are three aspects of a single coherent execution model. Unification determines whether and how two terms can be made identical. Backtracking gives the engine the ability to explore multiple paths through a proof. Recursion allows predicates to operate on structures of arbitrary depth. Together, they make Prolog capable of expressing problems that would require explicit stack management, complex loop constructs, or external libraries in procedural languages.
The cut and `fail` predicates give us surgical control over this search process. The green cut eliminates redundant backtracking. The `fail`-loop drives exhaustive solution generation. Together with `\+`, they cover the vast majority of control flow requirements in practical Prolog programs.
The knowledge base we have built now spans four files: `system_status.pl` (Chapter 1), `mint_library.pl` and `vm_optimizer.pl` (Chapter 2), and `directory_tree.pl` and `firewall.pl` (this chapter). These files collectively model the VM's software environment, its service configuration, its filesystem layout, and its network security policy. They are not toy examples. Every predicate in them could be loaded on the actual Mint VM and would produce correct results against the real environment.
Part II of this book turns to data structures. The knowledge bases we have built so far use atoms, numbers, and simple compound terms as their building blocks. In Chapter 4, we introduce the Dict — SWI-Prolog's native key-value structure, analogous to a JSON object or a Go map — and we examine how it transforms the way we model complex, real-world entities. Chapter 5 then introduces Definite Clause Grammars, which will allow us to parse real log files from `/var/log` and transform them into queryable Prolog facts. The simple, flat knowledge bases of Part I will give way to richer, more structured representations of the world — but the foundations of unification, backtracking, and recursion that we have laid in these three chapters will remain the engine beneath everything that follows.
---
## Appendix 3A: The Complete firewall.pl
```prolog
% firewall.pl
% A logic-based firewall rule validator for the Mint VM.
% Part I, Chapter 3 - Modern SWI-Prolog (2026 Edition)
:- module(firewall, [
evaluate_packet/5,
reachable_port/3,
blocked_port/3,
audit_policy/0,
policy_violations/1
]).
:- use_module(library(aggregate)).
% firewall_rule(Priority, Direction, Protocol, Port, Action)
firewall_rule(10, inbound, tcp, 22, allow).
firewall_rule(20, inbound, tcp, 5900, allow).
firewall_rule(30, inbound, tcp, 443, allow).
firewall_rule(40, inbound, udp, 53, allow).
firewall_rule(900, inbound, tcp, _, deny).
firewall_rule(910, inbound, udp, _, deny).
firewall_rule(10, outbound, tcp, 443, allow).
firewall_rule(20, outbound, tcp, 80, allow).
firewall_rule(30, outbound, udp, 53, allow).
firewall_rule(900, outbound, tcp, _, deny).
firewall_rule(910, outbound, udp, _, deny).
% evaluate_packet(+Direction, +Protocol, +Port, -Action, -MatchedPriority)
evaluate_packet(Direction, Protocol, Port, Action, MatchedPriority) :-
findall(
Priority-Act,
firewall_rule(Priority, Direction, Protocol, Port, Act),
Matches
),
Matches \= [],
sort(Matches, Sorted),
Sorted = [MatchedPriority-Action | _].
% reachable_port(+Direction, +Protocol, +Port)
reachable_port(Direction, Protocol, Port) :-
evaluate_packet(Direction, Protocol, Port, allow, _).
% blocked_port(+Direction, +Protocol, +Port)
blocked_port(Direction, Protocol, Port) :-
evaluate_packet(Direction, Protocol, Port, deny, _).
% known_service(Port, Name)
known_service(22, ssh).
known_service(53, dns).
known_service(80, http).
known_service(443, https).
known_service(5900, vnc).
known_service(8080, http_alt).
known_service(3306, mysql).
known_service(5432, postgresql).
% audit_policy/0
audit_policy :-
format("~n=== Firewall Policy Audit ===~n~n"),
forall(
(known_service(Port, Name),
reachable_port(inbound, tcp, Port)),
format(" ALLOWED inbound tcp/~w (~w)~n", [Port, Name])
),
forall(
(known_service(Port, Name),
blocked_port(inbound, tcp, Port)),
format(" DENIED inbound tcp/~w (~w)~n", [Port, Name])
),
format("~n").
% policy_violations(-Violations)
policy_violations(Violations) :-
RiskyPorts = [3306, 5432, 8080, 23, 21],
findall(
violation(Port, Service),
(
member(Port, RiskyPorts),
reachable_port(inbound, tcp, Port),
(known_service(Port, Service) -> true ; Service = unknown)
),
Violations
).
Appendix 3B: Snapshot Checkpoint
With all three chapters of Part I complete, this is a good point to take a named snapshot before moving into Part II.
Snapshot name: 04-part-one-complete
Description: All Part I knowledge bases complete and tested.
Files: system_status.pl, mint_library.pl,
vm_optimizer.pl, directory_tree.pl, firewall.pl
No comments to display
No comments to display