bard@THEORY.LCS.MIT.EDU (11/22/88)
> Worst-case lambda-expressions for this > translation have deeply nested subexpressions and functions of many arguments > - the nesting has to be proportional to the size of the program to get > the quadratic effects, e.g. (backslash = lambda): > > \x1.\x2.\x3.\x4.\x5.(x5 ((x2 (x1 x4)) x3)) > > Does this ever happen? In more theoretical settings, at least, LET x=m IN n is identical to (\x.n)m. If the typical program structure is LISP-like, it is a long sequence of short function declarations followed by a body: LET x1 = m1 IN LET x2 = m2 IN ... LET xk = mk IN n which is indeed a deeply nested term, although not quite of the form above. All this proves is that you should do something in a way other than the theoretician's straightforward translation of LET. What methods are actually used? > > 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. > > Is this a particular SK compiler you're talking about? Has someone actually > implemented the naive translation into just S and K? I'm not surprised it's > no good. The naive one. As I said before, I'm a theoretician (interested in denotational semantics of lambda calculus) and woefully ignorant about compiler technology. -- Bard Bloom
Krulwich-Bruce@cs.yale.edu (Bruce Krulwich) (11/22/88)
In article <8811212337.AA01324@toucan.LCS.MIT.EDU>, bard@THEORY writes: >If the typical program structure is LISP-like, it is a long sequence of short >function declarations followed by a body: > LET x1 = m1 IN > LET x2 = m2 IN > ... > LET xk = mk IN > n >which is indeed a deeply nested term, although not quite of the form above. > >All this proves is that you should do something in a way other than the >theoretician's straightforward translation of LET. Not necessarily. A better solution (if it works) is working on optimizing nested terms. This will help efficiency in the general case, not just in the case of LET. (This is the T/Orbit approach.) Bruce Krulwich