[plt-scheme] Applicative-order Y Combinator

Consider the term (λ (m) ((λ (f) (m (f f))) (λ (f) (m (f f))))). We shall abbreviate it as ‘Y’. Let ‹term› be an arbitrary lambda 
term without free occurrences of m and n. If it has, we can α-convert Y such that it does not contain any variable occurring free in 
‹term›. Now:

1       (Y ‹term›) =                                                                           Write Y in full.

2     ((λ (m) ((λ (f) (m (f f))) (λ (f) (m (f f))))) ‹term›) =                    Substitute ‹term› for m.

3     ((λ (f) (‹term› (f f))) (λ (f) (‹term› (f f)))) =                            Substitute (λ (f) (‹term› (f f))) for f.

4     (‹term› ((λ (f) (‹term› (f f))) (λ (f) (‹term› (f f))))) =                Because line 3 = line 2.

5     (‹term› ((λ (m) ((λ (f) (m (f f))) (λ (f) (m (f f))))) ‹term›)) =        Because line 2 = line 1.

6     (‹term› (Y ‹term›))

For this reason Y is called a fixed point combinator. A combinator is a lambda term without free variables. Indeed, Y has no free 
variables. Given a ‹term›0, Y produces a ‹term›1 ≡ (Y ‹term›0) such that (‹term›0 ‹term›1) = ‹term›1. ‹term›1 is called a fixed 
point of ‹term›0. In general: if f(x)=x, then x is called a fixed point of f. Now:

7     (Y (λ (‹var›) ‹body›)) =

8     ((λ (‹var›) ‹body›) (Y (λ (‹var›) ‹body›))) =

9     ‹body› in which (Y (λ (‹var›) ‹body›)) is substituted for ‹var› =

10   ‹body› in which ‹var› is replaced by a term equal to ‹body›: self-reference!

We can use this fact for the construction of lambda terms representing recursive functions:

11   (Y (λ (‹var›0) (λ (‹var›1) ‹body›))) =

12   (λ (‹var›1) ‹body›) in which ‹var›0 is bound to a term equal to (λ (‹var›1) ‹body›): recursion!

Hence in order to prepare a recursive function of the name ‹name›, formal argument ‹formal-argument› and body ‹body›, we write (Y (λ 
(‹name›) (λ (‹formal-argument›) ‹body›))). Y cannot be used in scheme. For example:

(((λ (m) ((λ (f) (m (f f))) (λ (f) (m (f f))))) (λ (!) (λ (n) (if (zero? n) 1 (* n (! (sub1 n))))))) 4)

as an attempt to compute the factorial of 4, does not work. Copy the above expression into DrScheme’s definition window and use 
Debug to see what happens. The reason that the above factorial function does not work is that Scheme evaluates in applicative order. 
Y is not suited for this strategy of reduction. Scheme is caught in an infinite recursion in the underlined subexpression. We must 
postpone the evaluation of (f f) within the underlined subexpression. This can be done as follows:

#lang scheme                                      ; File applicative-order-y-combinator.ss

(((λ (m) ((λ (f) (m (f f))) (λ (f) (m (λ (x) ((f f) x)))))) (λ (!) (λ (n) (if (zero? n) 1 (* n (! (sub1 n))))))) 4)

                                                                            → 24

We can call (λ (m) ((λ (f) (m (f f))) (λ (f) (m (λ (x) ((f f) x)))))) an applicative order Y combinator. Another, more symmetric 
form of this combinator is:

(λ (m)

 ( (λ (f) (m (λ (x) ((f f) x))))

  (λ (f) (m (λ (x) ((f f) x))))))

----- Original Message ----- 
From: "Lightstar" <laalaalovesu at yahoo.com>
To: <plt-scheme at list.cs.brown.edu>
Sent: Saturday, May 23, 2009 8:11 PM
Subject: [plt-scheme] Applicative-order Y Combinator


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