← playground

Elly spec

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:

For the broader vision (records, typing, uniqueness) see elly-intro.md. Everything outside this subset is collected under 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:

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

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:

(* 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:

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

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:

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

// 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:

(* 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  *)
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

__Int_* builtins

Arithmetic and elimination are builtins in the reserved __ namespace (see bindings, names): free names resolved from the runtime environment, referenceable but not bindable. 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).

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 
// 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).

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:

"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

__Str_* / __Sym_* builtins

Reserved __ namespace, 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. 
__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); 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>.

[]               // 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), a list value is [].

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

<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:

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

__List_* builtins

Reserved __ namespace, 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 
// 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) 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

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:

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.

{}                          // 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).

__Map_* builtins

Reserved __ namespace, 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_*; see 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).

// build { .a: 1, .b: 2 } explicitly
__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:

Both are applied by juxtaposition (see 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); Fun is the kind that matches any callable.

__Fun_* builtins

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.

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), 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.

A few words are keywords: let (the local binding form; see local binding), as (the type-narrowing pattern qualifier; see patterns), 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.

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

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

&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:

&[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). & 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.

(* 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). Two constraints hold on any binder:

The (…) binder group is the mirror of application 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:

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), 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 =:

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 lets:

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

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.

Recursion is still not directly expressible: an abstraction is anonymous and a name refers only to an enclosing binder, and let — desugaring to it — is the same. It can be recovered with a fixpoint combinator once the evaluation strategy is fixed; both are deferred.

application

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

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

(* 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:

(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 []:

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

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:

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:

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 / local binding):

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

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:

__match, the multi-clause form

__match <clauses> <val>

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

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:

// 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 equality relation it eliminates:

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 — 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).

// 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), 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:

// 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):

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): 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). 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.

__Err_* builtins

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 
// 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): 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.

deferred

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