Chapter 2: Speaking Logic — The Beginner's Vocabulary

Overview

There is a particular moment that almost every developer experiences when learning Prolog for the first time. It usually arrives somewhere in the second or third hour of study, after the syntax has started to feel slightly familiar but before the engine's behaviour has become intuitive. The moment is this: the realisation that the code is not doing anything in the sense that code usually does things. There are no loops. There is no explicit sequence of steps. There is no variable being incremented or pointer being followed. There is only a description of the world, and an engine that interrogates that description on demand.

This chapter is about building fluency in that new mode of expression. We are going to work with three constructs — facts, rules, and queries — and we are going to do so through a knowledge base that grows organically from something simple into something genuinely useful. By the end of the chapter, the knowledge base will be able to check software dependencies, identify configuration problems, and report on the health of the virtual lab environment we built in Chapter 1. Every predicate we write will be tested in the SWI-Prolog REPL on the Mint VM. Nothing here is illustrative pseudocode.

The fourth construct, the variable, deserves its own extended treatment because it is where the most important conceptual shift happens. In procedural programming, a variable is a named container for a value. In Prolog, a variable is a constraint — a placeholder that the engine is asked to fill in during its search. That distinction sounds subtle but its implications are profound, and we will spend the latter part of this chapter examining them carefully.

2.1 Facts: The Ground Floor of Knowledge

A Prolog program begins with facts. A fact is the simplest possible assertion about the world: a statement that something is true. In SWI-Prolog, a fact is written as a functor — a name — followed by zero or more arguments enclosed in parentheses, terminated by a full stop.

Create a new file in the workspace: ~/logic-lab/prolog/mint_library.pl. We are going to model the software environment of our Mint VM as a knowledge base — recording which applications are installed, what versions they are, their licences, and which category they belong to. This is a deliberate choice. The knowledge base describes something we can verify directly on the running system, which means every fact we write can be checked against reality.

% mint_library.pl
% A knowledge base modelling the installed software environment
% of the Linux Mint 22.x development VM.
% Part I, Chapter 2 - Modern SWI-Prolog (2026 Edition)

:- module(mint_library, [
    app/4,
    installed/1,
    licence_type/2,
    depends_on/2,
    dependency_status/2
]).

% app(Name, Version, Licence, Category)
app(swi_prolog,  '10.2.1', open_source, language_runtime).
app(vscode,      '1.89.0', proprietary,  ide).
app(golang,      '1.26.1', open_source, language_runtime).
app(openssh,     '9.7p1',  open_source, system_service).
app(qemu_agent,  '8.2.0',  open_source, system_service).
app(git,         '2.45.0', open_source, version_control).
app(curl,        '8.7.1',  open_source, utility).

The structure of each fact is identical: app(Name, Version, Licence, Category). The name of the functor — app — is called the predicate name. The number of arguments it takes is called its arity. Together, these give us the predicate indicator: app/4, meaning the predicate named app with arity 4. This notation appears throughout SWI-Prolog documentation, error messages, and the module declaration at the top of the file, so it is worth becoming completely comfortable with it now.

The arguments themselves fall into two categories. The unquoted atoms — open_source, proprietary, language_runtime, ide, system_service, version_control, utility — are atoms in the Prolog sense: indivisible symbolic constants. They have no internal structure; they simply are. The quoted strings like '10.2.1' are also atoms, but they require quoting because they begin with a digit or contain special characters that would otherwise confuse the parser. In SWI-Prolog 10.x, single-quoted atoms and double-quoted strings are distinct types (we will address strings properly in Chapter 4), but for version numbers used as labels — where we have no intention of doing arithmetic on them — single-quoted atoms are the appropriate choice.

Notice what is absent from these facts: there is no schema declaration, no type annotation, no table definition. The structure of the knowledge base is entirely implicit in the facts themselves. The predicate app/4 exists simply because we have written app(...) facts with four arguments. This is both a strength and a responsibility. The strength is flexibility — we can add new predicates or extend existing ones at any point without a migration script. The responsibility is consistency — if we accidentally write app(git, '2.45.0', open_source) with only three arguments somewhere in the file, the engine will treat that as a completely separate predicate app/3, not as an error. The Prolog LSP extension in VS Code will warn about singleton clauses, but the discipline of consistent arity is fundamentally the programmer's job.

Load the file into the REPL and verify that the facts are accessible:

swipl ~/logic-lab/prolog/mint_library.pl

?- app(swi_prolog, Version, Licence, _).
Version = '10.2.1',
Licence = open_source.

The underscore _ in the fourth argument position is the anonymous variable — it tells the engine "something goes here, but we do not care what it is." This is different from a named variable, which the engine would attempt to bind and report. The anonymous variable is used whenever an argument is structurally required but semantically irrelevant to the current question.

2.2 Atoms: The Building Blocks of Thought

It is worth pausing on atoms specifically, because they are the atomic unit of Prolog's symbolic world and their behaviour is quite different from strings in most other languages. An atom in Prolog is not a piece of text. It is an identity. When the engine encounters open_source in two different facts, it does not compare character sequences — it compares symbolic identities, which in SWI-Prolog's implementation are memory-interned pointers. This makes atom comparison extremely fast and makes atoms the natural choice for representing categories, states, identifiers, and any other discrete symbolic value.

The naming conventions for atoms matter practically. An atom that begins with a lowercase letter and contains only letters, digits, and underscores can be written without quotes: open_source, language_runtime, swi_prolog. An atom that begins with an uppercase letter, contains spaces, or contains special characters must be quoted: 'SWI-Prolog', 'open source', '10.2.1'. This is not merely a stylistic rule — it is a parsing rule. An unquoted token beginning with an uppercase letter is interpreted by the parser as a variable, not an atom. This is the source of one of the most common beginner errors in Prolog, and we will address it again when we introduce variables in section 2.4.

A particularly useful built-in predicate for working with atoms is atom_string/2, which bridges the symbolic world of atoms and the text-manipulation world of strings. We will not need it in this chapter, but it is worth knowing it exists. For now, the discipline to adopt is simple: use atoms for identifiers, categories, and states; use quoted atoms for values that look like something else (version numbers, names with hyphens); and reserve strings for actual text that needs to be processed character-by-character.

2.3 Querying the Knowledge Base

With the mint_library.pl facts loaded, we can begin asking questions. The REPL's query prompt is an invitation to describe a pattern, and the engine will search the knowledge base for everything that matches it.

The most basic query is a ground query — one with no variables, which simply asks "is this true?":

?- app(git, '2.45.0', open_source, version_control).
true.

The engine searches the app/4 facts, finds an exact match, and reports true. Change any argument:

?- app(git, '2.45.0', proprietary, version_control).
false.

No fact matches this pattern, so the engine reports false. Notice that false here does not mean "git is definitively not proprietary" in some absolute metaphysical sense. It means "no fact in the current knowledge base asserts that git's licence is proprietary." This is a critical distinction that we will revisit when we discuss the Closed World Assumption in Chapter 3. For now, the practical implication is that false always means "not provable from what we currently know" rather than "provably false."

A more powerful form of query uses variables to extract information:

?- app(Name, _, open_source, language_runtime).
Name = swi_prolog ;
Name = golang.

Here the engine is asked to find all values of Name such that app(Name, _, open_source, language_runtime) matches a fact in the knowledge base. It finds swi_prolog and golang, and offers them one at a time. In the interactive REPL, pressing ; requests the next solution. Pressing . or Enter accepts the current solution and stops searching. This interactive exploration — asking a question and then deciding whether to look for more answers — is one of the most natural ways to develop and debug a Prolog knowledge base.

We can ask more complex questions by combining multiple conditions in a single query using the comma operator, which means and:

?- app(Name, _, Licence, ide), Licence \= open_source.
Name = vscode,
Licence = proprietary.

This query asks for the name and licence of any application in the ide category whose licence is not open_source. The \= operator means does not unify with — it succeeds when the two terms cannot be made identical. VS Code, with its proprietary licence, is the only match.

These queries are already practically useful. On a security-conscious homelab, being able to ask "which installed software is not open source?" or "which system services were installed from what source?" is exactly the kind of audit capability that would otherwise require a custom shell script. We have it for free, simply by having modelled the environment as a knowledge base.

2.4 Rules: Automating Reason

Facts describe individual truths. Rules describe derived truths — things that are true because other things are true. A rule is written as a head (the conclusion) followed by :- (which means "if") followed by a body (the conditions that must hold). A rule fires when its body can be proven; the head then becomes provable too.

Add the following to mint_library.pl:

% installed(+Name)
% True if an app with the given name exists in the knowledge base.
installed(Name) :-
    app(Name, _, _, _).

% licence_type(?Name, ?Type)
% Relates an app name to its licence type.
licence_type(Name, Type) :-
    app(Name, _, Type, _).

% open_source_tool(+Name)
% True if the named application is open source.
open_source_tool(Name) :-
    app(Name, _, open_source, _).

The comments above each rule use a notation worth understanding: + before an argument name means the argument is expected to be instantiated (given a concrete value) when the predicate is called; ? means the argument can be either instantiated or uninstantiated — the predicate works in both directions; - means the argument is expected to be uninstantiated and will be filled in by the predicate. This is called the mode of the predicate, and while SWI-Prolog does not enforce these annotations at runtime (they are documentation), writing them consistently is a discipline that makes reading and debugging much easier.

Reload the file in the REPL (using make/0 in SWI-Prolog, which reloads modified source files without restarting):

?- make.

Now query the new rules:

?- open_source_tool(Name).
Name = swi_prolog ;
Name = golang ;
Name = openssh ;
Name = qemu_agent ;
Name = git ;
Name = curl.

The rule open_source_tool(Name) has no facts of its own. It derives its answers entirely from the app/4 facts, filtering for those where the third argument is open_source. This is composition: rules built on top of facts, and later rules that we will write on top of other rules, creating layers of increasingly abstract reasoning from the same underlying ground facts.

2.5 The Dependency Checker

To demonstrate the real power of rules, we are going to build something practically useful: a software dependency checker. The idea is straightforward — some applications depend on others being installed, and we want to be able to ask the engine whether a given dependency is satisfied or not, and if not, what is missing.

Add the following dependency facts to mint_library.pl:

% depends_on(App, Dependency)
% App cannot function correctly without Dependency being installed.
depends_on(vscode,     git).
depends_on(vscode,     curl).
depends_on(swi_prolog, openssh).
depends_on(golang,     git).

These are ground facts — specific, concrete assertions about the dependency relationships in our environment. Now we write the rules that reason over them:

% dependency_satisfied(+App, +Dep)
% True if App's dependency on Dep is satisfied (i.e. Dep is installed).
dependency_satisfied(App, Dep) :-
    depends_on(App, Dep),
    installed(Dep).

% dependency_missing(+App, ?Dep)
% True if App has a dependency on Dep that is NOT currently installed.
dependency_missing(App, Dep) :-
    depends_on(App, Dep),
    \+ installed(Dep).

% dependency_status(?App, ?Status)
% Reports the overall dependency status of an application.
dependency_status(App, all_satisfied) :-
    installed(App),
    \+ dependency_missing(App, _).
dependency_status(App, missing(Dep)) :-
    installed(App),
    dependency_missing(App, Dep).

There is a new operator here that deserves careful explanation: \+. This is Prolog's negation as failure operator. \+ Goal succeeds if Goal fails — that is, if the engine cannot find a proof of Goal in the current knowledge base. It does not mean that Goal is logically false; it means that Goal is not provable. This is a subtle but important distinction, and it is closely related to the Closed World Assumption mentioned earlier.

In dependency_missing/2, the condition \+ installed(Dep) succeeds when the engine cannot prove that Dep is installed. If Dep is simply absent from the knowledge base entirely — not listed as an app/4 fact — this condition will succeed, which is exactly the behaviour we want. A dependency that has never been declared as installed is, from the knowledge base's point of view, missing.

After reloading with make/0, test the checker:

?- dependency_status(vscode, Status).
Status = all_satisfied.

?- dependency_status(golang, Status).
Status = all_satisfied.

All dependencies are satisfied because we installed git, curl, and openssh as facts in the knowledge base. Now let us simulate a missing dependency. Add a new application that depends on something we have not installed:

app(hypothetical_tool, '1.0.0', open_source, utility).
depends_on(hypothetical_tool, docker).
depends_on(hypothetical_tool, git).

Reload and query:

?- dependency_status(hypothetical_tool, Status).
Status = missing(docker) ;
Status = all_satisfied.

This is the engine working exactly as intended. docker is not in the knowledge base as an installed application, so dependency_missing(hypothetical_tool, docker) succeeds, and dependency_status reports missing(docker). The git dependency is satisfied, so the second solution all_satisfied is also found, because \+ dependency_missing(hypothetical_tool, _) — read as "there is no missing dependency" — would need all dependencies to be missing to fail completely, but actually dependency_status(App, all_satisfied) only fires when \+ dependency_missing(App, _) holds, which means there is no missing dependency at all. Since docker is missing, dependency_status(hypothetical_tool, all_satisfied) should actually fail. Let us verify:

?- dependency_status(hypothetical_tool, all_satisfied).
false.

Correct. The all_satisfied clause requires \+ dependency_missing(App, _) — there must be no missing dependency. Since docker is missing, this condition fails, and the all_satisfied branch of the rule is not satisfied. The only true status for hypothetical_tool is missing(docker). The earlier query showing both results was a consequence of typing the query before adding the second depends_on fact — a reminder that in the REPL, make/0 must be called after every source file change.

2.6 The Variable: The Logic Searchlight

We have already used variables in queries — Name, Version, Status — but we have not yet examined what they actually are. In Prolog, a variable is not a storage location. It is not an alias for a memory address holding a value that can change over time. A Prolog variable, within the scope of a single query or rule, is an unknown that the engine is tasked with determining. Once the engine unifies a variable with a value, that variable is that value for the duration of the current proof attempt. It cannot be changed. It can only be unbound when the engine backtracks to try a different solution.

This property — that variables are single-assignment within a proof branch — is what makes Prolog code so different from procedural code. Consider this rule again:

dependency_missing(App, Dep) :-
    depends_on(App, Dep),
    \+ installed(Dep).

When the engine processes this rule in response to a query like dependency_missing(vscode, What), the variable App is immediately unified with vscode (it was given a concrete value in the query). The variable Dep and the query variable What are both uninstantiated. The engine then tries to prove depends_on(vscode, Dep). It searches the depends_on/2 facts and finds depends_on(vscode, git) — at this point, Dep becomes git. The engine then checks \+ installed(git). Since git is installed, installed(git) succeeds, and therefore \+ installed(git) fails. The entire rule body fails. The engine backtracks — it undoes the binding of Dep to git and looks for the next depends_on(vscode, ...) fact. It finds depends_on(vscode, curl). Now Dep is curl. Again, curl is installed, so \+ installed(curl) fails. No more depends_on(vscode, ...) facts exist. The overall query fails.

Following this trace through manually is one of the most valuable exercises a new Prolog programmer can do. The engine's behaviour is not magic; it is a disciplined, deterministic search process. Every step is predictable. Every backtrack has a clear cause. Once this mental model is internalised, debugging a Prolog program becomes significantly more straightforward.

SWI-Prolog provides a built-in tracer that makes this search visible. In the REPL, activate it with trace/0 and then rerun a query:

?- trace.
true.

[trace] ?- dependency_missing(vscode, What).
   Call: (12) dependency_missing(vscode, _G234)
   Call: (13) depends_on(vscode, _G234)
   Exit: (13) depends_on(vscode, git)
   Call: (13) installed(git)
   Call: (14) app(git, _G238, _G239, _G240)
   Exit: (14) app(git, '2.45.0', open_source, version_control)
   Exit: (13) installed(git)
   Fail: (13) \+installed(git)
   Redo: (13) depends_on(vscode, _G234)
   Exit: (13) depends_on(vscode, curl)
   ...

The tracer output is verbose, but it is the engine's complete internal monologue. Call means the engine is attempting to prove a goal. Exit means it succeeded. Fail means it failed. Redo means it is backtracking and trying the next alternative. Turn the tracer off with notrace/0 when done. We will return to this debugging tool in Chapter 3 when we examine unification in detail.

2.7 The System Optimizer: A Practical Variable Exercise

To close this chapter, we build a small but practical tool: a rule-based system optimizer for the Mint VM. The goal is to identify background services that are running but may be unnecessary given the current VM role. This introduces the variable as a genuinely useful search tool rather than just a mechanism for extracting values from queries.

Add the following to mint_library.pl or create a new file ~/logic-lab/prolog/vm_optimizer.pl that consults it:

% vm_optimizer.pl
% Rule-based system optimization advisor for the Mint logic lab VM.

:- module(vm_optimizer, [service_status/3, optimization_advice/2]).
:- use_module(library(aggregate)).

% service(Name, Status, RAM_MB)
% Models background services and their current resource usage.
service(bluetooth,       running, 12).
service(cups,            running, 28).
service(avahi_daemon,    running, 8).
service(qemu_agent,      running, 6).
service(ssh,             running, 4).
service(packagekitd,     running, 45).
service(tracker_miner,   running, 38).
service(evolution_data,  stopped, 0).
service(snapd,           running, 22).

% vm_role(Role)
% The declared role of this VM.
vm_role(development).

% role_requires_service(Role, Service)
% Services that are genuinely required for a given VM role.
role_requires_service(development, qemu_agent).
role_requires_service(development, ssh).

% service_status(?Name, ?Status, ?RAM_MB)
service_status(Name, Status, RAM_MB) :-
    service(Name, Status, RAM_MB).

% unnecessary_service(?Name, ?RAM_MB)
% A running service that is not required for the current VM role.
unnecessary_service(Name, RAM_MB) :-
    vm_role(Role),
    service(Name, running, RAM_MB),
    \+ role_requires_service(Role, Name).

% optimization_advice(?Service, ?Advice)
% Generates human-readable advice for each unnecessary running service.
optimization_advice(Service, advice(disable, Service, saves_mb(RAM_MB))) :-
    unnecessary_service(Service, RAM_MB).

Load this file and query it:

?- optimization_advice(Service, Advice).
Service = bluetooth,
Advice = advice(disable, bluetooth, saves_mb(12)) ;
Service = cups,
Advice = advice(disable, cups, saves_mb(28)) ;
Service = avahi_daemon,
Advice = advice(disable, avahi_daemon, saves_mb(8)) ;
Service = packagekitd,
Advice = advice(disable, packagekitd, saves_mb(45)) ;
Service = tracker_miner,
Advice = advice(disable, tracker_miner, saves_mb(38)) ;
Service = snapd,
Advice = advice(disable, snapd, saves_mb(22)).

The engine has searched through all running services, filtered out the two that role_requires_service declares as necessary for a development VM (qemu_agent and ssh), and generated structured advice terms for the remainder. The total RAM that could be reclaimed is the sum of those saves_mb values, which we can compute directly in Prolog:

?- aggregate_all(sum(RAM), unnecessary_service(_, RAM), Total).
Total = 153.

The aggregate_all/3 predicate (from library(aggregate), which is automatically available in SWI-Prolog 10.x) collects all solutions to unnecessary_service(_, RAM), sums the RAM values, and binds the result to Total. One hundred and fifty-three megabytes of RAM is occupied by services that have no defined purpose in a dedicated logic development VM.

This is not just a tutorial exercise. The vm_optimizer module is a small but real example of what "rules as code" means in practice. The logic for what is and is not necessary on this VM is declared explicitly, in a form that can be read, reviewed, and modified by anyone who understands the domain. If the VM role changes — if it becomes a web server as well as a development machine — we add role_requires_service(development, nginx) and the optimizer immediately stops reporting nginx as unnecessary. No code change, no recompile, no deployment pipeline. Just a new fact.

This pattern — using the knowledge base as the single authoritative source of policy, and using rules to derive consequences from that policy — is the central idea of this entire book. We have introduced it here in its simplest form. Every chapter from here forward makes it more powerful.

2.8 Chapter Summary and What Comes Next

In this chapter, we have moved from the installation checks of Chapter 1 into genuine Prolog programming. The mint_library.pl knowledge base demonstrates facts as ground assertions about the world; the vm_optimizer.pl module demonstrates rules as derived reasoning over those facts. The dependency checker introduced negation as failure (\+), which is one of the most important and occasionally misunderstood operators in Prolog. And the variable — introduced through queries and traced through the engine's backtracking search — has been shown to be something quite different from a variable in any procedural language.

The knowledge base at the end of this chapter is modest, but it is already doing real work. It is checking dependency satisfaction, identifying unnecessary services, and generating structured recommendations — all without a single loop, a single counter variable, or a single explicit conditional branch.

Chapter 3 takes us into the engine room. We will examine unification in depth — the mechanism by which the engine decides that two terms can be made identical — and we will look at backtracking as a structured search process rather than an incidental side effect. We will also introduce recursion, which is how Prolog handles repetition, and we will build a rule that maps the directory tree of the VM's home folder. Finally, we will introduce the cut operator (!), which gives us a tool for controlling backtracking when the engine's default exhaustive search is more than we need. The knowledge base we have built in this chapter will be the foundation on which those concepts are demonstrated.

---

Appendix 2A: The Complete mint_library.pl

The following is the complete, final state of mint_library.pl as it should exist at the end of this chapter. Ensure this matches the file on the VM before proceeding to Chapter 3.

% mint_library.pl
% A knowledge base modelling the installed software environment
% of the Linux Mint 22.x development VM.
% Part I, Chapter 2 - Modern SWI-Prolog (2026 Edition)

:- module(mint_library, [
    app/4,
    installed/1,
    licence_type/2,
    depends_on/2,
    dependency_status/2,
    open_source_tool/1
]).

% app(Name, Version, Licence, Category)
app(swi_prolog,        '10.2.1', open_source, language_runtime).
app(vscode,            '1.89.0', proprietary,  ide).
app(golang,            '1.26.1', open_source, language_runtime).
app(openssh,           '9.7p1',  open_source, system_service).
app(qemu_agent,        '8.2.0',  open_source, system_service).
app(git,               '2.45.0', open_source, version_control).
app(curl,              '8.7.1',  open_source, utility).
app(hypothetical_tool, '1.0.0',  open_source, utility).

% depends_on(App, Dependency)
depends_on(vscode,            git).
depends_on(vscode,            curl).
depends_on(swi_prolog,        openssh).
depends_on(golang,            git).
depends_on(hypothetical_tool, docker).
depends_on(hypothetical_tool, git).

% installed(+Name)
installed(Name) :-
    app(Name, _, _, _).

% licence_type(?Name, ?Type)
licence_type(Name, Type) :-
    app(Name, _, Type, _).

% open_source_tool(+Name)
open_source_tool(Name) :-
    app(Name, _, open_source, _).

% dependency_satisfied(+App, +Dep)
dependency_satisfied(App, Dep) :-
    depends_on(App, Dep),
    installed(Dep).

% dependency_missing(+App, ?Dep)
dependency_missing(App, Dep) :-
    depends_on(App, Dep),
    \+ installed(Dep).

% dependency_status(?App, ?Status)
dependency_status(App, all_satisfied) :-
    installed(App),
    \+ dependency_missing(App, _).
dependency_status(App, missing(Dep)) :-
    installed(App),
    dependency_missing(App, Dep).

Appendix 2B: The Complete vm_optimizer.pl

% vm_optimizer.pl
% Rule-based system optimization advisor for the Mint logic lab VM.
% Part I, Chapter 2 - Modern SWI-Prolog (2026 Edition)

:- module(vm_optimizer, [
    service_status/3,
    optimization_advice/2,
    unnecessary_service/2
]).
:- use_module(library(aggregate)).

% service(Name, Status, RAM_MB)
service(bluetooth,       running, 12).
service(cups,            running, 28).
service(avahi_daemon,    running, 8).
service(qemu_agent,      running, 6).
service(ssh,             running, 4).
service(packagekitd,     running, 45).
service(tracker_miner,   running, 38).
service(evolution_data,  stopped, 0).
service(snapd,           running, 22).

% vm_role(Role)
vm_role(development).

% role_requires_service(Role, Service)
role_requires_service(development, qemu_agent).
role_requires_service(development, ssh).

% service_status(?Name, ?Status, ?RAM_MB)
service_status(Name, Status, RAM_MB) :-
    service(Name, Status, RAM_MB).

% unnecessary_service(?Name, ?RAM_MB)
unnecessary_service(Name, RAM_MB) :-
    vm_role(Role),
    service(Name, running, RAM_MB),
    \+ role_requires_service(Role, Name).

% optimization_advice(?Service, ?Advice)
optimization_advice(Service, advice(disable, Service, saves_mb(RAM_MB))) :-
    unnecessary_service(Service, RAM_MB).