# 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