11 ms·

Resources for Amateur Compiler Writers

339 points by kilodeca 5y ago

nethunters 5y ago
Any similar resources on writing interpreters? Also is there are a technical difference between an interpreter and a VM?
- MH15 5y ago
  Interpreters usually execute by walking the abstract syntax tree at runtime, bytecode VMs usually execute actual bytecode similar to machine code. The bytecode for such VMs is often way simpler than the instruction set for an actual computer, so it's far more portable between platforms.
  - nethunters 5y ago
    Thanks for clearing that up. Which languages or implementations of languages directly interpret the AST without the intermediary bytecode compilation? I know Python, Java and JavaScript (V8 and SpiderMonkey) all compile to bytecode first probably to speed up subsequent runs and run some optimisations on the bytecode. What other benefits are there to compiling to bytecode first vs directly interpreting the AST?
    - herohamp 5y ago
      Portability. Say I wanted to make language X run on all platforms, but I didn't actually care about compiling it on all platforms. I can just write a relatively simple VM for each platform. This is one of the reasons Java was and still kinda is so ubiquitous
      - nethunters 5y ago
        Wouldn't writing an interpreter for each platform be less work and achieve the same goal as writing a VM for each platform? Edit: ^Aside from being able to execute the bytecode on any platform
        kaba0 5y ago
        As others mentioned, source code should be distributed that way, and I think creating a simple VM is easier than a simple language parser. But of course, an optimizing one can be really quite complex in both cases.
        klyrs 5y ago
        Why would it be less work? The interpreter will need to implement whatever operations a VM can perform, so a priori it's at least as much work. Bonus, if you can bootstrap the source->bytecode process, then you only need to write (and compile) that once to get a full-fledged interpreter on every host with a VM
    - CalChris 5y ago
      If you compile to AST and walk that then your portability is at the source level; you have to send the source over the wire; each target then needs a parser+walker and each target needs to parse+walk. If you compile to bytecode you can send bytecode over the wire and then simply interpret that bytecode.
    - jhgb 5y ago
      Gambit Scheme, CLISP, CMUCL are capable of interpreting ASTs, and I believe (although I'm not 100% sure) that this is the case for Lispworks and Allegro CL as well. Also, Ruby until version 1.8.
    - smueller1234 5y ago
      Perl is a tree based interpreter. It's not exactly an AST anymore but the time it's being executed, but close enough.
    - IainIreland 5y ago
      One major benefit of compiling to bytecode first is that bytecode is a more convenient shared source of truth. For example, SpiderMonkey has two interpreter and two compiler tiers. The output of the parser is bytecode. We can interpret it immediately, and it's a convenient input to the compilers. It also simplifies transitions between tiers: for example, when we bail out of Warp, we resume at a specific bytecode offset in the baseline interpreter. I'm not sure how you would resume at a particular point in the execution of an AST-based interpreter without agreeing on a linearized traversal of the AST, which is 90% of the way to bytecode.
  - tom_mellior 5y ago
    > Interpreters usually execute by walking the abstract syntax tree at runtime, bytecode VMs usually execute actual bytecode similar to machine code. This isn't the right way to separate these concepts. A VM that executes bytecodes by interpretation is also an interpreter (Python, Ruby, PHP are well-known examples). Many VMs don't interpret, or they interpret mostly during startup, but actually try to compile hot parts of the code and execute that machine code rather than interpreting (Java and JavaScript VMs are well-known examples). The VM part more properly refers to things like data representation and memory management. Interpreters of an abstract syntax tree, interpreters of bytecodes, and just in time compilers all need to run inside a system that takes care of loading code, allocating memory when requested, and often doing garbage collection. These services are what make a VM. The exact execution strategy is not what determines VM-ness.
  - quelltext 5y ago
    Keep in mind that bytecode interpreted languages (Ruby, Python) are typically called interpreted languages. Java is usually called "compiled" because of the explicit step vs. Ruby and Python, but it's essentially the same. And typically you'll find discussions wrt to JVM about interpretation in Java referring to bytecode interpretation vs. compiling being JIT compiling. Ultimately limiting interpreters to AST interpreters is not quite correct. The AST is just another IR that source code needs to be converted to just like bytecode. And the AST is essentially also executed by a virtual machine. Interpretation of the IR (the AST, or bytecode, etc.) is one part of a VM. Of course in some instances the VMness of a runtime is more pronounced (Java) than in others (Ruby). The difference between interpretation and compilation is that the latter is meant to run on real hardware vs. the former implies something that executes the IR of a program by dynamically choosing which machine instructions to run. Of course a compiler is also something that takes in some code and outputs some other, typically more low level representation. My point being I don't think there is a strict or consistent definition these days for what an interpreter is. Case in point: I've also heard people say interpreters read the code "line by line" (or rather, not that but more accurately, as far as they need to read before they know what to execute next) and execute it piece by piece. Which might be how some interpreters worked in some languages in the past. An AST interpreter OTOH already implies some whole source file pre-processing. Is an AST interpreter then less of an interpreter than one that streams the source code line by line. Is a program that does that more an interpreter than another which goes a step further and, e.g. executes a simplified AST, or one that executes a straightforward trivial bytecode representation of the simplified AST?
- mtlynch 5y ago
  I haven't read it, but Bob Nystrom's Crafting Interpreters has been on my list for a while: https://craftinginterpreters.com/ https://craftinginterpreters.com/
  - smueller1234 5y ago
    Don't wait, read it. It's fun and informative, worth every minute! I haven't had as much fun reading a technical book in years!
  - LordN00b 5y ago
    I second this. It's a great resource, very well written. Opinionated enough to have character and humour, but not so dry as to make your eyes glaze over. I guess I'm saying that for a technical tome it's very, very readable (as was his Game Design Patterns book incidentally)
  - orthoxerox 5y ago
    It's a great book. Bob's not a CS teacher, and it's great: the book is grounded in practice and has been structured in a way that lets you get a tangible result at the end of every chapter.
- CodeArtisan 5y ago
  A virtual machine executes instructions while an interpreter takes source code as input. An interpreter could be built on top of a virtual machine, obviously, but not necessary. For example, SICP/PLAI/OOPLAI[1] explain how to implement an interpreter on top of Scheme where you directly interpret the s-expressions. These may be a worth read if you want to learn about the usual concepts and techniques used in programming language implementations from a more general point of view. Like, for example, how to implement a static type system or an object model based on classes. Interpreters based on a virtual machine are actually compilers on the fly; the source code is not interpreted but translated into instructions beforehand. [1] http://sarabander.github.io/sicp/ http://sarabander.github.io/sicp/ http://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/ http://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04... https://users.dcc.uchile.cl/~etanter/ooplai/ https://users.dcc.uchile.cl/~etanter/ooplai/
- theodpHN 5y ago
  Check out Peter Norvig's neat BASIC Interpreter https://github.com/norvig/pytudes/blob/master/ipynb/BASIC.ipynb https://github.com/norvig/pytudes/blob/master/ipynb/BASIC.ip...
iTokio 5y ago
By the author of the excellent https://c9x.me/compile/ https://c9x.me/compile/ A lightweight alternative to llvm https://c9x.me/compile/doc/llvm.html https://c9x.me/compile/doc/llvm.html
dmitriid 5y ago
I'm not an expert by far, but I feel like many people who write compilers or develop languages no longer recommend The Dragon Book as it's very outdated. Additionally, the vast majority of compiler books and resources spend too much time on the easiest part of compiling: parsing. It's not uncommon for a book or a course dedicate 60-70% of its time to parsing. And leaves nothing to everything else.
- MaxBarraclough 5y ago
  Yep, here's a thread from two years ago on exactly that: https://news.ycombinator.com/item?id=20436399 https://news.ycombinator.com/item?id=20436399
- rualca 5y ago
  > Additionally, the vast majority of compiler books and resources spend too much time on the easiest part of compiling: parsing. I disagree. Parsing is the single most important feature of building a programming language. It influences how the language can be structured and also how it should be structured for performance reasons. Also, you're far more likely to write a parser for a language than implement anything remotely related to compilers and interpreters. It's one thing to state that some topics might justify more content, but it's absurd to downplay the fundamental importance of parsers in putting together a compiler.
  - dmitriid 5y ago
    > Parsing is the single most important feature of building a programming language It realy isn't. Also, it's the most trivial part of parsing a programming language (in a compiler). > It influences how the language can be structured and also how it should be structured for performance reasons. Once again, no, not really. However complex your language is, it can be parsed at 100 GB/s on a Raspberry Pi. Even if you do it with regexps. Everything that comes after parsing is very complex and is rarely explained in any detail. And everything that comes after actualy directly influences the structure, the performance etc. It really makes zero difference if you decide that your typeing info should be written like this: T x = new T(); or like this: let x: T = T() or like this: var x := T() All this is trivial to parse. However, deciding on how you implement typing, what needs to be in the languaage to support your choice etc., now that definitely influences the structure, performance, trade-offs etc. How much of that is in the Dragon Book? Next to zero? But surely there are 4 chapters on how to parse this.
jhgb 5y ago
Perhaps Cooper's and Torczon's "Engineering a Compiler (2nd Edition)" should be among the entries in the "Books" category.
UncleEntity 5y ago
The Zephyr Abstract Syntax Description Language, Wang et al. Has been invaluable for creating the AST (and soon the IR nodes)-- though it has been a source of much yak shaving as I've rewritten my asdl generator at least 3 times. Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages Book, Terence Parr Pretty java/antlr focused but wasn't too hard to take the concepts and apply them to a C++ based transpiler I've been slowly poking at. Combining Analyses, Combining Optimizations, Cliff Click His thesis and an extension of the linked paper Global Code Motion, Global Value Numbering -- my next step down the rabbit hole... Tree Automata Techniques and Applications, Comon et al. Still on the fence on this one vs the iburg/burs algorithm, probably be more useful and match better with the way Parr's book goes about things.
hardwaregeek 5y ago
This is definitely a backend, machine code focused list. If you're writing a compiler to WebAssembly or even the JVM you're probably not gonna need a lot of these resources. Indeed I'd argue that these lists are more for an intermediate compiler writer. Beginner compiler writers don't need to know register allocation. They need to understand how to think about language translation, how to write an intermediate representation, how to learn a target language. I've been toying with the idea of writing a post that goes through the thought process of translation. Specifically, how you build states, and invariants. When I write code generation I spend time thinking about the different states the stack could be in, or what invariant I need to keep across this expression (do I need to save a register or global?). One simple but important example of this is realizing that given a proper, sound type checker, your code generator should almost never give errors. By the time you reach code generation you should have proven enough invariants that code generation cannot fail. This isn't always true but I've found it to be the case.
- jstanley 5y ago
  > Indeed I'd argue that these lists are more for an intermediate compiler writer. Beginner compiler writers don't need to know register allocation. I'm not disagreeing with you, but note that the title does not say it's for beginners, it says it's for amateurs, which is just anyone who does it for fun rather than money.
- orthoxerox 5y ago
  > Beginner compiler writers don't need to know register allocation. They need to understand how to think about language translation, how to write an intermediate representation, how to learn a target language. I don't think people that want to write a compiler want to end up with helloworld.c instead of helloword.exe. At least I don't.
  - hardwaregeek 5y ago
    At least for me, compiling to a simpler target made learning the ideas easier. Compiling to to raw assembly does give you more nerd credit but it also makes it harder to get started.
hasitseth 5y ago
Alan Holub's 'Compiler Design in C' is not mentioned in the books. Holub's book had well-written code. I had learned a lot from his code.
- elvis70 5y ago
  And a free copy of this book in PDF has been made available by the author: https://holub.com/compiler/ https://holub.com/compiler/
piinbinary 5y ago
Are there any good resources for building a runtime and codegen for languages with garbage collection?
- aardvark179 5y ago
  The Garbage Collection Handbook is excellent, but might go into more depth than you need. For a simple garbage collector there needn’t be any effect on codegen, all you need to worry about is the runtime side of things. Search for how to build a conservative garbage collector and you should find plenty of tutorials and introductory CS courses on the subject.
- moonchild 5y ago
  For a basic GC, code generation should be unaffected. The only place you'd need to care about code generation is if you wanted to make a realtime GC, inserting read or write barriers.
  - piinbinary 5y ago
    My understanding from doing a bit of reading is that there are at least two things codegen-adjacent that an accurate collector will want (even if you stop the world while collecting): 1. The locations of pointers inside of allocations. 2. The locations of pointers in the stack (into which you may need to spill registers). I can think of ways to do these (e.g. perhaps each stack frame contains a bitmask at a certain offset), but I'd love to learn what the best practices are.
    - moonchild 5y ago
      Usually your objects are boxed, and the box contains a type identifier which the gc can use to identify pointer offsets. It is apparently possible to do precise garbage collection without boxes—I'll see if I can find the paper and link it later—but this is not widely done.
andromeduck 5y ago
Wish there were more resources about or tools for bidirectional parsing.
ahelwer 5y ago
Does anybody know of good introductory resources on error recovery techniques when writing a parser & interpreter? Bonus points if they use combinators instead of a hand-written parser.
- jstimpfle 5y ago
  Not a resource, but depending on what kind of parser you are doing, maybe an idea. The thing I'm going to try out next for one of my batch parsers (written recursive descent style as many or most parsers in the wild) is to have AST nodes of kind "invalid". The idea is that the parser should always complete, with minimal in-line error checking, even when I have say "require_token_kind()" or similar calls in my parser code. Maybe not even an "invalid" kind, but an additional "invalid" flag, so that even those invalid nodes can still have all the regular node-kind-depending structure on them. The other obvious idea is to use a parser generator. But I'm pretty sure I wouldn't be happy on that route - from the little experiments that I've done, I infer it's too bureaucratic, too much boilerplate for me to suffer. The more general advice for error handling is that you should try to make APIs that require very little in-line error handling. Instead, keep errors behind the APIs, maybe collect them in a list, or only keep the first or last error, and allow to handle them at a later point (out-of-line). And boom, most of the talk about smart syntax and type systems and other clever systems to make error handling more convenient suddenly becomes obsolete. Yet more abstractly, don't try to build systems that make cumbersome things more convenient, but think how you can do with less of these cumbersome things. (That works wonders for runtime performance, too).
  - deleted 5y ago
    [deleted]
  - tester756 5y ago
    >The more general advice for error handling is that you should try to make APIs that require very little in-line error handling. Instead, keep errors behind the APIs, maybe collect them in a list, or only keep the first or last error, and allow to handle them at a later point (out-of-line). I guess you wanted to say that instead of printing just what's wrong at some point, be smarter and try to build some handier error handling like attaching error to ast's node and then maybe do something with it
testrvb 5y ago
test
estebank 5y ago
A lot of ink is spilled on the details of how to make compilers go from taking text and turn it into fast executables, but I believe that the User Experience of compilers is as important a subject as those, but there's very little information about it in the literature, outside of a handful of papers and the design documents of existing compilers that do focus on this.
- dmitriid 5y ago
  No idea why you are being downvoted, but it's true. Compiler UX is often horrible, but the new breed of languages tries to rectify parts of it: - non-crpytic error messages. Show exactly what failed, where it failed, how to solve it. - compiler-as-a-service. Tool makers will love you. - compilation speed. If I need to wait 2 minutes for a 10 LOC project to compile, your compiler is doing something wrong. - the compiler should be the only tool you need. If you rely on 15 different tools just to compile a project, you're doing something wrong
  - estebank 5y ago
    As you allude to, treating a compiler as an isolated batch process is an outdated strategy. Any compiler started today should be designed such that it can be used in an IDE from the start, even if you don't implement it in that way until after you've reached a certain level of maturity. For error messages in particular is a very expansive topic because a compiler might have the following components: Lexer Parser Macro Expansion Name Resolution Lowering Type Checking Privacy Checking Lifetime Analysis Code Generation Linking and all of them can produce errors. If you introduce error recovery in your parser, then you better make sure you're carrying that information forward to name resolution and type checking. If you introduce a error type placeholder, better account for it during the rest of your analysis to avoid complaining about non-existing methods on something that wasn't resolved in the first place. Error deduplication. Exploring the grammar space to identify things that a human may attempt but isn't allowed for good reason but that will not blow up until some quasi-random stage. Now that I think about it you could write a whole book about these topic.
Rochus 5y ago
There is a more recent edition of "Compilers: Principles, Techniques, and Tools" worth considering: https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd-dp-0321486811/dp/0321486811 https://www.amazon.com/Compilers-Principles-Techniques-Tools....
deleted 5y ago
[deleted]
alanafarias22 5y ago
Amei esse posto
alanafarias22 5y ago
Esses comentários ajudam muito
phonebucket 5y ago
One thing I find curious: lots of compiler writing seems to be done in Haskell, but I can hardly find any Haskell-based resources for writing compilers. Can anyone here please recommend any such resources?
- tester756 5y ago
  >lots of compiler writing seems to be done in Haskell those 4fun of real world?
  - mechanicalDigit 5y ago
    Most compilers are written for fun. That’s the point of the thread. Also, there is a lot of modern language research is done from the “lens” (heh) of Haskell, or at least the Glasgow school.
- toolslive 5y ago
  https://www.microsoft.com/en-us/research/publication/implementing-functional-languages-a-tutorial/ https://www.microsoft.com/en-us/research/publication/impleme...
- atsuzaki 5y ago
  This is a pretty good tutorial that I know of: https://www.stephendiehl.com/llvm/ https://www.stephendiehl.com/llvm/. The author went on to write a book too, though it's still in progress http://dev.stephendiehl.com/fun/ http://dev.stephendiehl.com/fun/
chandlore 5y ago
Latest versions of the ABI specifications linked in the Machine Specific section ARM: https://github.com/ARM-software/abi-aa/releases https://github.com/ARM-software/abi-aa/releases x86-64: https://gitlab.com/x86-psABIs/x86-64-ABI https://gitlab.com/x86-psABIs/x86-64-ABI (go to most recent CI job and download artifacts for a compiled PDF)
failwhaleshark 5y ago
ProTips after writing numerous kinds of compilers in university: Recursive descent with backtracking is much easier to construct and maintain for diagnostics than bison/flex. Derivative parsing is very interesting.
ChicagoDave 5y ago
I've toyed with compiler stuff for years. My current idea is a fluent/piping language. Is there any reference that would help with that?

339 points by kilodeca 5y ago

Any similar resources on writing interpreters? Also is there are a technical difference between an interpreter and a VM?

MH15 5y ago
Interpreters usually execute by walking the abstract syntax tree at runtime, bytecode VMs usually execute actual bytecode similar to machine code. The bytecode for such VMs is often way simpler than the instruction set for an actual computer, so it's far more portable between platforms.
- nethunters 5y ago
  Thanks for clearing that up. Which languages or implementations of languages directly interpret the AST without the intermediary bytecode compilation? I know Python, Java and JavaScript (V8 and SpiderMonkey) all compile to bytecode first probably to speed up subsequent runs and run some optimisations on the bytecode. What other benefits are there to compiling to bytecode first vs directly interpreting the AST?
  - herohamp 5y ago
    Portability. Say I wanted to make language X run on all platforms, but I didn't actually care about compiling it on all platforms. I can just write a relatively simple VM for each platform. This is one of the reasons Java was and still kinda is so ubiquitous
    - nethunters 5y ago
      Wouldn't writing an interpreter for each platform be less work and achieve the same goal as writing a VM for each platform? Edit: ^Aside from being able to execute the bytecode on any platform
      - kaba0 5y ago
        As others mentioned, source code should be distributed that way, and I think creating a simple VM is easier than a simple language parser. But of course, an optimizing one can be really quite complex in both cases.
      - klyrs 5y ago
        Why would it be less work? The interpreter will need to implement whatever operations a VM can perform, so a priori it's at least as much work. Bonus, if you can bootstrap the source->bytecode process, then you only need to write (and compile) that once to get a full-fledged interpreter on every host with a VM
  - CalChris 5y ago
    If you compile to AST and walk that then your portability is at the source level; you have to send the source over the wire; each target then needs a parser+walker and each target needs to parse+walk. If you compile to bytecode you can send bytecode over the wire and then simply interpret that bytecode.
  - jhgb 5y ago
    Gambit Scheme, CLISP, CMUCL are capable of interpreting ASTs, and I believe (although I'm not 100% sure) that this is the case for Lispworks and Allegro CL as well. Also, Ruby until version 1.8.
  - smueller1234 5y ago
    Perl is a tree based interpreter. It's not exactly an AST anymore but the time it's being executed, but close enough.
  - IainIreland 5y ago
    One major benefit of compiling to bytecode first is that bytecode is a more convenient shared source of truth. For example, SpiderMonkey has two interpreter and two compiler tiers. The output of the parser is bytecode. We can interpret it immediately, and it's a convenient input to the compilers. It also simplifies transitions between tiers: for example, when we bail out of Warp, we resume at a specific bytecode offset in the baseline interpreter. I'm not sure how you would resume at a particular point in the execution of an AST-based interpreter without agreeing on a linearized traversal of the AST, which is 90% of the way to bytecode.
- tom_mellior 5y ago
  > Interpreters usually execute by walking the abstract syntax tree at runtime, bytecode VMs usually execute actual bytecode similar to machine code. This isn't the right way to separate these concepts. A VM that executes bytecodes by interpretation is also an interpreter (Python, Ruby, PHP are well-known examples). Many VMs don't interpret, or they interpret mostly during startup, but actually try to compile hot parts of the code and execute that machine code rather than interpreting (Java and JavaScript VMs are well-known examples). The VM part more properly refers to things like data representation and memory management. Interpreters of an abstract syntax tree, interpreters of bytecodes, and just in time compilers all need to run inside a system that takes care of loading code, allocating memory when requested, and often doing garbage collection. These services are what make a VM. The exact execution strategy is not what determines VM-ness.
- quelltext 5y ago
  Keep in mind that bytecode interpreted languages (Ruby, Python) are typically called interpreted languages. Java is usually called "compiled" because of the explicit step vs. Ruby and Python, but it's essentially the same. And typically you'll find discussions wrt to JVM about interpretation in Java referring to bytecode interpretation vs. compiling being JIT compiling. Ultimately limiting interpreters to AST interpreters is not quite correct. The AST is just another IR that source code needs to be converted to just like bytecode. And the AST is essentially also executed by a virtual machine. Interpretation of the IR (the AST, or bytecode, etc.) is one part of a VM. Of course in some instances the VMness of a runtime is more pronounced (Java) than in others (Ruby). The difference between interpretation and compilation is that the latter is meant to run on real hardware vs. the former implies something that executes the IR of a program by dynamically choosing which machine instructions to run. Of course a compiler is also something that takes in some code and outputs some other, typically more low level representation. My point being I don't think there is a strict or consistent definition these days for what an interpreter is. Case in point: I've also heard people say interpreters read the code "line by line" (or rather, not that but more accurately, as far as they need to read before they know what to execute next) and execute it piece by piece. Which might be how some interpreters worked in some languages in the past. An AST interpreter OTOH already implies some whole source file pre-processing. Is an AST interpreter then less of an interpreter than one that streams the source code line by line. Is a program that does that more an interpreter than another which goes a step further and, e.g. executes a simplified AST, or one that executes a straightforward trivial bytecode representation of the simplified AST?
mtlynch 5y ago
I haven't read it, but Bob Nystrom's Crafting Interpreters has been on my list for a while: https://craftinginterpreters.com/ https://craftinginterpreters.com/
- smueller1234 5y ago
  Don't wait, read it. It's fun and informative, worth every minute! I haven't had as much fun reading a technical book in years!
- LordN00b 5y ago
  I second this. It's a great resource, very well written. Opinionated enough to have character and humour, but not so dry as to make your eyes glaze over. I guess I'm saying that for a technical tome it's very, very readable (as was his Game Design Patterns book incidentally)
- orthoxerox 5y ago
  It's a great book. Bob's not a CS teacher, and it's great: the book is grounded in practice and has been structured in a way that lets you get a tangible result at the end of every chapter.
CodeArtisan 5y ago
A virtual machine executes instructions while an interpreter takes source code as input. An interpreter could be built on top of a virtual machine, obviously, but not necessary. For example, SICP/PLAI/OOPLAI[1] explain how to implement an interpreter on top of Scheme where you directly interpret the s-expressions. These may be a worth read if you want to learn about the usual concepts and techniques used in programming language implementations from a more general point of view. Like, for example, how to implement a static type system or an object model based on classes. Interpreters based on a virtual machine are actually compilers on the fly; the source code is not interpreted but translated into instructions beforehand. [1] http://sarabander.github.io/sicp/ http://sarabander.github.io/sicp/ http://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/ http://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04... https://users.dcc.uchile.cl/~etanter/ooplai/ https://users.dcc.uchile.cl/~etanter/ooplai/
theodpHN 5y ago
Check out Peter Norvig's neat BASIC Interpreter https://github.com/norvig/pytudes/blob/master/ipynb/BASIC.ipynb https://github.com/norvig/pytudes/blob/master/ipynb/BASIC.ip...

iTokio 5y ago

By the author of the excellent https://c9x.me/compile/ https://c9x.me/compile/ A lightweight alternative to llvm https://c9x.me/compile/doc/llvm.html https://c9x.me/compile/doc/llvm.html

dmitriid 5y ago

I'm not an expert by far, but I feel like many people who write compilers or develop languages no longer recommend The Dragon Book as it's very outdated. Additionally, the vast majority of compiler books and resources spend too much time on the easiest part of compiling: parsing. It's not uncommon for a book or a course dedicate 60-70% of its time to parsing. And leaves nothing to everything else.

MaxBarraclough 5y ago
Yep, here's a thread from two years ago on exactly that: https://news.ycombinator.com/item?id=20436399 https://news.ycombinator.com/item?id=20436399
rualca 5y ago
> Additionally, the vast majority of compiler books and resources spend too much time on the easiest part of compiling: parsing. I disagree. Parsing is the single most important feature of building a programming language. It influences how the language can be structured and also how it should be structured for performance reasons. Also, you're far more likely to write a parser for a language than implement anything remotely related to compilers and interpreters. It's one thing to state that some topics might justify more content, but it's absurd to downplay the fundamental importance of parsers in putting together a compiler.
- dmitriid 5y ago
  > Parsing is the single most important feature of building a programming language It realy isn't. Also, it's the most trivial part of parsing a programming language (in a compiler). > It influences how the language can be structured and also how it should be structured for performance reasons. Once again, no, not really. However complex your language is, it can be parsed at 100 GB/s on a Raspberry Pi. Even if you do it with regexps. Everything that comes after parsing is very complex and is rarely explained in any detail. And everything that comes after actualy directly influences the structure, the performance etc. It really makes zero difference if you decide that your typeing info should be written like this: T x = new T(); or like this: let x: T = T() or like this: var x := T() All this is trivial to parse. However, deciding on how you implement typing, what needs to be in the languaage to support your choice etc., now that definitely influences the structure, performance, trade-offs etc. How much of that is in the Dragon Book? Next to zero? But surely there are 4 chapters on how to parse this.

jhgb 5y ago

Perhaps Cooper's and Torczon's "Engineering a Compiler (2nd Edition)" should be among the entries in the "Books" category.

UncleEntity 5y ago

The Zephyr Abstract Syntax Description Language, Wang et al. Has been invaluable for creating the AST (and soon the IR nodes)-- though it has been a source of much yak shaving as I've rewritten my asdl generator at least 3 times. Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages Book, Terence Parr Pretty java/antlr focused but wasn't too hard to take the concepts and apply them to a C++ based transpiler I've been slowly poking at. Combining Analyses, Combining Optimizations, Cliff Click His thesis and an extension of the linked paper Global Code Motion, Global Value Numbering -- my next step down the rabbit hole... Tree Automata Techniques and Applications, Comon et al. Still on the fence on this one vs the iburg/burs algorithm, probably be more useful and match better with the way Parr's book goes about things.

hardwaregeek 5y ago

This is definitely a backend, machine code focused list. If you're writing a compiler to WebAssembly or even the JVM you're probably not gonna need a lot of these resources. Indeed I'd argue that these lists are more for an intermediate compiler writer. Beginner compiler writers don't need to know register allocation. They need to understand how to think about language translation, how to write an intermediate representation, how to learn a target language. I've been toying with the idea of writing a post that goes through the thought process of translation. Specifically, how you build states, and invariants. When I write code generation I spend time thinking about the different states the stack could be in, or what invariant I need to keep across this expression (do I need to save a register or global?). One simple but important example of this is realizing that given a proper, sound type checker, your code generator should almost never give errors. By the time you reach code generation you should have proven enough invariants that code generation cannot fail. This isn't always true but I've found it to be the case.

jstanley 5y ago
> Indeed I'd argue that these lists are more for an intermediate compiler writer. Beginner compiler writers don't need to know register allocation. I'm not disagreeing with you, but note that the title does not say it's for beginners, it says it's for amateurs, which is just anyone who does it for fun rather than money.
orthoxerox 5y ago
> Beginner compiler writers don't need to know register allocation. They need to understand how to think about language translation, how to write an intermediate representation, how to learn a target language. I don't think people that want to write a compiler want to end up with helloworld.c instead of helloword.exe. At least I don't.
- hardwaregeek 5y ago
  At least for me, compiling to a simpler target made learning the ideas easier. Compiling to to raw assembly does give you more nerd credit but it also makes it harder to get started.

hasitseth 5y ago

Alan Holub's 'Compiler Design in C' is not mentioned in the books. Holub's book had well-written code. I had learned a lot from his code.

elvis70 5y ago
And a free copy of this book in PDF has been made available by the author: https://holub.com/compiler/ https://holub.com/compiler/

piinbinary 5y ago

Are there any good resources for building a runtime and codegen for languages with garbage collection?

aardvark179 5y ago
The Garbage Collection Handbook is excellent, but might go into more depth than you need. For a simple garbage collector there needn’t be any effect on codegen, all you need to worry about is the runtime side of things. Search for how to build a conservative garbage collector and you should find plenty of tutorials and introductory CS courses on the subject.
moonchild 5y ago
For a basic GC, code generation should be unaffected. The only place you'd need to care about code generation is if you wanted to make a realtime GC, inserting read or write barriers.
- piinbinary 5y ago
  My understanding from doing a bit of reading is that there are at least two things codegen-adjacent that an accurate collector will want (even if you stop the world while collecting): 1. The locations of pointers inside of allocations. 2. The locations of pointers in the stack (into which you may need to spill registers). I can think of ways to do these (e.g. perhaps each stack frame contains a bitmask at a certain offset), but I'd love to learn what the best practices are.
  - moonchild 5y ago
    Usually your objects are boxed, and the box contains a type identifier which the gc can use to identify pointer offsets. It is apparently possible to do precise garbage collection without boxes—I'll see if I can find the paper and link it later—but this is not widely done.

andromeduck 5y ago

Wish there were more resources about or tools for bidirectional parsing.

ahelwer 5y ago

Does anybody know of good introductory resources on error recovery techniques when writing a parser & interpreter? Bonus points if they use combinators instead of a hand-written parser.

jstimpfle 5y ago
Not a resource, but depending on what kind of parser you are doing, maybe an idea. The thing I'm going to try out next for one of my batch parsers (written recursive descent style as many or most parsers in the wild) is to have AST nodes of kind "invalid". The idea is that the parser should always complete, with minimal in-line error checking, even when I have say "require_token_kind()" or similar calls in my parser code. Maybe not even an "invalid" kind, but an additional "invalid" flag, so that even those invalid nodes can still have all the regular node-kind-depending structure on them. The other obvious idea is to use a parser generator. But I'm pretty sure I wouldn't be happy on that route - from the little experiments that I've done, I infer it's too bureaucratic, too much boilerplate for me to suffer. The more general advice for error handling is that you should try to make APIs that require very little in-line error handling. Instead, keep errors behind the APIs, maybe collect them in a list, or only keep the first or last error, and allow to handle them at a later point (out-of-line). And boom, most of the talk about smart syntax and type systems and other clever systems to make error handling more convenient suddenly becomes obsolete. Yet more abstractly, don't try to build systems that make cumbersome things more convenient, but think how you can do with less of these cumbersome things. (That works wonders for runtime performance, too).
- deleted 5y ago
  [deleted]
- tester756 5y ago
  >The more general advice for error handling is that you should try to make APIs that require very little in-line error handling. Instead, keep errors behind the APIs, maybe collect them in a list, or only keep the first or last error, and allow to handle them at a later point (out-of-line). I guess you wanted to say that instead of printing just what's wrong at some point, be smarter and try to build some handier error handling like attaching error to ast's node and then maybe do something with it

testrvb 5y ago

test

estebank 5y ago

A lot of ink is spilled on the details of how to make compilers go from taking text and turn it into fast executables, but I believe that the User Experience of compilers is as important a subject as those, but there's very little information about it in the literature, outside of a handful of papers and the design documents of existing compilers that do focus on this.

dmitriid 5y ago
No idea why you are being downvoted, but it's true. Compiler UX is often horrible, but the new breed of languages tries to rectify parts of it: - non-crpytic error messages. Show exactly what failed, where it failed, how to solve it. - compiler-as-a-service. Tool makers will love you. - compilation speed. If I need to wait 2 minutes for a 10 LOC project to compile, your compiler is doing something wrong. - the compiler should be the only tool you need. If you rely on 15 different tools just to compile a project, you're doing something wrong
- estebank 5y ago
  As you allude to, treating a compiler as an isolated batch process is an outdated strategy. Any compiler started today should be designed such that it can be used in an IDE from the start, even if you don't implement it in that way until after you've reached a certain level of maturity. For error messages in particular is a very expansive topic because a compiler might have the following components: Lexer Parser Macro Expansion Name Resolution Lowering Type Checking Privacy Checking Lifetime Analysis Code Generation Linking and all of them can produce errors. If you introduce error recovery in your parser, then you better make sure you're carrying that information forward to name resolution and type checking. If you introduce a error type placeholder, better account for it during the rest of your analysis to avoid complaining about non-existing methods on something that wasn't resolved in the first place. Error deduplication. Exploring the grammar space to identify things that a human may attempt but isn't allowed for good reason but that will not blow up until some quasi-random stage. Now that I think about it you could write a whole book about these topic.

Rochus 5y ago

There is a more recent edition of "Compilers: Principles, Techniques, and Tools" worth considering: https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd-dp-0321486811/dp/0321486811 https://www.amazon.com/Compilers-Principles-Techniques-Tools....

deleted 5y ago

[deleted]

alanafarias22 5y ago

Amei esse posto

alanafarias22 5y ago

Esses comentários ajudam muito

phonebucket 5y ago

One thing I find curious: lots of compiler writing seems to be done in Haskell, but I can hardly find any Haskell-based resources for writing compilers. Can anyone here please recommend any such resources?

tester756 5y ago
>lots of compiler writing seems to be done in Haskell those 4fun of real world?
- mechanicalDigit 5y ago
  Most compilers are written for fun. That’s the point of the thread. Also, there is a lot of modern language research is done from the “lens” (heh) of Haskell, or at least the Glasgow school.
toolslive 5y ago
https://www.microsoft.com/en-us/research/publication/implementing-functional-languages-a-tutorial/ https://www.microsoft.com/en-us/research/publication/impleme...
atsuzaki 5y ago
This is a pretty good tutorial that I know of: https://www.stephendiehl.com/llvm/ https://www.stephendiehl.com/llvm/. The author went on to write a book too, though it's still in progress http://dev.stephendiehl.com/fun/ http://dev.stephendiehl.com/fun/

chandlore 5y ago

Latest versions of the ABI specifications linked in the Machine Specific section ARM: https://github.com/ARM-software/abi-aa/releases https://github.com/ARM-software/abi-aa/releases x86-64: https://gitlab.com/x86-psABIs/x86-64-ABI https://gitlab.com/x86-psABIs/x86-64-ABI (go to most recent CI job and download artifacts for a compiled PDF)

failwhaleshark 5y ago

ProTips after writing numerous kinds of compilers in university: Recursive descent with backtracking is much easier to construct and maintain for diagnostics than bison/flex. Derivative parsing is very interesting.

ChicagoDave 5y ago

I've toyed with compiler stuff for years. My current idea is a fluent/piping language. Is there any reference that would help with that?