[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