A (3:18)

So composition is the superpower of functional programming.

B (3:23)

Yeah.

A (3:27)

If I write my entire programming, if I write my entire program in this functional programming style, what how does that affect the architecture overall of the program?

B (3:40)

I think it affects it in a rather profound way. Your whole program will be a single expression, and then to evaluate that expression will be to run the program. And so it's a fundamentally different way of architecturing software. Architecturing? Is that even a word architecture of constructing? It's a fundamentally different way of constructing software.

A (4:05)

Yeah, constructing is a good word. What led you personally to this way of structuring software?

B (4:13)

So my background is in Java programming. So I did a lot of sort of enterprise Java for large systems in the past. And it always struck me that these systems were really difficult to manage, difficult to test, they had a lot of bugs, and it was difficult to just achieve the kind of stability that I wanted. And so that led me to investigate whether there was some way of having better static guarantees about software. And that led me to languages like Haskell, and Haskell is a purely functional programming language. And then from there I started investigating functional ideas and I started importing those ideas into Java. And I was a contributor to a library called Functional Java for a while, and then a similar one for Scala, which is called Scala Z.

A (5:23)

Your book Functional Programming in Scala teaches functional programming using the Scala programming language. Is that required? Is Scala required to do functional programming or can another language work?

B (5:37)

Oh, yeah, Scala is absolutely not required to do functional programming. I mean, the first words in the book are, this is not a book about Scala. Yeah, so like I said, we were doing functional programming back in the day in Java, before it even had closures. So all you really need is some ability to abstract out functions. To talk about functions is the first class thing. The way that we were doing this in Functional Java was just as an anonymous object. So a function was just an anonymous object of a class that had a single method called Apply, and that worked perfectly. Well. I wouldn't say perfectly well, but it did work.

A (6:26)

Maybe a little verbose, but gets the concept across.

B (6:29)

Right. And it allows you to structure your program in this way and reap the benefits, such as they are, of purely functional programming.

A (6:42)

So a pure function is a function in the mathematical sense, and it has no side effects.

B (6:48)

Right.

A (6:50)

And you're stating that a pure function is more modular and reusable than, say, an imperative procedure or a standard Java definition. Why is that?

B (7:03)

Well, so modularity is the property that you can take the system apart into modules and then reassemble them in ways that you didn't necessarily anticipate when you were designing those modules. And a function is sort of the ultimate module in a sense, because a function can basically always participate in a composition where its input type is provided and where its output type is expected. And that there's never going to be the case, like when you pull a function out of a system, it's never going to have sort of like wires hanging off of it, you know, like pulling the carburetor out of a car or something. It's always going to just have an input node and an output node, and you're going to be able to sort of snap that in to wherever that makes sense.

A (8:07)

And this is what is meant by referential transparency.

B (8:13)

So this is what is meant by modularity. But yeah, so referential transparency is the property that when you, when you evaluate the program or when you evaluate an expression, it's not going to. It's not going to have a side effect that is the result of evaluating the expression is going to have the same meaning as the, as the expression that you started with. So, for instance, like five plus two is referentially transparent because it just means seven. And if you replace that expression with seven, you're going to have the same program that you started with. And in functional programming, you have this property at every level.

A (9:16)

And this is often called the substitution model.

B (9:20)

Yeah, right.

A (9:21)

So I can take the result of my five plus two, which is seven, and I can replace it with five plus two and get the same result.

B (9:34)

Right, exactly. And this is what it means to execute a program in functional programming. You just keep doing this to all of the sub expressions of the program. You keep evaluating them and replacing, substituting the evaluated results for the expressions. And once you have substituted for all expressions, then you have executed your program.

A (10:01)

So I think that makes great sense. In terms of math, I think it seems a little tricky when you are pulling in information from a file system. You mentioned before the runtime system.

B (10:17)

Yeah.

A (10:18)

So what happens when there's IO involved?

B (10:23)

Well, so for instance, in Haskell, the main entry point into your program is going to be an expression, which is called main, and it's going to have a type which is called IO. And what ends up happening is that this expression is going to construct a value of this type IO, so it's going to reduce to a single such value, and that value is going to be returned to the caller, which is the runtime environment. The Haskell runtime environment is going to receive this sort of script type IO, and it's going to execute that. So the IO effects, like reading from files or whatever, that never happens inside of your program, they happen outside of your program in the runtime environment. Does that make sense?

A (11:23)

Yeah, it does make sense. I think in some ways it seems a little more complex than maybe we're used to in an imperative sense, but it actually matches the way like the computer works, your program isn't actually performing the I O. Right. Like there's a. It's like it's. The disk reading is done by some sort of IO system within the architecture of the computer.

B (11:46)

Yeah, exactly. I mean, the way that traditional programming languages work, like procedural programming normally, is that the I O system or the runtime environment expects to be called back. It expects the program to poke at it in certain ways, to call interrupts or other things like that. Functional programming is simply an inversion of control. So instead of calling the runtime environment back, we simply return a value to the runtime environment that lets it know what it needs to do.

A (12:30)

Mm. How. How does mutation work? Or actually why. Why is immutability important to functional programming?

B (12:45)

Well, immutability is important because mutation is. Mutation is a side effect. It's not referentially transparent. It breaks this substitution model because the sort of. The value of a particular variable will change when you mutate it. And so, yeah, it's going to be important to not mutate memory directly or if you do so, then to do it in a very controlled way. And there are methods for using mutable memory purely functionally, which we talk about in the book towards the end.

A (13:35)

So if I think of the first program I ever wrote, it was a C program and it had a for loop for I equals I plus one. So I equals I plus one. That's verboten.

B (13:55)

It's not totally forbidden. It depends on the context. It depends on whether anyone can observe that happening. So if someone has a reference to the value I and then I go. And so let's say I'm using the variable I in two places in my program, and then in one place I increment I by one, then it's going to come as a surprise to the other part of the program. Or it's going to lose the sort of referential transparency that evaluating or substituting in like I substituting the value of I is not going to give you the same. It's not going to give you the same program as I. So say I is 4. Then the value of I is going to be 5. And then taking I plus plus and substituting 5 is not going to have the same meaning, right?

A (15:03)

Yeah, it's breaking the substitution. And in that case it's because the I is shared, because there's a. A shared state between these two areas of the program.

B (15:16)

Yeah. So it's usually safe to mutate local state. So if you are in a function, say when you create this local Variable I like in a loop, like you said, you create this local variable I and you proceed to mutate it and you don't actually ever look at it except in this one place. And then it doesn't really matter. You can consider the for loop as just a single referentially transparent expression. If you don't look inside of it, then you can consider it to be referentially transparent because it will always evaluate to the same result as long as expression that's inside of the loop doesn't have any side effects.

A (16:10)

Yeah, because if I understand. Because my for loop is inside of a function and that function from the outside has no side effects. It doesn't. It doesn't matter so much that inside I'm actually mutating this variable because nobody from the outside can see that.

B (16:27)

Exactly.

A (16:27)

Is that right?

B (16:28)

Yeah, yeah. And then she. I think it's chapter 14 of the book. We talk about a data structure that allows you to reason about this sort of formally and allows you to actually share around values that compute with mutable state locally. And you get this sort of guarantee that if you are looking at a mutable variable, then it's always safe to mutate it and that you're the only one who can see it.

A (17:01)

And what data structure is that?

B (17:03)

It's called the ST monad.

A (17:06)

So state transformer.

B (17:08)

Yeah, it's not totally clear what ST stands for. It's like state thread, state transformer, or it's a mutable state monad.

A (17:20)

Okay, so back to my for loop example. Should I be writing for loops to loop over a list of whatever integers? Is that the functional programming style?

B (17:37)

It's not. So a for loop like that creates an incoherency in that the structure of the loop doesn't really reflect the structure of the list. It's possible to have off by one errors and other things like that. So you don't really have much of a guarantee that you're going to correctly loop over the list. So the functional way of going over a list is by using a fold. So you start with the. You start with the empty list and you say. You say, what is going to be the value if this list is empty? And then you say, how am I going to add? Or how am I going to evaluate one of the elements from this list and add that to my result? And then you recurse over the list with those two things.

A (18:45)

You recurse.

B (18:47)

Sorry, go ahead.

A (18:52)

You recurse over the list, but not explicitly. Is that right?

B (19:00)

So you can recurse explicitly, but that recursion is Always going to have the same structure. So you can abstract it out into a function. And that function is usually called fold left, fold, right for the lists.

A (19:19)

So I could write a recursive function wherein to operate over my list I handle the base case and then for the next element I call the function on itself. But what you're recommending is to use fold and fold abstracts over this concept.

B (19:45)

Yeah. So if you write the explicit recursion over a list, you're always going to write that the same way. So you're going to be repeating yourself a lot. So you can actually just write recursion over a list once as a concept and call that fold, and then the only thing you have to specify are the base case and the function with which to fold.

A (20:11)

So fold is, I think fold is a great example of kind of the power of abstraction of a functional programming language. In your book you state that a fold is a polymorphic higher order function. Could you define those terms or explain that?

B (20:34)

Sure. So it's polymorphic. That just means that it will accept a list of any type. So a list of integers, a list of strings or whatever, and you choose which type that is at the call site. So that's what's called parametric polymorphism. And higher order function is just a function that accepts another function as its argument. So fold will take the base case and it'll take a function that accepts the elements of the list.

A (21:21)

Mm. So parametric polymorphism, is that similar to polymorphism that I learned in my, like, intro to object oriented, like a circle is a square.

B (21:37)

It's not. I. It's been so long since I've thought about object oriented programming that I don't really know anymore what polymorphism means there.

A (21:53)

So polymorphism, I think that parametric polymorphism is maybe more like generics, and that polymorphism in the traditional OO sense is like inheritance. Does that make sense?

B (22:06)

Yeah, that makes sense. Although I think the purpose of both sort of similar. So it's going to be allowing to call a function with multiple different values and allowing, I mean, sorry, calling a function with multiple different types and choosing which type that is at the call set. I guess that's sort of the purpose. But with parametric biomorphism it's usually you can choose any type, not just like a subtype of another class.

A (22:49)

So map is another higher order polymorphic function. Could you describe map?

B (22:59)

Yeah. So map over a list will take the list and it'll take a function that accepts an element of that list and it'll turn it into A value of a different type and map will simply apply that function to every element of the list and it'll return the resulting list.

A (23:25)

Exceptions in the Java sense are a violation of. Of this encapsulation. A pure function throwing a null pointer exception seems to me violates the substitution rule that you were discussing. So how does functional programming deal with exceptional circumstances?

B (23:51)

Right, yeah. So exceptions absolutely do violate the reference to transparency. And if you throw an exception inside of a function, it's no longer a function because it's not returning a value. And the way we deal with that, the way we deal with exceptional conditions in functional programming, is simply to return a different value. So for instance, in Scala we use option. In Haskell it's called maybe. So you're going to have a function that takes an int and a maybe string, or maybe the other way around, it makes more sense. It's going to take a string and a maybe int. So in the case that the string actually can be parsed to an integer, then it's going to return that integer, and if it doesn't parse to an integer, it's going to return a special value called nothing or none, which is not the same thing as null, which we can talk about later, but it's going to be. So this special case, nothing or none, is going to be encoded in the type. So that value is going to be a value of the return type of the function. So it's going to. Which is going to be options, int or maybe int, depending on your language.

A (25:22)

So what makes it different than null?

B (25:27)

So null is sort of a special. Like in Java, null is a special value of every type. And so. And it's not like a part of the type. So null is not an integer technically. Right, but if you say null and you claim that that is a type integer, then the compiler is just going to accept that. And then when somebody receives that value, it's sort of like a landmine in their code. If they go and they dereference that and they say, okay, well now show me, like add 4 to this integer, the whole program is going to blow up. But with a value like, or a type like maybe or option, it's really like a list that can have either no elements or one element, and so you have to just fold that list in order to get at the element that might be inside. So it's a fundamentally different way of talking about absent values.

A (26:55)

So it's much more explicit, it seems, rather than any specific value can be null, you're specifying the return Type here, either can be an integer or it can be a none, and then the caller has to deal with that explicitly.

B (27:20)

Yeah, and then you can do other things. Like there's another data type called Ethereum. So instead of just having a none or nothing, like an empty value, you can say this function returns either an error or a string or an integer. So you can say, if I'm parsing my string to an integer, either it's going to return an integer or it's going to return a string telling you what went wrong, or something like that. And then you just have to deconstruct that either value and look at whether you have an error or an actual value. And that's just going to be a normal value, it's not going to be catching an exception.

A (28:11)

And so the either is valuable if you want to return more information about what went wrong.

B (28:19)

Right, exactly. And since it's just a normal value, you can make that type sort of arbitrarily complex.

A (28:32)

So it doesn't. Like we started off talking about exceptions, but it doesn't have to be exceptional and either could be used. If I wanted a function that returned a, say it takes a number from 1 to 10 and. And if the number's below 5, it returns a string, and if it's above 5, it returns an integer. I don't know why that would exist, but neither could be used.

B (28:58)

Yeah, yeah, you could totally do that.

A (29:02)

So if we're making. So we're making the exceptions less exceptional, we'll make them explicit values. Does that make it more difficult for the caller of the function? They have to explicitly deal with possible failure cases as opposed to an exception which just travels up the call stack.

B (29:29)

It doesn't really, because of things like map. So if you don't actually care about the exception, let's say you have an either like this, and if you don't care about the error condition, then you can map over it. So you take a function that just computes with your integer that you have inside of your either, and you map that over the either, and that will ignore the error side. And you can just keep doing this. And, and you never have to explicitly talk about your errors unless you actually care about them.

A (30:13)

The higher order abstractions like map and fold that we have let us kind of work, let us deal with these exceptions without a ton of boilerplate, I think. Is that what you're saying?

B (30:26)

Yeah, that's what I'm saying. It's the case that if you have either E, A, either E or A, then you have a function from A to B. You can always compose those two things together. The function from A to B just snaps where that A is going to occur and it'll turn that into an either E or B.

A (30:56)

So the exception can travel up the call site just by mapping inside of this either structure.

B (31:05)

Yeah, so it sort of travels in a different way, but it has the same effect.

A (31:14)

You mentioned earlier, functional data structures. Now, I don't know if we'll get into the stmonad, but. But just basic data structures that are used in an imperative way, like an array, seems to not be appropriate for functional programming. Like an array involves mutation. So how do we deal with lists in a functional manner?

B (31:47)

Right. So the, the traditional way of dealing with lists in functional programming is to use a linked list. So then you'll have a base case, which is the empty list, and then you'll have a constructor which can construct a list out of a single element and another list. And so it's going to be a recursive data structure. So yeah, you're very rarely going to be working with arrays, but you might be working with abstractions that hide away the fact that there are arrays under the hood. So that's a very common pattern.

A (32:33)

So there's no mutation involved. But it looks like an array.

B (32:37)

Oh, other way around. So there might be data structures that you have that are actually mutable arrays under the hood. But since you can't see that you can only operate on these arrays using referentially transparent functions, you're never going to see the fact that there are arrays under the hood that's abstracted away from you. It's just an implementation detail performance mechanism for the implementer of the data structure.

A (33:12)

So it looks like a linked list and it looks referentially transparent, but under the hood there's actually a bunch of memory and that it's being mutated. So why?

B (33:26)

Well, mainly for performance reasons. Like vector in Scala is like this. So it's a purely functional data structure that you can't mutate in place. But under the hood it's doing all kinds of tricks using regular arrays in order to make it fast.

A (33:50)

Makes sense. Because the performance. Well, let's dig in on the performance. So I guess there's implied with that is that there's some performance implications to this functional programming style, that this lack of mutation has a cost, I guess.

B (34:15)

Well, in the case of the linked list, the performance implication is just inherent in the nature of that data structure. So if you want to ask for the last element of a Linked list, you have to have a pointer to the last element, or you have to traverse from the head of the list. They have to go all the way to the end. And that will take time, which is proportional to the length of the list. And so if you can have a structure that you have random access to, like an array, that's going to be much faster. But your question is sort of in general whether there are. The question is whether there are performance implications with functional programming in general.

A (35:10)

Yeah.

B (35:14)

I don't think that's inherent, but I think with a lot of languages there are implications depending on how you do things. For instance, in Java and Scala, a function is an object on the heap. And so if you use a lot of functions, you're going to generate a lot of garbage, and that garbage has to be collected. Another thing is that a function call is going to occupy space on your stack. And so if you have a long chain of function calls, you might run out of stack and you're going to get a stack overflow exception.

A (35:59)

So how does that work with recursion? If we're talking about our fold previously and it's using some sort of recursive construct internally to map over a list, how do we deal with stack space there?

B (36:19)

Well, so what Scala does, it will do a tail call elimination. So it will turn your recursion into a while loop. So that's what the compiler will basically unroll your fold into a while loop. It can't always do this if you are making a call that's to a function. So if your function is calling something other than itself, Scala can't figure out that that's going to be a tail call. So a tail call, for those who don't know, is a call out of the function, which is the last step of that function. So there's no further work to be done after that call. So there's no need to return to the body of that function. So there's no need for a call stack to the stack frame to exist. And so what a lot of languages do is that they will eliminate stuff stack frames, if they're not necessary. But languages like Java don't do this, and Scala does this only in very specific cases. And so what you got to do is use clever tricks. Like in Scala you have to use a trampoline, which is a data structure that allows you to make recursive calls and then sort of bounce back on a trampoline. Basically all of the recursion happens in a single loop that is outside of your Program.

A (38:16)

So functional programming, as we discussed it here, it's a constraint on how we write software. So a pure function can necessarily do less than an impure function. So why would we constrain ourselves to a subset of the possible ways of writing software?

B (38:40)

Well, you know, because constraints liberate, man.

A (38:44)

Could you expand on that?

B (38:47)

Yeah, well, so the fact that they can do less, that fact means that you can reason more about what they're going to do. So the smaller the set of possibilities that the functions might potentially do, the more you're going to be able to reason about what they will actually do. And I think that's tremendously important. If you're going to be building a large system at every level, you want to be able to reason and to sort of get your head around and to write software about tests and things like that, what the system is going to be doing. And if you constrain that space, you're going to have a lot less work to do.

A (39:49)

So it's easier to reason about a function because what I know it does is constrained to this specific use case. Is that the idea? Or.

B (40:01)

Yeah. So if you think about a procedure that could have a side effect. Right. Versus a function. So understanding what a function does is very simple. It takes an argument and it returns a value. And you can, you know, it's guaranteed it will always just only do this. Whereas if you have a procedure that might have a side effect, it could do literally anything. Like it could, you know, mutate some memory somewhere. It might throw an exception, and these are the small cases. Or it could take down your whole system and erase all your hard drives and destroy a small country. You just don't know what it's going to do unless you read the source code and fully understood it.

A (40:57)

So you're arguing that in general constraints are good, is that right?

B (41:04)

Yeah, well, I mean, I think it depends. We should not forget the constraints constrain. Right. But in general, you want to impose constraints that sort of serve you, that constrain you to some space where you actually want to be.

A (41:33)

So you had mentioned in a talk relating to constraints, I think about the. How abstraction and precision are related. Could you expand on that?

B (41:49)

Yeah. I say that abstraction is what makes precision possible. A common mistake that people make that abstraction is about being vague, that it's about sort of omitting information, or that it's about sort of sweeping things under the rug, if you will, but it's not. Abstraction is really about going to a higher semantic level where we can talk, we can Talk in a language where we can be absolutely precise about the things that we want to be talking about. A sort of trivial example of where abstraction makes precision possible is if you consider the function that just takes its argument and returns it. So this is the identity function. So think of this as a function from integers to integers. If you look at the type signature of this, it's not very constrained, so it could be doing anything. It could be multiplying your integer by 4, it could be adding to, or whatever. It could always just return zero. So you don't really know what it's going to do. It's very unconstrained. But now if you introduce an abstraction, if you say, well, this is going to be polymorphic in the type, so the type is going to be A to A for any type A. So now I've abstracted out the type of, and I say the caller is going to supply the type A, and then they're also going to supply a value of that type, and then I'm going to return a value of that same type. Now, there's only one implementation of this function, so this function has to return exactly its argument because it doesn't know about any other values of that type, and it doesn't know what the type is going to be until it sees that value. So this abstraction creates this very precise specification of this function.

A (44:22)

Because it's generic, because it's abstract over the type, we know precisely what the definition of it could be because there's only one possible. There's only one possible result that could be that function, the identity.

B (44:41)

Right. Think about how the fact that you're abstracting creates that precision. The fact that it could be absolutely any type means that the space of implementations shrinks down to just one, because the implementation actually is now unable to look at what the value is.

A (45:14)

That's a great example. So, switching gears, your book, Functional Programming in Scala. I have the book here. I've gone, I've been working on it in a while. I really love the book. The thing that has me not finishing it so far is actually the thing I love about it, which is that it's full of exercises that really kind of drill the concept into you. What brought you to that idea when writing this book?

B (45:49)

Well, when. So when Paul and I were training our coworkers to do purely functional programming, we found that there were sort of a handful of people that were sort of clocked in and that were kind of like doing the work on their own and trying to figure things out and really Making functional programming a part of their own daily work. And then there were people that would just sort of show up and watch the lecture, that they would show up every week just like everyone else, but they learned significantly less to use functional programming in their daily work. And so what we sort of concluded was that, and this was consistent with our prior experience, was that in order to really learn something, you have to make it a part of your work. You have to play around with it. You have to experience it for yourself. And so that led us to the idea of having a book that you don't just read. It's a book that you do the book that you work through and gain practice with functional programming.

A (47:19)

I think it works very well. Like myself, I found the exercises can actually be tackled with pencil and paper, but are very effective at drilling this concept in. Is that just. Is the pencil and paper aspect of it? Is that. Is that. Is that intentional? Or is it just the nature of learning about functional programming? And it's very mechanical.

B (47:50)

I think it's. Yeah, it's just in the nature of things. It's not really intentional. Although when I was learning Haskell, I went through a book by Paul Hudak, which was amazing, and I could do most of the exercises just in a notebook with pencil and paper. But I think it's just in the nature of things that functional programming doesn't actually require a computer because it's just purely pure. You can execute functions just in your head because they're so simple. You don't need, like an IO subsystem. You don't need an operating system. You don't need any of this complicated stuff in order to evaluate a function. You're just doing mathematics, essentially.

A (48:47)

Because you can substitute. You can do the model of evaluation in your head.

B (48:53)

Yeah, you can do sort of. You only have to hold one step in your head at a time, so you can just do the evaluation. You know, you write out the next step on the piece of paper, just like you're writing out a proof in mathematics.

A (49:10)

If all new software were written, you know, using the principles of functional programming, if everybody bought your book, worked through it, or learned about the style in some other way, what would the software industry look like five, ten years from now?

B (49:28)

I don't know. That's hard to say. I mean, I think we'd all be a lot better off because we would. I think we would all have software that we have an easier time understanding. We'd have libraries that would be easier to pick up and maintain. We probably also have better software compatibility because, you know, we'd be able to compose software that wasn't necessarily written to be used together. Because often the problem with a particular system is that it's. It's doing some kind of side effect that isn't appropriate in a different context. But with pure functions, you can always kind of snap them together. So I think we'd have a much more sort of mix and match economy.

A (50:31)

Better composition, for sure, because everything would be declaring its inputs and outputs.

B (50:38)

Yeah, exactly.

A (50:43)

I need to be conscious of your time, so thank you for coming on the show, Renar. It's been great. And I love your book.

B (50:52)

Oh, thanks, man.