News for hackers. Stuff that matters.
Re:My First Fifteen Compilers by mojuba on Friday July 12, 2019 @05:34AM (#20419424)
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?
Re:My First Fifteen Compilers by lboasso on Friday July 12, 2019 @11:11AM (#20421269)
I wrote a self-hosted one pass compiler exactly to showcase Niklaus Wirth's approach to writing compilers: https://github.com/lboasso/oberonc

We often forget this alternative way (with its pros and cons).

Re:My First Fifteen Compilers by AnimalMuppet on Friday July 12, 2019 @12:46PM (#20422096)
I think that you need Wirth's approach to writing languages, not just compilers. I'm not sure that a one-pass C++ compiler would be easy. But Pascal (and Oberon?) were designed with that in mind. ("No forward references" is one place this shows.)
Re:My First Fifteen Compilers by mntmoss on Friday July 12, 2019 @04:46PM (#20424349)
Another one-pass data point is Action![0] for the Atari 8-bit computers. The compiler is extremely efficient for its day and a source code release was made just a few years ago. [1] But good luck making sense of it -- besides being all 6502 assembler, the source code is tremendously complicated by the amount of codesize optimization taking place, and discussion in the AtariAge forums from the folks who got it released indicates that writing this compiler pushed the author to his very limits. It probably could have benefited from a compiler-compiler!

[0] http://wiki.c2.com/?ActionLanguage

[1] https://sourceforge.net/projects/atari-action/

Re:My First Fifteen Compilers by soegaard on Friday July 12, 2019 @07:45AM (#20419956)
Apropos, a web-site/book dedicated to compiler internals: http://turbopascal.org/
Re:My First Fifteen Compilers by Wohlf on Friday July 12, 2019 @10:48AM (#20421117)
I have to imagine that was possible because everything was just simpler back then. Simpler hardware, simpler operating systems, lower overhead, lower expectations (i.e. security).

I feel like it may have been possible to know the full spec of everything you were working on.

Re:My First Fifteen Compilers by codr7 on Friday July 12, 2019 @10:57AM (#20421178)
More importantly, a simpler language.

It's still perfectly possible to design languages [0] for efficient single pass compilation, but they won't look like C#, Swift or Rust.

https://github.com/codr7/cidk

Re:My First Fifteen Compilers by cpeterso on Friday July 12, 2019 @11:32AM (#20421439)
What syntactic changes would be necessary for C++, C#, or Java style language to allow one-pass compilation?
Re:My First Fifteen Compilers by skybrian on Friday July 12, 2019 @11:58AM (#20421645)
Usually declarations need to come before usages. (Like happens with C headers.) Or else, you need to be able to generate the output for a usage without seeing the declaration.
Re:My First Fifteen Compilers by phaedrus on Friday July 12, 2019 @06:10PM (#20424981)
It seems to me that if a logic programming language with nondeterministic search and residuation were used to implement a compiler, the question of how many "passes" it has could be as moot and unimportant as counting the "number of stack frames" used in an imperative program. That is, I do not see why things could not be organized so that all the (pieces of) transformations are like actors in an actor model, and either act immediately or wait on data. In turn, whether their output is processed in another batch (layer) or immediately is just an optimization choice of the compiler compiler optimizer.
Re:My First Fifteen Compilers by tom_mellior on Saturday July 13, 2019 @02:08AM (#20426739)
Can you explain what you mean by residuation here?

But anyway, what you describe is maybe not entirely unlike equality saturation: https://www.cs.cornell.edu/~ross/publications/eqsat/

The idea is to apply a whole bunch of optimizations in parallel, but in a non-destructive fashion. So instead of changing "x * 5" to "x << 2 + x" or whatever, you just note that both are equivalent ways of expressing the same. Then you go on applying optimizations to both variants. At some point you stop and end up with a soup that contains many many different computations that all do the same thing. Then you apply a solver once to pick out an optimal variant.

The trick is to make this scale.

Re:My First Fifteen Compilers by ThinkBeat on Friday July 12, 2019 @06:47AM (#20419672)
and the code it produced was fast as well. IDE, Compiler and code all really fast (back then)
Re:My First Fifteen Compilers by tom_mellior on Saturday July 13, 2019 @12:15PM (#20428751)
Depends on what you mean by optimization standards, I guess. But a bare minimum for any compiler that wants to call itself optimizing is register allocation on whole functions. For that you need to build a representation of a whole function, do liveness analysis on it, then do the actual register assignment and spill code generation. That's at least three passes.
Re:My First Fifteen Compilers by sansnomme on Friday July 12, 2019 @09:05AM (#20420381)
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.
Re:My First Fifteen Compilers by dorfsmay on Friday July 12, 2019 @09:35AM (#20420561)
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.

Re:My First Fifteen Compilers by rickbutton on Friday July 12, 2019 @12:12PM (#20421750)
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".

Re:My First Fifteen Compilers by mojuba on Friday July 12, 2019 @09:36AM (#20420568)
Probably more to do with cross-CPU portability than laziness