Thinking in States

Markus Triska's essay (part of The Power of Prolog) addresses the wall newcomers hit when they move from imperative to declarative languages — "how do I even increase a variable?", "how do I remove an element from a list?" The answer is always the same shape: stop thinking about modifying state, start thinking about relations between states.

The move from mutation to relation

The imperative way to increment a variable is i = i + 1. The state of i changes, the old state is gone, and declaratively the equation i = i + 1 makes no sense — no integer equals itself plus one. In Prolog the same idea becomes I #= I0 + 1: I and I0 are two different variables in an equivalence relation. The relation is usable in all directions — bind I0, get the next integer; bind I, get the previous; leave both unbound, enumerate.

The mental leap: two variables for what would be one in an imperative language, because a single variable can't reflect two states at once.

Removing an element from a list

The naive imperative framing is remove(list, e). The declarative framing is a relation between three things — a list, an element, and another list — that holds when the second list is the first with all occurrences of the element omitted:

list1_element_list2([], _, []).
list1_element_list2([E|Ls1], E, Ls2) :-
        list1_element_list2(Ls1, E, Ls2).
list1_element_list2([L|Ls1], E, [L|Ls2]) :-
        dif(L, E),
        list1_element_list2(Ls1, E, Ls2).

The relation answers any of these queries: which element was removed? what does the input look like if the output is X? for which triples does the relation hold? Naming it remove/3 would obscure that generality. Using library(reif) and tfilter/3 collapses the same predicate to one declarative line.

States in puzzles

The water-jug puzzle (8/5/3, fill A to 4 and B to 4) makes the state representation choice concrete. Triska shows a Haskell version with (Int, Int, Int) triples and a Prolog version using jug(Name, Fill) terms with iterative deepening. The Prolog version is shorter because moves can be described uniformly — From and To are variables, the constraint solver handles the arithmetic, and the structure doesn't need to enumerate all six possible transfers explicitly.

The same pattern generalizes — wolf-and-goat, the 8-puzzle, Escape from Zurg, missionary-and-cannibal. Choosing the state representation that admits a small relation between states matters more than choosing the search strategy.

States in programs (an interpreter)

The piece builds a Prolog interpreter for a small imperative language over integers. ASTs are Prolog terms: function(Name, Parameter, Body), assign(Variable, Expression), if(Condition, Then, Else), while(Condition, Body), etc. The interpreter's state is a pair of association lists — variable bindings and function definitions — and the interpret/3 predicate threads that state through, with one clause per AST shape. Each clause defines a relation between the input environment and the output environment.

Two interesting wrinkles:

• print produces a side effect that doesn't fit the pure-relation model. To fix it properly you'd thread a representation of the "world" through the environment.
• return is special because its resulting "environment" is a single value, which eval/3 knows to consume when evaluating function calls.

States in compilers

The same essay continues into a compiler for the same language, targeting a stack-based VM with pushc, pushv, pop, arithmetic, jne/jge/jle, call, ret, print, halt. Compilation state is a quadruple s(Is, Fs, Vs, PC): emitted instructions, function offsets, variable offsets in the current function, and the program counter. The compiler is written in DCG semicontext notation so the state threads through implicitly:

state(S), [S] --> [S].
state(S0, S), [S] --> [S0].

state(S) reads as "the current state is S"; state(S0, S) reads as "currently S0, henceforth S." With this scaffolding the per-construct compilation clauses become almost literal transliterations of the semantics — vminstr/1 emits one instruction and bumps the PC.

The factorial example is shown alongside its compiled bytecode (38 instructions including the jmp 33 trampoline that skips over the function body to the entry point).

Why this matters

The essay's argument runs from "how do I increment a variable" to "how do I write a compiler" via the same move at every step — pick the state representation that admits a small, general relation. Prolog's semicontext DCG notation makes threading state through the relation almost invisible, which is the closest most languages get to imperative-feeling declarative code.

Sits next to no-silver-bullet-llms and the declarative-vs-imperative discussions in message-passing-shared-mutable-state — different angles on the same observation, that state-based reasoning is harder than relation-based reasoning at scale.