# Lexical binding in tulisp
## Context
tulisp historically bound `let` and function parameters via a per-symbol
global stack (`SymbolBindings.items: Vec<TulispObject>`). Each binding
push/pop touched a shared `Vec`. In single-threaded use, pushes and
pops are balanced and nothing is observed. Under concurrent invocation
(e.g. tulisp-async timers on different threads), pushes and pops
interleave — a task can push `x=1`, yield, and when it resumes see
`x=2` because a sibling pushed later.
## Current strategy — B-eager
`let`, `let*`, and the caller side of `defun`/`lambda` create fresh
`LexicalBinding` objects **per evaluation / per call** and rewrite the
body (`capture_variables`) so references resolve to those new
bindings. Each invocation thus gets its own, unaliased storage.
Cost: one AST walk + one allocation per symbol per evaluation. Fine
for tulisp-async timer bodies at 1 Hz; acceptable for moderate-depth
loops. Hot inner loops that re-enter a `let` thousands of times per
second will pay a measurable tax.
Semantically this matches Emacs `lexical-binding: t`: `setq` on a
let-bound name mutates the let's cell; the surrounding dynamic symbol
is untouched. `(set 'x value)` — where `x` happens to be let-bound —
reaches past the lexical binding and mutates the global symbol. That
last point is a small departure from strict dynamic scoping and
matches Emacs's lexical mode.
## Future — B-framed
The long-term fix is to lift lexical bindings out of the AST into
per-call activation records:
- At define/compile time, transform each `let` and each function body
once: replace each local reference with a positional frame ref
(e.g. `FrameRef { depth, slot }`).
- At entry to a `let` or a function call, push a fresh `Vec<TulispObject>`
onto a thread-local frame stack.
- Reads and writes route to the correct frame via `depth`/`slot`.
- On exit, pop the frame.
Benefits: no per-evaluation AST rewrite; no per-call allocation beyond
the frame vector; reads/writes are `Vec` indexing (no hash, no
symbol lookup). Matches how Emacs's byte compiler handles
lexical-binding.
Cost: substantial rework. Eval would need to know about frames.
`mark_tail_calls`, `macroexpand`, and friends would need to respect
the transformed AST. `capture_variables` becomes dead code (replaced
by the frame-assigning compile pass). Errors and traces need to carry
a frame origin to stay readable.
### Known considerations to revisit when doing B-framed
- Closures need to capture their enclosing frame(s) — either by
pointer into a parent frame (shared mutable state) or by value
(snapshot at closure creation). Emacs uses shared-ref; tulisp
probably should too, for `setq`-through-closure semantics.
- `macroexpand` runs before the compile pass today — decide whether
the frame pass runs before or after macroexpansion. Emacs runs it
after (so macros can expand to raw `let`/lambda and the compiler
handles them uniformly). We'll want the same.
- Tail-call marking (`mark_tail_calls`) needs to play nicely with
frames — tail-call bounce currently rebinds symbols; with frames
it would rewrite frame slots.
- Quoted/backquoted forms need `FrameRef` to survive serialization
through `eval` and `macroexpand`.
- Dynamic variables (`defvar`-declared specials in Emacs) skip the
frame machinery. Once B-framed lands, decide how tulisp declares a
symbol as dynamic (default Emacs is `defvar` / `special-variable-p`).
### Performance notes collected during B-eager
- `let_race` (tulisp-async) with 8 concurrent tasks each running
`(let ((x v)) (sleep-for 0.1) (unless (equal x v) FAIL))`: 0 / 8
failures, ~103 ms total wall time. Before B-eager the same
reproducer failed 2–6 / 8.
- microsim: stream `ReceiveElectricalComponentTelemetryStream` for
component 1005 while calling `SetElectricalComponentPower` runs
without value staleness (was Bug #3).
- `examples/fib.lisp` (fib 30, ~1.6M recursive calls) regressed
~10.6× (247 ms → 2633 ms, release, hyperfine n=10). Root cause is
`substitute_lexical` cloning/rewriting the body on every call plus
one `TulispObject::lexical_binding` allocation per param per call.
For fib's tiny body this is pure overhead — each call allocates
~20 cons cells just to route `n`. Hot inner loops that re-enter a
defun/lambda millions of times per second will feel this.
Paths to recover the cost without re-introducing the race:
1. **Defun-time rewrite + thread-local items.** Do the body rewrite
once at lambda creation (each param → a fresh
`LexicalBinding` shared across all calls). Make those
LexicalBindings' item stacks thread-local (e.g. a `thread_local!`
`HashMap<LexId, Vec<TulispObject>>`). Call entry does push, exit
does pop — no per-call allocation or AST walk. Threads get
independent stacks, recursion is the same thread pushing deeper.
Medium effort, no external deps needed.
2. **Skip straight to B-framed.** Positional frame refs + activation
records. Larger rework but subsumes (1) and matches Emacs's
bytecode model.
### Shadowing caveat — substitute_lexical matches LexicalBinding too
After function-param substitution, body references to a param are
`LexicalBinding` values, not `Symbol` values. An inner `let` that
shadows a param must therefore replace references whose current form
is a `LexicalBinding` pointing at the same underlying symbol — not
just raw `Symbol`s. `substitute_lexical` handles this by matching
both variants via `TulispObject::eq` (which consults `lex_symbol_eq`
for LexicalBinding/LexicalBinding comparisons). Missing this causes
inner-let shadowing to silently leak the outer binding's value.