3 ms·

> slow-ban I, too, can't post as many messages as I'd like. Not sure why, or how to change it, or how even to see if there's some limit imposed on me. Maybe <

by mafribe 11y ago

> slow-ban I, too, can't post as many messages as I'd like. Not sure why, or how to change it, or how even to see if there's some limit imposed on me. Maybe < 1000 rep users are throttled? > Maybe they're not ready for a compilers course then? We've been teaching compilers to 2nd years ever since the department was founded as far as I'm aware. The 2nd year is the right time to see how the programmer's most important tool works. > you don't have to roll out your own. I want students to write their own lexer and parser, and familiarise themselves with lexer/parser generators. This is an important part of a programmer's education. First, it let's them see the purpose of all that formal language theory they had to do in the first year. Second, and more important, working programmers have to design languages and write lexers/parsers all the time. A lot of commercial programming is about transforming data from one representation to another. In contrast, few programmers will ever write a real code generator. > you're teaching in a lunatics asylum I teach at a large, well-known and decidedly mediocre university. The kind of place that most working programmers graduate from. Needless to say that this is perfectly compatible with being a lunatics asylum. > truly efficient concurrent language is always very much > platform-specific Sure, but so what? That's like saying for truly efficient concurrent programming you need to program in assembly, because that's the only way to exploit all platform specific trickery. The purpose of high-level languages is to abstract away from the target platform. The additional goal of languages like C is to abstract as little as possible, so as to be platform independent while still allowing fast executables. In practise compilers for high-performance languages like C/C++ and Rust need to balance 3 contradictory goals. - Platform independence. - Fast executables. - Low cost of compiler development and evolution. Note that optimisations are by far the most expensive part of a compiler. Memory models are used in this balance: you want MMs that are platform agnostic, while still enabling powerful compiler optimisations. The CPU vendor has two more objectives (which is closely related to platform agnosticism): - Not giving away too many CPU internals. - Allowing CPU evolution. > Coq/HOL/ACL2 precise memory models Are they low-level models of CPUs that can also be used to reason about read/write reordering? Or are they genuine memory models, coming from the CPU manufacturers? As far as I'm aware, the construction of memory models these days is an empirical science like zoology, where people run experiments to confirm hypotheses about CPU behaviour. See eg. [1] > A very practical compiler can also be built as a beautiful and simple pipeline. Yes, and GHC is probably an example of this. But GHC is not simple by any stretch of the imagination. M Odersky once gave a talk (sorry, no reference handy) where he said that scalac, the Scala compiler, is no longer a pipeline, but has a database structure. That's because scalac's many stages cannot just live on the data feed by the immediate preceeding stage, and need to go back serveral stages sometime. Interesting. > you do not need a Turing-complete language to write a compiler. Type checking / inference in Haskell, Scala and C++ (among others) is Turing complete. Haskell's compile-time meta-programming extension Template Haskell, or scala.meta allow you to perform arbitrary computations as part of the code generation process, and do so by recursively invoking itself. On top of this, the control of a Turing machine is a finite state automata. So it's very simple too. Finally, I don't see the significance of Turing completeness here. You can write highly complicated programs in small fragments of Turing complete languages (e.g. Calculus of Constructions). This is the point of "Total Functional Programming" [2]. Indeed almost everything the typical working programmer writes is primitive recursive. Why do we have Turing complete programming languages? Because using just primitive recursion is really inconvenient. Try writing a trivial 4-line program like the ancient algorithm computing the greatest common denominator using just primitive recursion [3]. It's already annoying. So unrestricted recursion is a convenience, making programs more readable and shorter. Imagine you had to write type inferencers, graph-colouring based register allocators or program analyses based on fix-point iteration using just primitive recursion. Ugh! > some primitive form of term rewriting of a single input tree into a single output tree. Term rewriting is Turing complete. So yes, you can transform any compiler into a term rewriting system. So what? If you transform a sophisticated, industrial-strength compiler like GHC or scalac into a TRS, you end up with a very complex TRS that is difficult to understand. You cannot hide intrinsic complexity. You can kick the can down the road, and change the form in which the complexity manifests itself. > Such a chain is as simple as its most complex building block. Consider the Turing complete language {S, K} of combinators. By your reasoning any program written as SK combinators should be simple, because the building block are trivial. > JIT is a totally different beast Not really. In a way, JITs are simpler than AOTs in that the optimisations they run are simpler (eg register alloc by linear scan rather than graph colouring), and tracing JIT optimisations are simpler still since they traces they work on have linear control flow, which drastically simplifies the optimisation. Indeed that's the point of traces. The main complication of JITs is the seamless switching between interpretation and execution of compiled fragments. > existing JITs are idiotically, needlessly overcomplicated. Extraordinary claims require extraordinary evidence. The JIT teams at Oracle, Google, or Microsoft would like to hear from you if you can lower the cost of JIT compiler construction. > nanopass compilers are ... I have nothing against nano-pass compilers, and using a lot of immutable datastructures is fine. IIRC ocamlopt is heavily based on immutability, and it's one of the fastest compilers around. Whether nanopass is better for formal reasoning about compiler correctness remains to be seen. In formal reasoning it doesn't actually matter that much if information is passed explicitly by argument, or is global state, since either way, your logic has to keep track of it. But whether nano- or otherwise, the complexity is intrinsic in the problem of compilation, which is about bridging the semantic gap between two languages. And the bigger the semantic gap, the more complicated the task. [1] J. Alglave et al., Herding cats: Modelling, Simulation, Testing, and Data-mining for Weak Memory. http://www0.cs.ucl.ac.uk/staff/J.Alglave/papers/toplas14.pdf http://www0.cs.ucl.ac.uk/staff/J.Alglave/papers/toplas14.pdf [2] D. A. Turner, Total Functional Programming. http://sblp2004.ic.uff.br/papers/turner.pdf http://sblp2004.ic.uff.br/papers/turner.pdf [3] R. Harper, Old neglected theorems are still theorems. https://existentialtype.wordpress.com/2014/03/20/old-neglected-theorems-are-still-theorems/ https://existentialtype.wordpress.com/2014/03/20/old-neglect...

sklogic 11y ago
> Needless to say that this is perfectly compatible with being a lunatics asylum. I see... Yes, I'we been exposed to the quality of the intake of the so-called "new" universities (in the UK). Just did not think they're learning anything beyond Excel. > I want students to write their own lexer and parser, and familiarise themselves with lexer/parser generators. This is an important part of a programmer's education. I agree. It should follow the compilers course, once everything of importance there is properly absorbed. > In contrast, few programmers will ever write a real code generator. And this is where I cannot agree at all. I believe that everyone must build multiple compilers, routinely, on a daily basis. The reason to think so is: 1) DSLs are an ultimate answer to a complexity problem. And compilation is the best way to implement them easily. 2) Compilers are often present in where you won't even expect to find anything like a compilation. Protocols, UIs, business logic, databases, whatever. And, given the property of a compiler that it can be reduced to a tiny complexity (we'll get back to it later), it is extremely important to be able to spot such patterns early and convert your architecture to a compiler. And, of course, all such incidental compilers got absolutely nothing to do with any kind of a parsing. Their source languages are already some data structures (even graphs), almost never a plain boring stream of characters. > The purpose of high-level languages is to abstract away from the target platform. Impossible if your target platforms concurrency models are incompatible. You cannot fit message passing into a SPMD, and vice versa. > Note that optimisations are by far the most expensive part of a compiler. Not necessarily. For C++, for example, all the optimisations, even with a polyhedral vectorisation, abstract interpretation, partial specialisation and all the bells and whistles, are nothing compared to a mere template expansion. See the clang+llvm profiling data. > Or are they genuine memory models, coming from the CPU manufacturers? Not "coming" anywhere, unfortunately. They're all internal models. Not available even under an NDA. > But GHC is not simple by any stretch of the imagination. It got quite a few gotchas, to be honest. I'd definitely design it differently. And, Haskell is not the best language for this sort of things - see the "expression problem". A Scrap Your Boilerplate library is sort of fixing part of these issues, but it is not used inside GHC. > That's because scalac's many stages cannot just live on the data feed by the immediate preceeding stage, and need to go back serveral stages sometime. Interesting. It is exceptionally over-engineered. But, yes, there is a reason to have a backtracking in a compiler pipeline. While still having a linear pipeline (at the end of the day it is linear, but it may be branching and going back to try out certain hypothesis). I've been experimenting with this approach a lot. It does not increase complexity in any way. > Type checking / inference in Haskell, Scala and C++ (among others) is Turing complete. Firstly, for most of your DSLs you don't need such a type system. Secondly, all the implementations I've seen are extremely overengineered, and I've got no idea why. In fact, any Hindley-Milner like type system is laughably trivial, and the Turing-complete part of it is very much isolated (and you don't have to code it, just use an existing library). Hindley-Milner unification is not any different from Prolog unification, so my way of implementing these type systems is to simply compile your AST into a flat list of Prolog equations (see the recent history of my posts for this method explained in depth). > So it's very simple too. It's not. You cannot reason about it. > This is the point of "Total Functional Programming" Exactly. You don't need anything beyond a simple total language for your entire compiler (or, if you're implementing some metaprogramming, abstract interpretation or a Turing-complete type system, a 99.99% of your compiler, with the rest being well-isolated and reused over and over again). > Term rewriting is Turing complete. You only need a subset of term rewriting, which you can express in a total language. > In a way, JITs are simpler than AOTs in that the optimisations they run are simpler Yet, they're interpreters, especially the tracing ones. And interpreters are inherently orders of magnitude more complex than compilers. > By your reasoning any program written as SK combinators should be simple, because the building block are trivial. Not really. You're combining them in a deep, horrible tree, not a linear pipeline of isolated things. > Extraordinary claims require extraordinary evidence. I do not see anything extraordinary in an obvious notion of corporate coding being thoroughly broken. It's a common knowledge. > In formal reasoning it doesn't actually matter that much if information is passed explicitly by argument, or is global state, since either way, your logic has to keep track of it. It matters. If all you have is a language as an input and another language as an output, without any global state, then every chunk of your pipeline is isolated and you can comprehend it without thinking about the rest. That's exactly why the complexity of the passes do not add up, and the total complexity is only a complexity of the worst of the passes. > the complexity is intrinsic in the problem of compilation I've never seen anything complex there. After over 20 years in the field. > which is about bridging the semantic gap between two languages. It's not a chasm, you don't have to cross it in one step. Just build a hundred of trivial passes in between, one step at a time. > And the bigger the semantic gap, the more complicated the task. No, complexity do not grow. Mind giving an example of the opposite? P.S. Also, one of the nice properties of the compilers is that you can abstract out and reuse a lot of routine stuff. Register allocation? Write it once and reuse everywhere. SSA? Implement it once and reuse for any imaginable IR. Typing? See above. Constant folding, ADCE, inlining, etc? Write it once and reuse for all the possible IRs.

by mafribe 11y ago

sklogic 11y ago

> Needless to say that this is perfectly compatible with being a lunatics asylum. I see... Yes, I'we been exposed to the quality of the intake of the so-called "new" universities (in the UK). Just did not think they're learning anything beyond Excel. > I want students to write their own lexer and parser, and familiarise themselves with lexer/parser generators. This is an important part of a programmer's education. I agree. It should follow the compilers course, once everything of importance there is properly absorbed. > In contrast, few programmers will ever write a real code generator. And this is where I cannot agree at all. I believe that everyone must build multiple compilers, routinely, on a daily basis. The reason to think so is: 1) DSLs are an ultimate answer to a complexity problem. And compilation is the best way to implement them easily. 2) Compilers are often present in where you won't even expect to find anything like a compilation. Protocols, UIs, business logic, databases, whatever. And, given the property of a compiler that it can be reduced to a tiny complexity (we'll get back to it later), it is extremely important to be able to spot such patterns early and convert your architecture to a compiler. And, of course, all such incidental compilers got absolutely nothing to do with any kind of a parsing. Their source languages are already some data structures (even graphs), almost never a plain boring stream of characters. > The purpose of high-level languages is to abstract away from the target platform. Impossible if your target platforms concurrency models are incompatible. You cannot fit message passing into a SPMD, and vice versa. > Note that optimisations are by far the most expensive part of a compiler. Not necessarily. For C++, for example, all the optimisations, even with a polyhedral vectorisation, abstract interpretation, partial specialisation and all the bells and whistles, are nothing compared to a mere template expansion. See the clang+llvm profiling data. > Or are they genuine memory models, coming from the CPU manufacturers? Not "coming" anywhere, unfortunately. They're all internal models. Not available even under an NDA. > But GHC is not simple by any stretch of the imagination. It got quite a few gotchas, to be honest. I'd definitely design it differently. And, Haskell is not the best language for this sort of things - see the "expression problem". A Scrap Your Boilerplate library is sort of fixing part of these issues, but it is not used inside GHC. > That's because scalac's many stages cannot just live on the data feed by the immediate preceeding stage, and need to go back serveral stages sometime. Interesting. It is exceptionally over-engineered. But, yes, there is a reason to have a backtracking in a compiler pipeline. While still having a linear pipeline (at the end of the day it is linear, but it may be branching and going back to try out certain hypothesis). I've been experimenting with this approach a lot. It does not increase complexity in any way. > Type checking / inference in Haskell, Scala and C++ (among others) is Turing complete. Firstly, for most of your DSLs you don't need such a type system. Secondly, all the implementations I've seen are extremely overengineered, and I've got no idea why. In fact, any Hindley-Milner like type system is laughably trivial, and the Turing-complete part of it is very much isolated (and you don't have to code it, just use an existing library). Hindley-Milner unification is not any different from Prolog unification, so my way of implementing these type systems is to simply compile your AST into a flat list of Prolog equations (see the recent history of my posts for this method explained in depth). > So it's very simple too. It's not. You cannot reason about it. > This is the point of "Total Functional Programming" Exactly. You don't need anything beyond a simple total language for your entire compiler (or, if you're implementing some metaprogramming, abstract interpretation or a Turing-complete type system, a 99.99% of your compiler, with the rest being well-isolated and reused over and over again). > Term rewriting is Turing complete. You only need a subset of term rewriting, which you can express in a total language. > In a way, JITs are simpler than AOTs in that the optimisations they run are simpler Yet, they're interpreters, especially the tracing ones. And interpreters are inherently orders of magnitude more complex than compilers. > By your reasoning any program written as SK combinators should be simple, because the building block are trivial. Not really. You're combining them in a deep, horrible tree, not a linear pipeline of isolated things. > Extraordinary claims require extraordinary evidence. I do not see anything extraordinary in an obvious notion of corporate coding being thoroughly broken. It's a common knowledge. > In formal reasoning it doesn't actually matter that much if information is passed explicitly by argument, or is global state, since either way, your logic has to keep track of it. It matters. If all you have is a language as an input and another language as an output, without any global state, then every chunk of your pipeline is isolated and you can comprehend it without thinking about the rest. That's exactly why the complexity of the passes do not add up, and the total complexity is only a complexity of the worst of the passes. > the complexity is intrinsic in the problem of compilation I've never seen anything complex there. After over 20 years in the field. > which is about bridging the semantic gap between two languages. It's not a chasm, you don't have to cross it in one step. Just build a hundred of trivial passes in between, one step at a time. > And the bigger the semantic gap, the more complicated the task. No, complexity do not grow. Mind giving an example of the opposite? P.S. Also, one of the nice properties of the compilers is that you can abstract out and reuse a lot of routine stuff. Register allocation? Write it once and reuse everywhere. SSA? Implement it once and reuse for any imaginable IR. Typing? See above. Constant folding, ADCE, inlining, etc? Write it once and reuse for all the possible IRs.