path: root/lambda-calcul/haskell/plan.md

# Interpreter Extension Plan

This document describes a series of extensions to the minilang interpreter, ordered by
increasing difficulty. Each extension is intended to drive new challenges in the contest:
rather than testing knowledge of Church-encoding tricks, these challenges require
participants to actually *change* the parser, evaluator, or type system.

The codebase currently consists of:

- **`Minilang.Lambda.Parser`** — Megaparsec parser producing an `AST` (`Sym`, `Lit`, `Abs`, `App`,
  `Def`), with `desugar`/`resugar`/`pretty` for round-tripping to `Term`.
- **`Minilang.Lambda.Eval`** — Normalisation-by-Evaluation (NbE) evaluator over `Term`
  (`Var`, `Lam`, `App`, `Num`), producing `Value` (`Clos`, `VNeut`, `VNum`).
- **`Minilang.Lambda.DeBruijn`** — A separate CBV head-reduction evaluator used by
  `evalInEnv` at the top level, operating on De Bruijn-indexed terms.
- **`Minilang.Lambda.Infer` / `Unify`** — A complete Hindley-Milner type inferencer
  (Algorithm W, constraint-based), wired into the REPL but not yet exposed to challenges.
- **`Minilang.REPL.*`** — A layered REPL stack (pure, IO, Haskeline, network) built around
  a `MonadREPL` typeclass.
- **`Minilang.App` / `API` / `Server`** — A Servant HTTP server that drives the challenge
  contest: register, get challenge, post answer.

---

## Extension 1 — Integer literals ✅ implemented

**Difficulty: 2 / 5**

### What it is

Add native integer values to the language. An integer literal like `42` or `-7` is a
self-evaluating value — it needs no reduction. This is the smallest possible extension to
`Term` and the foundation for all arithmetic extensions that follow.

### What was changed

**`Minilang.Lambda.Eval`**
- Added `Num Int` to `Term` and `VNum Int` to `Value`.
- Added `NNum Int` to `Neutral` so that a number in function position produces a stuck
  neutral application rather than a pattern-match failure.
- `eval`: `Num n → VNum n`.
- `apply`: `VNum n` in function position wraps in `VNeut (NApp (NNum n) a)`.
- `readBack`: `VNum n → Num n` and `VNeut (NNum n) → Num n`.

**`Minilang.Lambda.DeBruijn`**
- Added `FNum Int` to `DeBruijn`, propagated through `fromDeBruijn`, `toDeBruijn`,
  `substitute` (numbers are closed values — `substitute` is a no-op), `eval`/`eval'`
  (numbers are already values), and `pretty` (rendered via `showNum`).
- `showNum` renders negative integers with `-` immediately preceding the digits and no
  intervening space, matching the parser's requirement.

**`Minilang.Lambda.Parser`**
- Added `Lit Int` to `AST`.
- Added a `lit` parser rule: optional `char '-'` with **no intervening whitespace** before
  `some digitChar`, wrapped in `lexeme`. Tried before `sym` in the `ast` alternation so
  that `-7` is consumed as a number rather than as an identifier starting with `-`.
- `desugar`: `Lit n → Num n`. `resugar`: `Num n → Lit n`.
- `pretty`/`prettyInt`: negative integers printed as `-N` (no space), positives as `N`.
- `Arbitrary AST` updated: `genAst` now includes `Lit <$> arbitrary`; `shrink` has a
  `Lit _ → []` base case; `Identifier` generator gained a `suchThat` guard excluding
  strings whose prefix would be consumed as an integer literal by the parser.

**Tests**
- `EvalSpec`: 8 new unit tests covering `normalise` and `eval` on `Num` values, identity
  through a lambda, constant ignoring an integer, and a number in function position.
- `ParserSpec`: 2 new property tests replacing all unit tests:
  - *valid*: `∀ n :: Int. parse (pretty (Lit n)) == Right (Lit n)`
  - *invalid*: `∀ n > 0. parse ("- " <> show n) ≠ Right (Lit (-n))`

### Example challenges

| Expression | Result |
|---|---|
| `42` | `42` |
| `((lam (x) x) 99)` | `99` |
| `((lam (n) n) -3)` | `-3` |

---

## Extension 2 — Built-in arithmetic operators

**Difficulty: 2 / 5**

### What it is

Depends on Extension 1. Add `+`, `-`, `*`, `/`, `mod`, `=`, `<` as first-class built-in
functions. The key interpreter challenge beyond the trivial "add a case" is *partial
application*: `(+ 1)` must be a valid value — a closure waiting for its second argument —
rather than an error.

### What changes

**`Minilang.Lambda.Eval`**
- Add `Builtin Text Int [Value]` to `Value` (name, remaining arity, accumulated args).
- `eval`: `Var x` where `x` is a known builtin name returns `Builtin x arity []`.
- `apply`: when `f` is `Builtin name 1 args`, dispatch on `name` and reduce; when arity > 1,
  return `Builtin name (arity-1) (args ++ [a])`.
- `readBack`: a fully-saturated builtin that wasn't reduced (e.g. `(+ x y)` with free vars)
  reads back as a neutral application.

**`Minilang.Lambda.Parser`**
- Builtin names (`+`, `-`, `*`, `/`, `mod`, `=`, `<`) are already valid identifiers under
  the current `extraIdentifierChars` definition, so no parser change is needed beyond
  registering them as known names.

### Example challenges

| Expression | Result |
|---|---|
| `(+ 3 4)` | `7` |
| `(* 2 (+ 1 4))` | `10` |
| `(- 10 3)` | `7` |
| `(= 3 3)` | `#t` (requires Extension 6) or `True` Church-bool |
| `(+ 1)` | a partial application — prints as a neutral `(+ 1)` |

---

## Extension 3 — String literals

**Difficulty: 2 / 5**

### What it is

Add double-quoted string values. Like integers, strings are self-evaluating. The extra
challenge compared to integers is the round-trip: `pretty` must re-emit surrounding
double-quotes and escape internal special characters, so the parser and printer must agree
on the escape convention.

### What changes

**`Minilang.Lambda.Eval`**
- Add `Str Text` to `Term` and `VStr Text` to `Value`.

**`Minilang.Lambda.DeBruijn`**
- Add `FStr Text`, propagated everywhere.

**`Minilang.Lambda.Parser`**
- Add `StrLit Text` to `AST`.
- Parser rule: `char '"' *> manyTill L.charLiteral (char '"')`, tried before `sym`.
- `desugar`: `StrLit s → Str s`. `resugar`: `Str s → StrLit s`.
- `pretty`: `StrLit s → "\"" <> escapeString s <> "\""`.

**String builtins** (same pattern as Extension 2): `concat`, `length`, `slice`, `str=`.

### Example challenges

| Expression | Result |
|---|---|
| `"hello"` | `"hello"` |
| `(concat "foo" "bar")` | `"foobar"` |
| `(length "abc")` | `3` |
| `(slice 1 3 "abcde")` | `"bc"` |

---

## Extension 4 — Floating-point number literals

**Difficulty: 2 / 5**

### What it is

Add native double-precision floating-point values to the language. A float literal like
`3.14` or `-0.5` is self-evaluating. This is similar to the integer literal extension but
requires careful handling in the parser to distinguish floats from integers (floats always
contain a `.`), and in `pretty` to ensure the printed form is always re-parseable as a
float (e.g. `1.0` rather than `1`).

### What changes

**`Minilang.Lambda.Eval`**
- Add `Flt Double` to `Term` and `VFlt Double` to `Value`.
- Add `NFlt Double` to `Neutral` so a float in function position produces a stuck neutral
  application rather than a pattern-match failure.
- `eval`: `Flt d → VFlt d`.
- `apply`: `VFlt d` in function position wraps in `VNeut (NApp (NFlt d) a)`.
- `readBack`: `VFlt d → Flt d` and `VNeut (NFlt d) → Flt d`.

**`Minilang.Lambda.DeBruijn`**
- Add `FFlt Double`, propagated through `fromDeBruijn`, `toDeBruijn`, `substitute`
  (floats are closed values), `eval`/`eval'`, and `pretty` (via `showFlt`).
- `showFlt` renders the value with enough decimal places that the printed form round-trips
  through the parser (always includes a `.`).

**`Minilang.Lambda.Parser`**
- Add `FltLit Double` to `AST`.
- Parser rule: try the float rule (digits, `.`, digits, optional exponent) *before* the
  integer rule so that `3.14` is not partially consumed as the integer `3`.
- `desugar`: `FltLit d → Flt d`. `resugar`: `Flt d → FltLit d`.
- `pretty`/`prettyFlt`: always emit a decimal point; negative floats printed as `-D.D`
  (no space), matching the parser's requirement.
- `Arbitrary AST` updated: `genAst` includes `FltLit <$> arbitrary`; `shrink` has a
  `FltLit _ → []` base case; the `Identifier` guard is extended to exclude strings that
  would be consumed as float literals.

**Tests**
- `EvalSpec`: unit tests covering `normalise` and `eval` on `Flt` values, identity through
  a lambda, constant ignoring a float, and a float in function position.
- `ParserSpec`: property tests mirroring the integer ones:
  - *valid*: `∀ d :: Double. parse (pretty (FltLit d)) == Right (FltLit d)`
  - *invalid*: `∀ d > 0. parse ("- " <> show d) ≠ Right (FltLit (-d))`

### Example challenges

| Expression | Result |
|---|---|
| `3.14` | `3.14` |
| `((lam (x) x) 2.718)` | `2.718` |
| `((lam (n) n) -0.5)` | `-0.5` |

---

## Extension 5 — Typed mode challenges

**Difficulty: 3 / 5**

### What it is

The Hindley-Milner type inferencer in `Minilang.Lambda.Infer` and `Minilang.Lambda.Unify`
is fully implemented and reachable via `:lang Typed` in the interactive REPL, but is
completely invisible to the challenge system. `evaluateOutputs` in `App.hs` pattern-matches
on `[Bye, Evaluated ast _ _]` and discards the `Type` field entirely.

### What changes

- Switch `initialREPL` from `Untyped` to `Typed` for these challenges (one field change).
- Add a parallel `evaluateType` path in `App.hs` that pattern-matches on the `Type` in the
  `Evaluated` constructor and compares it against the submitted string using `Unify.pretty`.
- Optionally introduce a second contest endpoint or a `kind: "type"` field in `Challenge`
  to distinguish "what does this reduce to?" from "what type does this have?".

### Example challenges

| Expression | Expected type |
|---|---|
| `(lam (x) x)` | `a -> a` |
| `(lam (x y) x)` | `a -> b -> a` |
| `(lam (f x) (f (f x)))` | `(a -> a) -> a -> a` |
| `(lam (x) (x x))` | circularity error |
| `(lam (f g x) (f (g x)))` | `(b -> c) -> (a -> b) -> a -> c` |

---

## Extension 6 — Boolean literals and `if`

**Difficulty: 2 / 5**

### What it is

Add `#t` / `#f` literals and an `if` special form. This is the first form that *cannot* be
desugared into a plain lambda application under call-by-value without Church-encoding,
because `if` must be *non-strict* in its branches to avoid evaluating the untaken one.
A divergent or error-raising expression in the dead branch must not be evaluated.

### What changes

**`Minilang.Lambda.Eval`**
- Add `Bool Bool` to `Term` and `VBool Bool` to `Value`.
- Add `If Term Term Term` to `Term`.
- `eval`: `If cond t e → if evaluate cond then eval env t else eval env e`. Note: only `cond`
  is evaluated eagerly; the branches are lazy.

**`Minilang.Lambda.Parser`**
- Add `BoolLit Bool` and `IfExpr AST AST AST` to `AST`.
- Parser rule for `#t` / `#f`.
- Parser rule for `(if cond then else)` as a special form (not desugared to lambda).
- `desugar`: `IfExpr c t e → If (desugar c) (desugar t) (desugar e)`.

**`Minilang.Lambda.DeBruijn`**
- Add `FBool Bool` and `DIf` cases, propagated through all functions.

### Example challenges

| Expression | Result |
|---|---|
| `#t` | `#t` |
| `(if #t a b)` | `a` |
| `(if #f a b)` | `b` |
| `(if (= 1 1) "yes" "no")` | `"yes"` (requires Extensions 2, 3) |
| `(if #f (omega omega) 42)` | `42` — the divergent branch is not evaluated |

---

## Extension 7 — Array literals

**Difficulty: 3 / 5**

### What it is

Add `[e1 e2 … en]` syntax for constructing array values. The square-bracket delimiters
are currently unused by the parser. Arrays are *eager*: all elements are evaluated at
construction time, consistent with CBV. Structural operations (`head`, `tail`, `cons`,
`nth`, `length`, `map`) follow the same partial-application builtin pattern as Extension 2.

### What changes

**`Minilang.Lambda.Eval`**
- Add `Arr [Term]` to `Term` and `VArr [Value]` to `Value`.
- `eval`: `Arr es → VArr (map (eval env) es)` — evaluate every element eagerly.
- `readBack`: `VArr vs → Arr (map readBack vs)`.

**`Minilang.Lambda.DeBruijn`**
- Add `FArr [DeBruijn ann]`, propagated through `toDeBruijn`, `fromDeBruijn`,
  `substitute`, `eval`/`eval'`, `pretty`.

**`Minilang.Lambda.Parser`**
- Add `ArrLit [AST]` to `AST`.
- Parser rule: `between (symbol "[") (symbol "]") (many ast)`.
- `pretty`: `ArrLit es → "[" <> Text.unwords (map pretty es) <> "]"`.

**Array builtins**: `head`, `tail`, `cons`, `nth`, `length`, `map` (requires lambda values
as arguments — the interaction between array builtins and lambda values is the interesting
new test here).

### Example challenges

| Expression | Result |
|---|---|
| `[1 2 3]` | `[1 2 3]` |
| `(head [10 20 30])` | `10` |
| `(tail [10 20 30])` | `[20 30]` |
| `(cons 0 [1 2])` | `[0 1 2]` |
| `(nth 1 [a b c])` | `b` |
| `(map (lam (x) (+ x 1)) [1 2 3])` | `[2 3 4]` (requires Extension 2) |

---

## Extension 8 — `quote` and `eval`

**Difficulty: 3 / 5**

### What it is

`(quote e)` (shorthand `'e`) returns the *unevaluated syntax tree* of `e` as a first-class
runtime value — a `VQuote Term`. Evaluation is non-recursive for the quoted sub-expression.
The dual `(eval e)` takes a `VQuote` and re-evaluates it in the current environment,
making the interpreter explicitly two-level. This is the first extension where the
distinction between *object language* and *meta-language* becomes observable in a challenge.

The hard part is `(eval e)`: the `eval` builtin must receive the current *environment* as a
hidden argument. This means the builtin dispatch mechanism must be extended to thread the
environment through, which is a non-trivial change to the builtin application architecture
introduced in Extension 2.

### What changes

**`Minilang.Lambda.Eval`**
- Add `Quote Term` to `Term` and `VQuote Term` to `Value`.
- `eval`: `Quote t → VQuote t` (does not recurse into `t`).
- `apply`: when `f` is `Builtin "eval" 1 []` and argument is `VQuote t`, call `eval env t`.
  This requires `apply` to receive `env` — currently it does not. All call sites of `apply`
  must be updated.
- `readBack`: `VQuote t → Quote t` (prints as `'t`).

**`Minilang.Lambda.Parser`**
- Add `QuoteExpr AST` to `AST`.
- Parser rule for `(quote e)` as a special form.
- Reader macro: `char '\'' *> ast` producing `QuoteExpr`.
- `pretty`: `QuoteExpr e → "(quote " <> pretty e <> ")"` or `"'" <> pretty e`.

### Example challenges

| Expression | Result |
|---|---|
| `(quote x)` | `x` (the symbol, not evaluated) |
| `(quote (lam (x) x))` | `(lam (x) x)` (syntax as data) |
| `(eval (quote (lam (x) x)))` | `(lam (x) x)` (re-evaluated) |
| `(eval (quote ((lam (x) x) y)))` | `y` |
| `(let ((e (quote (+ 1 2)))) (eval e))` | `3` (requires Extension 2) |

---

## Extension 9 — `letrec` / recursive definitions

**Difficulty: 3 / 5**

### What it is

The current `let` desugars to an immediate lambda application, which means bindings cannot
refer to themselves or each other. `letrec` allows mutually recursive definitions. Under
CBV this requires either mutable thunks (see Extension 10) or lazy tying-of-the-knot in the
Haskell host. The standard interpreter-level approach is to build a *circular environment*:
the closure created for each binding has the entire `letrec` group already in its
environment, which in a lazy host language like Haskell can be expressed directly using
`let rec` in the metalanguage.

### What changes

**`Minilang.Lambda.Eval`**
- Add `Rec Text Term` to `Term` (or handle recursion entirely at the `eval` level without a
  new `Term` constructor by building circular `EnvValue` entries using Haskell's laziness).
- `eval`: `Rec f body → let v = eval ((f, v) : env) body in v` (the circular binding).

**`Minilang.Lambda.Parser`**
- Add `Letrec [(Text, AST)] AST` to `AST`.
- Parser rule for `(letrec ((x e) …) body)` mirroring `letExpr` but desugaring differently.
- `desugar`: translate each binding to a `Rec` node.

**`Minilang.Lambda.DeBruijn`**
- Add a `Rec` case propagated through all functions.

### Example challenges

| Expression | Result |
|---|---|
| `(letrec ((f (lam (x) (if (= x 0) 1 (* x (f (- x 1))))))) (f 5))` | `120` (requires Extensions 2, 6) |
| `(letrec ((even? (lam (n) (if (= n 0) #t (odd? (- n 1))))) (odd? (lam (n) (if (= n 0) #f (even? (- n 1)))))) (even? 4))` | `#t` |

---

## Extension 10 — Mutable references

**Difficulty: 3 / 5**

### What it is

Add `ref`, `deref`, and `set!` as built-in operations over a mutable heap. This is the
first extension that introduces *effects* into the otherwise pure evaluator: `eval` can no
longer be a pure function. Its type must change to operate in a state monad (or return a
`(Value, Store)` pair), where `Store` maps fresh location identifiers to current values.
Every call site of `eval` and `apply` must be updated. The interaction between the store and
closures — closures close over variable *bindings*, not store *locations* — makes this a
genuinely instructive design challenge.

### What changes

**`Minilang.Lambda.Eval`**
- Add `VRef Int` to `Value` (a reference is a runtime address).
- Add a `Store` type: `IntMap Value`.
- Change `eval :: EnvValue -> Term -> Value` to
  `eval :: EnvValue -> Store -> Term -> (Value, Store)` (or use `State Store`).
- `apply` receives and threads `Store`.
- Three new builtins: `ref` (allocate), `deref` (read), `set!` (write and return unit).

**All call sites** of `eval` and `apply` (in `DeBruijn`, `Lambda`, `REPL.Run`) must be
updated to thread the store.

### Example challenges

| Expression | Result |
|---|---|
| `(let ((r (ref 0))) (deref r))` | `0` |
| `(let ((r (ref 0))) (set! r 42) (deref r))` | `42` |
| `(let ((r (ref 0))) (set! r (+ (deref r) 1)) (deref r))` | `1` (requires Extension 2) |
| Show that argument evaluation order is observable when both arguments mutate shared state | order-dependent result |

---

## Extension 11 — Type annotations

**Difficulty: 3 / 5**

### What it is

Extends the parser with `(lam ((x : A) …) body)` for annotated binders and `(the T expr)`
for standalone type ascriptions, where `T` is a type expression using `->` and type
variables. The type inferencer already exists; the new challenge is *checking* rather than
*inferring* — when a type annotation is present the inferencer should verify the expression
has exactly that type rather than discovering a fresh one. This is implemented by unifying
the inferred type with the declared type and reporting mismatches.

### What changes

**`Minilang.Lambda.Parser`**
- Add a type expression parser: `TyVar Text | TyArr Type Type`, parsed from the same text
  syntax as `Unify.Type` already uses (`a`, `b`, `(a -> b)`, etc.).
- Extend the `lambda` parser rule to accept `(x : T)` annotated binders.
- Add a `the` special form: `(the T expr)`.
- Add `Ann Type AST` and `AnnBinder Text Type` constructors to `AST`.

**`Minilang.Lambda.Infer`**
- `annotate`: when an `Ann` node is encountered, infer the inner expression and then unify
  its type with the declared type, returning a `TypeError` if they conflict.
- Annotated binders assign the declared type to the bound variable instead of a fresh type
  variable, then check the body against the remaining declared type.

**`Minilang.Lambda.Eval`** — no change (annotations are erased by `desugar`).

### Example challenges

| Expression | Result / type |
|---|---|
| `(the (a -> a) (lam (x) x))` | `(lam (x) x)` |
| `(the (a -> b -> a) (lam (x y) x))` | `(lam (x y) x)` |
| `(the (a -> a -> a) (lam (x y) x))` | unification error: `a` vs `b` |
| `(lam ((x : a) (y : b)) x)` | type `a -> b -> a` |
| `(the (a -> a) (lam (x) (x x)))` | circularity error |

---

## Extension 12 — Algebraic data types

**Difficulty: 4 / 5**

### What it is

Add `(data TypeName (CtorName field …) …)` declarations and `(match expr (pattern body) …)`
expressions. Constructors become first-class values that can be partially applied.
Pattern matching performs structural dispatch and binds sub-components. This is the most
significant structural change to the evaluator so far: it introduces a constructor registry,
a new value form, a pattern-matching engine with backtracking, and a significant expansion
of the type system (sum types, product types, type constructors, arity checking).

### What changes

**`Minilang.Lambda.Eval`**
- Add `Con Text [Term]` to `Term` (constructor application) and `VCon Text [Value]` to
  `Value`.
- `eval`: `Con name args → VCon name (map (eval env) args)` for saturated constructors;
  unsaturated constructors reduce to `Builtin`-style partial values.
- Add `Match Term [(Pattern, Term)]` to `Term`.
- `eval`: `Match scrutinee alts → matchAlts (eval env scrutinee) alts env`, where
  `matchAlts` tries each alternative in order, performing structural unification against
  `VCon` values, binding matched sub-components, and evaluating the matching branch.

**`Minilang.Lambda.Parser`**
- Add `DataDecl` and `MatchExpr` to `AST`.
- `data` declarations are processed by a new `runData` step in `loadProgram` that registers
  constructors and their arities in the environment.
- Pattern syntax: constructor name (possibly with sub-pattern variables) or wildcard `_`.

**`Minilang.Lambda.Infer`**
- Add type constructors, sum types, and product types to `Unify.Type`.
- Constructor types are stored in the `Context` alongside term types.
- `infer`: handle `Con` and `Match` nodes; check exhaustiveness (warnings or errors).

### Example challenges

| Expression | Result |
|---|---|
| `(data Bool (True) (False)) (match True (True "yes") (False "no"))` | `"yes"` |
| `(data List (Nil) (Cons head tail)) (match (Cons 1 Nil) (Nil 0) ((Cons h t) h))` | `1` |
| `(data Maybe (Nothing) (Just x)) (match (Just 42) (Nothing 0) ((Just v) v))` | `42` |
| Non-exhaustive match | runtime or type error |

---

## Extension 13 — `call/cc`

**Difficulty: 4 / 5**

### What it is

`(call/cc (lam (k) body))` captures the *current continuation* as a first-class value and
passes it to the given function. Invoking `k` with a value immediately returns that value
from the enclosing `call/cc`, discarding the rest of the computation. This is the most
fundamental control-flow extension: it can encode exceptions, early exit, cooperative
multitasking, and backtracking. Implementing it correctly requires transforming `eval`
into *continuation-passing style* — either explicitly by changing the return type to
`(Value -> r) -> r`, or by using a `Cont` monad. Either way every call site changes.

### What changes

**`Minilang.Lambda.Eval`**
- Change `eval` signature from `EnvValue -> Term -> Value` to
  `EnvValue -> Term -> (Value -> r) -> r` (or `EnvValue -> Term -> Cont r Value`).
- `apply` receives the current continuation as an extra argument.
- Add `VCont (Value -> r)` to `Value` (a captured continuation).
- `apply` on a `VCont k v`: simply call `k v`, discarding everything after the current
  continuation — this is the "abort to the capture point" behaviour.
- `eval` for `App f a` in CPS: evaluate `f`, evaluate `a`, then `apply f' a' k`.
- Register `call/cc` as a known name; `eval` of `Var "call/cc"` returns a `VBuiltin` that,
  when applied to a function `f`, calls `f` with `VCont k` where `k` is the current
  continuation.

**All call sites** of `eval` (in `DeBruijn`, `Lambda`, `REPL.Run`, `App`) must be updated
to supply an initial continuation (typically `id`).

**`Minilang.Lambda.Parser`** — no change; `call/cc` is a valid identifier already.

### Example challenges

| Expression | Result |
|---|---|
| `(call/cc (lam (k) 42))` | `42` (k never used) |
| `(call/cc (lam (k) (k 42) 99))` | `42` (early return, 99 is never reached) |
| `(+ 1 (call/cc (lam (k) (* 2 (k 3)))))` | `4` |
| Implement `throw`/`catch` using `call/cc` | |
| Implement list collection with early termination | |

---

## Extension 14 — Delimited continuations (`reset` / `shift`)

**Difficulty: 5 / 5**

### What it is

A refinement of `call/cc` (#12) where continuations are *delimited*: `(shift k body)`
captures only the continuation up to the nearest enclosing `(reset expr)` boundary, rather
than the entire rest of the program. The captured continuation `k` is a *composable
function*, not an escape: calling it does not abort but resumes. This is the basis for
algebraic effects, generators, coroutines, and non-determinism, all expressible without any
further language changes.

Implementing this correctly requires moving from a flat CPS transform (one continuation
argument) to a *two-level* architecture: an *outer* continuation representing the program
after the current `reset`, and an *inner* continuation representing the program up to the
`reset`. Danvy & Filinski's original presentation encodes this with a two-argument CPS
transform; alternatively, an explicit *continuation stack with reset marks* can be
maintained as a mutable data structure threaded through `eval`.

### What changes

**`Minilang.Lambda.Eval`**
- Prerequisite: Extension 13 (CPS'd evaluator).
- Change `eval` to carry *two* continuations: the current meta-continuation and the
  delimited one, or use an explicit stack of `Frame | Reset` markers.
- `reset expr`: evaluate `expr` with a fresh inner continuation and the current outer
  continuation; when `expr` completes normally, pass its value to the outer continuation.
- `shift k body`: capture the current inner continuation as a composable function `k`,
  install the outer continuation as the new current continuation, and evaluate `body`.
- Add `VShift` and `VReset` administrative value forms (used during evaluation, not
  user-visible).

**`Minilang.Lambda.Parser`** — add `reset` and `shift` as special forms.

### Example challenges

| Expression | Result |
|---|---|
| `(reset (+ 1 (shift k 10)))` | `10` (k discarded) |
| `(reset (+ 1 (shift k (k 10))))` | `11` (k applied once: adds 1) |
| `(reset (+ 1 (shift k (k (k 10)))))` | `12` (k applied twice) |
| Implement a generator using `shift`/`reset` | sequence of yielded values |
| Implement `amb` for non-deterministic choice | list of all results |
| Implement a cooperative coroutine scheduler | interleaved output |