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

TinyCompiler: A compiler in a week-end

ssloy.github.io

Post reply on HN
Print view View original

21–30 of 120 posts

Re: TinyCompiler: A compiler in a week-end

#21

Post by sieve »

RossBencina wrote: post #20
sieve wrote: post #8

Earlier quoted context omitted.

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.

> lexer + parser + treewalk interpreter If all you do is construct an AST and interpret it it's not really a compiler is it. It doesn't compile from source to target. At most you're describing a compiler front end (arguably), or an interpreter. I would expect: lexer + parser + AST definition and construction + semantic analysis/type checking + X + codegen to ASM/WASM/C where X includes - definition of an intermediate…

> If all you do is construct an AST and interpret it it's not really a compiler is it.

What if I dumped the AST to disk, called it "bytecode" and updated the "interpreter" to run this "bytecode"? Would you consider that to be a compiler? :-)

> where X includes

I don't consider any of these things to be essential. There are entire languages out there which run on interpreters of some kind. There are others which compile down to C/JS. Many compilers use LLVM as their backend. By your definition, none of them use (or are) compilers.

Re: TinyCompiler: A compiler in a week-end

#22

Post by sylware »

On the same way than cproc+QBE I guess, 70% of gcc speed in my benchmarks.

The more real-life alternatives to those abominations of gcc and clang, the merrier.

I wish the linux kernel devs did care to keep the door _reasonably_ open for such compilers (with assembler source files as alternative to inline assembly, some extensions avoidance and niche expensive compiler features).

This is another case of why super complex syntax computer languages should be avoided like hell (c++, rust, etc).

Re: TinyCompiler: A compiler in a week-end

#23

Post by n42 »

whartung wrote: post #16
sieve wrote: post #8

Earlier quoted context omitted.

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.

The hardest part (IMHO) about getting a simple language running, particularly for beginners, is the “expression”. Mostly for your typical algebraic style infix expressions with precedence. Just getting the grammar straight on the naturally recursive structures can be a trick. They also touch a large portion of the code generation and run time. Get: (a + c/2) * sqrt(b) working and you’re 80% there.

well, in my personal experience, parsing is the easiest part. it's what you do with the AST once you have one that is the hard part. but for some reason an overwhelming amount of writing is about frontends when you could teach the concepts to a layman with some boxes and arrows.

Re: TinyCompiler: A compiler in a week-end

#24

Post by RossBencina »

sieve wrote: post #21
RossBencina wrote: post #20

Earlier quoted context omitted.

> lexer + parser + treewalk interpreter If all you do is construct an AST and interpret it it's not really a compiler is it. It doesn't compile from source to target. At most you're describing a compiler front end (arguably), or an interpreter. I would expect: lexer + parser + AST definition and construction + semantic analysis/type checking + X + codegen to ASM/WASM/C where X includes - definition of an intermediate…

> If all you do is construct an AST and interpret it it's not really a compiler is it. What if I dumped the AST to disk, called it "bytecode" and updated the "interpreter" to run this "bytecode"? Would you consider that to be a compiler? :-) > where X includes I don't consider any of these things to be essential. There are entire languages out there which run on interpreters of some kind. There are others which compi…

> Would you consider that to be a compiler? :-)

:) No. Under my definition there needs to be some non-trivial transformation into or out of an intermediate and/or target representation (either syntax-directed directly out of the parser, or from a materialized AST). Personally I would argue that even if you trivially "compiled" to sequential bytecode, if the bytecode is then interpreted it is hard to argue that you have created a compiler (the pre-JIT cpython interpreter is still an interpreter, even though it includes a bytecode representation). But I can see that this point can be argued, and historically a school exercise of writing a Pascal-to-pcode converter would be called a compiler, so sure, you can take that perspective if you like. Just don't get confused about whether you are learning to build a compiler (definition 1) or a compiler (definition 2).

Re: TinyCompiler: A compiler in a week-end

#26

Post by RossBencina »

sieve wrote: post #11
sitkack wrote: post #10

Earlier quoted context omitted.

5 days if you don't, but have the right tutor.

If you know basic programming (js/python), a day is more than enough to get the concept across using a tiny language. Could probably be done in an hour. The problem, always, is people are given terrible reading recommendations which makes the subject more complicated than it is.

I never took a compilers course. The first reading recommendation I got was The Dragon Book. Perhaps not the worst starting place at the time (mid 90s) but my memory of it was that the book was front-loaded with automata and parser theory. At the time I didn't really make it past the front end. It would be interesting to see a compiler tutorial that started at codegen and worked backwards (or started at the ends: lexing and codegen, and worked towards the middle in alternating chapters).

Re: TinyCompiler: A compiler in a week-end

#27

Post by sieve »

RossBencina wrote: post #24
sieve wrote: post #21

Earlier quoted context omitted.

> If all you do is construct an AST and interpret it it's not really a compiler is it. What if I dumped the AST to disk, called it "bytecode" and updated the "interpreter" to run this "bytecode"? Would you consider that to be a compiler? :-) > where X includes I don't consider any of these things to be essential. There are entire languages out there which run on interpreters of some kind. There are others which compi…

> Would you consider that to be a compiler? :-) :) No. Under my definition there needs to be some non-trivial transformation into or out of an intermediate and/or target representation (either syntax-directed directly out of the parser, or from a materialized AST). Personally I would argue that even if you trivially "compiled" to sequential bytecode, if the bytecode is then interpreted it is hard to argue that you ha…

I have written all kinds of compilers, interpreters and vms over the last 15 years. A couple of them for work. The rest for fun. Some vms used RC, others did mark-and-sweep GC. Some vms even did JIT. A lot of them were simple treewalk interpreters because the point was to play with the syntax of the language.

Based on that experience, I would say your definition is more academic than realworldly as javac (or any compiler targeting the JVM) is not a real compiler according to it.

Re: TinyCompiler: A compiler in a week-end

#28

Post by milesrout »

whartung wrote: post #16
sieve wrote: post #8

Earlier quoted context omitted.

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.

The hardest part (IMHO) about getting a simple language running, particularly for beginners, is the “expression”. Mostly for your typical algebraic style infix expressions with precedence. Just getting the grammar straight on the naturally recursive structures can be a trick. They also touch a large portion of the code generation and run time. Get: (a + c/2) * sqrt(b) working and you’re 80% there.

I think the hardest part is function calls. Implementing the standard calling convention is really fiddly and annoying when you have to save and restore registers around function calls if you want to do it efficiently (keeping track of which registers are dirty, doing parallel loads of registers into the right argument registers, spilling when appropriate, etc. It is fiddly.

The alternative is going to an IR and doing full register allocation but then you need to implement Lengauer-Tarjan to get into SSA, all the same parallel load stuff for phi functions/block arguments, out-of-SSA, reconstruct in optimisation passes all the information you discard by going to a linear IR, etc.

Re: TinyCompiler: A compiler in a week-end

#29

Post by sieve »

RossBencina wrote: post #26
sieve wrote: post #11

Earlier quoted context omitted.

If you know basic programming (js/python), a day is more than enough to get the concept across using a tiny language. Could probably be done in an hour. The problem, always, is people are given terrible reading recommendations which makes the subject more complicated than it is.

I never took a compilers course. The first reading recommendation I got was The Dragon Book. Perhaps not the worst starting place at the time (mid 90s) but my memory of it was that the book was front-loaded with automata and parser theory. At the time I didn't really make it past the front end. It would be interesting to see a compiler tutorial that started at codegen and worked backwards (or started at the ends: lex…

The Dragon Book is terrible as an introduction. There are better books I would probably recommend, but not to a beginner. The best "complete" intro out there today is Nystrom's Crafting Interpreters.[1]

[1] https://www.craftinginterpreters.com/contents.html

Re: TinyCompiler: A compiler in a week-end

#30

Post by RossBencina »

sieve wrote: post #29
RossBencina wrote: post #26

Earlier quoted context omitted.

I never took a compilers course. The first reading recommendation I got was The Dragon Book. Perhaps not the worst starting place at the time (mid 90s) but my memory of it was that the book was front-loaded with automata and parser theory. At the time I didn't really make it past the front end. It would be interesting to see a compiler tutorial that started at codegen and worked backwards (or started at the ends: lex…

The Dragon Book is terrible as an introduction. There are better books I would probably recommend, but not to a beginner. The best "complete" intro out there today is Nystrom's Crafting Interpreters.[1] [1] https://www.craftinginterpreters.com/contents.html

> There are better books I would probably recommend

I'm curious what you'd recommend.

For what it's worth my goal was to compile to machine code. Anything less would have seemed insufficient. Later I got Appel's "Modern Compiler Implementation in Java" and Allen and Kennedy "Optimizing Compilers for Modern Architectures".

Cooper and Torczon "Engineering a Compiler" was recommended here recently. I haven't seen it.

Post reply on HN