# Thinking in States

[[metalevel-at|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:

```prolog
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:

```prolog
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.