[plt-scheme] Re: Applicative-order Y Combinator

What you have seen is a scheme representation of the Y combinator.

In English - Y is a function which given a function returns a
recursive version of that function. To understand why you need it,
it's a good idea to learn a bit of lambda calculus - I suggest the 2nd
book below.

In the lambda calculus all functions are anonymous. So the question is
how do you make a recursive call in a language that has only anonymous
functions - think about it - usually you give a function a name and
then use that name to call it within itself, but an anonymous function
has no name.

Read Simon Peyton Jones - Implementation of Functional Programming
Languages which I believe is available on line. Very succinct
explanation IIRC somewhere in Chapter 2.

Alternatively try Greg Michaelsons Introduction to Functional
Programming through the Lambda Calculus if you can get it (Chapter
4).

The latter book I recommend to all FP fledglings

On May 23, 7:11 pm, Lightstar <laalaalov... at yahoo.com> wrote:
> How does this function work? (below)
> I think that it is recursion but I have never seen anything use itself as a parameter before... ( (lambda (f) (f f)) ) could you explain this to me please?
>
> (define Y
>   (lambda (le)
>     ((lambda (f) (f f))
>      (lambda (f)
>        (le (lambda (x) ((f f) x)))))))
> _________________________________________________
>   For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme