Qu'est-ce qu'un terme pour une fonction qui, lorsqu'elle est appelée à plusieurs reprises, a le même effet que d'appeler une fois?

96

(En supposant un environnement mono-threadé)

Une fonction qui remplit ce critère est:

bool MyClass::is_initialized = false;

void MyClass::lazy_initialize()
{
    if (!is_initialized)
    {
        initialize(); //Should not be called multiple times
        is_initialized = true;
    }
}

En substance, je peux appeler cette fonction plusieurs fois et ne pas m'inquiéter de l'initialiser MyClassplusieurs fois.

Une fonction qui ne remplit pas ce critère pourrait être:

Foo* MyClass::ptr = NULL;

void initialize()
{
    ptr = new Foo();
}

Appeler initialize()plusieurs fois provoquera une fuite de mémoire

Motivation

Il serait bien d’avoir un seul mot concis pour décrire ce comportement afin que les fonctions censées répondre à ce critère puissent être dûment commentées (particulièrement utile lors de la description de fonctions d’interface censées être remplacées)

Rufus
la source
67
Pour le ou les électeurs proches: bien qu’il soit vrai que 99,999% (estimation approximative) de toutes les questions "nommez-le" sont hors sujet parce qu’elles n’ont pas de réponse simple, correcte, non ambiguë, objective et dénomination est purement subjective et basée avis, celui - ci ne posséderaient une seule correcte, objective sans ambiguïté, réponse qui a été donnée par l'OP lui - même.
Jörg W Mittag Le
30
L' appeler plusieurs fois fait avoir un effet, comme il pourrait y avoir autre code qui a changé « var » entre les deux.
RemcoGerlich
7
Pourquoi cette question a-t-elle été posée, si le PO connaissait la réponse au moment de la demande ? Y a-t-il une raison autre que rep / points / construction de karma?
dotancohen
13
Le style de réponse automatique de style Q / A est l'un des concepts clés de StackExchange.
Glglgl
17
@glglgl: Je suis d'accord, pour des questions méritoires. Quel mérite a cette question? Je suis sérieusement préoccupé par le fait que nous allons commencer à obtenir chaque question CS 101 posée et à laquelle l'OP répond immédiatement, chaque terme CS unique posé et défini immédiatement par l'OP, et les avantages et inconvénients de chaque algorithme de base mis en doute, puis immédiatement répondus par l'OP ( pas nécessairement cet OP). Est-ce le site que nous souhaitons que softwareengineering.SE soit?
dotancohen

Réponses:

244

Ce type de fonction / opération s'appelle Idempotent

Idempotence (UK: / ˌɪdɛmˈpoʊtəns /, [1] États-Unis: / ˌaɪdəm - /) [2] est la propriété de certaines opérations en mathématiques et en informatique selon lesquelles elles peuvent être appliquées plusieurs fois sans changer le résultat au-delà de l'application initiale.

En mathématiques, cela signifie que si f est idempotent, f ( f (x)) = f (x), ce qui revient à dire que ff = f .

En informatique, cela signifie que si f(x);est idempotent, f(x);est identique à f(x); f(x);.

Remarque: ces significations semblent différentes, mais sous la sémantique dénotationnelle d'état , le mot "idempotent" a en fait la même signification exacte en mathématiques et en informatique.

Rufus
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
maple_shaft
51

Le terme précis pour cela (comme le mentionne Woofas ) est idempotence. Je voulais ajouter que même si vous pouviez appeler votre func1méthode idempotente, vous ne pouviez pas l'appeler une fonction pure . Les propriétés d'une fonction pure sont deux: elle doit être idempotente et ne pas avoir d'effets secondaires, c'est-à-dire aucune mutation de variables statiques locales, de variables non locales, d'arguments de référence modifiables ou de flux d'E / S.

La raison pour laquelle je mentionne ceci est qu’une fonction idempotente avec des effets secondaires n’est pas bonne non plus, puisque techniquement idempotent fait référence au résultat de la fonction, et non aux effets secondaires. Donc techniquement, votre func2méthode est idempotente, car la sortie ne change pas en fonction de l’entrée.

Vous voudrez probablement spécifier que vous voulez une fonction pure. Voici un exemple de fonction pure:

int func1(int var)
{
    return var + 1;
}

Vous trouverez plus de lectures dans l'article de Wikipedia "Fonction pure" .

Neil
la source
37
Je pense que votre définition de idempotency est trop étroite, ou en d'autres termes, vous utilisez la définition mathématique de idempotency, pas celle de programmation. Par exemple, les méthodes PUTet DELETEHTTP sont appelées idempotent précisément parce que l’ exécution répétitive de leurs effets secondaires a le même effet que de les exécuter une seule fois. Vous dites "idempotency f∘f = f", alors que dans la programmation, on entend "exécuter fa le même effet que l'exécution f; f". Notez que vous pouvez facilement transformer le second sens en ancien en ajoutant un paramètre "world".
Jörg W Mittag Le
23
@Neil "Idempotency est strictement un terme mathématique." Non, il est également utilisé dans les réseaux et les systèmes de communication client / serveur distribués. Il est décrit comme décrit par JörgWMittag. C'est un concept utile car il permet plusieurs requêtes à un serveur / client avec la même opération / le même message sans changer le but du message original. Ceci est utile lorsque la communication n'est pas fiable et que vous devez relancer une commande car le message du client a été supprimé ou la réponse du serveur l'a été.
opa
7
Vous devriez aller plus en détail sur la différence entre pur et idempotent. Votre exemple func1 n'est pas idempotent parce que func1(1) != func1(func1(1)).
Tezra
5
La pureté et l'idempotence sont différentes. Une fonction pure ne doit pas nécessairement être idempotente au sens mathématique (elle est évidemment idempotente en termes d'effets secondaires, car elle n'en a pas). La fonction idempotente (au sens de la programmation) ne doit pas nécessairement être pure, comme dans l'exemple donné par OP. En outre, comme nous l’avons mentionné, l’idempotence est une propriété utile dont l’utilisation est strictement différente de celle de la pureté. Votre définition de la pureté comme "idempotente et sans effets secondaires" est fausse ou du moins trompeuse, en votant à la baisse.
Frax
5
Dans le contexte de la programmation, il n'y a pas "d'effets secondaires", mais si vous étiez élargi la définition pour inclure ceci, alors une fonction idempotente et une fonction pure signifieraient la même chose. Non, ils ne voudraient pas dire la même chose du tout. Idempotent, pas pur: void f(int var) { someGlobalVariable = var; }. Pur, non idempotent: int func1(int var) { return var + 1; }.
JLRishe
6

Le terme est Idempotence . Notez ci-dessous qu'il existe une différence distincte entre une fonction Idempotente (appelée récursivement sur elle-même; deuxième bloc de code et la définition mathématique) et idempotence fonctionnelle (appelée à plusieurs reprises avec la même entrée de manière séquentielle; premier bloc de code et souvent le terme utilisé dans la programmation).

Une fonction f avec des effets secondaires est dite idempotente dans la composition séquentielle f; f si, lorsqu'il est appelé deux fois avec la même liste d'arguments, le deuxième appel n'a aucun effet secondaire et renvoie la même valeur que le premier appel [citation nécessaire] (en supposant qu'aucune autre procédure n'a été appelée entre la fin du premier appel et le début du deuxième appel).

Par exemple, considérons le code Python suivant:

x = 0

def setx(n):
    global x
    x = n

setx(5)
setx(5)

Setx est idempotent car le second appel à setx (avec le même argument) ne modifie pas l'état visible du programme: x était déjà défini sur 5 dans le premier appel et est à nouveau défini sur 5 dans le second appel, conservant ainsi le même valeur. Notez que ceci est distinct de idempotence dans la composition de fonction f ∘ f. Par exemple, la valeur absolue est idempotente dans la composition de fonction:

def abs(n):
    if n < 0:
        return -n
    else:
        return n

abs(-5) == abs(abs(-5)) == abs(5) == 5
Tezra
la source
3

En physique, j'ai entendu parler de projection :

une saillie est une transformation linéaire P à partir d' un espace vectoriel à lui-même de telle sorte que P 2 = P . Autrement dit, chaque fois que P est appliqué deux fois à une valeur, il donne le même résultat que s'il était appliqué une fois (idempotent).

Graphiquement, cela a du sens si vous regardez un dessin animé d’une projection vectorielle :

entrez la description de l'image ici

Dans l'image, un 1 est la projection de a sur b , ce qui ressemble à la première application de votre fonction. Projections ultérieures de un 1 sur de b donnent le même résultat a 1 . En d'autres termes, lorsque vous appelez une projection à plusieurs reprises, cela a le même effet que si vous l'appeliez une fois.

Avertissement juste: je n'ai jamais entendu dire que ce soit utilisé en dehors de la physique, donc à moins que vous n'ayez de tels types dans votre équipe, vous risquez de dérouter tout le monde.

utilisateur1717828
la source
2
C'est en effet un bel exemple concret de la manière dont une fonction idempotente peut être visualisée (mathématiquement, et en particulier dans le champ géométrie vectorielle / algèbre linéaire). Bien que "l'idempotence" de la fonction logicielle soit un concept très proche, je ne pense pas que les développeurs / informaticiens utilisent souvent le mot "projection" dans ce contexte (une "fonction de projection" en génie logiciel ferait plutôt référence à une fonction qui prend un objet et retourne un nouvel objet qui en dérive, ou une propriété de cet objet, par exemple)
Pac0
2
@ Pac0 Oh, d'accord. Je travaille à la frontière entre la science et la programmation et je n’ai pas réalisé que le mot était déjà surchargé. Je peux penser à quelques exemples artificiels au travail où j'utiliserais cette terminologie, mais je travaille certes avec des personnes prêtes à accepter le jargon scientifique au quotidien :-)
user1717828
3

C'est un algorithme déterministe car, avec la même entrée (dans ce cas aucune entrée), il produira toujours la même sortie.

En informatique, un algorithme déterministe est un algorithme qui, avec une entrée particulière, produira toujours la même sortie, la machine sous-jacente passant toujours par la même séquence d'états. Les algorithmes déterministes sont de loin le type d'algorithme le plus étudié et le plus familier, ainsi que l'un des plus pratiques, car ils peuvent être exécutés efficacement sur de vraies machines.

Les bases de données SQL sont intéressées par les fonctions déterministes .

Une fonction déterministe donne toujours la même réponse quand elle a les mêmes entrées. La plupart des fonctions SQL intégrées à SQLite sont déterministes. Par exemple, la fonction abs (X) renvoie toujours la même réponse tant que son entrée X est la même.

Une fonction doit être déterministe si elle est utilisée dans le calcul d’un index.

Par exemple, dans SQLite, les fonctions non déterministes suivantes ne peuvent pas être utilisées dans un index: random(), changes(), last_insert_rowid()et sqlite3_version().

Stephen Quan
la source
6
Le demandeur func2est déterministe (il n'y a pas d'effets aléatoires), mais il est déjà déclaré en violation de la propriété qu'il recherche.
Draco18s
Que le même résultat soit produit par la répétition n'est pas la même chose que de dire que le même résultat est produit par imbrication ou chaînage. Les fonctions déterministes sont importantes pour la mise en cache des résultats, plus que pour l'indexation / le hachage.
mckenzm
3

En plus des autres réponses, s'il existe une entrée spécifique dans le functon qui possède cette propriété, il s'agit d'un point fixe , d' un point invariant ou d'un point fixe de la fonction. Par exemple, 1 pour tout pouvoir est égal à 1, donc (1ⁿ) = 1ⁿ = 1.

Le cas particulier d'un programme qui se produit en sortie est un quine .

Davislor
la source
Les quines sont au logiciel comme les jeux de Cantor aux maths :-). Et bien sûr, les quines ne sont pas idempotentes - elles échouent lorsque la sortie existe déjà ou elles "obstruent" le résultat précédent et écrivent une nouvelle sortie, bien que identique.
Carl Witthoft