Relix

Problem solving

Iterate until it settles

Grain: one row per thing that settles (a page, a cell) · Class: Iteration · Signals: converge, iterate until stable, simulate rounds, settle, numeric fixpoint, generations · Operators: ITERATE

The problem

"Rank these pages by a score that is refined until it stops moving. Or run a cellular automaton forward a few generations, where cells are born and die each round."

How to recognise it

The question describes a computation that settles rather than accumulates — converge, until stable, simulate N rounds, until the numbers stop moving, generations. Each round starts from what the last round produced and replaces it; the answer is the final round.

This is the tell that separates it from recursion (FIX): FIX only ever adds rows and terminates on its own when nothing new appears. ITERATE replaces the whole state each round, so rows can come and go — which is exactly what a score being refined, or a cell dying, needs, and what FIX cannot express.

ITERATE name (base, step) binds name to the previous round's whole output; the step's output replaces it. Say when to stop:

The two UNTIL forms require a round cap and do not return a result they did not reach.

Recipe 1: converge to a fixpoint (UNTIL … WITHIN)

PageRank refines every page's score by passing it along outgoing links, round after round, until the scores stop moving. A page's rank is the share of a random surfer's time spent on it.

Query
Links := [
| src | dst |
|-----|-----|
| A   | B   |
| A   | C   |
| B   | C   |
| C   | A   |
| D   | C   |
];

Pages     := { δ (π src → page (Links) ∪ π dst → page (Links)) };
OutDegree := { γ src, COUNT(*) → out (Links) };
Weighted  := { Links ⋈ OutDegree };

-- 0.0375 is the jump share: (1 − 0.85) / 4 pages
Rank := { ITERATE R (
  π page, 0.25 → rank (Pages),
  π page, 0.0375 + 0.85 * Coalesce(passed, 0) → rank (
    Pages ⟕ Pages.page = In.dst ρ In(dst, passed) (
      γ dst, SUM(rank / out) → passed (ρ From(src, rank) (R) ⋈ Weighted)))
) UNTIL rank WITHIN 0.0001 PER page MAX 100 ROUNDS };
query { τ rank DESC (Rank) };
Result
 page  rank
 ────  ──────────────
 C     0.394199878685
 A      0.37249131329
 B      0.19580880811
 D             0.0375
(4 rows)

The step reads the previous round's (page, rank) as R, passes each page's rank along its links (rank / out per link), sums what arrives at each destination, and keeps a page nothing links to via the outer join. UNTIL rank WITHIN 0.0001 PER page stops when no page's rank moved by more than the tolerance between rounds.

A scalar numeric fixpoint — Newton's method for a square root, x → (x + n/x) / 2 — is the same shape with one row and one UNTIL column.

Recipe 2: simulate rounds (a state machine)

Conway's Life is the canonical state machine: each generation replaces the last, and a cell's fate depends on its live neighbours. ROUNDS 4 runs the glider forward four generations.

Query
Offsets := [
| dx | dy |
|----|----|
| -1 | -1 |
| -1 | 0  |
| -1 | 1  |
| 0  | -1 |
| 0  | 1  |
| 1  | -1 |
| 1  | 0  |
| 1  | 1  |
];

Glider := [
| x | y |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 0 | 2 |
| 1 | 2 |
| 2 | 2 |
];

Later := { ITERATE Board (
  Glider,
  π x, y (σ n = 3 (ρ C(x, y, n) (γ nx, ny, COUNT(*) → n (π x + dx → nx, y + dy → ny (Board × Offsets)))))
  ∪ π x, y (σ n = 2 (ρ C(x, y, n) (γ nx, ny, COUNT(*) → n (π x + dx → nx, y + dy → ny (Board × Offsets)))) ⋈ Board)
) ROUNDS 4 };
query { τ x, y (Later) };
Result
 x  y
 ─  ─
 1  3
 2  1
 2  3
 3  2
 3  3
(5 rows)

The step counts live neighbours (Board × Offsets, grouped), keeps cells with exactly three (a birth) and cells with exactly two that were already alive (survival). Rows are born and die each round — the whole board is replaced — which is why this is ITERATE, not FIX. Swapping ROUNDS 4 for UNTIL STABLE MAX 50 ROUNDS would settle a still life, report a blinker as a period-2 cycle, and report the glider as not settling (it moves forever).

Variations

Pitfalls

Check it