[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Limitation with lambda

In article <4557@polya.Stanford.EDU> weening@Gang-of-Four.Stanford.EDU (Joe Weening) writes:
>In article <15590@agate.BERKELEY.EDU>, 128a-3aj@e260-3b (Jonathan Dubman) writes:
>>There seems to be a gross omission in the lambda primitive.  It seems like
>>there is no way to create a recursive function on the fly!  I'm reading
>>the Abelson and Sussman book but they seem to avoid this issue.
... [ Talk about LABEL ] ...
>I don't know if it was known in 1963, but LABEL or its equivalent is
>not actually necessary in order to define recursive functions.  The
>trick is to use the Y combinator.  In practice, though, this method
>would be fairly inefficient.

It was certainly known in 1963, the question is who knew it.  The fact that
Y can be defined in terms of (nonrecursive) functions was discovered in the
30s (I think) by Haskell B. Curry.  He didn't die until the -83 (or so) so
at least he knew, and assuming that people read his books others knew as well.
The problem is that probably very few computer scientist knew about it (well,
it's not really a problem since this definition(s) of Y is of theoretical
interest only).


	Lennart Augustsson
Email:	augustss@cs.chalmers.se or augustss@chalmers.csnet