[plt-scheme] Applicative-order Y Combinator

On May 23, 2009, at 4:46 PM, John Clements wrote:

> I also highly recommend the forthcoming "Semantics Engineering with  
> PLT Redex":
>
> http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=11885
>
> Its motivation for Y is one of the tidiest and most legible I've seen.

Thanks. A true collaboration.

> Nicer (imho) than "The Why of Y".
>
> Tangentially related: the "Why of Y" that I've seen is from Richard  
> Gabriel; perhaps you're referring to the development of Y in the  
> little/seasoned schemer? Or perhaps I'm confused.


Dick wrote up something about the Y combinator, too. The essay I  
wrote originated with a make-up session for 311, one late evening in  
Houston. As I was going to Rice to deliver some lecture on languages,  
I changed my mind and decided to speak about the Y combinator. I  
started with "As you know, I am the one who brought Scheme 84 to  
Rice, and this afternoon I broke it. DEFINE no longer introduces  
recursive functions. So on the way over I decided to figure out  
whether this really decreases the power of Scheme, because we still  
have LAMBDA left." For the first ten mins or so, the kids really  
believed it. Then they realized I was gently directing the questions  
in a certain way. The next day I wrote it all up with the TLL Q&A  
style -- I believe as (Y Y) but it got transformed -- and later that  
year I started showing it to people:

   http://www.ccs.neu.edu/home/matthias/misc.html

I believe Dick's essay is independent and appeared even a bit earlier  
than mine.

Now in contrast to the usual __declarative explanations__ (here is  
the definition, here is how it works) my lecture is a __derivation__  
from first principles. In particular, the self-application is not an  
ex deus machina appearance but is inspired by reasoning that we wish  
to achieve a certain goal. What I failed to write up is the natural  
transition into the fixed point functional, which also is explicable  
with (Y Y) .. Next life.

-- Matthias