Idempotence (UK: /ˌɪdɛmˈpoʊtns/; US: /ˌaɪdᵻmˈpoʊtəns/ EYE-dəm-POH-təns) is the property of certain operations in mathematics and computer science, that can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of places in abstract algebra (in particular, in the theory of projectors and closure operators) and functional programming (in which it is connected to the property of referential transparency).
Contents
- Unary operation
- Idempotent elements and binary operations
- Connections
- Functions
- Formal languages
- Idempotent ring elements
- Other examples
- Computer science meaning
- Examples
- Applied examples
- References
The term was introduced by Benjamin Peirce in the context of elements of algebras that remain invariant when raised to a positive integer power, and literally means "(the quality of having) the same power", from idem + potence (same + power).
There are several meanings of idempotence, depending on what the concept is applied to:
Unary operation
A unary operation
In particular, the identity function
An important class of idempotent functions is given by projections in a vector space. An example of a projection is the function
A unary operation
is the total number of possible idempotent functions on the set. The integer sequence of the number of idempotent functions as given by the sum above for
Neither the property of being idempotent nor that of being not is preserved under composition of unary functions. As an example for the former, f(x) = x mod 3 and g(x) = max(x, 5) are both idempotent, but f ∘ g is not, although g ∘ f happens to be. As an example for the latter, the negation function ¬ on truth values isn't idempotent, but ¬ ∘ ¬ is.
Idempotent elements and binary operations
Given a binary operation
In particular an identity element of
For example, the operations of set union and set intersection are both idempotent, as are logical conjunction and logical disjunction, and, in general, the meet and join operations of a lattice.
Connections
The connections between the three notions are as follows.
Functions
As mentioned above, the identity map and the constant maps are always idempotent maps. The absolute value function of a real or complex argument, and the floor function of a real argument are idempotent.
The function that assigns to every subset
The operation of subtracting the mean of a list of numbers from every number in the list is idempotent. For example, consider the numbers
Formal languages
The Kleene star and Kleene plus operators used to express repetition in formal languages are idempotent.
Idempotent ring elements
An idempotent element of a ring is, by definition, an element that is idempotent for the ring's multiplication. That is, an element a is idempotent precisely when a2 = a.
Idempotent elements of rings yield direct decompositions of modules, and play a role in describing other homological properties of the ring. While "idempotent" usually refers to the multiplication operation of a ring, there are rings in which both operations are idempotent: Boolean algebras are such an example.
Other examples
In Boolean algebra, both the logical and and the logical or operations are idempotent. This implies that every element of Boolean algebra is idempotent with respect to both of these operations. Specifically,
Computer science meaning
In computer science, the term idempotent is used more comprehensively to describe an operation that will produce the same results if executed once or multiple times. This may have a different meaning depending on the context in which it is applied. In the case of methods or subroutine calls with side effects, for instance, it means that the modified state remains the same after the first call. In functional programming, though, an idempotent function is one that has the property f(f(x)) = f(x) for any value x.
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.
Examples
A function looking up a customer's name and address in a database is typically idempotent, since this will not cause the database to change. Similarly, changing a customer's address is typically idempotent, because the final address will be the same no matter how many times it is submitted. However, placing an order for a car for the customer is typically not idempotent, since running the call several times will lead to several orders being placed. Canceling an order is idempotent, because the order remains canceled no matter how many requests are made.
A composition of idempotent methods or subroutines, however, is not necessarily idempotent if a later method in the sequence changes a value that an earlier method depends on – idempotence is not closed under composition. For example, suppose the initial value of a variable is 3 and there is a sequence that reads the variable, then changes it to 5, and then reads it again. Each step in the sequence is idempotent: both steps reading the variable have no side effects and changing a variable to 5 will always have the same effect no matter how many times it is executed. Nonetheless, executing the entire sequence once produces the output (3, 5), but executing it a second time produces the output (5, 5), so the sequence is not idempotent.
In the Hypertext Transfer Protocol (HTTP), idempotence and safety are the major attributes that separate HTTP verbs. Of the major HTTP verbs, GET, PUT, and DELETE should be implemented in an idempotent manner according to the standard, but POST need not be. GET retrieves a resource; PUT stores content at a resource; and DELETE eliminates a resource. As in the example above, reading data usually has no side effects, so it is idempotent (in fact nullipotent). Storing and deleting a given set of content are each usually idempotent as long as the request specifies a location or identifier that uniquely identifies that resource and only that resource again in the future. The PUT and DELETE operations with unique identifiers reduce to the simple case of assignment to an immutable variable of either a value or the null-value, respectively, and are idempotent for the same reason; the end result is always the same as the result of the initial execution.
Violation of the unique identification requirement in storage or deletion typically causes violation of idempotence. For example, storing or deleting a given set of content without specifying a unique identifier: POST requests, which do not need to be idempotent, often do not contain unique identifiers, so the creation of the identifier is delegated to the receiving system which then creates a corresponding new record. Similarly, PUT and DELETE requests with nonspecific criteria may result in different outcomes depending on the state of the system - for example, a request to delete the most recent record. In each case, subsequent executions will further modify the state of the system, so they are not idempotent.
In Event Stream Processing, idempotence refers to the ability of a system to produce the same outcome, even if an event or message is received more than once.
In a load-store architecture, instructions that might possibly cause a page fault are idempotent. So if a page fault occurs, the OS can load the page from disk and then simply re-execute the faulted instruction. In a processor where such instructions are not idempotent, dealing with page faults is much more complex.
When reformatting output, pretty-printing is expected to be idempotent. In other words, if the output is already "pretty", there should be nothing to do for the pretty-printer.
Applied examples
Applied examples that many people could encounter in their day-to-day lives include elevator call buttons and crosswalk buttons. The initial activation of the button moves the system into a requesting state, until the request is satisfied. Subsequent activations of the button between the initial activation and the request being satisfied have no effect.