Combinator Correction! (was Re: [FoRK] The World's Smallest Programming Language)

Kragen Javier Sitaker < kragen at > 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