# 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.

```nix
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.

```nix
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`.

```nix
interp.exprs.benchmarks.fib10
interp.exprs.benchmarks.lets500
interp.exprs.benchmarks.sum1000
```