# elly

Elly is a small language layered on Muon (see `muon-spec.md`). Muon defines only
lexical and structural syntax; Elly assigns evaluation semantics to Muon
structures — chains, items, and tuples. Elly source is therefore valid Muon:
Muon is a superset of Mu source code, and Elly is one front-end over it.

This document specifies only a first, deliberately small subset of Elly:

- variable **references** and name binding
- function **application** and **abstraction** (`&`)
- **symbols** (`.foo`)
- integer **numbers** (`Int`, arbitrary precision) and their `__Int` builtins
- positional **lists** (`[…]`) and keyed **maps** (`{ … }`) — with `()` reserved
  for syntactic grouping / argument spread
- **pattern matching** and a single **raise** / error channel

For the broader vision (records, typing, uniqueness) see `elly-intro.md`.
Everything outside this subset is collected under [deferred](#deferred) at the end.

## syntax, muon notation

Elly evaluates Muon structure. Each construct in this subset is a
reinterpretation of a Muon production:

| Elly construct     | Muon production                |
| ------------------ | ------------------------------ |
| reference          | `<sym>` (identifier)           |
| symbol literal     | `<prefixed>` — `.` (see below) |
| integer literal    | `<sym>` (numeric)              |
| application        | `<chain>` (juxtaposition)      |
| abstraction / bind | `<prefixed>` — `&` (see below) |
| list value        | `<list>` — `[…]`               |
| grouping / spread  | `<tuple>` — `(…)`              |

Elly uses Muon's whitespace and separator rules unchanged, but — unlike Muon,
which gives neither any meaning — Elly distinguishes them semantically:

- **juxtaposition** (whitespace within a chain) is **application**: `(f x)` is
  one chain, the application of `f` to `x`.
- a **separator** `<sep>` (`,` or newline) delimits the **chains** of a
  parenthesized or bracketed `<seq>`: `(f, x)` are two chains and `[f, x]` two
  list elements.

The two brackets do different jobs, and this is the one place a reader must keep
the Muon layer in mind:

- `(…)` is **pure syntax** — grouping, argument **spread**, and the nullary
  marker (see [application](#application) and [abstraction](#abstraction)). It never denotes a value: `(f x)`
  is one chain (the application `f x`), and `f (a, b)` spreads to the curried call
  `f a b`.
- `[…]` is the only **list value** constructor (see [lists](#list-lists)): `[]`, `[.x]`
  (a genuine 1-list, distinct from `.x`), `[f, x]`.

A program in this subset is a single expression (one `<chain>`). Top-level
sequencing of multiple chains in a `<seq>` is deferred — it needs
binding/sequencing semantics not in this subset.

Comments (`<comm>`) may appear between items as in Muon; they are ignored by
evaluation.

**The `&` extension to muon**. Abstraction needs a marker that is itself part of
the notation, so Muon's `<item>` is extended with a *prefixed item*:

```ebnf
(* no whitespace *)
<prefixed> ::= "&" <item>
```

At the Muon layer this is purely structural and carries no meaning, exactly as
`:` or `-1` are just `<sym>`s. Elly gives `&<item>` the meaning "introduce a
binding". `&` attaches to the item immediately after it (no whitespace): `&x` is
one prefixed item. This addition is reflected in `muon-spec.md`'s `<item>`
production.


## values

The literal values in this subset are:

- symbols (see [symbols](#sym-symbols))
- integers (see [integers](#int-integers))
- strings (see [strings](#str-strings))
- lists (see [lists](#list-lists))
- maps (see [maps](#map-maps))
- functions

A list is written `[…]`; the empty list `[]` is **unit** — there is no
separate unit value. A map is written `{ … }`.

The wider numeric tower (`Num`: rationals, floats, complex), of which `Int` is
the first, integer-only slice, is deferred. Strings get a first, deliberately
small design — literals, map keys, comparison, and a codepoint round-trip — with
most string *functionality* still deferred (see [strings](#str-strings)).


### `Sym`, symbols

Elly symbols are `.`-prefixed literals that evaluate to themselves (unless the
context gives them another meaning, e.g. list projection). A symbol is a `.`
directly glued to a single name or number segment:

```elly
.foo        // a symbol `.foo`
.0          // a symbol `.0`
```

A symbol wraps exactly one segment. Because `.` is a Muon sigil that breaks
symbols (see `muon-spec.md`), `.foo.bar` is *not* one symbol but the chain
`.foo .bar` — two symbols juxtaposed, i.e. successive projections; the two spell
the same value. The bare dot `.` (nothing glued to its right) is a Muon `<punct>`,
not a symbol — Elly reserves the spaced dot for a future application /
composition combinator and rejects it as an atom for now.


Symbols are the subset's tags and enumerations.

```elly
// map a status tag to a code, falling through to a default
&s __eq s .ok (&_ 0) (&_ __eq s .warn (&_ 1) (&_ 2))

// a catch handler: rescue .div_by_zero, re-raise anything else
// (see error handling for __Err.catch / __Err.raise)
__Err.catch
  (&exc __eq exc .div_by_zero (&_ .undefined) (&other __Err.raise other))
  (&_ (__Int.divrem 1 0).0)                              // ⇒ .undefined
```


### `Int`, integers

Integers are **arbitrary precision**, signed, and **self-evaluating**. This
subset provides only `Int`; the wider numeric tower — rationals, floats, complex
— is deferred under a future `Num`, with `Int` as its integer-only subset.

#### literals

An integer literal is a Muon `<sym>` that is not a `<symbol>` (not `.`-prefixed)
and matches:

```ebnf
(* recognized before <name>. `_` separates digit groups and may not lead,
   trail, or double. *)
<int>       ::= <sign>? <magnitude>
<sign>      ::= "-" | "+"
<magnitude> ::= <dec> | <hex> | <bin>
<dec>       ::= <digit>  ("_"? <digit>)*                 (* base 10 *)
<hex>       ::= "0" ("x"|"X") <hexdig> ("_"? <hexdig>)*  (* base 16 *)
<bin>       ::= "0" ("b"|"B") <bit>    ("_"? <bit>)*     (* base 2  *)
```

```elly
0
-123
+7
1_000_000
0xCAFE       // == 51966
0b1010       // == 10
```

The base prefix, sign and separators are notational only: `0xF`, `15`, `0b1111`
and `+15` all denote the same value. A `<sym>` that is neither a `<symbol>`, a
valid `<int>`, nor a valid `<name>` (e.g. `1a`, `0xZZ`, `--1`) is an error;
operator-like syms remain deferred. Note that `.0` is the **symbol** `.0` (a
`.`-prefixed `0`, a projection index), never the integer `0`.

#### semantics

- An integer is self-evaluating: it evaluates to itself.
- **Equality** is by mathematical value (`+0`, `-0`, `0` are all equal).
- **String representation** is canonical signed decimal, without separators or a
  redundant sign / leading zeros: `0`, `15`, `-123`.

#### the `__Int` module

Arithmetic and elimination are **builtins**, items of the `__Int`
[builtin module](#builtin-modules-and-their-aliases) — so `__Int.add`, or `Int.add`
through the alias. All are **curried** (`f x y` = `(f x) y`) and **strict** in
their integer arguments; supplying a non-integer where an integer is required
**raises** `.not_an_int` (see [errors](#error-handling)).

| builtin | shape | meaning |
| --- | --- | --- |
| `__Int.add x y` | `Int → Int → Int` | `x + y` |
| `__Int.sub x y` | `Int → Int → Int` | `x − y` (in this order) |
| `__Int.mul x y` | `Int → Int → Int` | `x × y` |
| `__Int.pow x y` | `Int → Int → Int` | `x` to the power `y` (`y ≥ 0`) |
| `__Int.divrem x y` | `Int → Int → [Int, Int]` | Euclidean quotient and remainder `[q, r]` |
| `__Int.for from to state onEach` | `Int → Int → s → (Int → s → s) → s` | ascending fold over `from … to−1` |

- `__Int.sub x y` subtracts in written order: `__Int.sub 2 5` is `−3`.
- `__Int.pow x y` raises `x` to the power `y`, with `0^0 = 1`. The exponent must
  be non-negative: `y < 0` would give a non-integer and **raises**
  `.negative_exponent`.
- `__Int.divrem x y` returns the Euclidean pair as a list `[q, r]` with
  `q = x ÷ y` and `r = x − y·q` normalized to `0 ≤ r < |y|`, so `x = y·q + r`
  always holds; project it with `.0`/`.1`. A zero divisor (`y = 0`) **raises**
  `.div_by_zero`.
- Integer **comparison** is done with patterns, not a builtin: equality is the
  `= <ref>` pattern (or the general `__eq`, see [equality](#__eq-value-equality)) and strict order is
  the `< <ref>` / `> <ref>` ordering patterns (see [patterns](#patterns-and-matching)), which compose
  with `=` into `<=` / `>=`. A `__match` over those clauses is the subset's
  conditional.
- `__Int.for from to state onEach` computes
  `onEach (to−1) (… (onEach (from+1) (onEach from state)) …)` — `onEach` takes the
  **index first**, accumulator second, returning the next accumulator. It iterates
  **ascending only** over the half-open range `[from, to)`; `from ≥ to` runs zero
  iterations and yields `state` (so an inverted range is a harmless no-op). It is
  the bounded iteration primitive, standing in for the fixpoint combinator this
  subset still defers.

```elly
// factorial: iterate i from 1 to n inclusive, acc ← acc × i
&n __Int.for 1 (__Int.add n 1) 1 (&i &acc __Int.mul acc i)

// sum 0 … n−1
&n __Int.for 0 n 0 (&i &acc __Int.add acc i)

// absolute value, via a sign test (0 named explicitly; no __Int.neg)
&n __match [&(< 0) __Int.sub 0 n, &_ n] n
```

A comparison returning a symbol (`.lt`/`.eq`/`.gt`) is deliberately **not**
provided: ordering is expressed directly with the `< <ref>` / `> <ref>`
patterns (and `=` for equality), which compose into the rest (`<=`, `>=`, …)
without a symbol to eliminate.


### `Str`, strings

A string is an immutable, ordered sequence of Unicode scalar values — the
subset's textual data, a runtime kind `Str` alongside `Int Sym List Map Fun`.
This is a first, deliberately small string design: literals, map keys,
comparison, and a codepoint round-trip, with most string *functionality* still
deferred (see [deferred](#deferred)).

#### literals

A string literal is a Muon `<str>` — text between double quotes. Muon validates
only the escape *syntax* and carries the text raw; Elly is the higher layer that
reads meaning into it, **decoding** a literal into the scalar values it denotes,
once, at parse time:

- the escapes `\" \\ \/ \n \t \r \b \f` stand for their usual characters;
- `\uXXXX` names one UTF-16 code unit, and a *surrogate pair* — a high unit
  (`\uD800`–`\uDBFF`) followed by a low unit (`\uDC00`–`\uDFFF`) — combines into
  the single scalar it encodes (`\uD834\uDD1E` denotes U+1D11E);
- an *unpaired surrogate* — a high unit not completed by a low one, or a lone low
  unit — names no scalar and is a **parse error** (not a runtime raise); it is the
  only way decoding fails.

```elly
"hello"
""                       // the empty string
"line\nbreak"            // contains a newline
"\u0041"                 // == "A"
"\uD83D\uDE00"           // one supplementary-plane scalar (above U+FFFF), U+1F600
```

The value a literal denotes keeps no trace of how it was spelled — `"A"` and
`"\u0041"` are the same string. A string is self-evaluating: it evaluates to
itself.

#### semantics

- **Equality** is structural, by scalar sequence: two strings are equal exactly
  when their scalars match. A string is not equal to the like-spelled symbol or
  name — `"foo"`, `.foo`, and `foo` are three different values.
- **Ordering** is lexicographic by scalar value. `Str` joins `Int` as a
  comparable kind for the `< <ref>` / `> <ref>` ordering patterns (see
  [patterns](#patterns-and-matching)).
- Neither equality nor ordering applies any Unicode normalization or collation:
  both compare the plain decoded scalar sequence (surrogates already resolved at
  parse), scalar for scalar. Two canonically-equivalent spellings that differ in
  scalars are therefore distinct strings and may sort apart.
- A string literal in **pattern** position is an equality pattern, the textual
  twin of `.sym` / `<num>` (`"foo"` ≡ `= "foo"`); a string may also be a **map
  key**, and a lookup key in a map pattern, keyed by that same equality (see
  [maps](#map-maps)).
- **String representation** re-quotes and re-escapes the text, so it reads apart
  from a symbol or a name.
- A string's internal storage is **unobservable**: the only windows onto its
  contents are the codepoint pack/unpack pair below. This leaves the
  representation free to change later.

#### the `__Str` and `__Sym` modules

**Curried**, and **strict** in their one typed argument —
each **raises** its own tag on the wrong kind (`.not_a_str`, `.not_an_int`, or
`.not_a_sym`). These primitives view a string as its sequence of codepoints — the
Unicode scalar values, so `.a` (U+0061) is `97` — and string manipulation for now
is a simple but inefficient round-trip through codepoint lists.

| builtin | shape | meaning |
| --- | --- | --- |
| `__Int.str n` | `Int → Str` | signed decimal of an integer (`15` → `"15"`, `-123` → `"-123"`). A non-int **raises** `.not_an_int`. |
| `__Sym.str s` | `Sym → Str` | a symbol's name without the dot (`.foo` → `"foo"`), the inverse of `__Sym.from`. A non-symbol **raises** `.not_a_sym`. |
| `__Str.pack cps` | `List → Str` | build a string from a list of codepoints; a non-`Int` element **raises** `.not_an_int`, and one outside `0 … 0x10FFFF` or in the surrogate range **raises** `.bad_codepoint`. |
| `__Str.unpack s` | `Str → List` | the codepoints of a string, in order (`"abc"` → `[97, 98, 99]`); the inverse of `__Str.pack`. |
| `__Sym.from s` | `Str → Sym` | the symbol named by a string (`"foo"` → `.foo`), the inverse of `__Sym.str`. The text must be a single Muon `<sym>` segment — the only form that re-lexes from `.<text>` — so a string with whitespace, an interior `.`, or any non-`<symchar>`, and the empty string, **raise** `.bad_symbol`. |

```elly
__Int.str 15                               // ⇒ "15"
__Sym.str .foo                             // ⇒ "foo"
__Sym.from "foo"                           // ⇒ .foo
__Str.unpack "abc"                         // ⇒ [97, 98, 99]
&s __Str.pack (__Str.unpack s)             // the identity on strings
```

Scalar→text is split by kind — `__Int.str` and `__Sym.str`, each monomorphic —
rather than one overloaded conversion; stringifying a compound value (list, map,
function) wants a real `inspect` and is deferred. Concatenation, interpolation,
multiline literals, and the rest of string manipulation are deferred too (see
[deferred](#deferred)); concatenate meanwhile by unpacking both strings, joining
the lists with `__List.append`, and packing the result.


### `List`, lists

A list is a positional, immutable sequence of zero or more values, written as a
Muon `<list>` — a `<seq>` in **brackets**. Elements are the `<chain>`s of the
sequence, delimited by `<sep>` (`,` or newline); each element chain is evaluated
as an `<expr>`.

```elly
[]               // the empty list — this is unit
[.a]             // a 1-list (distinct from the symbol .a)
[.a, .b]         // a 2-list, elements indexed .0 and .1
[.a, .b, .c]     // a 3-list
```

Brackets are the **only** list constructor, so every arity is spelled the same
way — including the 1-list `[.a]`, which is a real one-element list, *not* the
bare element. That removes the old ambiguity: grouping is `()` (which carries no
value — see [grouping and spread](#grouping-and-spread)), a list value is `[]`.

```elly
(x)              // grouping: == x        (no list)
[x]              // a 1-list holding x   (a value)
```

The empty list `[]` **is** unit: it is what the nullary marker `()` feeds (`f ()`
== `f []`), what a thunk is forced with, and the "none" of the `[]`/`[v]` option
convention. There is no separate unit value.

```ebnf
<list> ::= "[" <seq> "]"   (* zero or more element chains; a muon.list.
                               [] is unit; [e] is a 1-list; <sep> per muon-spec.md *)
```

#### projection and access

**Projection is not a separate form — it is syntax-level "application" of a list
to an index symbol that desugars into a getter** (like `List.get_elem` in
Elixir). Since juxtaposition is application, `[.zero, .one].0` is an `<iexpr>`:
the list "applied" to the symbol `.0`, selecting the named position:

- `[.zero, .one].0` evaluates to `.zero`
- `[.zero, .one].1` evaluates to `.one`
- `[].0` and `[.foo].1` do not name a valid position (raise
  `.projection_out_of_range`)
- `[.a, .b].foo` — a non-index symbol — raises `.bad_projection`

Note: the typeless interpreter may implement this as a special-cased
`App(<list>, <symbol>)`, but a typechecker will not accept a list in function
position, so it must treat projection as the distinct getter it desugars to. No
bracket-indexing syntax is added: `[i]` is itself a list value, so `t[i]` would
mean "apply the list `t` to the list `[i]`" (an error). Dynamic access and
destructuring are builtins (see below).

#### the `__List` module

Curried, strict in the list/index arguments; a
non-list where a list is required raises `.not_a_list`.

| builtin | shape | meaning |
| --- | --- | --- |
| `__List.size t` | `List → Int` | element count |
| `__List.get t i` | `List → Int → val` | element at 0-based `i`; out of range raises `.projection_out_of_range`, a non-integer `i` raises `.not_an_int` |
| `__List.append a b` | `List → List → List` | concatenation `[a…, b…]` |
| `__List.with t i v` | `List → Int → val → List` | `t` with index `i` replaced by `v`; out of range raises `.projection_out_of_range` |
| `__List.split n t` | `Int → List → [List, List]` | split at position `n` into `[left, right]` (left is the first `n` elements); `n` outside `[0, size]` raises `.projection_out_of_range` |

- `__List.get` generalizes `.N` projection to a **computed** index (`.0` only
  reaches literal positions). `__List.size` gives the bound for an `__Int.for`
  loop over a list.
- `__List.append`, `__List.with`, and `__List.split` are the **persistent
  update** operations the `rpds::Vector` backing makes cheap (structural sharing,
  no full copy): concatenate two lists, replace one index, or split at a
  position. `__List.split n t` returns a `[left, right]` pair, the inverse of
  `__List.append left right` when split at `left`'s size.

```elly
// sum a 3-list of ints by destructuring
[1, 2, 3] |> (&[a, b, c] __Int.add a (__Int.add b c))    // ⇒ 6

// safe head: branch on size first
&t __eq (__List.size t) 0 (&() .empty) (&() __List.get t 0)

// persistent update: grow, replace, split
__List.append [.a, .b] [.c]        // ⇒ [.a, .b, .c]
__List.with [.a, .b, .c] 1 .B      // ⇒ [.a, .B, .c]
__List.split 1 [.a, .b, .c]        // ⇒ [[.a], [.b, .c]]
```

The `__Int.divrem` builtin (see [integers](#int-integers)) returns a list `[q, r]`, so its
result is projected (`.0`/`.1`) or destructured by a pattern (`&[div, rem]`) like any
other.

Named fields / records are deferred; positional indices `.0`, `.1`, … are all
this subset has.


### `Map`, maps

A **map** is an immutable, persistent, **unordered** association from keys to
values, written `{ key: value, … }`. It is Elly's keyed collection, the
counterpart to the positional `[…]` list.

#### the map value

- **Keys are any value.** Symbols (`.foo`, `.0`), integers, unit, lists, other
  maps — and even closures — may all be keys; there is no key restriction and no
  bad-key error. Key identity is the **structural value equality** of `__eq` (see
  [equality](#__eq-value-equality)): integers by mathematical value (`0` = `+0`), symbols by text,
  strings by scalar sequence, lists/maps structurally — so the symbol `.0`, the
  integer `0`, and the string `"0"` are three **distinct** keys. Callables compare by **identity**, so two separately written
  `&x x` are distinct keys.
- **Iteration is unordered.** A map is a hash map, so the order in which
  `__Map.for` visits pairs (and in which a `(k)` capture pattern peels them) is
  unspecified — stable within one build, but not a language guarantee, so a
  program should not depend on it. There is no language-level ordering of keys,
  not even among numbers.

#### map literals (muon `<block>` → `Map`)

A literal is `{ <seq> }`; each chain of the sequence is one **entry**
`<key> ":" <value>`. The key is the single head item; the `:` is a `<punct>`; the
value is the rest of the chain lowered as an `<expr>`. An entry's key item is one
of:

- a bare **non-digit atom** (`one`) — the **symbol** of that spelling, exactly as
  `.one` would be (a key is just a token, so no keyword checks apply). A
  **digit-leading bare key** (`0`, `5`) is rejected to avoid the number/symbol
  confusion — write `.0` for the symbol or `(0)` for the integer;
- a `.`-prefixed **symbol** (`.one`, `.0`) — the same symbol key, written explicitly;
- a `(…)` **group** — a *computed* key, the enclosed expression evaluated
  (`(one)` is the value of variable `one`; `(0)` is the integer `0`);
- a `[…]` **list** — a list key; the empty list `[]` is the **unit** key;
- a `"…"` **string** — a string key, keyed by its text (distinct from the
  like-spelled symbol).

So `{ one: 1 }` is shorthand for `{ .one: 1 }`, and to key on a variable's value
or an integer you must parenthesize: `(one)`, `(0)`. An *empty* value tail is sugar
for the unit value `[]` (so `{ .foo: }` == `{ .foo: [] }`). A later entry with a key
equal to an earlier one **overwrites** it.

```elly
{}                          // the empty map (== __Map.nil)
{ []: .unit }               // the unit key
{ one: 1, two: 2 }          // symbol keys .one .two (== { .one: 1, .two: 2 })
{ .0: .zero }               // key is the SYMBOL .0
{ 0: .zero }                // also the SYMBOL .0 (bare atom → symbol)
{ (0): .zero }              // computed key → the INTEGER 0 (distinct from .0)
{ (one): 1 }                // computed key → the VALUE of variable one
{ (__Int.sub 2 2): .zero }  // computed key → integer 0
{ "foo": 1 }                // a STRING key (distinct from the symbol .foo)
{ "0": 0 }                  // STRING key "0" — distinct from .0 and the integer 0
```

#### access

There is no bracket / projection syntax yet; access is explicit via `__Map.get`
and `__Map.gets`. A missing key **raises** `.missing_key` (a catchable tag on the
single error channel), so a safe lookup is
`__Err.catch (&tag …) (&_ __Map.get m k)`.

TODO: add a projection syntax (bracket `m[k]` or a `.` projection).

#### the `__Map` module

Curried, strict in the map / key arguments; a non-map
where a map is required raises `.not_a_map`. Any value is a key, so there is no
bad-key error. Callbacks are applied with the same `apply` the `__Int`
eliminators use.

| builtin | shape | meaning |
| --- | --- | --- |
| `__Map.nil` | `Map` | the empty map (a value, not a function) |
| `__Map.with m k v` | `Map → key → val → Map` | `m` with `k` set to `v` (overwrites) |
| `__Map.get m k` | `Map → key → val` | value at `k`; a **missing key raises `.missing_key`** — branch safely with `__Err.catch` |
| `__Map.gets m ks` | `Map → (key…) → (val…)` | list of values for a list of keys (parallel); any missing key raises `.missing_key` |
| `__Map.for m state (&key &value &state e)` | `Map → s → (key → val → s → s) → s` | fold over the map (unspecified order) |
| `__Map.merge m1 m2 (&key &l &r e)` | `Map → Map → (key → opt → opt → opt) → Map` | generic merge: for each key in the **union**, the callback gets each side's value as an **option** (`[]` none / `[v]` some) and returns an option — `[]` drops the key, `[v]` sets it |
| `__Map.cat a b` | `Map → Map → Map` | union; on a key conflict **`b` wins** |
| `__Map.without m k` | `Map → key → Map` | `m` with `k` removed (a no-op if absent); the persistent-update counterpart of `__Map.with` |
| `__Map.size m` | `Map → Int` | element count, symmetric with `__List.size` (emptiness is also just `__eq {} m`) |

`__Map.merge`'s option encoding reuses lists: none is the empty list `[]`, some
is the 1-list `[v]` (built and size-matched with `__List`'s items; see [lists](#list-lists)). A
callback result that is not a `[]` / `[v]` list raises `.list_size_mismatch`
(or `.not_a_list` if it is not a list at all).

```elly
// build { .a: 1, .b: 2 } explicitly — the spread form, since a member reference
// in argument position would otherwise continue the chain (see application)
__Map.with(__Map.with(__Map.nil, .a, 1), .b, 2)

// count entries: fold ignoring key/value, +1 each
&m __Map.for m 0 (&_ &_ &st __Int.add st 1)

// value at .a, or .missing if absent (safe lookup via catch)
&m __Err.catch (&_ .missing) (&_ __Map.get m .a)

// union preferring the left map's value on a conflict
&a &b __Map.merge a b (&_ &l &r __eq (__List.size l) 1 (&_ l) (&_ r))

// refutable lookup: value at .a, or .absent — a miss falls through, not raises
&m __match [&{ .a: v, ...rest } v, &_ .absent] m
```

### `Fun`, functions

Functions are first-class values. There are two kinds of callable:

- **builtins** — the primitive operations in the reserved `__` namespace
  (`__Int.add`, `__List.get`, …), each curried and strict in its typed arguments;
- **closures** — user functions introduced by [abstraction](#abstraction) (`&`),
  which capture the environment in which they are written.

Both are applied by juxtaposition (see [application](#application)), and both
flow like any other value — passed as arguments, returned, stored in lists and
maps. Functions compare by **identity**, never by structure (see
[`__eq`](#__eq-value-equality)); `Fun` is the [kind](#value-kind-tests) that
matches any callable.

#### the `__Fun` module

TODO


## evaluation and control flow

Elly is a strict functional programming language, with arguments evaluated before
application.


### bindings, names

A bare name is a **reference**, never a binding. It evaluates to the value bound
by the nearest enclosing `&`-binder of the same name; if there is none, it is a
free name resolved in the surrounding (e.g. top-level / builtin) environment.

```elly
x        // the value bound by an enclosing &x, else a free name
```

Because binding is always marked with `&`, shadowing is explicit — a name is
never rebound by accident. The corollary is an accepted hazard in this subset:
omitting a `&` where you meant to bind silently turns an intended binding into a
reference.

The standalone name `_` is the **discard** pattern (see [abstraction](#abstraction)), not a
name: it never binds a value and is not a valid reference.

Names beginning with a double underscore (`__`) are **reserved** for builtins
and special forms (e.g. `__call`, `__keys` in `elly-intro.md`). They may be
*referenced* — they resolve in the surrounding environment like any other free
name — but a `&`-binder may not introduce a new one.

#### builtin modules and their aliases

Most builtins belong to a **builtin module**, a value that holds them as its
items and is named by a reserved `__`-name of its own:

| module | alias | holds |
| --- | --- | --- |
| `__Int` | `Int` | [integer](#int-integers) arithmetic and the ascending fold |
| `__Str` | `Str` | [string](#str-strings) packing and unpacking |
| `__Sym` | `Sym` | [symbol](#sym-symbols) conversion |
| `__List` | `List` | [list](#list-lists) size, access, and update |
| `__Map` | `Map` | [map](#map-maps) construction, lookup, update, and folds |
| `__Err` | `Err` | [raise and catch](#error-handling) |
| `__Mod` | `Mod` | module loading |

An item is reached with the ordinary dot — `__Int.add` is the module `__Int`'s
item `add` — so a builtin's name says which module it belongs to, and the dot
that says so is the same one that reads an item out of any other module. The
modules are values: `__Int` on its own evaluates to a module, and it is the same
module wherever it is referenced.

Each module is also reachable under its **bare alias** (`Int` for `__Int`), which
is the whole of Elly's prelude. An alias is resolved last, after every name that
could be bound — a `&`-binder, a `let`, a module item, a host-supplied binding —
so any of those shadows it, and the `__`-prefixed name is always available
underneath:

```elly
Int.add 2 3                              // ⇒ 5, through the alias
(&Int __Int.add 2 3) .anything           // ⇒ 5, the alias shadowed, the module still reached
```

`__match` and [`__eq`](#__eq-value-equality) belong to no module: they eliminate
values of every kind, so they are named bare.

Because [application](#application) is juxtaposition, a member reference written
as an argument continues the enclosing chain rather than standing alone —
`__Map.with __Map.nil .k 1` reads as `((__Map.with __Map) .nil .k) 1`. Write such
a call in the [spread form](#grouping-and-spread), which puts each argument in a
group of its own: `__Map.with(__Map.nil, .k, 1)`.

A few words are **keywords**: `let` (the local binding form; see
[local binding](#local-binding-let)), `as` (the type-narrowing pattern
qualifier; see [patterns](#patterns-and-matching)), and the
reserved-but-unused `with`, `when`, `match`, `case`, and `of` (parked for a
future `with`-binding form, a `<pat> when <cond>` guard, and surface `case` /
`match` sugar over the `__match` builtin). Unlike `__`-names, a keyword is not
even a reference — it is syntax, so it may be neither read nor bound anywhere.
This is the one exception to "a bare name is always a reference": these words are
recognized as keywords first. (Using a reserved-but-unused keyword at all is an
error until its form is designed.)

### abstraction

Abstraction introduces a function: `&` prefixes a binder, and the body is the
rest of the expression.

```elly
&x x       // the identity function
&x &y x    // &x (&y x) — a constant function of x
```

Binders curry, right-nested, mirroring left-nested [application](#application),
and because `&` reaches to the end of the expression a lambda used as a non-final
argument must be parenthesized:

```elly
&x &y e     ==  &x (&y e)          // abstraction, right-associative
f x y       ==  (f x) y            // application, left-associative
f x &y g y  ==  (f x) (&y (g y))   // the trailing lambda captures the tail
f (&x x) y  ==  ((f (&x x)) y)     // parens keep the lambda as one argument
```

A binder is a **pattern**, so it can destructure or narrow the argument, and a
`(…)` **binder group** curries several parameters at once:

```elly
&[a, b] e        // destructures a 2-list argument
&(x as Int) e    // narrows the argument to an Int
&(a, b) e   ==  &a &b e     // a binder group: two curried parameters
&() e       ==  &[] e       // nullary: a thunk asserting a unit argument, forced by f ()
```

#### formal definition

An abstraction is a Muon `<prefixed>` item (`&` glued to a binder header)
followed by a body expression; it evaluates to a one-parameter closure (see
[`Fun`](#fun-functions)). `&` has the **lowest precedence**, so the body is the
rest of the expression, extending to the end of the enclosing expression. An
abstraction with a binder but no body, or a body but no binder (`&x` alone), is
ill-formed.

```ebnf
(* no whitespace between "&" and the binder header *)
<abs>            ::= "&" <binder-header> <expr>  (* body is the rest of the expr, right-nested *)
<binder-header>  ::= <item-pattern>    (* a pattern occupying one Muon <item> (see below) *)
                   | <binder-group>    (* a (…) group that curries *)
<binder-group>   ::= "(" ")"                                  (* nullary: == "[]" *)
                   | "(" <pattern> (<sep> <pattern>)* ")"     (* == &p0 &p1 … *)
```

Because `&` binds a single Muon `<item>` (`<prefixed> ::= "&" <item>`), a bare
header — one written without a surrounding `(…)` group — must be a pattern that
fits in **one** item. Any pattern that spans several items (`= <ref>`,
`< <ref>`, `> <ref>`, `<pat> as <Type>`, the at-pattern `<name> = <pat>`, the
or-pattern `<pat> | <pat>`) is **not** a legal bare header and must be wrapped in
a `(…)` group. A bare matching literal — a `<num>`, a `.sym`, or a string — is
rejected too, though it fits in one item: `&(42)` / `&(.foo)` / `&("s")`, never
`&42` / `&.foo` / `&"s"`, so a lone literal is not read as a stray value in
binder position. The bare forms — each equal to the same pattern grouped,
`&(<pat>)` — are:

| bare header      | ≡            | binds / matches |
| ---------------- | ------------ | --------------- |
| `&<name>`        | `&(<name>)`  | binds the argument to `<name>` |
| `&_`             | `&(_)`       | discards the argument (binds nothing) |
| `&[<pat>, …]`    | `&([<pat>, …])` | a list pattern |
| `&{ <key>: <pat>, … }` | `&({ <key>: <pat>, … })` | a map pattern |

`&(…)` is not a table row because it is the **binder group** itself: a single
chain is one grouped pattern (`&(p)` == `&p`), while several comma-separated
chains curry into successive parameters (`&(a, b)` == `&a &b`).

Application is the **elimination** form: applying an abstraction substitutes the
argument for the bound name, β-reduction cancelling one `&` against one applied
argument — `(&x e) a → e[x := a]`. Abstraction and application are thus the
introduction and elimination forms of functions.

The binder header is matched in an **irrefutable** position: a structural
mismatch (wrong list size, wrong kind, a failed `= <ref>`) **raises** rather
than falling through — the refutable form is `__match` (see
[patterns and matching](#patterns-and-matching)). Two constraints hold on any
binder:

- `_` is the **discard** pattern: `&_ e` still consumes one applied argument
  (β-reduction cancels the `&` as usual) but binds no name.
- A binder may not introduce a `__`-prefixed name — those are reserved (see
  [bindings, names](#bindings-names)) — so `&__x e` is ill-formed.

The `(…)` **binder group** is the mirror of application spread
([grouping and spread](#grouping-and-spread)): its chains curry into successive
parameter patterns, and the empty group `()` is the nullary marker, desugaring to
`&[]` (the unit pattern). A "nullary function" is thus a thunk that *asserts* it
was forced with the unit `[]`: `&() e` suspends `e` behind one parameter until
`f ()` (feeding the unit `[]`) fires it — there is no zero-argument function
distinct from a value. The two roles of `(…)` diverge here: inside a binder group
commas **curry** into successive parameters, while inside a single pattern they
are an error — so `&[a, b]` is one 2-list parameter, `&(a, b)` is two parameters,
and `&((a, b))` is ill-formed.

### local binding (`let`)

Binding a value to a name is, at bottom, abstraction-and-application: `(&x e) v`
evaluates `e` with `x` bound to `v`. But that reads backwards — the value sits
*after* the body. `let` is **sugar** for the same thing, written name-first:

```elly
let (x = v) e          // ≡ (&x e) v  — evaluate e with x bound to v
let (x = .foo) x       // → .foo
```

`let` adds no evaluation semantics of its own: it lowers to `App`/`Abs` and
inherits everything from them — strict, value-first evaluation, and the fact that
a binder may be `_` (discard) but not a `__`-name.

A binding's left-hand side is a **pattern** (see [patterns](#patterns-and-matching)), exactly like a `&`
parameter: `let (pat = v) e` desugars to `(&pat e) v`. The **separator is the
first top-level `=`** (one not nested inside `(…)`/`[…]`/`{…}`), so a pattern
that itself carries a top-level `=` — an at-pattern `n = p` or an equality
`= <ref>` — must be parenthesized to keep the binding's `=` unique. A top-level
`|` (an or-pattern) must be parenthesized for the same reason, so it does not
compete with the binding `=`:

```elly
let ([a, b] = v) e            // atomic list pattern — parens optional
let ((n = [a, b]) = v) e      // at-pattern — the wrap makes the binding `=` unique
let ((= 3) = v) e             // an equality pattern in binder position is an assert
let ((.a | .b) = v) e         // or-pattern LHS — wrap the `|`, never `let (.a | .b = v)`
```

Unlike `&(a, b)` (two curried parameters), a `let` binding takes **one** pattern:
there is no `let ((a, b) = v)` curry-group. By happenstance `let ((= <val>) = e)`
is an **assert** — it binds nothing and raises `.no_match` unless `e` equals
`<val>`.

The body is **the rest of the expression**, exactly like `&`: `let` has the
lowest precedence and extends to the end, so `let (x = 1) f x` is
`let (x = 1) (f x)`, and a `let` used as a non-final argument must be
parenthesized.

A binder group may hold **several** bindings, separated by `<sep>` (`,` or
newline). They are **sequential**: each right-hand side sees the binders to its
left, so `let (a = 1, b = a) …` is valid and `b` is `1`. This desugars to nested
`let`s:

```elly
let (a = va, b = vb) e   ≡   let (a = va) (let (b = vb) e)   ≡   (&a ((&b e) vb)) va
```

so `va` is evaluated in the enclosing scope and `vb` in the scope where `a` is
bound. Being nested `&`/apply, `let` is therefore **non-recursive** — a
right-hand side never sees its own binder.

An **empty group binds nothing**: `let () e` is `e`, the fold over zero bindings.
It is not an error, so a group assembled by a generator, or one whose bindings are
all commented out, still reads. Because the group is a Muon `<seq>`,
blank lines, hanging separators, and comments between bindings are allowed, so a
group can be laid out as a block:

```elly
let (
  a = 1

  // b builds on a
  b = a
) __Int.add a b        // → 2
```

TODO: a binder group `(a = 1, b = 2)` is written with parens like an argument
group, but `let` reads it as a left-to-right **binding** group — scope threads
through the commas, so a right-hand side sees the binders to its left (unlike an
argument spread `f (a, b)`, whose chains are independent expressions in one
scope). This is the same syntax-is-context hazard the parens carry everywhere
(grouping vs spread vs binder group); a future parallel form (all right-hand
sides in the enclosing scope) is what the reserved keyword `with` is earmarked
for.

### recur

`recur` is `let`'s recursive sibling: the same parenthesized binder group followed
by a body, with the bindings **simultaneous** rather than sequential. Each one sees
all of them, itself included, so a group may be self- or mutually recursive and its
source order does not matter.

```elly
recur (
  even = &(n as Int) n |> __match [&(0) .yes, &(> 0) odd(__Int.sub(n, 1))]
  odd  = &(n as Int) n |> __match [&(0) .no,  &(> 0) even(__Int.sub(n, 1))]
) even 10                                       // → .yes
```

`let` cannot express this: it desugars to nested `&`/apply, so a right-hand side
never sees its own binder, and at `even`'s binding `odd` does not exist yet.

The two forms are deliberately parallel — read as siblings, differ in one word —
and they diverge in exactly two places, both falling out of the mechanism rather
than being choices:

- **The left-hand sides are plain names, not patterns.** The group is a table of
  named items, so it follows a module's rule rather than `let`'s. A duplicate name
  is an error.
- **A binding may not shadow a name already in scope.** Because the bindings are
  simultaneous, a shadowed name inside the group would mean the group's own
  binding, never the outer one — the opposite of what the identical `let` line
  means. That trap is rejected rather than resolved silently. A binder written
  *inside* the group still shadows an item, as binders shadow everything.

Everything else is `let`'s: lowest precedence with the body extending to the end of
the chain (so `recur (…) f x` is `recur (…) (f x)`, and a non-final `recur` must be
parenthesized), a group laid out over lines with comments and blank lines, and an
empty group meaning the body alone.

Bindings are **not forced on entry** — a binding is evaluated when it is first
referenced — so a group may carry one that would raise as long as nothing asks for
it. Each evaluation of a `recur` is a fresh activation with its own bindings: two
activations close over different scopes and their items are not equal.

### application

Juxtaposition of items in a chain is function application, **left-associative**:

```elly
f x      // apply f to x
f x y    // (f x) y
```

A parenthesized `<tuple>` in a chain does **not** contribute one argument — it
**spreads**: each of its chains becomes one successive argument (see *grouping and
spread* below), so `f (a, b)` is the curried call `f a b`. A *list value* is
written with brackets instead (see [lists](#list-lists)).

```ebnf
(* top-level expressions: mapped from a muon.chain *)
<expr> ::=
    | <let>              (* local binding; see "local binding" *)
    | <iexpr>? <abs>
    | <iexpr>

(* "itemic" expressions: mapped from a muon.chain of muon.item. Each <arg> is one
   item; a parenthesized <group> is *not* one arg but a spread — it contributes
   its chains as successive args (grouping / spread / nullary; see below). *)
<iexpr> ::=
    | <iexpr> <arg>      (* left-associative *)
    | <arg>
<arg> ::=
    | <aexpr>            (* one atom = one argument *)
    | <group>            (* a (…) spread: zero, one, or many arguments *)

(* a muon.tuple `( … )`, read by chain count:
     ()        -> the nullary marker: feeds one unit value [] (an empty call)
     (e)       -> grouping: the single expression e (one argument)
     (e0, e1…) -> spread: each chain as one successive argument *)
<group> ::= "(" <seq-of-exprs> ")"

(* "atomic" expressions: mapped from a muon.item *)
<aexpr> ::=
   | <name>          (* a reference to a binding *)
   | <symbol>        (* an atomic symbol like `.x`, `.0`, etc *)
   | <int>           (* an arbitrary-precision integer literal; see integers *)
   | <str>           (* a string literal, a muon.str `"…"`; see strings *)
   | <list>         (* a runtime list value, a muon.list `[ … ]`; see lists *)
   | <block>         (* a map literal, a muon.block `{ … }`; see maps *)

(* an identifier: latin letters, digits and `_`, not starting with a digit, and
   not the standalone `_` (the discard pattern; see abstraction). A name may
   start with `__`, but only to reference a builtin — never to bind a new name. *)
<name> ::= (* a <muon.sym> matching the above that is not a number *)

(* a `.`-prefixed literal: `.` glued to a single name or number segment. *)
<symbol> ::= (* a <muon.prefixed> with `.` sigil wrapping a name or number *)

(* an integer literal: `0`, `-123`, `+7`, `1_000_000`, `0xCAFE`, `0b1010`.
   Recognized before <name>; a `.`-prefixed item is a <symbol>, not an <int>.
   See integers for the full digit/base/separator grammar. *)
<int> ::= (* a <muon.sym> matching the integer grammar in "integers" *)

(* a string literal: `"…"`, a muon.str. JSON escapes and `\uXXXX` (surrogate
   pairs combined) are decoded at parse; a lone surrogate is a parse error.
   See strings. *)
<str> ::= (* a <muon.str>, decoded per "strings" *)

(* abstraction; the binder is a single name or a (…) group of binders that
   curries — &(a, b) e == &a &b e, &() e == &_ e. See "abstraction". *)
<abs> ::= "&" <binder-header> <expr>  (* the header is mapped from <muon.prefixed> *)

(* local binding; the keyword "let" leads a muon.chain, then a binder group
   (a muon.tuple) and the body. See "local binding". *)
<let>     ::= "let" "(" <binding> (<sep> <binding>)* ")" <expr>
<binding> ::= <pattern> "=" <expr>  (* LHS pattern carries no top-level "=" / "|" — wrap those in (…) *)
```

A trailing `<abs>` is the application's last argument and captures the rest of
the expression.

#### grouping and spread

Parentheses are **pure syntax** — they never build a value. A `( <seq> )` in a
chain is read by how many chains it holds, on the rule **one chain → one
argument**:

```elly
(e)         // grouping: the one expression e
(f x)       // == f x       (one chain: an application)
f (a, b)    // spread: == f a b  (two chains → two arguments)
f (a) b     // == f a b     (one-chain group is just grouping)
```

The single exception is the **empty** group `()`, the **nullary marker**: an
empty call still calls, so `()` feeds one **unit** value `[]`:

```elly
f ()        // == f []      (a nullary call feeds the unit [])
```

So the count is: N ≥ 1 chains spread to N arguments; 0 chains feed one unit. This
keeps the familiar `f ()` and the thunk idiom (`&() body`, forced with `()`; see
[abstraction](#abstraction)). A standalone `()` with no function to feed degenerates to the unit
`[]`.

Because `()` carries no value, a genuine list — including a 1-list — is written
with brackets: `[a, b]`, `[x]` (distinct from `x`), `[]` (see [lists](#list-lists)).

#### the pipe combinator

`|>` is the **pipe**: it threads its left operand in as the final argument of the
application on its right. `L |> R` is exactly `R L` — the whole right-hand spine
applied to one more argument, `L`:

```elly
x |> f            // == f x
h x |> g y        // == g y (h x)   (the left spine is one argument)
3 |> __Int.add 1  // == __Int.add 1 3   → 4  (piped value is the last argument)
```

It is left-associative, so a pipeline reads left-to-right as a data flow, each
stage receiving the previous result as its last argument:

```elly
h x |> g y |> f z   // == f z (g y (h x))
```

`|>` is a `<punct>` at the Muon layer (`>` is a punctchar, so `|>` munches as one
token; see `muon-spec.md`), given meaning only here — lowering-time sugar to
application (`App`), adding no evaluator semantics.

It binds looser than application (juxtaposition) but tighter than `&`/`let`
([abstraction](#abstraction) / [local binding](#local-binding-let)):

- Looser than application means the right operand is the whole spine, not just its
  head: `x |> f a b` is `f a b x`, and `xs |> map (&x f x)` is `map (&x (f x)) xs`
  — the pipe idiom, with the lambda parenthesized exactly as any non-final-argument
  lambda must be (see [abstraction](#abstraction)).
- Tighter than `&`/`let` means a `&`/`let` captures the pipe as (part of) its
  body: `&x x |> f` is `&x (f x)` — a composition — not `(&x x) |> f`, and
  `let (x = a) x |> f` runs `f x` with `x` bound to `a`.

Both operands must be present: `|> f`, `x |>`, and `x |> |> f` are ill-formed.


## patterns and matching

A **pattern** matches an input value, binding names as it goes. One grammar
serves every binder position — a `&` parameter, a `let` binding's left-hand
side, and a `__match` clause. A pattern is a **first-class AST node** the
evaluator matches **directly**: `&<pat> body` is the one binding form, and
applying it *matches* the argument against `<pat>`, extending the environment or
**refuting**. Patterns are *not* compiled into other primitives at parse time;
they carry no runtime value of their own. (A later bytecode backend may compile a
whole match into branch instructions — see [elly-patterns-native.md](./done/2026-07-26_elly-patterns-native.md).)

**Every structural mismatch refutes** (`⟂`) — a wrong kind, a wrong arity, a
failed `= <ref>` / `< <ref>` / `as <Type>` — carrying the *original error* it
stands for (`.not_a_list`, `.list_size_mismatch`, `.no_match`, …). A pattern is a
**closed grammar**: it embeds no general expression, so **matching itself does
not raise**. The comparand of `=` / `<` / `>` and a computed map key are each a
`<ref>` — a **name** or a **literal** — evaluated with the ordinary expression
default; a literal cannot raise, a bound name resolves, and the *only* real
`Error` a match can produce is referencing an **unbound** name in a `<ref>` (a
normal reference error, not a refutation), which propagates. A pattern is *used*
two ways: in **binder position** (`&` / `let`) a refutation is uncaught, so it
surfaces as its original error; the **refutable** `__match` builtin (below)
catches the refutation and falls through to a fallback instead.

| pattern             | meaning |
| ------------------- | ------- |
| `_`                 | matches anything, binds nothing (discard) |
| `name`              | binds the subject to `name`, sugar for `name = _` |
| `name = <pat>`      | at-pattern: binds the subject to `name`, **then** matches `<pat>` against it |
| `(<pat>)`           | grouping — a single subpattern (commas are an error here) |
| `(<pat> \| <pat>)`  | or-pattern: try left, on refutation try right (same binder set) |
| `<pat> as <Type>`   | type-narrowing (postfix): matches iff the subject is of `<Type>`, then matches `<pat>` |
| `(as <Type>) <pat>` | type-narrowing (prefix): the same, qualifier parenthesized |
| `.sym`              | matches a symbol literal (bare-literal equality, like `<num>`) |
| `<num>`             | matches an integer literal (`= <num>` sugar); binds nothing |
| `"str"`             | matches a string literal (`= "str"` sugar); binds nothing |
| `= <ref>`           | matches iff the subject equals `<ref>`'s value; binds nothing |
| `< <ref>`           | matches iff the subject is ordered **before** `<ref>`'s value; binds nothing |
| `> <ref>`           | matches iff the subject is ordered **after** `<ref>`'s value; binds nothing |
| `[<pat>, …]`        | list pattern — fixed arity, with an optional trailing rest |
| `{ <key>: <pat>, … }` | map pattern — closed by default, with an optional trailing rest |

where a **`<ref>`** (the comparand of `=` / `<` / `>`) is a single **atom** — a
`<name>` (`= x`) or a literal (`= 5`, `= .foo`, `= "s"`). It is *not* a general
expression:
a pattern never recurses into expression syntax, so a compound `= f x` / `< (f x)`
is a parse error.

Rules:

- **A bare `name` always binds; `.sym`, `<num>`, `"str"`, and `= <ref>` never bind.** The
  `= <ref>` comparand is a name or literal evaluated in the enclosing scope
  extended by the bindings to its left, so `[x, = x]` matches a pair of equal
  elements. (Left-to-right order between *independent* sub-patterns is not yet a
  language guarantee.)
- **A bare literal is an equality pattern.** A `.sym`, a `<num>`, or a string in
  pattern position matches by equality — `42` ≡ `= 42`, `.foo` ≡ `= .foo`,
  `"s"` ≡ `= "s"` — so `(1 | 2 | 3)` reads better than `(=1 | =2 | =3)`. One
  exception: a **lone matching literal that is a whole `&`-header or `let` LHS
  must be parenthesized** — `&(42)` / `&(.foo)` / `&("s")`, `let ((42) = v)`,
  never `&42` / `&.foo` / `&"s"` / `let (42 = v)` — so a bare literal is not
  mistaken for a stray value in binder position. A literal nested in `[…]` /
  `{…}` / `(…)` / an or-pattern needs no parens.
- **Ordering patterns compare within one kind.** `< <ref>` / `> <ref>` are
  *strict* comparisons of the subject against `<ref>`'s value. Each comparable
  kind orders only against itself — `Int` numerically, `Str` lexicographically by
  scalar (see [strings](#str-strings)) — so a subject and bound that are not both
  of the *same* comparable kind **refute** (a refutation, not a host raise):
  `.not_string` when the bound is a string, otherwise `.not_int`. An in-kind
  comparison that does not hold refutes `.no_match`. `<= e` and `>= e` are not primitives —
  write them as or-patterns, `(< e) | (= e)` and `(> e) | (= e)`. Both directions
  are provided (rather than just `<`) because the subject is fixed on the left, so
  neither bound can be expressed by flipping the other.
- **`as` narrows to a closed, capitalized set** — `Int Sym Str List Map Fun`,
  the six runtime kinds (`Fun` = any callable). `as` binds tighter than `=`, so
  `name = p as Int` reads `name = (p as Int)`. `as <Type>` is not a pattern on
  its own: the bind-nothing type test is `_ as <Type>`, and `(as Int)` alone is
  an error. The kind test is total, so a wrong kind *refutes* `.no_match`
  (fall-through) rather than raising a host `.not_an_int`.
- **List patterns** are fixed-arity; a size mismatch refutes. One **trailing
  rest** is allowed — `[p0, …, ...rest]` binds `rest` to a list of the
  remainder, and `...` (no name) ignores it. Rest-in-the-middle is deferred.
- **Or-patterns `(p1 | p2)` are committed, left-to-right.** The left arm is
  tried first; if its *pattern* refutes, the right arm is tried. Once an arm's
  pattern matches it is **committed** — a later refutation in the continuation
  (a sibling sub-pattern, or the body) propagates rather than backtracking into
  the other arm. Both arms must bind exactly the same set of names, checked at
  parse time. Multiple `|` is left-associative: `(a | b | c)` parses as
  `((a | b) | c)`.
- **Map patterns are closed by default.** `{ .a: p }` matches a map with
  **exactly** key `.a` (whose value matches `p`); an extra key refutes
  (`.map_size_mismatch`), a missing key refutes (`.missing_key`), a non-map
  refutes (`.not_a_map`). A trailing rest **opens** it: `{ .a: p, ... }` matches
  *at least* `.a`, and `{ .a: p, ...rest }` binds `rest` to the remainder map
  (the matched keys removed). A **key is itself a pattern**, of two kinds:
  - a **lookup** names a concrete key: the literal `.sym`, a string literal
    `"foo"`, a bare *non-digit* `sym`, or a parenthesized `(= <ref>)` / `(<lit>)`
    for a computed or numeric key. A **digit-leading bare key is rejected** (`{ 5: p }`) to avoid the
    number/symbol confusion — write `.5` for the symbol key, or `(5)` / `(= 5)`
    for the integer key `5`. Both `(5)` and `(= 5)` are lookups (a `(<pat>)` group
    whose pattern is an equality), but **`(= 5)` reads best** here: a bare `(k)` in
    key position is a *capture*, so the `=` marks "lookup, not binder". (This is
    also why the pattern writes `(= k)` where a map *literal* writes `(k)`.)
  - a **capture** is a grouped binder in key position — `(k)` / `(_)` — the map
    analogue of the list `[a, ...rest]`. It **peels an unspecified remaining
    entry**, binding its key (and, via the value pattern, its value): so
    `&{ (k): v } { .one: 1 }` binds `k = .one, v = 1`. Multiple captures peel that
    many entries; a map is unordered, so *which* entries they peel (and in what
    order) is unspecified and a program should not depend on it. **Lookups run
    first:** the specific-key lookups claim and remove their keys, *then* the
    captures pop from what remains, *then* closedness / the rest apply to the
    leftover — so a capture never steals a key a lookup wanted. A capture on an
    empty (or fully-consumed) map refutes `.missing_key`.


### `__match`, the multi-clause form

```elly
__match <clauses> <val>
```

`__match` takes a **list of clauses** (each a matcher, typically `&(<pat>) <body>`)
and tries them against `<val>` in order:

- the **first clause that matches** returns its body's value, and no later clause
  runs — only one body is guaranteed to run;
- a clause that **refutes** (a `NoMatch`) is skipped and the next is tried;
- a clause that raises a genuine **`Error`** — a real failure in the body (a
  pattern itself cannot raise, save an unbound name in a `<ref>`) — **propagates**;
- falling off the end — an empty list, or every clause refuting — itself refutes
  `.no_match`: uncaught it surfaces as `.no_match`, but nested inside another
  matcher it is still catchable.

Because every structural probe refutes, `__match` catches a wrong kind, a wrong
arity, and a failed `=`/`.sym`/`as` alike; only a real error escapes. A
multi-clause match is just a longer list — no nesting needed:

```elly
// classify a symbol, else fall through
&x __match [&(.a) .got_a, &(.b) .got_b, &_ .other] x
```

A `&_` final clause is the total fallback; drop it and an unmatched value refutes
`.no_match`. Surface `case` / `match` / `of` sugar over `__match` is reserved but
not yet built.

### `__eq`, value equality

`__eq` compares **any two values** and branches on whether they are equal.
It is the general equality eliminator.

| builtin | shape | meaning |
| --- | --- | --- |
| `__eq x y onEqual onElse` | `a → a → (a → r) → (a → r) → r` | `onEqual x` if `a` equals `b`, else `onElse x` |

- The branches receive the evaluated first argument (`a → r`)
- Neither operand is constrained — comparing values of different kinds is allowed

The **equality relation** it eliminates:

- **Data is structural.** Integers are equal by mathematical value (`0` = `+0`),
  symbols by their text, strings by their scalar sequence (no Unicode
  normalization), and lists elementwise (same length, equal elements). So the
  symbol `.0`, the integer `0`, and the string `"0"` are pairwise **not** equal,
  and `[]` (unit) equals only `[]`.
- **Functions are by identity, not structure.** Two closures are equal only if
  they are *the same* closure — one value flowing to two places — so two
  separately written `&x x` are **distinct**. Builtins are equal when they are the
  same operation applied to equal arguments (`__Int.add` = `__Int.add`,
  `__Int.add 1` = `__Int.add 1`, but `__Int.add 1` ≠ `__Int.add 2`), and a builtin
  is never equal to a closure.

There is no total order over all values. Ordering is defined only *within* the
comparable kinds `Int` and `Str`, and only through the `< <ref>` / `> <ref>`
[patterns](#patterns-and-matching) — numerically for integers, lexicographically
by scalar value for strings. Maps are hash maps keyed by this structural
equality, so their iteration order is unspecified (see [maps](#map-maps)).

```elly
// discriminate two values
__eq .a .a (&_ .same) (&_ .diff)          // ⇒ .same
__eq .0 0  (&_ .same) (&_ .diff)          // ⇒ .diff  (symbol vs integer)
__eq [1, 2] [1, 2] (&_ .same) (&_ .diff)  // ⇒ .same

// identity: a closure equals itself, not a twin
(&f __eq f f (&_ .same) (&_ .diff)) (&x x)   // ⇒ .same
__eq (&x x) (&x x) (&_ .same) (&_ .diff)     // ⇒ .diff
```


### value kind tests

Asking a value's kind and falling through on "no" is done with `<pat> as <Type>`
**patterns** (see [patterns](#patterns-and-matching)), not a builtin. `x as Int` narrows `x` to `Int`,
refuting `.no_match` off-kind; the six kinds are `Int Sym Str List Map Fun`
(`Fun` = anything applicable — a closure or an unsaturated builtin). Classify a value with
a `__match`:

```elly
// classify any value: the first matching clause wins
&x __match [&(_ as Int) .int, &(_ as Sym) .sym, &_ .other] x

// prove a value is callable, then use it
&g __match [&(f as Fun) f 2 3, &_ .not_a_fun] g
```

The kind test is **total** — it never raises, it only matches or refutes — which
is exactly what puts it on the pattern-refutation path. `Fun` is also the name the
future standard module/type will carry (`as Fun Int Int` ≙ `Int -> Int`).


### how matching runs

The evaluator matches a value `v` against a pattern by structural recursion,
threading the environment (this is the native `match_pattern` in `eval.rs`; there
is no eliminator desugaring):

- `_` succeeds binding nothing; `name` binds `v`.
- `name = p` binds `v` to `name`, then matches `p` against `v`.
- `= e` evaluates `e` (which may raise a real `Error`) and succeeds iff `v`
  equals it, else refutes `.no_match`. `< e` / `> e` likewise, but succeed iff
  `v` is strictly ordered before / after `e`'s value *within a shared comparable
  kind*, refuting off-kind (`.not_string` when the bound is a string, else
  `.not_int`) and `.no_match` on an in-kind miss.
- `p as T` succeeds iff `v` is of kind `T` (a total test, never raising), then
  matches `p` against the narrowed `v`; off-kind refutes `.no_match`.
- `[p0 … pn]` refutes `.not_a_list` on a non-list, `.list_size_mismatch` on a
  wrong arity (exact without a rest, a minimum with one), else matches each
  element left-to-right and binds a named rest to the remainder.
- `{ … }` matches in **two passes**: the concrete-key **lookups** claim and
  remove their keys first (a missing key refutes `.missing_key`), then each
  **capture** pops an unspecified remaining entry (an empty remainder refutes
  `.missing_key`), then closedness / a named rest apply to what is left (a
  leftover under a closed pattern refutes `.map_size_mismatch`). Lookup keys and
  embedded expressions each evaluate once, in source order.
- `(p1 | p2)` is **committed**: matching returns the first arm whose pattern
  matches (with that arm's bindings) and the body runs once afterward, so a later
  refutation propagates rather than backtracking into the other arm.

A `&<pat> body` binder and `let (pat = v) body` share this single matching path
(`let` desugars to `(&<pat> body) v`, reusing `&`/`App`). A backend may instead
compile a whole `__match` into a decision tree of explicit tests and branches,
turning a refutation into a jump; the operational rules above are the meaning it
must preserve. See `elly-patterns-native.md`.

### the refutation signal `⟂` — `NoMatch` vs `Error`

The error channel carries **two kinds** of unwinding value (see [errors](#error-handling)): an
`Error` — a genuine failure (`__Err.raise`, a host abort) — and a `NoMatch` — a
pattern refutation, produced by the matcher on a structural miss and carrying the
original error `v` the refutation stands for. The distinction is by
*construction*, not an inspectable tag: user code only ever produces `Error` (via
`__Err.raise`), so it **cannot forge** a `NoMatch` — a plain `__Err.raise
.no_match` is an `Error`, not a refutation. Only `__match` singles out `NoMatch`;
every other boundary (`__Err.catch`, the top level) treats it exactly as its
payload `v`, so an **uncaught refutation surfaces as its original error**.


## error handling

Evaluation has a single **raised-value** channel. Any expression either
evaluates to a value or **raises** one. A raise abandons the surrounding
computation — arithmetic, list construction, application, projection — and
unwinds to the nearest enclosing `__Err.catch`, or to the top level if there is
none (where it surfaces as the program's error).

A raise is one of **two kinds**: an `Error` (a genuine failure) or a `NoMatch` (a
pattern refutation carrying the original error it stands for; see [patterns](#patterns-and-matching)).
They differ only in what stops them — `__match` catches `NoMatch` and lets
`Error` through; **every other boundary treats a `NoMatch` as its payload**, so
`__Err.catch` and the top level see an uncaught refutation as its original error.
Host failures and `__Err.raise` produce `Error`; only the pattern matcher
produces `NoMatch` (on a structural miss), so the refutation signal cannot be
forged.

Host failures **raise**, they do not silently abort: `__Int.divrem x 0` raises
`.div_by_zero`, a non-integer operand raises `.not_an_int`, a negative exponent
raises `.negative_exponent`, an out-of-range projection raises
`.projection_out_of_range`, and so on. This is the same channel `__Err.raise`
uses, so all of them are catchable uniformly.

| host failure | raised value |
| --- | --- |
| divisor `0` in `__Int.divrem` | `.div_by_zero` |
| non-integer operand to an `__Int` builtin | `.not_an_int` |
| negative exponent in `__Int.pow` | `.negative_exponent` |
| projecting (or `__List.get`) past a list's end | `.projection_out_of_range` |
| projecting with a non-index symbol | `.bad_projection` |
| applying a non-function, non-list value | `.not_applicable` |
| a reference with no binding | `.unbound_name` |
| a non-list where `__List` needs one | `.not_a_list` |
| a non-map where `__Map` needs one | `.not_a_map` |
| `__Map.get` / `__Map.gets` on an absent key | `.missing_key` |
| a non-string where `__Str` / `__Sym.from` needs one | `.not_a_str` |
| a non-symbol argument to `__Sym.str` | `.not_a_sym` |
| a codepoint out of `0…0x10FFFF` (or a surrogate) in `__Str.pack` | `.bad_codepoint` |
| a string that is not one Muon `<sym>` segment in `__Sym.from` | `.bad_symbol` |
| an uncaught pattern refutation — decays to its original `tag` | e.g. `.not_a_list` / `.list_size_mismatch` / `.map_size_mismatch` / `.not_int` / `.not_string` / `.no_match` |

The tags are bare symbols for now; carrying the offending value (or a source
span / backtrace) is a deferred, additive refinement. `.unbound_name` is a check
that could later move to lowering; promoting it is subtractive from this channel,
not a redesign of it.

### the `__Err` module

| builtin | shape | meaning |
| --- | --- | --- |
| `__Err.raise x` | `a → ⊥` | raise `x` as an `Error`; never returns normally |
| `__Err.catch onErr wrapped` | `(e → r) → ([] → r) → r` | `wrapped ()`, but on *any* raise `onErr <payload>` |
| `__match clauses val` | `[a → r] → a → r` | try each clause on `val` in order; the first to match wins, a `NoMatch` clause is skipped, an `Error` propagates; an empty/exhausted list refutes `.no_match` |

- `__Err.raise x` raises the value `x` and does not return. It is strict only in
  that `x` is already evaluated (call-by-value; if computing `x` itself raised,
  that short-circuited first); it wraps `x` untouched — a symbol, list, or any
  other value.
- `__Err.catch onErr wrapped` forces `wrapped ()`. If that yields a value, it *is*
  the result of `__Err.catch` and evaluation continues in the enclosing
  expression (the implicit continuation — there is no `onOk`). If it instead
  raises, the result is `onErr <payload>` — `__Err.catch` is the *universal*
  boundary, catching both an `Error` and a `NoMatch` (an uncaught refutation,
  delivered as the original error it carried; only `__match` singles `NoMatch`
  out). `wrapped` **must** be a thunk (`&_ …`):
  under real short-circuiting an eager argument would unwind *past* the catch
  before it ran, so the thunk defers the risky work into the builtin's control —
  the same shape as the `__eq` branch thunks. A raise *from* `onErr`
  propagates; it is not re-caught here. Handler-first curries: `__Err.catch onErr`
  is a reusable catcher awaiting the risky computation.

```elly
// a safe divide: catch the zero-divisor raise, report a symbol instead
&x &y __Err.catch (&_ .undefined) (&_ (__Int.divrem x y).0)

// bubble a domain error, then rescue it at the boundary
__Err.catch (&exc exc) (&_ __Err.raise .not_found)   // ⇒ .not_found

// success flows straight through the catch into the continuation
__Int.add 1 (__Err.catch (&_ 0) (&_ 41))             // ⇒ 42
```

Discriminating a caught tag — handling `.div_by_zero` but re-raising the rest —
uses `__eq` (see [equality](#__eq-value-equality)): the handler tests `exc` against a tag, and its
`onElse` branch, which binds the original value, re-raises it. That handler
appears as the second example under [symbols](#sym-symbols).


## deferred

Intentionally out of this subset (carrying `TODO:` here and/or in
`elly-intro.md`):

- the wider numeric tower **`Num`** — rationals, floats, complex (with `Int` as a
  subset), and any numeric coercions
- named list **fields / records** (`[foo: 1, bar: 2]`) — a list-layer (`[…]`)
  feature
- **more string functionality** — concatenation, interpolation, multiline
  literals, slicing, and a general/polymorphic stringify (`inspect`); the `Str`
  value itself (literals, map keys, comparison, a codepoint round-trip) has
  landed (see [strings](#str-strings))
- **more of pattern matching** — the pattern grammar and the refutable `__match`
  builtin are in [patterns](#patterns-and-matching); still to come are pattern **rest-in-the-middle**
  (only a trailing rest is allowed today) and surface `case`/`match` sugar over
  `__match`
- the `.` composition **combinator** — a spaced dot (`f . g`) lexes as an infix
  `<punct>` awaiting these semantics (the `|>` pipe combinator is now specified;
  see [the pipe combinator](#the-pipe-combinator))
- **typing** (`<expr> as <ty>` on the value side; the pattern-side `as <Type>`
  is in [patterns](#patterns-and-matching)), including the full `<tyexpr>` (arrows, `__Type.of`)
- **recursion** / fixpoint combinator, and the **evaluation strategy**
  (call-by-value vs -name/-need) it depends on
- **uniqueness / references**, for which `^` is reserved (not `&`)
- value **equality** and **string representation** (open in `elly-intro.md`)