Tuesday, April 29, 2014
'Y' is for Y-Combinator
Y = λ f → f (Y f)
Wow. The thing about the Y-combinator, also called the fixpoint function, is that it's a big mess, type-wise, because sometimes you'll get no value out of it (as it does not terminate for many cases of functions) or sometimes you'll get multiple values out of it.
But what is it supposed to do? It's supposed to find the 'fixed' point of a function, the point of the function where it is 'fixed,' or comes to rest.
This is usually the case of a function with multiple cases, a case 'at rest' and an inductive case, like our good old friend, factorial:
factorial x = if (x = 0) then 1 else x * factorial (x -1)
for any natural number x.
The fixed point of this factorial function is one:
factorial x (where x = 1) = x
If you put this into the Y-combinator, you get:
Y factorial = factorial (Y factorial)
and when apply the natural number 1 you get
Y factorial 1 = factorial (Y factorial) 1
which comes to rest at 1 = 1
for any other number, this doesn't come to rest.
So, the Y-combinator is a very simple thing to define (as you saw above) and there's nothing in that definition about recursion (explicitly), but in computer science the Y-combinator is often used to model and to study recursion because of both its restful and (infinitely) inductive properties.
Okay, that's Y-combinator, the combinator from combinatory logic.
So, there's another Y-Combinator, and that's the name of a startup company headed up by Paul Graham (the Paul Graham, who wrote On Lisp). I had the pleasure of meeting Paul at the Little Languages conferences at MIT back in 2008/2009 time-frame. He had just started Y-Combinator after selling Yahoo!-store to Yahoo! for 40 million dollars.
Nice, personable guy.
At that same conference I met Joe Armstrong, the Joe Armstrong, who invented Erlang (another name from mathematics, c.f. Markov chains and Queuing theory used telephony) after having sold his Erlang company for 40 million dollars.
Nice, soft-spoken guy. Some pretty 'weird' ideas about Concurrent-oriented programming ('weird' is a direct quote from wikipedia when describing the properties of the Y-combinator).
What do these guys have in common ... besides working really hard on something everybody else told them didn't work and would never work. That, and 40 million dollars, each.
I mean, Paul Graham wrote web services (before 'web services' existed as a term) in Lisp, of all things. He was afraid to tell others about using Lisp, for if they found out, they'd start to copy him and program in Lisp, too.
Nobody programs in Lisp, by the way. Just stupid students going to comp.lang.lisp asking "How do I reverse a list in Lisp? Please answer right away; homework due tomorrow morning."
Paul was worried somebody would find out, until his partner, Robert Morris, laughed at him: "Nobody cares! Everybody's programming in Java and has an Oracle back-end. They're following 'best practices;' they'd never use Lisp. That's why they're going to fail, and why we're going to succeed!"
Paul chilled after that pep-talk.
And Joe Armstrong? Ericsson told him: write us a concurrent language.
So he did.
It didn't look like Java, and it was untyped (just like Paul Graham's Lisp), so Ericsson fired him (actually, they didn't fire him, they just mandated that Erlang was not to be used at all in Ericsson anymore, so he left. Yeah. They fired him). He asked if he could keep Erlang. They said. "Erlang? Whatever. Sure. Take it and go."
He took it and went.
Erlang supports 60,000 concurrent nodes, at the same time. Joe showed it by connecting to his Erlang web server.
Netscape webserver crashed after 1,000 connections. It's a Unix thing. So, you know, Java ...? Same problems.
Joe showed his stuff around. Somebody bit. Cell phones? You need to support a lot of concurrency. A lot. He made a lot of money until Ericsson bought him back. Seems they needed his technology, after all.
What's weird about these guys?
Paul Graham's Y-combinator has started up scribd, Dropbox, and reddit.
His startups, in total, are valued at over $13.7 billion dollars. The startups had their original ideas and did all the work, all Paul Graham, and his family and partners did was open the door, give them a tiny little bit of money, and listen to them.
Joe. All he did was go against convention of 'everything has to be typed' and 'shared memory' and what threads are, and he kept at it until he got something working and he made it work with stunning results. And still he was rejected.
These are two men who believed in what they were doing, regardless of what everybody else was telling them was so, and they kept at it through success and disappointment.
And they are both generous with their time and are soft-spoken. Yes, they believe what they believe, and stand up for it, but they don't start confrontations, they don't even finish them. They just walk away and get to work, and make it work.
I see it all the time. That is: very rarely. This one guy, Brian Kernighan, at work, he wasn't given resources and told the acquisition process would take forever, or long after the due delivery date for the project.
So he bought dedicated hardware, set up a web server, and ran the application from his house.
This was for a big, big, really big cable company. Really big.
He was a water-walker. Why? Because he did what he needed to do, regardless of what everybody told him what couldn't be done.
You. Me. Every day we're told 'no' or 'later' or 'that can't be done' or 'you can't do it.'
You. Me. Everybody. We can choose to listen to what we're told, and to believe it, or we can go ahead and do what we see needs to be done, but nobody's doing it, because everybody says it can't be done.
The Y-combinator as a mathematical function that does what math functions aren't suppose to do: it doesn't give an answer, or it can give multiple answers. A function just returns one answer, that's all. The Y-combinator doesn't. And it's modeled within mathematics using straight-up math.
It can't be done. But it's doing it.
You. You're told every day, 'it can't be done.' You can listen, and be like everybody else.
Or you can do it. And be what nobody else can be: you.
'Y' is for Y-combinator. 'Y' is for you.