Was ist ein Begriff für eine Funktion, die bei wiederholtem Aufruf die gleiche Wirkung hat wie ein einmaliger Aufruf?

96

(Unter der Annahme einer Umgebung mit einem Thread)

Eine Funktion, die dieses Kriterium erfüllt, ist:

bool MyClass::is_initialized = false;

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

Im Wesentlichen kann ich diese Funktion mehrmals aufrufen und muss mir keine Sorgen machen, dass sie MyClassmehrmals initialisiert wird

Eine Funktion, die dieses Kriterium nicht erfüllt, kann sein:

Foo* MyClass::ptr = NULL;

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

Ein initialize()mehrmaliger Aufruf führt zu einem Speicherverlust

Motivation

Es wäre schön, ein einziges prägnantes Wort zur Beschreibung dieses Verhaltens zu haben, damit Funktionen, von denen erwartet wird, dass sie dieses Kriterium erfüllen, ordnungsgemäß kommentiert werden können (besonders nützlich bei der Beschreibung von Schnittstellenfunktionen, von denen erwartet wird, dass sie überschrieben werden).

Rufus
quelle
67
An die nahen Wähler: Es ist zwar richtig, dass 99,999% (grobe Schätzung) aller "name-that-thing" -Fragen nicht zum Thema gehören, da sie keine einzige, korrekte, eindeutige, objektive Antwort haben Die Benennung ist rein subjektiv und meinungsbasiert, diese hat jedoch eine einzige, korrekte, eindeutige, objektive Antwort, die vom OP selbst gegeben wurde.
Jörg W Mittag
30
Es mehrmals aufrufen tut eine Wirkung haben, da es ein anderer Code sein könnte , die ‚var‘ zwischendurch geändert.
RemcoGerlich
7
Warum wurde diese Frage gestellt, wenn das OP die Antwort zum Zeitpunkt des Fragens kannte ? Gibt es einen anderen Grund als rep / points / karma building?
Dotancohen
13
@dotancohen Selbstantwortender Q / A-Stil ist eines der Schlüsselkonzepte von StackExchange.
glglgl
17
@glglgl: Ich stimme zu, für Fragen mit Verdienst. Welchen Verdienst hat diese Frage? Ich bin ernsthaft besorgt, dass wir anfangen, jede CS 101-Frage vom OP gestellt und sofort beantwortet zu bekommen, jeden einzelnen CS-Begriff, der vom OP gestellt und sofort definiert wird, und die Vor- und Nachteile jedes grundlegenden Algorithmus, die vom OP befragt und dann sofort beantwortet werden ( nicht unbedingt dieses OP). Ist das die Seite, die wir für softwareengineering.SE haben wollen?
Dotancohen

Antworten:

244

Diese Art von Funktion / Operation wird als idempotent bezeichnet

Idempotence (UK: / ˌɪdˌɪmɛpoˈtʊns /, [1] US: / ˌaˌdɪm - /) [2] ist die Eigenschaft bestimmter Operationen in Mathematik und Informatik, wobei sie mehrfach angewendet werden können, ohne das Ergebnis über die ursprüngliche Anwendung hinaus zu verändern.

In der Mathematik bedeutet dies, dass wenn f idempotent ist, f ( f (x)) = f (x) ist, was dasselbe ist, wie wenn man ff = f sagt .

In der Informatik bedeutet dies, dass wenn f(x);idempotent f(x);ist, dasselbe wie f(x); f(x);.

Anmerkung: Diese Bedeutungen scheinen unterschiedlich zu sein, aber unter den Bezeichnungen der Staatssemantik hat das Wort "idempotent" in Mathematik und Informatik genau dieselbe Bedeutung.

Rufus
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
maple_shaft
51

Der genaue Begriff dafür (wie Woofas erwähnt ) ist Idempotenz. Ich wollte hinzufügen, dass Sie Ihre func1Methode zwar idempotent, aber keine reine Funktion nennen können. Es gibt zwei Eigenschaften einer reinen Funktion: Sie muss idempotent sein und darf keine Nebenwirkungen haben, dh keine Mutation lokaler statischer Variablen, nicht lokaler Variablen, veränderlicher Referenzargumente oder E / A-Ströme.

Der Grund, warum ich dies erwähne, ist, dass eine idempotente Funktion mit Nebenwirkungen auch nicht gut ist, da sich technisch idempotent auf die Rückgabe der Funktion und nicht auf die Nebenwirkungen bezieht. Technisch gesehen ist Ihre func2Methode also idempotent, da sich die Ausgabe nicht entsprechend der Eingabe ändert.

Sie möchten höchstwahrscheinlich angeben, dass Sie eine reine Funktion wünschen. Ein Beispiel für eine reine Funktion könnte sein:

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

Weitere Informationen finden Sie im Wikipedia-Artikel "Reine Funktion" .

Neil
quelle
37
Ich denke, Ihre Definition von Idempotenz ist zu eng, oder anders ausgedrückt, Sie verwenden die mathematische Definition von Idempotenz, nicht die programmierende. Beispielsweise werden die PUTund DELETEHTTP-Methoden genau deshalb als idempotent bezeichnet , weil die mehrfache Ausführung ihrer Nebenwirkungen dieselbe Wirkung hat wie die einmalige Ausführung. Sie sagen, "Idempotenz bedeutet f∘f = f", während wir in der Programmierung meinen, "Ausführen fhat den gleichen Effekt wie Ausführen f; f". Beachten Sie, dass Sie die zweite Bedeutung einfach in die erstere umwandeln können, indem Sie einen "world" -Parameter hinzufügen.
Jörg W Mittag
23
@Neil "Idempotenz ist streng genommen ein mathematischer Begriff." Nein, es wird auch in Netzwerk- und Client-Server-Kommunikations- / verteilten Systemen verwendet und wird so beschrieben, wie JörgWMittag es beschreibt. Dies ist ein nützliches Konzept, da mehrere Anforderungen an einen Server / Client mit derselben Operation / Nachricht möglich sind, ohne dass geändert werden muss, was diese ursprüngliche Nachricht bewirken soll. Dies ist nützlich, wenn Sie eine unzuverlässige Kommunikation haben und einen Befehl wiederholen müssen, weil entweder die Client-Nachricht gelöscht wurde oder die Server-Antwort war.
opa
7
Sie sollten näher auf den Unterschied zwischen rein und idempotent eingehen. Dein Beispiel func1 ist da nicht idempotent func1(1) != func1(func1(1)).
Tezra
5
Reinheit und Idempotenz sind unterschiedlich. Eine reine Funktion muss nicht im mathematischen Sinne idempotent sein (sie ist offensichtlich in Bezug auf Nebenwirkungen idempotent, da sie keine hat). Die idempotente Funktion (im Sinne der Programmierung) muss nicht rein sein, wie im Beispiel von OP. Wie bereits erwähnt, ist Idempotenz eine nützliche Eigenschaft, deren Verwendung sich stark von der Reinheit unterscheidet. Ihre Definition von Reinheit als "idempotent und ohne Nebenwirkungen" ist falsch oder zumindest irreführend, Abstimmungen.
Frax
5
Im Kontext der Programmierung gibt es keine "Nebenwirkungen", aber wenn Sie die Definition dahingehend erweitern, dass sie dies einschließt, würden eine idempotente Funktion und eine reine Funktion dasselbe bedeuten. Nein, sie würden überhaupt nicht dasselbe bedeuten. Idempotent, nicht rein: void f(int var) { someGlobalVariable = var; }. Rein, nicht idempotent: int func1(int var) { return var + 1; }.
JLRishe
6

Der Begriff ist Idempotenz . Beachten Sie, dass es einen deutlichen Unterschied zwischen einer idempotenten Funktion (die rekursiv für sich selbst aufgerufen wird; zweiter Codeblock und die mathematische Definition) und einer funktionalen Idempotenz (die wiederholt mit der gleichen Eingabe nacheinander aufgerufen wird; erster Codeblock und häufig der in der Programmierung verwendete Begriff) gibt.

Eine Funktion f mit Nebenwirkungen soll bei sequentieller Zusammensetzung f idempotent sein; f Wenn der zweite Aufruf bei zweimaligem Aufruf mit derselben Liste von Argumenten keine Nebenwirkungen hat und denselben Wert wie der erste Aufruf zurückgibt (vorausgesetzt, zwischen dem Ende des ersten Aufrufs und dem Beginn wurden keine anderen Prozeduren aufgerufen) des zweiten Anrufs).

Betrachten Sie beispielsweise den folgenden Python-Code:

x = 0

def setx(n):
    global x
    x = n

setx(5)
setx(5)

Hier ist setx idempotent, weil der zweite Aufruf von setx (mit dem gleichen Argument) den sichtbaren Programmstatus nicht ändert: x wurde bereits beim ersten Aufruf auf 5 gesetzt und wird beim zweiten Aufruf wieder auf 5 gesetzt, wodurch die gleicher Wert. Beachten Sie, dass sich dies von der Idempotenz unter der Funktionszusammensetzung f ∘ f unterscheidet. Zum Beispiel ist der absolute Wert unter Funktionszusammensetzung idempotent:

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

abs(-5) == abs(abs(-5)) == abs(5) == 5
Tezra
quelle
3

In der Physik habe ich gehört, dass dies als Projektion bezeichnet wird :

ein Vorsprung ist eine lineare Transformation P von einem Vektorraum , um sich selbst , so dass P 2 = P . Das heißt, wenn P zweimal auf einen Wert angewendet wird, wird dasselbe Ergebnis erzielt, als wäre es einmal angewendet worden (idempotent).

Grafisch ist dies sinnvoll, wenn Sie sich eine Karikatur einer Vektorprojektion ansehen :

Bildbeschreibung hier eingeben

Im Bild ist a 1 die Projektion von a auf b , was wie die erste Anwendung Ihrer Funktion ist. Nachfolgende Projektionen von a 1 auf b ergeben das gleiche Ergebnis wie a 1 . Mit anderen Worten, wenn Sie eine Projektion wiederholt aufrufen, hat dies den gleichen Effekt wie ein einmaliger Aufruf.

Faire Warnung: Ich habe noch nie gehört, dass dies außerhalb der Physik verwendet wird. Wenn Sie also nicht über solche Typen in Ihrem Team verfügen, könnten Sie alle verwirren.

user1717828
quelle
2
Dies ist in der Tat ein schönes konkretes Beispiel dafür, wie eine idempotente Funktion visualisiert werden kann (mathematisch und insbesondere im Bereich Vektorgeometrie / Lineare Algebra). Während die "Idempotenz" von Softwarefunktionen ein sehr enges Konzept ist, denke ich, verwenden Entwickler / Informatiker in diesem Zusammenhang nicht oft das Wort "Projektion" (eine "Projektionsfunktion" in der Softwaretechnik würde sich eher auf eine Funktion beziehen, die ein Objekt annimmt und gibt ein neues Objekt zurück, das von ihm abgeleitet wurde, oder eine Eigenschaft dieses Objekts (zum Beispiel)
Pac0
2
@ Pac0 Oh, ok. Ich arbeite an der Grenze zwischen Wissenschaft und Programmierung und habe nicht bemerkt, dass das Wort bereits überladen ist. Ich kann mir ein paar erfundene Beispiele vorstellen, bei denen ich diese Terminologie verwenden würde, aber ich arbeite zugegebenermaßen mit Leuten, die bereit sind, sich täglich mit Wissenschaftssprache
abzufinden
3

Es ist ein deterministischer Algorithmus, da er bei gleicher Eingabe (in diesem Fall keine Eingabe) immer die gleiche Ausgabe erzeugt.

In der Informatik ist ein deterministischer Algorithmus ein Algorithmus, der bei einer bestimmten Eingabe immer dieselbe Ausgabe erzeugt, wobei die zugrunde liegende Maschine immer dieselbe Folge von Zuständen durchläuft. Deterministische Algorithmen sind bei weitem die am besten untersuchte und bekannteste Art von Algorithmen sowie eine der praktischsten, da sie auf realen Maschinen effizient ausgeführt werden können.

SQL-Datenbanken interessieren sich für deterministische Funktionen .

Eine deterministische Funktion gibt immer die gleiche Antwort, wenn sie die gleichen Eingaben hat. Die meisten integrierten SQL-Funktionen in SQLite sind deterministisch. Beispielsweise gibt die abs (X) -Funktion immer dieselbe Antwort zurück, solange ihre Eingabe X dieselbe ist.

Eine Funktion muss deterministisch sein, wenn sie zur Berechnung eines Index verwendet wird.

Zum Beispiel in SQLite können die folgenden nicht-deterministischen Funktionen nicht in einem Index verwendet werden: random(), changes(), last_insert_rowid()und sqlite3_version().

Stephen Quan
quelle
6
Der Fragesteller func2ist deterministisch (es gibt keine zufälligen Effekte), aber bereits als Verstoß gegen die gesuchte Eigenschaft deklariert.
Draco18s
Dass dasselbe Ergebnis durch Wiederholung erzeugt wird, ist nicht dasselbe wie das Sagen, dass dasselbe Ergebnis durch Verschachteln oder Verketten erzeugt wird. Deterministische Funktionen sind für das Cachen von Ergebnissen wichtiger als für das Indizieren / Hashing.
McKenzm
3

Zusätzlich zu den anderen Antworten, wenn es einen bestimmten Eingang an den functon ist , die diese Eigenschaft hat, ist es ein Fixpunkt , Festpunkt oder Fixpunkt der Funktion. Zum Beispiel ist 1 zu jeder Potenz gleich 1, also (1ⁿ) ⁿ = 1ⁿ = 1.

Der Spezialfall eines Programms, das sich selbst als Ausgabe produziert, ist ein Quine .

Davislor
quelle
Quines sind für Software wie Cantor-Sets für Mathematik :-). Und Quines sind natürlich nicht idempotent - sie schlagen entweder fehl, wenn die Ausgabe bereits vorhanden ist, oder sie "puffern" das vorherige Ergebnis und schreiben eine neue, wenn auch identische Ausgabe.
Carl Witthoft