Propagators: Computing with Partial Knowledge

12.1 Computation That Isn't a Function

You already rely on propagator networks daily, under other names. A spreadsheet is one: cells hold values, formulas connect them, and changing one cell wakes every formula that depends on it, which updates its cell, which wakes the next — computation spreading through a network until it settles. Reactive UI signals are the same idea: a derived value recomputes when any source changes. A constraint layout engine, like the one behind Auto Layout, solves position and size from constraints that arrive from all sides. An incremental build system repropagates only what a change can reach. Each is a special case of one general model: cells that hold information, and machines that keep the cells consistent as information arrives.

The generalization, due to Radul and Sussman, makes two moves past the spreadsheet. First, a cell holds not a value but partial knowledge — it may know nothing yet, or a range, or an exact value, or that it has been told contradictory things. Second, the connections are multi-directional: where a spreadsheet formula computes one cell from others, a propagator can run whichever way the available knowledge allows. Together these let a network compute with what it has, in whatever order it arrives.

12.2 Cells and Partial Knowledge

The heart of the model is the content of a cell, and the rule for combining two pieces of it. For the quote, partial knowledge is a range: the price is known to lie somewhere between a low and a high bound. Knowing nothing is a wide range; knowing exactly is a range collapsed to a point.

-- Partial knowledge about a price: it lies somewhere in [low, high].
class Price_Range
  create make(l: Money, h: Money)
  require
  ordered: l <= h              -- an empty range is a contradiction; see below
  do
  low := l  high := h
  end
feature
  low: Money
  high: Money

  -- Merge two pieces of knowledge into a sharper one: intersect the ranges.
  merged_with(other: Price_Range): Price_Range
  do
    let l: Money := low
    if other.low > l then l := other.low end
    let h: Money := high
    if other.high < h then h := other.high end
    result := create Price_Range.make(l, h)
  end

  is_known(): Boolean do result := low = high end
invariant
  ordered: low <= high
end

The one essential operation is merged_with, and it has a property that makes the whole model work: merging only ever produces knowledge at least as sharp as what went in. Intersecting ranges can narrow the bounds or leave them, but never widen them. Information in this world is monotone — it accumulates and never retreats. That single discipline is what frees the network from caring about order: because merging is commutative and associative and only ever sharpens, the cell reaches the same final content whichever fact arrives first, and however many times. Order-independence is not engineered; it falls out of a well-chosen merge.

12.3 The Machines Between the Cells

A cell holds knowledge; a propagator moves it. A propagator is a stateless machine wired to some cells: when any of them gains sharper content, the propagator wakes, computes what that implies for the others, and adds it — which may wake further propagators, and so the sharpening spreads until nothing new can be derived and the network goes quiet. Its interface is a single method, and it is deferred — like the language terms of Chapter 10, the vocabulary of propagators is open, each new source a new subclass:

-- A propagator is woken by a neighbor cell and spreads what the change implies.
deferred class Propagator
feature
  wake() deferred   -- recompute from the wired cells; add any sharper content
end

A cell, then, holds its content and the propagators wired to it, and on every accepted fact it wakes them:

class Cell
  create make(initial: Price_Range) do content := initial  neighbors := [] end
feature
  content: Price_Range
  neighbors: Array[Propagator]

  -- Add a fact from any source; keep only if it sharpens; then wake the network.
  add_content(info: Price_Range)
  do
    let sharper: Price_Range := content.merged_with(info)
    if not (sharper.low = content.low and sharper.high = content.high) then
      content := sharper
      across neighbors as p do
        p.wake
      end
    end
  ensure
    never_widens: content.low >= old content.low and content.high <= old content.high
  end
end

The postcondition never_widens states the monotonicity in the type of a contract: a cell's knowledge can only get sharper. That guarantee is what makes a propagator network something you can reason about at all — without it, a cell could oscillate and the network might never settle. Propagators can also be multi-directional, because nothing in the model marks any of a propagator's cells as inputs: one relating a subtotal, a discount, and a total can be written to fire in whichever direction it has the inputs for — deriving the total from the first two, or bounding the discount once the total is known. And because propagators are stateless and only add information, running one in any direction, any number of times, is safe. There is no privileged input and output, only cells that know more or less.

12.4 The Quoting Network

Now the running example comes together. The quote is not one unknown but several: what the goods cost, the tax on them, the shipping charge, and the totals those add up to. Each is a cell, initialized knowing almost nothing — a range from zero to some ceiling. Every source adds what it knows to the cell it knows about, and one kind of propagator ties the cells together, a sum:

-- total = left + right, usable in any direction.
class Sum inherit Propagator
  create make(l: Cell, r: Cell, t: Cell)
  do
    left := l  right := r  total := t
    -- wiring: this propagator is a neighbor of every cell it relates
    l.neighbors.add(this)
    r.neighbors.add(this)
    t.neighbors.add(this)
  end
feature
  left: Cell
  right: Cell
  total: Cell

  wake()
  do
    -- forward: the total lies between the sum of the lows and the sum of the highs
    total.add_content(create Price_Range.make(
      left.content.low + right.content.low, left.content.high + right.content.high))
    -- backward: each part is the total less the other part
    left.add_content(total_less(right))
    right.add_content(total_less(left))
  end

  -- What the total implies about one part, given what is known of the other.
  total_less(other: Cell): Price_Range
  do
    let zero: Money := create Money.zero(total.content.low.currency)
    let low: Money := total.content.low - other.content.high
    if low < zero then low := zero end   -- no part of a price is negative
    result := create Price_Range.make(low, total.content.high - other.content.low)
  end
end

Now build the network and let the sources feed it:

let unknown: Price_Range :=
  create Price_Range.make(create Money.zero(ceiling.currency), ceiling)

let goods: Cell := create Cell.make(unknown)
let tax: Cell := create Cell.make(unknown)
let shipping: Cell := create Cell.make(unknown)
let subtotal: Cell := create Cell.make(unknown)
let quote: Cell := create Cell.make(unknown)

let taxed: Sum := create Sum.make(goods, tax, subtotal)         -- subtotal = goods + tax
let shipped: Sum := create Sum.make(subtotal, shipping, quote)  -- quote = subtotal + shipping

-- Each source adds a partial fact to the cell it knows about, in any order.
goods.add_content(floor_bounds)         -- the order floor raises the low end
goods.add_content(promo_bounds)         -- a promotion lowers the high end
goods.add_content(inventory_bounds)     -- limited stock caps the fulfillable amount
tax.add_content(tax_bounds)             -- the jurisdiction bounds the tax owed
shipping.add_content(shipping_bounds)   -- the carrier bounds the shipping charge

if quote.content.is_known then
  -- low = high: the sources have pinned the quote to a single price
end

Neither Sum is ever called by name. When promo_bounds lowers the high end of goods, goods accepts the sharper range, walks its neighbors, and wakes taxed. taxed lowers the high end of subtotal, which wakes both of its neighbors, taxed and shipped, and shipped lowers the high end of quote. Knowledge flows backwards just as easily. A fact about the quote alone, such as a price the customer has already been shown, wakes shipped, which bounds subtotal and shipping. The change to subtotal then wakes taxed, which bounds goods and tax.

Each add_content intersects the new range with what the cell already knows, so a cell can narrow but never jump to a new value. The spreading stops when no cell can narrow further. Wakes nest rather than queue: a Sum may be woken again by its own write before its first wake has finished. That is harmless, because each nested wake starts from sharper content and only narrows further. The propagators keep no state of their own, so waking one twice with the same inputs adds nothing.

total_less clamps a part's low bound at zero, since no part of a price can be negative. If the total's high bound drops below the least the other part can be, the clamped low ends up above the computed high. An example is a quote capped below the shipping charge. The ordered contract on Price_Range then fires. That is a real contradiction, and it is reported where it entered.

This is additive design carried to its limit. A new source of pricing knowledge — a seasonal surcharge or a regional subsidy — is a new cell and one more Sum wired into the network. It is never an edit to the others; the network simply has one more way to learn. And because merging is monotone and order-free, it makes no difference whether the surcharge is known at checkout or arrives a second later from a slow service: the cell integrates it whenever it comes and settles to the same answer. The engine computes with partial knowledge and keeps computing as knowledge fills in.

12.5 Invariants Keep the Network Reliable

An open, multi-directional network is a frightening thing to trust. There is no single evaluation order to trace, and any number of independently-authored sources feed it at once. What stops two of those sources from quietly disagreeing — like a promotion insisting the price is at most ten versus a floor insisting it is at least twelve — and the network settling on a confident, wrong number?

The invariant does. Look again at Price_Range: its ordered invariant, and the matching precondition on make, say that the low bound may never exceed the high. When two sources disagree, their merge tries to construct a range whose low is above its high — and the contract fires, at the exact moment and place the contradiction entered, naming it. A silent wrong answer becomes a located, explained failure. In a network too open for the type system to check, the invariant is what catches the inconsistency. Constraint does not disappear at the most flexible edge of the system; it moves into the merge, where it guards a computation no signature could describe.

12.6 Provenance, and Taking Facts Back

Monotonicity buys order-independence but seems to forbid something a real quoting engine needs: a promotion can be withdrawn, and its contribution to the quote must then disappear. Information that only accumulates cannot simply be un-accumulated.

The resolution is to record not just what a cell knows but why — the provenance of each contribution, the set of premises it rests on. A cell's content becomes knowledge-relative-to-assumptions, and retracting a premise means recomputing the cell from the contributions that did not depend on it. Within any fixed set of assumptions, information is still monotone and the network still settles; across a change of assumptions, a supervising layer — a truth-maintenance system — rebuilds what the withdrawn premise supported. The withdrawn promo cleanly retracts, not by reversing time, but by asking what the network would have known without it.

Propagators show flexibility in a new dimension — not an open vocabulary, as in Part IV, but an open topology, with sources arriving from any direction and at any time. There is one more species of partial-knowledge computation to meet. Instead of narrowing numeric ranges, it matches and merges structures — asking not "what is the price?" but "what assignment of unknowns makes these values agree?", and searching when more than one might. That is unification and search.