10 ms·

My First Fifteen Compilers

388 points by azhenley 7y ago

narrowtux 7y ago
Please don't mess with the scroll event.
- slimsag 7y ago
  God, this is so annoying -- I literally cannot bear to read articles when they do this. I truly don't understand why people think this is a good idea. I also don't understand why there isn't a browser extension to prevent scroll-jacking effectively? "No more scroll jacking" on the Chrome store seems to, but annoyingly you have to hold a meta key for it to work.
  - adrianN 7y ago
    NoScript works very well for me.
    - elderK 7y ago
      Me too!
  - Sohcahtoa82 7y ago
    > I truly don't understand why people think this is a good idea. They're usually trying to create smooth scrolling. The problem is, it never works in every browser. > I also don't understand why there isn't a browser extension to prevent scroll-jacking effectively? It should really just be an option in the browser, even if it's in a fancy hidden advanced settings page.
cosarara 7y ago
How does this approach play with error handling? If there is an error in my code and it's only caught at step 10, won't the error message be completely inscrutable? Will the line numbers make sense?
- mojuba 7y ago
 Line number information is usually passed down the chain because it's required for generating debug info anyway. However, as you descend into deeper optimization layers of the compiler, errors are less and less likely to occur. Optimizations are either possible or not, though sometimes these layers can warn you about possible inefficiencies at the source code level (unused local, etc.)
- sterlind 7y ago
 A simple approach could be to mark up spans of characters in layer N with what spans were used to generate them in layer N-1. Then when parser N hits an error, put red squiggly lines under the source characters responsible. For instance, in C#: using (var x = 3) { Console.WriteLine(x);} Parser 0 transforms the using: var x = 3; try { Console.WriteLine(x); } finally { x.Dispose(); } Parser 1 (or a later parser, inductively) notices x doesn't have Dispose() defined, and throws MissingMethod(Dispose, span=generated). Parser 0 catches this error, knows that this is because x isn't disosable, and emits its own error: NotDisposable(span=decl). If a parser doesn't know to catch the error, it still passes it up the chain, transforming spans where appropriate. When it hits the IDE, the error is printed and the red squiggly lines go where they should. (Disclaimer: I've never written a compiler)
- thedufer 7y ago
 In the only compiler I'm somewhat familiar with (OCaml), a decent amount of the work is done in AST->AST transformations. In the AST, every node is annotated with a location, which is a tuple of filename, line number, char start, char end. As long as these are propagated in the right way, you get good location information in errors.
- deleted 7y ago
 [deleted]
deepaksurti 7y ago
Is Kent Dybvig‘s compilers course, known as P523 referred to in the article, still available online? Thanks!
- quazar 7y ago
  I can't find the course online, but there are two github repos with students' code: https://github.com/pavenvivek/Compiler-for-Scheme https://github.com/hyln9/P523 I did find a book ("Essentials of Compilation. An Incremental Approach"), also from Indiana University, but not authored by Dybvig, on compiling Racket to x86-64 assembly and it seems to take similar approach: https://jeapostrophe.github.io/courses/2017/spring/406/notes/book.pdf
  - asdfman123 7y ago
    Saving this textbook to hypothetically read in the future.
- Flow 7y ago
  I so want to take that class. Maybe it would be possible to start a fund raiser and pay him to record videos and release the materials used in the course?
mojuba 7y ago
As another extreme, Turbo Pascal's earlier implementations had only one pass. Just straight from Pascal to binary code with some optimizations too. I wonder what the minimum number of passes could be by today's optimization standards. Two? Three?
- ThinkBeat 7y ago
  and the code it produced was fast as well. IDE, Compiler and code all really fast (back then)
- soegaard 7y ago
  Apropos, a web-site/book dedicated to compiler internals: http://turbopascal.org/ http://turbopascal.org/
- sansnomme 7y ago
  Go, V etc. all have straightforward compiler systems that produce reasonably fast code without calling into LLVM. The fact that a lot of modern day compilers don't have a built-in assemblers etc. are probably more due to laziness.
  - dorfsmay 7y ago
    Laziness? Or time constraints and specialization? I see the last stage of compiling as a special skills which requires a lot of time, especially if you want to support multiple platforms. If you're thing is to create a great programming language, then your time is better spent on that rather than create a bad or ok backend supporting very few platforms.
  - mojuba 7y ago
    Probably more to do with cross-CPU portability than laziness
  - rickbutton 7y ago
    No one that maintains a production grade compiler is lazy. I would say that no one that maintains a compiler of any quality is lazy. Let's replace "laziness" with "carefully considered trade-offs" in this context. i.e. "The fact that a lot of modern day compilers don't have built in assemblers etc. are probably more due to carefully considered trade-offs".
moopling 7y ago
Does anyone have recommendations for good resources on writing your first compiler?
- deleted 7y ago
  [deleted]
- theSage 7y ago
  David Beazley hosts a pretty good compiler class. I wrote my first one there. https://www.dabeaz.com/compiler.html https://www.dabeaz.com/compiler.html
- melling 7y ago
  I’ve got some links here: https://github.com/melling/ComputerLanguages/blob/master/compilers.md https://github.com/melling/ComputerLanguages/blob/master/com...
- amelius 7y ago
  Also curious, what is the modern equivalent of the "Dragon Book"? A lot has changed since the old times, e.g. JIT compilers, and garbage collected VMs and such. Also CPUs have changed a lot, e.g. speculative execution, deep pipelining, large memory cache hierarchies, GPUs, etc. Is there a compiler book that addresses it all?
  - ernst_klim 7y ago
    Modern Compiler in ML/Java. Dragon book is nearly useless and could be useful only for lexer/parser implementation.
    - UncleMeat 7y ago
      Eh. Dragon still has good material on pipelining and local dataflow analysis frameworks. The version two stuff on bdds is the most poorly aged part, IMO.
    - MaxBarraclough 7y ago
      > Dragon book is nearly useless Why's that?
lewisjoe 7y ago
To folks interested in writing compilers, here's a tiny list of resources I put together for myself: http://hexopress.com/@joe/blog/2019/04/14/awesome-compiler-resources/ http://hexopress.com/@joe/blog/2019/04/14/awesome-compiler-r...
- langitbiru 7y ago
  There is a typo. "List Compiler" -> "Lisp Compiler". Also, you may need to update the list with some suggestions from this thread. :)
  - lewisjoe 7y ago
    Thanks! Fixed the typo and updated with links.
panda_4 7y ago
Every single time I try to do an online Compilers class, my brain gets stuck at grammars. I understand the concept of grammars but for whatever reason can't go from taking rules and writing a grammar out with it. Probably will have to do an in classroom course for it?
- marcosdumay 7y ago
  Well, you can sidestep the problem at first by either writing your compiler in Prolog or Haskell, or by writing a Lisp compiler. Or, alternatively you can dive into it and get a book or a course focused on parsers. It's not something that you can easily learn by just thinking about it, so being stuck on it is completely natural.
- aidenn0 7y ago
  Assuming you are talking about using a grammar to parser tool like yacc, you probably should at some point figure out what your hangup is there, but shouldn't let that stop you from writing a compiler. I very rarely use such a tool for writing a compiler, and find that real-world compilers similarly rarely use a tool. Regardless of whether you are writing a grammar or a recursive descent parser, start with a really simple language say: Expr = "A" | "(" Expr* ")" Which is balanced parentheses with the token that is the exact character "A" possibly appearing. All of these are valid matches: (()) ((A(A)A)A) (((((AAA))))) The parse tree should be such that each node is a list where each element is either an A token or another parse tree node. Once you can parse that, then you can start moving on to more complicated grammars; a possible complication is to add "B" as a valid expression, with the caveat that B cannot be the sibling of a parenthesized expression. That is: (ABA) is valid, but (B(A)) is not valid. I used single characters as the primitive here, so perhaps the next step would be to add a tokenizer. "B" has special rules, so it will be the keyword "bananas". A will be any other alphabetic token. If all of the above is already doable, then perhaps I've misunderstood where your hangup is. Let me know, perhaps I can help.
  - panda_4 7y ago
    Should that grammar be: Expr = "A" | "(" Expr* ")" | "" so that (()) is s a valid match? Because then Expr can be an empty string also?
rurban 7y ago
Note that you do that kind of mega multipass compilers only when compiling to static binaries, not when targetting dynamic languages. It's way too slow, the compilation steps would last longer than the expected runtime. You can easily combine all these passes into one tree traversal and optimize on demand and benefit. 400 passes is beyond sanity.
- rickbutton 7y ago
  the "nanopass" approach mentioned in the article is used in Dybvig's chez scheme (not the nanopass library, just the style of compiler construction), and chez scheme is as close to an industrial grade scheme compiler as it gets, and is pretty fast. edit: I missed that chez scheme is already mentioned in the article.
- mhh__ 7y ago
  I'm not convinced this is true in general. Depending on how complicated these passes are, if you were to write the compiler in a language that allows you to combine them at compile time it would be entirely possible for the compiler(The one compiling the compiler) to cut out of the inter-pass crud. https://d.godbolt.org/z/w9At24 https://d.godbolt.org/z/w9At24 I hacked together this to show what I mean, i.e. Composing working functions with templates, which the compiler can then optimize into just a function call like any other (i.e. This can be used to minimize runtime scheduling cost)
kazinator 7y ago
ROT13 in 39 nano-passes! Week 1: A-hoisting: free occurrences of A are renamed to the symbol @ which doesn't occur anywhere in the input. Week 2: N-substitution: every top-level as well as lexically nested N is transformed to A. Week 3: @-lowering: every @ (denoting a previously hoisted A from pass 1) is reified as an instance of N.
oh_teh_meows 7y ago
This might be a little off-topic, but I wonder if the idea of nano-passes can be applied to other areas. For example, can we predict the future of technology by gradually evolving their capabilities? Or say start from some point in the future (interstellar travel!), and gradually work backwards what we think is needed? Or how about predicting geopolitics/economics? To use this method effectively, I think we'll need to fully specify, to the extent possible, the condition of each stage in time. That way, at any stage, we can see what constituents might possibly interact with each other and evolve something new.
- derjames 7y ago
  A common practice in organic chemistry is to start from the target molecule and work backwards trying to determine simpler precursor molecules that would produce the target. 'Retrosynthesis'
  - oh_teh_meows 7y ago
    Really really cool! I wonder if we can do something similar with programming. Suppose we have a conceptual framework where each module/system is a widget made up of slightly simpler and well-defined widgets. If we can specify what we want, perhaps a system can be devised that would try to build it from a database of widgets. If some of the constituent widgets are not found, the system could recursively specify each one and find/construct. In this recursive process, the language used to specify the requirements of a widget can be a changing DSL whose grammar and basic constructs co-evolve with the complexity/abstraction level of the widgets. This seems feasible because we (software engineers) are one such system. Starting from basic transistors, we build ever higher abstraction layers along with the language used to specify them (circuit diagrams -> microcodes -> assembly -> C -> DSLs). I believe multi-layer neural networks are also a prime example of such a system.
- naturlich 7y ago
  The difference in those targets is that they're uncertain, and that that uncertainty compounds as you reach further into the future. I don't think the nanopass-in-reverse approach lends itself well to resolving uncertainty, because you'd start from the point of most uncertainty, which sort of begs the question a bit.
wglb 7y ago
This is a marvelous article. I first encountered a many-many pass compiler when working on the IBM 1800 (same architecture as the IBM 1130) where the Fortran II compiler had 29 passes. It was challenging, as the machines often had only 4k and the removable cartridge disks were 5 megs.
deleted 7y ago
[deleted]
deleted 7y ago
[deleted]
jonjacky 7y ago
There was a FORTRAN compiler for the IBM 1401 that had 63 passes (they called them phases). See this paper from 1965: http://ibm-1401.info/1401-IBM-Systems-Journal-FORTRAN.html http://ibm-1401.info/1401-IBM-Systems-Journal-FORTRAN.html
- mntmoss 7y ago
  I came into the thread looking for this comment. The motivation in the 63-pass compiler is to get the job done in a very memory-frugal form. That it's relatively easy to follow is an additional bonus - a good lesson in software design.
mhh__ 7y ago
I think all compilers should follow the many-pass, lowering, based approach. It greatly reduces the surface area that needs to be tested while also keeping the compiler's code from being spaghetti crap which can often happen in non-toy compilers.
- asdfman123 7y ago
  > spaghetti crap That's called optimization, baby!
  - mhh__ 7y ago
    optimizing bug counts, usually.
- Gibbon1 7y ago
  I saw your comment and decided to look up how C#'s compiler does things. It does two passes of the program text. And then does three dozen passes after that. Each pass does what you suggest, only one thing. https://blogs.msdn.microsoft.com/ericlippert/2010/02/04/how-many-passes/ https://blogs.msdn.microsoft.com/ericlippert/2010/02/04/how-... I think it's still fast because the passes are all or mostly O(n).
  - mhh__ 7y ago
    There's no reason for the approach to be slow anyway because as long as there is a reasonable way for information to be retained inter-pass then they should be doing approximately the same amount of work as a less discrete alternative. AST lowering can be very fruitful for languages with lots of metaprogramming etc., i.e. DRY principle. Error propagation could be a bit lacklustre if not handled with care, however. On a more local basis, if you program in a language that encourages it, composing work at compile time can save a huge amount of cruft that one might imagine comes with using a many-pass compiler. https://d.godbolt.org/z/w9At24 https://d.godbolt.org/z/w9At24 (Already posted on this thread), I wrote this little example to show how you can compose series of discrete manipulations in D into what is indistinguishable from a normal function as if it were monolithically written by hand. That example (in D, in particular) could be made as pure-functional and discrete as is desired but I used pointers to keep it small. Compilers are extremely good at optimizing interprocedural code, or at least better than a human, so a certain level of lazyness can be bestowed upon the programmer at the expense of trusting a compiler.

388 points by azhenley 7y ago

narrowtux 7y ago

Please don't mess with the scroll event.

slimsag 7y ago
God, this is so annoying -- I literally cannot bear to read articles when they do this. I truly don't understand why people think this is a good idea. I also don't understand why there isn't a browser extension to prevent scroll-jacking effectively? "No more scroll jacking" on the Chrome store seems to, but annoyingly you have to hold a meta key for it to work.
- adrianN 7y ago
  NoScript works very well for me.
  - elderK 7y ago
    Me too!
- Sohcahtoa82 7y ago
  > I truly don't understand why people think this is a good idea. They're usually trying to create smooth scrolling. The problem is, it never works in every browser. > I also don't understand why there isn't a browser extension to prevent scroll-jacking effectively? It should really just be an option in the browser, even if it's in a fancy hidden advanced settings page.

cosarara 7y ago

How does this approach play with error handling? If there is an error in my code and it's only caught at step 10, won't the error message be completely inscrutable? Will the line numbers make sense?

mojuba 7y ago
Line number information is usually passed down the chain because it's required for generating debug info anyway. However, as you descend into deeper optimization layers of the compiler, errors are less and less likely to occur. Optimizations are either possible or not, though sometimes these layers can warn you about possible inefficiencies at the source code level (unused local, etc.)
sterlind 7y ago
A simple approach could be to mark up spans of characters in layer N with what spans were used to generate them in layer N-1. Then when parser N hits an error, put red squiggly lines under the source characters responsible. For instance, in C#: using (var x = 3) { Console.WriteLine(x);} Parser 0 transforms the using: var x = 3; try { Console.WriteLine(x); } finally { x.Dispose(); } Parser 1 (or a later parser, inductively) notices x doesn't have Dispose() defined, and throws MissingMethod(Dispose, span=generated). Parser 0 catches this error, knows that this is because x isn't disosable, and emits its own error: NotDisposable(span=decl). If a parser doesn't know to catch the error, it still passes it up the chain, transforming spans where appropriate. When it hits the IDE, the error is printed and the red squiggly lines go where they should. (Disclaimer: I've never written a compiler)
thedufer 7y ago
In the only compiler I'm somewhat familiar with (OCaml), a decent amount of the work is done in AST->AST transformations. In the AST, every node is annotated with a location, which is a tuple of filename, line number, char start, char end. As long as these are propagated in the right way, you get good location information in errors.
deleted 7y ago
[deleted]

deepaksurti 7y ago

Is Kent Dybvig‘s compilers course, known as P523 referred to in the article, still available online? Thanks!

quazar 7y ago
I can't find the course online, but there are two github repos with students' code: https://github.com/pavenvivek/Compiler-for-Scheme https://github.com/hyln9/P523 I did find a book ("Essentials of Compilation. An Incremental Approach"), also from Indiana University, but not authored by Dybvig, on compiling Racket to x86-64 assembly and it seems to take similar approach: https://jeapostrophe.github.io/courses/2017/spring/406/notes/book.pdf
- asdfman123 7y ago
  Saving this textbook to hypothetically read in the future.
Flow 7y ago
I so want to take that class. Maybe it would be possible to start a fund raiser and pay him to record videos and release the materials used in the course?

mojuba 7y ago

As another extreme, Turbo Pascal's earlier implementations had only one pass. Just straight from Pascal to binary code with some optimizations too. I wonder what the minimum number of passes could be by today's optimization standards. Two? Three?

ThinkBeat 7y ago
and the code it produced was fast as well. IDE, Compiler and code all really fast (back then)
soegaard 7y ago
Apropos, a web-site/book dedicated to compiler internals: http://turbopascal.org/ http://turbopascal.org/
sansnomme 7y ago
Go, V etc. all have straightforward compiler systems that produce reasonably fast code without calling into LLVM. The fact that a lot of modern day compilers don't have a built-in assemblers etc. are probably more due to laziness.
- dorfsmay 7y ago
  Laziness? Or time constraints and specialization? I see the last stage of compiling as a special skills which requires a lot of time, especially if you want to support multiple platforms. If you're thing is to create a great programming language, then your time is better spent on that rather than create a bad or ok backend supporting very few platforms.
- mojuba 7y ago
  Probably more to do with cross-CPU portability than laziness
- rickbutton 7y ago
  No one that maintains a production grade compiler is lazy. I would say that no one that maintains a compiler of any quality is lazy. Let's replace "laziness" with "carefully considered trade-offs" in this context. i.e. "The fact that a lot of modern day compilers don't have built in assemblers etc. are probably more due to carefully considered trade-offs".

moopling 7y ago

Does anyone have recommendations for good resources on writing your first compiler?

deleted 7y ago
[deleted]
theSage 7y ago
David Beazley hosts a pretty good compiler class. I wrote my first one there. https://www.dabeaz.com/compiler.html https://www.dabeaz.com/compiler.html
melling 7y ago
I’ve got some links here: https://github.com/melling/ComputerLanguages/blob/master/compilers.md https://github.com/melling/ComputerLanguages/blob/master/com...
amelius 7y ago
Also curious, what is the modern equivalent of the "Dragon Book"? A lot has changed since the old times, e.g. JIT compilers, and garbage collected VMs and such. Also CPUs have changed a lot, e.g. speculative execution, deep pipelining, large memory cache hierarchies, GPUs, etc. Is there a compiler book that addresses it all?
- ernst_klim 7y ago
  Modern Compiler in ML/Java. Dragon book is nearly useless and could be useful only for lexer/parser implementation.
  - UncleMeat 7y ago
    Eh. Dragon still has good material on pipelining and local dataflow analysis frameworks. The version two stuff on bdds is the most poorly aged part, IMO.
  - MaxBarraclough 7y ago
    > Dragon book is nearly useless Why's that?

lewisjoe 7y ago

To folks interested in writing compilers, here's a tiny list of resources I put together for myself: http://hexopress.com/@joe/blog/2019/04/14/awesome-compiler-resources/ http://hexopress.com/@joe/blog/2019/04/14/awesome-compiler-r...

langitbiru 7y ago
There is a typo. "List Compiler" -> "Lisp Compiler". Also, you may need to update the list with some suggestions from this thread. :)
- lewisjoe 7y ago
  Thanks! Fixed the typo and updated with links.

panda_4 7y ago

Every single time I try to do an online Compilers class, my brain gets stuck at grammars. I understand the concept of grammars but for whatever reason can't go from taking rules and writing a grammar out with it. Probably will have to do an in classroom course for it?

marcosdumay 7y ago
Well, you can sidestep the problem at first by either writing your compiler in Prolog or Haskell, or by writing a Lisp compiler. Or, alternatively you can dive into it and get a book or a course focused on parsers. It's not something that you can easily learn by just thinking about it, so being stuck on it is completely natural.
aidenn0 7y ago
Assuming you are talking about using a grammar to parser tool like yacc, you probably should at some point figure out what your hangup is there, but shouldn't let that stop you from writing a compiler. I very rarely use such a tool for writing a compiler, and find that real-world compilers similarly rarely use a tool. Regardless of whether you are writing a grammar or a recursive descent parser, start with a really simple language say: Expr = "A" | "(" Expr* ")" Which is balanced parentheses with the token that is the exact character "A" possibly appearing. All of these are valid matches: (()) ((A(A)A)A) (((((AAA))))) The parse tree should be such that each node is a list where each element is either an A token or another parse tree node. Once you can parse that, then you can start moving on to more complicated grammars; a possible complication is to add "B" as a valid expression, with the caveat that B cannot be the sibling of a parenthesized expression. That is: (ABA) is valid, but (B(A)) is not valid. I used single characters as the primitive here, so perhaps the next step would be to add a tokenizer. "B" has special rules, so it will be the keyword "bananas". A will be any other alphabetic token. If all of the above is already doable, then perhaps I've misunderstood where your hangup is. Let me know, perhaps I can help.
- panda_4 7y ago
  Should that grammar be: Expr = "A" | "(" Expr* ")" | "" so that (()) is s a valid match? Because then Expr can be an empty string also?

rurban 7y ago

Note that you do that kind of mega multipass compilers only when compiling to static binaries, not when targetting dynamic languages. It's way too slow, the compilation steps would last longer than the expected runtime. You can easily combine all these passes into one tree traversal and optimize on demand and benefit. 400 passes is beyond sanity.

rickbutton 7y ago
the "nanopass" approach mentioned in the article is used in Dybvig's chez scheme (not the nanopass library, just the style of compiler construction), and chez scheme is as close to an industrial grade scheme compiler as it gets, and is pretty fast. edit: I missed that chez scheme is already mentioned in the article.
mhh__ 7y ago
I'm not convinced this is true in general. Depending on how complicated these passes are, if you were to write the compiler in a language that allows you to combine them at compile time it would be entirely possible for the compiler(The one compiling the compiler) to cut out of the inter-pass crud. https://d.godbolt.org/z/w9At24 https://d.godbolt.org/z/w9At24 I hacked together this to show what I mean, i.e. Composing working functions with templates, which the compiler can then optimize into just a function call like any other (i.e. This can be used to minimize runtime scheduling cost)

kazinator 7y ago

ROT13 in 39 nano-passes! Week 1: A-hoisting: free occurrences of A are renamed to the symbol @ which doesn't occur anywhere in the input. Week 2: N-substitution: every top-level as well as lexically nested N is transformed to A. Week 3: @-lowering: every @ (denoting a previously hoisted A from pass 1) is reified as an instance of N.

oh_teh_meows 7y ago

This might be a little off-topic, but I wonder if the idea of nano-passes can be applied to other areas. For example, can we predict the future of technology by gradually evolving their capabilities? Or say start from some point in the future (interstellar travel!), and gradually work backwards what we think is needed? Or how about predicting geopolitics/economics? To use this method effectively, I think we'll need to fully specify, to the extent possible, the condition of each stage in time. That way, at any stage, we can see what constituents might possibly interact with each other and evolve something new.

derjames 7y ago
A common practice in organic chemistry is to start from the target molecule and work backwards trying to determine simpler precursor molecules that would produce the target. 'Retrosynthesis'
- oh_teh_meows 7y ago
  Really really cool! I wonder if we can do something similar with programming. Suppose we have a conceptual framework where each module/system is a widget made up of slightly simpler and well-defined widgets. If we can specify what we want, perhaps a system can be devised that would try to build it from a database of widgets. If some of the constituent widgets are not found, the system could recursively specify each one and find/construct. In this recursive process, the language used to specify the requirements of a widget can be a changing DSL whose grammar and basic constructs co-evolve with the complexity/abstraction level of the widgets. This seems feasible because we (software engineers) are one such system. Starting from basic transistors, we build ever higher abstraction layers along with the language used to specify them (circuit diagrams -> microcodes -> assembly -> C -> DSLs). I believe multi-layer neural networks are also a prime example of such a system.
naturlich 7y ago
The difference in those targets is that they're uncertain, and that that uncertainty compounds as you reach further into the future. I don't think the nanopass-in-reverse approach lends itself well to resolving uncertainty, because you'd start from the point of most uncertainty, which sort of begs the question a bit.

wglb 7y ago

This is a marvelous article. I first encountered a many-many pass compiler when working on the IBM 1800 (same architecture as the IBM 1130) where the Fortran II compiler had 29 passes. It was challenging, as the machines often had only 4k and the removable cartridge disks were 5 megs.

deleted 7y ago

[deleted]

deleted 7y ago

[deleted]

jonjacky 7y ago

There was a FORTRAN compiler for the IBM 1401 that had 63 passes (they called them phases). See this paper from 1965: http://ibm-1401.info/1401-IBM-Systems-Journal-FORTRAN.html http://ibm-1401.info/1401-IBM-Systems-Journal-FORTRAN.html

mntmoss 7y ago
I came into the thread looking for this comment. The motivation in the 63-pass compiler is to get the job done in a very memory-frugal form. That it's relatively easy to follow is an additional bonus - a good lesson in software design.

mhh__ 7y ago

I think all compilers should follow the many-pass, lowering, based approach. It greatly reduces the surface area that needs to be tested while also keeping the compiler's code from being spaghetti crap which can often happen in non-toy compilers.

asdfman123 7y ago
> spaghetti crap That's called optimization, baby!
- mhh__ 7y ago
  optimizing bug counts, usually.
Gibbon1 7y ago
I saw your comment and decided to look up how C#'s compiler does things. It does two passes of the program text. And then does three dozen passes after that. Each pass does what you suggest, only one thing. https://blogs.msdn.microsoft.com/ericlippert/2010/02/04/how-many-passes/ https://blogs.msdn.microsoft.com/ericlippert/2010/02/04/how-... I think it's still fast because the passes are all or mostly O(n).
- mhh__ 7y ago
  There's no reason for the approach to be slow anyway because as long as there is a reasonable way for information to be retained inter-pass then they should be doing approximately the same amount of work as a less discrete alternative. AST lowering can be very fruitful for languages with lots of metaprogramming etc., i.e. DRY principle. Error propagation could be a bit lacklustre if not handled with care, however. On a more local basis, if you program in a language that encourages it, composing work at compile time can save a huge amount of cruft that one might imagine comes with using a many-pass compiler. https://d.godbolt.org/z/w9At24 https://d.godbolt.org/z/w9At24 (Already posted on this thread), I wrote this little example to show how you can compose series of discrete manipulations in D into what is indistinguishable from a normal function as if it were monolithically written by hand. That example (in D, in particular) could be made as pure-functional and discrete as is desired but I used pointers to keep it small. Compilers are extremely good at optimizing interprocedural code, or at least better than a human, so a certain level of lazyness can be bestowed upon the programmer at the expense of trusting a compiler.