Is there always a way to implement an algorithm without mutable state?
It’s tempting to use mutable state in your algorithm. It’s so convenient! And we’re so used to it, if we come from an imperative paradigm. But we must remember that there is always a way, even if it’s not immediately obvious. I go over two ways to implement an algorithm without mutable state.
Transcript
Eric Normand: Is there always a way to design and implement an algorithm without mutation? Hi, my name is Eric Normand. These are my thoughts on functional programming.
I’ve seen this before where there’s some algorithm that seems like, “No, this one just needs mutation.” That’s the whole point of it is that things change over time. We need to have mutation.
I always challenge that because once you let in mutation, it’s really hard to get rid of it. It’s really hard to make it functional on top of that. Unimpossible, but if you’ve got mutation in the core of your abstraction, it’s really hard.
You get all the problems of mutation, and then you’re not using functional programming anymore. You’re just all doing actions. Reading and writing from a mutable thing. The thing is it is always possible.
We know this theoretically, mathematically proven that it is possible to convert any Turing machine into a lambda calculus representation. You could consider the Turing machine the immutable version of algorithm.
If you’re using mutation, you’re in that side, you’re in that camp. Then the immutable more functional version is the lambda calculus. We know that they’re equivalent. Anything you can calculate with the Turing machine, you can calculate with lambda calculus.
The question then is about how to do it. I do think the first step is believing it can be done. If you’ve already made the decision that it has to [inaudible 2:28] be with mutation, you’ve lost the battle. Your mind is not going to go there and even look for the solution without mutation.
I think that is always the first step, it’s just trust that there is a way to do it and that you can find it. That’s the mental part of it. When we’re making transitions from one paradigm to another, that’s the kind of leap of faith you have to make.
You’ll eventually get used to thinking in the functional paradigm, and it won’t be a leap anymore. You’ll know that it will be possible. The second thing is you need to think of two…There’s two different approaches when you’ve got a problem like this, where you think, “I need mutation.” The first is, can you pass this state around? Meaning, it’s not mutable values.
The current state is passed in as an argument, and the next state is returned as the return value. Then you just thread it through. There’s always a possibility. You’re not mutating anything. You’re threading stuff through.
Then you can take a step back and you say, “Well, I actually am not threading any functions through. I have something else that’s threading that value through different functions, so I could have it in a loop,” for instance.
The current state is stored in the local variable in the loop, and then you recur. You do a loop recur. The recursion, if you’re not using Clojure, if it’s just standard recursion, you change the value of that as you recurse.
You’re not changing anything. That function is calling itself with the next value. That’s the same thing as threading. It’s just happening on the outside.
The other thing is often what people use mutable state for or shared mutable state is, a decision in this part of the code is going to affect this part of the code. I could say something like, “I’m gonna set an option here in this part of the code, and that’s going to make this thing, which isn’t running yet, do something else.”
A simple example is if you’ve got a wizard, a step-by-step process, and the first step gets presented to the user. They make some options. They say, “I want to file my taxes jointly with my spouse.” You click that.
Then the next step is going to change based on what you chose in that step. We’re going to give you this workflow, because you said you want to file jointly. It seems like I’m making a decision here. I’m setting an option. It’s mutable. Now, that is going to change what happens next.
That other screen is going to have to read that value, which just got set, and change the UI for that. Here’s the thing, you could potentially solve that with threading the value through, but you could also do it where…Let me back up.
Because you’re threading, the challenge though is that the decision has to be reified. This is that second technique that I’m trying to get at. If you have an if statement, when I click this button that says, “I wanna file jointly,” I could think of it as, “OK. Now, that means the next step needs to be…”
I have an if statement that says, if it’s jointly, set the next step to the jointly workflow. If it’s single, the [inaudible 7:35] branch set it to the single workflow. It seems mutable. You’re making a decision here. The if statement, you’re making it here, and it’s going to affect something over here.
If you reify that decision, that if statement, into a function so the function takes the value that you’re threading through, that function can return the next step. This is a pure function. It’s a calculation.
It takes the current state which contains the option that you set that got threaded through, so no mutation. It makes a decision. What is the next step to show? It’s that same if statement, but you’ve wrapped it in a function. Now it’s a thing that you can put for the next step.
You could have a kind of step in your workflow that is a decision step that has this function that determines the actual next step. You have regular steps and then these decision steps. That’s two cases.
If you do that, you’re still functional. You have not had any mutation in there. You’re still doing all calculations but you’ve still solved the problem of having this piece of the code or some decision on this side affecting decision. You just moved the decision, reified it up, and you’re good.
These are two techniques that happen. Here’s the thing about threading state. If you’re into this, threading state is a pattern. In a language like Haskell, they would call that the state monad.
That state gets threaded through for you as part of the binding rules for the monad. If you bind two state monad values together, this one can change the state, and then this one can read it. It can read that change.
Any monad or any other values that come after it can read the state, because it’s basically just threading. You could do it by hand. You don’t have to have a type class system to do that. You could do it by hand, and I’ve done that before. Just think of threading a state through.
This decision thing is just normal for first class. You don’t have an if statement in a first class if statement. Many languages don’t. JavaScript doesn’t. Clojure doesn’t. Does Haskell? Maybe it does. I don’t know. I don’t think it does. If it does, great, use it. If not, you can make it. It’s really easy.
It’s a function that takes a Boolean and it returns either the second argument or the third argument. You can make one that’s more tailored just for this decision that you’re making, which is to take the current state.
Have an if statement in there that determines which one to do, and it just does whatever you’re supposed to do to make a step happen. There you go. You’ve reified it.
That was this thought. I’ve encountered that before where people give up and say, “This has to be mutable. We’re changing things. The workflow changes as you make decisions.” It does not have to be that way.
My name is Eric Normand. This has been my thought on functional programming. If you’ve had an algorithm that you’ve had trouble making functional, please get in touch with me. I’d love to see it. I’d love to help you out with it. Maybe there’s something else to glean from it.
I’ve broke this down into two little microskills you need to use to try out how to do this. There could be more skills to use that you would need. I’d love to see some examples to expand this out.
When I have these thoughts, they’re really just all about finding other people who could use these thoughts, helping others, getting in touch with people who are also doing the same thing, trying to make functional programming more practical, more accessible to people.
If you’re one of those people, if you got a question, if you want to just get in touch, you can find me on LinkedIn, just search for Eric Normand and Clojure. I’m the first one. I should be. You can also get in touch with me on Twitter, I’m @ericnormand, and via email at eric@lispcast.com.
See you later.
The post Is there always a way to implement an algorithm without mutable state? appeared first on LispCast.