My first fifteen compilers
composition.al
My first fifteen compilers
1–10 of 77 posts
Re: My first fifteen compilers
#2Favorite quote:
> There’s a wealth of tutorials, courses, books, and the like about how to write compilers. But if somebody believes that writing a transpiler isn’t fundamentally the same thing as writing a compiler, it may not occur to them to look at any of that material.
The basic argument is this: "compiler" isn't a term that needs to be limited from transforming a high-level input to a low-level output. Any program which is structured to map an AST to another AST, no matter the relative levels of abstraction, can borrow from many of the principles of modern compiler theory, including using many small passes rather than monolithic rewrites.
At a company I worked for, we compiled a high-level declarative expression language of our own devising into SQL and other back-end representations, including English. Is that a "compiler" as many see it? No. However, thinking about the problem like a compiler problem gave us lots of insights into how to architect our product; it let us draw on an existing wealth of knowledge to make improvements quickly and reliably.
Re: My first fifteen compilers
#3I suppose if you look at it that way, then anyone who has completed Crenshaw's excellent tutorial series[1] could also claim to have written (approximately) the same number of "compilers".
With a parser combinator library, you write a parser by starting with a bunch of primitive parsers (say, that parse numbers or characters) and combining them, eventually building up the ability to parse a sophisticated language.
That sounds like recursive descent, also a highly recommended method of writing a parser for its simplicity, speed, and ease of error reporting.
But if somebody believes that writing a transpiler isn’t fundamentally the same thing as writing a compiler, it may not occur to them to look at any of that material.
From what I understand, the definition of a transpiler is one which almost exclusively performs syntax-syntax transforms, and doesn't delve into the semantics with e.g. dataflow or control flow. Thus the lack of material about writing "transpilers" --- or rather, someone looking to write one should instead be seeking out information on "search and replace" algorithms.
[1] https://compilers.iecc.com/crenshaw/ --- highly recommended.
Re: My first fifteen compilers
#4I suppose if you look at it that way, then anyone who has completed Crenshaw's excellent tutorial series[1] could also claim to have written (approximately) the same number of "compilers". With a parser combinator library, you write a parser by starting with a bunch of primitive parsers (say, that parse numbers or characters) and combining them, eventually building up the ability to parse a sophisticated language. Th…
It is recursive descent. Scala's parser combinator library is beautiful, and has been, hour-for-hour, the most useful tool I have learned as a programmer. Parsing problems became so common once I understood how to parse things.
I'm writing my first compiled DSL right now, inspired by the sense that parser combinators gave me: "maybe you don't have to be a genius to write a compiler."
In addition to parser combinators, another great functional tool for dealing with recursive structures (e.g. abstract syntax trees) is recursion schemes. I've been banging my head against them this week, and I finally made some headway. They are useful for the nanopass technique referenced in the article.
Re: My first fifteen compilers
#5I wonder if scheme-based compiler courses are still run at Indiana University?
Abdulaziz Ghuloum's 'Incremental compiler construction' [1] also has a working compiler at the end of each stage. For example after the first week you have a compiler that outputs a program that prints a single integer, the 2nd week immediates. The tutorial is at [2]. It doesn't use a nanopass framework, just builds the complexity of the language. It's for a scheme compiler written in scheme.
Apparently Ghuloum was a phd student under Dyvbig who also wrote his own scheme compiler to x86 [3],[4].
[1] http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf
[2] https://raw.githubusercontent.com/namin/inc/master/docs/tuto...
[3] https://en.wikipedia.org/wiki/Ikarus_(Scheme_implementation)
[4] https://web.archive.org/web/20101210085823/http://www.cs.ind...
Re: My first fifteen compilers
#6This is an interesting instance of the sorites paradox :)
Re: My first fifteen compilers
#7Favorite quote: > There’s a wealth of tutorials, courses, books, and the like about how to write compilers. But if somebody believes that writing a transpiler isn’t fundamentally the same thing as writing a compiler, it may not occur to them to look at any of that material. The basic argument is this: "compiler" isn't a term that needs to be limited from transforming a high-level input to a low-level output. Any prog…
I'm curious what are the canonical references which state that a compiler does high-level to low-level transformations?
Re: My first fifteen compilers
#8Favorite quote: > There’s a wealth of tutorials, courses, books, and the like about how to write compilers. But if somebody believes that writing a transpiler isn’t fundamentally the same thing as writing a compiler, it may not occur to them to look at any of that material. The basic argument is this: "compiler" isn't a term that needs to be limited from transforming a high-level input to a low-level output. Any prog…
I'm curious what are the canonical references which state that a compiler does high-level to low-level transformations?
Googling "what is a compiler" returns this: "a program that converts instructions into a machine-code or lower-level form so that they can be read and executed by a computer." So, that's something.
It's hard to get more canonical than the Dragon Book. The Dragon Book (2nd Ed.) says this in section 1.2: "Up to this point we have treated a compiler as a single box that maps a source program into a semantically equivalent target program."
So, the most canonical source doesn't include an explicit mention of high-level to low-level (though there may be sources I'm missing). But in my experience, that's definitely the connotation. Otherwise, the term transpiler, which is connoted with not outputting low-level code, never would have arisen.
Re: My first fifteen compilers
#9I'd strongly suggest diving into compilers if you've never studied the subject. Learning a bit on the subject unlocks a ton of incredibly useful skills. That knowledge helps you implement stuff like autocomplete, linters, syntax highlighting, etc.
The Super Tiny Compiler [0] is a very gentle introduction to the subject. It's great because it helps you quickly develop an initial mental model.
To give an everyday usage example: I've used jscodeshift [1] many times to safely refactor large amounts of code. In one case, I quickly migrated a project's test assertion library to an alternative which the team agreed was superior. This tool is also typically used by the react team in order to provide a smooth migration path whenever they make changes to the public API.
Re: My first fifteen compilers
#10I'd strongly suggest diving into compilers if you've never studied the subject. Learning a bit on the subject unlocks a ton of incredibly useful skills. That knowledge helps you implement stuff like autocomplete, linters, syntax highlighting, etc. The Super Tiny Compiler [0] is a very gentle introduction to the subject. It's great because it helps you quickly develop an initial mental model. To give an everyday usage…
If people find getting started on a compiler to be a bit too intimidating, one good way to get your feet wet is implementing an interpreter for small subset of a language. Perhaps the basic arithmetic part of adding/multiplying/dividing integers.