# Ruby Conf 12 – Y Not- Adventures in Functional Programming by Jim Weirich  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   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  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  