[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