Erstklassige Funktion

Im Informatik, a Programmiersprache soll haben erstklassige Funktionen Wenn es behandelt wird Funktionen wie erstklassige Bürger. Dies bedeutet, dass die Sprache die Übergabe von Funktionen als Argumente an andere Funktionen unterstützt, sie als Werte aus anderen Funktionen zurückgibt und sie Variablen zugewiesen oder in Datenstrukturen speichert.^[1] Einige Programmiersprache Theoretiker erfordern Unterstützung für Anonyme Funktionen (Funktionsliterale) auch.^[2] In Sprachen mit erstklassigen Funktionen die Namen von Funktionen haben keinen besonderen Status; Sie werden wie gewöhnlich behandelt Variablen mit einer Funktionstyp.^[3] Der Begriff wurde von geprägt von Christopher Strachey im Kontext von "Funktionen als erstklassige Bürger" Mitte der 1960er Jahre.^[4]

Erstklassige Funktionen sind eine Notwendigkeit für die Funktionelle Programmierung Stil, in dem die Verwendung von Funktionen höherer Ordnung ist eine Standardpraxis. Ein einfaches Beispiel für eine höher angeordnete Funktion ist die Karte Funktion, die als Argumente, eine Funktion und eine Liste nimmt und die Liste zurückgibt, indem die Funktion auf jedes Mitglied der Liste angewendet wird. Für eine Sprache zu unterstützen KarteEs muss unterstützen, eine Funktion als Argument zu übergeben.

Es gibt bestimmte Implementierungsschwierigkeiten, Funktionen als Argumente zu übergeben oder sie als Ergebnisse zurückzugeben, insbesondere in Gegenwart von Nicht-lokale Variablen eingeführt in verschachtelt und Anonyme Funktionen. Historisch gesehen wurden diese als als als bezeichnet Funarg -Probleme, der Name aus "Funktionsargument".^[5] In frühen imperativen Sprachen wurden diese Probleme vermieden, indem die Funktionen nicht als Ergebnistypen unterstützt werden (z. Algol 60, Pascal) oder weglassen verschachtelte Funktionen und damit nicht-lokale Variablen (z. C). Die frühe funktionale Sprache Lispeln nahm den Ansatz von Dynamischer Scoping, wo sich nicht lokale Variablen auf die engste Definition dieser Variablen an dem Punkt beziehen, an dem die Funktion ausgeführt wird, anstatt dass sie definiert wurde. Richtige Unterstützung für lexikalisch abgebildet Erstklassige Funktionen wurden in eingeführt Planen und erfordert den Umgang mit Verweise auf Funktionen als Schließungen statt kahl Funktionszeiger,^[4] was wiederum macht Müllsammlung eine Notwendigkeit.

Konzepte

In diesem Abschnitt vergleichen wir, wie bestimmte Programmierungen in einer funktionalen Sprache mit erstklassigen Funktionen gehandhabt werden.Haskell) im Vergleich zu einer imperativen Sprache, in der Funktionen zweiter Klasse sind (Bürger der zweiten KlasseC).

Funktionen höherer Ordnung: Funktionen als Argumente übergeben

In Sprachen, in denen Funktionen erstklassige Bürger sind, können Funktionen als Argumente an andere Funktionen wie andere Werte übergeben werden (eine Funktion, die eine andere Funktion als Argument als Funktion höherer Ordnung bezeichnet). In der Sprache Haskell:

Karte :: (a -> b) -> [a] -> [b] Karte f []  = [] Karte f (x:xs) = f x : Karte f xs 

Sprachen, in denen Funktionen nicht erstklassig sind Funktionszeiger oder Delegierte. In der Sprache C:

Leere Karte(int (*f) (int), int x[],, size_t n) {   zum (int i = 0; i < n; i++)   x[i] = f(x[i]); } 

Es gibt eine Reihe von Unterschieden zwischen den beiden Ansätzen, die es sind nicht direkt im Zusammenhang mit der Unterstützung erstklassiger Funktionen. Die Haskell -Probe arbeitet auf Listen, während die C -Probe arbeitet Arrays. Beide sind die natürlichsten zusammengesetzten Datenstrukturen in den jeweiligen Sprachen, und die C -Stichprobe auf verknüpften Listen hätte es unnötig komplex gemacht. Dies erklärt auch die Tatsache, dass die C -Funktion einen zusätzlichen Parameter benötigt (anhand der Größe des Arrays). Die C -Funktion aktualisiert das Array an Ort und Stelleohne Wert zurückzugeben, während in Haskell -Datenstrukturen Datenstrukturen sind hartnäckig (Eine neue Liste wird zurückgegeben, während das alte intakt bleibt.) Die Haskell -Probe verwendet Rekursion Um die Liste zu durchqueren, während die C -Probe verwendet Wiederholung. Dies ist wiederum die natürlichste Möglichkeit, diese Funktion in beiden Sprachen auszudrücken, aber die Haskell -Probe hätte leicht in Bezug auf a ausgedrückt werden können falten und die C -Probe in Bezug auf die Rekursion. Schließlich hat die Haskell -Funktion a polymorph Typ, da dies nicht von C unterstützt wird int.

Anonyme und verschachtelte Funktionen

In Sprachen, die anonyme Funktionen unterstützen, können wir eine solche Funktion als Argument an eine Funktion höherer Ordnung übergeben:

hauptsächlich = Karte (\x -> 3 * x + 1) [1, 2, 3, 4, 5] 

In einer Sprache, die anonyme Funktionen nicht unterstützt, müssen wir ihn stattdessen an einen Namen binden:

int f(int x) {   Rückkehr 3 * x + 1; } int hauptsächlich() {   int aufführen[] = {1, 2, 3, 4, 5};   Karte(f, aufführen, 5); } 

Nicht-lokale Variablen und Schließungen

Sobald wir anonyme oder verschachtelte Funktionen haben, wird es für sie natürlich, sich auf Variablen außerhalb ihres Körpers zu beziehen (genannt Nicht-lokale Variablen):

hauptsächlich = Lassen a = 3  b = 1  in Karte (\x -> a * x + b) [1, 2, 3, 4, 5] 

Wenn Funktionen mit nackten Funktionszeiger dargestellt werden, können wir nicht mehr wissen, wie der Wert, der außerhalb des Körpers der Funktion liegt, an sie übergeben werden sollte, und aus diesem Grund muss ein Schließung manuell gebaut werden. Daher können wir hier nicht von "erstklassigen" Funktionen sprechen.

Typedef Struktur {   int (*f) (int, int, int);   int *a;   int *b; } CLEIDE_T; Leere Karte(CLEIDE_T *Schließung, int x[],, size_t n) {   zum (int i = 0; i < n; ++i)   x[i] = (*Schließung->f) (*Schließung->a, *Schließung->b, x[i]); } int f(int a, int b, int x) {   Rückkehr a * x + b; } Leere hauptsächlich() {   int l[] = {1, 2, 3, 4, 5};   int a = 3;   int b = 1;   CLEIDE_T Schließung = {f, &a, &b};   Karte(&Schließung, l, 5); } 

Beachten Sie auch, dass die Karte ist jetzt spezialisiert auf Funktionen, die sich auf zwei beziehen ints außerhalb ihrer Umgebung. Dies kann allgemeiner eingerichtet werden, erfordert jedoch mehr Boilerplate -Code. Wenn f Wäre ein gewesen verschachtelte Funktion Wir wären immer noch auf das gleiche Problem gestoßen, und dies ist der Grund, warum sie in C nicht unterstützt werden.^[6]

Funktionen höherer Ordnung: Funktionen als Ergebnisse zurückgeben

Bei der Rückgabe einer Funktion geben wir tatsächlich ihre Schließung zurück. Im C -Beispiel werden alle lokalen Variablen, die durch den Verschluss erfasst werden, aus dem Zielfernrohr, sobald wir von der Funktion zurückkehren, die die Schließung aufbaut. Das Erzwingen des Verschlusses zu einem späteren Zeitpunkt führt zu undefiniertem Verhalten und kündigt möglicherweise den Stapel. Dies ist als die bekannt Aufwärts funarg Problem.

Zuweisen von Funktionen an Variablen

Zuweisung Funktionen zu Variablen und das Speichern in den (globalen) Datenstrukturen leiden möglicherweise unter den gleichen Schwierigkeiten wie die Rückgabefunktionen.

f :: [[Ganze Zahl] -> [Ganze Zahl]] f = Lassen a = 3  b = 1  in [Karte (\x -> a * x + b), Karte (\x -> b * x + a)] 

Gleichheit der Funktionen

Da man die meisten Literale und Werte für Gleichheit testen kann, ist es natürlich zu fragen, ob eine Programmiersprache Testfunktionen für Gleichheit unterstützen kann. Bei weiterer Inspektion erscheint diese Frage schwieriger und man muss zwischen verschiedenen Arten der Funktionsgleichheit unterscheiden:^[7]

Erweiterungsgleichheit

Zwei Funktionen f und g werden als extensional gleich angesehen, wenn sie sich auf ihre Ausgaben für alle Eingänge einig sind (∀x. f(x) = g(x)). Unter dieser Definition von Gleichheit beispielsweise zwei beliebige Implementierungen von a Stallsortieralgorithmus, wie zum Beispiel Sortieren durch Einfügen und Zusammenführen, sortieren, würde als gleich angesehen werden. Die Entscheidung für die Erweiterungsgleichheit ist unentscheidbar Im Allgemeinen und sogar für Funktionen mit endlichen Domänen oft unlösbar. Aus diesem Grund implementiert keine Programmiersprache die Funktion Gleichheit als Erweiterungsgleichheit.

Intensionale Gleichheit

Unter intensionale Gleichheit zwei Funktionen f und g werden als gleich angesehen, wenn sie die gleiche "interne Struktur" haben. Diese Art von Gleichheit könnte in umgesetzt werden interpretierte Sprachen durch Vergleich der Quellcode der Funktionskörper (z. Objektcode in kompilierte Sprachen. Die intensionale Gleichheit impliziert eine Erweiterungsgleichheit (unter der Annahme, dass die Funktionen deterministisch sind und keine versteckten Eingaben haben, wie z. Programm zähler oder ein veränderlich Globale Variable.))

Referenzgleichheit

Angesichts der Unpraktik der Implementierung von Erweiterungs- und intensionaler Gleichheit verwenden die meisten Sprachen, die Testfunktionen für die Gleichstellung der Gleichheit verwenden, die Referenzgleichheit. Alle Funktionen oder Schließungen werden eine eindeutige Kennung (normalerweise die Adresse des Funktionsorganisation oder des Verschlusses) zugewiesen, und Gleichheit wird auf der Grundlage der Gleichheit der Kennung entschieden. Zwei separat definierte, aber ansonsten identische Funktionsdefinitionen werden als ungleich angesehen. Referenzielle Gleichheit impliziert eine intensionale und extensionale Gleichheit. Referenzgleichheit bricht Referenztransparenz und wird daher nicht in reinen Sprachen wie Haskell unterstützt.

Typentheorie

Im Typentheoriedie Art der Funktionen, die Werte vom Typ akzeptiert A und zurückgegebene Werte vom Typ B kann geschrieben werden als A → B oder B^A. In dem Curry -Howard -Korrespondenz, Funktionstypen Stehen im Zusammenhang mit logische Implikation; Die Lambda -Abstraktion entspricht der Entladung hypothetischer Annahmen und Funktionsanwendung entspricht der Modus Ponens Inferenzregel. Neben dem üblichen Fall von Programmierfunktionen verwendet die Typtheorie auch erstklassige Funktionen, um zu modellieren assoziative Arrays und ähnlich Datenstrukturen.

Im Kategorie-theoretische Programmkonten über die Verfügbarkeit erstklassiger Funktionen entsprechen der geschlossene Kategorie Annahme. Zum Beispiel die Einfach tippte Lambda -Kalkül entspricht der internen Sprache von Kartesische Kategorien geschlossen.

Sprachunterstützung

Funktionale Programmiersprachen wie z. Erlang, Planen, Ml, Haskell, F#, und Scalaalle haben erstklassige Funktionen. Wann LispelnEine der frühesten funktionalen Sprachen wurde entworfen, und nicht alle Aspekte der erstklassigen Funktionen wurden dann richtig verstanden, was dazu führte, dass Funktionen dynamisch geschrieben wurden. Am später Planen und Common Lisp Dialekte haben lexikalisch abgeschottete erstklassigen Funktionen.

Viele Skriptsprachen, einschließlich Perl, Python, Php, Lua, Tcl/Tk, JavaScript und Io, haben erstklassige Funktionen.

Für imperative Sprachen muss zwischen Algol und seinen Nachkommen wie Pascal, der traditionellen C-Familie und den modernen Müllvarianten unterschieden werden. Die Algol-Familie hat verschachtelte Funktionen und Funktionen höherer Ordnung als Argumente ermöglicht, jedoch nicht als Funktionen höherer Ordnung, die Funktionen als Ergebnisse zurückgeben (mit Ausnahme von Algol 68, was dies zulässt). Der Grund dafür war, dass es nicht bekannt war, wie man mit nicht lokalen Variablen umgeht, wenn eine verschachtelte Funktion zurückgegeben wurde (und Algol 68 in solchen Fällen Laufzeitfehler erzeugt).

Die C -Familie erlaubte beide Funktionen als Argumente als Ergebnis, vermieden jedoch Probleme, indem sie verschachtelte Funktionen nicht unterstützten. (Der GCC-Compiler ermöglicht ihnen als Erweiterung.) Da die Nützlichkeit der Rückkehrfunktionen in erster Linie in der Fähigkeit liegt, verschachtelte Funktionen zurückzugeben, die nicht lokale Variablen erfasst haben, anstatt auf obersten Funktionen zu finden, werden diese Sprachen im Allgemeinen nicht als Ersten angesehen -Klassfunktionen.

Moderne imperative Sprachen unterstützen häufig die Müllsammlung, die die Umsetzung erstklassiger Funktionen machbar macht. Erstklassige Funktionen wurden oft erst in späteren Überarbeitungen der Sprache unterstützt, einschließlich C# 2.0 und Apples Blöcken Erweiterung C, C ++ und Objective-C. C ++ 11 hat Unterstützung für anonyme Funktionen und Verschlüsse für die Sprache hinzugefügt. Aufgrund des nicht-marmbären gesammelten Charakters der Sprache muss jedoch spezielle Sorgfalt für nicht lokale Variablen in Funktionen als Ergebnisse berücksichtigt werden (siehe unten) ).

C ++

C ++ 11 Schließungen können nicht-lokale Variablen durch Kopierkonstruktion, durch Bezugnahme (ohne ihre Lebensdauer) oder durch durch Kopierkonstruktion erfassen Konstruktion bewegen (Die Variable lebt so lange wie die Schließung). Die erste Option ist sicher, wenn der Verschluss zurückgegeben wird, aber eine Kopie benötigt und nicht verwendet werden kann, um die ursprüngliche Variable zu ändern (die möglicherweise zum Zeitpunkt des Abschlusses aufgerufen wird). Die zweite Option vermeidet möglicherweise eine teure Kopie und ermöglicht die Änderung der ursprünglichen Variablen, ist jedoch unsicher, falls der Verschluss zurückgegeben wird (siehe baumelnde Referenzen). Die dritte Option ist sicher, wenn der Verschluss zurückgegeben wird und keine Kopie benötigt, aber auch nicht zur Änderung der ursprünglichen Variablen verwendet werden kann.

Java

Java 8 Verschlüsse können nur die endgültigen oder "effektiv endgültigen" nicht-lokalen Variablen erfassen. Java Funktionstypen werden als Klassen dargestellt. Anonyme Funktionen nehmen den aus dem Kontext abgeleiteten Typ. Methodenreferenzen sind begrenzt. Weitere Informationen finden Sie unter Anonyme Funktion § Java -Einschränkungen.

Lispeln

Lexikalisch abgebildet Lisp -Varianten unterstützen Schließungen. Dynamisch abgebildet Varianten unterstützen keine Schließungen oder benötigen kein spezielles Konstrukt, um Schließungen zu schaffen.^[22]

Im Common LispDie Kennung einer Funktion im Funktionsnamespace kann nicht als Verweis auf einen erstklassigen Wert verwendet werden. Der Spezialbetreiber Funktion muss verwendet werden, um die Funktion als Wert abzurufen: (Funktion foo) bewertet ein Funktionsobjekt. #'Foo existiert als Kurzbeschreibung. Um ein solches Funktionsobjekt anzuwenden, muss man das verwenden Funcall Funktion: (Funcall #'Foo Bar Baz).

Python

Explizite teilweise Anwendung mit functools.Partial seit Version 2.5 und Operator.Methodcaller Seit Version 2.6.

Rubin

Die Kennung einer regulären "Funktion" in Ruby (was wirklich eine Methode ist) kann nicht als Wert verwendet oder übergeben werden. Es muss zuerst in a abgerufen werden Methode oder Proc Objekt, das als erstklassige Daten verwendet werden soll. Die Syntax zum Aufrufen eines solchen Funktionsobjekts unterscheidet sich vom Aufruf regulärer Methoden.

Verschachtelte Methodendefinitionen nisten nicht den Bereich.

Explizite Currying mit [1].

Siehe auch

• Defunktionalisierung
• bewerten
• Erstklassige Nachricht
• Kappa -Kalkül -ein Formalismus, der erstklassige Funktionen ausschließt
• Mann- oder Jungen -Test
• Teilweise Anwendung

Anmerkungen

Verweise

• Leonidas Fegaras. "Funktionssprachen und Funktionen höherer Ordnung". CSE5317/CSE4305: Design und Bau von Compilern. Universität von Texas in Arlington.

Externe Links

• Erstklassige Funktionen an Rosetta -Code.
• Funktionen höherer Ordnung bei IBM Developerworks