TITLE: StrangeLoop 6: Y Y
AUTHOR: Eugene Wallingford
DATE: September 29, 2012 3:40 PM
DESC:
-----
BODY:
I don't know if it was coincidence or by design of the conference
organizers, but Wednesday morning was a topical repeat of Tuesday
morning for me: two highly engaging talks on functional programming.
I had originally intended to write them up in a single entry, but
that write-up grew so long that I decided to give them their own
entries.
Y Not?
Watching talks and reading papers about the Y combinator are
something of a spectator
code kata
for me. I love to see new treatments, and enjoy seeing even
standard treatments every now and then. Jim Weirich presented it
at StrangeLoop with a twist I hadn't seen before.
Weirich opened, as speakers often do, with him. This is a
motivational talk, so it should be...
- non-technical. But it's not. It is highly technical.
- relevant. But it's not. It is extremely pointless.
- good code. But it's not. It shows the worst Clojure
code ever.
But it will be, he promises, fun!
Before diving in, he had one more joke, or at least the first half
of one. He asked for audience participation, then asked his
volunteer to calculate cos(n) for some value of n I
missed. Then he asked the person to keep hitting the cosine
button repeatedly until he told him to stop.
At the dawn of computing, to different approaches were taken in an
effort to answer the question, What is effectively computable?
Alan Turing devised what we now call
a universal Turing machine
to embody the idea. Weirich showed
a video demonstration
of a physical Turing machine to give his audience a sense of what a
TM is like.
(If you'd like to read more about Turing and the implication of his
universal machine, check out
this reflection
I wrote earlier this year after a visit by Doug Hofstadter to my
campus. Let's just say that the universal TM means more than just
an answer to what functions are effectively computable.)
A bit ahead of Turing, Alonzo Church devised an answer to the same
question in the form of
the lambda calculus,
a formal logical system. As with the universal TM, the lambda
calculus can be used to compute everything, for a particular value
of eveything. These days, nearly every programming language has
lambdas of some form
... now came the second half of the joke running in the background.
Weirich asked his audience collaborator what was in his calculator's
display. The assistant called out some number, 0.7... Then
Weirich showed his next slide -- the same number, taken out many
more digits. How was he able to do this? There is a number
n such that cos(n) = n. By repeatedly
pressing his cosine button, Weirich's assistant eventually reached
it. That number n is called
the fixed point
of the cosine function. Other functions have fixed points to, and
they can be a source of great fun.
Then Weirich opened up his letter and wrote some code from the
ground up to teach some important concepts of functional programming,
using the innocuous function 3(n+1). With this short demo,
Weirich demonstrated the idea of a higher-order function, including
function factories, a set of useful functional refactorings that
included
- Introduce Binding
-- where the new binding is unused in the body
- Inline Definition
-- where a call to a function is replaced by the function
body, suitably parameterized
- Wrap Function
-- where an expression is replaced by a function call that
computes the expression
- Tennent Correspondence Principle
-- where an expression is turned into
a think
At the end of his exercise, Weirich had created a big function call
that contained no named function definitions yet computed the same
answer.
He asks the crowd for applause, then demurs. This is 80-year-old
technology. Now you know, he says, what a "chief scientist" at
New Context
does. (Looks a lot like what an academic might do...)
Weirich began a second coding exercise, the point behind all his
exposition to this point: He wrote the factorial function, and
began to factor and refactor it just as he had the simpler
3(n+1). But now inlining the function breaks the code!
There is a recursive call, and the name is now out of scope.
What to do?
He refactors, and refactors some more, until the body of factorial
is an argument to a big melange of lambdas and applications
of lambdas. The result is a function that computes the
fixed point of any function passed it.
That is Y. The Y combinator.
Weirich talked a bit about Y and related ideas, and why it matters.
He closed with a quote from Wittgenstein, from Philosophical
Investigations:
The aspects of things that are most important for us are hidden
because of their simplicity and familiarity. (One is unable to
notice something -- because it is always before one's eyes.)
The real foundations of his enquiry do not strike a man at all.
Unless that fact has at some time struck him. -- And this means:
we fail to be struck by what, once seen, is most striking and
most powerful.
The thing that sets Weirich's presentation of Y apart from the many
others I've seen is its explicit use of refactoring to derive Y.
He created Y from a sequence of working pieces of code, each the
result of a refactoring we can all understand. I love to do this
sort of thing when teaching programming ideas, and I was pleased
to see it used to such good effect on such a challenging idea.
The title of this talk -- Y Not? -- plays on Y's interrogative
homonym.
Another classic in this genre
echos the homonym in its title, then goes on to explain Y in four
pages of English and Scheme. I suggest that you study
@rpg's
essay while waiting for Weirich's talk to hit InfoQ. Then watch
Weirich's talk. You'll like it.
-----