[plt-scheme] PLT Mzlib: Libraries Manual 24.3 Examples Y operator ill 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 
Mzlib: Libraries Manual, is not an appropriate predicate for the 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

However,  when  you  then  construct  the  function fact  as  in:

(define nextfact (lambda (f x) (if (<= x 1) 1 (* x (f (- x 1))))))
(define fact (Y* nextfact))
(check (fact* 7) => 5040 ) => procedure nextfact: expects 2 arguments, 
given 1: #<procedure>

you receive these unsatisfying  results.

May I propose an alternate predicate Y??:

(define Y??
  (match-lambda
    [('lambda (f1)
       (('lambda (y1)
          ('lambda (x1) (f2 ('lambda (z1) ((x2 x3) z2))x4)))
        (lambda (y2) ('lambda (a1) (f3 ('lambda (b1) ((a2 a3) b2))a4)))))
     (and (symbol? f1) (symbol? y1) (symbol? y2) (symbol? x1) (symbol? 
z1) (symbol? a1) (symbol? b1)
          (eq? f1 f2) (eq? f1 f3) (eq? y1 y2)
          (eq? x1 x4) (eq? x2 x3) (eq? z1 z2)(eq? y1 x2)
          (eq? a1 a4) (eq? a2 a3) (eq? b1 b2)(eq? y1 a2))]
    [_ #f]))

 From which one can construct a function Y:

(define (Y f) ((lambda (x)
                 (lambda (z) (f (lambda (y)
                                  ((x x) y))
                                z)))
               (lambda (x)
                 (lambda (z) (f (lambda (y)
                                  ((x x) y))
                                z)))))

For which (Y?? Y) => #t, and further:

(define nextfact (lambda (f x) (if (<= x 1) 1 (* x (f (- x 1))))))
(define fact (Y nextfact))
(check (fact 7) => 5040 )
(check (nextfact fact 7) => 5040 )

work as advertised.

And, thus you have Y F = F Y F as stated above.

I would welcome comments and further testing by others.  I have run 
these examples on DrScheme v352.6

--kyle

Kyle Smith
airfoil at bellsouth.net