Re: [Haskell-cafe] Compilers: Why do we need a core language?
On 24/11/2012, at 5:26 PM, wren ng thornton wrote: On 11/20/12 6:54 AM, c...@lavabit.com wrote: Hello, I know nothing about compilers and interpreters. I checked several books, but none of them explained why we have to translate a high-level language into a small (core) language. Is it impossible (very hard) to directly translate high-level language into machine code? It is possible to remove stages in the standard compilation pipeline, and doing so can speed up compilation time. For example, Perl doesn't build an abstract syntax tree (for now-outdated performance reasons), and instead compiles the source language directly into bytecode (which is then interpreted by the runtime). This is one of the reasons why Perl is (or was?) so much faster than other interpreted languages like Python etc. I have found Perl anything from the same speed as AWK (reading and writing lots of data with hardly any processing) to 10 times slower than AWK (with respect to the 'mawk' implementation of AWK). The deeply saddening thing here is that there are lots of improvements I _know_ how to make to mawk to make it even faster, but the thing that stops me is the way mawk generates word-code directly without an AST. I don't know why Perl is direct-to-byte-code, but I'm pretty sure why mawk is direct-to-word-code and The One True Awk interprets its AST. AWK used to run on PDP-11s and for large source files had room for VM instructions or ASTs but not both at the same time. Designing a compiler for fast *compiling* leads to one kind of design; designing for fast *running* of generated code leads to another. And run times for scripting languages depends on things like the structure of hash tables, the quality of hashing functions, the cripplingly excessive richness of certain regular expression libraries, the memory management scheme, ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
On 22/11/2012 11:52 AM, Brandon Allbery wrote: On Thu, Nov 22, 2012 at 7:56 AM, Jacques Carette care...@mcmaster.ca mailto:care...@mcmaster.ca wrote: On 20/11/2012 6:08 PM, Richard O'Keefe wrote: On 21/11/2012, at 4:49 AM, c...@lavabit.com mailto:c...@lavabit.com wrote: Well, I don't know. Would it save some time? Why bother with a core language? For a high level language (and for this purpose, even Fortran 66 counts as high level) you really don't _want_ a direct translation from source code to object code. You want to eliminate unused code and you want to do all sorts of analyses and improvements. It is *much* easier to do all that to a small core language than to the full source language. Actually, here I disagree. It might be much 'easier' for the programmers to do it for a small core language, but it may turn out to be much, much less effective. I 'discovered' this when (co-)writing a partial evaluator for Maple: You're still using a core language, though; just with a slightly different focus than Haskell's. I already mentioned gcc's internal language, which similarly is larger (semantically; syntactically it's sexprs). What combination is more appropriate depends on the language and the compiler implementation. Right, we agree: it is not 'core language' I disagreed with, it is 'smaller core language'. And we also agree that smaller/larger depends on the eventual application. But 'smaller core language' is so ingrained as conventional wisdom that I felt compelled to offer evidence against this bit of folklore. Jacques ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
On 22/11/2012 7:37 PM, Richard O'Keefe wrote: On 23/11/2012, at 1:56 AM, Jacques Carette wrote: Actually, here I disagree. It might be much 'easier' for the programmers to do it for a small core language, but it may turn out to be much, much less effective. I 'discovered' this when (co-)writing a partial evaluator for Maple: we actually made our internal language *larger*, so that we could encode more invariants syntactically. This ended up making our jobs considerably easier, because we did not have to work so hard on doing fancy analyses to recover information that would otherwise have been completely obvious. Yes, there were a lot more cases, but each case was relatively easy; the alternative was a small number of extremely difficult cases. I don't think we do disagree. We are talking about the same thing: ``not hav[ing] to work so hard on doing fancy analyses''. The key point is that an (abstract) syntax *designed for the compiler* and a syntax *designed for programmers* have to satisfy different design goals and constraints; there's no reason they should be the same. I must have mis-interpreted what you said then. We definitely agree on this key point. Jacques ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
Jacques Carette care...@mcmaster.ca wrote: On 22/11/2012 11:52 AM, Brandon Allbery wrote: On Thu, Nov 22, 2012 at 7:56 AM, Jacques Carette care...@mcmaster.ca mailto:care...@mcmaster.ca wrote: On 20/11/2012 6:08 PM, Richard O'Keefe wrote: On 21/11/2012, at 4:49 AM, c...@lavabit.com mailto:c...@lavabit.com wrote: Well, I don't know. Would it save some time? Why bother with a core language? For a high level language (and for this purpose, even Fortran 66 counts as high level) you really don't _want_ a direct translation from source code to object code. You want to eliminate unused code and you want to do all sorts of analyses and improvements. It is *much* easier to do all that to a small core language than to the full source language. Actually, here I disagree. It might be much 'easier' for the programmers to do it for a small core language, but it may turn out to be much, much less effective. I 'discovered' this when (co-)writing a partial evaluator for Maple: You're still using a core language, though; just with a slightly different focus than Haskell's. I already mentioned gcc's internal language, which similarly is larger (semantically; syntactically it's sexprs). What combination is more appropriate depends on the language and the compiler implementation. Right, we agree: it is not 'core language' I disagreed with, it is 'smaller core language'. And we also agree that smaller/larger depends on the eventual application. But 'smaller core language' is so ingrained as conventional wisdom that I felt compelled to offer evidence against this bit of folklore. I don't think you're evidence contacts that bit of folklore. But as stated it's vague. In particular, is smaller relative to the full source language, or is it absolute (in which case you should compile to a RISC architecture and optimize that :-)? Since the latter seems silly, I have to ask if your core language for Maple was larger than Maple? -- Sent from my Android tablet with K-9 Mail. Please excuse my swyping. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
On 23/11/2012 9:59 AM, Mike Meyer wrote: [...] I have to ask if your core language for Maple was larger than Maple? Yes. Maple 10 had 62 cases in its AST, we had 75 (p.13 of [1]) Jacques [1] http://www.cas.mcmaster.ca/~carette/publications/scp_MaplePE.pdf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
On 11/20/12 6:54 AM, c...@lavabit.com wrote: Hello, I know nothing about compilers and interpreters. I checked several books, but none of them explained why we have to translate a high-level language into a small (core) language. Is it impossible (very hard) to directly translate high-level language into machine code? It is possible to remove stages in the standard compilation pipeline, and doing so can speed up compilation time. For example, Perl doesn't build an abstract syntax tree (for now-outdated performance reasons), and instead compiles the source language directly into bytecode (which is then interpreted by the runtime). This is one of the reasons why Perl is (or was?) so much faster than other interpreted languages like Python etc. But there are some big problems to beware of: * Not having a concrete representation for intermediate forms can rule out performing obvious optimizations. And I do mean *obvious* optimizations; I can talk more about this problem in Perl, if you really care. * Not having a concrete representation for intermediate forms means mixing together code from many different stages of the compilation process. This sort of spaghetti code is hard to maintain, and even harder to explain to new developers. * Not having a concrete representation for intermediate forms can lead to code duplication (in the compiler) because there's no convenient way to abstract over certain patterns. And, of course, repeating code is just begging for inconsistency bugs due to the maintenance burden of keeping all the copies in sync. All three points are major driving forces in having intermediate forms. Joachim Breitner gave some illustrations for why intermediate forms are inevitable. But then, once you have intermediate forms, if you're interested in ensuring correctness and having a formal(izable) semantics, then it makes sense to try to turn those intermediate forms into an actual intermediate language. Intermediate forms are just an implementation detail, but intermediate languages can be reasoned about in the same ways as other languages. So it's more about shifting perspective in order to turn systems problems (implementation details) into language problems (semantics of the Core). Furthermore, if you're a PL person and really are trying to ensure correctness of your language (e.g., type safety), you want to try to make your proof obligation as small as possible. For convenience to programmers, source code is full of constructs which are all more or less equivalent. But this is a problem for making proofs because when we perform case analysis on an expression we have to deal with all those different syntactic forms. Whereas if you first compile everything down into a small core language, then the proof has far fewer syntactic forms it has to deal with and so the proof is much easier. Bear in mind that this isn't just a linear problem. If we have N different syntactic forms, then proving something like confluence will require proving O(N^2) cases since you're comparing two different terms. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
On 20/11/2012 6:08 PM, Richard O'Keefe wrote: On 21/11/2012, at 4:49 AM, c...@lavabit.com wrote: Well, I don't know. Would it save some time? Why bother with a core language? For a high level language (and for this purpose, even Fortran 66 counts as high level) you really don't _want_ a direct translation from source code to object code. You want to eliminate unused code and you want to do all sorts of analyses and improvements. It is *much* easier to do all that to a small core language than to the full source language. Actually, here I disagree. It might be much 'easier' for the programmers to do it for a small core language, but it may turn out to be much, much less effective. I 'discovered' this when (co-)writing a partial evaluator for Maple: we actually made our internal language *larger*, so that we could encode more invariants syntactically. This ended up making our jobs considerably easier, because we did not have to work so hard on doing fancy analyses to recover information that would otherwise have been completely obvious. Yes, there were a lot more cases, but each case was relatively easy; the alternative was a small number of extremely difficult cases. Jacques ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
On Thu, Nov 22, 2012 at 7:56 AM, Jacques Carette care...@mcmaster.cawrote: On 20/11/2012 6:08 PM, Richard O'Keefe wrote: On 21/11/2012, at 4:49 AM, c...@lavabit.com wrote: Well, I don't know. Would it save some time? Why bother with a core language? For a high level language (and for this purpose, even Fortran 66 counts as high level) you really don't _want_ a direct translation from source code to object code. You want to eliminate unused code and you want to do all sorts of analyses and improvements. It is *much* easier to do all that to a small core language than to the full source language. Actually, here I disagree. It might be much 'easier' for the programmers to do it for a small core language, but it may turn out to be much, much less effective. I 'discovered' this when (co-)writing a partial evaluator for Maple: You're still using a core language, though; just with a slightly different focus than Haskell's. I already mentioned gcc's internal language, which similarly is larger (semantically; syntactically it's sexprs). What combination is more appropriate depends on the language and the compiler implementation. -- brandon s allbery kf8nh sine nomine associates allber...@gmail.com ballb...@sinenomine.net unix/linux, openafs, kerberos, infrastructure http://sinenomine.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
On 23/11/2012, at 1:56 AM, Jacques Carette wrote: On 20/11/2012 6:08 PM, Richard O'Keefe wrote: On 21/11/2012, at 4:49 AM, c...@lavabit.com wrote: Well, I don't know. Would it save some time? Why bother with a core language? For a high level language (and for this purpose, even Fortran 66 counts as high level) you really don't _want_ a direct translation from source code to object code. You want to eliminate unused code and you want to do all sorts of analyses and improvements. It is *much* easier to do all that to a small core language than to the full source language. Actually, here I disagree. It might be much 'easier' for the programmers to do it for a small core language, but it may turn out to be much, much less effective. I 'discovered' this when (co-)writing a partial evaluator for Maple: we actually made our internal language *larger*, so that we could encode more invariants syntactically. This ended up making our jobs considerably easier, because we did not have to work so hard on doing fancy analyses to recover information that would otherwise have been completely obvious. Yes, there were a lot more cases, but each case was relatively easy; the alternative was a small number of extremely difficult cases. I don't think we do disagree. We are talking about the same thing: ``not hav[ing] to work so hard on doing fancy analyses''. The key point is that an (abstract) syntax *designed for the compiler* and a syntax *designed for programmers* have to satisfy different design goals and constraints; there's no reason they should be the same. As a very very crude example of this, with its user-defined operators, Prolog lets you write rules using lots of (unquoted) operators to express yourself in an quasi-English sort of way, e.g., if Block must move and top of Block is not clear then clear top of Block. Readable. But lousy for processing. You'd want to change it to something like action(clear_top(Block), [ must_move(Block), \+ top_is_clear(Block)]). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
I believe the question you are asking is why do large software systems need to be designed in terms of levels or some other software engineering construct(s). To manage their complexity as opposed to getting mangled in their complexity. :D -- -- Regards, KC ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
Hey, Here are some interesting links you that might help answer your question. http://www.aosabook.org/en/ghc.html http://www.youtube.com/watch?v=7NPBrWDzO2A Regards, José On 11/20/2012 12:54 PM, c...@lavabit.com wrote: Hello, I know nothing about compilers and interpreters. I checked several books, but none of them explained why we have to translate a high-level language into a small (core) language. Is it impossible (very hard) to directly translate high-level language into machine code? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
Le Tue, 20 Nov 2012 06:54:25 -0500 (EST), c...@lavabit.com a écrit : Hello, I know nothing about compilers and interpreters. I checked several books, but none of them explained why we have to translate a high-level language into a small (core) language. Is it impossible (very hard) to directly translate high-level language into machine code? What would be the point in doing so? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
What would be the point in doing so? Well, I don't know. Would it save some time? Why bother with a core language? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
Le Tue, 20 Nov 2012 10:49:01 -0500 (EST), c...@lavabit.com a écrit : What would be the point in doing so? Well, I don't know. Would it save some time? Why bother with a core language? The compilation process might be slightly faster, but I guess it wouldn't be much noticeable. Also I guess having a core language eases porting to new architectures, you just have to port a simple core language rather than porting a complex language. The semantics of the core language is also rather simple, so you can use it to explain and understand how it works, then for the high level part, you can give a semantics by compilation to the core language. Finally, adding a new feature seems easier and less error prone if you have to translate it into the core language rather than compiling it directly. I never studied the Haskell compiler so I do not know the details, but I think that having a core language is a good idea. It is also good to have some VM to porting purposes. If you have N source languages and M target machines, by providing N+M stuff, you get N×M compilers ! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
Hi, Am Dienstag, den 20.11.2012, 06:54 -0500 schrieb c...@lavabit.com: I know nothing about compilers and interpreters. I checked several books, but none of them explained why we have to translate a high-level language into a small (core) language. Is it impossible (very hard) to directly translate high-level language into machine code? I would expect that even if you were to implement a compiler for full Haskell itself, you would end up generating a core language. E.g, where clauses can be implemented using let. So after you have implemented let you are likely to not copy the code but rather transform your where clause into a let clause. And alas, you suddenly have introduced a core language (Haskell without where clauses). This way you will end up with a very reduced subset of Haskell. Then you might also notice that some features are similar to implement and you can merge the code if you add some feature to your language, making it a bit more expressive. Then your core language will be more than just a subset of Haskell. As you can see, you will have a hard time preventing yourself from introducing a core language. Greetings, Joachim -- Joachim Breitner e-Mail: m...@joachim-breitner.de Homepage: http://www.joachim-breitner.de Jabber-ID: nome...@joachim-breitner.de signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
On Tue, Nov 20, 2012 at 6:54 AM, c...@lavabit.com wrote: I know nothing about compilers and interpreters. I checked several books, but none of them explained why we have to translate a high-level language into a small (core) language. Is it impossible (very hard) to directly translate high-level language into machine code? You might note that gcc does the same thing internally; its core seems to be inspired by S-expressions. (It's also somewhat lower level than GHC's core, but then C is itself lower level.) As for why: * It's a way to remove redundancy and simplify implementation. * Sometimes it's easier to rephrase a language feature in terms of another similar feature, instead of duplicating code or making that code sufficiently reusable to apply easily in multiple not-quite-identical places. * Sometimes it's because the language definition specifies a translation that describes the behavior of a language feature (see, for example, do blocks and automatically derived typeclasses in Haskell) and the simplest way to ensure compliance with the standard is to do the same translation in the compiler. * It can also be easier to apply high level optimization techniques; if you go straight from the highest level code to the lowest level, you are likely to miss optimization opportunities that are only revealed (or only sanely implementable) at intermediate levels. -- brandon s allbery kf8nh sine nomine associates allber...@gmail.com ballb...@sinenomine.net unix/linux, openafs, kerberos, infrastructure http://sinenomine.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
Is it impossible (very hard) to directly translate high-level language into machine code? There's a context to your question I don't understand, so let me ask: Wouldn't it be easier to break a big step into smaller baby steps? And if it's indeed easier why wouldn't you choose that route? -- Kim-Ee On Tue, Nov 20, 2012 at 6:54 PM, c...@lavabit.com wrote: Hello, I know nothing about compilers and interpreters. I checked several books, but none of them explained why we have to translate a high-level language into a small (core) language. Is it impossible (very hard) to directly translate high-level language into machine code? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
On 12-11-20 06:54 AM, c...@lavabit.com wrote: I know nothing about compilers and interpreters. I checked several books, but none of them explained why we have to translate a high-level language into a small (core) language. Is it impossible (very hard) to directly translate high-level language into machine code? Let the overall distance be fixed. More steps over that same distance means each step is smaller, easier to design, easier to understand, easier to correct if there are mistakes. Forget code generation. Just parse and validate and then discard. Already there are like 4 steps. Translate character sequence into token sequence. Translate token sequence into grammar tree, while checking grammar. Translate grammar tree into declaration groups, identifier lookup tables, etc., while checking whether every used identifier is declared or imported. Translate those groups and tables into type-annotated groups and tables, while checking types. Whew! After 4 steps of translating this to that, we still haven't reached the core language! Why? Because... have you ever tried to write a type-checker for character sequence? I'm sure some mad genius can do it, but I don't want to be that mad genius. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
* It can also be easier to apply high level optimization techniques; if you go straight from the highest level code to the lowest level, you are likely to miss optimization opportunities that are only revealed (or only sanely implementable) at intermediate levels. Not to mention that since optimizations are often expressed as replacements (note how stream fusions are implemented), optimizing after desugaring reduces the number of patterns an optimization needs to match against. By my understanding, GHC does not compile to core and then reparse the core file; 'core' is merely the name given to a certain stage in syntax tree manipulations. Thus, a compiler with no analogue of core would forego all syntax tree manipulations, instead taking the raw parse tree and running the code generator on that. And while that can be done for a sufficiently simple language, for a language with the complexity of Haskell I dare say that it is impossible: Because... have you ever tried to write a type-checker for character sequence? I'm sure some mad genius can do it, but I don't want to be that mad genius. -- Ian Sturdy sturdy...@mail.wlu.edu From: haskell-cafe-boun...@haskell.org [haskell-cafe-boun...@haskell.org] on behalf of Albert Y. C. Lai [tre...@vex.net] Sent: Tuesday, November 20, 2012 12:47 PM To: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Compilers: Why do we need a core language? On 12-11-20 06:54 AM, c...@lavabit.com wrote: I know nothing about compilers and interpreters. I checked several books, but none of them explained why we have to translate a high-level language into a small (core) language. Is it impossible (very hard) to directly translate high-level language into machine code? Let the overall distance be fixed. More steps over that same distance means each step is smaller, easier to design, easier to understand, easier to correct if there are mistakes. Forget code generation. Just parse and validate and then discard. Already there are like 4 steps. Translate character sequence into token sequence. Translate token sequence into grammar tree, while checking grammar. Translate grammar tree into declaration groups, identifier lookup tables, etc., while checking whether every used identifier is declared or imported. Translate those groups and tables into type-annotated groups and tables, while checking types. Whew! After 4 steps of translating this to that, we still haven't reached the core language! Why? Because... have you ever tried to write a type-checker for character sequence? I'm sure some mad genius can do it, but I don't want to be that mad genius. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers: Why do we need a core language?
On 21/11/2012, at 4:49 AM, c...@lavabit.com wrote: What would be the point in doing so? Well, I don't know. Would it save some time? Why bother with a core language? For a high level language (and for this purpose, even Fortran 66 counts as high level) you really don't _want_ a direct translation from source code to object code. You want to eliminate unused code and you want to do all sorts of analyses and improvements. It is *much* easier to do all that to a small core language than to the full source language. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
