[FoRK] Re: Combinator Correction!

Dave Long < dave.long at bluewin.ch > on > Sat Sep 16 03:41:10 PDT 2006

> Quadratic is still not "exponential".

Right, but (if the kragen-hacks post* is what we're discussing) when  
one uses nodes to share subgraphs, that's performing graph reduction  
instead of string reduction.

The original claim was exponential, in the absence of naming or  
sharing.  This is a more explicit statement; is it accurate?

names/lambda --n^x--> shared nodes/G-machine --x^n--> strings/SK

-Dave

:: :: ::

* "SK-combinators in JavaScript"
http://lists.canonical.org/pipermail/kragen-hacks/2006-September/ 
000435.html


More information about the FoRK mailing list