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