Seed: Adding `vau` with an immutable dynamic environment to Chez Scheme

I have been impressed by Kernel, created by John Nathan Shutt, for several years. I tried to let it go, but it came back into my life, much like Python, JavaScript, or PHP, but without the same elegance or attitude. Perhaps it is elitism, or perhaps it is intellectual curiosity and possibly tribalism. Maybe it is the parentheses. I am repeating myself.

Kernel bridges almost 70 years of history. Lisp started in 1958 at MIT, Scheme branched off in 1975, Brian Cantwell Smith's 1982 thesis on 3-Lisp is the intellectual ancestor of everything Kernel does with reified environments, and Common Lisp crystallized another branch in the Symbolics era. The ideas never stopped spreading — Femtolisp powers Julia's parser, Clojure's edn brought s-expression data notation to a mainstream audience, Fennel found traction in game development. What these share is the recurring discovery that a small, programmable core pays off. Kernel's vau is the next idea in that lineage waiting to land: the unification of macros and procedures.

John Nathan Shutt managed to crystallize with brilliance and likely formal accuracy the work of the entire Lisp community since its early days with the release of the SINK interpreter and the last draft of specification for Kernel programming language in particular Revised -1 Report on the Kernel Programming Language in 2009. He supported his thesis Fexprs as the basis of Lisp function application or $vau: the ultimate abstraction in 2010. He passed away in 2020.

He was not the only one to believe in the ideas that are in Kernel. For example, first-class environments are found in MIT Scheme and Guile. I think I remember that Gambit has reified continuations (and more), and continuation attachments came to Chez Scheme, a device similar to keyed dynamic variables from Kernel. Gambit (again!) has had them under a different guise for much longer. So, Kernel, like any other Lisp, is a Lisp.

The thing that got me hooked on Kernel, despite my passion for code, was laziness. Despite the excellent work to document syntax rules and syntax-case such as the work of “Extending a Language — Writing Powerful Macros in Scheme” by Marc Nieper-Wißkirchen, I do not subscribe to this approach. I prefer Kernel’s vau. I like the idea of unifying macros and procedures so you don't need two separate metalinguistic systems, one mechanism instead of two.

However, vau was cursed. In 1998, Wand, "The Theory of Fexprs is Trivial," ACM SIGPLAN Notices 33(9), 1998. proved that fexpr make equational reasoning impossible because you cannot substitute equals for equals when you don’t know if an expression will be evaluated. Compilation was considered intractable.

Until 2026.

EDIT (2026-02-06): I was pointed to kraken-lang.org and in particular Practical compilation of fexprs using partial evaluation: Fexprs can performantly replace macros in purely-functional Lisp. The difference between Kraken and seed, is that seed is not purely functional, seed support define, and set! but not on dynamic environments, also seed is an extension of chezscheme.

Making vau’s dynamic environment immutable restores enough static knowledge to compile competitively. In standard Kernel, a vau operative receives the caller's dynamic environment as first-class value; it can read it, traverse it, and crucially, mutate it. That last power is what kills compilation. If any operative can rewrite the caller's bindings at any time, the compiler cannot know what any variable means at any call site, so it cannot substitute, inline, or optimize anything. The fix is surgical: pass the environment, but make it read-only. The operative can still introspect the caller's bindings, that is the whole point of vau, the ability to decide whether and how to evaluate its arguments, but it cannot side-effect them. In practice, it can't define, or set! a variable in the dynamic environment, hence there is no mutation, no new bindings. Concretely, in the compiler, each operative call passes the environment as the first element of a (env . args) pair. The environment is a value, not a mutable store. That single constraint — immutability — gives the compiler back enough static knowledge to reason about the code, inline calls, and emit the same quality of native code that Chez Scheme produces from syntax-case.

Catamorphism vs. syntax-case. Consider a small expression evaluator. In Scheme with syntax-case, you write a macro that pattern-matches at compile time, then a separate runtime function that walks the tree with car, cdr, and cond. Two mechanisms, two languages — the macro language and the runtime language — kept apart by design. In Kernel, vau with match does both in one shot. The match clause (+ ,a ,b) binds a and b and recurses when the comma signals a catamorphism, meaning the transformation applies to subexpressions automatically before the clause body sees them. No explicit recursive calls, no peeling apart list structure by hand. The Scheme version is more verbose not because the programmer is less skilled, but because the language forces the separation of two concerns that are, structurally, the same concern: tree-in, tree-out transformation. Readability is subjective; the reader can judge for themselves. Performance is not.

vau does not require learning a new DSL, the pattern matching domain specific language of syntax-rules, and the shenanigans of syntax-object-fu of syntax-case. All three implementation implement the same behavior, only the last, using vau is economical.