Re: Y, again (long)

[polya!max@labrea.stanford.edu (Max Hailperin)]

I think I may have just been tarred as a philospher or as pedantic --
ouch!  So let me try to clarify what I see to be some of the more
substantive issues:

1) I didn't mean to imply that Rozas's compiler actually has a Y
   recognizer; my point was merely that it wasn't surprising that it
   could do those things a Y recognizer could.  The question is, how
   does it hold up in more difficult cases?  One case I'd very much
   like Rozas to compare the generated code for is Y itself, *not
   applied to anything*.  E.g., how similar/different is the code for
   these two procedures:
     (define (Y1 f)
       (let ((g (lambda (g)
                  (f (lambda (x) ((g g) x))))))
         (g g)))

     (define (Y2 f)
       (letrec ((y-of-f (f (lambda (x) (y-of-f x)))))
         y-of-f))

2) I wasn't weighing the possibility of a compiler defining letrec in
   terms of Y, I was weighing the possibility of the language standard
   defining letrec in terms of Y.  While users of Rozas's compiler
   would notice no difference if he were to do so, users of other less
   optimizing compilers would notice a difference, namely in
   "self"-eqvness.  The issue isn't excess eqvnes, either, as Rozas
   seems to think, but rather insufficient eqvness.  As long as scheme
   supports procedural objects with identities, letrec will have to
   remain defined in terms of set! rather than Y.