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

From: Chongkai Zhu (czhu at cs.utah.edu)
Date: Tue Oct 24 22:32:49 EDT 2006

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


Posted on the users mailing list.