Module machine 

CK machine — explicit-continuation iterative evaluator.

Overview

This is narju’s sole evaluator. It walks an Exp tree by alternating between two modes:

• Mode::Eval { env, exp } — about to evaluate exp under env. step_eval dispatches on exp and either produces a Val immediately (terminals) or pushes a Cont onto the kont stack and switches to a sub-expression.

• Mode::Apply { val } — just produced val. Pop a Cont from the kont stack; step_apply resumes the paused operation, either producing another val or switching back to Mode::Eval.

Every operand evaluation, every reify scope, every η-expansion lives on the heap kont rather than the Rust stack. The Rust stack depth is O(1) regardless of program size or staging tower depth. (The name is Felleisen’s: C for the control string, K for the continuation stack. Environments ride inside both, so strictly this is a CEK machine with E folded into C and K.)

Where staging happens

The machine does not distinguish “normal” from “staging” evaluation. Staged operations are just the arms of each dispatch that fire when an operand is Val::Code: instead of computing, they call EvalCtx::reflectc, which appends the operation to the innermost open block in the EvalCtx and hands back a fresh residual variable. Reify scopes (Class S below) delimit those blocks and fold them into ANF Let-chains. All state involved lives in the EvalCtx; ScopeSnapshot saves and restores it around each scope — except cells and I/O, which are effects and survive.

Layout of this file

In source order: Mode; the operator-kind enums (BinOpKind, UnOpKind); Cont, the continuation alphabet itself; the resume-descriptor enums (ForceMode, ForceCodeResume, ReifyResume); Machine and its run loop with unwind_to_catch; step_eval; step_apply; the shared dispatch helpers (dispatch_unop, dispatch_binop); and ScopeSnapshot at the end.

Continuation taxonomy

• Class T (tail). Let body, If chosen-branch (Cst), App closure body. Resumes a Mode::Eval directly — no kont frame.

• Class O (operand). Binary/unary primitives push a cont holding the unevaluated sibling (binary) or the op-kind (unary), then evaluate the first/only operand. Dispatch happens on resume in step_apply.

• Class S (staged). Reify scopes (If-Code, LiftRef-Code, Run-Code, run-now, Evalms) push Cont::ForceCode { resume: ReifyDrain { saved, then } } or Cont::ReifyVExit { saved, resume }, save a ScopeSnapshot, and evaluate the staged body under a fresh block. On completion the kont drains ctx.block into a Let-chain and dispatches a ReifyResume to describe what surrounding staged construction is being assembled.

  Lift’s Clo arm η-expansion is implemented as a nested ForceCode → LiftCloFinish pair that grows the kont rather than the Rust stack.

• Class C (error). Catch pushes Cont::CatchExit { saved } and evaluates the body. The Machine’s run loop catches Err results from step_eval/step_apply and walks the kont via unwind_to_catch, restoring state from each popped cont until it finds a CatchExit (or runs out, in which case the original error propagates).

Structs

Machine

The CK machine’s execution state.

ScopeSnapshot

A snapshot of the staging-related fields of EvalCtx. Used to save and restore the staging context at scope boundaries (reify, reifyc, reifyv, run_now, Catch).

Enums

BinOpKind

Binary primitive operators that share the same shape:

Cont

An entry on the kont stack — represents pending work to resume when the current sub-evaluation produces a Val.

ForceCodeResume

Discriminator for what to do with the Exp produced by a ForceCode continuation. Different callers want to assemble different surrounding constructions from the forced Exp.

ForceMode

How Cont::ForceCode treats a non-Code value.

Mode

The CK machine alternates between two modes:

ReifyResume

Discriminator for what shape of staged Exp to assemble when a reify scope completes. Each reify scope in the recursive code corresponds to one of these — the resume action knows what surrounding Exp the reified body slots into.

UnOpKind

Unary primitive operators that share the same shape: