Why do functional programmers focus on time?

It turns out that in distributed and parallel systems, time plays a huge role. I think that's why fp is booming these days: all web sites are distributed systems. And web developers are facing all the irreducible problems of distributed systems, and they're turning to fp for answers.

Transcript

Eric Normand: Why do functional programmers focus so much on time? Hi, my name is Eric Normand and these are my thoughts on functional programming.

We talked about the different sources of complexity and software. One of the major sources of complexity is it has to do with different possible histories.

When you have, let's say, two threads running on a single CPU — this is a very simple case — these threads don't actually run at the same time. There's only room in the CPU for one operation to happen at a time.

What we talk about is that the operations in the threads can interleave, meaning the thread scheduler is going to let one of them run a little bit, one thread.

Then it's going to switch to the other thread and let that one run a little bit, and then switch back and forth between them. You don't know when that switch is going to happen. Every time you run it, it's probably going to be different.

Where the complexity comes from is that you don't know what the next instruction is going to be executed. It could be the one from this thread. It could be the one next from this thread.

Then of course, if you have a lot of threads that the threads run for a really long time, that if you had to calculate how many possible ways could this run, then you get this really big number because it's a combinatorial explosion.

As an example, if you have two threads — very small case — and each thread has 12 actions that it runs, the number of interleavings is already at a million. 12 instructions is a very short program that does almost nothing.

Our programs that we write in higher level languages are going to have so many interleavings, millions, billions, trillions of possible interleavings. It's really hard to tell what is going to happen next. There's no controlling it.

Once you let the cat out of the bag with threads, that's just the problem you face. There's nothing you can do to push that back into the box.

What you can do is start to manage it. Manage it more cognitively by reducing that number of possible histories using some kind of concurrency things. Now, I've been talking about threads as an example, but it happens with other things too. It's not just about threads.

JavaScript famously only has one thread. The same problems happen to it because once you introduce async callbacks, you now have this same problem.

Imagine you make two AJAX requests one after the other. Which one comes back first? You can't know. There's no way to know, there's no way to control it. The callback or the promise or whatever for that, for those AJAX requests are going to get called in different orders. Different depending on like how long those requests took to process.

You're just introducing the same problem of, "I don't know what's going to happen next, and I have to think about all the possible ways that it could happen next." There's four actions that could happen after this one. In fact, it also has the same property that it's a combinatorial explosion.

To unify all these ideas of threads — of first. Let me take a step back. The things that do have this same property of exploding number of possible things next are threads, asynchronous operations, so you think of a callback chain. Any kind of promise like a linear promise chain or an async nested callbacks. All of those are creating timelines.

Two processes running on the same machine, if they communicate or share anything you're going to have this problem. None includes the Web server talking to the database.

Anytime you have multiple machines in your system. That's like every Web application that uses any JavaScript. Even if you don't use JavaScript, you have this problem because the browser is still handling stuff for you.

You have the Web server and then a whole bunch of clients open at the same time on the web page. Even if they're not doing JavaScript, you still have the user clicking different links or posting forums at different times that you can't control.

On the server, you don't know what the next request that's going to come in is. Is it for this user, for that user? It's the same problem. This is the world we live in today. It's a world where we have to start thinking about time. I'm talking about Einsteinian relativity.

You have a web page open, I have a web page open, same page. I click a button at the same time on the wall clock as you click the button. To me, to my browser, it looks like I clicked it first because I clicked it before I got the message that your thing was clicked. You clicked yours before you got the message that I had clicked it.

You have this problem of, "It looks like I was first until you. It looks like you were first." Same as in relativity, if you're looking at two different supernovas at the same time, which one happened first? It depends on where you are in space relative to those two supernovas.

This is a problem that we are faced with all the time now. It adds a huge amount of complexity to our software. It's platform tax in complexity. You're on the Web, boom. You've got this problem, which is probably why functional programming is getting more popular now.

We're realizing that the languages we used before were based on the single threading model. They don't have the tools built-in to deal with this. Some of them do to a greater, lesser extent. I'm not saying that you can't use a procedural language on the Web.

I'm just saying that functional programming is getting popular because it has been thinking about these problems. It has been asking these questions for a long time.

Not in a simplistic way, which a lot of languages, let's say like C, the main way that you would do this would to handle concurrency is with locks. Locks just don't work across machines. There's no distributed lock that is reliable, that works well, that you would want to use in a system like this. They don't scale that well. We need better tools.

The whole idea in functional programming is making time a first class concept. It's not a first class value. We talk about functions are first class values. It's a first class concept. We're thinking about time. When I make an AJAX request, I'm thinking, "Is this happening before or after this other thing?"

Does the order matter? Does it matter what the wall clock is when this thing happens? Does it matter what order the things get to the server in? If it does matter, then you need to deploy a lot of tools to make sure it happens at the right time. If it doesn't matter or if you can make it not matter, all the better because. It's one less thing you have to worry about.

In functional programming, what we do is we do this analysis. We talk about time. We figure out what things matter when they happen, if the order is important, if it matters how many times the thing is run.

We deploy tools that functional programmers have in their toolbox. Some of those tools, I'll just quickly talk about them is making something transactional. You have a mutable state. You want a read and a write to be a transaction so that you always see a consistent view of that state.

You can do that in functional programming. You have a mutable thing with transactional semantics for updates.

You can make an action idempotent. You only want to send that email once, but you're afraid that your message to the email send will get sent twice. On the email server you can have it be idempotent, meaning it somehow remembers that, "I already sent that so I'm not going to send it again."

That can be as simple as having a HashMap of the last 24 hours of IDs of emails that got sent. You can guarantee that you won't send it a second time. If it's in that list, it's already been sent.

I want to talk just a little bit about the analysis that can happen. Let's imagine you have two timelines. Let's get visual. We have two timelines and there are certain things we can look at.

One is that if the two things don't share any resources, let's call them. No messages get passed between them. If they don't have any mutable state that they are both reading and writing to, if there isn't some queue that they're both using. Something like that.

If we can eliminate all of those shared things, then the order doesn't matter. They're totally independent. If you can give someone a task that they don't need to talk to anybody, they don't need to wait for anything from anybody, they're not sharing any tools with anybody, they can just run and do it at their own pace.

They don't have to coordinate with anybody, and the order that they do stuff in, meaning compared to someone else's order, it doesn't matter. It's one way to scale up. Like digging a ditch, not only do you need more people digging the ditch, but you need more shovels.

If people have to share shovels, then they're going to have to coordinate a lot. If they don't have to share shovels then they can just work independently. As long as they're not digging in exactly the same spot.

All right. That's one analysis you can do. That's like a vertical cut between the two timelines if we we're looking at them going down like this.

Another thing you can do is a horizontal cut. In JavaScript you would use a promise.all. You're making sure that everything above this line is done before we continue on. Of the stuff above the line you can do the same analysis on, none of that stuff shares, none of the timelines above the line share anything.

Below this line we can do a separate analysis because it's cut. All of this is going to be done before we start the rest. That's just another way of reducing the number of histories that you have to keep in your head. You can now answer the question, what's the next thing that's going to happen?

They're all going to wait here, all these timelines are going to wait here until they're all done, and then the next thing that's going to happen is this. It makes it much easier to reason about.

Another thing we can do, and this is the standard way of explaining what functional programming is, one thing we could do is eliminate the action.

If it's something that depends on time or ordering or anything, just replace it with something like a function, a pure function, a calculation that does not depend on time. Here's an interesting thing. You can look at a calculation like pure function as a timeline that shares nothing with anything else.

It has no shared stuff. It is an action, but it doesn't share anything. If it doesn't share anything, we've already talked about that, it doesn't matter what order it happens in relative to something else. The interleavings all give you the same answer.

Those are three things that we can do. One, eliminate actions, replace them with pure functions, with calculations, with stuff that simply just doesn't share anything. Two, we can isolate two timelines to ensure that they don't share anything, and then we can stop worrying about what order they have it in.

Three is to do a horizontal cut. You say, "When we're analyzing the stuff below the line, we don't have to worry about the stuff above the line." Here's another one that...I'm doing this off the top of my head, I just remembered it. You can do something like transactions.

That's saying if I have two actions in each timeline, timeline A has one and two and timeline B has one and two, there's actually six ways those things can interleave. All of A could happen before all of B, or the A1 could happen and then B1 happen etc. There's all these different ways and they could give you different answers.

Imagine A1 is read a value and then A2 is add 10 to it. You're reading and then adding. You could miss because the read of the B happens before the write of the A, and then you've forgotten that second thing. One thing you can do is put transactions around that.

You're guaranteeing that some of those interleavings are not possible. All the As could happen before all the Bs, or all the Bs could happen before all the As, but you won't have the thing where A starts and then B starts before A is finished. You're eliminating these bad orderings.

You're eliminating histories. It becomes a little bit easier to reason about. You might get different answers because A and B are happening in different orders, you're not guaranteeing that. You are eliminating some of them. This is just a tool to use when you're working, because sometimes the order doesn't matter.

That's another thing. You can use operations or place these actions with operations where the order doesn't matter. If you're counting a bunch of things, the order that the counts happen in shouldn't matter. By the end, when all of them are in, then you'll have the same answer.

Addition, it doesn't matter what order stuff happens in. As long as you wait until the end. This is called eventual consistency.

I'm going to leave it there. The main idea is that functional programmers think about time as a primary idea. They divide the world into things that depend on time and the things that don't depend on time.

They want more stuff in the places that don't depend on time. Stuff that depends on time requires a lot more work, a lot more thinking, and is a lot more error-prone.

All right, my name is Eric Normand. This has been a thought on functional programming. Please follow me on Twitter. I love to tweet out ideas about functional programming. If you're into that, I'm @ericnormand. You can also reach me via email at eric@lispcast.com.

I love to get into discussions so ask me your questions, tell me your thoughts, what are you working on, that kind of thing. All right, see you later. Bye.