narju/eval/
staging.rs

1//! Pink bridge layer: Exp ↔ Val cons-list conversion and the `trans` pass.
2//!
3//! Three passes connect expression trees to source-as-data:
4//!
5//! - `trans` is base.scm's `trans`: it rewrites an s-expression value
6//!   into the *nameless* source encoding — symbols become `(var n)`
7//!   lists by position in a name environment, binders lose their names
8//!   — leaving everything else as tagged lists.
9//! - `val_cons_to_exp` finishes what `trans` starts, converting the
10//!   nameless encoding into an actual [`Exp`] tree the machine can run.
11//! - `exp_to_val_cons` goes the other way, rendering an [`Exp`] back
12//!   into the nameless list encoding; `trans` uses it to splice
13//!   already-compiled code (a `(name . code)` env entry) into its
14//!   output.
15//!
16//! All three are iterative (explicit heap work stacks): arbitrarily
17//! deep Pink source trees cannot overflow the native stack.
18
19use smol_str::SmolStr;
20
21use crate::core::{rc_exp, tup, Exp, RcExp, Val};
22use crate::error::NarjuError;
23
24// ── exp_to_val_cons ───────────────────────────────────────────────────────────
25
26/// Build a proper cons-list from a slice of values.
27pub(super) fn mk_list(items: &[Val]) -> Val {
28    items.iter().cloned().rev().fold(Val::Nil, |acc, v| tup(v, acc))
29}
30
31/// Frame variants for the iterative `exp_to_val_cons` worklist.
32/// Mirrors `VcFrame` (used by `val_cons_to_exp`) but goes the other
33/// direction: borrowed `&Exp` children get visited later, completed
34/// `Val` children get folded into the parent's cons-list.
35///
36/// `tag: Option<SmolStr>` is `None` only for `Exp::App`, which is the
37/// one binary form that emits an untagged 2-element list (just `(f a)`)
38/// rather than a 3-element tagged list (`(tag a b)`).
39enum EvFrame<'a> {
40    /// Waiting for the sole child of a unary form.
41    Unary {
42        /// Head symbol of the emitted list.
43        tag: SmolStr,
44    },
45    /// Waiting for the first child of a binary form.
46    Binary1 {
47        /// Head symbol; `None` for `App`'s untagged 2-element list.
48        tag: Option<SmolStr>,
49        /// Child still to visit.
50        second: &'a Exp,
51    },
52    /// First child done; waiting for the second.
53    Binary2 {
54        /// Head symbol; `None` for `App`'s untagged 2-element list.
55        tag: Option<SmolStr>,
56        /// Completed first child.
57        first: Val,
58    },
59    /// Waiting for the first child of a ternary form (`if`).
60    Ternary1 {
61        /// Head symbol of the emitted list.
62        tag: SmolStr,
63        /// Second child still to visit.
64        second: &'a Exp,
65        /// Third child still to visit.
66        third: &'a Exp,
67    },
68    /// First child done; waiting for the second.
69    Ternary2 {
70        /// Head symbol of the emitted list.
71        tag: SmolStr,
72        /// Completed first child.
73        first: Val,
74        /// Third child still to visit.
75        third: &'a Exp,
76    },
77    /// Two children done; waiting for the third.
78    Ternary3 {
79        /// Head symbol of the emitted list.
80        tag: SmolStr,
81        /// Completed first child.
82        first: Val,
83        /// Completed second child.
84        second: Val,
85    },
86}
87
88/// Render an [`Exp`] tree into the nameless source encoding: tagged
89/// cons-lists with `(var n)` for variables. The inverse (up to the
90/// unrepresentable variants) of [`val_cons_to_exp`].
91pub(super) fn exp_to_val_cons<'a>(root: &'a Exp) -> Val {
92    let mut todo:    Vec<&'a Exp>     = vec![root];
93    let mut frames:  Vec<EvFrame<'a>> = Vec::new();
94    let mut results: Vec<Val>         = Vec::new();
95
96    while let Some(cur) = todo.pop() {
97        // ── Convert the next Exp ──────────────────────────────────────────
98        let before = results.len();
99
100        match cur {
101            // Leaves: produce Val directly.
102            Exp::Nil    => results.push(Val::Nil),
103            Exp::Lit(n) => results.push(Val::Cst(*n)),
104            Exp::Sym(s) => results.push(Val::Sym(s.clone())),
105            Exp::Var(n) => results.push(
106                mk_list(&[Val::Sym("var".into()), Val::Cst(*n as i64)])
107            ),
108
109            // Unary: 2-element tagged list. Push frame, push child to visit.
110            Exp::Lam(b)    => { frames.push(EvFrame::Unary { tag: "lambda".into()  }); todo.push(b.as_ref()); }
111            Exp::Car(e)    => { frames.push(EvFrame::Unary { tag: "car".into()     }); todo.push(e.as_ref()); }
112            Exp::Cdr(e)    => { frames.push(EvFrame::Unary { tag: "cdr".into()     }); todo.push(e.as_ref()); }
113            Exp::IsNum(e)  => { frames.push(EvFrame::Unary { tag: "number?".into() }); todo.push(e.as_ref()); }
114            Exp::IsSym(e)  => { frames.push(EvFrame::Unary { tag: "symbol?".into() }); todo.push(e.as_ref()); }
115            Exp::IsNil(e)  => { frames.push(EvFrame::Unary { tag: "null?".into()   }); todo.push(e.as_ref()); }
116            Exp::IsPair(e) => { frames.push(EvFrame::Unary { tag: "pair?".into()   }); todo.push(e.as_ref()); }
117            Exp::Lift(e)   => { frames.push(EvFrame::Unary { tag: "lift".into()    }); todo.push(e.as_ref()); }
118            Exp::CellNew(e)  => { frames.push(EvFrame::Unary { tag: "cell-new".into()  }); todo.push(e.as_ref()); }
119            Exp::CellRead(e) => { frames.push(EvFrame::Unary { tag: "cell-read".into() }); todo.push(e.as_ref()); }
120            Exp::Throw(e)    => { frames.push(EvFrame::Unary { tag: "throw".into()     }); todo.push(e.as_ref()); }
121
122            // Binary: 3-element tagged list (or 2-element untagged for App).
123            // Push frame waiting for first child, then push first child to visit.
124            Exp::Let(a, b)     => { frames.push(EvFrame::Binary1 { tag: Some("let".into()),     second: b.as_ref() }); todo.push(a.as_ref()); }
125            Exp::App(f, a)     => { frames.push(EvFrame::Binary1 { tag: None,                   second: a.as_ref() }); todo.push(f.as_ref()); }
126            Exp::Cons(a, b)    => { frames.push(EvFrame::Binary1 { tag: Some("cons".into()),    second: b.as_ref() }); todo.push(a.as_ref()); }
127            Exp::IsCode(a, b)  => { frames.push(EvFrame::Binary1 { tag: Some("code?".into()),   second: b.as_ref() }); todo.push(a.as_ref()); }
128            Exp::Plus(a, b)    => { frames.push(EvFrame::Binary1 { tag: Some("+".into()),       second: b.as_ref() }); todo.push(a.as_ref()); }
129            Exp::Minus(a, b)   => { frames.push(EvFrame::Binary1 { tag: Some("-".into()),       second: b.as_ref() }); todo.push(a.as_ref()); }
130            Exp::Times(a, b)   => { frames.push(EvFrame::Binary1 { tag: Some("*".into()),       second: b.as_ref() }); todo.push(a.as_ref()); }
131            Exp::Eq(a, b)      => { frames.push(EvFrame::Binary1 { tag: Some("eq?".into()),     second: b.as_ref() }); todo.push(a.as_ref()); }
132            Exp::Run(b, e)     => { frames.push(EvFrame::Binary1 { tag: Some("run".into()),     second: e.as_ref() }); todo.push(b.as_ref()); }
133            Exp::LiftRef(a, b) => { frames.push(EvFrame::Binary1 { tag: Some("lift-ref".into()),second: b.as_ref() }); todo.push(a.as_ref()); }
134            Exp::Log(a, b)     => { frames.push(EvFrame::Binary1 { tag: Some("log".into()),     second: b.as_ref() }); todo.push(a.as_ref()); }
135            Exp::CellSet(a, b) => { frames.push(EvFrame::Binary1 { tag: Some("cell-set!".into()), second: b.as_ref() }); todo.push(a.as_ref()); }
136
137            // Ternary: 4-element tagged list.
138            Exp::If(c, t, f) => {
139                frames.push(EvFrame::Ternary1 {
140                    tag: "if".into(),
141                    second: t.as_ref(),
142                    third:  f.as_ref(),
143                });
144                todo.push(c.as_ref());
145            }
146
147            // Fallback: unhandled Exp variants render as a debug-formatted Sym.
148            // Catch, Read, Print, Evalms, Trans land here — they don't have
149            // Pink-source representations so trans never emits them.
150            other => results.push(Val::Sym(format!("<exp:{other:?}>").into())),
151        }
152
153        if results.len() == before {
154            continue; // pushed a frame + child; no result to propagate yet
155        }
156
157        // ── Fire frames whose input just arrived ──────────────────────────
158        'propagate: loop {
159            match frames.last() {
160                None => break 'propagate,
161
162                Some(EvFrame::Unary { .. }) => {
163                    let child = results.pop().unwrap();
164                    let EvFrame::Unary { tag } = frames.pop().unwrap() else { unreachable!() };
165                    results.push(mk_list(&[Val::Sym(tag), child]));
166                }
167                Some(EvFrame::Binary1 { .. }) => {
168                    let first = results.pop().unwrap();
169                    let EvFrame::Binary1 { tag, second } = frames.pop().unwrap() else { unreachable!() };
170                    frames.push(EvFrame::Binary2 { tag, first });
171                    todo.push(second);
172                    break 'propagate; // must convert `second` before continuing
173                }
174                Some(EvFrame::Binary2 { .. }) => {
175                    let second = results.pop().unwrap();
176                    let EvFrame::Binary2 { tag, first } = frames.pop().unwrap() else { unreachable!() };
177                    let val = match tag {
178                        Some(t) => mk_list(&[Val::Sym(t), first, second]),
179                        // App: untagged 2-element list (f a)
180                        None    => tup(first, tup(second, Val::Nil)),
181                    };
182                    results.push(val);
183                }
184                Some(EvFrame::Ternary1 { .. }) => {
185                    let first = results.pop().unwrap();
186                    let EvFrame::Ternary1 { tag, second, third } = frames.pop().unwrap() else { unreachable!() };
187                    frames.push(EvFrame::Ternary2 { tag, first, third });
188                    todo.push(second);
189                    break 'propagate;
190                }
191                Some(EvFrame::Ternary2 { .. }) => {
192                    let second = results.pop().unwrap();
193                    let EvFrame::Ternary2 { tag, first, third } = frames.pop().unwrap() else { unreachable!() };
194                    frames.push(EvFrame::Ternary3 { tag, first, second });
195                    todo.push(third);
196                    break 'propagate;
197                }
198                Some(EvFrame::Ternary3 { .. }) => {
199                    let third = results.pop().unwrap();
200                    let EvFrame::Ternary3 { tag, first, second } = frames.pop().unwrap() else { unreachable!() };
201                    results.push(mk_list(&[Val::Sym(tag), first, second, third]));
202                }
203            }
204        }
205    }
206
207    debug_assert!(frames.is_empty(), "exp_to_val_cons: incomplete frames at end");
208    results.pop().expect("exp_to_val_cons: empty results at end")
209}
210
211// ── val_cons_to_exp — iterative ───────────────────────────────────────────────
212//
213// Work stacks:
214//   todo:    Val items still to convert (LIFO).
215//   frames:  pending combination steps; each fires when its child is ready.
216//   results: completed Exp values.
217//
218// Push order for frames: since the stack fires LIFO, the *innermost* (first
219// child to produce) must be on top.  For Binary1{a,b}: push Binary1 (waiting
220// for a), then push a to todo — Binary1 fires once a is on results, then
221// pushes b to todo and upgrades to Binary2 to wait for it.
222
223/// Pending combination steps for `val_cons_to_exp`; each fires when
224/// its next child lands on the results stack, mirroring [`EvFrame`] in
225/// the other direction.
226enum VcFrame {
227    /// Waiting for the sole child of a unary form.
228    Unary(fn(RcExp) -> Exp),
229    /// Waiting for the first child of a binary form.
230    Binary1 {
231        /// The unconverted second child.
232        second: Val,
233        /// Constructor for the finished form.
234        make: fn(RcExp, RcExp) -> Exp,
235    },
236    /// First child done; waiting for the second.
237    Binary2 {
238        /// The converted first child.
239        first: Exp,
240        /// Constructor for the finished form.
241        make: fn(RcExp, RcExp) -> Exp,
242    },
243    /// Waiting for the first child of a ternary form (`if`).
244    Ternary1 {
245        /// The unconverted second child.
246        second: Val,
247        /// The unconverted third child.
248        third: Val,
249        /// Constructor for the finished form.
250        make: fn(RcExp, RcExp, RcExp) -> Exp,
251    },
252    /// First child done; waiting for the second.
253    Ternary2 {
254        /// The converted first child.
255        first: Exp,
256        /// The unconverted third child.
257        third: Val,
258        /// Constructor for the finished form.
259        make: fn(RcExp, RcExp, RcExp) -> Exp,
260    },
261    /// Two children done; waiting for the third.
262    Ternary3 {
263        /// The converted first child.
264        first: Exp,
265        /// The converted second child.
266        second: Exp,
267        /// Constructor for the finished form.
268        make: fn(RcExp, RcExp, RcExp) -> Exp,
269    },
270}
271
272/// Convert nameless source encoding (typically `trans` output) into an
273/// [`Exp`] tree. Unrecognised tags and non-symbol heads left-fold as
274/// curried applications, which is also how Pink's tower-navigation
275/// forms pass through.
276pub(super) fn val_cons_to_exp(root: &Val) -> Result<Exp, NarjuError> {
277    let mut todo:    Vec<Val>     = vec![root.clone()];
278    let mut frames:  Vec<VcFrame> = Vec::new();
279    let mut results: Vec<Exp>     = Vec::new();
280
281    while let Some(cur) = todo.pop() {
282        // ── Convert the next Val ──────────────────────────────────────────
283        let before = results.len();
284
285        match cur {
286            Val::Cst(n) => results.push(Exp::Lit(n)),
287            Val::Sym(s) => results.push(Exp::Sym(s)),
288            Val::Nil    => results.push(Exp::Nil),
289
290            Val::Tup(ref head, _) => match head.as_ref() {
291                Val::Sym(tag) => match tag.as_str() {
292                    "var" => {
293                        let n = vce_nth(&cur, 1).and_then(|v| match v {
294                            Val::Cst(n) => Ok(n as usize),
295                            o => Err(NarjuError::Stage(format!("val_cons_to_exp: bad var {o:?}"))),
296                        })?;
297                        results.push(Exp::Var(n));
298                    }
299                    "lambda"  => { let b=vce_nth(&cur,1)?; frames.push(VcFrame::Unary(Exp::Lam)); todo.push(b); }
300                    "lift"    => { let e=vce_nth(&cur,1)?; frames.push(VcFrame::Unary(Exp::Lift));   todo.push(e); }
301                    "car"     => { let e=vce_nth(&cur,1)?; frames.push(VcFrame::Unary(Exp::Car));    todo.push(e); }
302                    "cdr"     => { let e=vce_nth(&cur,1)?; frames.push(VcFrame::Unary(Exp::Cdr));    todo.push(e); }
303                    "number?" => { let e=vce_nth(&cur,1)?; frames.push(VcFrame::Unary(Exp::IsNum));  todo.push(e); }
304                    "symbol?" => { let e=vce_nth(&cur,1)?; frames.push(VcFrame::Unary(Exp::IsSym));  todo.push(e); }
305                    "null?"   => { let e=vce_nth(&cur,1)?; frames.push(VcFrame::Unary(Exp::IsNil));  todo.push(e); }
306                    "pair?"   => { let e=vce_nth(&cur,1)?; frames.push(VcFrame::Unary(Exp::IsPair)); todo.push(e); }
307
308                    "let" => {
309                        let init=vce_nth(&cur,1)?; let body=vce_nth(&cur,2)?;
310                        frames.push(VcFrame::Binary1 { second: body, make: |a,b| Exp::Let(a,b) });
311                        todo.push(init);
312                    }
313                    "run"      => vce_binary(&cur, Exp::Run,     &mut frames, &mut todo)?,
314                    "code?"    => vce_binary(&cur, Exp::IsCode,  &mut frames, &mut todo)?,
315                    "+"        => vce_binary(&cur, Exp::Plus,    &mut frames, &mut todo)?,
316                    "-"        => vce_binary(&cur, Exp::Minus,   &mut frames, &mut todo)?,
317                    "*"        => vce_binary(&cur, Exp::Times,   &mut frames, &mut todo)?,
318                    "eq?"      => vce_binary(&cur, Exp::Eq,      &mut frames, &mut todo)?,
319                    "cons"     => vce_binary(&cur, Exp::Cons,    &mut frames, &mut todo)?,
320                    "lift-ref" => vce_binary(&cur, Exp::LiftRef, &mut frames, &mut todo)?,
321                    "log"      => vce_binary(&cur, Exp::Log,     &mut frames, &mut todo)?,
322                    "cell-set!"=> vce_binary(&cur, Exp::CellSet, &mut frames, &mut todo)?,
323                    "cell-new" => { let e=vce_nth(&cur,1)?; frames.push(VcFrame::Unary(Exp::CellNew));  todo.push(e); }
324                    "cell-read"=> { let e=vce_nth(&cur,1)?; frames.push(VcFrame::Unary(Exp::CellRead)); todo.push(e); }
325                    "throw"    => { let e=vce_nth(&cur,1)?; frames.push(VcFrame::Unary(Exp::Throw));    todo.push(e); }
326
327                    "if" => {
328                        let c=vce_nth(&cur,1)?; let t=vce_nth(&cur,2)?; let f=vce_nth(&cur,3)?;
329                        frames.push(VcFrame::Ternary1 { second: t, third: f, make: |c,t,f| Exp::If(c,t,f) });
330                        todo.push(c);
331                    }
332
333                    // Pink tower-navigation forms and unrecognised tags: left-fold as App.
334                    _ => vce_app(&cur, &mut frames, &mut todo)?,
335                },
336                // Non-symbol head: left-fold as application.
337                _ => vce_app(&cur, &mut frames, &mut todo)?,
338            },
339
340            other => return Err(NarjuError::Stage(format!("val_cons_to_exp: unexpected {other:?}"))),
341        }
342
343        if results.len() == before {
344            continue; // pushed a frame + child; no result to propagate yet
345        }
346
347        // ── Fire frames whose input just arrived ──────────────────────────
348        'propagate: loop {
349            match frames.last() {
350                None => break 'propagate,
351
352                Some(VcFrame::Unary(_)) => {
353                    let exp = results.pop().unwrap();
354                    let VcFrame::Unary(make) = frames.pop().unwrap() else { unreachable!() };
355                    results.push(make(rc_exp(exp)));
356                }
357                Some(VcFrame::Binary1 { .. }) => {
358                    let first = results.pop().unwrap();
359                    let VcFrame::Binary1 { second, make } = frames.pop().unwrap() else { unreachable!() };
360                    frames.push(VcFrame::Binary2 { first, make });
361                    todo.push(second);
362                    break 'propagate; // must convert `second` before continuing
363                }
364                Some(VcFrame::Binary2 { .. }) => {
365                    let second = results.pop().unwrap();
366                    let VcFrame::Binary2 { first, make } = frames.pop().unwrap() else { unreachable!() };
367                    results.push(make(rc_exp(first), rc_exp(second)));
368                }
369                Some(VcFrame::Ternary1 { .. }) => {
370                    let first = results.pop().unwrap();
371                    let VcFrame::Ternary1 { second, third, make } = frames.pop().unwrap() else { unreachable!() };
372                    frames.push(VcFrame::Ternary2 { first, third, make });
373                    todo.push(second);
374                    break 'propagate;
375                }
376                Some(VcFrame::Ternary2 { .. }) => {
377                    let second = results.pop().unwrap();
378                    let VcFrame::Ternary2 { first, third, make } = frames.pop().unwrap() else { unreachable!() };
379                    frames.push(VcFrame::Ternary3 { first, second, make });
380                    todo.push(third);
381                    break 'propagate;
382                }
383                Some(VcFrame::Ternary3 { .. }) => {
384                    let third = results.pop().unwrap();
385                    let VcFrame::Ternary3 { first, second, make } = frames.pop().unwrap() else { unreachable!() };
386                    results.push(make(rc_exp(first), rc_exp(second), rc_exp(third)));
387                }
388            }
389        }
390    }
391
392    if !frames.is_empty() {
393        return Err(NarjuError::Stage(
394            "val_cons_to_exp: incomplete frames at end — input malformed".into(),
395        ));
396    }
397    results.into_iter().next()
398        .ok_or_else(|| NarjuError::Stage("val_cons_to_exp: empty result".into()))
399}
400
401/// The `n`th element of a cons-list, cloned out.
402fn vce_nth(v: &Val, n: usize) -> Result<Val, NarjuError> {
403    let mut cur = v;
404    for _ in 0..n {
405        match cur {
406            Val::Tup(_, t) => cur = t.as_ref(),
407            _ => return Err(NarjuError::Stage(format!("val_cons_to_exp: list too short at {n}: {v:?}"))),
408        }
409    }
410    match cur {
411        Val::Tup(h, _) => Ok((**h).clone()),
412        _ => Err(NarjuError::Stage(format!("val_cons_to_exp: no element at {n}: {v:?}"))),
413    }
414}
415
416/// Schedule both children of a tagged binary form.
417fn vce_binary(cur: &Val, make: fn(RcExp, RcExp) -> Exp, frames: &mut Vec<VcFrame>, todo: &mut Vec<Val>) -> Result<(), NarjuError> {
418    let a = vce_nth(cur, 1)?;
419    let b = vce_nth(cur, 2)?;
420    frames.push(VcFrame::Binary1 { second: b, make });
421    todo.push(a);
422    Ok(())
423}
424
425/// Left-fold application: push N Binary1 frames in reverse so arg1 fires first.
426/// (f a b c) → App(App(f,a),b),c)
427fn vce_app(cur: &Val, frames: &mut Vec<VcFrame>, todo: &mut Vec<Val>) -> Result<(), NarjuError> {
428    let items = val_to_vec(cur)?;
429    match items.len() {
430        0 => Err(NarjuError::Stage("val_cons_to_exp: empty application".into())),
431        1 => { todo.push(items.into_iter().next().unwrap()); Ok(()) }
432        _ => {
433            let mut iter = items.into_iter();
434            let head_val = iter.next().unwrap();
435            let args: Vec<Val> = iter.collect();
436            // Frames are LIFO: push in reverse so arg1 fires first (innermost).
437            for arg_val in args.into_iter().rev() {
438                frames.push(VcFrame::Binary1 { second: arg_val, make: |f,a| Exp::App(f,a) });
439            }
440            todo.push(head_val);
441            Ok(())
442        }
443    }
444}
445
446// ── trans — iterative ─────────────────────────────────────────────────────────
447
448/// A name-environment entry for `trans`.
449#[derive(Clone)]
450pub(super) enum NameEntry {
451    /// A plain name: occurrences translate to `(var n)` by position.
452    Name(SmolStr),
453    /// A splice: occurrences translate to the embedded code, rendered
454    /// back into source encoding. This is how `evalms`-driven Pink
455    /// sessions inject already-compiled values into fresh source.
456    Splice {
457        /// The surface name occurrences match on.
458        name: SmolStr,
459        /// The code spliced in at each occurrence.
460        exp: Exp,
461    },
462}
463
464impl NameEntry {
465    /// Whether this entry binds the surface name `s`.
466    pub(super) fn matches_name(&self, s: &str) -> bool {
467        match self {
468            NameEntry::Name(n) => n.as_str() == s,
469            NameEntry::Splice { name, .. } => name.as_str() == s,
470        }
471    }
472}
473
474/// Persistent name env: single backing Vec with O(1) push/restore.
475/// Avoids the O(depth²) allocation of `env.to_vec()` on every binder.
476struct NameEnv {
477    /// Backing storage; slots past `len` are stale but reusable.
478    entries: Vec<NameEntry>,
479    /// Number of live entries.
480    len: usize,
481}
482
483impl NameEnv {
484    /// A name env seeded with the caller's initial entries.
485    fn new(initial: &[NameEntry]) -> Self {
486        Self { entries: initial.to_vec(), len: initial.len() }
487    }
488    /// Innermost binding of `s`, as a position — the number that ends
489    /// up inside `(var n)`.
490    fn lookup(&self, s: &str) -> Option<usize> {
491        self.entries[..self.len].iter().rposition(|e| e.matches_name(s))
492    }
493    /// Push one entry; returns saved_len for restoration.
494    fn push1(&mut self, entry: NameEntry) -> usize {
495        let saved = self.len;
496        if self.entries.len() == self.len {
497            self.entries.push(entry);
498        } else {
499            self.entries[self.len] = entry;
500        }
501        self.len += 1;
502        saved
503    }
504    /// Drop back to a previously saved length.
505    fn restore(&mut self, saved: usize) { self.len = saved; }
506}
507
508/// Work items for the iterative [`trans`] loop.
509enum TransFrame {
510    /// Translate a Val, push result.
511    Trans(Val),
512    /// Cons two results: pop second, pop first, push tup(first, second).
513    Cons2,
514    /// Prepend a pre-computed Val onto the translated tail result.
515    ConsPrepend(Val),
516    /// After translating binder body: wrap as (tag body) and restore env.
517    WrapBinder {
518        /// The binder's head symbol (`lambda`).
519        tag: SmolStr,
520        /// Name-env length to restore after wrapping.
521        saved_len: usize,
522    },
523    /// After translating let-init: extend env with `name`, then translate body.
524    LetBody {
525        /// The name the `let` binds.
526        name: SmolStr,
527        /// The untranslated body.
528        body: Val,
529        /// Name-env length to restore when the body completes.
530        saved_len: usize,
531    },
532    /// After translating let-body: wrap as (let init body) and restore env.
533    WrapLet {
534        /// Name-env length to restore after wrapping.
535        saved_len: usize,
536    },
537}
538
539/// base.scm's `trans`: rewrite s-expression source into the nameless
540/// encoding, resolving symbols positionally against `initial_env`
541/// (extended through binders as translation proceeds). The output goes
542/// to [`val_cons_to_exp`]; the pair implements the `(trans e env)`
543/// primitive.
544pub(super) fn trans(e: &Val, initial_env: &[NameEntry]) -> Result<Val, NarjuError> {
545    let mut env  = NameEnv::new(initial_env);
546    let mut work: Vec<TransFrame> = vec![TransFrame::Trans(e.clone())];
547    let mut results: Vec<Val>     = Vec::new();
548
549    while let Some(frame) = work.pop() {
550        match frame {
551            TransFrame::Trans(v) => trans_step(v, &mut env, &mut work, &mut results)?,
552
553            TransFrame::Cons2 => {
554                let second = results.pop().expect("Cons2: missing second");
555                let first  = results.pop().expect("Cons2: missing first");
556                results.push(tup(first, second));
557            }
558
559            TransFrame::ConsPrepend(head_val) => {
560                let tail_val = results.pop().expect("ConsPrepend: missing tail");
561                results.push(tup(head_val, tail_val));
562            }
563
564            TransFrame::WrapBinder { tag, saved_len } => {
565                let body_val = results.pop().expect("WrapBinder: missing body");
566                env.restore(saved_len);
567                results.push(tup(Val::Sym(tag), tup(body_val, Val::Nil)));
568            }
569
570            TransFrame::LetBody { name, body, saved_len } => {
571                // tinit is on results. Extend env for body, then translate body.
572                // saved_len is the len *before* init was translated (env unchanged
573                // during init translation), so it is also the right restore point.
574                env.push1(NameEntry::Name(name));
575                work.push(TransFrame::WrapLet { saved_len });
576                work.push(TransFrame::Trans(body));
577            }
578
579            TransFrame::WrapLet { saved_len } => {
580                let tbody = results.pop().expect("WrapLet: missing body");
581                let tinit = results.pop().expect("WrapLet: missing init");
582                env.restore(saved_len);
583                results.push(tup(Val::Sym("let".into()), tup(tinit, tup(tbody, Val::Nil))));
584            }
585        }
586    }
587
588    results.pop().ok_or_else(|| NarjuError::Stage("trans: empty result".into()))
589}
590
591/// Dispatch one value in the `trans` worklist: atoms resolve or pass
592/// through, binders extend the env and schedule wrap-up frames, known
593/// operator tags pass through with their arguments translated, and
594/// anything else is an application.
595fn trans_step(v: Val, env: &mut NameEnv, work: &mut Vec<TransFrame>, results: &mut Vec<Val>) -> Result<(), NarjuError> {
596    match v {
597        Val::Cst(_) | Val::Nil => results.push(v),
598
599        Val::Sym(ref s) => {
600            let pos = env.lookup(s)
601                .ok_or_else(|| NarjuError::Stage(format!("trans: unbound variable {s}")))?;
602            match &env.entries[pos] {
603                NameEntry::Splice { exp, .. } => results.push(exp_to_val_cons(exp)),
604                NameEntry::Name(_) => results.push(tup(
605                    Val::Sym("var".into()),
606                    tup(Val::Cst(pos as i64), Val::Nil),
607                )),
608            }
609        }
610
611        Val::Tup(ref head, ref tail) => match head.as_ref() {
612            Val::Sym(tag) if tag == "quote" => {
613                match tail.as_ref() {
614                    Val::Tup(datum, _) => results.push((**datum).clone()),
615                    _ => return Err(NarjuError::Stage("trans: malformed quote".into())),
616                }
617            }
618
619            // Note: `clambda` is *not* a binder here — per pink.scm, it's
620            // a Pink-level dispatch tag handled at runtime by pink-poly's
621            // `(eq? 'clambda (car exp))` branch. We pass it through the
622            // passthrough-op path below so the tag is preserved and its
623            // arguments are translated in the current env. Treating it as
624            // a binder here (as narju did pre-Patch-D) silently rewrote
625            // clambda forms into lambda forms during trans, breaking
626            // delta-eval and EM-style runtime semantic modifications.
627            Val::Sym(tag) if tag == "lambda" => {
628                let (f, x, body) = extract_binder(&v)?;
629                let saved = env.push1(NameEntry::Name(f));
630                env.push1(NameEntry::Name(x)); // restored together via `saved`
631                let emit_tag = tag.clone();
632                work.push(TransFrame::WrapBinder { tag: emit_tag, saved_len: saved });
633                work.push(TransFrame::Trans(body));
634            }
635
636            Val::Sym(tag) if tag == "let" => {
637                let (x, init, body) = extract_let(&v)?;
638                let saved = env.len; // snapshot before touching env
639                work.push(TransFrame::LetBody { name: x, body, saved_len: saved });
640                work.push(TransFrame::Trans(init));
641            }
642
643            Val::Sym(op) if is_passthrough_op(op) => {
644                // Keep tag, translate args list in current env.
645                let tag_val = (**head).clone();
646                work.push(TransFrame::ConsPrepend(tag_val));
647                work.push(TransFrame::Trans((**tail).clone()));
648            }
649
650            _ => {
651                // Application: Cons2(translate_head, translate_tail).
652                // Push in reverse (LIFO) so head is translated first.
653                work.push(TransFrame::Cons2);
654                work.push(TransFrame::Trans((**tail).clone()));
655                work.push(TransFrame::Trans((**head).clone()));
656            }
657        },
658
659        other => results.push(other),
660    }
661    Ok(())
662}
663
664/// Operator tags `trans` preserves verbatim (translating only their
665/// arguments) rather than treating as applications or binders. Note
666/// this is a superset of the floor's special forms: `unlift`, `delta`,
667/// `delta-eval`, and `clambda` are Pink-level tags that pink-poly
668/// dispatches at runtime.
669fn is_passthrough_op(op: &str) -> bool {
670    matches!(
671        op,
672        "if" | "+" | "-" | "*" | "eq?" | "number?" | "symbol?" | "pair?" | "null?"
673            | "car" | "cdr" | "cons" | "code?" | "lift" | "run" | "lift-ref" | "log"
674            | "unlift" | "delta" | "delta-eval"
675            | "cell-new" | "cell-read" | "cell-set!" | "throw"
676            | "clambda"   // dispatched by Pink-poly at runtime, not a host binder
677    )
678}
679
680/// Destructure `(lambda f x body)` into its parts.
681fn extract_binder(v: &Val) -> Result<(SmolStr, SmolStr, Val), NarjuError> {
682    let f    = val_to_sym(&list_nth(v, 1)?)?;
683    let x    = val_to_sym(&list_nth(v, 2)?)?;
684    let body = list_nth(v, 3)?;
685    Ok((f, x, body))
686}
687
688/// Destructure `(let x init body)` into its parts.
689fn extract_let(v: &Val) -> Result<(SmolStr, Val, Val), NarjuError> {
690    let x    = val_to_sym(&list_nth(v, 1)?)?;
691    let init = list_nth(v, 2)?;
692    let body = list_nth(v, 3)?;
693    Ok((x, init, body))
694}
695
696/// The `n`th element of a cons-list, cloned out.
697fn list_nth(v: &Val, n: usize) -> Result<Val, NarjuError> {
698    let mut cur = v;
699    for _ in 0..n {
700        match cur {
701            Val::Tup(_, t) => cur = t.as_ref(),
702            _ => return Err(NarjuError::Stage(format!("list_nth: too short at {n}: {v:?}"))),
703        }
704    }
705    match cur {
706        Val::Tup(h, _) => Ok((**h).clone()),
707        _ => Err(NarjuError::Stage(format!("list_nth: no element at {n}: {v:?}"))),
708    }
709}
710
711// ── Shared list utilities ─────────────────────────────────────────────────────
712
713/// Collect a proper cons-list into a `Vec`; improper lists error.
714pub(super) fn val_to_vec(v: &Val) -> Result<Vec<Val>, NarjuError> {
715    let mut result = Vec::new();
716    let mut cur = v;
717    loop {
718        match cur {
719            Val::Nil => break,
720            Val::Tup(h, t) => { result.push((**h).clone()); cur = t; }
721            _ => return Err(NarjuError::Stage(format!("val_to_vec: improper list: {cur:?}"))),
722        }
723    }
724    Ok(result)
725}
726
727/// Require a symbol, cloned out.
728pub(super) fn val_to_sym(v: &Val) -> Result<SmolStr, NarjuError> {
729    match v {
730        Val::Sym(s) => Ok(s.clone()),
731        other => Err(NarjuError::Stage(format!("val_to_sym: expected Sym, got {other:?}"))),
732    }
733}
narju/eval/staging.rs

narju/eval/
staging.rs
