conteff

A small language with algebraic effects, delimited continuations (shift/reset), and first-class undelimited continuations (call_cc), implemented as a tree-walking interpreter in Rust.

The interesting part is how the control operators work: the evaluator is written as ordinary recursive code, turned into cloneable coroutines by diapause. Capturing a continuation is cloning a suspended coroutine, which makes every continuation in the language first-class and multi-shot, essentially for free.

This is a proof-of-concept project; the language is deliberately minimal.

Example

eff Choose(a, b);

let results = [];
handle {
  let x = perform Choose(1, 2);
  let y = perform Choose(10, 20);
  array_push(results, x + y);
} with {
  // Resuming twice runs the rest of the computation once per
  // alternative, so all four combinations are explored.
  Choose(a, b) => {
    resume(a);
    resume(b)
  }
};
results  // => [11, 21, 12, 22]

resume is a plain value: call it zero times to abort the handled expression (exceptions), once to answer the perform (dynamic binding, generators), or many times to fork the rest of the computation (nondeterminism). You can even store it in a variable and call it after the handle expression has finished.

Syntax tour

Informal, by example — the test suite under tests/ is the real spec.

Values and expressions

let n = 42;                // int (i32)
let s = "hi";              // string
let b = true;              // bool
let nothing = null;        // null
let xs = [1, "two", [3]];  // arrays are mutable, shared by reference

n + 1; n - 1; n * 2; n / 2; n % 2;   // arithmetic
"a" + "b";                            // + concatenates strings
1 < 2; 1 <= 2; 1 > 2; 1 >= 2;         // comparison
xs == [1, "two", [3]];                // == is structural for arrays
!b; -n; b && true; b || false;        // logic (&& and || short-circuit)

xs[0];          // indexing
xs[0] = 10;     // index assignment

Blocks are expressions: the value of { stmt; stmt; expr } is the trailing expression's value, or null when there is none.

Bindings, functions and control flow

let x = 1;      // declare
x = 2;          // assign (the binding must exist)

fn add(a, b) { a + b }        // function declaration
let inc = x => x + 1;         // arrow function, expression body
let mul = (a, b) => { a * b }; // arrow function, block body

fn make_counter() {           // closures capture their environment
  let n = 0;
  () => { n = n + 1; n }
}

if (x == 2) { println("two"); } else if (x == 3) { println("three"); }
else { println("other"); }

while (x < 10) { x = x + 1; }

fn f() { return 1; }          // early return
assert x == 10;               // aborts with an error when false

// Line comments look like this.

Builtins

print(x) / println(x) (these perform the Print effect; see below), array_push(xs, v), array_length(xs), to_string(v), and the control operators call_cc, shift, reset.

Effects and handlers

eff declares an effect with a fixed arity (parameter names are for documentation only). Effect identity is name-based.

eff Ask(question);

fn greeting() {
  let name = perform Ask("What is your name?");
  "Hello, " + name + "!"
}

handle greeting() with {
  Ask(q) => {
    println("Q: " + q);
    resume("conteff")   // the perform expression evaluates to "conteff"
  }
}

• perform Eff(args) suspends the current computation and searches outwards for the nearest enclosing handle with a matching clause.
• Inside a clause, resume is bound to the continuation of the perform. Handlers are deep: resuming reinstalls the handler around the rest of the body. Because of this, resume cannot be used as a clause parameter name (e.g. Ask(resume) => ... is a parse error); it remains a normal identifier everywhere else.
• A clause that never calls resume aborts the handled expression; the clause's value becomes the value of the whole handle expression.
• An unhandled effect reaching the top level is an error, except Print, which the interpreter handles by writing to stdout. Declaring eff Print(s) and handling it intercepts the output of print/println; performing Print again inside the clause forwards to the default handler.

call_cc

call_cc(k => ...) captures the whole continuation of the program. Invoking k(v) abandons whatever is running and continues from the call_cc with value v — good for early exit, and k stays valid (and multi-shot) even after the program has moved on.

fn product(xs) {
  call_cc(k => {
    let acc = 1;
    let i = 0;
    while (i < array_length(xs)) {
      if (xs[i] == 0) { k(0); }   // jump straight out
      acc = acc * xs[i];
      i = i + 1;
    }
    acc
  })
}

shift / reset

shift(k => ...) captures the continuation up to the nearest reset as a composable function: calling k(v) runs the captured fragment to its delimiter and returns the result (a handle is not a delimiter for shift).

reset(() => "a" + shift(k => k("b") + k("c")))  // => "ab" + "ac" = "abac"
reset(() => 1 + shift(k => k(10) + k(100)))     // => 11 + 101 = 112

Implementation

The evaluator (src/eval.rs) is a tree-walking interpreter whose control state lives in diapause coroutines. Every evaluation function is annotated with

#[diapause::coroutine(yield = Pause, resume = Resume)]

and delegates to sub-evaluations with yield_all!, so a suspension request raised anywhere deep in the tree walk travels outwards through the whole chain of evaluator frames. Pause (src/pause.rs) is the yield type, and Resume the type of the replies that come back:

• Perform(effect) — looks for the nearest handle frame with a matching clause; the value that frame resumes with becomes the value of perform.
• Shift(callback) — looks for the nearest reset frame.
• CaptureCont / InvokeCont(state, value) — call_cc machinery, answered only by the top-level driver.

The consumers of these requests are drivers that pump a coroutine and decide what each yield means: the top-level driver (eval_with_output), a drive_handle frame per handle expression, and a drive_reset frame per reset call.

The point of using diapause specifically is that its coroutines are Clone (state machines holding their locals as data, not native stack frames). That turns the hard part of continuation semantics into cloning:

• capturing a continuation = cloning the suspended coroutine state (call_cc: the top-level driver clones itself);
• a multi-shot invocation = driving a fresh clone of the saved state, so the originally captured state is never consumed;
• deep handler semantics = bundling the suspended handle body with its handler and reinstalling both on each resume.

What the tree walk pays for that is host stack: one stack frame per level of yield_all! delegation, rebuilt on every resume. The evaluator therefore counts its own frames and aborts with a stack depth limit exceeded error at MAX_EVAL_DEPTH (src/eval.rs) — deep enough for ordinary recursion, and far enough from the host limit that no host ever reaches it. That matters most in the browser: exhausting the stack in wasm is a trap, which unwinds nothing and leaves the wasm instance permanently damaged, so "let it overflow and report the error" is not an option there.

Suspended coroutine states are ordinary values on the garbage-collected heap (the gc crate), so continuations can be stored in globals, returned from handlers, and outlive the handle expression that created them — including across REPL inputs.

Crates in the workspace:

• conteff — the language: lexer, parser, evaluator, REPL binary.
• conteff-derive — a GcTrace derive that avoids gc_derive's Drop impl (which would prevent destructuring values by move in the evaluator).
• conteff-playground — the browser playground: the interpreter compiled to wasm plus a static REPL front end (conteff-playground/www).

Building and running

cargo run            # the REPL
cargo test           # the test suite (also the de facto language spec)

# The browser playground (requires wasm-pack):
cd conteff-playground
./build.sh
python3 -m http.server --directory dist