[plt-scheme] PLT Mzlib: Libraries Manual 24.3 Examples Y operatorill defined

----- Original Message ----- 
From: "Kyle Smith" <airfoil at bellsouth.net>
To: <plt-scheme at list.cs.brown.edu>
Sent: Tuesday, October 24, 2006 5:38 PM
Subject: [plt-scheme] PLT Mzlib: Libraries Manual 24.3 Examples Y operatorill defined


> Hi,
> 
> I don't claim to be an expert at these things, but after a little 
> research I'm fairly certain that Y?, as defined in 24.3 of the PLT 
                                                                                ~~

First of all, the Y? is defined in Chapter 25.3. It rather takes me some
time to find that out, just because you type in the wrong number.


> Mzlib: Libraries Manual, is not an appropriate predicate for the Y operator.

Second, the document says, the Y? "recognizes some ***s-expressions*** that represent the standard Y operator".

 
> A Y operator should  satisfy the condition Y F = F Y F, while a Fixed 
> Point function will not, but will still give you a recursive function 
> back from a nameless lambda form that is essentially the rule that the 
> function is defined by.  The  classic example is the factorial function. 
> Where the rule can be stated as:.
> 
> (define nextfact (lambda (f x) (if (<= x 1) 1 (* x (f (- x 1))))))
> 
> A function satisfying  the Y?  predicate  of  24.3  can be  constructed  as:
> 
> (define Y*
>  (lambda (f)
>    (lambda (z)
>      (((lambda (x) (f (lambda (y) ((x x) y))))
>        (lambda (x) (f (lambda (y) ((x x) y)))))z))))
> 
> Where (Y?  Y*)  =>  #t


If you define Y* like this, (Y?  Y*)  =>  #f.
> However,  when  you  then  construct  the  function fact  as  in:
> 
> (define nextfact (lambda (f x) (if (<= x 1) 1 (* x (f (- x 1))))))


The example is to demonstrate pattern matching, not about what Y should be. But any way, nextfact should be defined as:

(define nextfact (lambda (f) (lambda (x) (if (zero? x) 1 (* x (f (sub1 x)))))))

In pure lambda calculus, a function can only take one argument.

(define fact ((eval Y*) nextfact))

(fact 7) => 5040


Chongkai