CXL: a staged language

A clinker config can contain expressions: coalesce(email, "n/a"), age > 18, a computed column. Each runs on every record, millions of times. That puts two demands in tension. A typo or a nonsense comparison (a_string > a_date) must be caught before the job starts, so a three-hour run doesn’t die at row nine million. And evaluation must be fast per record. CXL, Clinker’s expression language, meets both by being a staged language: it separates “understand the formula” from “run the formula,” and does the understanding exactly once. This is the whole of Planning & Expressions in one subsystem, so it’s a fitting place to finish.

Prerequisites

• Error handling

→

Leads to

• Dispatching a node

What you’ll be able to do

• Name CXL’s three teaching stages (parse, typecheck, eval) and the distinct Rust type each one produces.
• Trace a formula like price + 10 through those stages and say what each boundary type proves about the stage before it.
• Explain why typechecking runs once at plan time before any record, and what makes that possible (the closed Value/Type set).
• Distinguish “compile once to closures” from a tree-walking interpreter, and describe what per-record evaluation actually does.
• Write a small compile-once-to-closures evaluator in plain Rust that mirrors CompiledExpr.

New terms in this lesson (each is also expanded inline at the point you first need it):

• CXL: Clinker’s expression language; here, seen as a staged language.
• staged language: a language processed in distinct, ordered phases (parse → typecheck → eval), where each phase’s output is a separate type that the compiler will not let you skip past.
• parse / typecheck / eval: the three stages. Turn text into a tree (parse), assign every node a type and reject nonsense (typecheck), then run the tree against data (eval).
• expression (AST): a formula’s structure as a tree of Expr nodes (an abstract syntax tree), not its source text.
• Value: the closed set of cell kinds a CXL Type mirrors (from The Value cell).

Predict first

✋ Predict first

A clinker config contains the formula a_string > a_date, comparing a string column to a date column. The job is set to process 9,000,000 records. At which point does Clinker reject this nonsense: before record 1, somewhere in the middle, at the last record, or never (it returns garbage)? Write down your answer and one sentence of why before revealing.

Decide on your answer before you open the reveal — committing a guess is what makes it stick.

Reveal the answer

It is rejected before record 1, at plan time, the moment the formula is typechecked, which happens once before any data flows.

Why: CXL is a staged language. The formula first parses to a tree, then a separate typecheck pass assigns every node a type and checks the operation makes sense. Comparing a String to a Date has no valid result type, so typecheck returns Err and no runnable program is produced. Because the evaluator only accepts a typechecked program, there is no way to even start running a formula that failed typecheck.

The tempting wrong model is “it checks each row as it goes, so it’d fail at row 1 while running.” That conflates two stages. The check isn’t a per-record guard inside the run loop. It happens before the loop exists, on the formula’s structure, exactly once. That is the whole point of staging: pay the understanding cost once, up front, so a three-hour run can’t die at row nine million on an error that was knowable before record one.

A pipeline of typed stages

A formula moves through CXL as a sequence of stages, each producing a distinct type:

"price + 10"  ──parse──▶  Program  ──typecheck──▶  TypedProgram  ──compile──▶  CompiledProgram
                          (an AST)                  (AST + types)              (closures)

Those aren’t just phases in a function; they’re different Rust types, and the compiler enforces the order. You cannot hand an un-typechecked Program to the evaluator, because the evaluator’s input type is TypedProgram, which only the typechecker produces. It’s the same proof-handle idea as ValidatedPath (Newtype proof tokens) and CompiledPlan (The plan/runtime boundary): each stage’s output type is evidence that the stage ran.

Evidence note

The teaching arc here is parse → typecheck → eval. The real crate inserts a resolve (name-resolution) pass between parse and typecheck, so the true boundary chain is Program → ResolvedProgram → TypedProgram → CompiledProgram. The principle is identical (distinct types enforce stage order); there’s just one more stage than the three we walk through.

Stage 1: parse to an AST

Parsing turns the formula text into an abstract syntax tree: a tree of Expr nodes. This is the closed-enum story from Data & Representation, now describing a language rather than a value:

cxl ·ast.rs ·Expr type @19acdcb4

/// CXL expression — the core of the language. All variants carry a NodeId and Span.
pub enum Expr {
    Binary { op: BinOp, lhs: Box<Expr>, rhs: Box<Expr>, /* … */ },
    Unary { op: UnaryOp, operand: Box<Expr>, /* … */ },
    Literal { value: LiteralValue, /* … */ },
    FieldRef { name: Box<str>, /* … */ },
    MethodCall { receiver: Box<Expr>, method: Box<str>, args: Vec<Expr>, /* … */ },
    Coalesce { lhs: Box<Expr>, rhs: Box<Expr>, /* … */ },
    // ... ~20 variants in all
}

Two Data & Representation ideas show up at once. It’s a closed enum, a fixed set of expression shapes, so every later stage can match exhaustively and the compiler guarantees no shape is forgotten (Reading a value with match). And the children are Box<Expr>: a tree is recursive, and a recursive type needs the indirection a Box provides, or its size would be infinite (the Value-cell boxing, smart pointers). price + 10 parses to Binary { op: Add, lhs: FieldRef("price"), rhs: Literal(10) }, a little tree. Every node also carries a Span, so a later error can point back at the source (Span-preserving parse).

Stage 2: typecheck, before any record runs

Now the formula has structure but no guarantees. Typechecking walks the AST against the record schema and assigns every node a type, drawn from a closed set that mirrors the nine Value shapes:

cxl ·types.rs ·Type type @19acdcb4

pub enum Type {
    Null, Bool, Int, Float, String, Date, DateTime, Array, Map,
    Numeric,            // the int/float union
    Any,                // unknown
    Nullable(Box<Type>),
}

The typechecker’s signature is the pedagogical crux. On success it yields a TypedProgram; on failure, a list of diagnostics and nothing runnable:

cxl ·pass.rs ·type_check fn @19acdcb4

pub fn type_check(
    resolved: ResolvedProgram,
    schema: &Row,
) -> Result<TypedProgram, Vec<TypeDiagnostic>> { /* … */ }

Read what the Result guarantees. If your formula compares a String to a Date, type_check returns Err(...). No TypedProgram is ever built. And since the evaluator only accepts a TypedProgram, evaluation of a type-incorrect formula is literally unreachable: not “checked again at run time,” but unrepresentable. That’s how the closed Value set you met in the Value-cell lesson pays off: because the shapes are fixed and known, a formula over them can be fully typechecked at plan time, and a type error fails the job before record one, exactly the “validate once at the boundary” discipline of the plan/runtime boundary, now for expressions.

Stage 3: compile once to closures, evaluate per record

The TypedProgram is correct but still a tree, and walking a tree, re-matching every Expr variant, on every record, would be slow. So CXL does what the plan/runtime boundary did for the whole plan, one level down: it lowers the typed AST once into a tree of closures, then runs that per record. The module doc names the strategy outright: “Compile-once-to-closures evaluator.”

cxl ·compiled.rs ·CompiledProgram type @19acdcb4

// each lowered node IS a closure
type CompiledExpr<S> =
    Box<dyn Fn(&mut Frame<S>) -> Result<Value, EvalError> + Send + Sync>;

pub(crate) struct CompiledProgram<S: RecordStorage + 'static> {
    statements: Vec<CompiledStmt<S>>,
}

// lowered exactly once, then reused across every record (and every thread)
pub(crate) fn compile<S>(typed: &TypedProgram) -> CompiledProgram<S> { /* lower each stmt once */ }

Each AST node becomes a boxed closure that captures its already-compiled children by value. A literal bakes its Value once at lowering instead of re-reading the AST per record; a field reference captures its resolved name. Per-record evaluation is then just calling closures: a sequence of direct Fn calls with no central dispatch match and no re-indexing of the AST. Because the compiled program is immutable, one copy is shared across records and threads (the per-record bookkeeping lives in a separate state value the caller threads in). This is the same generic S: RecordStorage from One reader, every format: the compiled closures are monomorphized over the storage, so field reads stay zero-cost.

Worked → completion → faded

Now you build the staged evaluator yourself, the eval stage in miniature, scaffolded from a fully-worked version down to one you write from a skeleton. Each rung compiles on std alone and mirrors CompiledExpr: each node becomes a closure capturing its already-compiled children. The one new idea here is compile once, call many; the rest is the closed-enum match you already command, so the scaffolding fades fast.

Worked: read the whole thing

Parse → an AST, compile-once → closures, evaluate per record. Run it and watch compile execute a single time while the per-record loop just calls the result:

rust // editable

reset ▶ run

use std::collections::HashMap;

// Stage 1 — the AST. A recursive enum needs Box for its children (lesson 09).
enum Expr {
  Lit(i64),
  Field(String),
  Add(Box<Expr>, Box<Expr>),
}

type Record = HashMap<String, i64>;

// Stage 3 — compile ONCE into a closure, instead of re-walking Expr per record.
type Compiled = Box<dyn Fn(&Record) -> i64>;

fn compile(e: Expr) -> Compiled {
  match e {
      Expr::Lit(n) => Box::new(move |_rec| n),               // bake the literal once
      Expr::Field(name) => Box::new(move |rec| *rec.get(&name).unwrap_or(&0)),
      Expr::Add(l, r) => {
          let lc = compile(*l);      // children compiled once, captured by value
          let rc = compile(*r);
          Box::new(move |rec| lc(rec) + rc(rec))
      }
  }
}

fn main() {
  // formula: price + 10  ->  Add(Field("price"), Lit(10))
  let expr = Expr::Add(
      Box::new(Expr::Field("price".into())),
      Box::new(Expr::Lit(10)),
  );

  // Compile the expression ONE time...
  let program = compile(expr);

  // ...then evaluate it over many records — no AST re-walk per record.
  let records = [
      HashMap::from([("price".to_string(), 100)]),
      HashMap::from([("price".to_string(), 250)]),
      HashMap::from([("price".to_string(), 7)]),
  ];
  for rec in &records {
      println!("{}", program(rec)); // 110, 260, 17
  }
}

use std::collections::HashMap; // Stage 1 — the AST. A recursive enum needs Box for its children (lesson 09). enum Expr { Lit(i64), Field(String), Add(Box<Expr>, Box<Expr>), } type Record = HashMap<String, i64>; // Stage 3 — compile ONCE into a closure, instead of re-walking Expr per record. type Compiled = Box<dyn Fn(&Record) -> i64>; fn compile(e: Expr) -> Compiled { match e { Expr::Lit(n) => Box::new(move |_rec| n), // bake the literal once Expr::Field(name) => Box::new(move |rec| *rec.get(&name).unwrap_or(&0)), Expr::Add(l, r) => { let lc = compile(*l); // children compiled once, captured by value let rc = compile(*r); Box::new(move |rec| lc(rec) + rc(rec)) } } } fn main() { // formula: price + 10 -> Add(Field("price"), Lit(10)) let expr = Expr::Add( Box::new(Expr::Field("price".into())), Box::new(Expr::Lit(10)), ); // Compile the expression ONE time... let program = compile(expr); // ...then evaluate it over many records — no AST re-walk per record. let records = [ HashMap::from([("price".to_string(), 100)]), HashMap::from([("price".to_string(), 250)]), HashMap::from([("price".to_string(), 7)]), ]; for rec in &records { println!("{}", program(rec)); // 110, 260, 17 } }

compile runs once and returns a closure tree; the per-record loop just calls it. The recursion is the staging: compiling an Add compiles its children first, captures those compiled closures by value, and hands back a closure that calls them. By the time main reaches the loop, every match and every child lookup is already done.

Completion: lower the Add node

Same evaluator, but the Add arm is left for you. Both children are already compiled into lc and rc; your job is the closure that runs per record. It must capture lc and rc and, given a record, return their sum. The other two arms are done; fill the one gap so the formula price + 10 prints 110, 260, 17.

rust // editable

reset ▶ run

use std::collections::HashMap;

enum Expr {
  Lit(i64),
  Field(String),
  Add(Box<Expr>, Box<Expr>),
}

type Record = HashMap<String, i64>;
type Compiled = Box<dyn Fn(&Record) -> i64>;

fn compile(e: Expr) -> Compiled {
  match e {
      Expr::Lit(n) => Box::new(move |_rec| n),
      Expr::Field(name) => Box::new(move |rec| *rec.get(&name).unwrap_or(&0)),
      Expr::Add(l, r) => {
          let lc = compile(*l);   // left child, already compiled
          let rc = compile(*r);   // right child, already compiled
          // TODO: return a closure that, per record, returns lc(rec) + rc(rec).
          todo!()
      }
  }
}

fn main() {
  let expr = Expr::Add(
      Box::new(Expr::Field("price".into())),
      Box::new(Expr::Lit(10)),
  );
  let program = compile(expr);
  for price in [100, 250, 7] {
      let rec = Record::from([("price".to_string(), price)]);
      println!("{}", program(&rec));
  }
}

use std::collections::HashMap; enum Expr { Lit(i64), Field(String), Add(Box<Expr>, Box<Expr>), } type Record = HashMap<String, i64>; type Compiled = Box<dyn Fn(&Record) -> i64>; fn compile(e: Expr) -> Compiled { match e { Expr::Lit(n) => Box::new(move |_rec| n), Expr::Field(name) => Box::new(move |rec| *rec.get(&name).unwrap_or(&0)), Expr::Add(l, r) => { let lc = compile(*l); // left child, already compiled let rc = compile(*r); // right child, already compiled // TODO: return a closure that, per record, returns lc(rec) + rc(rec). todo!() } } } fn main() { let expr = Expr::Add( Box::new(Expr::Field("price".into())), Box::new(Expr::Lit(10)), ); let program = compile(expr); for price in [100, 250, 7] { let rec = Record::from([("price".to_string(), price)]); println!("{}", program(&rec)); } }

💡 Hint 1

The compiling work is done: lc and rc are closures. You only need the per-record step. Box::new(move |rec| ...) captures both by value; inside, call them: lc(rec) and rc(rec) each return an i64.

Show solution

Expr::Add(l, r) => {
    let lc = compile(*l);
    let rc = compile(*r);
    Box::new(move |rec| lc(rec) + rc(rec)) // compiled once; this closure is the per-record step
}

Notice the split: compile(*l) and compile(*r) run once, at lowering time; the move |rec| lc(rec) + rc(rec) body runs once per record. That boundary, expensive structure work up front and cheap calls per record, is the staged-evaluation model in three lines.

Faded: add a Sub node from a skeleton

Now with much less scaffolding. Extend the language with subtraction. Add a Sub variant to Expr, then add its arm to compile so it lowers exactly like Add but subtracts. The formula below is price - 10, so the records 100, 250, 7 should print 90, 240, -3.

rust // editable

reset ▶ run

use std::collections::HashMap;

enum Expr {
  Lit(i64),
  Field(String),
  Add(Box<Expr>, Box<Expr>),
  // TODO: add a Sub variant with the same shape as Add.
}

type Record = HashMap<String, i64>;
type Compiled = Box<dyn Fn(&Record) -> i64>;

fn compile(e: Expr) -> Compiled {
  match e {
      Expr::Lit(n) => Box::new(move |_rec| n),
      Expr::Field(name) => Box::new(move |rec| *rec.get(&name).unwrap_or(&0)),
      Expr::Add(l, r) => {
          let lc = compile(*l);
          let rc = compile(*r);
          Box::new(move |rec| lc(rec) + rc(rec))
      }
      // TODO: lower Sub the same way Add is lowered, but subtract.
  }
}

fn main() {
  // formula: price - 10
  let expr = Expr::Sub(
      Box::new(Expr::Field("price".into())),
      Box::new(Expr::Lit(10)),
  );
  let program = compile(expr);
  for price in [100, 250, 7] {
      let rec = Record::from([("price".to_string(), price)]);
      println!("{}", program(&rec)); // 90, 240, -3
  }
}

use std::collections::HashMap; enum Expr { Lit(i64), Field(String), Add(Box<Expr>, Box<Expr>), // TODO: add a Sub variant with the same shape as Add. } type Record = HashMap<String, i64>; type Compiled = Box<dyn Fn(&Record) -> i64>; fn compile(e: Expr) -> Compiled { match e { Expr::Lit(n) => Box::new(move |_rec| n), Expr::Field(name) => Box::new(move |rec| *rec.get(&name).unwrap_or(&0)), Expr::Add(l, r) => { let lc = compile(*l); let rc = compile(*r); Box::new(move |rec| lc(rec) + rc(rec)) } // TODO: lower Sub the same way Add is lowered, but subtract. } } fn main() { // formula: price - 10 let expr = Expr::Sub( Box::new(Expr::Field("price".into())), Box::new(Expr::Lit(10)), ); let program = compile(expr); for price in [100, 250, 7] { let rec = Record::from([("price".to_string(), price)]); println!("{}", program(&rec)); // 90, 240, -3 } }

💡 Hint 1

A Sub node holds the same two boxed children as Add: Sub(Box<Expr>, Box<Expr>). Its compile arm is the Add arm with + swapped for -. Because Expr is a closed enum, once you add the variant the match will refuse to compile until you handle it: the exhaustiveness check from the reading-a-value lesson telling you which arm you owe.

Show solution

enum Expr {
    Lit(i64),
    Field(String),
    Add(Box<Expr>, Box<Expr>),
    Sub(Box<Expr>, Box<Expr>),
}

// ...in compile's match:
Expr::Sub(l, r) => {
    let lc = compile(*l);
    let rc = compile(*r);
    Box::new(move |rec| lc(rec) - rc(rec))
}

You just extended the language by one operator and felt the real evaluator’s shape: one lowering pass per node, then cheap repeated calls. Adding the variant forced a new match arm, and the closed enum makes “you forgot to handle Sub” a compile error, not a runtime surprise. (CXL also has language-level closures, it => body for array operations like filter/map, which lower to a host loop over a separately-compiled body. Same mechanism, exposed to the user.)

Want Box and recursive types from first principles, no engine framing? Read the docs →

// quick check

Why can a type-incorrect CXL formula never be evaluated at run time?

• The evaluator re-checks types on every record and skips bad ones
• type_check returns Err and produces no TypedProgram; since the evaluator only accepts a TypedProgram, evaluating a type-incorrect formula is unrepresentable
• Type errors are routed to the dead-letter queue

Retrieval checkpoint

✓ Checkpoint — CXL staging

💡 Hint 1

Read type_check’s return type: what comes back on Err? Then read the first line of eval/compiled.rs. The two together explain why a bad formula can’t reach the per-record path.

What the stages establish

Expr is the parsed AST (a closed, boxed-recursive enum). Type is the closed type set the typechecker assigns. type_check returns Result<TypedProgram, Vec<TypeDiagnostic>>: an error yields no TypedProgram, so eval is unreachable for a bad formula. eval/compiled.rs lowers a TypedProgram once into a CompiledProgram of closures, run per record. Parse, typecheck, eval: distinct typed stages, with the expensive understanding done once.

// quick check

What does 'compile once to closures' save compared with a tree-walking interpreter?

• It avoids allocating the AST at all
• It lowers the typed AST a single time into closures that capture their children, so per-record evaluation is direct closure calls, with no re-matching every Expr variant on every record
• It typechecks each record individually

// quick check

Spaced recall from the plan/runtime boundary lesson: at the whole-plan level, the executor accepts only a &CompiledPlan and refuses a raw PipelineConfig. What is the shared idea between that boundary and CXL's parse → typecheck → eval staging?

• Both make the program faster by avoiding heap allocation
• Both push expensive, checkable work to plan time and freeze it behind a typed handle, so the per-record/run path only reads results it can't recompute or skip: decide once, run many
• Both run the validation again on every record as a safety net

// quick check

Which statement about CXL's stages is the MISCONCEPTION to correct?

• parse → typecheck → eval are distinct Rust types, and the compiler enforces the order because each stage's input is the previous stage's output type
• Typechecking is a safety net the evaluator re-runs per record, so a type error is caught the first time a bad row reaches that expression
• Compiling once to closures bakes each node's structure in at lowering time, so per-record work is just calling closures

You should be able to:

• You can name CXL's three stages (parse, typecheck, eval) and the distinct type each produces (Program → TypedProgram → CompiledProgram)
• You can trace price + 10 through the stages and say what each boundary type proves
• You can explain why typechecking happens before any record and what makes it possible (the closed Value/Type set)
• You can distinguish 'compile once to closures' from a tree-walker and say what per-record evaluation does
• You wrote a compile-once-to-closures evaluator (and extended it with a Sub node) that mirrors CompiledExpr

Verify in the checkout:

grep -n 'pub enum Expr' crates/cxl/src/ast.rs
grep -n 'pub enum Type' crates/cxl/src/typecheck/types.rs
grep -n 'pub fn type_check' crates/cxl/src/typecheck/pass.rs
grep -n 'Compile-once-to-closures' crates/cxl/src/eval/compiled.rs

Connections

That closes Planning & Expressions. You’ve seen the engine’s typed proof handles (ValidatedPath, the strict/spanned parse, CompiledPlan), its failure taxonomy (PipelineError, abort versus quarantine), and now the staged language that runs over every record. A single thread runs through all of it: push the work and the proof to plan time, and let the type system carry the guarantee into run time. Execution & Memory descends into that run time: how the DAG executor dispatches nodes, moves records across threads, and stays inside a memory budget.

Prerequisites

• Error handling

→

Leads to

• Dispatching a node

Go deeper on the Rust (optional; for the same concept taught from first principles in The Rust Book):

• Want Box and recursive types (the Box<Expr> in the AST) from first principles? Read the docs →

Glossary terms used: CXL, Value.

Mark this lesson complete