[plt-scheme] Re: PLT Mzlib: Libraries Manual 24.3 Examples Y operatorill defined
Chongkai Zhu <czhu at ...> writes:
> 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.
My appologies.
> Second, the document says, the Y? "recognizes some ***s-expressions*** that
represent the standard Y operator".
I agree.
>The example is to demonstrate pattern matching, not about what Y should be.
>But any way, nextfact should be
See below.
> (define nextfact (lambda (f) (lambda (x) (if (zero? x) 1 (* x (f (sub1
x)))))))
I agree.
> In pure lambda calculus, a function can only take one argument.
> Chongkai
Thanks for you comments Chongkai,
Like I said I'm really not an expert at lambda calculus. In fact, the only
reason I caught the inconsistency in definitions was when I did some web
research to find out what the Y operator was in the first place. What I found
out was that there were many different forms floating around, including airity
two forms.
(define Y2
(lambda (f)
((lambda (x) (f (lambda(z1 z2) ((x x) z1 z2))))
(lambda (x) (f (lambda(z1 z2) ((x x) z1 z2)))))))
(define (y-iter-fact n)
((Y2 (lambda (iter)
(lambda (n result)
(if (<= n 0)
result
(iter (- n 1) (* n result))))))
n 1))
(check (y-iter-fact 5) => 120)
I found this site to be particularly helpful:
http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html. A this site I they
define the form that most of the examples I was finding were similar to. They
called the applicative-order Y-combinator:
(define Y
(lambda (X)
((lambda (procedure)
(X (lambda (arg) ((procedure procedure) arg))))
(lambda (procedure)
(X (lambda (arg) ((procedure procedure) arg)))))))
Now, this form looks very similar to that listed in 25.3 (sorry about the typo
BTW.) It's possible that this is the form the author meant to use. At any
rate, all the forms I found had one thing in common, they were able to take a
function of the form you correctly expressed for factorial:
(define fact (lambda (n) (if (zero? n) 1 (* n (fact (- n 1))))))
and by applying their version of Y to it come back with a factorial function
that actually worked. This is not the case with the functions of the class
described by the predicate Y? in 25.3.
And the only version of the Y operator that I could find that satisfied the Y
F = F Y F requirement was the one I presented, although as you point out, it
is an airity two function.
So, my purpose in the post was just that we have, in 25.3, a predicate for a
class of functions that wouldn't lead to the same confusion I had to deal
with. As I said, my purpose in being in that section was indeed pattern
matching, but to understand the pattern being represented, at least for
myself, I needed to know what class of function was being represented. In
doing so, I was surprised to find it did not seem to work as advertised.
Thanks for your reply,
--kyle
Kyle Smith
airfoil at bellsouth.net