Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!bloom-beacon!bu-cs!purdue!decwrl!labrea!polya!weening@Gang-of-Four.Stanford.EDU
From: weening@Gang-of-Four.Stanford.EDU (Joe Weening)
Newsgroups: comp.lang.scheme
Subject: Re: Limitation with lambda
Keywords: lambda
Message-ID: <4557@polya.Stanford.EDU>
Date: 19 Oct 88 02:31:35 GMT
References: <15590@agate.BERKELEY.EDU>
Sender: news@polya.Stanford.EDU
Reply-To: weening@Gang-of-Four.Stanford.EDU (Joe Weening)
Organization: Stanford University
Lines: 27
In-reply-to: 128a-3aj@e260-3b.berkeley.edu (Jonathan Dubman)

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
    notation."

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