Why Functional Programming Matters

In this episode, I read excerpts from 'Why Functional Programming Matters' by John Hughes. Does it answer the question of what is functional programming and why is it powerful? Read the paper here.

Transcript

Our ability to decompose the problem into parts depends directly on our ability to glue solutions together. To support modular programming, a language must provide glue. Functional programming languages provide two new kinds of glue, higher order functions, and lazy evaluation. Using these glues one can modularize programs in new and useful ways. This explains why functional programs are so much smaller and easier to write than conventional ones. If any part of a program is messy or complicated, the programmer should attempt to modularize it and to generalize the parts. He or she should expect to use higher order functions and lazy evaluation as the tools for doing that. Hello. My name is Eric Normand and I help people thrive with functional programming. Today we're going to be reading from a classic paper called "Why Functional Programming Matters". By John Hughes, this paper was published, this edition was published in 1990, but it's actually a version of a memo that was circulating around Tallers University as far back as 1984. This is one of those nice, tight papers that had lots of revisions and got tighter and better and the argumentation better each time. I love those papers, it's just like a little nugget, very dense, it's like a diamond, it's compressed into its final form, but this version is from 1990. This was a different time in programming 30 years ago, it's 2020 as I record this. It's a much different time. This was a time in functional programming before the current boom that we've got. In fact, this might be the end of the AI winter of the 1980s. This paper is very influential and I like to talk about how every paper has a question that it's trying to answer. This one kind of asks it in the title "Why Functional Programming Matters". Really it's about how do we define functional programming in a way that explains why it could possibly be of use. Because if all we do is talk about what it doesn't have, so it doesn't have mutation, it doesn't have side effects, then how does that add power at all? This paper tries to explain why functional programming is a good thing in a positive way. It's 22 pages long, oh sorry, 23 if you count the acknowledgments and references. But it's got a lot of code, so there's a lot of white space. It's very tight, and I'm not going to read it all of course, but there are some good paragraphs in here that I'll get to. Let's get started. Functional programming is so-called because its fundamental operation is the application of functions to arguments. A main program itself is written as a function that receives the program's input as its argument and delivers the program's output as its result. Typically, the main function is defined in terms of other functions, which in turn are defined in terms of still more functions. Until at the bottom level, functions are language primitives. It's not a definition, but it's kind of explaining the name that functional programming is all about functions and how you use a main function, you divide a main function that's defined in terms of other functions until you get finally to the language primitives. Notice it says the main function receives the program's input as its argument and delivers the program's output as its result. So it is literally a function, like a mathematical function, and that's not the typical kind of programming we do today, but you could imagine if you wanted to calculate some mathematical formula or something where you could provide the parameters at the command line, and those are passed in as arguments, and then the result is then printed to standard out at the end. That's the kind of program we're talking about right here. More generally, functional programs contain no side effects at all. A function call can have no effect other than to compute its result. This eliminates a major source of bugs and also makes the order of execution irrelevant, since no side effect can change an expression's value. It could be evaluated at any time. This relieves the programmer of the burden of prescribing the flow of control. Okay, so again, functional programs contain no side effects at all. It's a very strong statement. It's not one that I tend to agree with, I think, that people who call themselves functional programmers do use side effects, and they do reason about side effects. What I do think is that this is a typical academic style definition that aims to push the envelope. It's asking a very constrained question, a very hard thing to do, which is, the question is, if we don't have side effects, what can we do? How can we make things work? What possibilities does that give us? This is something that you see a lot in academic circles, and unfortunately, most of the literature that we have in functional programming takes this point of view. Even though in industry, we don't quite do it that way. This is before Haskell, it's before Monads, that we're introduced in Haskell. Of course, Monads existed in math before that, but the idea of being able to make an inner active program, meaning, let's say you wanted to program a thermostat that was reading in sensor input. It was getting a thermometer reading and then deciding, "Oh, it's too cold, let me turn the air conditioner off," or "It's too hot, let me turn the air conditioner on." That is not possible with this setup, because it's just a function from inputs to outputs. It has no idea of time running or interaction with the environment, having some kind of effect on the environment, but that limited definition of a program with no side effects actually does give some benefits and we'll keep reading. He also says, "Programs are referentially transparent." That term is used a lot, but what it means is you can replace an expression by its eventual value, so you can replace 4 plus 2 with 6, and that doesn't have an effect on the result of the program. That you can imagine a really complex formula or calculation that got replaced at compile time with its value, or at any time in runtime, for example, because it's also, it doesn't, this lets you not worry about the flow of control. This is something that we talked about in "Out of the Tarpit," how one of the sources of complexity was having to deal with flow of control unnecessarily. The idea is if you have x equals a plus b, and then y equals c plus d, you are explicitly stating please calculate x first, and then calculate y first, whereas in a language like Miranda, which is what they use in this paper, or Haskell, the order doesn't matter. It's literally an equivalent program if you swap to x and y statements there, and we'll see why that's important in a second. Such a catalog of advantages is all very well, but one must not be surprised if outsiders don't take it too seriously. It says a lot about what functional programming isn't, but not much about what it is. The functional programmer sounds rather like a medieval monk, denying himself the pleasures of life and the hope that it will make him virtuous, by saying that when we make a definition that just says what functional programming doesn't have, it doesn't have side effects, it doesn't have assignment statements, it doesn't have mutable data. It just doesn't sound like it's better, it sounds worse. Functional programmers argue that there are great material benefits, that a functional programmer is an order of magnitude more productive than is his or her conventional counterpart, because functional programs are an order of magnitude shorter. Yeah, why should this be? The only fately plausible reason one can suggest on the basis of these advantages is that conventional programs consist of 90% assignment statements. This is plainly ridiculous, if omitting assignment statements brought such enormous benefits then Fortran programmers would have been doing it for 20 years. It is a logical impossibility to make a language more powerful by omitting features, no matter how bad they may be. So this is a really powerful statement he makes at the end, it is a logical impossibility to make a language more powerful by omitting features, no matter how bad they may be. So you could say that an imperative language is more powerful because you have everything you can do in the functional language, plus you can mutate the data, right? So it's strictly more powerful. There is more stuff you can do in it, an equivalent imperative language. So you took a functional language and you added mutable state, wow, your language is now more powerful, right? But there's something that we, as functional programmers, distrust about that. So he's going to try to explain why it is that we feel that functional languages give us some kind of power. One cannot write a program that is particularly lacking in assignment statements, or particularly referentially transparent. There is no yardstick of program quality here, and therefore no ideal to AMAT. Okay, this is, I'll try to explain what he's saying. He's saying it's also this idea of, you know, getting rid of assignment statements, getting rid of side effects is not something to AMAT, meaning if you got rid of a side effect or two, it's not going to make your program referentially transparent, right? It's not going to be given all these properties that we appreciate. I disagree with this. I think if you had a hundred assignment statements in your program and you refactored and, you know, changed variables to singles, static assignment and stuff, and you got it down to 50 assignments, you know, or like 100 mutable variables down to 50 mutable variables, that is an improvement, that it is a yardstick, that you can, you know, approach functional, like purely referentially transparent in that way. You might not ever get there, but all along the way you're gaining the advantages of it. So I disagree with that. I do know what he's trying to say, which is that, well, you can't do lazy evaluation if you have some assignment statement somewhere, like if it's not, if your code is in a hundred percent referentially transparent, there are some features of functional language that you can't do. And yes, that's true. But it doesn't mean that it's not better if you've made it, wrote a four train program without mutable variables. But you know, one of the cool things about reading papers is that you get to put yourself into a new mindset, a new perspective. So even though I disagree with some of these things, I'm not looking for, okay, I agree with that, I disagree with that, and just kind of cataloging what, you know, how close we are in our viewpoints. What I really try to do is, is identify my own beliefs and biases so that I can better put myself into, into the author's perspective that he's sharing, he or she is sharing in the paper, right? So that's what I'm trying to do by identifying, oh, I disagree with that, I agree with that. So that I can, I can say, oh, that's different from my thinking, so that's the place where I'm going to have to change, right? So I'm, as I'm going through this introduction, I'm like entering into this new mindset. And then you get to see the world from a new perspective. You can always come back if you need to. Okay, clearly this characterization of functional programming is inadequate. We must find something to put in its place, something that not only explains the power of functional programming, but also gives a clear indication of what the functional programmer should strive towards. Okay, so this is the end of the conclusion, and we have kind of a mission statement. We need an explanation that gives us something to strive towards. Okay, so now he's going to give an analogy so we can better understand the problem. It's helpful to draw an analogy between functional and structured programming. In the past, the characteristics and advantages of structured programming have been summed up more or less as follows. Structured programs contain no go-to statements. Blocks in a structured program do not have multiple entries or exits. Again, a negative. Structured programs are more tractable mathematically than their unstructured counterparts. That's a positive, tractable mathematically. These advantages of structured programming are very similar in spirit to the advantages of functional programming we discussed earlier. They are essentially negative statements and have led to much fruitless argument about essential go-tos and so on. Okay, so if you were to characterize structured programming, you'd say it doesn't have go-tos, and you use blocks and like if statements and things instead of go-tos, and that's kind of saying us the same thing, it's like a negative way of describing the paradigm. With the benefit of hindsight, it's clear that these properties of structured programs, although helpful, do not go to the heart of the matter, so they don't explain why structured programming is better, it just tells you how to do it. The most important difference between structured and unstructured programs is that structured programs are designed in a modular way. Modular design brings with it great productivity improvements. First of all, small modules can be coded quickly and easily. Second, general purpose modules can be reused, leading to faster development of subsequent programs. Excuse me. Third, the modules of a program can be tested independently, helping to reduce the time spent debugging. Okay, so he's talking about modules, modularity, being able to have some kind of constraints on the entry points and the exit points of the modules so that, you know, you don't want to just like go to into the middle of a module, you want some kind of, some kind of encapsulation of what's going on inside that module, so you have some function endpoints, right? Some procedures that are designed to be used from the outside. The absence of go-tos and so on has very little to do with this, the absence of them in the language, right? It helps with programming in the small, whereas modular design helps with programming in the large. Thus, one can enjoy the benefits of structured programming in Fortran or assembly language, even if it is a little more work. So this argument has been made for most paradigms. Oh, I can do object-oriented programming in C, or I can do structured programming in assembly. Yes, it's true. You can. There's nothing to do with the language. It is simply a way of building modules. But you're going to have to do it all by discipline, because languages that do have structured programming and don't have go-tos make it much easier to do. And the same is true of functional programming. You can do functional programming in Java, but it's a lot harder. There's a very important point that is often missed. When writing a modular program to solve a problem, one first divides the problem into subproblems, then solves the subproblems, and finally combines the solutions. The ways in which one can divide up the original problem depend directly on the ways in which one can glue the solutions together. Therefore, to increase one's ability to modularize a problem conceptually, one must provide new kinds of glue in the programming language. This is kind of the central thesis that functional programming provides new kinds of glue. Now, a glue is not a technical term, but you take these problems, you divide them up into small subproblems. Now, how do you put them back together? Where can you cut those lines so that you can be sure you can put them back together later, and the better the glue you know that works on the small pieces, the more modular you can make it. So now he's going to talk about the glue. We shall argue in the remainder of this paper that functional languages provide two new, very important kinds of glue. This is the key to functional programming's power. It allows improved modularization. It is also the goal for which functional programmers must drive. Small and simpler and more general modules glued together with the new glues we shall describe. Okay, so that's a tall order. improved modularization, it's a goal that we should strive for, smaller, simpler, and more general modules. And now I'm going to spill the beans on the two kinds of glue. The first one is higher order functions, and the second one is lazy evaluation. Okay, we'll do higher order functions first. The first of the two new kinds of glue enables simple functions to be glued together to make more complex ones. It can be illustrated with a simple list processing problem, adding the elements of a list. Okay, so he defines a new list type, and then he defines sum over that list, a simple recursive definition of sum, and then he extracts out the plus and the zero, because you always start a sum at zero, and he turns that into a general purpose recursive function called fold r. And this, because it takes plus, fold r is a higher order function. And so, you know, you should look at the code if you're interested, but then he starts to use fold r in all sorts of ways. He uses it to make the product, to do an or over a list, an and over a list, even to copy a list. Okay, here we go. One way to understand fold r, f, a, is as a function that replaces all occurrences of cons in a list by f, in all occurrences of nil by a. Now it's obvious that fold r cons nil, just copies a list, right, so you're replacing one cons with another cons, and you're replacing the final nil with a nil. Okay, so, you know, he's showing with a bunch of little examples that he's able to create this really general purpose recursive function, that lets him do all sorts of stuff very succinctly. He writes map in it, yeah, he just does a bunch of things. We can even write a function to add all the elements of a matrix represented as a list of lists, it is some matrix equals some dot map sum. The function map sum uses sum to add up all the rows, and then the leftmost sum adds up the row totals to get the sum of the whole matrix. So I know it's hard to hear code and imagine it, but it's basically four functions, sum dot map and sum, all in a row, no other punctuation, nothing, just very succinct definition like that. These examples should be enough to convince the reader that a little modularization can go a long way. By modularizing a simple function, sum, is a combination of a higher order function and some simple arguments, we have arrived at a part pulled R that can be used to write many other functions on lists with no more programming effort. So this is pretty convincing, the idea that you could find these very general purpose functions that let you do a ton of things with very little work. I know when I first was learning object oriented programming, this was kind of the same selling point. Oh, you just learned this set of classes and they will be so general purpose that you'll be able to reuse them all the time, and it never really worked out. It definitely was often more convenient than doing it by hand in line and see, but it never had this kind of feel, this kind of, I mean, it's just so sparse, so Spartan, sum dot map, sum, to summarize a list, I mean, sorry, it's a sum of matrix. You know, if you were to think back, like, how would you sum a matrix in an object-oriented language, you'd probably use for loops and things, and this is just so tiny. Maybe too tiny, you know, sum dot map, sum does not really call to mind very much, right? Sometimes I wonder if it's not, if it's not one of its weaknesses, then it's two six-sinked. Okay, I'm not going to go into this, but he goes into building a tree out of lists, out of cons lists, and then he can do stuff like map tree, right, so you're mapping over all the nodes of the tree. All this can be achieved because functional languages allow functions that are indivisible in conventional programming languages to be expressed as a combination of parts, a general higher-order function and some particular specializing functions. Once defined, such higher-order functions allow many operations to be programmed very easily. Whenever a new data type is defined, higher-order functions should be written for processing it. This makes manipulating the data type easy, and it also localizes knowledge about the details of its representation. The best analogy with conventional programming is with extensible languages. In effect, the programming language can be extended with new control structures whenever desired. Oh, there's a lot to unpack here. So he's saying that there are things that you couldn't break up in a conventional program, and I've experienced this before, where you would like to be able to break up, let's say, a for loop. You want to generalize this. You're tired of writing for loops, and you want to remove the duplication because you always use a for loop. I'm not always, but there's a particular way that you use a for loop where you're looping over an array and you do it 100 times, 1,000 times in a program. And you just want to get rid of that duplication. It just screams at you all day, but how do you get rid of it? You can't do a typical refactoring. So something like procedural decomposition, where you say, "Okay, this is three steps, and I'll move the first step into a procedure and the second step into a procedure and the third step into a procedure." You can't do that because the steps aren't sequential. So the for loop has an opening and then a closing, and the body is different each time. The opening and the closing are the same. The body is different. So how do you make it so that you can have this syntactically wraps the body? Well the answer is a higher order function. You can extract that out into a function. Some people would call it for each, something like that that takes an array and calls the function on each element of the array. So then once you have it, it lets you program them very easily. He suggests that we should develop higher order functions as the APIs for our data types. That's interesting. I typically don't do that, but that would be very interesting like a way of encapsulating it and not having to de-structure your data structures all the time because this higher order function would do it for you. And then this idea of being able to extend the language with new control structures. This is an idea that functional programmers have, that something like map or reduce is kind of like a control structure, it's kind of like a loop, it's kind of like an if statement. I think it's kind of stretching a metaphor, especially as these concepts enter into conventional languages, as map and filter and reduce, they're even in Java and JavaScript now, and they don't quite feel as much like a control structure over there, but I think that the perspective that you would have in 1990 where you are mostly writing for loops, and now you have this new thing like fold R that essentially does the same thing, but you wrote it. I think that that is, you know, that's the idea that you're having, right? And then once you implement fold R in fortran as a for loop, you kind of think, well, yeah, it's not really a control structure over there. So I think that this is one of those things that like, as it enters the mainstream, it feels less and less like a new control structure. I'm trying to think of a good analogy for this. I mean, the main analogy I'm thinking of is like at one point fortran, because it was not, it was parsed and compiled, it was considered the domain of artificial intelligence, that this was like automatic programming, that you don't have to write the individual instructions that the compiler would figure out what you meant, and what instructions to write. And nowadays we do consider it programming, it's not automatic, it's still hard. Although it's much easier. And so I think that there's some kind of drift that happens that our perception of what is a control structure kind of shifts into, well, that's just a method, right? Anybody could write that, it's not special anymore. The other new kind of glue that functional languages provide enables whole programs to be glued together. If a and g are such programs that g.f is a program that when applied to its input computes g of f of input. The program f computes its output, which is used as the input to program g, this might be implemented conventionally by storing the output from f in a temporary file. The problem with this is that the temporary file might occupy so much memory, that it is impractical to glue the programs together in this way. Functional languages provide a solution to this problem. The two programs f and g are run together in strict synchronization. Program f is started only when g tries to read some input, and runs only for long enough to deliver the output g is trying to read. Then f is suspended, and g is run until it tries to read another input. As an added bonus, if g terminates without reading all of f's output, then f is aborted. Program f can even be a non-terminating program, producing an infinite amount of output, since it will be terminated forcibly as soon as g is finished. This allows termination conditions to be separated from loop bodies. A powerful modularization. I'm going to stop there and comment. He's describing a pretty cool system, which is a way of a, let's say in a bash command line, you're piping one program's output into the next program as input. Very common operation, but how bash works is it will run both programs at the same time, and the output, the first one is going to be outputting to the second one. The first one is just running and outputting as much as it can, and the second one is just inputting as much as it can. What if the second one doesn't want all of the output of the first one? You have this problem where that first one doesn't know. There's no way to communicate like back up. What he's suggesting is, what if you run it so that as the second one uses the input, the first one is run to generate just enough input to get the next step for the second program. It's pretty cool. You wonder how that might work. What it lets you do is you write one program, your first program could be infinite. You could never stop generating data. It could just generate, let's say, random numbers forever, and since the second program is going to eventually stop and let's say it only needs 10 random numbers, it will, once it stops, then the first program will be stopped, which would be pretty cool. As this method of evaluation runs F as little as possible, it is called lazy evaluation. It makes it practical to modularize a program as a generator that constructs a large number of possible answers, and a selector that chooses the appropriate one. This is, he's talking about this kind of glue called lazy evaluation, lets us modularize a program in a new way. It lets us separate it between a thing that knows how to generate the data and the other thing knows how many it needs, how many of the pieces of data it needs, which is a new way of cutting it. You don't have to tell the first thing how many to generate because the second thing can just stop requesting new stuff. Lazy evaluation is perhaps the most powerful tool for modularization in the functional programmers repertoire. Okay, so he talks about, I'm not going to read it, but he talks about how in functional languages, because they are referentially transparent. That basically means that you can run any expression zero or one times. You don't have to run it, maybe you never run it, because that value was never needed based on whatever branch you went down, you just didn't need that value. And then the one time is like, once you generate it, you don't have to generate it again. And because they're referentially transparent, you got this property, you only need it zero or one times, you never need it twice, and you don't have to run everything because it doesn't have a side effect. If it sent an email or sent some message over the network, you definitely need to run it. And since functional programs in his definition do not have that stuff, then everything's referentially transparent, which means that every function call can be potentially lazy. So you don't ever have to run any function if you don't need it. And so it's just pervasive, it's everywhere, every little bit of work that your program does is done lazily. Adding lazy evaluation to an imperative notation is not actually impossible, but the combination would make the programmer's life harder rather than easier. Because lazy evaluations power depends on the programmer giving up any direct control over the order in which the parts of a programmer executed. It would make programming with side effects rather difficult, because predicting in what order or even whether they might take place would require knowing a lot about the context in which they are embedded. Such global interdependence would defeat the very modularity that in functional languages lazy evaluation is designed to enhance. This is, okay, I have a lot to say about this. So I think it's very true you can't have lazy evaluation in the presence of side effects. It's not recommended. It would be more work to express the order that things can happen in and what needs to happen when then just running the thing in strict evaluation. But I also think that this is a kind of binary thinking that we often fall into as programmers, certainly as functional programmers, where something is just like before he said, you're either referentially transparent or you're not, it's not a yardstick, it's not something that you can measure how referentially transparent you are. He's saying you're either lazy or you're not. And I don't think that that's true. I think that, for instance, enclosure, it has lazy evaluation for lists, for sequences. And that gives you a lot of the benefits, it's not all of them, certainly, certainly not all of them. Haskell has pervasive lazy evaluation and it's definitely a different ball game. But to say that there's no halfway, I just can't agree with that after using closures lazy evaluation. Now, of course, enclosure, you do have to be a little bit more careful because you don't have the help of the type system. And so you could accidentally put in some side effects in your code that will be lazily evaluated. But in general, it's not really a big deal. Okay, so he goes over some very mathematically oriented functions that he's writing. He wants to write something that finds the square root. And then what he does is he generates successive using the Newton-Raphson method. He generates successive approximations of the square root in a list lazily. So he's an infinite number of approximations, they get better and better and better. And then he runs other functions on top of that, that approximate it faster. And so this is also lazy, so he's mapping over that. And he does all this cool stuff. I'll read this section here. There's a lot of codes, I don't want to read it. The function repeat is an example of a function with an infinite output. But it doesn't matter because no more approximations will actually be computed than the rest of the program requires. The infinity is only potential. All it means is that any number of approximations can be computed if required, repeat itself places no limit. So here we see how he can make this module called repeat that doesn't need to know anything about how many to generate. It can just generate as many as the consumer needs. The remainder of a square root finder is a function within, which takes a tolerance and a list of approximations and looks down the list for two successive approximations that differ by no more than the given tolerance. So he has his other function, which is going to consume this infinite list and check two subsequent values in the list and see if they're closing up together to say, ah, you've stopped, you know, this is below my tolerance. And so I'll just accept this as a good enough answer. And then of course he refines this and refines this. All of this stuff is from structured interpretation of computer programs when they get into, um, I don't know how, where they get into this, what chapter, but it's, it's, it's something I remember from that. And he, he does cite it. Okay, all right, so this, so this is where he ends this, um, this example where he just keeps iterating on like, oh, let's find it this way and we can make the answer better this way. And of course it's still like one line programs to do this. This is probably a case of using a sledgehammer to crack a nut. But the point is that even an algorithm as sophisticated as super is easily expressed when modularized using lazy evaluation. Okay, another example. He will do some numerical integration. Now I'm not going to read all the code. I'm not going to go through the explanation. He does an awful lot of, um, what I would consider kind of showing off like what functional programming can do. If you know what you're doing, um, there's just a lot of like, oh, and then we can write this function. We can write this fun. We put them together and we get this and we take this and we get this. And he shows like, wow, you can, you can so easily in like a line of code, uh, get something that would require, you know, a good chunk of imperative code in it. And at one point, he does shows, I think it's a Fortran program. One thing that bothers me about this is that it's all very maffy, um, it, it does to me make functional programming look like this is a paradigm that's only good for math. You know, given that it only can compute a function of, from inputs to outputs. And then all the examples are mathematical. It's kind of suspect that this would ever be practical, um, I don't know what to say about that except that, uh, I think it's, it's just kind of, it's typical of this kind of paper. It's written for an academic audience is, it's a memo circulating at a university computer science department, um, it's, it's just going to, it's just going to be that way. It's going to be kind of mathematical, um, I also think that there's, uh, a little bit of what would you call that is, is being a little false in that, um, there's no discussion of how you might have ever found these functions that he's using. You know, you know, do you know enough math to come up with, uh, these kinds of functions that he's showing you because often in my code, uh, it, it doesn't look like this even when I'm using a functional language. So I just wonder about that, you know, sometimes you go down a rabbit hole trying to factor something out into something beautiful and it doesn't turn out. So what does normal code look like? That's, that's my, my issue there. Okay, the final example in section five is he, he writes a game tree and he, then he does minimax over it, which is actually a pretty cool algorithm. And I remember writing this algorithm in a class I did in college. And so this was very, uh, revealing to me that, you know, this algorithm was very complicated because it starts as a simple, like for loop, you're managing your own stack. And then, oh, now you have to do this optimization. You have to do this optimization and like the loop just grows and gets hairier and has all sorts of variables, keeping track of things. And his solution while, uh, certainly more concise, uh, is very terse, very terse and like, I, I don't know if I could read it. Um, so anyway, I'm going to read a paragraph from here, uh, this is one of the cool things about the way he's written it. So he writes it as, you know, an infinite game tree. This function returns an infinitely deep tree, of course, since it's lazy, it's not generated until you actually go down the tree, and so then you can have a function, uh, composed with that, that using lazy evaluation says, well, I'm only going to take, uh, let's say five levels deep, right? Or then another function is like, well, I'm only going to take the first three branches of every node. Right? And so you've automatically, um, modularized, you've optimized the problem, but you haven't changed the simple code that generates the game tree. You've only added, you've only added an optimization, uh, and the, the point is that instead of taking this hairy for loop and like making it even more hairy by adding an optimization, you can add the optimization in a separate step and not have to modify the existing stuff, which is kind of the definition of modularity, right? You can add a module that does the optimization and the original code is still there and still useful. Since each part can be thrown away, that is reclaimed by the garbage collector, as soon as maximize has finished with it, the whole tree is never resident in memory, only a small part of the tree is stored at a time. The lazy program is therefore efficient. This efficiency depends on the interaction between maximize, the last function in the chain of composition, and game tree, the first. Without lazy evaluation, therefore, it could be achieved only by folding all the functions in the chain together, into one big one. This would be a drastic reduction in modularity, but it is what is usually done. We can make improvements to this evaluation algorithm by tinkering with each part. This is relatively easy. A conventional programmer must modify the entire program as a unit, which is much harder. So that is kind of just what I said, what I just said, that it is a series of functions composed together, and stuff that is on the first function that gets called game tree, which is the one that generates the game tree, and the thing that does maximize, which is the last function, there is an interaction between them. That interaction is through that maximize is kind of requesting more game tree from the game tree, because of lazy evaluation. So this means that in a conventional program that does not have lazy evaluation, they would have to be in the same function. They would have to be part of the same bit of code, because you could not get that interaction between them. So this idea of maximize deciding, I do not need to go down that branch. That would somehow need to be communicated to the part of the code that is generating the tree. So typically what happens is that all happens in the same big loop, and functional programming with lazy evaluation lets us avoid that. I just want to show how concise this thing can get. So he writes this function called evaluate. It is using point-free style, which means he does not name his arguments. By the end of this section, he is iterating on, it is not like he starts this way. He writes evaluate equals max dot maximize prime dot high first dot map tree static dot prune eight dot game tree. Of course, if you do not know what they mean, it is gobbledygook, but each of these functions is just composed with the last, and so it is just kind of like a stream of data coming from game tree being manipulated, optimized until it finally gets to maximize, and max which chooses the best one. To me, sometimes I think of this as right-only code, you know, like it is hard to read, but there is something to be said for it being decomposed into all these little pieces. Maybe you choose better names, I do not know, but there you are, it is much cleaner. Okay, this is the end, I will not read the conclusion again, but I really like this paper. It attempts to talk about why functional programming does seem to work better for certain problems, and the answer that it gives is modularity, and that functional programming provides two new kinds of what he calls a glue, two new ways of putting programs together, and those two things are higher order functions and lazy evaluation. I happen to think that higher order functions are probably more powerful than lazy evaluation, but it has me thinking, this paper is really getting me to think that maybe lazy evaluation is one of those unsung heroes that we still haven't really integrated into the way we do program. High order functions I think are already there, you know, JavaScript, even Java and C# with lambdas and things, that world has experienced higher order functions. Maybe the next step is lazy evaluation, and it would be neat to see if we could get there somehow. Right, well I hope you enjoyed this paper as much as I did, I don't feel like I had too many insights on this one. Maybe it's just so straightforward, not much to say. I want to believe it, that it's all about modularity, but man I really have to sit on this and really think about whether that's the case. Really kind of blow a hole in a lot of the ways I think functional programming is better. Okay, well I'm going to sit on that and I'd love to hear your thoughts on it. If you have some thoughts you want to share with me, if you like it, you don't like it, disagree, agree, look me up. You can find this in all the past episodes at lispcast.com/podcast and you'll find links to get in touch with me in various ways. I'd love to hear your thoughts on this, the kinds of things that other topics you have, questions about, other papers you'd like me to read, and please subscribe and tell your friends all about the podcast. All right, my name is Eric Normand, this has been my thought on functional programming. Thanks for listening.