If the sleep time of a function at first time differs from the second time, but the output is the same, is it still a idempotent function?

For example, if the sleep time of a function would change after first execution but the output remains unchanged, e.g.:

public static int myFunction(){
    try {
        Thread.sleep(MyClass.IsCalledBefore?1:1000);
    } catch(Exception e){
    }
    MyClass.IsCalledBefore=true;
    return 0;
}

is still a idempotent function?

This is really a matter of definition, but to me if the execution time matters at all for idempotence then to be most strictly idempotent the second call to the function should take zero or negligible time, to make the following two snippets equivalent.

myFunction();

myFunction();
myFunction();

Idempotence doesn’t mean that the function does the same thing each time it’s called, it means that calling it twice is functionally the same as calling it once.

The function you reference is idempotent. The relevant definition of idempotent is (per Wikipedia):

a subroutine with side effects is idempotent if multiple calls to the subroutine have the same effect on the system state as a single call

Note: that the second definition given does not apply here because it is about functions without side-effects. Also note that in this context, it is not just the result of the function that matters, it’s the resulting state of the system i.e. side-effects.

This meaning of idempotence is defined in terms of ‘state’. The definition of ‘state’ does not include execution times. The state of a system can only be determined at a point in time. If changes in execution time were an aspect of state, techniques such as memoization could not be considered valid in pure functional programming. Expanding the concept of state to include execution times simply muddies the meaning of the term.

That isn’t to say that execution times are not relevant. There are known security implications to changing execution times. Processes with consistent execution times are called ‘constant-time algorithms’. Whether a function (or algorithm) executes in constant time (not to be confused with constant time-complexity) may be related to state changes but it need not be. The execution time of a pure function can be (and usually is) dependent on its inputs.

After thinking about some of the comments on this answer and how they relate to the original question, I think a simpler and more obvious question is: does implementing a cache (or memoization) make a function stateful? Consider HTTP GET. Per the relevant RFC, a GET call is ‘safe’. That means it is not only idempotent but (roughly) that it will not create any side effect at all. One of the advantages of this is that it allows for caching on the client and/or between the client and the client and host server. The main point of caching is to reduce the time of retrieval. But if that change response time is a state change, the call is no longer (strictly) safe. This is inherently a contradiction in terms. If you want to argue (as some have) that HTTP isn’t generic enough, the same argument applies to memoization (basically: internal caching) of pure functions.

Clearly this is depends on magnitude.

For some tasks, a speed difference of one second might be a difference like night and day (or even between life and death). For others it could be totally inconsequential. So whether you model “idempotence” as being affected by this depends on how big the difference is, and on how sensitive to delay your task is.

(I realize that there are sources who define idempotence as not being about execution speed, ever, but surely that is hard to follow in the real world. There’s always a point at which a function becomes so slow as to be effectively unavailable.)

In short

Depending on your definition, either your function is idempotent or no function at all is idempotent.

Some more arguments

Idempotence is about producing the same result even when applied multiple times in a row.

Let’s take an engineering example where the results that matters is obvious. Take an elevator: I can press multiple times the same “floor 3” button, and in the end the operation will always bring me to floor 3, the intended result. Perhaps due to some extrinsic factors it will stop at an other intermediate floor. Maybe it will take more or less time to arrive there depending on the departure floor. The operation “go to level 3” is nevertheless idempotent: should I press it several times in a row, it will still give the same result.

Back to computer science. Of course, it all depends on what you consider to be part of your result space:

If it is only the return value of the function, your function is idempotent.
If timing is an essential part of the expected result, it is not at all idempotent. And even if the time to return would always be identical, because invoking it two time on the row would mean that it already takes twice the time. In fact if you include time in the result space, no function is anymore idempotent, as invoking it several times in a row takes more time, which contradicts your definition (you could at best claim about “allost idempotent” for functions that have a very neglectable curation.

Conclusion

To leave idempotence any useful meaning, the best is therefore to focus on functional results and consider your function as idempotent. Invent another concept for the timing effect, but define it precise enough, as the reasoning shows that it can become easily ambiguous.

Yes, the function itself is idempotent because there are seemingly no additional unintended side-effects when the function is called repeatedly – i.e. final state of the program is the same after calling the function again, and way the function is written seems to suggest that the side-effect of modifying the sleep time is intentional so would likely be expected by the caller (though it is important that the caller should be aware of this).

Related question on StackOverflow: language agnostic – What is an idempotent operation?

Note: others in the thread have pointed out that there is no one ‘true’ definition of idempotence as it depends on context. Given that the question as currently written doesn’t give any clues over the significance of the sleep duration nor the importance of execution time, there is no way from the question to be sure exactly which of the multiple definitions of idempotence the question is asking about.

^{Timing and system clock state are important in context of this question. I therefore reject hypotheticals about mathematical purity.}

If our only concern is inexact system clock which can’t measure 1ms intervals, the the second invocation of the function does nothing making the function idempotent.

However, from a security perspective an additional context switch caused by Thread.sleep() is a major effect. Therefore, for the function to be idempotent in a full sense, it has to eliminate a call to Thread.sleep() from subsequent calls:

    public static int myFunction(){
        try {
            if (!MyClass.IsCalledBefore) {
                Thread.sleep(1000);
            }
        } catch(Exception e){
        }
        MyClass.IsCalledBefore=true;
        return 0;
    }

It depends on what function we’re talking about.

Definition. A function f is idempotent if f(f(x)) = f(x).

Is `f(x) = myFunction()` idempotent?

Yes. Proof:

f always returns 0. Thus, f(f(x)) = f(0) = 0 = f(x).

Is `f((_, world_state)) = (myFunction(), get_world_state())` idempotent?

No. The world_state (which includes the current time) changes. Proof:

Let x = (_, WorldState(time=0)).

Then,

f(f(x))
  = f(f((_, WorldState(time=0))))
  = f((0, WorldState(time=1000)))
  = (0, WorldState(time=1001))

However, this does not equal
(0, WorldState(time=1000)) = f((_, WorldState(time=0))) = f(x).

Is `f((was_called, _, _)) = (True, myFunction(), time_elapsed_by_previous_function_call())` idempotent?

No. Proof:

Let x = (False, _, _).

Then,

f(f(x))
  = f(f((False, _, _)))
  = f((True, 0, 1000))
  = (True, 0, 1)

However, this does not equal
(True, 0, 1000) = f((False, _, _)) = f(x).

Filed under: softwareengineering - @ 22:22

Thẻ: definition, functions

Thiết kế website giá rẻ

Danh mục

If the sleep time of a function at first time differs from the second time, but the output is the same, is it still a idempotent function?

In short

Some more arguments

Conclusion

Is `f(x) = myFunction()` idempotent?

Is `f((_, world_state)) = (myFunction(), get_world_state())` idempotent?

Is `f((was_called, _, _)) = (True, myFunction(), time_elapsed_by_previous_function_call())` idempotent?

Danh mục

In short

Some more arguments

Conclusion

Is f(x) = myFunction() idempotent?

Is f((_, world_state)) = (myFunction(), get_world_state()) idempotent?

Is f((was_called, _, _)) = (True, myFunction(), time_elapsed_by_previous_function_call()) idempotent?

Is `f(x) = myFunction()` idempotent?

Is `f((_, world_state)) = (myFunction(), get_world_state())` idempotent?

Is `f((was_called, _, _)) = (True, myFunction(), time_elapsed_by_previous_function_call())` idempotent?