3 ms·

You should have done it in a homoiconic language like Scheme, where nobody would be puzzled by a notion of an AST.

by sklogic 11y ago

mafribe 11y ago
Then my students would have been puzzled by Scheme, which they don't know. Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme. The only advantage is that Scheme's syntax is simple. Moreover the problem of language representation doesn't go away. You still need to represent programs. The real problem is to understand that there are two level: programs and representations of programs. Avoiding to confuse the two is the real challenge, and it remains a challenge in Scheme.
- sklogic 11y ago
  Sorry, I'm under a slow-ban here (currently like 2 posts in 6 hours allowance), so I'll answer to all your posts at once here. > Then my students would have been puzzled by Scheme, which they don't know. Maybe they're not ready for a compilers course then? You could have saved a lot of time and effort for them this way. > Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme. It can have as much syntax as you want. Nobody cares - there is already a parser, ready to use, and you don't have to roll out your own. > The real problem is to understand that there are two level: programs and representations of programs. This is the most important takeaway from a compilers course. It makes sense to get there as soon as possible. Also, I'm a bit skeptical about your assessment of your students, from your words it sounds like you're teaching in a lunatics asylum. > https://news.ycombinator.com/reply?id=11281976 https://news.ycombinator.com/reply?id=11281976 > you need a platform independent memory model Sorry, this is a wishful thinking. A truly efficient concurrent language is always very much platform-specific (think of Occam on one side of the spectrum and OpenCL and Cuda on another). > nobody really knows what exactly the memory model is Really? I've seen a number of Coq/HOL/ACL2 precise memory models of certain architectures. > https://news.ycombinator.com/reply?id=11282014 https://news.ycombinator.com/reply?id=11282014 > idealised compilers have a beautiful pipeline structure A very practical compiler can also be built as a beautiful and simple pipeline. > By this reasoning, any computable problem is trivially simple, because I can translate it into ARM/x86/MIPS/... machine code, and machine code is just a linear list of trivial commands, i.e. I can "turn it into a laughably simple chain". You did not get it at all. You cannot translate "any code" into a linear trivial sequence with each step being nothing but some primitive form of term rewriting of a single input tree into a single output tree. A trivial proof for how badly wrong you are: you do not need a Turing-complete language to write a compiler. Now try to apply this to your "any computable problem" reasoning. > if you chain enough simple things, the result stops being simple. Incorrect. Such a chain is as simple as its most complex building block. Complexity does not add up. > Look for example at modern JIT compilers, tracing or otherwise. Firstly, we're talking about the proper compilers here. JIT is a totally different beast, it got a very severe performance constraint. Secondly, even JIT can be structured this way, and most of the existing JITs are idiotically, needlessly overcomplicated. > They are not simple by any stretch of the imagination. Sorry, but no, they are. Yes, the non-Turing-complete property breaks there, as well as with any other interpreter, but a Turing-complete subset of a JIT compiler can be very easily isolated. > https://news.ycombinator.com/reply?id=11279390 https://news.ycombinator.com/reply?id=11279390 > Optimisations are easy only if you can accept the optimisation process to be slow, and/or the resulting code buggy. And this is nothing but a FUD. Firstly, nanopass compilers are not any slower than the fused ones. In some cases they're faster, due to some of the nice properties of the immutability. Also, you can fuse some passes automatically, while still keeping your code trivial. Secondly, the simpler your passes are, the easier it is to reason about their correctness. Compare it to the notoriously shitty instcombine pass in LLVM, as it is an example of the opposite approach (the one you're apparently advocating).
  - 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...

You should have done it in a homoiconic language like Scheme, where nobody would be puzzled by a notion of an AST.

by sklogic 11y ago

You should have done it in a homoiconic language like Scheme, where nobody would be puzzled by a notion of an AST.

Then my students would have been puzzled by Scheme, which they don't know. Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme. The only advantage is that Scheme's syntax is simple. Moreover the problem of language representation doesn't go away. You still need to represent programs. The real problem is to understand that there are two level: programs and representations of programs. Avoiding to confuse the two is the real challenge, and it remains a challenge in Scheme.

sklogic 11y ago
Sorry, I'm under a slow-ban here (currently like 2 posts in 6 hours allowance), so I'll answer to all your posts at once here. > Then my students would have been puzzled by Scheme, which they don't know. Maybe they're not ready for a compilers course then? You could have saved a lot of time and effort for them this way. > Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme. It can have as much syntax as you want. Nobody cares - there is already a parser, ready to use, and you don't have to roll out your own. > The real problem is to understand that there are two level: programs and representations of programs. This is the most important takeaway from a compilers course. It makes sense to get there as soon as possible. Also, I'm a bit skeptical about your assessment of your students, from your words it sounds like you're teaching in a lunatics asylum. > https://news.ycombinator.com/reply?id=11281976 https://news.ycombinator.com/reply?id=11281976 > you need a platform independent memory model Sorry, this is a wishful thinking. A truly efficient concurrent language is always very much platform-specific (think of Occam on one side of the spectrum and OpenCL and Cuda on another). > nobody really knows what exactly the memory model is Really? I've seen a number of Coq/HOL/ACL2 precise memory models of certain architectures. > https://news.ycombinator.com/reply?id=11282014 https://news.ycombinator.com/reply?id=11282014 > idealised compilers have a beautiful pipeline structure A very practical compiler can also be built as a beautiful and simple pipeline. > By this reasoning, any computable problem is trivially simple, because I can translate it into ARM/x86/MIPS/... machine code, and machine code is just a linear list of trivial commands, i.e. I can "turn it into a laughably simple chain". You did not get it at all. You cannot translate "any code" into a linear trivial sequence with each step being nothing but some primitive form of term rewriting of a single input tree into a single output tree. A trivial proof for how badly wrong you are: you do not need a Turing-complete language to write a compiler. Now try to apply this to your "any computable problem" reasoning. > if you chain enough simple things, the result stops being simple. Incorrect. Such a chain is as simple as its most complex building block. Complexity does not add up. > Look for example at modern JIT compilers, tracing or otherwise. Firstly, we're talking about the proper compilers here. JIT is a totally different beast, it got a very severe performance constraint. Secondly, even JIT can be structured this way, and most of the existing JITs are idiotically, needlessly overcomplicated. > They are not simple by any stretch of the imagination. Sorry, but no, they are. Yes, the non-Turing-complete property breaks there, as well as with any other interpreter, but a Turing-complete subset of a JIT compiler can be very easily isolated. > https://news.ycombinator.com/reply?id=11279390 https://news.ycombinator.com/reply?id=11279390 > Optimisations are easy only if you can accept the optimisation process to be slow, and/or the resulting code buggy. And this is nothing but a FUD. Firstly, nanopass compilers are not any slower than the fused ones. In some cases they're faster, due to some of the nice properties of the immutability. Also, you can fuse some passes automatically, while still keeping your code trivial. Secondly, the simpler your passes are, the easier it is to reason about their correctness. Compare it to the notoriously shitty instcombine pass in LLVM, as it is an example of the opposite approach (the one you're apparently advocating).
- 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...