[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