From: Jim Weirich <jweirich@...>
Date: 2004-01-23T17:00:03+09:00
Subject: Y-Combinator (was: how to broadcast UDP packets)

Florian Frank wrote:
> On Fri, 2004-01-23 at 00:37, Hal Fulton wrote:
> 
>>Would you explain your .sig? It makes my brain itch. :)
> 
> 
> Not only your brain! ;)
> 
> It's the (applicate order) Y-Combinator that's used to implement
> recursion in lambda calculus. It has the property Y(f) = f(Y(f)),
> that means that it returns the fixed point of the given function
> f.

I was skimming through the threads in the mail list.  Imagine my 
surprise to find a discussion of the dreaded applicative order Y 
combinator in a thread titled "how to broadcast UDP packets".  Cool.

I played around with the Y combinator some years ago, and traces of that 
conversation still remain on some mailing list archives.  It started 
when someone posted a a version of the Y combinator in Perl (shudder). 
I responded with a version in Java (double shudder).  The java version 
didn't fit so nicely in one line however.

If you are interested in the java version you can find it here: 
http://www.clug.org//ml/archive/programming/1998-11/msg00014.html
But watch out, it is more likely to make your brain explode than itch.

I even wrote out a commented derivation of the Y-combinator.  I swear I 
understand each individual step of the derivation, but fitting the 
entire thing in my head at once is difficult.  The derivation in here: 
http://www.clug.org//ml/archive/programming/1998-11/msg00028.html

-- 
-- Jim Weirich       jweirich@one.net      http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)