elly_core/ast.rs
1//! The Elly AST and its s-expression dump.
2//!
3//! `to_sexp` emits a compact parenthesized form used by the parse golden
4//! tests so they read close to `docs/elly-spec.md`. Leaves own their text as
5//! [`Text`] (a cheap-clone inline/`Rc` handle), so the AST is `'static` — no
6//! longer tied to the Muon source lifetime; structure is `alloc`ated.
7//!
8//! **Patterns are first-class AST** (see `docs/done/2026-07-26_elly-patterns-native.md`):
9//! an `&`-abstraction, a `let` binding, and a `__match` clause all bind through
10//! the same [`Pattern`] node, which the evaluator interprets directly (a native
11//! matcher, not a lowering to eliminator builtins). The AST *rephrases* Muon
12//! into Elly's own syntax; it does not *compile* patterns into anything else —
13//! that is a later (VM) pass's job.
14
15use alloc::boxed::Box;
16use alloc::format;
17use alloc::rc::Rc;
18use alloc::string::{String, ToString};
19use alloc::vec::Vec;
20
21use num_bigint::BigInt;
22
23use crate::eval::{Builtin, ModuleData};
24
25/// An owned, cheap-clone text leaf — hipstr's single-threaded `Local` (`Rc`)
26/// backend: **inline** for short strings (≤ 23 bytes on 64-bit), else a shared
27/// `Rc<str>` slice, an **O(1) clone** either way. Replaces the former `&'a str`
28/// source borrow so `Expr`/`Value` are `'static` and no longer tied to the Muon
29/// source (see `docs/todo/elly-impl-expr-repr-v1.md`). A `'static` host tag is
30/// stored for free via [`Text::from_static`](hipstr::string::HipStr::from_static).
31pub type Text = hipstr::LocalHipStr<'static>;
32
33/// An Elly expression in the first subset. Strings and records are deferred
34/// (see the spec), so there is no variant for them yet.
35#[derive(Debug, Clone, PartialEq, Eq)]
36pub enum Expr {
37 /// An arbitrary-precision integer literal, parsed from the token (`0`, `-123`,
38 /// `0xCAFE`); see the *integers* section of the spec.
39 Int(BigInt),
40 /// The **unit** value, written `()` — the nullary marker in a chain (`f ()`,
41 /// a standalone `()`) and the empty-value sugar in a map (`{ .k: }`). It is
42 /// its own value, distinct from the empty list `[]` / `#[]`; `&()` is the
43 /// [pattern](Pattern::Unit) that matches it. Rendered `()`.
44 Unit,
45 /// A runtime list literal from a Muon `#`-prefixed `<brackets>` (`#[…]`), of
46 /// *any* arity: `#[]` (the empty list — a list, *not* unit), `#[e]` (a genuine
47 /// 1-list, distinct from `e`), or `#[e0, e1, …]`. Parens `(…)` never produce
48 /// this — they are grouping / argument spread at parse time (see `parse.rs`).
49 List(Vec<Expr>),
50 /// A bare name: a reference to an enclosing `&`-binding, else a free name.
51 /// Produced by the parser as the *unresolved* form; the resolution pass
52 /// (`resolve.rs`) rewrites every in-scope `Name` into a [`Expr::Local`] and
53 /// rejects the rest. Tooling that wants the raw, pre-resolution tree
54 /// (`parse_open`) keeps seeing `Name`; the evaluator only ever sees `Local`.
55 Name(Text),
56 /// A **resolved** reference: a flat de Bruijn `index` produced by the resolver
57 /// from a [`Expr::Name`]. The environment is a nameless cons list of bindings
58 /// (one cell per bound name, innermost first), and `index` counts cells to walk
59 /// from the top (0 = the most recent binding) — so the evaluator's lookup is a
60 /// pointer chase with no string compare and no per-link clone. The original
61 /// `name` is kept only for rendering, **boxed** so it does not widen `Expr` past
62 /// four words (it is read solely by `to_sexp` / `to_json`): a `Local` then
63 /// prints exactly like the `Name` it replaced (`(name foo)` / `{"name":"foo"}`),
64 /// so the goldens are unchanged.
65 Local { name: Box<Text>, index: u32 },
66 /// A `__`-builtin resolved **at parse** (see `Builtin::from_name`). `__` names
67 /// are un-bindable, so a reference like `__Int.add` never depends on the
68 /// environment; resolving it here turns each call into a direct dispatch rather
69 /// than a failing env walk plus a name match at eval. Rendered exactly like the
70 /// `Name` it replaces (`(name __Int.add)` / `{"name":"__Int.add"}`) so the
71 /// goldens are unchanged.
72 Builtin(Builtin),
73 /// A **module sibling reference**: a name that resolved not to a lexical
74 /// binding but to another item of the enclosing module (see
75 /// `docs/done/2026-08-07_elly-modules-v0.md`). Produced only by the module resolver
76 /// (`resolve::resolve_module_bodies`), never by `parse`; it is a *sink* — it
77 /// carries no module reference and is resolved at eval through the home module
78 /// carried in the environment (`EnvNode::Module`).
79 ///
80 /// `index` is the item's position in the home module's (name-sorted) item
81 /// table, assigned at resolve so eval indexes straight into it with no name
82 /// compare — the module-tier analogue of a `Local`'s de Bruijn index. `name` is
83 /// kept for rendering only (boxed to keep `Expr` at four words). Renders
84 /// `(moditem factorial)` / `{"moditem":"factorial"}`.
85 /// `depth` is how many [`Module`](crate::EnvNode::Module) terminals the walk
86 /// **skips** before the one that owns this item. A program with one module has
87 /// no nesting and every `ModItem` carries `0`; a [`recur`](Expr::Recur) inside
88 /// a module body puts a second terminal on the chain, and a reference to the
89 /// module's own item from inside the `recur` has to step over the `recur`'s.
90 /// It is the barrier-stack distance the resolver measured, not rendered (like
91 /// a `Local`'s index, it is derived addressing).
92 ModItem {
93 name: Box<Text>,
94 index: u32,
95 depth: u32,
96 },
97 /// A **recursive binding group as an expression**: `recur (a = va, b = vb) e`.
98 /// The bindings are *simultaneous* — each sees all of them, itself included —
99 /// which is what separates it from `let`, whose group is sequential and
100 /// desugars to nested [`App`](Expr::App)/[`Abs`](Expr::Abs) with no node of its
101 /// own.
102 ///
103 /// The group is a module — the whole of one, body included: the bindings are
104 /// its (name-sorted) item table, and they reach each other as
105 /// [`ModItem`](Expr::ModItem)s *through the terminal* rather than by
106 /// capturing references to each other, the edge that would cycle. The
107 /// expression the group scopes over is the [`ModuleData`'s own
108 /// body](crate::ModuleData::body), the slot a module source fills with
109 /// `__main`. Evaluating this builds the terminal over the current environment
110 /// (the cons-shaped frame) and runs that body under it; see
111 /// `docs/done/2026-08-13_elly-recur.md` and `docs/done/2026-08-14_elly-run.md`.
112 Recur(Rc<ModuleData>),
113 /// A `.`-prefixed literal (`.foo`, `.0`), stored *without* the dot — the dot
114 /// is the Muon sigil and is re-added when displayed / dumped.
115 Symbol(Text),
116 /// A string literal, **decoded** at parse from a Muon `<str>` (JSON/Muon
117 /// escapes resolved, `\uXXXX` surrogate pairs combined) into owned UTF-8. It
118 /// is self-evaluating: eval clones the handle into `Value::Str`. Rendered as
119 /// the bare quoted, re-escaped literal (`"foo"`) — the quotes already mark it
120 /// apart from `.foo` / `foo`, so no `(str …)` wrapper.
121 Str(Text),
122 /// Application: a **flattened call spine** whose element 0 is the callee and
123 /// `[1..]` the arguments. A source spine `f a b c` and a spread call `f(a, b)`
124 /// both parse into one node with a known call-site arity, so the evaluator
125 /// binds a whole call's arguments in one pass (see `apply_n` in `eval.rs`).
126 /// Always holds at least a callee and one argument (two elements); currying is
127 /// recovered by `apply_n`'s over-application loop, so a flat spine is
128 /// semantically identical to the left-nested binary applications it replaced —
129 /// which is exactly how it is re-rendered in `to_sexp` / `to_json`.
130 App(Box<[Expr]>),
131 /// Abstraction `&<pattern> body`: the one universal binding form, its *code*
132 /// (`Lambda`: the parameter patterns and the body) shared behind `Rc`. A run
133 /// of `&p0 &p1 …` is collected at parse into one multi-parameter `Lambda`
134 /// (arity `head.len()`), so applying it *matches* a whole call's arguments in
135 /// one pass. The evaluator builds a closure by cloning the `Rc<Lambda>` and
136 /// capturing the environment, rather than deep-cloning the subtree. Rendered as
137 /// nested `(abs p0 (abs p1 …))` — the curried reading the collected head stands
138 /// for — to keep the goldens stable.
139 Abs(Rc<Lambda>),
140 /// A map literal from a Muon `#`-prefixed `<braces>` (`#{ … }`): its entries as
141 /// (key-expr, value-expr) pairs, in source order. Keys stay expressions
142 /// until eval, so computed keys (`(expr)`) just evaluate like any other
143 /// expression; see the *maps* section of the spec.
144 Map(Vec<(Expr, Expr)>),
145 /// A **home-module leaf**: `Self` (the module), `#Self(…)` (construct) or
146 /// `x.Self` (read the payload), each reading the module the body it sits
147 /// in was written in (see [`HomeLeaf`]). Like a
148 /// [`ModItem`](Expr::ModItem) it is a *sink* — it carries no module reference
149 /// and finds its module through the environment's terminal at eval — and like
150 /// one it costs a leaf and no capture slot.
151 ///
152 /// `depth` is how many [`Module`](crate::EnvNode::Module) terminals to step
153 /// over before the module: a leaf names the nearest terminal *written as a
154 /// module*, so a [`recur`](Expr::Recur) between the leaf and its module is
155 /// stepped over and a method that loops internally still constructs objects of
156 /// its own type. The resolver measures it (the same barrier-stack distance a
157 /// `ModItem` carries) and rejects a leaf with no module on the stack; it is
158 /// derived addressing, so it is not rendered. See
159 /// `docs/done/2026-08-15_elly-objects-v0.md` and
160 /// `docs/done/2026-09-11_elly-v1-self.md`.
161 Home { leaf: HomeLeaf, depth: u32 },
162 /// A **block** `{ c0, c1, …, e }`, and the desugaring target of `let (…) e`:
163 /// a sequence of `Clause`s evaluated in order under one shared scope
164 /// whose bindings do not escape, the **last clause's value** the block's. The
165 /// clauses are kept represented — not folded into nested [`App`](Expr::App) /
166 /// [`Abs`](Expr::Abs) — so a later effects pass (`break`, `defer`) has the
167 /// block boundary and the clause list to attach to; this is the representation
168 /// change the `Expr::Let` experiment deferred (`docs/todo/elly-v1-blocks.md`).
169 /// Boxed as a slice so `Expr` stays four words (`tests/sizes.rs`). The parser
170 /// rejects a trailing binding ([`ParseError`](crate::ParseError)`::BlockTrailingBinding`)
171 /// and collapses the degenerate blocks, so the final clause is a
172 /// `Do` and neither `{}` (→ [`Unit`](Expr::Unit)) nor `{ e }`
173 /// (→ `e`) reaches this node.
174 Block(Box<[Clause]>),
175 /// `case <subject> { &p0 b0, ... }`: evaluates subject once and matches arms in order.
176 /// The first matching arm's body is evaluated. No matching arm raises `.no_match`.
177 ///
178 /// Unlike `__match`, arms are fixed at parse time and share the enclosing environment
179 /// (no new activation).
180 ///
181 /// Subjectless `case { ... }` is lowered to `&__arg (case __arg { ... })`.
182 Case {
183 subject: Rc<Expr>,
184 cases: Box<[(Pattern, Expr)]>,
185 },
186}
187
188/// One clause of a [block](Expr::Block): a sequential binding or a bare
189/// expression. In a block the bindings are visible to the clauses after them and
190/// to the final clause; a bare non-final clause is evaluated for its effect and
191/// its value discarded, and the final clause's value is the block's.
192#[derive(Debug, Clone, PartialEq, Eq)]
193pub enum Clause {
194 /// `<pat> = <value>` — match `value` against `pat` and bind it for the clauses
195 /// that follow. **Non-recursive**: `value` is evaluated *before* this clause's
196 /// binders enter scope, so it does not see them (the `let`-clause reading).
197 Bind(Pattern, Expr),
198 /// A bare expression: the block's value when it is the final clause, otherwise
199 /// evaluated for its effect and discarded (a `_ =` clause, `_ = io.print(…)`).
200 Do(Expr),
201}
202
203/// Which of the three [home-module leaves](Expr::Home) a reference is — the
204/// module itself (`Self`), construction (`#Self(…)`), and the payload read
205/// (`x.Self`). They share one variant because they share the whole of their
206/// machinery — one walk to the terminal, one parse clause each, no capture —
207/// and differ only in what they evaluate to once it is found.
208#[derive(Debug, Clone, Copy, PartialEq, Eq)]
209pub enum HomeLeaf {
210 /// `Self` — the home module itself, a `Value::Module`.
211 Module,
212 /// `#Self(…)` / `#Self …` — the object constructor over the home module:
213 /// the object builtin with the module already applied, so what is left
214 /// takes the payload. Always the callee of an [`App`](Expr::App) — a bare
215 /// `#Self` is refused at parse — so it renders as `(new …)`, never alone.
216 New,
217 /// `x.Self` — the payload reader over the home module, the same shape. In
218 /// *pattern* position the spelling is the [`Pattern::Unwrap`] qualifier
219 /// `Self <pat>` instead. Like [`New`](HomeLeaf::New) it is only ever an
220 /// `App` callee.
221 Value,
222}
223
224impl HomeLeaf {
225 /// The name the resolver reports a leaf by when it sits outside a module
226 /// body: every form is spelled `Self`, so the one error names the one word
227 /// (see `docs/done/2026-09-11_elly-v1-self.md`).
228 pub fn name(self) -> &'static str {
229 "Self"
230 }
231}
232// TODO: annotate expressions with source spans
233// TODO: do not hardcode `Vec`/`Box`
234
235/// The body of a [`recur`](Expr::Recur) group. It is an `Option` on
236/// [`ModuleData`] because a *module* may decline to declare one, but a group's is
237/// required by the grammar ([`ParseError::RecurMissingBody`]) — so every
238/// `Expr::Recur` has one, and the two readers that would otherwise both unwrap
239/// (`to_sexp`/`to_json` here, [`eval`](crate::eval) there) say why once.
240///
241/// [`ParseError::RecurMissingBody`]: crate::ParseError::RecurMissingBody
242pub(crate) fn recur_body(data: &ModuleData) -> &Expr {
243 data.body().expect("a recur group always has a body")
244}
245
246/// The *code* of an abstraction: the parameter patterns and the body. Shared
247/// behind `Rc` between the [`Expr::Abs`] that builds a closure and the
248/// `Value::Closure` that captures an environment over it, so a partial
249/// application is one `Rc::clone` (plus a bumped `applied` counter and an
250/// extended environment) rather than a fresh `Lambda` allocation. The **arity is
251/// `head.len()`** — collected greedily at parse from a run of `&p0 &p1 …` — and
252/// is capped at 255 (see `parse.rs`). `head` is non-empty: every abstraction
253/// binds at least one parameter.
254#[derive(Debug, Clone, PartialEq, Eq)]
255pub struct Lambda {
256 pub head: Box<[Pattern]>,
257 pub body: Expr,
258 /// How a closure over this lambda gets its environment: see [`Captures`].
259 /// Derived data, not syntax — it is not rendered by `to_sexp` / `to_json`.
260 pub captures: Captures,
261}
262
263impl Lambda {
264 /// The number of parameters this abstraction binds before its body runs.
265 pub fn arity(&self) -> usize {
266 self.head.len()
267 }
268}
269
270/// How a closure over a [`Lambda`] gets the environment its body runs in — decided
271/// per abstraction by the resolver, and the *only* thing that distinguishes the two
272/// closure representations (both are semantically identical; environments are
273/// immutable, so reading a value now or later gives the same answer).
274#[derive(Debug, Clone, PartialEq, Eq)]
275pub enum Captures {
276 /// Not yet resolved — the state the parser leaves behind. The evaluator refuses
277 /// it rather than silently reading the wrong slots (the same posture as an
278 /// unresolved [`Expr::Name`] at eval).
279 Unresolved,
280 /// **Share** the defining environment by reference: no frame, no allocation, and
281 /// the body's indices keep counting into the enclosing activation's chain.
282 ///
283 /// Chosen where a closure cannot outlive the call that creates it, so retaining
284 /// the chain retains nothing observable: the callee of a direct application
285 /// (every `let`), and a literal `&`-abstraction handed straight to a builtin that
286 /// only *applies* it — a `__match` clause, an `__Err.catch` or `__eq` branch, a
287 /// `__Int.for` / `__Map.for` / `__Map.merge` callback. Elly mints these on every
288 /// call, and making each one copy a frame is what a measured 10–28% regression
289 /// was made of (see `docs/done/2026-08-14_elly-perf-closure-capture.md`).
290 Chain,
291 /// **Capture** these free variables into a fresh frame, one [`Capture`] each,
292 /// **sorted by `outer`** (see `Capture` for why). The closure then retains only
293 /// what its body uses, and a reference into an enclosing scope is one index into
294 /// the frame (see `EnvNode::Frame` in `eval.rs`). This is the default — every
295 /// abstraction whose closure may escape. An empty plan is a *closed* lambda: it
296 /// captures nothing and allocates no frame.
297 Frame(Box<[Capture]>),
298}
299
300/// One captured free variable: **where to read it** (`outer` — a de Bruijn index in
301/// the *enclosing* activation, at the point the [`Expr::Abs`] is evaluated) and
302/// **where it goes** (`slot` — its position in the closure's frame).
303///
304/// The two are separate because the resolver fixes `slot` at a free variable's
305/// first use, while `outer` only falls out of resolving it in the enclosing scopes;
306/// re-ordering the frame to match would mean renumbering references already emitted
307/// into the body. Instead the resolver sorts the *plan* by `outer`, so the
308/// evaluator fills the whole frame in **one** walk of the defining environment
309/// (ascending indices, never restarting) and writes each value to its `slot`.
310#[derive(Debug, Clone, Copy, PartialEq, Eq)]
311pub struct Capture {
312 pub outer: u32,
313 pub slot: u32,
314}
315
316/// A **pattern**: the left-hand side of any binding (`&<pat> …`, `let (<pat> =
317/// …)`, a `__match` clause). Matched against a value by the evaluator's native
318/// matcher (`match_pattern` in `eval.rs`), which either extends the environment
319/// or refutes. `Bind`/`Discard` are irrefutable; every other shape may refute.
320#[derive(Debug, Clone, PartialEq, Eq)]
321pub enum Pattern {
322 /// `_` — matches anything, binds nothing.
323 Discard,
324 /// `name` — binds the subject to `name`. The matcher conses one cell carrying
325 /// the subject onto the environment; the name itself is not stored at runtime
326 /// (references to it were resolved to a de Bruijn index).
327 Bind(Text),
328 /// `name = <pat>` — binds the subject to `name`, then matches `<pat>` against
329 /// the same subject.
330 At(Text, Box<Pattern>),
331 /// `= <expr>` (and its `.sym` sugar) — matches iff the subject equals the
332 /// value of `<expr>`; binds nothing. Evaluating `<expr>` may raise a real
333 /// error, which propagates (it is not a refutation).
334 Equal(Expr),
335 /// `< <expr>` — matches iff the subject is (strictly) ordered before the value
336 /// of `<expr>`; binds nothing. Ordering is defined only within a comparable
337 /// kind (`Int` for now, later `Str`), so a subject/bound that are not both of
338 /// one such kind refute with `.not_int` (a refutation, not a host raise).
339 Less(Expr),
340 /// `> <expr>` — the mirror of [`Less`](Pattern::Less): matches iff the subject
341 /// is ordered after the value of `<expr>`.
342 Greater(Expr),
343 /// `<pat> as <Proto>` / `(as <Proto>) <pat>` — matches iff the subject's
344 /// prototype is `<Proto>`, then matches `<pat>` against the (narrowed)
345 /// subject. See [`ProtoRef`] for the two forms the prototype takes.
346 Type(ProtoRef, Box<Pattern>),
347 /// `Self <pat>` — matches iff the subject is an **object of the home
348 /// module** and its payload matches `<pat>`, binding what the inner pattern
349 /// binds. It is the pattern side of the [`payload read`](HomeLeaf::Value),
350 /// and the prototype check is implicit for the same reason the leaf's is:
351 /// unwrapping a foreign object has no sound reading.
352 ///
353 /// It holds no reference — the module is implicit, exactly as it is for
354 /// `#Self` — so the pattern grammar stays closed. `depth` is the leaf's, and
355 /// the matcher walks the environment to that terminal and compares the
356 /// prototype by pointer before descending.
357 Unwrap { depth: u32, inner: Box<Pattern> },
358 /// `(p1 | p2)` — try the left arm, on refutation try the right. Both arms bind
359 /// the same set of names (checked at parse time). **Committed**: once an arm's
360 /// pattern matches, a later failure does not backtrack into the other arm.
361 Or(Box<Pattern>, Box<Pattern>),
362 /// `&()` — matches the [unit](Expr::Unit) value and nothing else, binding
363 /// nothing. Distinct from the empty list pattern `&[]` / `&#[]`, which
364 /// matches the empty list.
365 Unit,
366 /// `[p0, ...]` list pattern. `rest` matches the remainder of the list:
367 /// `None` for exact arity, `Some(Discard)` (`...`) for minimum arity,
368 /// and `Some(Bind(name))` (`...name`) to bind the remainder.
369 List {
370 elems: Vec<Pattern>,
371 rest: Option<Box<Pattern>>,
372 },
373 /// `{ k0: p0, ... }` map pattern. `rest` matches the remainder map as in [`Pattern::List`].
374 Map {
375 entries: Vec<(MapKey, Pattern)>,
376 rest: Option<Box<Pattern>>,
377 },
378 /// `<pat> when (<cond>)` guarded pattern. Matches `inner`, then the guard.
379 /// Plain guards (`None`) must be `Bool` and refute on `__false`.
380 /// Pattern guards (`Some(gpat)`) match `gpat` against the condition's value.
381 /// Guards can nest and their bindings are visible to the body.
382 When {
383 inner: Box<Pattern>,
384 when: (Option<Box<Pattern>>, Expr),
385 },
386}
387
388/// A map-pattern entry's key. A **lookup** key (`.sym`, bare `sym`, `(= expr)`)
389/// names a concrete key to probe. A **capture** key (a binder pattern in key
390/// position, e.g. `(k)` / `(_)`) instead *peels* the smallest remaining entry and
391/// matches its key against the pattern — the map analogue of `[a, ...rest]`.
392#[derive(Debug, Clone, PartialEq, Eq)]
393pub enum MapKey {
394 Lookup(Expr),
395 Capture(Box<Pattern>),
396}
397
398/// The prototype an `as <Proto>` pattern narrows to. One rule covers both forms —
399/// the subject matches iff its prototype *is* the named module — and they differ
400/// only in how much of the work is left to run time.
401#[derive(Debug, Clone, PartialEq, Eq)]
402pub enum ProtoRef {
403 /// The **compiled fast form**: a reference the resolver recognized as the
404 /// builtin module that is some value kind's prototype, so the check is the
405 /// discriminant test [`TyKind`] always was rather than an eval plus a pointer
406 /// compare. `as Int` takes this path, alias or `__`-spelling alike.
407 Kind(TyKind),
408 /// Any other prototype, named by an **atom** — a module item, a local, a
409 /// frame slot, or `Self`. Resolved like an [`Equal`](Pattern::Equal)
410 /// comparand, evaluated at match time, and required to be a module value.
411 Ref(Expr),
412}
413
414impl ProtoRef {
415 /// Render the reference: a kind by its bare name (`Int`), so the existing
416 /// goldens are unchanged, and anything else as the expression it is.
417 fn write_sexp(&self, out: &mut String) {
418 match self {
419 ProtoRef::Kind(ty) => out.push_str(ty.name()),
420 ProtoRef::Ref(expr) => expr.write_sexp(out),
421 }
422 }
423
424 fn write_json(&self, out: &mut String) {
425 match self {
426 ProtoRef::Kind(ty) => json_str(ty.name(), out),
427 ProtoRef::Ref(expr) => expr.write_json(out),
428 }
429 }
430}
431
432/// The value kinds whose prototype is a **builtin module**, so that `as <Proto>`
433/// against it compiles to a discriminant test (see [`ProtoRef::Kind`]).
434#[derive(Debug, Clone, Copy, PartialEq, Eq)]
435pub enum TyKind {
436 Int,
437 Sym,
438 Str,
439 List,
440 Map,
441 Fun,
442 /// A module value, whose prototype is `__Mod`. It has no `as Mod` history —
443 /// the kind set was closed before modules existed — and is here because
444 /// `__Mod` is a builtin module like the rest, so the fast form covers it.
445 Mod,
446 /// The [unit](crate::Value::Unit) value, whose prototype is `__Unit`.
447 Unit,
448 /// A [boolean](crate::Value::Iota) — an iota of `__Bool`. Like `Mod` it is a
449 /// builtin-module prototype, so `as Bool` takes the fast discriminant form.
450 Bool,
451}
452
453impl TyKind {
454 /// The spelling used in the `as <Proto>` surface and the dumps.
455 pub fn name(self) -> &'static str {
456 match self {
457 TyKind::Int => "Int",
458 TyKind::Sym => "Sym",
459 TyKind::Str => "Str",
460 TyKind::List => "List",
461 TyKind::Map => "Map",
462 TyKind::Fun => "Fun",
463 TyKind::Mod => "Mod",
464 TyKind::Unit => "Unit",
465 TyKind::Bool => "Bool",
466 }
467 }
468}
469
470impl Expr {
471 /// Serialize to a compact s-expression, e.g. `(app (name f) (name x))`.
472 pub fn to_sexp(&self) -> String {
473 let mut out = String::new();
474 self.write_sexp(&mut out);
475 out
476 }
477
478 // TODO: replace with impl de::Deserialize, impl ser::Serialize
479 /// Serialize to compact, tagged JSON, e.g.
480 /// `{"app":[{"name":"f"},{"name":"x"}]}`. Parallels `muon::Seq::to_json`;
481 /// used by the `elly-wasm` playground to render the AST as a tree.
482 pub fn to_json(&self) -> String {
483 let mut out = String::new();
484 self.write_json(&mut out);
485 out
486 }
487
488 fn write_json(&self, out: &mut String) {
489 match self {
490 Expr::Int(n) => {
491 // f64 (JSON's only number type) represents every integer in
492 // [-2^53, 2^53] exactly. Within that range emit a bare number so
493 // the playground shows it as-is; outside it, fall back to a
494 // decimal *string* tagged `Int` to avoid precision loss.
495 if fits_f64_exactly(n) {
496 out.push_str(&n.to_string());
497 } else {
498 out.push_str("{\"Int\":");
499 json_str(&n.to_string(), out);
500 out.push('}');
501 }
502 }
503 // A `Name` (unresolved) and a `Local` (resolved) both render by name.
504 Expr::Name(n) => {
505 out.push_str("{\"name\":");
506 json_str(n, out);
507 out.push('}');
508 }
509 Expr::Local { name, .. } => {
510 out.push_str("{\"name\":");
511 json_str(name.as_str(), out);
512 out.push('}');
513 }
514 // A parse-resolved builtin renders as the `Name` it stands in for.
515 Expr::Builtin(op) => {
516 out.push_str("{\"name\":");
517 json_str(op.name(), out);
518 out.push('}');
519 }
520 // A home-module leaf renders as the form it is — `{"self":true}` for
521 // the module, `{"new":…}` / `{"value":…}` for the two always-applied
522 // callee leaves (an applied one is folded by the spine writers
523 // below) — since the depth beside them is derived addressing, like
524 // a `Local`'s index, and is not rendered.
525 Expr::Home { leaf, .. } => match leaf {
526 HomeLeaf::Module => out.push_str("{\"self\":true}"),
527 HomeLeaf::New => out.push_str("{\"new\":true}"),
528 HomeLeaf::Value => out.push_str("{\"value\":true}"),
529 },
530 Expr::ModItem { name, .. } => {
531 out.push_str("{\"moditem\":");
532 json_str(name.as_str(), out);
533 out.push('}');
534 }
535 Expr::Recur(data) => {
536 out.push_str("{\"recur\":[");
537 for (i, (name, body)) in data.items().iter().enumerate() {
538 if i > 0 {
539 out.push(',');
540 }
541 out.push('[');
542 json_str(name.as_str(), out);
543 out.push(',');
544 body.write_json(out);
545 out.push(']');
546 }
547 out.push_str("],\"body\":");
548 recur_body(data).write_json(out);
549 out.push('}');
550 }
551 Expr::Symbol(s) => {
552 let mut dotted = String::from(".");
553 dotted.push_str(s);
554 out.push_str("{\"sym\":");
555 json_str(&dotted, out);
556 out.push('}');
557 }
558 Expr::Str(s) => {
559 out.push_str("{\"str\":");
560 json_str(s, out);
561 out.push('}');
562 }
563 // Render the call spine flat, preserving the arity the AST stores.
564 Expr::App(items) => write_app_json(items, out),
565 // Re-render the collected head as nested single-parameter abstractions.
566 Expr::Abs(code) => write_abs_json(&code.head, &code.body, out),
567 Expr::Unit => out.push_str("{\"unit\":true}"),
568 Expr::List(elems) => {
569 out.push_str("{\"list\":[");
570 for (i, e) in elems.iter().enumerate() {
571 if i > 0 {
572 out.push(',');
573 }
574 e.write_json(out);
575 }
576 out.push_str("]}");
577 }
578 Expr::Map(entries) => {
579 out.push_str("{\"map\":[");
580 for (i, (k, v)) in entries.iter().enumerate() {
581 if i > 0 {
582 out.push(',');
583 }
584 out.push('[');
585 k.write_json(out);
586 out.push(',');
587 v.write_json(out);
588 out.push(']');
589 }
590 out.push_str("]}");
591 }
592 // `{"block":[<clause>…]}` — a bind clause is `{"bind":{"pat":…,"value":…}}`,
593 // a bare clause the expression itself, in source (evaluation) order.
594 Expr::Block(clauses) => {
595 out.push_str("{\"block\":[");
596 for (i, c) in clauses.iter().enumerate() {
597 if i > 0 {
598 out.push(',');
599 }
600 match c {
601 Clause::Bind(pat, value) => {
602 out.push_str("{\"bind\":{\"pat\":");
603 pat.write_json(out);
604 out.push_str(",\"value\":");
605 value.write_json(out);
606 out.push_str("}}");
607 }
608 Clause::Do(value) => value.write_json(out),
609 }
610 }
611 out.push_str("]}");
612 }
613 // `{"case":{"subject":…,"arms":[{"pat":…,"body":…}, …]}}`.
614 Expr::Case { subject, cases } => {
615 out.push_str("{\"case\":{\"subject\":");
616 subject.write_json(out);
617 out.push_str(",\"arms\":[");
618 for (i, (pat, body)) in cases.iter().enumerate() {
619 if i > 0 {
620 out.push(',');
621 }
622 out.push_str("{\"pat\":");
623 pat.write_json(out);
624 out.push_str(",\"body\":");
625 body.write_json(out);
626 out.push('}');
627 }
628 out.push_str("]}}");
629 }
630 }
631 }
632
633 fn write_sexp(&self, out: &mut String) {
634 match self {
635 Expr::Int(n) => {
636 out.push_str("(int ");
637 out.push_str(&n.to_string());
638 out.push(')');
639 }
640 // A `Name` (unresolved) and a `Local` (resolved) both render by name.
641 Expr::Name(n) => {
642 out.push_str("(name ");
643 out.push_str(n);
644 out.push(')');
645 }
646 Expr::Local { name, .. } => {
647 out.push_str("(name ");
648 out.push_str(name.as_str());
649 out.push(')');
650 }
651 // A parse-resolved builtin renders as the `Name` it stands in for.
652 Expr::Builtin(op) => {
653 out.push_str("(name ");
654 out.push_str(op.name());
655 out.push(')');
656 }
657 // A home-module leaf renders as the form it is — `(self)` for the
658 // module, `(new)` / `(value)` for the two always-applied callee
659 // leaves (an applied one is folded into `(new …)` / `(value …)` by
660 // the spine writers below, so these bare spellings are the
661 // defensive arm) — since the depth beside it is derived addressing,
662 // like a `Local`'s index, and is not rendered.
663 Expr::Home { leaf, .. } => match leaf {
664 HomeLeaf::Module => out.push_str("(self)"),
665 HomeLeaf::New => out.push_str("(new)"),
666 HomeLeaf::Value => out.push_str("(value)"),
667 },
668 Expr::ModItem { name, .. } => {
669 out.push_str("(moditem ");
670 out.push_str(name.as_str());
671 out.push(')');
672 }
673 // `(recur (bind a …) (bind b …) <body>)` — the bindings in the table's
674 // sorted order, then the body, so the group reads as one form.
675 Expr::Recur(data) => {
676 out.push_str("(recur");
677 for (name, body) in data.items() {
678 out.push_str(" (bind ");
679 out.push_str(name.as_str());
680 out.push(' ');
681 body.write_sexp(out);
682 out.push(')');
683 }
684 out.push(' ');
685 recur_body(data).write_sexp(out);
686 out.push(')');
687 }
688 Expr::Symbol(s) => {
689 out.push_str("(sym .");
690 out.push_str(s);
691 out.push(')');
692 }
693 // A string leaf is the bare quoted, re-escaped literal — the quotes
694 // already set it apart from `(sym .foo)` / `(name foo)`, so no wrapper.
695 Expr::Str(s) => json_str(s, out),
696 // Render the call spine flat, preserving the arity the AST stores.
697 Expr::App(items) => write_app_sexp(items, out),
698 // Re-render the collected head as nested single-parameter abstractions.
699 Expr::Abs(code) => write_abs_sexp(&code.head, &code.body, out),
700 Expr::Unit => out.push_str("(unit)"),
701 Expr::List(elems) => {
702 out.push_str("(list");
703 for e in elems {
704 out.push(' ');
705 e.write_sexp(out);
706 }
707 out.push(')');
708 }
709 Expr::Map(entries) => {
710 out.push_str("(map");
711 for (k, v) in entries {
712 out.push_str(" (entry ");
713 k.write_sexp(out);
714 out.push(' ');
715 v.write_sexp(out);
716 out.push(')');
717 }
718 out.push(')');
719 }
720 // `(block (bind <pat> <value>) … <value>)` — the clauses in evaluation
721 // order, a binding wrapped `(bind …)` and a bare clause bare, mirroring
722 // how `recur` renders its table then its body.
723 Expr::Block(clauses) => {
724 out.push_str("(block");
725 for c in clauses.iter() {
726 out.push(' ');
727 match c {
728 Clause::Bind(pat, value) => {
729 out.push_str("(bind ");
730 pat.write_sexp(out);
731 out.push(' ');
732 value.write_sexp(out);
733 out.push(')');
734 }
735 Clause::Do(value) => value.write_sexp(out),
736 }
737 }
738 out.push(')');
739 }
740 // `(case <subject> (arm <pat> <body>) …)` — the subject then each arm
741 // as a `(pattern, body)` pair. A subjectless `case { … }` never reaches
742 // here as a `Case`: it is lowered to `(abs __arg (case (name __arg) …))`.
743 Expr::Case { subject, cases } => {
744 out.push_str("(case ");
745 subject.write_sexp(out);
746 for (pat, body) in cases.iter() {
747 out.push_str(" (arm ");
748 pat.write_sexp(out);
749 out.push(' ');
750 body.write_sexp(out);
751 out.push(')');
752 }
753 out.push(')');
754 }
755 }
756 }
757}
758
759/// Render a flat call spine `[callee, a0, a1, …]` (≥ 2 elements) as the flat
760/// s-expression `(app callee a0 a1)` — the arity is shown as the AST stores it,
761/// not re-curried into left-nested binary `(app (app callee a0) a1)` forms.
762///
763/// A construction / payload-read spine — `#Self(…)`, `x.Self` — renders as the
764/// form it is written as, `(new a0)` / `(value a0)`, rather than `(app (new) a0)`:
765/// the leaf alone is never a value, so the application *is* the form.
766fn write_app_sexp(items: &[Expr], out: &mut String) {
767 let (open, body) = match &items[0] {
768 Expr::Home {
769 leaf: HomeLeaf::New,
770 ..
771 } => ("(new", &items[1..]),
772 Expr::Home {
773 leaf: HomeLeaf::Value,
774 ..
775 } => ("(value", &items[1..]),
776 _ => ("(app", items),
777 };
778 out.push_str(open);
779 for it in body {
780 out.push(' ');
781 it.write_sexp(out);
782 }
783 out.push(')');
784}
785
786/// Render a collected head `[p0, p1, …]` (non-empty) over `body` as the nested
787/// `(abs p0 (abs p1 body))` it stands for.
788fn write_abs_sexp(head: &[Pattern], body: &Expr, out: &mut String) {
789 out.push_str("(abs ");
790 head[0].write_sexp(out);
791 out.push(' ');
792 if head.len() == 1 {
793 body.write_sexp(out);
794 } else {
795 write_abs_sexp(&head[1..], body, out);
796 }
797 out.push(')');
798}
799
800/// The tagged-JSON twin of [`write_app_sexp`]: `{"app":[callee, a0, a1, …]}`, the
801/// whole spine flat so the AST view shows the call's arity as stored — with the
802/// same two special cases, `{"new":[a0, …]}` / `{"value":[a0, …]}` for a
803/// construction / payload-read spine.
804fn write_app_json(items: &[Expr], out: &mut String) {
805 let (tag, body) = match &items[0] {
806 Expr::Home {
807 leaf: HomeLeaf::New,
808 ..
809 } => ("new", &items[1..]),
810 Expr::Home {
811 leaf: HomeLeaf::Value,
812 ..
813 } => ("value", &items[1..]),
814 _ => ("app", items),
815 };
816 out.push_str("{\"");
817 out.push_str(tag);
818 out.push_str("\":[");
819 for (i, it) in body.iter().enumerate() {
820 if i > 0 {
821 out.push(',');
822 }
823 it.write_json(out);
824 }
825 out.push_str("]}");
826}
827
828/// The tagged-JSON twin of [`write_abs_sexp`]: `{"abs":{"param":…,"body":…}}` nested.
829fn write_abs_json(head: &[Pattern], body: &Expr, out: &mut String) {
830 out.push_str("{\"abs\":{\"param\":");
831 head[0].write_json(out);
832 out.push_str(",\"body\":");
833 if head.len() == 1 {
834 body.write_json(out);
835 } else {
836 write_abs_json(&head[1..], body, out);
837 }
838 out.push_str("}}");
839}
840
841impl Pattern {
842 /// Serialize a pattern to the same compact s-expression family as `Expr`.
843 /// A bare `Bind`/`Discard` renders as just its name (`a`, `_`) so the common
844 /// `&x` reads `(abs x …)`; structured patterns are tagged forms
845 /// (`(list a ...rest)`, `(at n <p>)`, `(as Int <p>)`, `(eq <expr>)`, …).
846 fn write_sexp(&self, out: &mut String) {
847 match self {
848 Pattern::Discard => out.push('_'),
849 Pattern::Unit => out.push_str("(unit)"),
850 Pattern::Bind(name) => out.push_str(name),
851 Pattern::At(name, inner) => {
852 out.push_str("(at ");
853 out.push_str(name);
854 out.push(' ');
855 inner.write_sexp(out);
856 out.push(')');
857 }
858 Pattern::Equal(expr) => {
859 out.push_str("(eq ");
860 expr.write_sexp(out);
861 out.push(')');
862 }
863 Pattern::Less(expr) => {
864 out.push_str("(lt ");
865 expr.write_sexp(out);
866 out.push(')');
867 }
868 Pattern::Greater(expr) => {
869 out.push_str("(gt ");
870 expr.write_sexp(out);
871 out.push(')');
872 }
873 Pattern::Type(proto, inner) => {
874 out.push_str("(as ");
875 proto.write_sexp(out);
876 out.push(' ');
877 inner.write_sexp(out);
878 out.push(')');
879 }
880 Pattern::Unwrap { inner, .. } => {
881 out.push_str("(unwrap ");
882 inner.write_sexp(out);
883 out.push(')');
884 }
885 Pattern::Or(left, right) => {
886 out.push_str("(or ");
887 left.write_sexp(out);
888 out.push(' ');
889 right.write_sexp(out);
890 out.push(')');
891 }
892 Pattern::List { elems, rest } => {
893 out.push_str("(list");
894 for e in elems {
895 out.push(' ');
896 e.write_sexp(out);
897 }
898 write_rest_sexp(rest, out);
899 out.push(')');
900 }
901 Pattern::Map { entries, rest } => {
902 out.push_str("(map");
903 for (key, vpat) in entries {
904 out.push_str(" (entry ");
905 key.write_sexp(out);
906 out.push(' ');
907 vpat.write_sexp(out);
908 out.push(')');
909 }
910 write_rest_sexp(rest, out);
911 out.push(')');
912 }
913 // `(when <inner> <cond>)` for a plain guard, `(when <inner> (bind
914 // <gpat> <cond>))` for a pattern guard — the guard reading `(bind …)`
915 // the same way a block binding does.
916 Pattern::When {
917 inner,
918 when: (guard, cond),
919 } => {
920 out.push_str("(when ");
921 inner.write_sexp(out);
922 out.push(' ');
923 match guard {
924 None => cond.write_sexp(out),
925 Some(gpat) => {
926 out.push_str("(bind ");
927 gpat.write_sexp(out);
928 out.push(' ');
929 cond.write_sexp(out);
930 out.push(')');
931 }
932 }
933 out.push(')');
934 }
935 }
936 }
937
938 fn write_json(&self, out: &mut String) {
939 match self {
940 Pattern::Discard => out.push_str("{\"discard\":true}"),
941 Pattern::Unit => out.push_str("{\"unit\":true}"),
942 Pattern::Bind(name) => {
943 out.push_str("{\"bind\":");
944 json_str(name, out);
945 out.push('}');
946 }
947 Pattern::At(name, inner) => {
948 out.push_str("{\"at\":[");
949 json_str(name, out);
950 out.push(',');
951 inner.write_json(out);
952 out.push_str("]}");
953 }
954 Pattern::Equal(expr) => {
955 out.push_str("{\"eq\":");
956 expr.write_json(out);
957 out.push('}');
958 }
959 Pattern::Less(expr) => {
960 out.push_str("{\"lt\":");
961 expr.write_json(out);
962 out.push('}');
963 }
964 Pattern::Greater(expr) => {
965 out.push_str("{\"gt\":");
966 expr.write_json(out);
967 out.push('}');
968 }
969 Pattern::Type(proto, inner) => {
970 out.push_str("{\"as\":[");
971 proto.write_json(out);
972 out.push(',');
973 inner.write_json(out);
974 out.push_str("]}");
975 }
976 Pattern::Unwrap { inner, .. } => {
977 out.push_str("{\"unwrap\":");
978 inner.write_json(out);
979 out.push('}');
980 }
981 Pattern::Or(left, right) => {
982 out.push_str("{\"or\":[");
983 left.write_json(out);
984 out.push(',');
985 right.write_json(out);
986 out.push_str("]}");
987 }
988 Pattern::List { elems, rest } => {
989 out.push_str("{\"listpat\":{\"elems\":[");
990 for (i, e) in elems.iter().enumerate() {
991 if i > 0 {
992 out.push(',');
993 }
994 e.write_json(out);
995 }
996 out.push_str("],\"rest\":");
997 write_rest_json(rest, out);
998 out.push_str("}}");
999 }
1000 Pattern::Map { entries, rest } => {
1001 out.push_str("{\"mappat\":{\"entries\":[");
1002 for (i, (key, vpat)) in entries.iter().enumerate() {
1003 if i > 0 {
1004 out.push(',');
1005 }
1006 out.push('[');
1007 key.write_json(out);
1008 out.push(',');
1009 vpat.write_json(out);
1010 out.push(']');
1011 }
1012 out.push_str("],\"rest\":");
1013 write_rest_json(rest, out);
1014 out.push_str("}}");
1015 }
1016 Pattern::When {
1017 inner,
1018 when: (guard, cond),
1019 } => {
1020 out.push_str("{\"when\":{\"inner\":");
1021 inner.write_json(out);
1022 out.push_str(",\"guard\":");
1023 match guard {
1024 None => out.push_str("null"),
1025 Some(gpat) => gpat.write_json(out),
1026 }
1027 out.push_str(",\"cond\":");
1028 cond.write_json(out);
1029 out.push_str("}}");
1030 }
1031 }
1032 }
1033}
1034
1035/// Renders the trailing rest as `...` followed by the pattern (if not `Discard`).
1036fn write_rest_sexp(rest: &Option<Box<Pattern>>, out: &mut String) {
1037 if let Some(p) = rest {
1038 out.push_str(" ...");
1039 if !matches!(**p, Pattern::Discard) {
1040 p.write_sexp(out);
1041 }
1042 }
1043}
1044
1045/// Renders `null` for closed patterns, otherwise the rest pattern's JSON.
1046fn write_rest_json(rest: &Option<Box<Pattern>>, out: &mut String) {
1047 match rest {
1048 None => out.push_str("null"),
1049 Some(p) => p.write_json(out),
1050 }
1051}
1052
1053impl MapKey {
1054 fn write_sexp(&self, out: &mut String) {
1055 match self {
1056 // A lookup key is a plain expression (`.a`, a computed `(name k)`).
1057 MapKey::Lookup(expr) => expr.write_sexp(out),
1058 // A capture key wraps a pattern that matches the peeled key.
1059 MapKey::Capture(kpat) => {
1060 out.push_str("(capture ");
1061 kpat.write_sexp(out);
1062 out.push(')');
1063 }
1064 }
1065 }
1066
1067 fn write_json(&self, out: &mut String) {
1068 match self {
1069 MapKey::Lookup(expr) => {
1070 out.push_str("{\"lookup\":");
1071 expr.write_json(out);
1072 out.push('}');
1073 }
1074 MapKey::Capture(kpat) => {
1075 out.push_str("{\"capture\":");
1076 kpat.write_json(out);
1077 out.push('}');
1078 }
1079 }
1080 }
1081}
1082
1083/// Whether `n` is exactly representable as an `f64`: every integer in
1084/// `[-2^53, 2^53]` is (2^53 is the largest magnitude with no representation gap).
1085fn fits_f64_exactly(n: &BigInt) -> bool {
1086 const LIMIT: i64 = 1 << 53; // 2^53 == 9_007_199_254_740_992
1087 *n >= BigInt::from(-LIMIT) && *n <= BigInt::from(LIMIT)
1088}
1089
1090/// Write `s` as a JSON string literal (quoted and escaped). Shared with `eval.rs`
1091/// so a `Value::Str`'s display re-escapes identically to an `Expr::Str`'s dumps.
1092pub(crate) fn json_str(s: &str, out: &mut String) {
1093 out.push('"');
1094 for ch in s.chars() {
1095 match ch {
1096 '"' => out.push_str("\\\""),
1097 '\\' => out.push_str("\\\\"),
1098 '\n' => out.push_str("\\n"),
1099 '\r' => out.push_str("\\r"),
1100 '\t' => out.push_str("\\t"),
1101 c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
1102 c => out.push(c),
1103 }
1104 }
1105 out.push('"');
1106}