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

61–70 of 120 posts

Re: TinyCompiler: A compiler in a week-end

#61

Post by rurban »

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.

    (a + c/2) * sqrt(b)
is not a simple language.

    (* (+ a (/ c 2)) (sqrt b))
would be a simple and precise to parse language, and the typical compiler for this is written in a day. Search for SIOD

Re: TinyCompiler: A compiler in a week-end

#62

Post by Tomte »

RossBencina wrote: post #32
sieve wrote: post #27

Earlier quoted context omitted.

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

> javac (or any compiler targeting the JVM) is not a real compiler according to it I think it depends on how you interpret my "non-trivial transformation into or out of an intermediate and/or target representation". For example if javac involves IR, SSA based analysis and transformation (which I assume it does) then that would be a non-trivial transformation and I'd call it a compiler. If on the other hand it was a d…

javac does very, very few things. It intentionally emits byte code close to the source program. The HotSpot compiler in the JVM does the heavy lifting.

Re: TinyCompiler: A compiler in a week-end

#63

Post by PhilipRoman »

andai wrote: post #18
whartung wrote: post #16

Earlier quoted context omitted.

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.

Is that really the hard part? I figured that part out before I knew much programming: made a simple Excel type formula parser. (A horrible, horrible solution based around replacing strings and manually counting parentheses... but it worked!) I never got much farther than that though, I've looked into making a compiler many times and got overwhelmed every time.

Good to know I wasn't alone in writing terrible expression parsers. Since I knew absolutely nothing about parsing, my parser/interpreter consisted of splitting on whitespace, followed by linear scanning to find the most high precedence operation, repeated until a single token remains (basically how a human would do it).

Re: TinyCompiler: A compiler in a week-end

#64

Post by haqreu »

milesrout wrote: post #28
whartung wrote: post #16

Earlier quoted context omitted.

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

I'd argue that Lengauer-Tarjan is overrated. While it is neat, it's premature optimization IMHO. Fully maximal SSA (at the entry of each block insert a phi-node for each variable) + dead code elimination (we need it anyways) is much simpler.

Re: TinyCompiler: A compiler in a week-end

#65

Post by sitkack »

RossBencina wrote: post #30
sieve wrote: post #29

Earlier quoted context omitted.

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.

There is a whole body of non-academic work aimed at practioners for implementing compilers.

Nils Holm's work https://t3x.org/

Teaching and Learning Compilers Incrementally - Jeremy Siek - RacketCon 2023 https://www.youtube.com/watch?v=43VA_QaTRT8

Nanopass https://nanopass.org/

original paper that was the basis for nanopass http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf

https://www.reddit.com/r/ProgrammingLanguages/comments/gnzra...

The Crafting Interpreters and the Thorsten Ball books

https://craftinginterpreters.com/contents.html

https://interpreterbook.com/ https://compilerbook.com/

https://www.phind.com/search/cm7efcpv000002e6hqdbfojex

Re: TinyCompiler: A compiler in a week-end

#66

Post by sitkack »

musicale wrote: post #43
zabzonk wrote: post #39

Earlier quoted context omitted.

From wikipedia: "Pascal was influenced by the ALGOL W efforts, with the explicit goals of teaching programming in a structured fashion and for the development of system software.[5] A generation of students used Pascal as an introductory language in undergraduate courses." Its grammar made it relatively easy to write compilers for the language, which could be done as undergraduate exercises. Of course, this did not m…

I have the greatest respect for Prof. Kernighan, but history hasn't been kind to C's unbounded arrays and strings, however convenient they may be for the programmer. Moreover, just two years after his critique, Turbo Pascal would come out with an environment that is still revered as a pioneering and exceptionally productive IDE. It outsold C compilers by multiple orders of magnitude in the mid-1980s. (And that's igno…

I really really dislike the, "Why Pascal is Not My Favorite Programming Language" esp when you have a horse in the race as he did.

Re: TinyCompiler: A compiler in a week-end

#67

Post by sitkack »

pjmlp wrote: post #60
sylware wrote: post #22

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

Circle frontend, that includes all C++17 (when it was current) and the Rust related extensions, was implemented by a single guy.

Relativity was discovered by a single guy.

Re: TinyCompiler: A compiler in a week-end

#68

Post by sitkack »

sylware wrote: post #22

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

QBE is ... problematic. The source has no comments, single letter variable names. It is not written to be extended by anyone else other than the author.

I would recommend libfirm over QBE by at least 10km.

https://libfirm.github.io/ https://github.com/libfirm/libfirm

Re: TinyCompiler: A compiler in a week-end

#69

Post by pjmlp »

sitkack wrote: post #67
pjmlp wrote: post #60

Earlier quoted context omitted.

Circle frontend, that includes all C++17 (when it was current) and the Rust related extensions, was implemented by a single guy.

Relativity was discovered by a single guy.

Which confirms complex matters aren't an issue, being able to handle them might be.

Re: TinyCompiler: A compiler in a week-end

#70

Post by contificate »

haqreu wrote: post #64
milesrout wrote: post #28

Earlier quoted context omitted.

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

I'd argue that Lengauer-Tarjan is overrated. While it is neat, it's premature optimization IMHO. Fully maximal SSA (at the entry of each block insert a phi-node for each variable) + dead code elimination (we need it anyways) is much simpler.

Typical implementations of Lengauer-Tarjan are often taken verbatim from Andrew Appel's book and involve higher constant factors than alternative algorithms - such as Cooper et al's "engineered" version of the usual fixpoint algorithm, which is very neat, simple, and performs well.

If you are saying that constructing SSA following the classical approach is a premature optimisation, perhaps you would prefer Braun et al's retelling of Cliff Click's SSA construction algorithm - which works backwards from uses to place phis and requires no dominance information to be computed.

Post reply on HN