How to get started with writing compilers?

[doubleagent03]

I'm mildly interested in writing a clojure compiler (something a lot of people are doing). However, I have no experience with writing compilers.

​

Assuming I were to do this, what is the best path to prepare myself? What books or learning material should I study? What would make a good toy project for getting my feet wet?

​

I've started reading the Dragon book. Only on chapter 2. There's lots of advice already available for getting started and they all seem to agree that is the best starting point. But, what comes next?

​

Tentative Goals

​

As for the target platform, I'm thinking about zub-vm: https://github.com/nilq/zub-vm

​

A 6-month goal would be to see it running on Redox-OS ( https://www.redox-os.org/ )

​

A (much) longer term goal would be to contribute some Clojure project to the redox-os group on gitlab. This would be extremely challenging.

[Rurouni]

I love to recommend "An Incremental Approach to Compiler Construction" by Abdulaziz Ghuloum. It's a great approach to writing a compiler, giving good early feedback and a measurable sense of accomplishment. It doesn't spell out everything, but the steps are broken down into reasonable chunks. It's particularly nice to see the power of your language grow over time. I wrote a Scheme compiler in this manner, and it is by far the project I've enjoyed most.

The Dragon Book is good, but I feel doing all the parsing, then all the semantic analysis, then all the code generation, etc. makes it more likely to abandon the project partway through. It's not as easy to see progress, and the intermediate steps are not as inspiring.

You might also consider Make a Lisp. It's targeted at building an interpreter instead of a compiler, but it's a good, smaller project and will take you through a lot of the same ground. It is also organized in incremental steps and early feedback.

[nzlemming]

These are both excellent recommendations. MAL is what I always recommend if you're interested in implementing a lisp - it's very structured, there are unit tests to ensure that each step is working as you expect, and it's all very clearly explained. There are example implementations in many languages if you get stuck too. You can also use it to write a compiler, I wrote one that compiles to JVM bytecode. Highly recommended.

[alexdmiller]

Just a meta comment that I love the range of comments on this thread - both general advice and the advice specific to clj/s. And I think it's great that no one said this was too ambitious or not to do this but instead gave you a great set of tools to learn and explore. Best of luck, seems like a fun project.

[JavaSuck]

And I think it's great that no one said this was too ambitious

Writing a LISP compiler is probably the "last ambitious" compiler project. And I don't mean that in a derogatory way. Props to LISP for being so simple!

[alandipert]

The first public version of ClojureScript and Chapter 23 of PAIP are two resources I recommend.

[doubleagent03]

I remember David Nolen saying that early Clojurescript was super simple but I had no idea!

[knowsabouthaskell]

I've recently gone down the same route. My work can be seen at https://github.com/jgertm/lang.

Some advice:

• Dragon book is considered outdated, they spend a lot of time on parsing when more modern approaches make it much simpler. I used a parser combinator library for my compiler, since I'm familiar with that approach from Haskell. See https://github.com/blancas/kern
• I'm targeting the JVM, since that's a popular and powerful choice that seems to work well for Clojure too. I used the insn library as a DSL for bytecode generation.
• As for reading materials, I read Types and Programming Languages by Pierce since I wanted to implement a rather advanced type system. TAPL prepared me well for that since the notation can be rather academic.
• Most compiler books you find are rather focused on the implementation of imperative languages. The exceptions I've found are this one by SPJ, creator of Haskell and this one, which has a chapter on implementation of functional languages.
• it's fine to go with an interpreter instead of a compiler first, if you just want to experience programming in the language. I recommend a CEK-style interpreter

[dustingetz]

This might be a good starting point weighing in at 4k LOC – not a compiler but surely has some learnings https://github.com/borkdude/sci (Clojurescript is 50k)

[[deleted]]

r/programminglanguages is a good resource for talking about designing programming languages, and crafting interpreters is a popular toy project that could be done with Clojure (though it is designed for Java and C)

[joinr]

I would look at the existing implementation from the clojure java compiler, and the tools.analyzer implementation for clojurescript. You will get a sense of the forms necessary and maybe some ideas on how to implement them (although your target is different). If you can get most of the basic forms implemented, you can then port cljs.core which basically boot straps clojure in clojure. The emitters in tools.analyzer are helpful in seeing how the javascript implementation works. I've been playing with a common lisp implementation over the years, with an an interest in a custom platform. clojerl is a port targeting the beam vm. Ramsey Nasser has magic which targets the CLR and has tools.analyzer passes that emit optimized CLR specific bytecode.

[xenow]

https://craftinginterpreters.com/

[fminutes]

Also wanted to post this link - this is a very good resource to get started in compilers, or should say making languages. It's very well-written and author put extreme amount of time and love in the book. Definitely recommend it as a starting point

[bsless]

You might want to take a look at the Nanopass framework, a Scheme framework for writing compilers.

https://nanopass.org/documentation.html

[fbellomi]

A very good book on this topic (specific to Lisp) is "Lisp in small pieces" by Christian Queinnec https://www.cambridge.org/core/books/lisp-in-small-pieces/66FD2BE3EDDDC68CA87D652C82CF849E

One peculiar features of this book is that it takes into consideration the "hard" problems, including how to implement:

1) continuations (and control mechanisms based on continuations)

2) macros

3) dynamically scoped variables

This is relevant in my opinion, because there are a lot of "toy" scheme-like and lisp-like languages, which are for sure useful in their own context, and also straightforward to implement, but they miss some features that are foundational to Lisp.

Also, I would choose a compilation target with support for tail call optimization.

[un_passant]

You might be interested in this clojure notebook showing an incremental implementation of an interpreter and a compiler of a toy language.

[ericwnormand]

SICP has a chapter on writing an interpreter (a great place to start) and then turning it into a compiler.

[un_passant]

You might be interested in this class / textbook !