Combinator Correction! (was Re: [FoRK] The World's Smallest
Programming Language)
Kragen Javier Sitaker <
kragen at pobox.com
> on >
Thu Sep 14 11:57:14 PDT 2006
I went back and read the relevant chapter of Peyton Jones' book.
I got B and C backwards in my Tuesday post: B is 'compose', and C is
\f g x.f x g. Also there's a quadratic growth in the combinator graph
(N^2 combinators for N levels of lambda nesting) for naive rewriting,
even including B and C, although there are other combinators (S', B*,
and C') that you can use in your compiler to cut down on this problem.
Finally, I think the quadratic growth becomes linear growth with S',
B*, and C'.
Quadratic is still not "exponential".
Last night I implemented an SK-combinator-graph-reduction machine in
JavaScript, and it was indeed pretty easy, especially compared to
other alternative ways of doing fully-lazy graph reduction. I
probably should have spent the last couple of hours working on a
lambda-to-combinator compiler instead of hand-debugging simple
programs I'd hand-translated into combinator graphs.
More information about the FoRK
mailing list