Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My first fifteen compilers

composition.al

Post reply on HN
Print view View original

21–30 of 77 posts

Re: My first fifteen compilers

#21

Post by amelius »

eighthnate wrote: post #10
TheAceOfHearts wrote: post #9

I'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.

And ideally, your compiler will turn that interpreter into a compiler :)

Re: My first fifteen compilers

#22

Post by samth »

kristianp wrote: post #5

I 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 l…

Yes, we still have a similar course at IU. Here's the textbook for the current incarnation: https://github.com/IUCompilerCourse/Essentials-of-Compilatio...

Re: My first fifteen compilers

#23

Post by Athas »

I am very fascinated by this notion of teaching compilers by starting at code generation and working backwards from there. I've read about nanopass compilers before, but do they also work well if the compiler is written in a statically typed language? They clearly will for passes that do not change the program representation, but my experience is that it is awkward to define large amount of similar-but-slightly-different representations in a statically typed language.

Re: My first fifteen compilers

#24

Post by ris »

kornish wrote: post #2

Favorite 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…

> 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

Wow. Snap. Except we never got it to compile to English (well, we probably could have but the result would have had deeply nested bracketed clauses...)

Re: My first fifteen compilers

#25

Post by userbinator »

TheAceOfHearts wrote: post #9

I'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 you are interested in compilers at all, but not for Lisp-like languages, I would recommend studying this self-compiling C-subset compiler and virtual machine very, very carefully: https://news.ycombinator.com/item?id=8558822

Re: My first fifteen compilers

#26

Post by austincheney »

I find many people tend to use the terms parser and compiler almost interchangeably, which is a horrid mistake. These terms are not the same and are not related. So, lets get clear on terminology:

* lexer: A scanner. It runs code, typically as a string, through an evaluator and builds pieces based upon known language syntax rules.

* parser: A rule evaluator. Parsers typically use lexers to reason about code and then evaluate the pieces to determine context, relationships, and categories that describes the code structure.

* compiler: A transformer. Compilers change code from one format (syntax) to another different format.

---

> 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.

I do like that part of the article. I am working on a universal language parser right now. To be truly universal you have to accomplish two big goals:

1. parse all the languages

2. seamless interchange between the various different parsers (it is a single parser with interchange between the various lexers)

Seamless interchange is necessary for languages like JSX, which starts as JavaScript, but can contain XML code units that then escape back to JavaScript syntax. Another example is code blocks in markdown documents where the code block can specific a name of the language described by the code block.

Re: My first fifteen compilers

#27

Post by mseebach »

kornish wrote: post #8
sigjuice wrote: post #7

Earlier quoted context omitted.

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 equivale…

There's also the etymology, ie. the pre-computing dictionary definition: you compile eg. a list, ie. make something smaller/shorter from a larger input. You also write a book when it's an original work, but another author or editor might take parts of yours and other books and compile an anthology. You might translate a book from one language to another, but that's not considered a compilation.

Re: My first fifteen compilers

#28

Post by mseebach »

sjrd wrote: post #18
shakna wrote: post #13

Earlier quoted context omitted.

> But if somebody believes that writing a transpiler isn’t fundamentally the same thing as writing a compiler, I'd be surprised if anyone did. The use of transpiler is more about audience expectation, a specificity. It's shorter than writing "source-to-source compiler", and acknowledges compiler as its superset, right there in its name

That's unfortunately not my experience. I'm appalled every time someone tells me "But Scala.js is not a compiler, it's a transpiler, since it compiles to JS!" I assume other language users and authors suffer the same kind of comments on a regular basis.

I'd argue that it's a compiler if it treats JS as a lower language - that the output is simply an intermediate artefact for executing Scala on a JS engine, and not meant for human consumption. If, on the other hand, the output is meant to be developed further by hand, if the output is considered an equivalent and not lower representation, then it's a transpiler.

Re: My first fifteen compilers

#29

Post by mickronome »

I've always thought of compilers as usually lossy graph rewriters with input and output data structures usually being 'flatter' in some sense. Maybe a both simplistic and vague model, but it has served me well enough the few times I needed to build one.

This isn't meant to validate or invalidate any other view or definition, but I'm curious if there are any good counter examples or theoretical reasons for characterising compilers differently ?

Quite naturally, all compilers might not be implemented with explicit graphs and their subsequent rewrites, but implicitly both input and output represent a set of statements encoding a specific set of truths and actions, all of them which is intrinsically related to their various contexts.

In this light there is really no distinction between high level and low level targets, but only between various levels of information loss and how explicit the actions and truths are expressed in the input and output.

It might be worth noting that most of the perceived information loss, except for names, is only due to human perception and limitations. State of the art decompilers can in many cases recover a surprising amount of the original types and code structures, albeit at considerable computational costs.

Re: My first fifteen compilers

#30

Post by yorwba »

kqr wrote: post #20
eighthnate wrote: post #10

Earlier quoted context omitted.

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.

I disagree. I tried that approach for many years but without external input, I could never figure out how to transition from a simple expression language to a proven, working compiler architecture. While large compiler architectures work well for smaller languages, the opposite is not true. I have found it much better to pick a good introductory text and just work through the exercises.

You can turn an interpreter into a compiler by replacing all code that actually does something by code that prints out the code that does it in the target language. It takes a bit to wrap your head around it, and you won't get an optimizing compiler, but a compiler it will be.

So your values are no longer values in the interpreter's language, but descriptions in the target language for getting that value. To compile an expression, you first handle the sub-expressions, as in an interpreter, which prints the code to compute them. Additionally, you get such a value description for the return value of each expression. Then you can use those descriptions to print out code to get them into known locations (e.g. registers). Then you can print out code to perform your operation on the values in those locations and put the result in another location (e.g. on the stack). The return value of this compilation step is the description of that location.

Post reply on HN