Idempotence - Idempotence

Pour les concepts en algèbre, voir Idempotent (théorie des anneaux) et Idempotent matrix .
On / Off boutons d'un train signe destination du panneau de commande. L'appui sur le bouton On (vert) est une opération idempotente, puisqu'elle a le même effet qu'elle soit effectuée une ou plusieurs fois. De même, appuyer sur Off est idempotent.

Idempotence ( Royaume - Uni : / ˌ ɪ d ɛ m p oʊ t ən s / , États - Unis : / ˌ aɪ d ə m - / ) est la propriété de certaines opérations en mathématiques et en informatique par lequel ils peuvent être appliqués plusieurs fois sans changer la résultat au-delà de la demande initiale. Le concept d'idempotence apparaît à plusieurs endroits en algèbre abstraite (en particulier, dans la théorie des projecteurs et des opérateurs de fermeture ) et en programmation fonctionnelle (dans laquelle il est lié à la propriété de transparence référentielle ).

L'expression a été introduit par Benjamin Peirce dans le contexte des éléments de algèbres qui restent invariant lorsqu'ils sont élevés à une puissance entière positive, et signifie littéralement « (la qualité d'avoir) de la même puissance », à partir idem + potence (même puissance +).

Définition

Un élément x d'un ensemble S muni d'un opérateur binaire • est dit idempotent sous • si

x • x = x .

L' opération binaire • est dite idempotente si

∀ x ∈ S , x • x = x .

Exemples

Fonctions idempotentes

Dans le monoid ( E E , ∘) des fonctions d'un ensemble E de lui - même avec la composition de fonctions ∘, les éléments idempotent sont les fonctions f : E → E telle que f ∘ f = f , qui est telle que ∀ x , f ( f ( x )) = f ( x ) (l'image de chaque élément dans E est un point fixe de f ). Par exemple:

Si l'ensemble E a n éléments, on peut le partitionner en k points fixes choisis et n − k points non fixes sous f , et alors k n − k est le nombre de fonctions idempotentes différentes. Par conséquent, en tenant compte de toutes les partitions possibles,

est le nombre total de fonctions idempotentes possibles sur l'ensemble. La séquence entière du nombre de fonctions idempotentes donnée par la somme ci-dessus pour n = 0, 1, 2, 3, 4, 5, 6, 7, 8, … commence par 1, 1, 3, 10, 41, 196 , 1057, 6322, 41393, … (séquence A000248 dans l' OEIS ).

Ni la propriété d'être idempotent ni celle de n'être pas ne sont conservées sous la composition de fonctions. A titre d'exemple pour les premiers, f ( x ) = x mod 3 et g ( x ) = max ( x , 5) sont tous les deux idempotent, mais f ∘ g est pas, bien que g ∘ f se trouve être. A titre d'exemple pour ce dernier, la fonction de négation ¬ sur le domaine booléen n'est pas idempotente, mais ¬ ∘ ¬ l' est. De même, la négation unaire −( ) des nombres réels n'est pas idempotente, mais −( ) ∘ −( ) l' est.

Sens de l'informatique

Voir aussi : Transparence référentielle , Réentrant (sous-programme) et Tri stable

En informatique , le terme idempotence peut avoir un sens différent selon le contexte dans lequel il est appliqué :

C'est une propriété très utile dans de nombreuses situations, car cela signifie qu'une opération peut être répétée ou réessayée aussi souvent que nécessaire sans provoquer d'effets indésirables. Avec les opérations non idempotentes, l'algorithme peut avoir à garder une trace de si l'opération a déjà été effectuée ou non.

Exemples d'informatique

Une fonction qui recherche le nom et l'adresse d'un client dans une base de données est généralement idempotente, car cela n'entraînera pas de modification de la base de données. De même, une demande de modification de l'adresse d'un client en XYZ est généralement idempotente, car l'adresse finale sera la même quel que soit le nombre de fois où la demande est soumise. Cependant, la demande d'un client pour passer une commande n'est généralement pas idempotente, car plusieurs demandes entraîneront la passation de plusieurs commandes. Une demande d'annulation d'une commande particulière est idempotente car quel que soit le nombre de demandes effectuées, la commande reste annulée.

Une séquence de sous-programmes idempotents où au moins un sous-programme est différent des autres, cependant, n'est pas nécessairement idempotent si un sous-programme ultérieur dans la séquence modifie une valeur dont dépend un sous-programme antérieur - l' idempotence n'est pas fermée sous composition séquentielle . Par exemple, supposons que la valeur initiale d'une variable est 3 et qu'il existe une séquence de sous-programmes qui lit la variable, la modifie ensuite en 5, puis la lit à nouveau. Chaque étape de la séquence est idempotente : les deux étapes de lecture de la variable n'ont pas d'effets secondaires et l'étape faisant passer la variable à 5 aura toujours le même effet quel que soit le nombre de fois qu'elle est exécutée. Néanmoins, exécuter la séquence entière une fois produit la sortie (3, 5), mais l'exécuter une deuxième fois produit la sortie (5, 5), donc la séquence n'est pas idempotente. 

int x = 3;
void read() { printf("%d\n", x); }
void change() { x = 5; }
void sequence() { read(); change(); read(); }

int main() {
  sequence();  // prints "3\n5\n"
  sequence();  // prints "5\n5\n"
  return 0;
}

Dans le protocole HTTP ( Hypertext Transfer Protocol ), l'idempotence et la sécurité sont les principaux attributs qui séparent les méthodes HTTP . Parmi les principales méthodes HTTP, GET, PUT et DELETE doivent être implémentées de manière idempotente conformément à la norme, mais POST n'a pas besoin de l'être. GET récupère l'état d'une ressource ; PUT met à jour l'état d'une ressource ; et DELETE supprime une ressource. Comme dans l'exemple ci-dessus, la lecture des données n'a généralement pas d'effets secondaires, elle est donc idempotente (en fait nullipotente ). La mise à jour et la suppression d'une donnée donnée sont généralement idempotentes tant que la demande identifie de manière unique la ressource et uniquement cette ressource à l'avenir. PUT et DELETE avec des identifiants uniques se réduisent au cas simple de l'affectation à une variable d'une valeur ou de la valeur nulle, respectivement, et sont idempotentes pour la même raison ; le résultat final est toujours le même que le résultat de l'exécution initiale, même si la réponse diffère.

La violation de l'exigence d'identification unique lors du stockage ou de la suppression entraîne généralement une violation de l'idempotence. Par exemple, stocker ou supprimer un ensemble de contenus donné sans spécifier d'identifiant unique : les requêtes POST, qui n'ont pas besoin d'être idempotentes, ne contiennent souvent pas d'identifiants uniques, la création de l'identifiant est donc déléguée au système récepteur qui crée alors un nouveau record correspondant. De même, les demandes PUT et DELETE avec des critères non spécifiques peuvent entraîner des résultats différents selon l'état du système - par exemple, une demande de suppression de l'enregistrement le plus récent. Dans chaque cas, les exécutions ultérieures modifieront davantage l'état du système, de sorte qu'elles ne sont pas idempotentes.

Dans le traitement des flux d'événements , l'idempotence fait référence à la capacité d'un système à produire le même résultat, même si le même fichier, événement ou message est reçu plusieurs fois.

Dans une architecture load-store , les instructions susceptibles de provoquer un défaut de page sont idempotentes. Ainsi, si un défaut de page se produit, le système d'exploitation peut charger la page à partir du disque, puis simplement réexécuter l'instruction défaillante. Dans un processeur où de telles instructions ne sont pas idempotentes, le traitement des défauts de page est beaucoup plus complexe.

Lors du reformatage de la sortie, la jolie impression devrait être idempotente. En d'autres termes, si la sortie est déjà "jolie", il ne devrait y avoir rien à faire pour la jolie-imprimante.

Dans l' architecture orientée services (SOA), un processus d'orchestration à plusieurs étapes composé entièrement d'étapes idempotentes peut être rejoué sans effets secondaires si une partie de ce processus échoue.

De nombreuses opérations qui sont idempotentes ont souvent des moyens de « reprendre » un processus s'il est interrompu – des moyens qui se terminent beaucoup plus rapidement que de tout recommencer depuis le début. Par exemple, reprendre un transfert de fichiers , synchroniser des fichiers , créer un build de logiciel , installer une application et toutes ses dépendances avec un gestionnaire de packages , etc.

Exemples appliqués

Un bouton de passage pour piétons typique est un exemple de système idempotent

Les exemples appliqués que de nombreuses personnes pourraient rencontrer dans leur vie quotidienne incluent les boutons d'appel d' ascenseur et les boutons de passage pour piétons . L'activation initiale du bouton fait passer le système dans un état de demande, jusqu'à ce que la demande soit satisfaite. Les activations ultérieures du bouton entre l'activation initiale et la satisfaction de la demande n'ont aucun effet, sauf si le système est conçu pour ajuster le temps de satisfaction de la demande en fonction du nombre d'activations.

Voir également

Les références

Lectures complémentaires