Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!ames!nrl-cmf!mailrus!cornell!uw-beaver!uoregon!markv
From: markv@uoregon.uoregon.edu (Mark VandeWettering)
Newsgroups: comp.lang.scheme
Subject: Re: Limitation with lambda
Keywords: lambda
Message-ID: <2992@uoregon.uoregon.edu>
Date: 19 Oct 88 16:46:05 GMT
References: <15590@agate.BERKELEY.EDU> <4557@polya.Stanford.EDU>
Reply-To: markv@drizzle.UUCP (Mark VandeWettering)
Organization: University of Oregon, Computer Science, Eugene OR
Lines: 101

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.

	Oh contraire!  There is the most amazing goodie in the world,
	the Y combinator to save the day...

	The Y combinator is defined so that when applied to a function,
	it returns an infinite series of applications:

	Y H = H (Y H) = H (H (Y H)) = H (H (H (Y H))) = H (H (H ...

	How do we make use of this?  Well, quite simply.  Take our 
	definition of factorial?

	(define factorial
		(lambda (n)
			(if (= n 1)
			    1
			    (* n (factorial (- n 1))))))

	We can "abstract" out the inner call to factorial by making it
	a parameter, call the result H:

	H = (lambda (factorial n)
		(if (= n 1)
		    1
		    (* n (factorial (- n 1)))))
	
	and then apply Y to it to get our the definition....

	FACTORIAL = (Y H)

	We can illustrate this by applying it to an arg, say 3:

	Y H 3
	-> H (Y H) 3
	-> (if (= 3 1) 1 (* 3 ((Y H) (- 3 1))))
	-> (* 3 (Y H 2))
	-> (* 3 (H (Y H) 2))
	-> (* 3 (if (= 2 1) 1 (* 2 ((Y H) (- 2 1)))))
	-> (* 3 (* 2 ((Y H) 1)))
	-> (* 3 (* 2 (if (= 1 1) 1) (* 1 ((Y H) 0))))
	-> (* 3 (* 2 1))
	-> 6

	and we are done!  Two important things to note,

	1.	Y can be written as a lambda itself!
		Y = (lambda (h) (lambda (x) (h (x x)))
				(lambda (x) (h (x x))))
		Try applying it to an arg, and see...

	2.  	Evaluation of Y will not terminate under
		an applicative order evaluator (such as those 
		used in Lisp or Scheme.  Functions must evaluate their
		args first, which results in an infinite stream
		of computation.  This isn't a problem for functionally
		pure languages, which can use normal order evaluation.


Abelson and Sussman's SICP does mention this in passing, on pg. 488.
They have to be careful that too much doesn't get evaluated, but the 
idea is the same.

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

	One element of my master's thesis work is to decide if the Y 
	combinator is indeed as inefficient as people seem to imagine.
	Nevertheless, the Y combinator has been around for a LONG time,
	probably to Alonzo Church in the 40's.   

	McCarthy has admitted that his knowledge of the lambda calculus
	was admittedly limited.  Such things as dynamic scoping were 
	less than totally thought through.  

	For an excellent intro the lambda calculus, and functional
	programming in general, try Simon Peyton Jones' book, the
	Implementation of Functional Programming Languages.  Excellent.

>Joe Weening                                Computer Science Dept.
>weening@Gang-of-Four.Stanford.EDU          Stanford University