Ruby Conf 12 – Y Not- Adventures in Functional Programming by Jim Weirich

Ruby Conf 12 – Y Not- Adventures in Functional Programming by Jim Weirich

(energetic music) Jim: Good morning. You excited
to be here for RubyConf? (cheers) Excellent, excellent.
I’m glad to be here too. We’re going to be talking about
the y combinator this morning. How many people here are very
familiar with the y combinator? Just a very few people, very good. That means I can say
anything I want to about it. I’ve got extensive speaking
experience, and I’ve learned a couple rules, particularly
about keynote talks. Keynotes are just a little bit different than your regular, everyday session. For one thing, keynotes tend
to be a little less technical. You want to inspire the
folks that are attending, you want to motivate them, so you tend to stay away from
the highly technical talks. I am glad to say this talk
will be highly technical. If you’re going to be really
technical then maybe you should at least make what
you’re talking about relevant to the day-to-day life of
the programmers, so they can take home something that
they can use in their work. You may use it tomorrow. I am glad to say that this
talk is extremely pointless. There’s very little in this
that you can take home and use. If you’re not going to be relevant, and you’re going to be highly technical, then at least if you’re
doing code examples, make it examples of good
code, good coding practices, so you’re instilling those
good practices in the people, so that when they get home at least they got something out of that. I am also happy to say this will be the worst Ruby code you’ve probably ever seen. So what are the redeeming
factors of this talk? Well all I can say, it’s going
to be a little bit of fun. (applause) The first thing I need
to do is I’m going to need a little bit of
audience participation. I need someone who has
a calculator that can calculate the cosine
of an angle in radians. Do I have any people who might
have a calculator to do that? Anybody, any volunteers here? Way in the back there, yes, yes! You got a calculator in there?
Go ahead and pull it out. Oh good, he’s coming up
here. Excellent, excellent. I want you to type in the number zero. Make sure you are in
radians mode for cosine. Then hit the cosine button. You got an answer? Audience Member: I do.
Jim: Okay, hit the cosine button again. Hit it again. Hit it again. Keep doing that until I get back to you. (laughter) The topic of my talk is
called effectively computable, that’s what we’re going
to be talking about. This was a topic that was explored by a fellow named Alan Turing. You may have heard of Turing, he invented something
called a Turing machine. A Turing machine is a simple machine that has an infinite tape with cells on it. Those cells, you could write
characters into those cells, and you can then read back the cell, you can erase the cell and
write a new character into it, and you can move the tape
one position at a time. All those functions are
controlled by a very, very, very simple-minded program that
sits and can say if the current cell is a one then shift left
and go to this, you know. Very simple-minded programming. In fact, here is an animation
of a turing machine. I so want one of these devices. If you’re watching here, there
is a camera here with a light, and you can see it’s reading
these characters right there. It’s reading the one,
it’s reading that one. There’s an eraser head over
here, that he can erase that one and then write
a zero in place of it. This is a counter. He initialized
it with the number 11. Now we’re up to 12. Now we’re up to 13. It’s a very simple program
that just reads the character under the
camera and decides whether to change it to a one
or a zero, and carries the one over, and it’s
doing binary counting. We are up to, that looks like 14 now. Now we’re up to 15. Now we’re carrying the one all the way up. Erases the one. And now it’s running
real-time. It was actually running in fast speed before.
This is real-time now. Sees a zero, reads a zero. Reads a one, erases it. Writes in the zero, it’s
going to carry the one. It reads over until it finds a blank space and then it carries the one over to the blank
space, and the program’s done. That is a Turing machine. (applause) Can somebody build me one
of those? That’s awesome. Turing said that anything
that is effectively computable can be computed by this really dirt-simple machine, this Turing machine. What he meant by anything
that can be computed, he’s generally talking about mathematical functions or logic
problems, things like that. Anything that you can
write an algorithm to do, you can write that algorithm
in a Turing machine and have your Turing
machine calculate it out. That’s kind of mind-boggling.
And look at the date on this. This is in the 1936, 1937 time frame. The very first programmable computer was probably invented in
Germany in around 1936. So he’s doing all this
research in his head, on paper. There’s no computers that he’s using to do any of this stuff with at all. This is actually pre-computer
work that’s being done. Around the same time frame there’s this fellow named Alonzo Church. Church designed something
called lambda calculus, you might have heard of that. Lambda calculus is a way
of calculating things. It consists of the lambda character here, which introduces a function. After the lambda character will become a variable name, here x. After the x is a dot that separates the variable name from the
body of the function. In this case the body of
the function is another x. This is, in essence,
the identity function. You pass this function in any value and it will return that very same value. This is a very, very, very simple
function in lambda calculus. This is all there is to lambda calculus. There are no strings,
there are no integers, there are no floating point
numbers in lambda calculus. There are only functions and
the calling of those functions. So how do we represent
interesting things in it? Here’s one particular scheme you might use to represent some numbers. Let’s look at the number one over there. You see it’s a lambda function
that takes an argument f and it returns a lambda function
that takes an argument x. In essence you can think
of this, in my mind I group this together as a single
function taking two arguments. It takes the function f and applies it, it calls it, given the value x. It calls the function f
passing in an x one time. That represents the number one. The number two is represented
by a two argument function that takes the function f and
a value x, and it calls the function f twice on the function
f, so that represents a two. Zero calls the function f
zero times on the value, and this is how we represent numbers. We can represent any
number you want to just by applying the function f
multiple times to that value. This is called a Church numeral. This is how you represent
numbers in lambda calculus. How might you represent true and false? At the bottom of the screen you can see true is a function of two variables. True returns the first variable. False is also a function of two variables and returns the second argument to that. True is kind of like an if-then-else, it returns the then part, and the false is an if-then-else that
returns the false part. That’s how you represent true
and false in lambda calculus. Keys to lambda calculus are that functions are the only data type. No integers, no strings,
no floating point, no arrays, nothing else but functions. Lambda binding is the only way you can associate a value with a variable name. You do lambda binding by
calling the function on a value, and that will bind the
value to the variable, the argument in the
function, and then you expand the body of the function
using that substitution. All calculation in lambda calculus happens by a process called beta reduction. There’s also another process
called alpha reduction, but the important one
is the beta reduction. Let’s give you an example
of beta reduction. Here we have the lambda
calculus representations of true and it’s being called on
the number one, and then the result of that is being
passed in the number zero, and we’re passing in the
lambda calculus versions. To do a beta reduction you
take the function in question. You identify the variable x, and you expand the body of the function out. Then you replace anywhere in
the body where there is an x, the variable, you replace
that with the argument. The argument one gets
substituted in for the x, and this is the final result
of that beta expansion. Let’s do one more beta expansion, expanding the result of
this with the argument zero. We identify the argument
of the function is y. We expand the body of
the function out and we brought it down below,
that’s the red circle there. Then we substitute in zero for
the value y in the body, and happens to be no value y in the
body so we’re done, that’s it. If you pass true a one and a zero, it’s going to return a
one. That makes sense. True is a function that
returns the first argument. That’s beta reduction in lambda
calculus, and you can see that lambda calculus is nothing
more than macro expansion. It’s merely text substitution
that you take the arguments and you substitute
them in and expand them out. This is really, really
simple macro expansion here. Church said, “Anything that
can be effectively computable “can be computed via lambda calculus.” I hope you’re scratching your
head here because as I just said, lambda calculus is nothing more
than simple macro expansion. But Church actually made his thesis, he beat Turing to the punch,
he said this around 1933, 1935, he wrote a couple papers on this topic, so he beat Turing by a couple years. In fact when Turing’s paper came out, and Turing said a Turing
machine can calculate anything that’s effectively
computable, there was a long debate in the
mathematical circles whether the two sets of things that
were effectively computable were actually the same thing or not. Generally today we agree
that lambda calculus and Turing machines, and then
there was a third thing called general recursion
that was also done. All of those things are Turing complete. In other words they can all
calculate everything that can be calculated, can be calculated
in any of those three systems, lambda calculus, general
recursion or Turing machines. We see the influences of
lambda calculus today. If you look at our language
Lisp has lambdas all over it. Clojure has an fn anonymous function that is essentially a lambda. In Ruby we like lambdas so much we have several ways of doing them. CoffeeScript has a very concise
way of representing lambdas, and Javascript itself has lambdas as well. Anonymous functions are nothing
more than lambdas or closures. If you went to Pat’s talk yesterday on block you learned what a closure was. This is all these things
are, closures or lambdas. Let’s put that aside and remember
that even though it seems hard for us to believe, lambda
calculus is Turing complete. There’s a problem with
that that we’ll get to in a little bit but first I
want to return to the topic. Where’s my volunteer? What number did you get after pressing cosine many, many times? Audience: 0.739085 Jim: Very good. Thank you, thank you very much, I really appreciate that. (applause) Turns out, if you take the
cosine of zero that’s a one. If you take the cosine of one
that is about .54 blah blah blah. If you keep doing that over
and over again, and if you do that about 89 or 90
times, depends on how precise your floating point math
is, you’ll start zeroing in on a number that is
.7390851 blah blah blah blah. This is a fixpoint of cosine. That means if I give that
.73 number to the cosine function in radians it
will return that exact same number, and we
have converged on this. A fixpoint is nothing more than a value you give to a function
and if that functions returns the same value
then that is a fixpoint. It turns out lots of
functions have fixpoints. Here’s the formal definition of
fixpoint so you could see it. Give x to a function, it returns x, x will be a fixpoint of that function. For cosine, cosine is a fun
fixpoint because you get to zero in on it just by hitting
that cosine button a lot. Other functions have actually
much simpler fixpoints. For example, sine has a fixpoint of zero. Cosine of zero is zero. Square root it turns out
it has two fixpoints. Square root of zero is
zero and the square root of one is one, so both zero and one will be fixpoints of the function square root. If you had an identity
function, any value you gave to an identity
function would be a fixpoint for the identity function, so there’s an infinite number of
fixpoints for that function. And there’s certainly some functions that have no fixpoints at all. Keep the idea of a fixpoint in your head, we’re going to return to that. We’re going to switch now to the live coding part of the demonstration. I’m going to, you guys are familiar with the stabby procs is Ruby 1.9, right? You call them by saying dot parentheses, that’s at least one way to call them. I’m going to put this into
my codebase right here so I can just type in something
and the last thing in this list of expressions
when I evaluate the buffer will just return the last
thing in that expression. That’s just going to
be a convenient way for me to evaluate a buffer
and print things out. Let’s talk about the problem
with lambda calculus. I’m going to demonstrate it by
writing a factorial function. We’ll use the stabby proc notation. Factorial is a function of
what argument, if that argument is zero then the result of
factorial of zero should be one. If it’s not zero the
result of factorial should be n times the factorial of n minus one. I can prove that works by
calling factorial on five, and we know the factorial of five is 120. And indeed, that’s what we get. But in lambda calculus I’m not really allowed to assign things like this. I have to create a lambda expression
and then call it directly. I’m going to try to call my
factorial problem like this, and it says, oh, I don’t
have a method called fact defined anywhere, and that’s
because I’m using fact in the definition of the
function I’m defining. Well in lambda calculus all
functions are anonymous, so how in the world can
I define that factorial without referring to
itself? That’s a problem. How can lambda calculus
possibly be Turing complete? I’m going to leave that comment up there, and just think about that for a while. There’s about four topics,
three or four topics I want to cover first before we go
back and solve this problem. The first thing we’ve already talked about, the first thing is fixpoints. You guys know what a fixpoint is, it’s a value when given to a function, the function returns
that same value again. The next thing I want to talk
about it higher order functions. How many people here are familiar
with higher order functions? Yeah, I suspect most of us are. The rest of us who are
not, probably use them all the time and don’t
really realize that. In Ruby, each, in its own sense,
is a higher order function. Let’s talk about regular functions first. I’m going to write a
function called add one that takes a number and adds one to it. I can demonstrate that
add one works by giving it 10 and I should get an 11 out of that. Add one is a very simple function. Let’s do another simple
function, just for demo purposes. It’s going to be multiply by three, we’ll take n and multiply it by three. We’ll multiply by three
the result of adding one to ten and we should
get 33 out of that. Add one and mul three are
both basic simple functions, they take a value, they return a value. Let’s write a higher order function now. Make adder is a function
that takes an argument x, and what it’s going to return
is another function that takes an argument n, that
adds x and n together. Make adder is a function
that creates a new function. Given the x it will take that x and it will create a new function that will add x to anything that you give to the new x. So I could actually have
rewritten add one like this. Make adder one. And that’s a decent definition of add one. We can evaluate our
buffer and see we get the 33 back, so add one
obviously must be working. Make adder is a higher
order function, it’s higher order because its return
value is a function itself. That’s all it means to be a higher order function, it returns functional values. Here’s another higher order
function, we’ll call it compose. Compose takes functions as argument, two functions in this case, f and g. It’s also going to return
a function that’s going to compose f on top of g called
on n, and return a new function that calls f and
g on top of each other. We can now create a function
called mul three add one that is the composition
of mul three and add one. Then we can use that newly
composed method right here and we see we get
the same answer 33 back. Compose is a higher order function. It’s higher order for two reasons. It returns a function, but it also takes functions as arguments,
and that’s enough to make it a higher order function as well. We are going to use higher
order functions a lot in the rest of this demo, so if
you’ve never seen them before just get comfortable with
the fact that functions are values and we can manipulate
them just like we can manipulates strings and
integers and what not. Next topic will be
functional refactorings. Just like in the object-oriented world, there are refactorings that we can do, like extract method or collapse hierarchy. There are a number of
refactorings that you can do in the functional world as well, and they are purely functional in flavor. The first one I want to talk about is the Tennent correspondence principle. Tennent says if I have an
expression x and I surround it by a lambda, and then immediately
call that lambda, I get x back. It essentially has no effect. It’s a true refactoring, in that
it does not affect the code. Let’s demonstrate that. Let’s go down here to mul
three and inside mul three … Inside mul three I’m going to wrap this expression inside a lambda,
and then immediately call the lambda, that’s
the Tennent principle. And we see that it has
no effect on the outcome, we still get 33, it is a true refactoring. Let’s do it one more time. I’m going to wrap this whole functional expression in a Tennent lambda. And this time I’m going to
do it with an editor macro just to show that these
things truly are mechanical. There, my editor did it for me,
and yes, we get 33 out of it. The Tennent principle, very
useful in functional refactoring. Our next refactoring would
be to introduce a binding. If I have a lambda here with no arguments, I can add a new argument binding to it. We’ll call it z. If I add an argument here,
when I call it I have to give it a value, and I can give it
any value that I feel like. Because z is not used anywhere
it doesn’t matter what value it takes, so I can
introduce the argument z and evaluate that and
it’s still 33, no effect. Now there’s one rule you have to follow, and let’s demonstrate that here. You have to make sure that anything, any variable you add
in, that you introduce, is not free in the
expression you’re wrapping. Down in here we’ve got variable n. n is not free because
it’s bound right here. I could actually reuse n. It
would be confusing but I could. But f and g are both free variables in this expression, they’re defined outside. So if I were to take f in here and give it an arbitrary value, it would die. Whereas if I called it n, that would work. Generally I’m going to avoid
using any used variable at all, so xyzzy is a good choice
there, and that works. As long as you stay
away from free variables in the expression you’re wrapping it doesn’t matter what the variable name is. Number three will be wrap function. If I have an expression
that is a function of one argument, I can wrap
that in a lambda of one argument and then call
the function inside that lambda and pass the argument
down to the call site. Let’s demonstrate. Here is
a function of one argument. I can wrap it in a brand new
lambda with an argument of v. Then on the inner function
that I just wrapped I need to call it
immediately and pass v in. This essentially, what I’m
doing is make adder now returns a lambda that has the same
signature as the function it was previously returning,
but it doesn’t actually evaluate the lambda on the
inside until you call it again. It’s kind of like a delaying tactic. If you don’t want to evaluate
something right away, this is something you can do to do that. And you can tell, I still
get 33 out of the result, so function wrapping
is a true refactoring. One final one, you’re
going to love this one. This is inline definition. I can take any definition here,
in this case the definition of make adder, and wherever
make adder is called by name I can replace the name of make
adder with the definition. Let’s delete this line here. And when I evaluate that, same result. Again this is totally mechanical. I can take compose and run the
inline refactoring on that. I get the same result back. Let’s go wild with this one. Inline add one, no that’s part of the name, but here’s add one, yes. Let’s inline mul three, there. (laughter) One more time guys. Let’s inline this guy. I did promise you the worst
ruby code you’d ever see, right? (laughter) That mess, let’s evaluate
it, still returns 33. (applause) The really interesting thing about this, this is a pure lambda expression. There are no assignments anywhere in this. The only binding that
we do to variable names is through calling these lambda functions, we do a lot of calling
of the lambda functions. That’s really ugly and very unreadable, and I don’t recommend
writing code like this, but it proves a very important principle, that lambda calculus, this
is the goal of what we want to get to in lambda
calculus is have one big lambda expression that
does this calculation. Okay, enough of the preliminaries. Seems a shame to write all that
and just delete it, doesn’t it. Let’s get back to the
problem of recursion. Let me grab my factorial thing and let’s paste it back here, and uncomment. So this is what we’re dealing with. I want to write a factorial
function that’s recursive, and I can’t because I
cannot refer to factorial inside the definition of factorial, because there are no
names for these functions. Well I could actually, there
are names that are introduced by lambda binding, so I
actually could do this. Let’s create a function that
has factorial as an argument. And then, now factorial
will be bound to this. Let’s call this make factorial. Then all I have to do
to create the factorial function is to call make
factorial, and all I need to do is pass in the
definition of factorial. Think about that for just a sec. Okay, I haven’t solved the problem yet, I’ve just introduced
some indirection there. That’s not going to work because to make a factorial I need the
definition of factorial. Little bit circular logic there,
I need to do something else. Maybe I can relax the
requirements a little bit. Maybe I don’t need a
make factorial, maybe I need a function that is
a factorial improver. Instead of taking the definition
of factorial as an argument, it will take a partial definition
of factorial as an argument. And by partial I mean a
function that acts like factorial over a subset
of the possible inputs. In other words, if I have a
factorial function that works from zero to 10, it calculates
the factorial of zero, one, two, three, on up
to the factorial of 10. If I pass that partial
definition of factorial into my fact improver, I will get
out of that a new function that works for factorial from zero to 11, it improves any factorial
definition by one step. That’s kind of cool. I need an error function here, so bare with my while I write this. This is just a function
of one argument that throws an error so we
can see what’s happening. Now if I factorial improve,
factorial improver, and I call that on error,
I claim that I will get out of this a
function I’ll call f zero, because f0 correctly calculates
the factorial of zero. Oops. I left this five on there, that
five should not be in there. Yes, it correctly calculates
the factorial of zero. That’s interesting. Oh, but if I can calculate
the factorial of zero, I can create a function that
calculates the factorial of one. Yeah, but f one does not
calculate the factorial of two. But if I got one that
calculates one, I can write an f two based on
f one that works for two. Does it work for three? No, not at all. You can kind of see where
I’m going with this maybe. Before I go any further let’s
inline some of these things. I’m going to do the inline
refactoring there and there. Let’s call this fx right now,
not tied to a particular number. And then I’m going to take
this from here to here. I’m going to cut it and paste it one, two, three, four, five times. One, two, three, four, five
to balance the parentheses. And now fx calculates
the factorial of five. It will do 10, it will do
14, but it will not do 15. Well, I’m getting closer to my goal. (laughter) All I have to do is decide the biggest number I will ever want the factorial of (laughter) and call fact improver
on it that many times. Okay, maybe that’s not
quite so practical, that’s not going to get us the
real factorial function. Let’s get rid of that.
Let’s think about this. Before I go any farther let’s go ahead and do the whole embed this in a lambda trick. I’m going to create a lambda function that expects a factorial
improver as an argument, and here’s the body of that function. Should be open parentheses
and close parentheses. Here is the body of the function. Here is where I’m passing in the argument, I’m passing in the factorial improver. Let’s just call it improver for right now. Then in here I can do the same
tricks I was doing elsewhere. I can say improver dot error,
and if I put this into fx and fx should work for one,
but it won’t work for two. This is exactly the
same thing I did before, except I’ve embedded it in a lambda. Instead of assigning to
improver I’m binding to it with lambda binding, which is what
we want to get to anyways. Improver is interesting.
Improver says I can take any function and
improve it by one step. I was using this error
thing, which obviously has nothing to do with factorial at all. But I’m wondering if I replaced
error with just improver, I should get a function that
works for factorial of zero. And it does. But if I call factorial
of one it should fail in a weird way, and the
weird way is that it says that proc can’t
be coerced to a fixnum. The error happens right here on this line, right at this multiply, where
it’s taking n times that. This partial now is the
improver function and improvers expect functions, not numbers,
so of course it’s not working. In fact we can make this much plainer if I replace the word partial
with improver here. Since I’m passing in improver to improver, and this is improver, so
let’s call it improver as the argument, I’m actually doing that. And this becomes very plain
that improver does not take a numeric argument,
improver expects a function. Well, I’ve got a function laying around. Let’s pass an improver. (laughter) Gosh, I wonder if this
could possibly work. Well factorial of one is good. How about factorial of
two? Oh, how about five. How about 50? How about 500? I think I can go up to 2000
before I overflow my stack. So there, factorial of 2000. Here you go. Let’s make
this all the way pure lambda calculus by defining the
function and then calling it with the argument five at
the end here, and we will have a pure lambda expression
that calculates factorial. (applause) Now this is good enough for our goal of proving that lambda calculus can actually calculate arbitrary
mathematical functions. Recursion is no problem
for it by doing this little trick of passing these
things to itself, it actually can do recursion with
lambda calculus, even though lambda calculus is nothing
but anonymous functions. This is mind blowing to me actually. But I’m still not quite happy
with this definition here. There’s two things I don’t like about it. First of all, I’m calling
this thing improver and it’s no longer improver, improver
took a partial definition. This function is taking
something that is not a partial definition, so this thing
here should not be called improver at all, it should
be called something else. So let’s replace the name
improver with a different name, and here I get stuck,
because I have no common name for the thing that
this argument now is. It’s no longer an improver function. I’m going to go with the name gen, because it’s a generator that
somehow when you feed it itself, when it swallows itself, it
generates a recursive function. If we can live with that,
that’s what I’m going to call it for the purposes
of this demonstration. I can see that I haven’t changed anything, we still have a working
factorial system there. That’s the number one thing I didn’t like. The second thing is that
if I were to sit down and write a recursive function
it would never in my entire life occur to me to
write it in this manner. There’s lots of mechanics right here involved in just to do the recursion. If I could get this in a form where I was writing factorial as an improver function, improver function makes
a lot of sense to me, that seems more or less natural, at least in the lambda calculus world. If I could get back to
the improver form of this I would be really glad,
so let’s see if we can work on this code base a little bit. I’m going to take this inner
lambda right here and I’m going to do the Tennent correspondence
principle refactoring on it. Let’s break that up
just a little bit here. I wrapped this in a lambda
and immediately called the lambda and it has no effect,
it does the same thing. We still have a working factorial,
it didn’t break anything. Now I’m going to introduce a binding, and the variable name
I’m going to use is code, that’s the name of the variable, and the value I’m going to pass
in will be my error function. Remember when you introduce a
variable, introduce a binding, the value doesn’t matter,
it can be anything. There I have a function that
takes an argument of code, and I’m passing in the error function. We’re not using code anywhere
so we never trigger the error, and it still results 120
for the factorial five. Well I can pass anything
in, let’s pass in gen. Hey, that still works too. This whole gen of gen thing is a
function, let’s call gen of gen. Oops. Stack too deep. This is what has happened. I’m calling gen of gen inside
of here, so this entire thing, this entire thing right
here is the gen function, so when I call gen and pass in gen, it goes and it would call
gen of gen inside of it, but it only called it if n was not zero, so it actually bottomed out,
it would actually terminate. Here I’m passing in gen
or gen and it always calls gen of gen, even when n is
zero, so it has infinite recursive depth in there,
and that’s no good. If there were only some
way of delaying evaluation. Let’s wrap it in a function. There’s my wrap function.
Argument name will be v. There I’ve taken gen of gen
and replaced it with a lambda so when I call it it
doesn’t infinitely recurse, it just passes the
lambda in in it’s place, that’s functionally equivalent
to calling gen of gen. And we see, this actually works. Okay, next step. I’ve got code, code is
bound to that lambda that evaluates to gen of gen,
and we know that here, let’s go ahead and wrap this as well. I see right here, from
here to here, this is the exact same thing that I’m passing in to code so let’s just call code instead. And that works. That’s interesting. Let’s rename code to partial. All of a sudden, out of nowhere, that little piece of
code right there is our improver function,
we’ve got it back. Cool. But it’s still buried in
the middle of all this recursive stuff, let’s
see if we can pull it out. Out here, from here down to
here, not including the argument call but the entire body of
the function, I’m going to do a Tennent refactoring again,
that wraps it in a lambda. Let’s put some line feeds in and pretty up the indentation a little bit there. I’m going to introduce a
new binding here again. The binding will be code, the
value will be error again, because that worked so
well for us last time. And that still works, that’s still 120. Now I’m going to point out
that here is the improver. I’m going to copy the
improver from here and call, pass in the improver as the value of code. And that still works because
we’re not using code. But I point out that code
is now the same thing as the improver function embedded in here. I can replace this now with
code and it still is 120. Now let’s rename code to be improver. I was practicing this this
morning and I was typing improver so often all of a sudden I
started reading it as imp rover. Replace those two with improver and we still got 120 out of that. And there we have, we have a
complete lambda expression. Here, this part of the
code right here deals with the recursive nature of the problem. This piece right here
is the only piece that knows anything about the
definition of factorial. So this is really nice,
this is exactly what I want, and now that I’ve got a
complete lambda expression that does this I’m going
to pull the pieces out and name them so we can talk
about them reasonably. Let’s pull this out, I’m going to call this fact improver again, imp rover. And let’s put it up here.
Fact improver is that. Nice indentation. Still works, no problem. Let’s take out this piece right here. I’m going to call this piece y. Get some nice indentation going on that. Then I’m going to take this out here and I’m going to call this
piece fact, or factorial. Then we’ll call factorial right
there, everything still works. I’m going to clean this code base up just a little bit here,
streamline it just a wee bit. Now I’ve got three pieces. Let’s start with the
bottom and work our way up. This is factorial, this is
the real factorial function and I prove it by calling
factorial five and it actually does calculate
the factorial of five. If I were to take the factorial function and run it through the fact improver what will come out of that? Well fact improver takes a partial function and improves it by one step. But if I’ve already got the
real factorial function, all improver can do is return
the factorial function. This is indeed the factorial function. I can run this and I still get 120. We’re using this definition of
factorial now, not this one, and that proves that fact
improver returns its argument. Factorial is the fixpoint
of fact improver. I’m going to say imp rover now
in my head every time I do that. Factorial is the fixpoint
of fact improver. Higher order functions
have fixpoints as well. Their fixpoints happen
to be functions, but that doesn’t change the fact
that they’re fixpoints. Now I’d like to point
out that the function y calculates the fixpoint
of an improver function. In this case we’re calculating
the fixpoint of the fact improver, but I could write
any recursive function I wanted to and it would calculate the
fixpoint of that recursive function, as long as it’s
done in an improver style. I could write a Fibonacci improver and it would work perfectly well. y calculates that, so let’s talk about y. y here is actually the y combinator that we’ve all heard about and loved. Well, maybe not loved. In particular this, there’s actually many, many, many versions of the
y combinator, and if you go to Wikipedia you will
not see this version at all. First of all, mathematicians don’t
like intention-revealing names. (laughter) So they call improver f, and
they call the generator function, I’ve seen it called g,
I’ve also seen it called x. The Wikipedia article uses
x so we’ll use that here. So this is probably more likely
the form of the y combinator you’ll see with variable names
f and x in it, but we haven’t changed anything, we’re
still calculating factorial. The other issue here is this in particular is the applicative order y combinator. Ruby is an applicative language. In other words it evaluates
its arguments before it passes the arguments
down into functions. Ruby is applicative,
Python is applicative, Lisp and Clojure are all
applicative languages. Examples of language that are
not applicative would be Haskell. Haskell is lazy, it will
evaluate its arguments only at the point it really needs them. There’s a version of the y
combinator for normal order languages like Haskell, and the
difference is that you don’t have to introduce this wrap
function thing right here that we had to do to prevent
our infinite stack recursion. That would be the normal
order y combinator. When you talk about y
combinators normally they mean the normal order in
the mathematical sense. In a language like Ruby we need to use the applicative order version instead. The applicative order has another name, it’s called the z combinator. Why these things have so
many names I have no idea. It’s also known as the
fixpoint combinator, because it is the combinator that calculates fixpoints of functions. There you have it. Oh, oh, one more thing. If you go to the Wikipedia page you will not find it in exactly this format, there’s a preferred style
they like to write it. I’ll show you that through
two refactorings here. Remember f is really the name
of the improver function, so if I call f on this x of x thing, I’m just improving the factorial function, and that is a no-op in this term. This still returns 120, no change. Then I can also do a function wrap here. We know function wrap
doesn’t change anything, and you can see it doesn’t. Then if I take off two
levels of indentation, all of a sudden you see a
great symmetry between the body of the function and the
argument you’re passing in. This is the version you will
probably see if you look it up in Wikipedia or some math
on computational science. There you have it, there
is the y combinator derived from [first] principles. (applause) Wow, my brain is dead after that one. I started on this journey because I always heard about the y
combinator, and I really, really, really wanted to understand it. Now people ask, “Oh, that’s cool! “How can I use the y
combinator in my own code?” Well if you have named functions, you don’t need the y combinator. If you want to write all your
code as anonymous functions, then maybe the y
combinator would be useful, but I don’t really recommend that. What I found interesting
though is by starting with some very basic principles and
applying these refactorings, I found the functional refactorings
to be very fascinating. By applying that you can
take something in one shape and transform it and get
it into a different shape that’s more appropriate for
the needs that you have. I really enjoyed playing around with those refactorings in that exercise. Now you can go home and you can explain to all your coworkers that you’ve seen the y combinator, you
understand how it’s done. I think the y combinator is one of those examples of great beauty in mathematics. It’s a really interesting function that is theoretical in a lot of
respects, but comes out of something like lambda
calculus which seems a trivial macro replacement
type of language, but yet lambda calculus is
buried so deep into Ruby, we use it all the time
without even realizing it. It’s one of those things that
have a great and profound impact. That’s one of the the things
I really enjoyed researching this particular topic, and I
hope you guys enjoyed it as well. If you liked this, I’m going
to recommend a talk called Programming with Nothing by Tom Stuart. Tom uses nothing but
lambdas, the stabby procs, and calling thereof, and writes
the fizzbuzz application. He uses no integers, no strings, no logic, anything except calling lambda functions. It’s a true example of
lambda calculus done in Ruby. Just Google programming with nothing and you’ll turn up that video.
I recommend that one. Thank you very much, you
guys have a good day. (applause) (energetic music)

27 thoughts to “Ruby Conf 12 – Y Not- Adventures in Functional Programming by Jim Weirich”

  1. One of Jim's finest talks. It will be remembered as a timeless expression of the love of programming he embodied. People will be watching this talk for many many years. We will miss you.

  2. The subtitles are wrong at 48 minute – he surely doesn't mean Pascal, he means Haskell programming language. Pascal not being applicative made me laugh 😀
    Otherwise, great talk.

  3. Very interesting. The explanation at 34:34 is wrong: It fails at the multiplication ("in `*'") because the right hand side must be a number, but improver (called on anything) returns a function (of the form -> (n) {…}).

  4. This is amazing is so many ways that I can't even begin to write them down. Thank you so much for posting and /kneel to Jim Weirich, you will be missed.

  5. 7:30 — starts explaining Lambda Calculus
    12:40 — does this mean JS got arrow functions thanks to Ruby?
    21:30 — starts about the "functional refactoring"
    36:02 — done with implementing the factorial in lambda calculus
    43:45 — splits out the Y-combinator from it

Leave a Reply

Your email address will not be published. Required fields are marked *