Exactly what rules must a function abide before we can call it "idempotent"?

Question

A post from another thread says that a function is said to be idempotent if it can be called multiple times without changing the result.

However the terms used (like no-side-effects and return-same-results) are relatively ambiguous. Consider this piece of code:

public class test {

    int x = 0;
    java.util.Random r = new java.util.Random();

    public int F() {
        return x + 1;
    }

    public void F2() {
        x = r.nextInt();
    }
}

Can we say that F() is idempotent because successive calls to F() returns the same value?

Or is it not idempotent since successive calls to F() does not return the same value if F2() is called inbetween?

_{PS: "idempotent" as defined in computer science, not maths.}

Answer 1

I'm going to disagree (actually, I now see that I agree with them!) with the other answers and say that, in the most common computer science use (function calls with side-effects, not functional programming), a function is idempotent if you can safely replace any invocation of the function with calling the function twice and keeping only the second result.

For example, consider two functions for deleting a file by name:

1) A function that returns success if the file does not exist. (Since the purpose of a delete operation is to make the file not exist.)

2) A function that returns a "file does not exist" error if the file does not exist. (Since the file could not be deleted.)

The first one is idempotent. If you call it and ignore the result, you can call it again and still get correct information. The file does not exist when you are done.

The second one is not idempotent. If you call it once and ignore the result, your second call will fail, making you think you did not delete the file.

A function to get the current time is idempotent under this definition, even though the result may be different. There is no harm to calling the function twice.

The concept is important in client-server protocols. Say you send a command and get no reply, maybe the connection breaks, maybe the server crashed. So you send the command again and get a reply. But on the first command, was the command lost or the reply? If the command is idempotent, it doesn't matter. You can just use the result.

If a protocol guarantees that all operations are idempotent, lower-level code can retry failed operations, switch servers, and otherwise try to "make things work" without breaking the semantics of the operations.

It takes some doing to make an idempotent protocol. For example, you might wonder how you make a sensible "delete file" operation. One way is to assign each file a unique ID that changes when the file is deleted and recreated. Then you split a delete into two halves. The first, "get ID from name" is idempotent and fails if the file does not exist. The second, "delete ID if it exists" is idempotent and succeeds if you, or anyone else, deleted the file. (The one quirk is this doesn't tell you for sure that you were the one to delete the file.) The combination of the two idempotent operations provides the desired non-idempotent delete operation.