u/cutculusin r/ProgrammingLanguages • Recommends
Writing a Nanopass Compiler - Andy Keep (ClojureConf 2013 video)
0:00 / 0:00
Andy Keep - Writing a Nanopass Compiler
ClojureTV
111K subscribers • 135 videos on Hallway
- Recommended by 5 people: 1 on Hacker News, 1 on Lobsters, 2 in engineering communities and 1 curated list.
- A classic. People kept recommending it from 2014 to 2020.
- Presented by Andy Keep
Intermediate. Assumes working knowledge.
28K views12 years ago5 recommendations
Systems programmingProgramming languagesCompilers and interpretersLanguage design and type systemsFunctional programming
Andy Keep explains the nanopass compiler framework, which manages compiler complexity by using many small, single-task passes with formally defined intermediate languages.
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.Why it's here
5 people recommend thisWhat people say. Recommended as a great introduction to the nanopass compiler architecture and its origins in teaching compiler construction.
programming-talkscurated list on GitHubRecommends
Under “Compilers/Interpreters”
Writing a Nanopass Compiler 00:40:48 by **Andy Keep** (2014)
undecidaboton Hacker News • Recommends
On “MLton Compiler Overview”
…. 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 link to this video 3 link 4 link…
u/johnfrazer783in r/ProgrammingLanguages • Mentions
On “From a PL perspective, how significant are the "shortcomings" of LaTeX?”
> weirdness ... age ... multi-pass compilation model
I cannot quite agree to this. The flaw is not with *needing* multiple passes to compile a document; this has actually become a very recent trend in compilation, vz. nanopass compilers where you pass over the source and its transformations a *lot* of times.
Rather, I think the flaw is with TeX refusing to do this *automatically* and leaving it to user intervention. You always have to read one pass's output and then decide whether or not to do another pass, which quickly gets old. When I did quite a bit of TeX one of the first things I built was a very simple tool to automate this step (by looking whether the contents of the `*.aux`…
u/Roboguy2in r/ProgrammingLanguages • Mentions
On “Does anyone have issues with tightly coupled implementations?”
I've run into this before.
One approach that helped me a lot, and is often used, is to use multiple passes. You can set it up so that each pass only does one thing. For example, you could have something like this:
1. Parse
2. Type check
3. Closure conversion
4. Defunctionalize higher-order function applications
5. Constant expression folding
6. Loop unrolling
7. Inlining
8. Translate into an intermediate language with only conditional jump instructions, no loops (and no other differences from the language from the previous pass)
9. Eliminate tail recursion
10. Code generation
Each pass only has to worry about solving one problem. You could subdivide some passes further, if a pass becomes…
u/Deadly_Mindbeamin r/compsci • Mentions
On “Does anyone know of any good resources for building a compiler?”
I've heard good things about "Let's build a compiler" and another good idea is nanopass compilers, see http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf and a cool video link to this video
616con Hacker News • Mentions
On “An Incremental Approach to Compiler Construction (2006) [pdf]”
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. link to this video link link
vengariothon Hacker News • Mentions
On “Ask HN: Resources for building a programming language?”
…sing 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 link to this video Also there's a great series on compiler frontends by Al…
LiamPowellon Hacker News • Mentions
On “Want to Write a Compiler? Just Read These Two Papers (2008)”
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: link to this video 3: link
u/rlpin r/ProgrammingLanguages • Mentions
On “Dumbing down the syntax tree?”
If you'd like an extreme example of this, check out the nanopass compiler framework, which uses lots of passes with slightly different trees. Here's a good talk by the creator
u/mttdin r/ProgrammingLanguages • Mentions
On “The Nanopass Framework as a Nanopass Compiler - ELS 2020”
….edu/~dyb/pubs/nano-jfp.pdf
- Nanopass Compiler Infrastructure
- 2008 PhD Thesis; Indiana University; Dipanwita Sarkar
- https://dl.acm.org/citation.cfm?id=1570904
- https://search.proquest.com/openview/b5126e30af6bce9eec3308a0739eb535/1?pq-origsite=gscholar&cbl=18750&diss=y
- Writing a Nanopass Compiler
- ClojureConf 2013; Andy Keep
- link to this video
- previously discussed here: https://www.reddit.com/r/ProgrammingLanguages/comments/f81tv4/writing_a_nanopass_compiler_andy_keep_clojureconf/
- My First Fifteen Compilers
- Lindsey Kuper; Jul 9, 2019
- https://blog.sigplan.org/2019/07/09/my-first-fifteen-compilers/
- Tock (Translator from occam to C from Kent) - written in Haskell,…
u/fullouterjoinin r/ProgrammingLanguages • Mentions
On “whats the best way to model a compiler using object oriented programmng?”
Great video by Andy Keep on Writing a Nanopass Compiler
u/oilshellin r/ProgrammingLanguages • Mentions
On “Representing ASTs as byte strings with with small integers rather than pointers”
Yeah this is something I'm starting to learn about.
I think I had read the paper a long time ago and they talked about performance. And I just watched a few videos on it, some by his students:
link to this video
That one talked about how Chez Scheme is 57-passes. It seems like it is fast enough even so? I didn't really know the details of Chez Scheme, but it seems like an impressive piece of work. I always look for validation that something is used to solve real problems, and it looks like it meets that bar.
I also watched a video on the Scala compiler by Odersky, and he the Scala compiler is also VERY deep. Maybe 50+ passes? However he did mention that speed an issue? That's kind of interes…
u/max_maximain r/ProgrammingLanguages • Mentions
On “A random idea - dynamic typing, static nullability”
> Define "State of the art"?
ChezScheme: https://github.com/cisco/ChezScheme
Nanopass: link to this video
> The D compiler has been around for a decade and it's pretty fast.
Is we are going to take years as a factor, Chez scheme has been around since 1985.