0
$\begingroup$

Currently there are two things that may change between invocations of a function: the return value, and the external states. I understand that if the external states changes, the function is not idempotent. However, it seems controversial whether the return value is required to stay the same. For example, is the below function idempotent?

int foo = 1; // global
int bar() {
    int ret_val = foo;
    foo = 5;
    return ret_val; // 1, 5, 5, 5...
}

Or is there consensus over this?

$\endgroup$
  • $\begingroup$ Idempotence is a property of functions in mathematics. Are you asking about that or something else? Where do you see this "controversy", what are your sources? $\endgroup$ – Raphael Dec 20 '17 at 15:45
  • $\begingroup$ @Raphael I didn't mean that there is controversy about the definition of idempotence in mathematics. However, when this concept is introduced to computer science, there seems to be different analogy of "function composition". Some claims func_a(func_b(1)) (formal function composition), other claims func_a(); func_b(); (consecutive instruction), even two consecutive HTTP request. I thought the imperative-programming would explain better... $\endgroup$ – Franklin Yu Dec 20 '17 at 20:24
  • $\begingroup$ Depending on the kind of (formal) semantics you use, the two may be the same. Don't make the mistake to reason on syntax; apply semantics first. $\endgroup$ – Raphael Dec 20 '17 at 20:49
  • $\begingroup$ @Raphael So next time I say "this function is idempotent", it's better to say "it's idempotent in the sense that..."? Or it would be language specific? (Then how about in C where both syntax seems viable?) $\endgroup$ – Franklin Yu Dec 20 '17 at 20:52
  • $\begingroup$ No idea, honestly. As long as you define what you mean at some point, no problem. $\endgroup$ – Raphael Dec 20 '17 at 21:32
2
$\begingroup$

There are two related concepts called "idempotence" in programming. One is the mathematical one that quicksort and Raphael talk about. Namely, given a mathematical function $f$, $f$ is idempotent if $f(f(x))=f(x)$. Or more algebraically, $f\circ f = f$.

The other notion that's common in practice and particularly for distributed computations is if an identical "request" is made multiple times, the system will behave as if it was made once. For example, an HTTP PUT is supposed to be an idempotent request so that it can be transparently repeated in case it's suspected that an earlier request was lost. This sense of idempotence is important in distributed computing because it turns at-least-once semantics into effectively exactly-once semantics.

The second notion cast into the context of an imperative language would correspond to the property of a procedure or method that calling it once is the same as calling it arbitrarily many times with the same arguments (assuming no intervening related procedures/methods are called).

The second notion can be related to the mathematical notion by viewing the request/procedure/method as performing a function on the state of the system (taken broadly). An idempotent request/procedure/method, corresponds to an idempotent function on the system state.

Arguably, the response to an idempotent request should be the same on every request. In practice, the responses tend to be informational and so potentially non-deterministic (often due to the concurrency inherent in distributed computing), that you have no real guarantee of any response. For example, the MDN page I linked discusses the case of HTTP DELETE. A HTTP DELETE may return a 200 status code after successfully deleting a resource and then a 404 for future HTTP DELETE requests. But the non-determinism of networking means that making two identical DELETE requests could produce any of two 200 responses, two 404 response, a 200 response followed by a 404, or a 404 followed by a 200 response. (And, of course, many other possibilities such as a 503 response or no response.) The upshot is that your DELETE request could get a 404 response even when you expected a 200 response for a variety of reasons and thus, since the 404 response means the resource wasn't there at the time the request was processed*, you should treat that as just as good as having gotten a 200 response.

If the semantics of your procedure/method are: "on these arguments, do this, then non-deterministically return one of this set of responses", then the procedure/method is free to return different responses (from that set of responses) even when called multiple times with the same arguments. I would consider such a procedure idempotent assuming the "do this" part was idempotent. On the other hand, if the semantics of your procedure/method are: "on these arguments, do this, then if it is the first time this procedure was called return X else return Y", then I would not consider the procedure/method idempotent.

* Of course, someone could have added it back between the time the 404 was generated and the time you received it.

$\endgroup$
  • $\begingroup$ "The other notion that's common in practice and particularly for distributed computations is if an identical "request" is made multiple times, the system will behave as if it was made once." -- isn't that exactly the same? The message/operation/request is $f$, and the system state is $x$. $\endgroup$ – Raphael Dec 20 '17 at 19:08
  • 1
    $\begingroup$ @Raphael I explicitly mention that relation in the answer, but it's not quite the same. First, the "system state" may be something quite abstract. Second, and related to the first, an idempotent operation is usually not allowed to do any (externally visible, semantically relevant) I/O. For example, my bank balance is arguably not part of Amazon's "system state", but Amazon shouldn't make duplicate credit card charges due to duplicated requests! $\endgroup$ – Derek Elkins Dec 20 '17 at 19:11
  • $\begingroup$ For the OP, I'm not really aware of an "controversy" about this. I can imagine specific individuals getting hung up because they (and many others) don't clearly distinguish between an operations specified behavior and its implemented behavior. $\endgroup$ – Derek Elkins Dec 20 '17 at 19:12
  • 1
    $\begingroup$ @Raphael Going the other way, I doubt many mathematicians would view void DeletePost(int id) as representative of an idempotent function (or a mathematical function at all). It's not even an endofunction. In fact, even if you add an implicit "state" input and output, it's still not an endofunction, but more like $A\times S\to S$. So it wouldn't be idempotent in the simplest mathematical sense, though you could presumably formulate a notion of "idempotent in an argument". If DeletePost did return something, it just fits even less. $\endgroup$ – Derek Elkins Dec 20 '17 at 19:26
  • $\begingroup$ This is long and let me read through it. Actually the DELETE in HTTP is exactly the reason why I raised this question as a more general case. As for controversy, at least there are different opinions about what DELETEshould return, right? $\endgroup$ – Franklin Yu Dec 20 '17 at 20:18
1
$\begingroup$

Idempotence is a concept that applies to mathematical functions. Since functions in imperative programming languages can have side effects, the concept is not well defined.

In programming languages that allow to define functions without side effects (such as purely functional languages), the definition is exactly the same as the mathematical one, i.e. $f$ is idempotent if and only if $f(f(x)) = f(x)$.

$\endgroup$
  • $\begingroup$ ... for all $x$. $\endgroup$ – Raphael Dec 20 '17 at 19:07
  • $\begingroup$ Yes, I can see consensus about idempotence in pure mathematical function, as well as strict functional programming languages like Haskell. AFAIK the controversy mainly lies in imperative languages, and that't why I tagged the question with imperative-programming. $\endgroup$ – Franklin Yu Dec 20 '17 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.