Expression Interpreter

This example implements a strict expression language with arithmetic, booleans, let bindings, lambdas, application, and recursive bindings. The evaluator emits effects for environment lookup, local scope, and failure; handlers decide how those requests run.

The same module also exports scalable expression generators used by the benchmark suite.

Expression syntax

Expressions are plain tagged Nix attrsets. Constructors keep the evaluator independent from any parser or source format.

num = n: { _tag = "Expr"; _variant = "Num"; inherit n; };
add = l: r: { _tag = "Expr"; _variant = "Add"; inherit l r; };
lam = param: body: { _tag = "Expr"; _variant = "Lam"; inherit param body; };
app = fn: arg: { _tag = "Expr"; _variant = "App"; inherit fn arg; };

Handler boundary

Variable lookup, scoped execution, and failure are effects. Recursive bindings work by building a closure whose environment refers back to itself, while the handler owns the actual environment map.

lookup = name: send "lookup" name;
getEnv = send "getEnv" null;
fail = msg: send "fail" msg;

run = expr:
  let result = handle {
    handlers = mkHandler { };
    state = { env = { }; };
  } (eval expr);
  in if result ? error then throw "eval error: ${result.error}" else result.value;

Benchmark generators

exprs.nix generates large recursive and nested expressions. The benchmark suite imports these generators from examples/interp.

interp.exprs.benchmarks.fib10
interp.exprs.benchmarks.lets500
interp.exprs.benchmarks.sum1000