Idempotence versus Referential Transparency
There is a lot of misunderstanding about the difference between idempotence and referential transparency. My plan here, is to explain the key differences without going into any specific detail about either concept. I plan to write something about referential transparency in the future and when I do, I will refer here to dispel any myths regarding idempotence.
I will assume that my reader is roughly familiar with the concept of referential transparency, but not necessarily its implications (since there are many), even though some clearly demonstrate a lack of understanding of this concept, strangely accusing others of same (go figure?) and even trying to proclaim that Java has higher-kinds while suggesting that others do not understand Java’s (mediocre) type system. Ignorance is bliss and all that, anyway on with the story…
Here is a fact; all idempotent functions are also referentially transparent, but not necessarily the other way around. Let us express this fact by other means; a referentially transparent function is not necessarily idempotent, because it is (only) possibly idempotent.
Idempotence can be easily written as follows. A function (f) is idempotent if the following property holds:
f o f = f
That’s all there is to it. Since many of my audience are Java programmers, I will appeal to their potential misunderstanding here and elaborate. The o symbol means function composition. The statement can be read as “the function f composed with the function f is equivalent to (just) f”.
Function composition comes about by… well composing functions. Suppose a function (f) that accepts a type Y and returns a type Z and another function (g) that accepts a type X and a type Y that returns another function that accepts a type X and returns a type Z. We express this as f o g.
Here is an example in the favourite programming language of some:
class Foo { static String f(int i) { return Integer.toString(i); } static int g(char c) { return c + 7; } static String composeFG(char c) { return f(g(c)); } }
Easy Peasey right? In my statement above, the type X is char, Y is int and Z is String. Function composition is written in Java as f(g(a)). Back to the definition of idempotence, which states (in Java syntax), that f(f(a)) is equivalent to f(a). Clearly we see that f must at least have the same type in its argument and return type in order to satisfy idempotence. This means that our previous example has no idempotent functions, however, they were all referentially transparent. Furthermore, a function that is referentially transparent and having the same type in its argument and return type is not necessarily idempotent. A counter-example is easily produced:
class Bar { static int add1(int i) { return i + 1; } }
Since there exists at least one (in fact, all in this case) arg for add1(add1(arg)) such that it is not equivalent to add1(arg), then add1 is not idempotent. For example, add1(add1(7)) is not equivalent to add1(7), clearly.
Here are some insights. Adhering with my naming convention, suppose the function add0. Guess what? It is idempotent. Also, multiply1 is idempotent. Every single function on this web page is referentially transparent, but only the two aforementioned hypothetical functions are idempotent.
We might write this using logic as follows for add0
∀ n | n ∈ Z. n + 0 = n
For all n such that n is an element of the set of integers, n + 0 = n [is a true statement].
…and for multiply1
∀ n | n ∈ Z. n * 1 = n
For all n such that n is an element of the set of integers, n * 1 = n [is a true statement].
For completeness, here is an actual idempotent function with the added twist of a polymorphic type parameter (generic parameter in Java speak):
class Baz { static <T> T identity(T t) { return t; } }
I hope this clears some things up 
July 5th, 2007 at 6:52 pm
Both your sample idempotent functions are identity functions, I just wanted to point out that there are other idempotent functions, like abs.
July 6th, 2007 at 8:24 am
Thanks augustss.
I considered making this note, but I wanted to keep it simple for the intended audience
July 14th, 2007 at 2:09 am
I take it the date function is not idempotent? Even though it has no side effects and its return value is independent of how many times it was called before?
July 20th, 2007 at 8:00 pm
You also need to consider a more general notion of idempotence, which is probably what some people are thinking of. Sure, you have the mathematical definition, f = f o f. But you also have the notion which is quite important in distributed programming: if a call a function, method, web-service, etc multiple times with the same arguements, then I get the same result. See the bottom of http://en.wikipedia.org/wiki/Idempotence for example.
I do agree that referential transparency and idempotence (either definition) are different. Your argument probably should have considered both definitions of idempotence, as that is where the confusion lies.
Furthermore, using the words necessarily and possibly does not mean you are using modal logic.
July 26th, 2007 at 3:13 pm
More interesting examples are such things as stable sorting functions and their ilk.
As for Dave’s point, these functions are (close to, exempting error conditions) idempotent, but have “hidden parameters”—such as the state of the network. The same goes for IntendedAudience’s example—where the hidden parameter is the current time.
These hidden parameters can be made explicit in a functional programming language such as Haskell, where they form part of a structure such as a monad.
August 6th, 2008 at 2:08 pm
I realize that your main point is that
“referentially transparent” does not entail “idempotent”
but the converse does not hold either, for several common meanings of “idempotent”,
“idempotent” does not entail “referentially transparent”
What are your definitions of “idempotent” and “referentially transparent”?
My definitions:
Mathematically idempotent: f(f(x) == f(x)
Computationally idempotent: f() leaves same system state as {f(); f()}
Referentially transparent: f(x) == f(x)
Assuming some sort of non-referentially transparent random() function, here is a mathematically idempotent function that is not referentially transparent, in pseudocode:
Definitions:
function f(x) := if (x == 0) then { if random() then {return 1} else {return 2}} else {return x}
var y_0 := f(0)
var y_n := f(n)
F is idempotent:
f(y_0) == y_0 // always true, but y_0 could be either 1 or 2 each time the program runs.
f(y_n) == y_n == n // always true, for any n != 0
but not referentially transparent:
f(0) == f(0) — maybe, maybe not.
Here’s a computationally idempotent function that is not referentially transparent:
var x := 0;
function f := {y := x; x := 1 ; return y; }
//Startup Virtual Machine
f(); // returns 0, x is now 1
f(); // returns 1, but no state change: x is still 1
August 6th, 2008 at 2:14 pm
If you use a “strong computational idempotency” that also requires a consistent return value, which I guess is what many folks do use, then idempotency does imply transparency.
Strongly Computationally idempotent: y:= f() leaves same system state as {f(); y:= f()}, particularly, both set the same value of y.
Under this defintion, computational idempotency entails referential transparency:
Experiment 1:
Startup Virtual Machine:
var y_0 := f();
Experiment 2:
Startup Virtual Machine:
var y_0 := f();
var y_1 := f();
By Idempotency: y_0 == y_1, which proves Referential Transparency.
August 8th, 2008 at 8:14 am
Does a “result” always have to be a return value? For example I have applied idempotence in a batch process where the system will NOT reprocess transactions it has already processed. So resubmitting a halted batch will not process transaction that have already processed, it will leave the state of those exactly as they were and continue processing when it reaches a transaction that has NOT previously been processed. This makes troubleshooting a batch really easy, but is it real idempotence?