# [plt-scheme] PLT Mzlib: Libraries Manual 24.3 Examples Y operator ill defined

 From: Kyle Smith (airfoil at bellsouth.net) Date: Tue Oct 24 19:38:17 EDT 2006 Previous message: [plt-scheme] A 15-minute Scheme search engine with Google Co-op Next message: [plt-scheme] PLT Mzlib: Libraries Manual 24.3 Examples Y operatorill defined Messages sorted by: [date] [thread] [subject] [author]

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

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 )

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

```

 Posted on the users mailing list. Previous message: [plt-scheme] A 15-minute Scheme search engine with Google Co-op Next message: [plt-scheme] PLT Mzlib: Libraries Manual 24.3 Examples Y operatorill defined Messages sorted by: [date] [thread] [subject] [author]