A Theory of Functional Programming 0004
This is an episode of Thoughts on Functional Programming, a podcast by Eric Normand.
Today, we're going to be talking actions. Now, as counter-intuitive as it may be, functional programming has more to say about actions than it does about data and calculations. At least, more interesting stuff to say.
**Eric Normand**: Hello, my name is Eric Normand. I'm writing a book called "A Theory of Functional Programming." I'm trying to create a unified, cohesive, coherent definition of functional programming as we use it in industry because we have so-called definitions for a more academic view of functional programming, and we don't have much of a literature in industry.
We might have books talking about functional languages, but we don't have the same kind of literature that you have in object-orientated programming, stuff like the design patterns books and things like that, all the OOP principals.
Today, we're going to be talking actions. Now, as counter-intuitive as it may be, functional programming has more to say about actions than it does about data and calculations. At least, more interesting stuff to say.
When you read definitions about functional programming, they all often focus on the pure functions, meaning calculations, how it doesn't have side effects, meaning no actions. I think that what functional programmers do with actions is actually where all the action is. The first thing I want to say is, in functional programming, we treat actions as first class.
An action is a value. What does that mean? It means that you can hold an action. Hold meaning assign it to a variable, pass it as an argument, put it in a data structure, that kind of thing. You can have a handle on that. You can have a handle on a thing that will send an email. It's all configured, it's all ready, and you can invoke it. Boom, and it will send the email.
That is something that you can do in many languages, but it's often not thought of in that way. For instance, you can have a bunch of actions, you put them on a queue, and then you have your workers just pulling them off of the queue and invoking them. They don't even know what it's going to do, those workers.
You can set that up using these ideas in functional programming. You have to have first-class actions. It has to be something that you can invoke without knowing what it's going to do or knowing its interface. The interface has to be uniform across all actions. I think that's another key that I haven't mentioned before.
Often, in object-oriented language, you might have an object that sends emails. You have a method on it called Send, and it takes the To, and the Subject, and the Body as arguments. Yes, that is going to execute an action, but you need to have some object that does that where the arguments are packaged in already.
It's going to have a uniform interface like an invoke method or something, or a run method that it will use so that the thing at the other end of the queue doesn't have to know all about its interface. I think that's an important part of functional programming, that unified interface to actions.
What that would let you do is compose the actions up. You could compose actions up in a sequence. You do action A and then you do action B. You make a new action that first runs A and, when it's done, it runs B, or you can compose actions up in parallel.
If you have an action A and B, you can make a new action that will run A in one thread and B in another thread, run them in parallel. Then, maybe package up the answers and provide it in the current thread when they're all done. Something like that. These are operations where, in general, you can be composing actions up.
What makes an action an action? We've talked about this already. Actions are bound in time. There's two ways that something can be bound in time. First way is, it matters when you invoke the action. When could be reading mutable state. Reading mutable state is an action because, if you read it now, you could get a different answer as if you read it in one second, or if you read it in 20 seconds.
When you read, it matters. It's an action. You could read it after someone has written, or you could read it before someone has written. In this case, the when isn't an absolute time, but a relative time to another action. That writing to mutable state is an action and reading from it is an action.
The reason this is important is because, when you get into multi-threaded programming, parallel programming, or concurrent programming, you often don't have control over the specific order of things happening. You need to be aware of that when you're doing actions in the general case. It matters when you do it.
The other thing that bounds mind something in time is how many times it is run. An example of this is sending an email. It might not matter when you send the email. It might, but it might not. If you send it zero times, that's very different from sending it one time. That's also very different from sending it 100 times. You're spanning someone at that point.
I'll contrast this with adding two numbers or doing some other calculation. It doesn't matter. No one's going to care. No one's going to complain to you that you added this number too many times. No one will know. It never leaves the machine. It's all in memory and it's all boxed up. Those are the two things, when and how many times.
If it matters — either one, or both of those — then it is an action. If it doesn't matter, then it is a calculation or it's data because it can't be evoked at all, is inert. We've talked also about actions being universal. What this means is, you can do everything your computer does with only actions. In fact, that's how it works.
Every instruction that your computer can execute is actually modifying memory. It uses heat. It takes time. You can't just do an addition at any point in time. It matters when you do it. Really, actions are universal, and we've created an illusion where functions are pure, where we fudge. We ignore that things are impure really deep down. I like to think of it like in physics.
If you've ever done a physics problem...It's very common in physics problems. If you've ever taken a physics class where they ignore friction and they ignore air resistance...We all know that there's no such thing as a frictionless surface, and you're always going to have some air resistance.
In many cases, the friction and the air resistance are so negligible compared to the other forces that we ignore it and we get an answer that is close enough.
That is the same kind of attitude that a functional programmer will have to the time it takes to run a calculation or the heat it generates, or whatever other effect it's having, like the electric bill going up because you're running a calculation. Typically, we ignore that. We will talk about cases where you don't ignore that, but those are very rare.
They're actually the exception that shows that this framework really makes a lot of sense. They're universal, which means, if you had to make a system that only had one of these categories, it would be action. You basically write a procedural language, an imperative language, and then you could fake functional stuff from that.
You can fake calculations and you could fake data within that. That is the main benefit of actions. There's another benefit that I think is underappreciated, which is how straightforward actions are. They're basically step-by-step recipes or instructions for the computer to execute. They're procedural, and they just happen one after the other.
Every procedure is made out of sub procedures, and every sub procedure is made out of more sub procedures. It's a very easy way of structuring. It's easy to picture what's happening. It also maps very well to the way the machine works. I think that's a big advantage. You don't have any...
When you get into calculations, and you get into algebraic manipulation, that can get pretty abstract pretty quickly, but that's all I have to say about that. There's an advantage into the straightforwardness of doing everything in actions instead of breaking it down into this way that we do as functional programmers into the actions' calculations of data.
Patterns. Action patterns. This is where functional programming really shines because we care about these things. You can take those two conditions, whether it's when the thing executes or how many times it executes, and you can break it down. If we look at, just real quickly, the easiest one is the number of times something executes.
In the general case, it matters. Every count of the times it is executed matters. If it's zero times, it matters. It's different from one, which is different from two, which is different from three, which is different from four, but, in functional programming, we've found sometimes the zero matters is different from the rest, but all the rest are the same.
This is one of those places where I really think that functional programming is often more intuitive than object-oriented programming, and I'll get to that. That is a whole topic in itself. That's a different chapter. Let's look at a real-world example of an elevator button.
If you want to go wait for the elevator, you want to call the elevator, you press the button, and it lights up. That first press, you press the button that matters. Someone else who walks up and they press the button, or you're in a hurry and you just keep pressing it, it doesn't matter. The elevator has already been called.
It's not counting the number of times you press it, and comes more urgently when you do that. That zero or more, you're dividing the world, or the possible states, into zero or more — zero times pressed versus one or more times pressed. In the calculation world, in mathematical world, it's called idempotence.
That I can execute the same action twice, and it will be like executing it once. I can execute it 100 times, it'll be like executing it once. That once is different from zero times, but the duplicates don't matter. This is really important because, in a system, let's say a distributed system, coordination is expensive.
You're working with your friends, and you don't want to have to ask him, "Hey, did you already do this? Did you already...?" What's an example? Cleaning the windows. It's a silly example. I'm just winging it right now. Cleaning the windows. Cleaning the windows twice, sure it's a waste of time, but it's not going to hurt anything.
The window will be just as clean as it was before. You're not going to clean it any better, let's say. Instead of an expensive call to your friend like, "Hey, did you clean the windows?" and he says, "No." Then you call another friend, "Hey, did you clean the windows?" She says, "No." "Hey, did you clean the windows?" They say no.
You call your 10 friends to find out, should I wipe this down? It's probably better just to do it instead of wasting the time. If you imagine a network of computers and they have a job to do, it would be really convenient if they didn't have to talk. If they could just do what they think needs to be done. Even if the work has already been done, it's not going to hurt anything.
That's called idempotence. It's a thing that we tend to build into our systems. Another one is when you have something like a get request on HTTP. Let's make it even more real world. Peeking into the fridge. You're not going to take anything. You're just looking. Do we have milk?
It's not really going to hurt anything to peek twice or even to peek zero times if you happen to already know that you don't have milk. It has no visible effect. This kind of thing is nice because that means it has no visible effect, meaning zero times is just as good as one time if you already know the answer. You have to already know the answer.
You might find out the answer later some other way, so why do the work of looking in the fridge now? You don't need to until you need to go to the store. You're planning a visit to the store and you're saying, "Well, I might need milk. I might." You're just making a mental note of that.
Instead of looking in the fridge and making sure whether you have milk or not, you just wait because you're not ready to go to the store yet. Then, while you're waiting, your friend comes home with milk, puts it in the fridge. Now you know. [snaps fingers] "I never even had to look in there." Doesn't matter. The fridge doesn't care. Who cares? That is called being lazy.
In the computer, you have this thing called laziness. You can do a lazy read where you might not ever need the answer because it's never going to be used. No one cares because it doesn't affect anything to do the read or not to do the read. It doesn't change anything. If you have no visible effect of doing what you're doing, even though it's an action, you're doing something that's bound in time.
If you look in the fridge after your friend comes home with the milk versus before, you'll get different information about how much milk you have, but it doesn't change anything outside of yourself looking in the fridge to know how much milk. It's a convoluted example, but it's subtly useful.
Something that's a little more useful is there are certain actions that guarantee a single read. We rely on this in the real world a lot more than you think. For instance, if I had a pile of books to put away, and I enlisted my friend to help me put the books on the shelf. I pull a book and I put it on the shelf and I pull a book.
Meanwhile, my friend is pulling a book, putting it on the shelf, pulling a book and putting it on the shelf. We have one stack of books. We're, in essence, using it to co-ordinate what books I put on versus what books they put on. We can both work basically as fast as we can, but we don't have to work at the same speed. We're each working at a separate speed.
It guarantees that the work gets done the fastest. If I took half the books and my friend took half the books, what if I'm faster? Now, his stack will still have books on it when I'm done, and I can't go get them from his stack. Anyway, we're using this single stack, but we're also not duplicating any work.
Whereas, if you had a stack or a queue on a computer, you would have to ensure that, when I pull something off, I'm the only one who pulls it off the queue. When another person pulls off or another thread pulls it off, they're the only one to pull it off. We try to guarantee that property that we have in the real world of a single message on the queue is only going to get read once.
It's an action because, if I read a little bit later, it could be after my friend reads, so I'm going to get a different value, but I'm guaranteeing that, even though the order matters, two reads aren't going to get the same thing.
Let's talk about when. I feel like there are more patterns in the number of times it gets executed that I'm missing. There's actually a lot more in when that I've discovered, that I've cataloged. Discovered, I don't mean that I invented them. I mean I know about them. [laughs] There is so many that I know about that I've written down to tell you about.
The first thing I want to say is the when is typically not about the clock time. It's mostly about the order. It could be about the clock time. If you actually read the clock, it's literally clock time. Usually, what we're talking about is when you're sharing some action. I'm reading, my thread is reading, your thread is reading — concurrently. We're sharing that read.
Functional Programmers have figured out how to coordinate these safely. When I say functional programmers, I don't mean object-oriented programmers don't know this, too. I think there's a lot more focus on this in functional programming. Maybe that's wrong. Maybe I shouldn't even say that. It's about order.
If someone writes and then I read, it's different from me reading and then them writing. I'm going to get a different answer in my read. The first thing that we can do is we can talk about transactional reads and writes. If I have to do a couple operations, I do a read, and then I do a little calculation on whatever I read, and then I write back to it.
It's a bundle of things I do, a few steps, and someone else does a similar thing. They do a few steps. What you don't want is for those steps to get mixed up. What you don't want is for them to interleave. You want to guarantee that one happens before the other. You might not know which one happens first and which one happens second.
You want to make it so it doesn't matter which one happens first and what happens second, but at least things aren't at the same time. It's like a mutex. You want to disallow simultaneous operations.
Blocking reads. This is a thing like in communicating sequential processes or promises. The idea is I need an answer to proceed. I'm having this answer generated in another thread. I need the answer to proceed. I'm just going to block. My thread is going to block. What you're doing — and this is a theme in all of these — you're collapsing the number of states.
You're making a checkpoint in time where it doesn't matter who finishes first, the other thread calculating this answer for me or the other stuff I was doing in my thread. Whoever finishes first, we're going to checkpoint at this time. What you're doing is you're collapsing the number of possible states.
Before, there was one possible configuration where my worker thread finished first and I finished second. There was another possible one where I finished first and the worker thread finished second. The blocking reads and writes like a promise, or communicating sequential processes. It collapses that down into one possible universe.
Let's talk about this idea of collapsing states for a second in the transactional read and write. Before, you had all these possible interleavings. Let's say you don't do anything to control this. I'm doing three operations. My other thread is doing three operations. They can interleave in so many ways. It's exponential how many ways they can interleave.
All my stuff can happen before all of theirs. All of theirs can happen before all mine. Plus, I could insert my operations in any spot in them. There are so many different ways that these things could interleave that it becomes hard to reason about. In fact, you get bugs that only happen rarely, that you can't reproduce because you can't really guarantee the order.
What we're doing is we're collapsing the number of states. Now there's only two states — all of mine before or all of mine after. It's a way of taking this situation that's exploding exponentially and converting it into something that's easy to manage, easy to keep in your head.
I do want to go back to the times. It's the same. We have an elevator button. You don't do any controls on it, so you press the button and it'll call an elevator. I press it five times and it'll call five elevators. [laughs] You don't have any control on it, every single state, every single number of times I could press that button is another possible state of your system.
I pressed it zero times, then I pressed it one, then I pressed it two, then I pressed it three. Each of those might have a different outcome. All the way to a million. All the way to infinity. By making something idempotent, we've turned it into two possible states — unpressed and pressed. We're making the universe of our system that we're writing more manageable.
Same thing for this lazy read that I talked about. I either have the answer or I don't. I might not even need it, which I don't care. Maybe I will, maybe I won't. We've collapsed that. I might not need it, so I'm not going to do it yet.
The single read. I've removed the possibility of both of us grabbing the book at the same time. In a computer — because everything is just copies, and is just digits, just binary — if I put a book on the shelf, my friend puts a book on the shelf at the same time, it's going to be on the shelf twice. We've removed that possibility that one of us is going to get each book.
Let me talk about commutativity. We've already talked about how when is usually about order — that A happens before B, or B happens before A. If I read after you've written, I get a different answer from if I read before you've written, but there are some operations where we can guarantee the order doesn't matter.
This is very interesting because it also reduces...When I say the order doesn't matter, it means it doesn't matter in some particular respect, which is the respect we care about. What's an example in the real word? Let's say we're shoveling rocks or dirt into a hole. Does it matter if I shovel before you or you shovel before me?
No. We just all work as fast as we can and fill the hole, and we're all happy. It doesn't really matter what order stuff happened in. Otherwise, if it did matter, we would have to have some coordination strategy. I'll go, then you go, and I go, then you go. Maybe it matters. All of mine goes first and then all of yours goes first.
That would take a lot of coordination, and you wouldn't be done as fast. It's something that, let's just say, collapses all of the possible states of how things got ordered into a single state, which is that they all got done. We're done. There's no problem. It doesn't matter what order they happened in if you were just doing incrementing.
Every time someone visited your website, you just incremented — increment, increment — like one of those clickers that you see people counting people who go to the county fair. When they enter, click, click, click, click. It doesn't matter what order the people went in. If Sally went before Bob or Bob went before Sally. It's just, click, click, click, click.
That is an example of that, where the order doesn't matter. You'll get the same answer regardless of the order that people go in. There's another case where it's similar, except you don't really care about the exact answer, but you care about...The answer of doing it in one order is exactly equal to the answer doing in another order. You get the exact same value.
If I ask my daughter to fold her clothes and she folds...Let's say she has two things to fold. She folds the shirt, she puts it on this side of the drawer, or in drawer A, in the top drawer. Then she folds the pants, puts them in drawer B. I don't really care if she does this pants first or the shirt first. They're going in different drawers. The result is the same.
I'm just happy that she folded her own clothes. However, if she has four shirts and they need to be stacked in the drawer, let's say, the order does matter. She does the red shirt before the blue shirt. The red shirt's going to go on the bottom. Then the blue shirt's going to go on top. Then the green shirt's going to go on top of that.
If she does it in a different order, they will be stacked in a different order, but I don't care. [laughs] I'm just glad that she's folded all her clothes and that they're in a nice stack. They're not equal in the sense of red, green, blue or blue, green, red. They're not equal, but they are fine. [laughs] They satisfy the work requirements.
That is something that we can look at as a kind of communitivity where it's not communitivity with equality, but communitivity with some kind of other validity function, some other validity predicate. That's what we're doing. We're collapsing the possible states.
We have only one possible...There's two states — not folded and put away, and folded and put away. We're not going to worry about the order. Whether it's in the rainbow order, or whatever other system you could have — Are all the reds together and all the blues together? I just don't care. We want to allow that lack of care in the system because that lets us collapse these states.
If you do care about the order, notice you have a lot more states that it can be in. You can be in the red, green, blue state. You can also be in the blue, green, red state. They're different, and you have to keep track of that. If you don't care, fewer states. Fewer possible states you can be in, folded or not folded.
All right. I'm at 36 minutes. Mash all the buttons. Tell YouTube, and iTunes, and whatever that you do like what you've heard and you want other people to know that it's a good thing. Those AIs eyes are listening. They're waiting. They're going to process your actions into their algorithms and recommend — Yes, do it now. Mash the buttons.
All right, check you later. Bye.