Andy Keep Rebuilds Chez Scheme Backend Across 52 Nanopass Phases

Andy Keep - Writing a Nanopass Compiler — ClojureTV

ClojureTV

Breaking monolithic compilers into dozens of formally verified micro-passes eliminates cascading defects without sacrificing commercial throughput, as individual algorithmic complexity rather than pass count dictates compiler speed.

AI-assisted summary of Andy Keep - Writing a Nanopass Compiler — original source. Check the original for full context.

Source published:

Key ideas

  • The Nanopass framework decomposes monolithic compiler passes into dozens of small, single-task transformations with strictly validated intermediate grammars to prevent subtle bugs from propagating downstream. (2:17)
  • Refuting academic criticism that the technique was only viable for education, Andy Keep and R. Kent Dybvig rewrote the commercial Chez Scheme compiler's backend into 52 distinct passes, retaining high compilation speeds (self-compiling in ~10 seconds). (9:50)
  • In a live demonstration, an ad-hoc 27-pass compiler built in days successfully lowered Scheme code down to low-level C with pointer tagging and flat closures, compiling and executing native binaries end-to-end directly from the REPL. (16:41)
  • Porting Nanopass to Clojure is viable either by implementing passes via core.match or by porting the entire meta-framework using Clojure macros, though reproducing Scheme's syntax-case metaprogramming is non-trivial. (35:33)

Detailed notes

## Background Published by ClojureTV on YouTube on January 6, 2014, this talk features Andy Keep presenting his research on nanopass compiler development. Based on his doctoral work at Indiana University replacing the Chez Scheme compiler, Keep explains how breaking compilers into dozens of tiny, single-task passes with formally defined intermediate languages can tame architectural complexity and run at commercial performance levels.

## TL;DR Keep traces the evolution of compiler architectures from early, I/O-constrained monolithic passes to fine-grained nanopass frameworks that define formal grammars between intermediate stages. He recounts how the technique transitioned from Dan Friedman and Kent Dybvig's pedagogical exercises at Indiana University to production-grade implementation, exploding Chez Scheme's backend from 5 passes to 52 while maintaining high throughput. Demonstrating a brand-new 27-pass compiler targeting C built on an airplane just days prior, Keep walks through language specifications, catamorphism transformations, tagged pointer schemes, and flat closures before discussing the possibilities of porting the paradigm into Clojure.

## Atmosphere & style The presentation carries a candid, affectionate, and caffeine-fueled hacker vibe, punctuated by self-deprecating humor about sleep deprivation, airplane coding, and uncompleted to-do comments. Keep speaks with contagious enthusiasm for the craft of compilation, drawing warmth and laughter from the Clojure audience despite openly joking about demonstrating purely Scheme code. The mood shifts from engaging technical history to suspenseful live REPL demos, culminating in genuine crowd applause as his freshly assembled 27-pass pipeline successfully compiles and executes programs on the fly.

## Bulletin - [02:17](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=137s) The Nanopass framework decomposes monolithic compiler passes into dozens of small, single-task transformations with strictly validated intermediate grammars to prevent subtle bugs from propagating downstream. - [09:50](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=590s) Refuting academic criticism that the technique was only viable for education, Andy Keep and R. Kent Dybvig rewrote the commercial Chez Scheme compiler's backend into 52 distinct passes, retaining high compilation speeds (self-compiling in ~10 seconds). - [16:41](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1001s) In a live demonstration, an ad-hoc 27-pass compiler built in days successfully lowered Scheme code down to low-level C with pointer tagging and flat closures, compiling and executing native binaries end-to-end directly from the REPL. - [35:33](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=2133s) Porting Nanopass to Clojure is viable either by implementing passes via core.match or by porting the entire meta-framework using Clojure macros, though reproducing Scheme's syntax-case metaprogramming is non-trivial.

## Key takeaways - [00:11](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=11s) Historical compilers were constrained to very few passes because intermediate representations had to be read from and written to tape drives or paper tape, whereas modern memory enables many in-memory passes. - [02:17](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=137s) Traditional compilers bundle unrelated optimizations into monolithic passes, making it difficult to insert new transformations without risking delicate invariants. - [03:22](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=202s) The Nanopass methodology originated from Dan Friedman's 'playing the game' pedagogy at Indiana University, where students verified transformations by evaluating both input and output Scheme expressions. - [06:22](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=382s) Relying on generic S-expression list matching caused slow compilation and delayed bug detection, leading to the creation of the Nanopass framework with formal grammars and record-based representations. - [06:22](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=382s) The Nanopass framework automates boilerplate AST traversals, requiring developers to write logic only for the grammar productions being explicitly transformed. - [09:50](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=590s) To disprove reviewer skepticism regarding production viability, Keep and Dybvig revamped Chez Scheme's backend from 5 passes to 52 individual passes, including a graph-coloring register allocator. - [10:22](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=622s) Compile times are driven by the computational cost of specific passes, such as register allocation loops, rather than the raw number of passes. - [16:41](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1001s) For the demonstration, Keep implemented an ad-hoc compiler targeting C across 27 single-task passes and 23 intermediate language specifications. - [21:19](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1279s) Within passes, unquote with catamorphisms syntax triggers recursive traversal on smaller AST components, while quasiquoting is overridden to instantiate strongly typed records instead of raw lists. - [25:48](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1548s) The runtime memory model uses 3-bit pointer tagging on 64-bit aligned addresses to differentiate immediate fixnums, pairs, boxes, vectors, and closures without type structures. - [25:48](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1548s) Closures are implemented as flat contiguous memory blocks containing a code pointer in slot 0 followed by captured free variables. - [29:02](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1742s) The end-to-end compiler driver shells out to GCC and parses binary output back into the Scheme REPL, allowing intermediate AST state tracing across all 27 passes. - [38:17](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=2297s) The Nanopass framework is not limited to tree-like ASTs; passes can emit and analyze explicit control flow graphs before reconstructing intermediate ASTs. - [38:17](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=2297s) The framework permits large, monolithic passes when optimizations are deeply interdependent, as demonstrated by Chez Scheme's unified source optimizer.

## Detailed walkthrough ### [00:11](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=11s) The Evolution of Compiler Architectures

Andy Keep opens by joking that, keeping with the tradition set by his office mate Will Byrd, he will not be showing any Clojure code during the presentation, offering Scheme code instead. Expressing his sheer enthusiasm for the craft, Andy explains: “I love writing compilers and doing things with compilers I just I think it's a lot of fun so I wanted to start out with a little bit of compiler history uh just to talk about what the idea of the nanopass stuff was and what the Genesis for it is.”

He recounts how early compilers were historically structured as merely a small handful of passes—often illustrated as three passes, though practical compilers had slightly more. This architecture was dictated purely by strict hardware constraints: machines lacked the memory to perform all necessary transformations in a single pass, and they could not even hold the intermediate representations in memory. Each pass read the program representation from storage and wrote the transformed program back out to disk, which at the time often meant physical tape drives or paper tape. Minimizing passes was vital when intermediate I/O was that punishingly slow.

As computer hardware evolved, memory became plentiful enough to keep intermediate representations entirely in RAM across passes. Yet even with that leap, the architectural paradigm largely remained frozen in place: compilers still grouped transformations into a handful of coarse-grained passes. In modern interactive environments—such as the REPL in Scheme, Clojure, Haskell, or ML—compilers often skip disk I/O entirely, compiling directly in memory and executing immediately.

- Early compilers minimized passes because swapping intermediate representations to tape drives or paper tape imposed massive I/O penalties. - Modern REPL environments build on in-memory compilation, executing generated machine code without touching the file system.

```mermaid flowchart LR accTitle: Traditional Compiler Pipeline vs In-Memory REPL accDescr: Diagram illustrating early disk-bound compilation passes versus modern in-memory compilation. subgraph Early["Early Compilers (I/O Bound)"] direction TB E1["Pass 1"] -->|"Tape / Paper Tape"| E2["Pass 2"] E2 -->|"Tape / Paper Tape"| E3["Pass 3"] end subgraph Modern["Modern Compilers & REPLs"] direction TB M1["Frontend Pass"] -->|"In-Memory AST"| M2["Optimizer"] M2 -->|"In-Memory AST"| M3["Codegen / Run"] end ```

---

[02:17](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=137s) Monolithic Passes and the Problem of Interleaving Optimizations

The major downside of having only a handful of passes is that each pass becomes an overloaded, monolithic beast. Looking back at the compiler he previously worked on, Andy illustrates how much disparate work was crammed together: a single pass simultaneously performed closure conversion, loop recognition, multiple return values handling, foreign callable handling, foreign function calls, and direct call optimizations, while closure optimizations were awkwardly split across that pass and the subsequent one.

This bundling becomes an engineering nightmare when actively developing and extending a compiler. If an engineer needs to insert a new optimization pass that logically must execute after one specific task but before another, and both tasks reside inside the same monolithic pass, clean separation is impossible. Describing this bind, Andy notes: “well now I'm sort of in trouble because I have to find a way to kind of weave that into the existing path without breaking anything that's already there and so that's pretty tricky.” The overarching goal of the nanopass philosophy is to dismantle these monolithic structures, decomposing them into dozens of tiny, single-task passes.

- A single traditional pass in Chez Scheme bundled closure conversion, loop recognition, multiple return value processing, foreign function interfaces, and direct call optimizations. - Tightly bundled tasks make inserting new optimization phases risky, as developers must surgically weave code into complex existing passes without breaking delicate invariants.

---

[03:22](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=202s) The Educational Roots at Indiana University and "Playing the Game"

The nanopass approach originated in the compiler design course at Indiana University. When Andy's advisor, R. Kent Dybvig, went on sabbatical, Dan Friedman stepped in to teach the class. Friedman wanted to move away from the traditional model of building big passes and focus students' attention on the core conceptual ideas of compilation. He introduced the concept of tiny, single-task passes implemented with pattern matchers, alongside an pedagogical technique called "playing the game." In this setup, a pass took an input expression that looked like Scheme and produced a transformed output that also looked like Scheme. Because both forms were executable Scheme expressions, students could evaluate the input and the output and verify that both yielded the identical semantic result. As Andy observes: “And he called this playing the game and so we still do this in the IU compiler class.”

However, during that initial semester, the curriculum produced disconnected passes rather than a working end-to-end compiler. When Kent Dybvig returned, he embraced the conceptual elegance of Friedman’s approach but insisted that students must construct a complete compiler. Dybvig restructured the class so that students wrote roughly 40 micro-passes over the semester, compiling a subset of Scheme down to native assembly and implementing sophisticated algorithms like a Chaitin-style graph-coloring register allocator.

While this pedagogical compiler was successful, it suffered from two key engineering defects. First, the compiler was slow, primarily due to pattern-matching overhead across raw S-expression lists. Second, passes lacked strict structural verification: an early pass might produce a malformed intermediate AST, but intermediate passes that did not inspect that specific construct would silently pass it along. An error would eventually explode five to seven passes later in an unrelated pass. Students would spend hours debugging the pass where the failure manifested, unaware that the defect originated far upstream in an earlier pass.

- Dan Friedman designed "playing the game" so students could evaluate both the input and transformed output in Scheme to verify semantic equivalence. - Kent Dybvig adapted Friedman's ideas into a semester-long course where students built an end-to-end compiler of roughly 40 passes that emitted assembly with graph-coloring register allocation. - Relying on generic list matching led to slow compilation and delayed error reporting, masking bugs until downstream passes failed.

---

[06:22](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=382s) The Nanopass Framework: Design, Rejection, and Core Forms

To eliminate pattern-matching slowness and surface malformed ASTs immediately, Kent Dybvig, Oscar Waddell, and Dipanwakar Sarkar set out to build a formalized framework. When they submitted their initial paper describing a technique suited for both educational and production compilers to ICFP (the International Conference on Functional Programming), the reviewers pushed back with skepticism: “and they sent it to the uh icfp the International Conference on functional programming and they said no we don't believe that you can do a commercial compiler with this we think you have to refocus the paper to just say educational compilers.”

The resulting framework solved the list-matching and validation problems by introducing formally defined intermediate language grammars between passes. Instead of untyped lists, the framework uses Scheme records behind the scenes. This allows the system to determine match branches in constant time without traversing full lists, dramatically improving compilation speed. More importantly, every pass specifies an explicit input language and output language. If a pass emits code that violates the output grammar, the framework throws an error immediately at the boundary rather than allowing corrupt ASTs to pollute downstream passes.

The framework also drastically reduces compiler boilerplate. Because the system tracks both the input and output grammars and knows precisely what syntactic forms differ between them, it automatically generates the traversal and reconstruction boilerplate for all forms that remain identical. The programmer only writes code for the specific language forms being transformed. The core language primitives include: - `define-language`: Defines the syntactic grammar of an intermediate language, allowing incremental extensions and subtractions from previous languages. - `define-pass`: Specifies an explicit transformation pass, declaring its formal input language, output language, and matching clauses. - `with-output-language`: Constructs language AST forms outside of a pass body. - `nanopass-case`: Deconstructs and pattern-matches language AST forms outside of an official pass.

---

[09:50](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=590s) Taking on the Commercial Challenge in Chez Scheme

Spurred by the ICFP review asserting that nanopass architectures were unfit for production environments, Andy and Kent Dybvig set out to prove the reviewers wrong by replacing the existing commercial Chez Scheme compiler with a fully nanopass-based implementation.

Andy explains that the existing production Chez Scheme compiler had around 11 passes when he began the project. This included five or six front-end passes, followed by an optional source optimizer pass positioned directly in the middle of the compilation pipeline, which handled a dense variety of optimizations before handing code off to the back-end stages. Emphasizing their ambition, Andy recalls: “so as an aside uh we decided that we wanted to take up this challenge of a commercial nanopass compiler and we did this in the context of Chez Scheme uh which is my advisor's uh scheme uh compiler and we took his compiler and we decided we were going to write a commercial nanopass compiler.”

- The project aimed to directly refute academic claims that nanopass compilers could not perform at commercial scale and speed. - The baseline Chez Scheme compiler consisted of approximately 11 passes, featuring 5 to 6 front-end passes and an optional, heavy-duty middle-end source optimizer.

[10:22](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=622s) Exploding the Backend: 52 Passes and Nanopass Compile Times

Andy points out that the revamped Chez Scheme compiler retained essentially the same front end, but they “kind of exploded the back end just a bit.” The back end expanded from only 5 passes all the way to 52 individual passes. Crucially, they introduced an optimization loop in the back end to handle graph-coloring register allocation. While this addition improved the runtime performance of generated code, it came at the cost of slowing compiler throughput down.

```mermaid flowchart TD accTitle: Backend Pass Expansion in Chez Scheme accDescr: Diagram showing the transition from the legacy 5-pass backend to the 52-pass Nanopass backend with graph-coloring register allocation.

subgraph Legacy["Original Chez Scheme"] L1["Frontend"] --> L2["5-Pass Backend"] end

subgraph Nanopass["Nanopass Architecture"] N1["Frontend"] --> N2["52-Pass Backend"] N2 --> N3["Graph Coloring Register Allocator Loop"] end ```

To put compiler speed in perspective, Andy emphasizes just how blindingly fast Chez Scheme originally was. The initial compiler could self-compile tens of thousands of lines of code in roughly 3 seconds. The new 52-pass nanopass-based compiler self-compiles in about 10 seconds. Andy stresses that despite the massive increase in passes, “it’s not the number of passes that impacts it as much as it is that you have some passes in there that are just more expensive and they tend to dominate the amount of time that you spend.” The overall compile time is only slower by roughly half, but because the framework's language- and pass-defining macros generate vastly more code under the hood, the compiler is doing considerably more work.

- Original Chez Scheme self-compile time: ~3 seconds for tens of thousands of lines. - Nanopass Chez Scheme self-compile time: ~10 seconds. - Back-end pass count grew from 5 passes to 52 distinct passes.

---

[11:55](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=715s) Building an Ad-Hoc Compiler for the Talk

To demonstrate the nanopass technique, Andy initially considered using the class compiler from Indiana University. However, he decided against sharing that implementation publicly on GitHub because current students might download it and submit it as homework, robbing them of the learning experience and forcing the course instructor to hunt down academic integrity violations. Instead, Andy took an impromptu approach: “I decided Monday afternoon that I would write a new compiler.” He spent the ensuing days and a cross-country plane ride writing the codebase, admitting that he had not slept much leading up to the presentation.

The toy compiler targets a subset of Scheme with concrete language choices: - Variables are represented as Scheme symbols. - Immediate constants include booleans (`#t`, `#f`), empty list (`nil` or `()`), and 61-bit signed integers (a bit-width chosen specifically for tagging schemes). - List and pair primitives include `car`, `cdr`, `cons`, `pair?`, and `null?`. Notably, `set-car!` and `set-cdr!` are omitted, guaranteeing that user lists remain immutable. - Vector primitives are supported: `make-vector`, `vector-ref`, `vector-set!`, `vector?`, and `vector-length`, using vector literal syntax like `#(1 2 3)` to represent fixed-length arrays. - Memory mutation primitives include `box`, `unbox`, and `box-set!`. - Arithmetic and relational operators (`+`, `-`, `*`, `/`, `=`, comparisons) operate over 61-bit signed integers. - Identity comparison is provided via `eq?`. - Quoted data (`quote <datum>`) supports constant symbols, quoted pairs, nested structures, and vector literals.

---

[14:15](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=855s) Formally Defining the Intermediate Language Grammar

The Nanopass Framework uses formal language specifications with explicit terminal types and productions. Language terminals are verified via Scheme predicates: `symbol?` checks variable names, while custom predicates check primitives, constants, and structured datums. The framework uses these predicates to enforce strict dynamic or static validation whenever forms are constructed: “this is going to allow the nanopass framework to check to make sure that when we construct a new language form all of the parts of it are of the correct type.”

```mermaid flowchart LR accTitle: Nanopass AST Verification Pipeline accDescr: Pipeline showing raw S-expressions being parsed and checked against terminal predicates to generate validated AST records.

A["S-Expressions (Input Source)"] --> B["Nanopass Predicate Validation"] subgraph Preds["Predicates"] P1["symbol? (Variables)"] P2["primitive?"] P3["constant? / datum?"] end B --> Preds Preds --> C["Typed Internal Record Forms"] ```

Although the language specifications look syntactically like S-expressions, the framework generates strongly typed internal records for every compound syntactic construct. For instance, a `(quote datum)` node generates a dedicated single-field record. The grammar includes: - Core expressions: standalone primitives, variable references, constants, and quoted data. - Branching forms: single-armed `(if test then)`, two-armed `(if test then else)`, as well as `or`, `and`, and `not`. Because the toy language lacks a user-level macro system, forms like `and` and `or` (defined using `...` to denote zero or more arguments) are handled as primitive language forms to be expanded away by compiler passes. - State and sequencing: `set!` (included because Andy finds assignment conversion fun, despite having no particular fondness for `set!` itself) and `begin` for sequenced operations. - Bindings and functions: `let`, `letrec`, `lambda`, and function application. Square brackets are treated identically to round parentheses, used solely to make binding pairs visually distinct for readability.

---

[16:41](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1001s) Lowering Through 27 Passes to C

While Andy usually prefers targeting raw assembly, the time pressure of writing the compiler between Monday and the talk led him to target C. Setting up graph-coloring register allocation from scratch without reference materials on an airplane was impractical, so targeting C allowed him to delegate machine register allocation to the underlying C compiler.

The full compilation pipeline consists of 27 distinct passes:

```mermaid flowchart TD accTitle: 27-Pass Scheme to C Nanopass Pipeline accDescr: Flowchart illustrating the sequence of lowering passes from Scheme S-expressions down to C emission.

subgraph Front["1. Parsing & Normalization"] P1["parse-and-rename"] --> P2["remove-one-armed-if"] P2 --> P3["remove-and-or-not"] P3 --> P4["make-begins-explicit"] P4 --> P5["eta-inverse-primitives"] end

subgraph Mid["2. Desugaring & Closures"] Front --> P6["quote-constants & remove-complex"] P6 --> P7["identify-assigned & convert-assignments"] P7 --> P8["purify-letrec & optimize-direct-calls"] P8 --> P9["uncover-free & convert-closures"] P9 --> P10["optimize-known-calls"] end

subgraph Back["3. Lowering to C"] Mid --> P11["lift-lambdas & flatten-nesting"] P11 --> P12["expose-allocation-primitives"] P12 --> P13["reintroduce-set! & drop-let"] P13 --> P14["Emit C Code"] end ```

The pipeline methodically decomposes complex high-level features into primitive operations: - **Reader parsing & renaming**: Standard Scheme `read` converts text to S-expressions, after which the compiler parses them into internal records and renames all variables to globally unique symbols. - **Syntactic simplification**: Passes remove one-armed `if` expressions, desugar `and`, `or`, and `not`, and ensure explicit `begin` sequences inside the bodies of `let`, `letrec`, and `lambda`. - **Inverse η-expansion (eta inversion)**: Standalone primitive references are wrapped in lambdas with matched arities (e.g., bare `+` becomes `(lambda (x y) (+ x y))`). This guarantees every primitive appears directly in operator call position, enabling them to be open-coded directly into inline C statements without function-call overhead. - **Constant & assignment processing**: Complex constants have their runtime memory allocations made explicit. Assigned variables are detected and converted via assignment conversion (wrapping mutated variables in single-element heap boxes), eliminating `set!` so that every variable is strictly immutable. - **Binding and closure conversion**: Applied lambdas are converted to `let` bindings; `let`-bound lambdas are promoted into `letrec`s; anonymous lambdas are eliminated. Free variables are identified to enable closure conversion, packaging procedures into explicit environments suitable for C (bypassing newer C lambda standards). - **Lowering to C-level constructs**: Known function calls bypass closure lookups to call direct function pointers. Nested expressions are flattened, lambdas are lifted to global top-level C functions, allocation primitives are exposed, and imperative statements with reassigned C variables (`set!`) are reintroduced to model low-level assignment while dropping high-level `let` blocks.

[20:11](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1211s) Pipeline Overview and Intermediate Languages

Andy Keep continues outlining the compilation pipeline leading down to C generation. Before diving into the concrete passes, he details the structural simplifications remaining: flattening assignments so that a `set!` is never nested on the right-hand side of another `set!`, pushing `if` expressions inward so that all predicates end up in the expected positions for C, establishing a concrete runtime representation for constants (which directly explains the 61-bit signed integers in the source specification), expanding primitives, and finally generating C code.

Across the entire compiler, there are 23 intermediate languages defined. Keep jokes about the naming convention: > “L Source the the only admittedly the only named language and then a whole bunch of unnamed languages that have been conveniently enumerated as L1 through L22 yeah sometimes it's hard to come up with meaningful names for these things.”

```mermaid flowchart LR accTitle: Nanopass compiler pipeline progression accDescr: High-level compilation pipeline showing passes from L_src through flattening, tagging, and C generation. subgraph Frontend ["AST Normalization"] L0["L_src"] -->|"remove-one-armed-if"| L1["L1"] L1 --> L_mid["... Flatten set! & push ifs..."] end subgraph Backend ["Lowering & Emission"] L_mid --> L_rep["Specify Constant Rep (61-bit)"] L_rep --> L_prim["Expand Primitives"] L_prim --> L22["L22 -> Generate C"] end ```

The second language in the system, `L1`, embodies the philosophy of making minuscule, verifiable modifications to the grammar. It differs from `L_src` in only two respects: - The primitive set is extended to include `void`. - The grammar drops the one-armed `(if e0 e1)` form, requiring all subsequent conditionals to have an explicit alternative branch.

---

[21:19](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1279s) Anatomy of a Nanopass: `remove-one-armed-if`

Keep presents the implementation of the very first pass, `remove-one-armed-if`. The entire pass is remarkably concise—essentially a one-line transformation wrapped in standard pass-definition scaffolding. Using the `define-pass` form, the developer declares: - The pass name: `remove-one-armed-if`. - The input signature: an input language (`L_src`) and argument list (a single input form). - The output signature: the target language (`L1`) and any extra return values (expressed as empty parentheses `()` since Scheme supports multiple return values, but none are needed here). - A nested transformer: by convention named after the non-terminal it operates on (in this case, `Expr`). The framework automatically infers which transformer to invoke based on grammar rules, tracking the input non-terminal, argument count, output non-terminal, and extra return values.

Within the transformer body, pattern matching checks for the one-armed `(if,[e0],[e1])` form. Keep highlights two critical pieces of syntax:

1. **Unquote and Catamorphisms:** The comma `,` is Scheme's standard unquote (analogous to `~` in Clojure syntax-quote). When combined with square brackets around an expression variable—`[e0]`—it denotes a *catamorphism*. Keep quips: > “The idea behind the catamorphism is really fancy category Theory stuff. I think of it as I recur on something that's smaller than the thing that I had before, which I think is more or less the definition.” Operationally, it causes the framework to generate a recursive call to `Expr` on the subform, binding the processed result to `e0` before entering the clause body.

2. **Quasiquote Overriding:** On the emission side, the pass reconstructs the conditional as an explicit two-armed form: `` `(if,e0,e1 (void)) ``. Keep warns that this quasiquote syntax is deceiving: > “Quasi quote does not do what you expect it to do here because it's not building a list it's actually building a record for this particular type.” By leveraging Scheme's hygienic macro system, the Nanopass framework hijacks quasiquote inside passes to instantiate strongly typed AST records rather than linked lists of symbols.

The developer only writes code for the specific clause being eliminated or changed. For every other AST production in the grammar, the framework automatically synthesizes the recursive traversal and reconstruction boilerplate. If a clause cannot be matched or constructed, the generated code raises a runtime error preserving original source locations: > “Because I got sick of trying to debug this while we were working on the Chez Scheme compiler is it puts an error message in there that remembers the source location of where things may have gone wrong and reports back, ‘Hey, something went wrong at this source location,’ which is kind of nice when you're trying to debug things, especially if you spend about 18 months working on a compiler and it turns out you run into these things more frequently than you would like.”

---

[25:48](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1548s) Low-Level Runtime Representations: Pointer Tagging and Flat Closures

Keep explains the concrete memory representation chosen for Scheme values in the generated C target. Because all runtime heap objects are aligned to 64-bit word boundaries (multiples of 8 bytes), the low three bits of any pointer address are guaranteed to be zeros (`000`).

Rather than waste those bits, the compiler employs a traditional tagged-pointer scheme to encode types within a single 64-bit word (`uintptr_t`): - **`000` (tag 0):** Used for fixnums (immediate 61-bit signed integers). This choice allows arithmetic operations to execute efficiently with minimal shifting and provides fast zero-checks. - **Other tags (1 through 7):** Distinguish heap-allocated pairs, vectors, boxes, and closures.

When lowering high-level lambdas to C, the compiler must also resolve closures, since C lacks first-class closures. Keep implements a standard **flat closure** model: - Each closure is represented as a contiguous block of heap memory. - Slot 0 holds a function pointer pointing to the emitted top-level C function containing the compiled code. - Each subsequent slot stores one of the closure's captured free variables, computed via free-variable analysis.

```mermaid flowchart TD accTitle: Flat Closure Memory Layout accDescr: Diagram showing a tagged closure pointer pointing to a header slot with a code pointer followed by data slots for captured free variables. Ptr["Closure Pointer (low 3 bits tagged)"] --> Layout["Flat Closure Block in Heap"] subgraph Layout ["Memory Slots"] S0["Slot 0: Code Pointer (*fn)"] S1["Slot 1: Captured Var X"] S2["Slot 2: Captured Var Y"] end ```

For instance, in a nested lambda where an inner lambda references `x` and `y` defined in enclosing scopes, free variable analysis identifies `x` and `y` as free. The closure instantiated at runtime contains exactly three slots: one code pointer and two data slots holding the bindings of `x` and `y`.

Rather than declaring rich C `struct` types or safe wrappers for pairs, boxes, and closures, Keep opts for raw, untyped pointer manipulation: > “Because, you know what, C really doesn't care. C is happy to do whatever you want with a pointer, and that's what we're going to do. So maybe not the safest C code; we're going to have to trust our compiler is going to generate the right stuff.”

---

[29:02](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1742s) Compiler Driver and Live Implementation

Transitioning to a live code demonstration, Keep mirrors his laptop displays to walk through the actual Chez Scheme source files available in the public GitHub repository. The project is released under a permissive open-source license: > “Yeah, copyright... you know, I put that in there mostly just so that I can put a like an MIT copyright on these things, MIT-style or BSD-style copyright.”

He walks through the exported interface of the compiler library: - **`my-tiny-compile`:** The primary driver function. It accepts an S-expression, runs the Nanopass compilation pipeline, emits raw C code, invokes GCC in the background to build an executable or dynamic library, and executes the compiled binary while reading back the return value directly into Scheme. This end-to-end driver allows testing and development to stay entirely inside the Scheme REPL without manually dealing with the shell or C tooling. - **Pass Tracing:** Built-in instrumentation enabling developers to inspect the AST intermediate representation between any arbitrary intermediate language step (`L_src` through `L22`). - **Boehm GC Integration:** Keep mentions an experimental runtime option to hook into the Boehm garbage collector for automatic heap reclamation, joking that he spent about ten minutes reading the Boehm collector documentation and ran out of time to thoroughly test it, so it remains optional in the flags. - **Tag Constants:** The source explicitly defines constant bindings for runtime tagging, starting with a fixnum tag of `0` and a pair tag of `1`.

[30:32](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1832s) Implementation Details: Tagging, Environments, and S-Expression Exports

Andy walks through the underlying runtime representations laid out in the compiler’s source code. He highlights the tag values used for low-level value differentiation: two for box tags, three for vector tags, and four for closure tags, noting that additional tag space remains available if needed. The runtime defines distinct representations for boolean values (`#t` and `#f`), including a dedicated boolean tag intended to simplify the implementation of the `boolean?` predicate. Integers use fixnum tagging, tracked via a record that stores the fixnum shift: “a record for our fix num shift here so that we know that we need to shift the thing three bits up when we want to make a change to it or three bits down after we've done operations like multiply and divide.”

He also points out an explicit word size of eight bytes (64-bit words), helpers for handling unique variable generation, and a list of primitives. Spotting an unfinished comment in his editor, he laughs at an uncompleted task: “my to-do here which didn't actually get done o and my misspelling of should sad.”

Moving on to intermediate language definitions, Keep explains that while the file contains a full grammar reference as a comment, the intermediate languages themselves are generated automatically. Users can inspect or regenerate complete grammatical representations at any time by loading the compiler library along with the Nanopass framework and running `language->s-expression`, which outputs the full language specification.

When discussing the compiler passes, Andy pauses briefly on the first pass, `parse-and-rename`. He chose not to discuss it earlier because of its sheer length, noting that it acts somewhat like a macro expander by setting up an initial environment. In Scheme, core syntactic forms and keywords can be shadowed or rebound. To prevent user code from breaking compiler semantics—for instance, if user code binds a variable named `quote`, subsequent function invocations using that name should not be misinterpreted as literal quotation forms—the pass references an initial environment and continuously extends it as new bindings enter scope.

- **Tag Bit Assignments**: Box (`2`), Vector (`3`), Closure (`4`). - **Fixnum Shift**: 3 bits (left-shift before operations or right-shift after multiplication/division). - **Architecture Word Size**: 8 bytes (64 bits). - **Grammar Introspection**: `language->s-expression` regenerates the expanded intermediate language definitions directly from the Nanopass framework.

---

[32:40](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=1960s) Live Compiler Demo: Compiling to C and End-to-End Execution

Facing a ticking clock, Andy switches over to a terminal demonstration. He jokes that he deliberately pruned his command history down to just a few entries so he could easily cycle through them without getting lost. After importing the compiler library—which experiences a brief pause due to loading several thousand lines of compiler logic, the Nanopass framework code itself, and all the macro-generated output—he proceeds to test running actual programs.

His initial target was modest: get two programs working properly end-to-end, specifically the constant `5` and recursive `factorial`. Testing the trivial literal `5`, the compiler successfully runs through all 27 distinct passes, generates a C source file on disk, shells out to the host C compiler to produce an executable binary, executes that binary, writes the stdout to the filesystem, and uses Scheme’s native `read` function to parse the printed output back into the REPL. The room breaks into applause at the successful pipeline execution, to which Keep remarks: “It compiled five through all 27 passes it wrote A C file to the file system it told the C compiler to compile it it ran the program the program output was written to the file system and then we use a schem r to read that back in that all that's what happened.”

```mermaid flowchart TD accTitle: Nanopass End-to-End Compilation Pipeline accDescr: Pipeline showing Scheme code moving through 27 passes, emitting C, compiling, executing, and reading results back into Scheme.

subgraph FrontEnd["Nanopass Pipeline"] SRC["Scheme Source Code"] --> P1["Pass 1: parse-and-rename"] P1 --> P2["Middle Passes (2 to 26)"] P2 --> P27["Pass 27: C Code Generation"] end

subgraph Native["Host System Execution"] P27 -->|"write"| CFILE["Output.c File"] CFILE -->|"invoke"| CC["Host C Compiler"] CC --> BIN["Native Binary"] BIN -->|"exec & stdout"| OUT["Output File"] end

OUT -->|"Scheme read"| REPL["REPL Result"] ```

Andy then runs `(factorial 10)`, proving that the system handles recursion, arithmetic shifts, and conditionals quickly. Anticipating audience skepticism about whether actual compilation took place under the hood, he invokes `(trace-passes)` and reruns the program. The terminal flashes with intermediate forms as each pass logs its progress. While early passes such as `remove-one-armed-if` simply recur down the AST without altering structures that lack single-branch conditionals, later passes rewrite terms into low-level representations until printing raw C code via numerous nested `printf` calls. He laments the ergonomics of emitting C without high-level C abstractions, noting that pointer arithmetic and tagged references force awkward casting constructs such as casting a pointer to a `long`, performing the byte math, and casting it back again.

---

[35:33](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=2133s) Future Work and Porting Nanopass to Clojure

Reflecting on next steps for the project, Keep notes that having a working compiler opens up numerous avenues for expansion. Beyond targeting C, alternative backends could be written for JavaScript, Clojure, the JVM,.NET, or LLVM (which he expresses strong interest in exploring). He also highlights the possibility of introducing richer data structures inspired by Clojure into Scheme, adding a garbage collector, supporting foreign function interfaces (FFI), and implementing deeper optimization passes, driven by his personal motivation: “part of the reason why I love compilers is I love fast and these are to make things fast.”

```mermaid flowchart LR accTitle: Potential Compiler Backend and Target Paths accDescr: Diagram illustrating potential backends and Clojure porting avenues for the Nanopass compiler.

subgraph Targets["Target Backends"] C["C Backend (Current)"] LLVM["LLVM"] JVM["JVM / JavaScript /.NET"] end

subgraph ClojurePort["Porting Strategies to Clojure"] CM["Option 1: Port Compiler via core.match"] MAC["Option 2: Port Framework via Clojure Macros"] end ```

He then explores the challenges and approaches for porting Nanopass ideas into the Clojure ecosystem: 1. **Porting the Compiler Using `core.match`**: Translating the compiler passes directly to Clojure using `clojure.core.match` over internal data representations. Keep suspects this would be the easier path and likely provide solid execution speed. 2. **Porting the Nanopass Framework Itself**: Reimplementing the meta-framework using native Clojure macros to provide idiomatic, Clojure-style syntax and workflow.

He warns that porting the framework itself is far more challenging because the Scheme implementation relies heavily on complex `syntax-case` macros. Explaining the metaprogramming heavy lifting involved, he jokes: “part of the reason why I know that we can do arbitrary computation with syntax case cuz believe me I do arbitrary computation.” Even so, he emphasizes that there are no fundamental technical roadblocks preventing a Clojure implementation.

Andy concludes his slides by listing project links, his email, his Twitter handle, and his website. He mentions that the current codebase runs on Chez Scheme and should run on other R6RS-compliant systems like Icarus and Vicare, though platform-specific differences mean he has not yet verified them.

---

[38:17](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=2297s) Q&A: Relational Passes, Control Flow Graphs, and Monolithic Passes

Opening the floor for questions, Andy addresses an inquiry regarding whether passes could be structured relationally using miniKanren or logic programming principles. He shares that his lab neighbor is Will Byrd (co-author of *The Reasoned Schemer*), and that they have often discussed related concepts: “I do sit next to will bird uh so we we have actually talked about uh some of the ideas somewhat somewhat in the context of actually like uh writing a type Checker that you write with a pass like this uh that is actually written in a relational style.”

He points out that passes performing simple AST transformations—like eliminating single-branch `if` statements—are fundamentally term rewriting operations, and any term rewriting system can be expressed relationally.

An audience member asks how the Nanopass approach handles stages where the representation diverges from a straightforward AST, such as control flow graphs (CFGs) for register allocation. Keep explains that passes in the framework are not restricted to consuming and outputting strictly hierarchical ASTs:

```mermaid flowchart LR accTitle: Non-AST Control Flow Graph Pipeline accDescr: Illustrates how an AST transforms into a Control Flow Graph, undergoes graph passes, and returns to an AST.

AST1["Abstract Syntax Tree"] -->|"generate"| CFG["Control Flow Graph"] CFG --> GP1["Graph Pass: Register Allocation"] GP1 --> GP2["Graph Analysis Passes"] GP2 -->|"reconstruct"| AST2["Target AST"] ```

Earlier compiler iterations attempted to embed control flow metadata directly inside the AST nodes, but this proved clumsy for register allocation. The updated compiler explicitly converts the AST into an explicit graph structure, routes that graph through dedicated graph-oriented passes, and reconstructs an AST once those passes conclude.

Finally, Andy clarifies that the Nanopass philosophy does not mandate breaking every compiler stage into atomic nano-passes if doing so degrades optimization quality. Chez Scheme's source optimizer, for instance, is built as a single, large pass within the framework. It bundles multiple mutually dependent optimizations together because decoupling them would compromise compiler output efficiency. As Keep summarizes: “this the idea behind this framework is to write these little passes because we can write these little passes but we can't always write these little passes.”

With time expired, Andy thanks the audience to closing applause.

## Notable quotes > [10:22](https://www.youtube.com/watch?v=Os7FE3J-U5Q&t=622s) it's not the number of passes that impacts it as much as it is that you have some passes in there that are just more expensive and they tend to dominate the amount of time that you spend. — Andy Keep

## Mentioned Andy Keep, Will Byrd, Dan Friedman, R. Kent Dybvig, Oscar Waddell, Dipanwakar Sarkar, Matt Might, Chez Scheme, Nanopass Framework, Scheme, Clojure, Haskell, ML, Scala, miniKanren, C, GCC, LLVM, Boehm GC, Icarus, Vicare, Indiana University, University of Utah, International Conference on Functional Programming (ICFP), The Reasoned Schemer

## Video description Contemporary compilers are among the most complex of software systems, typically being required to handle sophisticated high-level source languages, generate efficient code for multiple hardware architectures and operating systems, and support source-level debuggers, profilers, and other program development tools. Nanopass frameworks are designed to help manage this complexity. A nanopass compiler is comprised of many single-task passes with formally defined intermediate languages. The nanopass compiler technique evolved from a methodology for teaching a compiler course at Indiana University, into a full-fledged framework, capable of implementing a replacement for the Chez Scheme compiler that runs on par with the original compiler. This talk will discuss the idea of a nanopass compiler and the implementation of a simple language using the framework in Chez Scheme, along with the challenges and opportunities of using these techniques in Clojure.

Andy is a postdoc at the University of Utah, currently working on malware detection in Android Apps, using both Scala and miniKanren to write abstract analyzers in Matt Might's lab. Andy completed his Ph.D. at Indiana University, defending his dissertation, "A Nanopass Framework for Commercial Compiler Development", in December 2012 and will be presenting a paper related to this work at this year's International Conference on Functional Programming. This project focused on replacing Chez Scheme's compiler with a nanopass compiler, along with his adviser R. Kent Dybvig. Before returning to graduate school in 2007, Andy worked in industry as a web developer, first for the consulting firms Razorfish and Gotham Broadband, along with some independent consulting work for Viacom, and later worked full time at Teach For America, maintaining both front-end and back-end web applications.

[Source](https://www.youtube.com/watch?v=Os7FE3J-U5Q)

中文简报

Andy Keep基于52个Nanopass阶段重构Chez Scheme后端 将单体编译器拆解为数十个形式化验证的微阶段，可在不牺牲商用吞吐量的前提下消除级联缺陷，因为决定编译器速度的是单个算法的复杂度而非阶段数量。 Keep梳理了编译器架构的演变历程，从早期受I/O限制的单体阶段，到在中间阶段之间定义形式文法的细粒度Nanopass框架。他讲述了这项技术如何从Dan Friedman和Kent Dybvig在印第安纳大学的教学实践转变为生产级实现，在将Chez Scheme的后端从5个阶段扩展到52个阶段的同时保持了高吞吐量。Keep现场演示了几天前在飞机上构建的一个面向C语言的全新27阶段编译器，逐步讲解了语言规范、余代数折叠变换、标记指针方案和平坦闭包，随后探讨了将该范式移植到Clojure中的可行性。 Nanopass框架将单体编译器阶段拆解为数十个小型的单任务转换，并借助严格验证的中间文法防止微妙的缺陷向下游传播。 (2:17) 针对认为该技术仅适用于教学的学界批评，Andy Keep和R. Kent Dybvig将商用Chez Scheme编译器的后端重写为52个独立阶段，同时保持了极高的编译速度（自编译耗时约10秒）。 (9:50) 在现场演示中，一个几天内临时构建的27阶段编译器成功将Scheme代码降级为包含指针标记和平坦闭包的底层C代码，并直接从REPL端到端编译并执行了原生二进制程序。 (16:41) 将Nanopass移植到Clojure是可行的，既可以通过core.match实现各个阶段，也可以利用Clojure宏移植整个元框架，不过复现Scheme的syntax-case元编程并非易事。 (35:33)

Reading summary

Andy Keep argues that decomposing monolithic compiler pipelines into dozens of isolated, single-responsibility "nanopasses" simplifies engineering and optimization without imposing catastrophic performance penalties. Backing this approach with an end-to-end Scheme compiler, he demonstrates that formal intermediate language grammars eliminate the debugging hazards and boilerplate historically associated with fine-grained compiler architectures. Historical Trade-Offs of Monolithic Compiler Architecture (0:11) Early compilers grouped operations into coarse-grained passes because hardware lacked the memory to retain intermediate structures, requiring expensive I/O cycles to write code out to paper tape or disk. While modern RAM and interactive REPL environments eliminated these physical throughput limits, compilers preserved the monolithic architecture. Systems like legacy Chez Scheme condensed closure conversion, loop recognition, foreign function interfaces, and multiple-return-value handling into singular passes. Keep notes that this dense coupling creates an engineering bottleneck: inserting a new optimization between two tightly linked tasks inside a monolithic pass requires risky surgical modifications that frequently break fragile internal invariants. Nanopass Framework and Grammar Validation (3:22) The nanopass methodology evolved from an Indiana University compiler course designed by Dan Friedman and R. Kent Dybvig, which originally relied on "playing the game"—evaluating both the input and output Scheme code to ensure semantic equivalence. While conceptually sound, initial implementations suffered from slow list pattern-matching and delayed bug detection, where an upstream syntactic defect went unnoticed until failing five to seven passes later. To solve this, Dybvig, Oscar Waddell, and Dipanwakar Sarkar formalized the Nanopass Framework using Scheme records instead of raw lists, enabling constant-time matching branches. Automating Boilerplate and Commercial Feasibility (6:22) The modern framework uses primitives such as `define-language` and `define-pass` to enforce explicit grammatical contracts at every boundary. By analyzing the syntactic deltas between input and output grammars, the compiler automatically generates recursive traversals and reconstruction code for unchanged forms, requiring engineers to write transformation clauses only for altered forms. Quasiquote syntax is hijacked to generate strongly typed AST records rather than untyped lists. To disprove academic skepticism that the design could not scale to commercial use, Keep and Dybvig rebuilt the Chez Scheme backend into a 52-pass nanopass architecture. Despite introducing an intensive graph-coloring register allocator loop, self-compilation time rose only from 3 seconds to 10 seconds, refuting claims that high pass counts ruin compilation throughput. Lowering Scheme to C Across 27 Micro-Passes (16:41) To demonstrate the paradigm practically, Keep outlines an ad-hoc 27-pass compiler targeting C, moving across 23 distinct intermediate languages. Early phases normalize syntax by eliminating single-armed conditionals, desugaring logic forms, and using inverse η-expansion (eta inversion) to place primitives into direct call positions for C emission. The runtime relies on 64-bit tagged architecture: fixnums use a `000` tag for efficient arithmetic, while tags 1 through 4 handle pairs, boxes, vectors, and closures. Mutation is encapsulated through assignment conversion by boxing variables, while higher-order functions lower into flat heap closures with a code pointer in slot 0 followed by captured free variables. A live demonstration verified that this pipeline compiles expressions through all 27 passes, invokes GCC, and reads stdout back into the Scheme REPL seamlessly. Keep emphasizes that the nanopass philosophy does not mandate breaking down passes dogmatically when doing so harms optimization quality, pointing out that Chez Scheme's complex source optimizer remains a single integrated pass. Although the meta-framework heavily exploits Scheme's `syntax-case` macro system, he sees viable paths for porting either individual compilers via `clojure.core.match` or the core meta-framework itself into other environments like Clojure, LLVM, and the JVM.

精炼阅读摘要

Andy Keep 阐述了 Nanopass 编译器架构的设计理念：通过将传统编译器中庞大交织的宏单趟阶段拆解为数十个细粒度的单任务微通道，并结合强类型中间语言文法验证与样板代码自动推导，能够从根本上提升编译器的可维护性与调试效率，同时在工业级规模下保持可行的性能表现。 从单体通道的工程困境到教学实验的萌芽 (0:11) Keep 回顾指出，早期编译器之所以被设计为仅包含少数粗粒度通道（Pass），本质上受制于硬件内存限制，中间表示必须频繁换出到磁带或纸带等高延迟 I/O 介质。随着硬件内存充裕，编译器架构却长期保留了这种粗粒度划分，导致单个处理通道往往堆叠了闭包转换、循环识别、多返回值处理、外部函数调用（FFI）以及直接调用优化等多项异质任务。这种高度交织的设计使得在既有逻辑间插入新的优化阶段变得极其困难，极易破坏脆弱的不变量。 为打破这一架构壁垒，Dan Friedman 与 Kent Dybvig 在印第安纳大学的编译课程中提出了 Nanopass 原型，通过“玩游戏”（Playing the Game）模式让学生编写约 40 个微通道，确保每一步的输入输出均为语义等价的可执行 Scheme 代码。然而，早期教学实践暴露了严重工程缺陷：基于原始 S 表达式列表的模式匹配性能低效，且由于缺乏严格的阶段间文法校验，早期通道生成的畸形抽象语法树（AST）往往潜伏穿过数个中继阶段，最终在相隔五到七个通道后才暴露崩溃，大幅增加了调试成本。 形式化文法、模式消除与工业级性能验证 (6:22) 为了克服列表遍历低效与校验缺失问题，Dybvig、Oscar Waddell 和 Dipanwakar Sarkar 构建了形式化的 Nanopass 框架。该框架弃用无类型列表，在底层引入 Scheme 记录类型（Records），使模式分支能在常数时间内完成派发，并在通道边界强制实施输入输出文法校验。针对代码冗余问题，框架基于前后文法差异，通过卫生宏自动合成未变动 AST 节点的递归遍历与重建代码；开发者只需编写发生结构变异的节点规则，并可结合显式解引用与形变机制（Catamorphism）自动化缩减项的递归调用。 面对函数式编程国际会议（ICFP）审稿人对其无法适应工业编译器的质疑，Keep 与 Dybvig 重构了 Chez Scheme 的商业编译器作为抗辩。重构后的版本保留前端，将原本 5 个后级通道大幅拆解为 52 个独立的微通道，并引入图着色寄存器分配优化循环。尽管生成的内部代码规模大增，且经历了密集的文法校验，Chez Scheme 自举编译数万行代码的时间仅从原先极致的约 3 秒上升至约 10 秒。Keep 强调，编译器吞吐量的核心瓶颈并非通道数量的增加，而是少数重度算法通道的内在复杂度。 27趟微通道编译管线与底层运行时表示 (16:41) Keep 现场展示了一款在数日内构建、包含 27 个微通道与 23 种中间语言（L_src 至 L22）的原型编译器，旨在将 Scheme 子集直接降维编译至 C 语言。源语言涵盖不可变列表、向量、堆内存盒子、符号引用及 61 位有符号整数。整个编译管线逐层消除语法糖：第一阶段通过命名解析隔离作用域并消除单分支 if 语句（如 L_src 转化为 L1 时引入显式 void 分支）；随后进行反向 η 展开将独立原始操作符封装为具备固定参数数量的 lambda，进而消除 set! 并引入堆盒子实现赋值转换，最终通过自由变量分析将 lambda 降级为平面闭包（Flat Closures）。 在生成 C 目标代码时，编译器确立了具体的 64 位字长内存模型。由于堆内存分配严格按 8 字节边界对齐，指针最低 3 位天然为零，编译器利用这 3 个比特实现指针标记（Tagged Pointers）：标记 0 用于表示 61 位定长整数（Fixnum）以优化位移与算术效率，标记 1 至 4 则分别编码序对、盒子、向量及平面闭包。闭包在运行时被映射为连续内存块，首槽存放 C 函数指针，后续槽位存放捕获的环境变量，使得无一等闭包支持的 C 能够正确承载高阶函数语义。 超越树状结构：非AST表示与工程务实妥协 (38:17) 针对问答环节中关于非树状结构（如控制流图 CFG）的处理疑问，Keep 澄清 Nanopass 框架并不局限于纯层级 AST 的转换。在处理复杂的寄存器分配与数据流分析时，现代 Nanopass 编译器会明确将 AST 重构为显式的图结构，由专属的图通道完成优化遍历，再于后续阶段重新构建回 AST。此外，针对简单的项重写通道，其理论模型亦可与 miniKanren 等逻辑编程方法相结合，构建关系型类型检查与转换系统。 Keep 同时指出，Nanopass 理念并不主张机械地将所有编译阶段无限原子化。在 Chez Scheme 中，源程序优化器（Source Optimizer）依然保留为单个庞大的复合通道，因为该阶段包含多项高度互依的耦合优化，强行切分会损害优化质量。关于技术移植，Keep 分析在 Clojure 中实现 Nanopass 存在两种路径：使用 core.match 重写通道逻辑相对直接可行，而完整移植元框架则需要依托强大的宏系统进行任意计算，但技术上并无不可逾越的障碍。 Andy Keep 证实了 Nanopass 架构在保持极细粒度模块化与严格文法断言的同时，依然能够胜任工业级生产编译器的吞吐要求；然而，该架构的有效落地重度依赖宏元编程能力，且要求工程团队在微通道的解耦清晰度与紧耦合算法优化的现实收益之间做出务实权衡。

Source quotes

[10:22] Andy Keep: it's not the number of passes that impacts it as much as it is that you have some passes in there that are just more expensive and they tend to dominate the amount of time that you spend.

Original transcript

[0:09] [Applause] [0:11] thanks very much um so uh I'm Andy keep [0:15] and following in my office mate will [0:17] Bird's uh tradition I'm I'm not going to [0:19] show any closure code today sorry but I [0:22] will show some scheme code so [0:26] uh so so I you know I wanted to start by [0:29] saying I'm Andy keep and I love [0:31] compilers I love writing compilers and [0:34] doing things with compilers I just I [0:35] think it's a lot of fun so I wanted to [0:38] start out with a little bit of compiler [0:39] history uh just to talk about what the [0:42] idea of the nanopass stuff was and what [0:44] the Genesis for it is um so we used to [0:48] write compilers as just a a handful of [0:50] passes uh for convenience here I've only [0:53] represented three passes most of those [0:55] compilers had more than that but not too [0:57] many more than that and the early [0:59] compilers were written this way because [1:02] uh each individual pass had some work [1:04] that it needed to do but there weren't [1:06] enough resources on the machine to [1:07] necessarily do that all in a single pass [1:10] and in fact there wasn't even enough [1:11] resources on the machine to store all [1:13] this stuff in memory each pass would [1:16] actually read in uh a representation of [1:19] the program write it to the file system [1:22] the next pass would read it in and write [1:23] it to the file system and so you can see [1:26] why they wanted to minimize the number [1:28] of passes that they had in their their [1:30] compilers especially when the file [1:32] system was a tape drive or paper tape so [1:36] you know not not not a great design uh [1:39] or not a great space to to be able to do [1:41] this stuff in but computers got better [1:46] and then we could do our same handful of [1:48] passes and we could keep everything in [1:49] memory and that was that was kind of [1:52] nice but people continue to write their [1:54] compilers sort of this way I mean there [1:55] are some exceptions some things were [1:56] written with many passes but for the [1:58] most part it stayed this way [2:00] and sometimes we even never write it to [2:02] the file system we just go ahead and run [2:04] it um and you know that's pretty cool [2:07] this is sort of the situation when [2:08] you're at the reppel in something like [2:09] scheme or uh closure or hcll or ml or [2:13] whatever your favorite repple is um and [2:17] it to talk a little bit about the [2:18] compiler that I worked on a single pass [2:20] did closure conversion Loop [2:23] recognition uh it began our uh handling [2:26] it handled multiple return values [2:27] foreign callable handling foreign fun [2:29] function handling direct call [2:32] optimizations and then closure [2:33] optimizations started in one pass and [2:35] then continued in the next pass and the [2:37] thing that makes this all kind of tricky [2:39] is that if I'm sort of actively working [2:41] on my compiler and I want to add a new [2:44] optimization and that new optimization [2:46] has to happen after one task but before [2:49] another task and both of those tasks are [2:52] performed by the same pass well now I'm [2:54] sort of in trouble because I have to [2:56] find a way to kind of weave that into [2:58] the existing path with without breaking [3:00] anything that's already there and so [3:02] that's pretty tricky so what we sort of [3:04] want to do is we want to take these [3:06] things and break them up into a bunch of [3:07] small passes where each one of these [3:10] passes is just performing some single [3:12] task and then run through them that [3:15] way so as I said I love compilers um but [3:19] I particularly love nanopass compilers [3:22] and I've spent some time working on this [3:24] stuff so just to give you a little [3:26] background on where the nanopass stuff [3:28] comes from uh this all grew out of the [3:32] compiler class at Indiana University uh [3:35] or at least had some of its Genesis [3:37] there uh so my adviser Kent dvig who was [3:40] at Indiana at the time had gone on [3:42] sabatical I think and Dan fredman taught [3:45] the course and he really wanted to uh [3:49] get away from this sort of teaching of [3:51] passes these big passes and you know [3:53] building a compiler and he wanted to [3:55] talk specifically about like what are [3:57] the ideas the interesting ideas in the [3:59] compiler and how can we get um students [4:02] to go through them in a way that they'll [4:03] more easily understand them and so he [4:06] came up with this idea of writing these [4:08] passes that were very simple just did a [4:10] single task using like a pattern [4:13] matcher and uh introduce this idea of [4:16] playing the game where you handed in [4:18] some piece of you know something that [4:21] looked maybe a little bit like scheme [4:23] and you got something out that maybe [4:24] looked a little bit like scheme but had [4:26] been transformed but you could evaluate [4:28] the input and you could evaluate the [4:29] output and you could see that both of [4:31] them were the same and he called this [4:33] playing the game and so we still do this [4:35] in the IU compiler [4:36] class now that particular Year my [4:40] understanding at least is that the [4:41] compiler sort of wasn't a compiler as [4:44] much as it was a set of disconnected [4:46] passes so the ideas got across but they [4:49] never built a full [4:50] compiler so when my adviser Kent dvig [4:53] got back and started doing this uh class [4:56] he said ah here's a good idea but we [4:58] have to have the students build a [4:59] compile of course and so the result was [5:03] a compiler that was around 40 some [5:05] passes that the students wrote over the [5:07] course of the semester and it compiled a [5:10] subset of scheme down to assembly [5:13] code and implemented things like a graph [5:16] coloring register allocator and fun [5:18] algorithms like that and uh the whole [5:21] thing was written with match and the [5:23] representation that we used for the [5:25] compiler were lists so we're doing match [5:28] over lists and this was good uh it [5:31] worked pretty well um but there were a [5:33] couple of downsides um the compiler was [5:36] a bit slow uh partially because of some [5:38] of the pattern matching overhead um and [5:41] uh I I don't have it on the slide but [5:43] the other sort of downside of this was [5:44] that um you might have a pass that [5:47] produced ill-formed [5:49] output and the next few [5:51] passes accepted it because it they [5:54] didn't know any better or they didn't do [5:55] anything that impacted it and then you'd [5:58] have a past fail that was five six seven [6:00] passes down the line and you would think [6:02] ah you know this 10th pass in my [6:05] compiler must be wrong because it's [6:07] where the error occurs but the problem [6:09] wasn't there the problem was actually [6:10] five or six passes ago when you had this [6:13] malformed uh uh result and so the idea [6:17] was then to create a nanop pass [6:20] framework to try and address some of [6:22] this and so the nanop pass framework was [6:25] originally prototyped uh by Kent a [6:28] fellow named Oscar wadell and and [6:30] primarily by uh deepar car and they put [6:34] together a framework they wrote a paper [6:36] about it they sent the paper off they [6:38] said we have this technique for doing [6:40] educational compilers and you know [6:43] commercial compilers and they sent it to [6:45] the uh icfp the International Conference [6:48] on functional programming and they said [6:50] no we don't believe that you can do a [6:52] commercial compiler with this we think [6:54] you have to refocus the paper to just [6:56] say educational compilers so that was [6:58] the nanop pass the idea behind the [7:00] nanopass framework and sort of its its [7:01] first [7:02] iteration um some of the details of the [7:06] nanopass framework we have formal [7:07] language grammars so we Define the [7:10] syntax of each of our intermediate [7:12] representations between each of our [7:14] passes this gives us the ability to [7:17] check that information as we go [7:20] along we then Define passes over these [7:22] grammars so we're able to create these [7:25] passes and make sure that they uh have [7:28] an a formal input and formal output [7:30] language when I say formal here I'm just [7:32] talking about a a grammar syntax not a [7:35] semantics and then we made it easy for [7:37] languages to be extended so we wanted to [7:39] be able to make very small changes and [7:41] have lots of languages in addition to [7:43] having lots of passes and this led us [7:45] sort of Express these tiny changes as we [7:47] are going [7:49] along and the past form itself can [7:52] generate some of the boiler plate code [7:54] that we otherwise would have had to [7:55] write doing all of these uh sort of [7:58] micro passes using the um match system [8:02] so we have two forms main forms in the [8:04] language uh Define language which we use [8:06] for defining our [8:07] languages and Define pass which we use [8:10] for defining passes uh to this I've [8:13] added a couple of other forms uh with [8:15] output language that allows us to create [8:17] uh language forms outside of a Pass and [8:20] nanop Pass case which allows us to match [8:22] language forms outside of a pass uh so [8:25] the idea there being that you know [8:26] sometimes we need to sort of separate [8:28] the two things that the past does [8:30] reading and constructing uh language [8:34] forms so all this Machinery gives us [8:36] some benefits uh first it allows us to [8:38] autogenerate some of the past Clauses so [8:41] because we know the input language and [8:43] we know the output language and we know [8:44] how they're different we also know how [8:46] they're the same and so for those things [8:49] that are the same we can autogenerate [8:51] things like recurring through forms that [8:53] are otherwise not changing but might [8:55] contain some changing form uh it also [8:58] allows us to choose a more efficient [9:00] representation than lists so uh in in [9:03] scheme we don't have some of the fancy [9:05] data types that you guys have in closure [9:07] uh but we we do have records and we can [9:09] use the records to make things more [9:11] efficient by uh making a decision about [9:15] uh what pattern we've hit just looking [9:17] at the record and not needing to uh sort [9:20] of Traverse the whole list to decide [9:22] whether or not we've hit a pattern [9:24] match it also allows the framework to [9:27] check that output from each pass is [9:29] going to well formed um and so now if [9:32] our pass is producing something that [9:34] doesn't match the syntax we know for [9:36] sure immediately that that's not going [9:38] to meet the syntax and uh we can raise [9:40] an error right away and hopefully a [9:42] student or a commercial compiler writer [9:45] that runs into this can fix it much [9:48] earlier [9:49] on so as an aside uh we decided that we [9:52] wanted to take up this challenge of a [9:55] commercial nanopass compiler and we did [9:57] this in the context of Shay scheme uh [9:59] which is my advisor's uh scheme uh [10:01] compiler and we took his compiler and we [10:04] decided we were going to write a [10:05] commercial nanopass compiler so his [10:08] original compiler looked something like [10:10] this when I first started working on it [10:12] it had about 11 passes five uh six front [10:15] end passes uh one that was optionally [10:17] run with the uh Source Optimizer that's [10:20] this guy in the middle here which again [10:22] my laser pointer doesn't actually seem [10:23] to show up but oh well um and uh we sort [10:27] of kept the same front end and we kind [10:29] of exploded the back end just a [10:33] bit uh so just so you I can spare you [10:37] counting there are 52 passes now in the [10:39] back end so we went from five to 52 and [10:43] uh we added this Loop here in the back [10:45] end as well where we're doing uh graph [10:48] coloring register allocation which uh [10:50] gave us some benefits in terms of the [10:53] performance of the code that we compile [10:55] um but did slow down the compiler a bit [10:59] just just to give you an idea though of [11:00] the the order of time that we're talking [11:02] about uh when I started the Shas scheme [11:05] compiler could compile itself in about 3 [11:07] seconds so tens of thousands of lines of [11:10] code roughly in about 3 seconds well [11:12] okay to be fair I haven't counted um but [11:16] it's a significant amount of code and it [11:17] does it in about 3 seconds the new [11:20] compiler currently will compile itself [11:21] in about 10 seconds so it's still very [11:24] very fast even though it's doing a lot [11:26] more um going through a lot more passes [11:29] and sort of the the idea here is that [11:31] it's not the number of passes that [11:32] impacts it as much as it is that you [11:34] have some passes in there that are just [11:35] more expensive and they tend to dominate [11:37] the amount of time that you spend um so [11:40] we actually the overall compile time is [11:42] only about slower by half but uh as much [11:45] code as we had before our macros now [11:48] that we use to to Define these languages [11:50] and these passes uh generate a lot more [11:53] code so with all of that said I thought [11:55] it would be interesting for us to look [11:56] at an example and I did a little bit of [11:59] a stupid thing um I was going to talk [12:01] about the class compiler that we have at [12:04] IU uh but I sort of didn't want to put [12:06] that code out on GitHub and share it [12:07] because you know we we have students [12:09] still taking that class and I would sort [12:11] of feel bad if one they downloaded it [12:15] and turned it in as their assignments [12:16] because they wouldn't get the benefit of [12:18] actually learning it and uh uh the [12:20] fellow that's teaching the class right [12:22] now would actually have to try and find [12:23] all those cases and it wouldn't work out [12:25] well so I decided Monday afternoon that [12:28] I would write a new [12:29] compiler um and it's available on [12:33] GitHub I haven't slept much in the last [12:35] few days but it's available on [12:37] GitHub and uh we're going to compile uh [12:41] we're also going to compile a subset of [12:42] scheme um so uh just some parts of [12:46] scheme here we're going to represent our [12:48] variables as symbols uh not surprising [12:50] this is how we represent them in scheme [12:52] as well uh we're going to have a handful [12:54] of constants uh true #t uh false # F uh [13:00] nil uh or n and 61 bit integers and I [13:04] I'll tell you why 61 bit signed integers [13:07] in a few minutes um and then we're going [13:10] to implement a handful of Primitives uh [13:12] so car cter cons pair and null for [13:15] dealing with you know lists and pairs U [13:18] boine question mark um make vector [13:21] vector ref Vector set bang Vector [13:22] question mark Vector length uh box unbox [13:25] and box set uh which is not something [13:27] that we have the students implement but [13:29] but we're going to use it for something [13:30] you'll notice that I didn't put set car [13:32] or set cter in there so my lists are [13:34] immutable um we've got plus minus times [13:37] divide equal those are all going to [13:39] operate over our 61 bit [13:42] integers um the you know other [13:45] comparison operators and then EQ which [13:46] we're going to use for sort of [13:48] identifying whether something is the the [13:50] identity right so is this thing exactly [13:53] that thing in memory and we also have [13:55] quoted datm uh so we can Define [13:58] constants we can Define uh quoted pairs [14:01] uh which then can contain more datum and [14:05] then this funny thing here with the hash [14:07] is uh how we represent vectors in scheme [14:10] so we're going to use this to represent [14:11] vectors which are basically just fixed [14:13] length [14:15] arrays okay so I said that we had a [14:17] formal language for defining these [14:19] things in the nanopass framework so of [14:21] course we have a source language and we [14:23] can Define that in uh using the nanopass [14:26] uh framework here so we have a set of [14:28] terminals and part of how we know that [14:30] our languages are well formed is each of [14:33] these terminals uh corresponds to uh a [14:36] predicate so scheme has a a predicate [14:40] called symbol question mark we're going [14:41] to use that for recognizing our [14:42] variables uh The Primitives I wrote uh [14:45] my own uh predicate for constants I have [14:48] my own predicate for and datum I have my [14:50] own predicate for to check these things [14:52] but this is going to allow the nanopass [14:54] framework to check to make sure that [14:56] when we construct a new language form [14:58] all of the parts of it are of the [15:00] correct [15:01] type then we have a set of Productions [15:04] that are our the expressions in our [15:06] language so the first few productions [15:08] here are Standalone Primitives uh [15:11] references to variables and uh [15:14] Standalone constants and quoted [15:16] datum so these all look like s [15:19] Expressions but underneath all of this [15:22] we're going to create records for [15:23] anything that's structured so this [15:25] quoted thing here there's actually going [15:27] to be a record created for it with one [15:28] field [15:31] then we have our branching things if uh [15:34] one armed if two armed if uh or and not [15:37] and of course we could implement or and [15:39] a not as macros but our language doesn't [15:41] have macros yet so we have to actually [15:44] Define those as compiler passes and the [15:47] dot dot dot here just means we're going [15:48] to have zero or more of these things so [15:51] or has to have zero or more elements and [15:54] and has to have zero or more [15:56] elements um and these of course are each [15:58] getting a record associated with them as [16:00] well and then finally we have uh set [16:02] bang uh mostly because I just think [16:04] assignment conversion is kind of fun I [16:06] don't have any particular love of set [16:08] bang uh but then uh we'll have begin so [16:11] that we can do more than one thing in [16:12] our ifs uh let let W and Lambda and of [16:17] course function application and the [16:19] square brackets here uh they they mean [16:23] the same thing as the round brackets we [16:24] just use them to so that we don't get [16:26] confused when we see the bindings so I [16:29] I'm sorry if it's a little confusing uh [16:31] I I know that closure uses these to mean [16:33] different things um so uh scheme's a [16:36] little bit yeah you know everything's a [16:38] parentheses in scheme so um so our [16:41] target language for this is going to be [16:42] C now normally uh you know I Target [16:45] assembly but again I I did start this [16:47] Monday afternoon and I felt like you [16:50] know writing the register allocator [16:51] while it's a lot of fun uh also tends to [16:54] be a little bit of work particularly [16:55] remembering how to get it right and I [16:57] wrote some of this on the plane I knew I [16:58] wouldn't have reference to everything [17:00] that I that I needed so I decided to do [17:02] it in C mostly so that it will do the [17:04] register allocation for [17:06] us uh so uh I went home Monday afternoon [17:10] and I wrote a bunch of code and then I [17:11] got on a plane I wrote a bunch of code [17:13] and then I kind of finished up the last [17:15] details of this over the last couple of [17:16] days um and I got a compiler that looks [17:19] a bit like [17:20] this uh so again to spare you the [17:23] counting there are 27 passes here um and [17:27] this takes us from our source scheme [17:29] language down to uh C and we generate C [17:33] code um and just to zoom in a little bit [17:36] uh the first thing that we're going to [17:37] do is sort of parse and rename and it's [17:40] a little unfair to say parse we we call [17:42] this parsing in scheme but really we're [17:43] going to use a scheme reader to do the [17:45] real from string parsing and we're going [17:48] to use S expressions and turn them into [17:50] our internal record representation and [17:53] we're also going to rename variables so [17:55] that uh once they're uh in the compiler [17:57] they're always unique that's going to [17:59] that's helpful for us because then we [18:00] don't have to worry about that later [18:02] then we've got some steps that are just [18:03] going to simplify things we're going to [18:05] remove our one armed if we're going to [18:06] remove and or a not uh we're going to [18:08] make the begins explicit in the bodies [18:10] of our let letre and Lambda um we're [18:13] going to inverse Ada raw Primitives [18:15] which is a really fancy way of saying [18:16] that when we see a primitive standing [18:18] standing by itself we're going to wrap a [18:19] Lambda around it with a proper number of [18:22] arguments and we're going to call it and [18:24] this is mostly just so that we can move [18:25] all of our Primitives into call position [18:27] so that we can do what's called open [18:28] coding them uh in other words we're [18:30] going to generate the C code to do those [18:32] directly rather than having some [18:34] function that we're going to call for [18:35] The [18:36] Primitives then we're going to quote our [18:38] constants remove our complex constants [18:40] so where we have structured constants [18:41] we're going to make their uh allocation [18:43] explicit and we're going to identify the [18:45] assigned varibles so that we can do [18:47] assignment [18:48] conversion and we're going to turn our [18:49] let Rex into things that bind only [18:52] labels to [18:53] lambdas uh optimize direct calls is just [18:56] a way of looking for directly applied [18:58] lambdas and turning them into lets uh [19:01] we're going to find our let bound [19:03] lambdas and turn those into let Rex We [19:05] like Let Rex they're they're pure and [19:07] fun to deal with um we're going to [19:09] remove our Anonymous lambdas and we're [19:11] going to convert assignments and that's [19:12] going to get rid of set bang for us so [19:15] by the time we're done with that [19:16] everything will be either uh an un [19:19] immutable variable or a data structure [19:21] that has some way to mutate it then [19:24] we're going to uncover free variables [19:26] convert closures we need to do this in [19:28] order to sort of drop this stuff into C [19:30] where we don't have closures available [19:31] to us well okay I know that there are [19:34] now sort of lambdas in in at least the [19:35] newest C standard but we're not going to [19:37] use them uh then we're going to optimize [19:39] known calls which is basically a way of [19:41] saying we're going to make the function [19:44] call rather than pulling it out of the [19:45] closure we're going to just call it [19:48] directly um now we'll lift the lambdas [19:51] get rid of uh nested uh things nested uh [19:56] Expressions uh we'll separate things [19:58] into context I go into all that detail [20:01] uh expose the allocation Primitives is [20:03] going to basically start to convert some [20:06] of our stuff into something that looks [20:07] closer to C we're going to reintroduce [20:09] set bang we're going to get rid of let [20:11] we're going to flatten those so that [20:12] they don't have we never have a set bang [20:14] that's on the other side of a set bang [20:17] uh and then we're going to push our ifs [20:19] in which we I think we need to do for C [20:21] just to get all of the uh predicates in [20:22] the same place we're going to specify a [20:25] constant representation this is part of [20:26] why we have the 61 bit [20:29] integers and we're going to expand [20:31] Primitives and finally generate C which [20:33] is a lot of stuff um so first let's [20:36] start by looking at the second language [20:39] in our in our compiler so there are 23 [20:41] languages total uh L Source the the only [20:45] admittedly the only named language and [20:47] then a whole bunch of unnamed languages [20:49] that have been conveniently enumerated [20:51] as L1 through [20:54] l22 yeah sometimes it's hard to come up [20:57] with meaningful Nam names for these [20:59] things um so uh the basic idea here is [21:03] that we're making a very small change [21:05] we're going to uh extend our our list of [21:08] Primitives to add void and we're going [21:11] to get rid of our uh one-armed ifs here [21:14] and so that's going to be uh the [21:16] technique and we're going to look at one [21:19] pass here in detail so this is the very [21:22] first pass it's not too much code to [21:24] write actually it's just this kind of [21:26] oneline clause and some of the cont text [21:28] to wrap around it so when we Define a [21:31] new pass we're going to get a new [21:33] function uh named removed one armed if [21:36] this is our name and then we have a [21:38] signature associated with it and the [21:40] signature tells us what our input [21:41] language is uh what our argument list is [21:44] so this one accepts one argument and [21:47] it's an argument of the L Source [21:49] type um and then we're going to have an [21:52] output language uh and we're going to [21:54] Output the one thing the language thing [21:57] and uh scheme has m return values so we [21:59] have a way of returning multiple things [22:01] but we're not going to return anything [22:02] else here so we can indicate that by [22:04] just having these empty bra empty BRS [22:07] here and then we're going to have a [22:09] Transformer and the Transformer uh here [22:11] is just this piece um the framework [22:15] figures out what Transformer it should [22:16] call automatically and the Transformer [22:19] we we can name uh we tend to name it the [22:21] same as the the non-terminal that we're [22:23] processing uh but you can choose any [22:25] name you like uh we just have sort of [22:28] done that as is a standard and then we [22:30] indicate what the input non-terminal is [22:32] what its argument count is what the [22:34] output non-terminal is and any extra [22:37] values that we want in return and then [22:39] within the body of our Transformer we're [22:41] going to match some Claws and take a [22:45] look to see what it is so we've got an [22:46] if [22:48] here the one armed if that we were [22:50] trying to [22:51] match uh the little commas here these [22:54] are schemes version of unquote so uh the [22:57] Tilda that's used in closure this is the [22:59] scheme equivalent of and then our Square [23:02] bracketed things here this is actually [23:04] to indicate what's called a catamorphism [23:07] uh the the idea behind the catamorphism [23:09] is is really fancy category Theory stuff [23:12] I I think of it as I recur on something [23:14] that's smaller than the thing that I had [23:16] before which I think is more or less the [23:18] definition so what this is basically [23:20] going to generate for us is uh a call uh [23:24] to exper so it's going to generate the [23:26] value of e0 by calling exper on the [23:28] thing that it found and making that [23:30] available in the [23:32] body so we really don't have to do too [23:34] much fancy the really the work that [23:36] we're doing here is to add this void so [23:38] that we have a two arm diff instead of [23:39] one arm diff so here the Quasi quote uh [23:43] even for those of you familiar with [23:45] scheme is maybe going to be a little bit [23:47] misleading quasi quote does not do what [23:49] you expect it to do here because it's [23:51] not building a list it's actually [23:53] building a record for this particular [23:56] type uh we made use of the fact fact [23:58] that we have the flexibility of the [24:00] macro system to override what quasi [24:02] quote means in this [24:04] context um which is nice because it [24:07] means that we can sort of take our old [24:08] match based compilers and we can just [24:10] kind of translate them pretty easily um [24:13] but it's a little confusing for people [24:14] when they first see this [24:15] stuff um and then of course we have our [24:18] quotes again uh again this is our our [24:21] unquote um and our void and here uh we [24:28] are actually building a record for the [24:30] Primitive call or for the rather for the [24:32] the the um the call here and the [24:34] Primitive is just the quoted um uh [24:37] symbol void uh which we don't have to do [24:40] the unquote and quote around but I think [24:41] in closure you do have to do the unquote [24:43] and quote around to get that piece [24:44] working um so pretty simple actually but [24:48] this is really isn't all this P needs to [24:50] do because there are many many other [24:52] forms in this language that need to be [24:55] recurred through and so this is one of [24:57] the great things about the nanopass it [24:59] actually is going to generate for us all [25:00] these other Clauses that we don't need [25:02] to worry about and if it finds a clause [25:05] that it can't figure out how to build it [25:07] will either well okay let's see does it [25:09] ever complain at compile time I don't [25:11] think it ever complains at compile time [25:12] although it probably could in some [25:14] situations uh but what it does do um [25:17] because I got sick of trying to debug [25:18] this while we were working on the uh uh [25:21] Shas schem compiler is it puts an error [25:23] message in there that remembers the S [25:25] Source location of where things may have [25:27] gone wrong and reports back hey [25:30] something went wrong at this Source [25:31] location which is kind of nice when [25:33] you're trying to debug things especially [25:35] if you spend about 18 months working on [25:37] a compiler and it turns out you run into [25:40] these things more frequently than you [25:41] would like um because you forget to [25:44] write some Clause that you needed to [25:47] write uh okay so let's talk about the [25:49] representation I I said I would say why [25:51] we had [25:52] 16bit signed integers 61 bit signed [25:56] integers uh so the whole reason behind [25:59] this is because scheme objects are going [26:01] to be word aligned we're going to kind [26:04] of uh play a little bit of a game here [26:07] and uh put all of represent all of our [26:10] scheme objects with just a one a word [26:12] siiz 64-bit [26:14] pointer because they're word aligned it [26:16] means that the bottom three bits are [26:18] always going to be [26:19] zero [26:21] so hating to waste anything that we [26:24] could use we're going to use those [26:26] bottom three bits in order to tag [26:28] the types of our [26:30] pointers so these bottom three bits are [26:33] going to give us a tag for pairs vectors [26:36] boxes closures and actually for fixed [26:39] nums which is why we have our 61 bit [26:42] signed integers we're actually going to [26:43] use raw pointers to represent them where [26:46] the tag on them is just going to be zero [26:49] turns out that works out well for the [26:50] math and we can identify them fairly [26:53] easily so what about representing [26:55] closures uh because I said you know we [26:58] don't have closures in C and there's a [27:00] diff a number of different ways we could [27:01] have decided to do this uh but I decided [27:03] to sort of follow the model that I'm [27:05] most familiar with uh partially because [27:07] I was you know running a little bit on [27:09] trying to get these all put together so [27:11] we're going to use what's called a flat [27:12] closure [27:13] representation uh with a flat closure [27:15] there is one slot for the code pointer [27:18] and one slot for each of the free [27:20] variables that's needed so just to give [27:22] you an idea of what that looks like [27:24] let's imagine we have these nested [27:26] lambdas here and we want to figure out [27:29] what the closure looks like for the [27:30] innermost Lambda so we do a free [27:32] variable analysis and we figure out that [27:35] X and Y are free variables in the [27:37] innermost Lambda because they aren't [27:40] arguments they actually come from the [27:42] outer lambdas here so when we create a [27:45] closure for the innermost Lambda we need [27:48] to have one code slot and two data slots [27:52] one for the X and one for the Y and [27:55] that's how we're going to represent [27:56] things internally [27:59] so what about C I mean how are we going [28:02] to represent all of this in C and one [28:05] one approach that we could have taken is [28:07] to represent uh our closures by building [28:10] new data structures that represented [28:12] each closure we could represent our [28:15] Pairs and boxes and things like that as [28:17] data [28:18] structures um but you know I I don't [28:22] like to do that kind of stuff admittedly [28:24] some of this is because I'm used to [28:26] generating assembly and I kind of like [28:28] to play with the low low low LEL [28:30] representations so we're just not going [28:32] to tell C what we're doing at [28:34] all because you know what c really [28:36] doesn't care c c is happy to do whatever [28:39] you want with a pointer and that's what [28:41] we're going to do so maybe not the [28:43] safest C code we're going to have to [28:45] trust our compiler is going to generate [28:46] the right [28:48] stuff so instead what we're going to do [28:50] is we're going to just play with the [28:51] memory directly when we need space we'll [28:53] allocate some space when we represent a [28:56] fixed num that'll just be anointer [28:59] so uh so with all of that said uh let's [29:02] take a look at this and uh let me adjust [29:05] my screen [29:09] here this works out so much better if [29:12] the displays are [29:15] mirrored all right [29:19] so yeah yeah copyright [29:22] uh you know I put that in there mostly [29:25] just so that I can put a like an MIT [29:27] copyright on these things [29:28] MIT style or BSD style copyright so this [29:32] is all the stuff this is what's out [29:33] there on the uh the GitHub actually [29:35] these are all the random things we're [29:37] we're exporting the important thing from [29:39] our export list is we've built this as a [29:40] little library and we have uh the main [29:43] entry function my tiny compile which is [29:46] going to compile things for us uh using [29:49] GCC as the back end and uh actually [29:52] reread the value we're actually going to [29:54] do everything from inside scheme so that [29:56] we don't have to actually like touch C [29:58] that would be nasty um and then we can [30:00] trace our passes and see what it's [30:02] actually [30:03] doing uh so uh I I took like 10 minutes [30:07] and looked up the bom garbage collector [30:09] to see if I could get a garbage [30:10] collector running but and I sort of ran [30:11] out of time to test it so uh you can [30:14] actually turn this on and in theory it [30:16] should generate code that will use the [30:17] bom collector but uh in practice may [30:23] not okay so we have a representation for [30:26] our data types and so the fix and um tag [30:29] is just zero we have our pair tag is one [30:32] you know two for our box tag three for [30:34] our Vector tag uh four for our closure [30:37] tag we have more tags that we could use [30:39] um but uh we have a representation for [30:43] our true and our false values a little [30:45] tag for booing just to make booing [30:47] question mark a little simpler and a a [30:51] record for our fix num shift here so [30:53] that we know that we need to shift the [30:54] thing three bits up when we want to make [30:56] a change to it or three bits down after [30:58] we've done operations like multiply and [31:01] divide um and our word size just so that [31:03] we know that we've got eight bytes here [31:05] in each of our [31:07] words um and then we've got some stuff [31:10] here for taking care of like unique [31:12] variables and our list of Primitives [31:15] which should all be cleaned up my my [31:16] to-do here which didn't actually get [31:18] done o and my misspelling of should sad [31:22] all right and then uh we have a number [31:24] of language [31:26] definitions um so you can kind of uh [31:29] look through these I actually included a [31:32] potentially out ofd comment with the uh [31:35] the full language in here but most of [31:36] these languages are generated this way [31:39] and they can actually be regenerated by [31:40] loading the library and loading the [31:42] nanopass framework and then just saying [31:44] language Arrow s expression and it will [31:46] give you the full the full language [31:49] definition um and then we have all of [31:52] our passes uh so the first pass the [31:54] Parson rename pass uh yeah it's a little [31:57] long which is why I didn't end up [31:59] talking about it we're doing something [32:01] that's a little bit macro expand here in [32:03] that we're defining this initial [32:05] environment and this is really all I [32:06] wanted to show from this uh so because [32:09] we're in scheme our keywords can be [32:11] overwritten and we need to have an [32:13] environment as we read in the code to [32:15] know which thing we're actually [32:16] referring to uh so we we want to make [32:19] sure that if if someone binds a variable [32:21] called quote we don't then see all of [32:23] the calls to quote as uh quotes So we [32:27] use an initi environment and then as we [32:29] rebind new things we just extend the [32:30] environment and that's the idea there uh [32:34] so since I'm running a little short on [32:35] time here let's actually take a look [32:38] at [32:40] uh this example code [32:44] here so I I intentionally shrink my [32:46] history so that I'd only have a few [32:48] things in here so I cheated a little bit [32:51] um so we are going to import this and [32:53] you know it is a little bit slow to [32:55] import there's a couple thousand lines [32:56] of code that's actually in the uh in our [32:59] compiler itself plus there's all the [33:00] nanopass code and then the nanopass code [33:03] generates a whole heck of a lot of code [33:05] so we tend to uh uh get a little bit of [33:08] slowdown there but let's let's do our [33:10] first tiny little program uh originally [33:13] I was just going to test this for two [33:15] programs and make sure that those two [33:16] programs worked the program five and [33:19] factorial um so let's test the program [33:22] five okay so that worked that was good [33:26] it it compiled five through all 27 [33:28] passes it wrote A C file to the file [33:31] system it told the C compiler to compile [33:33] it it ran the program the program output [33:35] was written to the file system and then [33:36] we use a schem r to read that back in [33:38] that all that's what happened [33:40] [Applause] [33:44] there [33:46] thanks thanks okay so so we have our [33:49] other F our other program factorial and [33:51] we're going to run factorial of 10 [33:53] because this is a compiler there's no [33:55] reason for us to limit ourselves to five [33:59] it's also reasonably fast uh so that's [34:01] that's our answer there uh and I know it [34:04] might seem like hey how how do I know [34:07] that you're actually doing anything here [34:09] um so we're going to turn on our Trace [34:12] passes and we'll run the same program [34:16] again okay that actually went by too [34:19] fast uh this is the stuff this is the [34:22] stuff that it [34:24] generated okay all right we're somewhere [34:26] around the start here so you can see you [34:28] know we start we start running our our [34:31] initial pass here Parson rename and then [34:34] we run our remove one armed if and you [34:36] know some of these passes aren't going [34:37] to do anything really they're just going [34:39] to recur through the code and generate [34:41] the exact same thing that came in [34:43] because none of those pieces are [34:44] actually there we don't need to do [34:46] anything with those things um but there [34:49] are certain parts that are going to do [34:50] transforms and as we get through this [34:52] whole thing we're eventually going to [34:53] get to uh some C code the C code is also [34:56] entirely generated from inside scheme uh [34:59] so if you go and look at the code [35:01] there's a bunch of printfs that print f [35:03] printfs um in order to do this stuff um [35:07] this was less fun to write by the way [35:09] this is this is the downside of not [35:11] having not using the data structures [35:13] that c provides is that you end up doing [35:15] things like casting to a long a [35:17] reference of a pointer that you cast to [35:19] a long to do the math on the [35:24] pointer okay so have an idea of what's [35:28] going on here now and uh let's go back [35:30] to the slides for a [35:33] second okay so we have a little compiler [35:36] what else can we do right I mean it does [35:38] a little a little thing and it runs at [35:39] least two programs um I actually did [35:42] test it on some other programs and I [35:44] fixed my Vector representation for those [35:46] people who I was talking to and I had [35:48] had a broken Vector representation but [35:50] one of the things we could do is add a [35:51] different backend I mean you know C is a [35:54] fine Target for us but we could also [35:56] Target you know JavaScript or closure or [35:59] the jvm or net whatever we want really [36:02] llvm uh I've really been wanting to play [36:05] with llvm but I haven't had a chance to [36:06] yet so that would be a fun one um we [36:09] could also add more Primitives and data [36:11] types you know there's a lot of data [36:12] types that I that I think are really [36:14] neat in closure that I would love to add [36:16] uh to a scheme implementation so that I [36:18] can use them in a scheme implementation [36:20] of course I I should probably also you [36:22] know use some closure um we could also [36:25] add more optimizations and of course [36:27] this is my favorite thing to do because [36:29] uh part of the reason why I love [36:30] compilers is I love fast and uh these [36:33] are to make things fast and we could add [36:35] more runtime factors like GC which may [36:37] or may not work um but we could also add [36:40] things like foreign function calls and [36:41] things like that uh another thing is we [36:44] could Port it to closure uh I would love [36:46] to Port it to closure uh sadly I don't I [36:48] don't know closure yet but I it's on my [36:50] list of things to do um and we could do [36:53] a couple of things here we could Port [36:54] compiler uh using just core match uh [36:57] sort of the internal representation I [37:00] suspect this would be faster than our [37:01] match this I think would be the easier [37:03] task uh the other piece is we could [37:05] actually Port the framework to use [37:07] closure macros and to use a more closure [37:09] like syntax and to feel generally more [37:11] closy I think this is going to be a bit [37:13] harder um harder partially because right [37:16] now the entire thing is written using [37:18] these gigantic syntax case macros uh [37:21] which is part of the reason why I know [37:22] that we can do arbitrary computation [37:23] with syntax case uh cuz believe me I do [37:26] arbitrary computation [37:29] uh and uh but but you know there's [37:32] nothing missing for us doing this it's [37:33] just the the work of getting it done and [37:35] figuring out how the all the pieces fit [37:38] together um and with that uh I'd like to [37:40] say thanks I have a ton of links here [37:44] the compiler the framework uh my email [37:47] if if that's the one to remember if you [37:49] get lost on everything else because I I [37:50] can respond with everything else the [37:53] Twitter which I suppose is also useful [37:54] because I can also respond on that one [37:57] uh my page where I will post this stuff [37:59] and then this stuff runs on Sha scheme [38:01] unfortunately the scheme compilers they [38:03] are not all so close together uh I think [38:07] it should run on Icarus and vicari [38:09] although I have not yet tested it on [38:10] those platforms but it should be [38:11] supported on those um and I think I have [38:14] just like a minute for [38:17] questions and I can't see very well so [38:20] if someone has a [38:23] question yeah [38:31] [Laughter] [38:42] Rel other paramet yeah so uh I haven't [38:46] thought about it in that quite that way [38:48] uh I do sit next to will bird uh so we [38:51] we have actually talked about uh some of [38:53] the ideas somewhat somewhat in the [38:55] context of actually like uh writing a [38:58] type Checker that you write with a pass [39:00] like this uh that is actually written in [39:03] a relational style and many of the [39:05] passes are written in a relational style [39:06] in fact the if that you saw could have [39:09] been done as a relational thing right [39:11] it's just a term rewriting at that point [39:13] and like any term rewriting it could be [39:15] done relationally [39:16] so uh [39:18] yeah what do you do [39:21] about that have a lot more output [39:23] than control flow some [39:28] yeah yeah so uh uh we produce a control [39:30] flow graph um so passes actually don't [39:34] have to produce uh an a they can produce [39:37] things of different types and what we [39:39] used to do was we we sort of produced an [39:41] that had the information about the [39:43] control flow graph embedded in it uh it [39:45] turns out that's not necessarily the [39:47] best way to write your register [39:48] allocator so what we did instead was [39:51] have it generate the graph for us and [39:53] then the graph gets passed through a [39:54] couple of uh graph oriented pass and [39:57] then it gets turned back into an as when [39:59] we're done with that process so you know [40:02] this the idea behind this framework is [40:04] to write these little passes because we [40:05] can write these little passes but we [40:07] can't always write these little passes [40:09] so in particular like the Shea Source [40:11] Optimizer doesn't use the style of these [40:14] tiny passes because the things that it [40:16] do that it does in order to to get the [40:19] performance that it gets it combines [40:22] several different optimizations at the [40:23] same time that are mutually beneficial [40:25] and so it's actually quite a big pass [40:27] even though you know it's using the [40:28] nanop pass framework to build it so [40:30] you're never limited this is more to [40:32] enable you to write more in this style [40:35] so and I think I'm I'm passed out of [40:38] time so I'll leave the rest of the [40:40] questions for after thank you [40:45] [Applause]