Evaluators You Can Extend

11.1 Closed Syntax, Open Operators

The insight that makes an extensible evaluator possible is a separation. Evaluation has two parts that are usually tangled together: the structure of expressions — how they are put together and taken apart — and the operators — what the fundamental operations actually do. The structure is small and can be fixed forever. The operators are the part that must stay open.

So we close the one and open the other. An expression is one of a tiny, sealed set of forms: a literal value, a reference to a name, or an application of an operator to arguments. That is the whole syntax, and it will never grow — which means the evaluator can match it exhaustively, with the compiler proving every form is handled.

-- The syntax is closed: exactly three forms, sealed and exhaustively handled.
union Expr
  Lit(value: Money)                       -- a literal price
  Ref(name: String)                       -- a name, resolved in the environment
  Apply(operator: String, args: Array[Expr])  -- operator (named, resolved at runtime) applied to args
end

Notice the deliberate asymmetry, which is the whole book in miniature. The syntax is sealed — a closed core the evaluator reasons about completely. The operators, named by the strings inside Apply, are open — a vocabulary that grows without limit. Constraint in the structure, flexibility in the vocabulary, and the seam between them guarded, as we are about to see, by contract.

11.2 An Evaluator With a Table

The evaluator walks the closed syntax and, when it meets an application, looks the operator up in a table of primitives — the same data-directed dispatch of §9.2, now at the heart of the interpreter. Literals evaluate to themselves; references are resolved in an environment; applications dispatch through the table.

class Evaluator
  create make() do primitives := {} end
  feature
    primitives: Map[String, Primitive]

    -- Extend the evaluator at runtime: teach it a new fundamental operation.
    install(name: String, p: Primitive)
      do
        primitives.put(name, p)
      end

    eval(expr: Expr, env: Environment, order: Placed): Money
      do
        match expr of
          when Lit as l then
            result := l.value
          when Ref as r then
            result := eval(env.lookup(r.name), env, order)     -- resolve a named rule
          when Apply as a then
            result := apply_op(a, env, order)
        end
      end

    apply_op(a: Apply, env: Environment, order: Placed): Money
      require
        known_op: primitives.contains_key(a.operator)     -- the table may not have it
      do
        result := primitives.get(a.operator).call(a.args, env, order, this)
      end
end

The match over Expr is exhaustive and compiler-checked, because the syntax is sealed. Everything uncertain has been pushed into the one line where an operator is looked up by name — and that line is guarded by the precondition known_op. The structure is proven; the openness is fenced.

11.3 New Primitives While Running

A primitive is an operation that takes unevaluated argument expressions, evaluates the ones it needs through the same evaluator, and returns a price. Passing the evaluator in (ev) is what lets a primitive recurse into its arguments — so operators compose to any depth without knowing about one another.

deferred class Primitive
  feature
    call(args: Array[Expr], env: Environment, order: Placed, ev: Evaluator): Money
      do end
end

-- "the smaller of two prices" — a flooring/capping building block.
class Lesser inherit Primitive
  create make() do end
  feature
    call(args: Array[Expr], env: Environment, order: Placed, ev: Evaluator): Money
      require
        arity: args.length = 2
      do
        let a: Money := ev.eval(args.get(0), env, order)
        let b: Money := ev.eval(args.get(1), env, order)
        if a < b then result := a else result := b end
      end
end

Installing it teaches the running evaluator a word it did not have a moment ago — and no line of the Evaluator class is touched:

let ev: Evaluator := create Evaluator.make()
ev.install("lesser", create Lesser.make())
-- later, from entirely different code, loaded from a plugin, added mid-session:
ev.install("round_to_cents", create Round_To_Cents.make())

This is extension in its strongest form in the whole book. In Chapter 9 you could add a new rule; here you can add a new fundamental operation of the language itself, at runtime, from outside. The evaluator is complete without knowing what operators will ever exist — it knows only how to find one and hand it its arguments.

11.4 Names, So Rules Can Build on Rules

The Ref form and the environment are what let one rule refer to another by name — so a library of pricing rules can be assembled, each defined in terms of the others, and each definable at runtime.

class Environment
  create make() do defs := {} end
  feature
    defs: Map[String, Expr]

    define(name: String, e: Expr)
      do
        defs.put(name, e)
      end

    lookup(name: String): Expr
      require
        defined: defs.contains_key(name)      -- an unbound name is a located failure
      do
        result := defs.get(name)
      end
end

Now the vocabulary and the definitions both grow at runtime, independently of the evaluator. A manager defines "summer_sale" as an expression; another rule references "summer_sale" by name; a plugin installs a "loyalty_discount" primitive that the summer-sale rule uses — and none of this required editing, recompiling, or even restarting the evaluator. The language has become a living thing, extended from the outside in three independent directions: new syntax never (it is sealed), new operators freely, new named definitions freely.

11.5 When Contracts Are Nearly All You Have

Step back and count what the type system still guarantees inside this evaluator. That the syntax is exhaustively handled — yes, because it is sealed. Almost everything else, it cannot see. It cannot promise that an applied operator is installed, that a referenced name is bound, that a primitive receives the number of arguments it expects, or that the value any primitive returns is well-formed. The evaluator is so open that the compiler, which carried the argument through all of Part II, is nearly silent here.

And yet the system is not unguarded — because every one of those gaps has a contract standing in it. known_op guards the operator lookup; defined guards the name resolution; arity guards each primitive's argument count; and the membrane postconditions from §9.5 still guard the price on its way back to the core. Each is a named, located promise that turns what would be an inscrutable runtime failure deep in a plugin into a precise report at the exact seam that was violated. This is the book's thesis at its most extreme: push openness as far as it will go, and contracts are not merely a supplement to the type system — they become, very nearly, the guarantees themselves.

11.6 The Far End of the Frontier

Part IV set out to open the frontier, and it has now reached the edge of it. The three chapters were three widenings of a single door. Generic operations opened the set of behaviors a fixed operation could have (Chapter 9). Domain languages opened the set of rules that could be expressed and made them data (Chapter 10). Extensible evaluators opened the set of primitives the language itself is built from, at runtime (Chapter 11). At each step the type system said less and the contracts said more, and at each step the value produced still crossed into the constrained core only through the membrane — so the openness, however wide, stayed fenced.

There is one more kind of flexibility, and it is different in nature rather than degree. Everything in Part IV still computed in one direction: an expression in, a price out, the evaluator pulling values from leaves to root. But some problems do not arrive that way. Information shows up in fragments, from several directions at once, and the answer must be assembled from partial knowledge that no single evaluation order can capture — a network settling toward a solution rather than a tree reducing to a value. That is Part V, and it is where the open techniques of this book meet the hardest shape of all: computing when you do not yet know everything, and may never. It begins with propagators.