bard@THEORY.LCS.MIT.EDU (11/16/88)
> > Mark VandeWettering writes: > > I think (and my thesis work is evolving into this kind of > argument) that Y is overlooked for trivial reasons. Partial > evaluation and smarter code generation could make an SK based > compiler generate code which is equal in quality to that produced > by supercombinator based compilation. I thought that the reason for using supercombinators rather than S and K is space. Ordinary \-calculus expressions can be translated into SK-combinatory expressions, but the combinatory version is exponentially longer than the SK term. Some sets of supercombinators give polynomial-length expansions; I think some give linear expansions. Now, code size isn't usually much of a problem, in that we don't usually care whether a program is 50K or 250K. The difference between 50K and 2^50K is significant. I don't know if the translation has a decent expected case or not. In any event, the SK compiler has a lot of work to do before it can match even a fairly stupid supercombinator compiler, simply because it can be forced to produce incredibly long code. My guess, and I gather the guess of many people who actually work on this, is that SK would lose. I would be very interested in some proof that this guess was wrong. -- Bard Bloom
jeschke@iuvax.cs.indiana.edu (Eric Jeschke) (11/17/88)
Mark VandeWettering writes: | | I think (and my thesis work is evolving into this kind of | argument) that Y is overlooked for trivial reasons. Partial | evaluation and smarter code generation could make an SK based | compiler generate code which is equal in quality to that produced | by supercombinator based compilation. | Bard Bloom points out the space problem: |I thought that the reason for using supercombinators rather than S and K is |space. | <stuff deleted> | | In any event, the SK compiler has a lot of work to do before it can match |even a fairly stupid supercombinator compiler, simply because it can be |forced to produce incredibly long code. My guess, and I gather the guess of |many people who actually work on this, is that SK would lose. I would be |very interested in some proof that this guess was wrong. | More specifically, the problem is not with the larger code image produced by SK compilation (because memory size is typically not a problem these days), but rather that the granularity of the instructions is too fine. Supercombinators have much coarser granularity, and get more work done per `instruction'. This is reminicent of the RISC vs. CISC arguments that are raging over in comp.arch. I think Mark is making a case that with a high enough instruction bandwidth and more intelligent code generation/optimization, SK reduction performance could approach current supercombinator reduction performance. I doubt it, especially with SK, but you might with a larger set of fixed combinators, such as Turner's expanded set. I think you will also need hardware support to really approach/improve on supercombinator performance. Some fixed combinator machines have been built, but I haven't heard of any that are close performance-wise to the current breed of supercombinator implementations. In short, a number of people have looked into this already, and most are opting in favor of supercombinators. With the performance of general-purpose architectures climbing steadily, the trend seems to be moving away from building special purpose machines. For the forseeable future, fixed combinator implementations will be slower, given the advanced state of supercombinator compilation techniques. -- Eric ------ jeschke@iuvax.cs.indiana.edu ...{pyramid, rutgers}!iuvax!jeschke ------
markv@uoregon.uoregon.edu (Mark VandeWettering) (11/17/88)
In article <8811161428.AA13775@toucan.LCS.MIT.EDU> bard@THEORY.LCS.MIT.EDU writes: > >> >> Mark VandeWettering writes: >> >> I think (and my thesis work is evolving into this kind of >> argument) that Y is overlooked for trivial reasons. Partial >> evaluation and smarter code generation could make an SK based >> compiler generate code which is equal in quality to that produced >> by supercombinator based compilation. >I thought that the reason for using supercombinators rather than S and K is >space. Ordinary \-calculus expressions can be translated into SK-combinatory >expressions, but the combinatory version is exponentially longer than the SK >term. Some sets of supercombinators give polynomial-length expansions; I >think some give linear expansions. This is true for the trivial compilation algorithm described in Turner's original paper. Typically with better compilation and the addition of several "longer reach" combinators, expansions can typically be O(nlogn) or less. I should point out that I do not intend to use SK combinators as the final "primitives" in the SK machine. I believe that SK combinators form a good basis for performing partial evaluation. Hence, the compilation algorithm I am currently deriving is as follows: SASL-like functional language | V Enriched Lambda Calculus | V SK combinators | (by Partial Evaluation) V Stack Machine Code (similar to the G-machine) I have found the work of Wand, Friedman, Haines and Kohlbecker to be interesting, in that they transform an interpreter for Scheme into a compiler. I have applied much of the same methodology within the framework of a graph reduction engine, and find very interesting results. > Now, code size isn't usually much of a problem, in that we don't >usually care whether a program is 50K or 250K. The difference between 50K >and 2^50K is significant. I don't know if the translation has a decent >expected case or not. Recent evidence has shown that it does have "decent" performance. > In any event, the SK compiler has a lot of work to do before it can match >even a fairly stupid supercombinator compiler, simply because it can be >forced to produce incredibly long code. My guess, and I gather the guess of >many people who actually work on this, is that SK would lose. I would be >very interested in some proof that this guess was wrong. I question whether "longer code" is indeed the bugaboo here. We are basically talking about a logn performance difference here. Imagine that our implementation of supercombinators actually required the implementation of a primitive that didn't have a bounded execution time. Most of the time, we are indeed concerned with TIME of execution rather than space. I wonder (and don't really believe) if the way that other supercombinator methods don't achieve shorter code is by making more complex primitives. It was an idea, not a particularly good one. I am very impressed with the G machine, and find myself playing "catch up" to make SK combinators have similar performance. Why? Well, its the stuff that theses are made of..... >-- Bard Bloom Mark VandeWettering
markv@uoregon.uoregon.edu (Mark VandeWettering) (11/17/88)
In article <15089@iuvax.cs.indiana.edu> jeschke@iuvax.UUCP (Eric Jeschke) writes: > More specifically, the problem is not with the larger code image >produced by SK compilation (because memory size is typically not a >problem these days), but rather that the granularity of the >instructions is too fine. Supercombinators have much coarser >granularity, and get more work done per `instruction'. Perhaps I haven't been entirely clear: I am NOT using SK combinators as the final code in the target machine. Just as supercombinators have an efficient implementation in the G-machine, I believe that SK combinators have an efficient implementation in a similar stack based machine. Why use SK combinators? Because they provide a convenient formalism for reasoning about optimizations, strictness and partial evaluation. >This is reminicent of the RISC vs. CISC arguments that are raging over >in comp.arch. I think Mark is making a case that with a high enough >instruction bandwidth and more intelligent code >generation/optimization, SK reduction performance could approach >current supercombinator reduction performance. I see the problem of implementing an SK machine as twofold, the instructions themselves are reasonably "highlevel", but do relatively little relative to the source language. For instance, a numerically intensive program spends most of its time copying argument pointers into the right place on the heap for execution. I believe that by partially evaluating SK expressions, and studying the actions that are performed in an INTERPRETER, we eliminate most of the silly and redundant copying of pointers and heap allocation that plague SK implementations. >I doubt it, especially with SK, but you might with a larger set of >fixed combinators, such as Turner's expanded set. I think you will >also need hardware support to really approach/improve on >supercombinator performance. Some fixed combinator machines have been >built, but I haven't heard of any that are close performance-wise to >the current breed of supercombinator implementations. I should be more clear, when I say SK combinators, I mean the expanded set. > In short, a number of people have looked into this already, and most >are opting in favor of supercombinators. With the performance of >general-purpose architectures climbing steadily, the trend seems to be >moving away from building special purpose machines. For the >forseeable future, fixed combinator implementations will be slower, >given the advanced state of supercombinator compilation techniques. I agree in part, smart compilation will beat special hardware MOST of the time. But I don't believe that the state of the art in compiler technology has been applied to compiling combinators. Also, the target of my compilation is NOT to a fixed set of combinators. >Eric ------ > jeschke@iuvax.cs.indiana.edu ...{pyramid, rutgers}!iuvax!jeschke >------ Mark VandeWettering