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)