[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Limitation with lambda
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.
This problem actually has quite an interesting history. From the Lisp
1.5 Programmer's Manual (J. McCarthy et al, 1963), p. 8:
"The lambda notation alone is inadequate for naming recursive
functions. Not only must the variables be bound, but the name of
the function must be bound, since it is used inside an expresion
to stand for the entire expression. ... In order to be able to
write expressions that bear their own name, we introduce the LABEL
LABEL only defines a single function in terms of itself. Scheme's
LETREC and Common Lisp's LABELS extend this to allow mutually
recursive function definitions.
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.
Joe Weening Computer Science Dept.
weening@Gang-of-Four.Stanford.EDU Stanford University
- Limitation with lambda
- From: firstname.lastname@example.org (Jonathan Dubman)