#112 Functional Programming

While very few programmers work in purely functional languages, functional programming has captured an increasing amount of mind share in the programming world. In today's episode, we'll explain what functional programming is and why it's useful. Welcome to Copec Explained Software, the podcast where we make computing intelligible. In today's episode, we're talking about functional programming. Functional programming is one of four major paradigms in the programming world. In order to get the most out of today's episode, you'll really need to be a programmer. So this is one for the programmers and to understand the context of different programming languages. If you don't have a CS education, I'm going to link in the show notes to some of our previous episodes that explain some of the characteristics of different programming languages.

Let's start with just a lay of the land of the different programming paradigms.

We can divide the programming paradigms, and there's about four of them, into two major categories imperative and declarative. The imperative category includes paradigms like procedural programming and objectoriented programming paradigms that most programmers are familiar with. The declarative world includes two paradigms that are a little bit more foreign to most programmers and those are functional programming and logic programming. Today, of course, we're talking about functional programming, but I want to talk about imperative versus declarative a little bit so people understand where functional is coming from as opposed to object oriented and procedural languages. In an imperative language, you tend to explain how to do something. So let's say we have a list of strings and we want all of them to be lowercase. Well, in an imperative programming language we say, well, I want to have a for loop and I want it to go through each of the items in that list. And for each list I'm going to remove it and I'm going to call a function that's going to change it into a lowercase string and then I'm going to add it to a new list. And then at the end I'm going to return that list that has everything bundled altogether. If I was doing the same thing in declarative programming language, if it was truly declarative, I might just be able to literally say, take this list and make it all lowercase and then it's up to the programming language and the runtime to figure out exactly how to do that. So it figures out, oh, there needs to be a loop and here's all the things that the loop needs to do. We don't explicitly write the loop in imperative programming language we're constantly explaining all the steps and saying how to do something, whereas in a declarative language we're just saying what we want to do and hopefully the language is figuring out more about how to do it so we don't have to explicitly write out all of the steps. Functional programming languages tend to be more in that declarative camp where we're writing out less of the individual steps and keeping things at a higher level.

That sounds pretty nice and efficient.

Yeah. Declarative is the dream, and a lot of people think that's the long term future of programming, us programmers will hopefully be less in the nitty gritty. Functional programming today is not all the way there. You're still explaining some of the how and it's not like you can just work at an extremely high level, but you're working hopefully at a higher level than you are typically in an imperative language.

Give us the bird's eye view of functional programming.

Yeah. Now that we've talked about the paradigm and how the paradigm fits into declarative versus imperative, let's talk about some characteristics that most functional programming languages tend to have in common. The problem with this, doing this entire episode, is that people actually disagree on what the term functional programming really means. And if you talk to different people, they'll give you different characteristics of functional programming languages. I have chosen the ones that I think are important to why functional programming has been influential in the programming world today. So these are from my mind. This is not from some academic article. So one of the first things that we tend to see in a lot of functional programming languages is the idea of immutable data types. Immutable data types and immutable data structures. Instead of constantly dealing with state and mutating state all the time, we deal with data the way that it is. And when we want to have some different data, we actually copy the old data structure and make some changes to the copy instead of changing the original instance of the data. This can have some advantages, especially in a multi threaded, multiprocessing concurrent environment, so that we don't have different threads messing and mutating the same data at the same time. It's naturally safer to have the data types be immutable. It can have some performance problems because if you're copying data all the time, instead of mutating the original data, that's going to be expensive. You're going to be using extra memory. And it actually takes some CPU cycles, of course, to do all that copying all the time. And there are some performance optimizations in functional programming languages, things like Copy on Right, where you only actually start making a copy when you know that you're going to make a change to that different instance of the data. So immutable data types are really common in functional programming languages. Another thing, and this is probably the most important thing in functional programming languages, is there's the idea of the pure function. And we can have pure functions in any programming language, but they tend to be more common in functional programming languages. A pure function is a function. That result is completely determined by its arguments. So the arguments that are passed in as parameters to the function completely determine how the function operates. There's no outside global variables affecting the function. There's no state that's having side effects that are somehow going to be different from one run of the function to another run of the function. So the function has no side effects. Effectively, every time we run the same function with the same arguments passed to it, we always can expect the same result.

It's like a function in math.

That's right, yeah. That's kind of similar to how we think about functions in math. So if a function will always return the exact same result for the exact same arguments, then we say it's a pure function. And functional programming languages tend to prefer pure functions.

Is that why they're called functional programming?

Yeah, it's a big part of it. And also a function is just the main unit of abstraction in a functional programming language in the same way that a procedure is in a procedural programming language or an object is in an objectoriented programming language. That's the fundamental unit of abstraction. A few other things about functional programming languages, they tend to prefer recursion over loops. Some functional programming languages don't even have loops. The only way to repeat yourself is to use recursion. Functional programming languages tend to support first class functions, and a lot of modern imperative languages do too. And I'll talk a little bit later about what that is for folks who don't know what that is. And also functional programming languages tend to have builtin support for higher order functions and the use of higher order functions in their standard library, things like Map, Reduce and Filter, which a lot of programmers are familiar with. They exist in languages like Python and JavaScript, but they tend to be one of the main ways that you interact with collections in functional programming languages. So those are my characteristics of a functional programming language. And you know, not every functional programming language is going to have all of these characteristics. What I've done is I've taken some common functional programming languages and some just common modern languages and I've kind of categorized them by how purely functional they are. So if we take a language like Haskell or Idris or Elm, I would say those three languages are quite purely functional. They have all of those characteristics we talked about before, and they don't even have support for programming in more of an imperative style. So I would really think about them as almost purely functional languages. Then we have some languages that really have a lot of influence from the functional programming world. We think about them as functional programming languages, but they are able to be programmed in more of an imperative style if you really want to. And languages that I think about from that area are things like Scheme Closure, ML, and F Sharp. I definitely would call all four of those languages functional programming languages, but I don't think they're as pure as a language, let's say like Haskell. They have all those characteristics that Haskell does, but they let you do things another way if you want to. And then we have some modern languages that have been influenced by functional programming but often are actually programmed in an object oriented style, or maybe more in a procedural style too. Sometimes I would think about languages like Swift, JavaScript, C Sharp and Scala as all supporting the ability to be programmed in a functional style. But I really think about them as multiparadigm languages that are often programmed in an object oriented style. So you can program them in a functional style if you want to, but they're not really limiting you or really like pushing you to have to work in that direction.

That's a real benefit to be able to choose the paradigm that you want to program in.

Perhaps it gives you more options as a programmer, but it also can mean that two different programmers may be working at two different companies with two different style. Guides can be programming in quite different ways. So you can see some Swift code from one company that's in an extremely functional style and you can see some Swift code from another company that's really in an object oriented style, and the two might really look quite different from one another. And then trying to merge a library that was programmed in one style with a program that was programmed in another style can sometimes lead to some impedance mismatches. And so there's pros and cons to being a multiparadigm language. The biggest con being that there's more than one way to do the same thing and then it might not always fit well with people who are doing some of their program the other way. If you have to, then combine the two styles.

Would a user be able to tell this is how this is being programmed in this paradigm if someone's using a more functional paradigm or not?

Hopefully not. Hopefully all of our programs are bug free enough and they work well enough that our users don't really know what's going on behind the scenes. Of course, one of the ideas of functional programming is to be more provably correct, because we have these pure functions that we can really extensively test, because we have these immutable data types, hopefully we're having less concurrency errors, so hopefully we're building more robust software. That's one of the reasons that we're going into this more esoteric style. But in reality, of course, somebody can program badly in a functional language, just like somebody can program well in a nudge oriented language. So there's no guarantees there.

How has functional programming impacted the programming world or the software community?

Yeah, functional programming really grew up in the academic world and for decades it was really just popular in academia. For example, the second course I took in my CS journey in college was in Scheme, which is a functional programming language. And that was really common. A lot of schools were using Scheme as either an intro language or a second language in their CS curriculums, and there was a lot of excitement about functional programming for decades within academia. It's really only in the last 20 years that functional programming has really matured from the academic world into industry. And where we're seeing it is not in the widespread usage of purely functional languages, but in the adoption of some ideas from functional programming in mainstream multiparadigm languages. So even take a language like Java. Java, originally a purely object oriented language, came out in the mid 90s, really had almost no influence on it from the functional programming world. But as Java has continued to evolve, especially in the last five years or so, there have been some ideas from functional programming that have made their way into the Java language with some of its new features. Or if you take a language like Swift, swift I would truly call a multiparadigm language. You can program it in a functional style if you want to, and that was true all the way going back to Swift. One and two, the early versions of the language, you can also program in an object oriented style. And what a lot of people do is they're kind of merging some of the two styles. Most of your program might be object oriented, but the way that you're manipulating collections is usually going to be with Map, filter and Reduce in Swift. And those are ideas that really are more common in the functional programming world. And you might be using a lot of immutable structs when you program in Swift. Again, that's an idea that comes a lot from the functional programming world. So Swift has a lot of influence from functional programming, I think, both in the language itself and also in its standard library. So we're seeing functional programming kind of influencing mainstream languages, while those mainstream languages are not becoming purely functional themselves.

Functional programming wouldn't work for everything that you're trying to do though, right?

Yeah. We talked about earlier how in a lot of functional programming languages, there's no global mutable state, and a lot of programs require global mutable state. For example, anything you do with a graphical user interface, there's generally going to be a Windows Server that has some global state about what are all the Windows that are right now open and where are they positioned on the screen, et cetera, et cetera. Would there be a way to program a Gui with a functional programming language? Sure, and there are systems for doing that, but it's not generally going to be as performant as if you have some mutable global state. The same is true for graphically intense video games. They're going to need to eke out every little bit of performance, and we're still going to end up getting the most performance using a language like C or C plus plus. That's at a low imperative level where we're really specifying how to do every last instruction, and we also have that global mutable state instead of copying things around memory all over the place. So some specific application verticals really make the most sense still in an imperative language instead of in a more declarative language, and specifically in a functional programming language. Functional programming is really not right for every app.

What about first class functions?

Yeah, we mentioned it earlier as a characteristic of functional programming languages, but it's a great example because it's one place where functional programming has really had an influence on a lot of existing programming languages and new programming languages that are non functional. Most modern programming languages have first class functions. Programming languages that have first class functions have all of the following characteristics you can assign functions to variables, you can pass functions as arguments to other functions, you can have functions that return functions as their results and you can even have functions be part of data structures and you can declare functions anywhere that you can declare other types. So you can even declare a function within a function. A lot of modern programming languages have all of those features and we would say therefore that they have first class functions. For example, the programming languages Go, JavaScript, Swift all have first class functions. And this is an idea that really came a lot from the functional programming world. So this is a very specific area where we see the influence of functional programming on a lot of modern languages. Another area I want to get into a little bit more is recursion. It might be shocking to some new programmers to hear the idea that we would do away with loops and try to always repeat ourselves just using recursion. And recursion is just a function that calls itself. But this is the direction that a lot of functional programming languages go in. They have optimizations because otherwise this can be expensive. One is called tail call optimization and you really need that to have a performant language that doesn't have loops. Anything that you can do with recursion, you can also do with a loop. There are some instances where we don't have tail call optimization and the loops are going to be more performant than the recursion. But you can implement the same algorithms that you can implement with recursion, also with loops. So it's really just another way of being able to repeat yourself. It's a slightly different way of thinking. And the fact that functional programming languages really prefer recursion over loops sometimes scares off some new programmers. That said, there are some problems that actually map better to the way that we think about them with recursion than they do with loops. So working with a recursive mindset can actually be a benefit for implementing certain kinds of algorithms.

Is functional programming performant well?

It's going to vary, of course, based on the specific functional programming language, but we can talk about it in some generalities. Most functional programming languages that are used today are reasonably performant. Generally they're ahead of time compiled, a lot of them are statically typed, they'll often have garbage collection, which is a bit of a downside for performance, but not the end of the world memory. Performance can suffer if we're doing tons of copying all the time because of those immutable data types. Some compilers will be able to avoid some of this by implementing optimizations like copy on right recursion has some performance downsides, especially if we don't have tail call optimization. So there can be some situations where just the fact that we don't have loops in some purely functional language could be a real downside. A lot of higher order functions and we'll talk maybe a little bit more about them in a minute can be parallelized, which is nice, and that naturally leads it to be easy to make some functional programs concurrent. But the biggest downside for performance of working in a functional programming language is if you don't have access to global state. Like we mentioned earlier, there are some types of applications, for example, certain kinds of graphical user interfaces and certainly many 3D games that really will be a lot faster if we just have some global state that we're constantly mutating instead of copying around some more limited state. So that's really one of the biggest bottlenecks for them. But in general, functional programming languages that are out there on the market, languages like Haskell are reasonably performant, they're not as performant as CRC plus plus, but they're also not going to be out in the weeds like a Python or a Ruby, they're going to be somewhere in the middle.

So why would a programmer choose to program in a purely functional language?

Well, it really depends on the kind of software that you're building. For example, I have a friend who is a real expert in Haskell and he was actually a vice president at a large bank working in Haskell because they wanted to use a language that had immutable data types for safety of working with all kinds of financial transactions. There's a certain amount of safety and provability where if we're really working with pure functions, we can be sure that they really work and they can be really extensively unit tested without the question mark that comes from side effects. And so there are certain kinds of applications where we really want a certain degree of provability and we want to be able to prevent certain kinds of errors where functional programming languages really make a lot of sense. And then some of these ideas from them have been influential on bigger modern languages because they actually lead to new ways of thinking and solving problems that might be simpler than the old ways that we were doing them. We talked at the beginning about the whole idea of declarative style instead of imperative style. When you use higher order functions like Mapreduce and Filter, you operate on collections and you say more just what you want to do to the collections, instead of having to go through the nitty gritty of writing loops that piece by piece modify the collections. And that actually, once you get used to it, can be a much more readable style. And it's actually a less error prone style because, again, you're saying more just what you want to do instead of the specifics of how to do it, where you could make mistakes on some of those steps about how to do it. So functional programming, I think, is here to stay. It is having an increasing impact on the entire world of programming. It's been kind of building up over the last 20 years. Its influence, it's definitely broken out of the world of academia and made it into the mainstream. Do I think it's going to overtake imperative programming right now? No, I think there's still too many performance bottlenecks for working in purely functional programming languages for everything. But I think its influence is going to continue to increase. And I think if you want to be a good programmer today, even if you're working in a C Sharp or Java or a Python, you should at least be familiar with the ideas from functional programming, because I think they'll improve your existing programs that are written in an odd oriented style. Okay, thanks for listening to us today, Rebecca. How can people get in touch with us on Twitter?

We're at Copec explains K-O-P-E-C-E-X-P-L-A-I-N-S. Don't forget.

To follow or subscribe to us on your podcast, Player of Choice, and we'll see you in two weeks.

Bye.

Thank you.