I think it's much more common to talk about idempotence in programming w.r.t. state and state transitions. With immutable data, this approaches the mathematical definition:
(= (remove-el set 1) (remove-el (remove-el set 1) 1))
With network protocols, state machines, and mutable data, idempotence helps ensure consistent state without the fixed-point-ness.
Idempotence is usually used when talking about effectful code. Modeling the state as part of the input/output seems to run counter to that purpose, because that's how you create a pure model of an effectful program. It's useful to talk about idempotence when running the function zero times is different than running it once, which is hard to do in that framing. As you say, "on the same input" is difficult to reconcile if the state is part of the input.
If we consider the state to be part of the input, then it's easier to say that when f(x) = y, then f(y) = y as well. In other words, f(f(x)) = f(x). Which, as it just so happens, is literally the mathematical definition of idempotence which the programming concept is based on.
In any case, this still gets to the same overall conclusion: the point is to arrive at a specific destination, not to move towards it. That shift of perspective is helpful in framing problems towards an idempotent solution.
Okay, I understand that the formal definition of "idempotent" is different than what the author means. What is the correct term to use in this case?
Edit: Next paragraph says:
This is a very useful property in many situations, as it means that an operation can
be repeated or retried as often as necessary without causing unintended effects.
With non-idempotent operations, the algorithm may have to keep track of whether the
operation was already performed or not.
"A change in state" would be an unintended effect I think.
Idempotence is a desirable property of systems whereby repeating an action has no effect. Mathematically, an operator is idempotent if f(f(x)) = f(x).
Idempotence is handy because it implies that one can retry safely if one isn't sure whether something succeeded or failed. Not sure if your file was saved? Save again! If it was indeed saved, the file continues to be saved. If the file was not saved, it is now. Yay.
I would kill for such descriptions of every system I work with.
Not to mention idempotent code is trivially memoized, allowing you to skip computations you couldn't previously reason about. A function that produces a value is always comparable to another value — a function that modifies some state requires that you have a way to observe that the world changed in order to skip doing it again.
I was trying to respond specifically to didibus's obvious misunderstanding: they thought an increment function might be designed to be idempotent. That doesn't make any sense, whether you know the CS meaning of idempotence or not.
One significant issue here is the question of a priori vs. a posteriori properties. When thinking algebraically about software, it's often a case of defining things in an a priori way in order to get the right laws to apply to operations. Idempotence is one such law.
The other angle on this is the a posteriori angle, where you note that something behaves a certain way and use an appropriate word to describe that behaviour.
My reading of didibus's comment was that it was basically about imperative programming, and that there was some confusion around the situations in which the concept of idempotence applies (incrementing a variable isn't one of them).
I think you are trying to introduce the State monad and the technique of modelling a stateful program by chaining pure functions. That's fine, but it does introduce a level of complication that is not implied by a straightforward comparison of memoized functional vs. idempotent imperative code.
In general, an idempotent method is a method such that calling it one time is the same as calling it n times in a row for any n > 1. However, idempotency doesn't require that calling the method one time is the same as calling it zero times, although such a method isn't excluded from the definition either. So a stateless method is necessarily idempotent, but an idempotent method isn't necessarily stateless.
Author here. State is not immutable, it is mutate-in-place via atomic swap. That makes it somewhat different than both functional programming and imperative programming, but it's not an excessively difficult programming style to use in practice.
Sure, one little hobby horse, e.g. "inversion of control" can run amok to negative effect (looking at you, Java projects with object traces 75 layers deep) but that doesn't make idempotency or inversion of control into bad ideas.
A bit of pragmatism goes a long way, like Python's odd
Either I'm completely misunderstanding your grammar, or you don't understand what idempotent means... idempotent and state-changing are almost opposites.
Immutable state, functional programming, etc, is not about eliminating state, its about isolating it and carefully managing it.
In a standard-imperative-mutable world, you can never be completely sure that state isn't being modified behind your back, you can never be completely sure that concurrent access is safe, you can never be completely sure how far reaching state changes you make are.
The idea, IMHO, isn't to remove state. All programs need state. All interesting programs need state that changes over time. The "big idea" is that these changes are isolated and managed carefully so that nobody can pull the rug out from under you and change something behind your back or in a way that makes concurrent access unsafe.
Immutable data means that the data you are reading will never change. If you read it again in ten minutes, it will still give you the same value. No other module or thread can change it. Concurrent access is safe too and all reads give the same consistent view.
But even immutable data needs to be updated, so there will always be some mutable state (for example, in Clojure, you might have one or more atoms, which are mutable cells into which you can put immutable data. The data doesn't mutate -- it gets replaced[0]. Only the cell is mutated, but in a carefully managed way. There are other mutable state management primitives too). The programmer cannot accidentally mess up the state, they have to intentionally do it.
So to reiterate: its not about eliminating all mutable state, its about isolating and carefully managing it.
[0] and anyone still holding a reference to the data (not the atom) will continue to see the same data as before, unchanged. That is, if I take the value from the atom, somebody else updating the atom will not change the value I took out of it. This of course introduces things like the dual-writes problem, but Clojure gives me other tools (like refs with STM) to tackle these: ie atoms aren't the right tool for all use cases, just one example I chose.
Like Rust, you keep the truly non-idempotent actions minimal, isolated, and well understood. Then you wrap everything around those models and state changes with idempotent behavior.
As a trivial instance, you can guard a non-idempotent email send event with a database table and idempotency key. When you attempt to send the same message twice, you'll see that you have already done so.
With diligent engineering, this type of thinking can scale to non-trivial active-active concurrent writes and more.
The (somewhat contrived) example is trying to model what happens when the state change is done with I/O (hence by definition asynchronous). Your idea to make the state changes idempotent is a good one, but not typically possible.
that's assignment AND reassignment. Mutable state is fundamental to how computers work no matter how hard the fans of the current fad of functional programming try to deny it.
reply