Andy Keep - Writing a Nanopass Compiler

See also, Andy Keep's dissertation [1] and his talk at Clojure/Conj 2013 [2]. I think that the nanopass architecture is especially well suited for compilers implemented by LLMs as they're excellent at performing small and well defined pieces of work. I'd love to see Anthropic try their C compiler experiment again but with a Nanopass framework to build on. I've recently been looking in to adding Nanopass support to Langkit, which would allow for writing a Nanopass compiler in Ada, Java, Python, or a few other languages [3]. [1]: link [2]: ▶ this video [3]: link

Compilers come in all shapes and sizes. Some are single pass like Turbo Pascal. They directly generate machine code while parsing (no AST!). Niklaus Wirth (Pascal/Modula/Oberon guy) wrote a book following this approach [1]. Some have multiple passes like Chez Scheme. They have many simple passes, which they call a "nanopass". Andrew Keep has a great talk on this approach [2]. In practice, most compilers today are multi-pass, though probably not as many Chez. If we look at Rust, they go from AST -> HIR -> MIR -> LLVM IR -> machine code [3]. There are probably more things going on from LLVM to machine code, but I'm not knowledgeable enough to comment on it. I think the trade-off here is clear: less passes -> shorter compile times, more passes -> faster code generated, more modular compiler. Martin Odersky (Scala guy) has a paper attempting to get the best of both [4]. [1] link [2] ▶ this video [3] link [4] link

Many suggest resources for compiler implementations, i personally would start prototyping the language itself, think about it's type system and its runtime properties. There are many possibilities in terms of type systems, from static to dynamic and everything in between, concepts like linear types, algebraic types, etc. Runtime properties are things like it's memory model (garbage collection, yes or no). All of this depends on the purpose of your language. The second part would be choosing a platform to run on (so you only have to write a compiler frontend). There are many great technologies to host a language, but i'd advocate two specific ones here: * link (shoutout to @love2code) * link ZetaVM is a great target for dynamicly typed and/or jit compiled languages like python or javascript. LLVM is used in many low level / near metal languages like C, C++, rust and so on. None of both must be your final targets, your compiler frontend can be moved to target another platform like the JVM later. As a last part, implement your compiler frontend. This involves lexing/parsing source code, type checking if needed and generating your target's intermediate representation. I personally prefer hand-written recursive descent parsers using a parser combinator framework (like link ) over parser generators. For further processing like type checking, there is the common monolith aproach and the nanopass framework/approach ▶ this video Also there's a great series on compiler frontends by Al

Is this preceding work to the tour de force that is the Chez Scheme incremental like 40+ Scheme compiler. I mean, Cisco bought it, probably to hide it from us all. It must be worth something. ▶ this video link link