(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)

Didn't understand a thing but it was entertaining.

Great talk, interesting and fun ðŸ™‚

Simply brilliant!

è·ªäº†

I think I understand Lambda Calculus now. I think.

This is an excellent talk!

I have a question: How is Jim evaluating the code in his Emacs' buffer?

RIP

28:56 "Mention from Brandon – I can smell the brains being [cooked?]"

Damn this guy is good.

RIP, Jim Weirich.

Mind blown posthumously by Jim. Â I will have to re-watch many times. Â RIP.

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.

My mind just died. 120 times.

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.

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) {…}).

Mind blown from beyond the grave. RIP Jim.

Amazing talk. Really helped me understand lambda calculus.

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.

there is no alpha reduction, only alpha conversion. 9:20

"wrap function" is eta expansion. 24:30

Anyone knows what font did he have set up here? I really like it.

Worth it

Syntax is kind of weird.

i dont get it, but i get how he got it, with is about as close to getting it as im going to get

Absolutely amazing presentation and charisma ðŸ™‚ Thank you

Alan Turing was the founder of Turing police.

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

RIP, watch again