Path: utzoo!attcan!uunet!mcvax!enea!kth!draken!chalmers!cs.chalmers.se!augustss
From: augustss@cs.chalmers.se (Lennart Augustsson)
Newsgroups: comp.lang.scheme
Subject: Re: Limitation with lambda
Keywords: lambda
Message-ID: <2769@fnatte.cs.chalmers.se>
Date: 20 Oct 88 20:24:11 GMT
References: <15590@agate.BERKELEY.EDU> <4557@polya.Stanford.EDU>
Organization: Dept. of CS, Chalmers, Sweden
Lines: 27

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