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, from wherever it comes, 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 operation that matters 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 no matter which fact arrives first, or how 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.

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. Because propagators are stateless and only add information, they are also multi-directional: a propagator relating a subtotal, a discount, and a total can 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. There is no privileged input and output, only cells that know more or less.

12.4 The Quoting Network

Now the running example resolves. The quote is a cell, initialized knowing almost nothing — a range from zero to some ceiling. Each source is a propagator that adds what it knows, from its own direction, whenever it learns it:

let quote: Cell := create Cell.make(create Price_Range.make(Money.zero, ceiling))

-- Each source contributes a partial fact; order does not matter.
quote.add_content(floor_bounds)       -- the order floor raises the low end
quote.add_content(promo_bounds)       -- a promotion lowers the high end
quote.add_content(tax_bounds)         -- jurisdiction shifts the range
quote.add_content(inventory_bounds)   -- limited stock caps the fulfillable amount

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

This is additive design carried to its limit. A new source of pricing knowledge — a seasonal surcharge, a regional subsidy — is a new propagator wired to the quote cell. 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 does not matter 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, no function signature that captures what it computes, and any number of independently-authored sources feeding it at once. What stops two of those sources from quietly disagreeing — a promotion insisting the price is at most ten, 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 full system this is the signal a truth-maintenance layer uses to back out an assumption and try another; here the point is narrower and it is the point of the whole book: 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: any number of sources, in any direction, over time. There is one more shape of partial-knowledge computation to meet, and it is the most open technique in the book. Instead of narrowing numeric ranges, it matches and merges structures — asking not "what is the price?" but "what assignment of unknowns makes these shapes agree?", and searching when more than one might. That is unification and search, and it is the final chapter of the frontier.