Erstklassige Funktion - First-class function

In der Informatik spricht man von erstklassigen Funktionen, wenn eine Programmiersprache Funktionen wie erstklassige Bürger behandelt . Dies bedeutet, dass die Sprache die Übergabe von Funktionen als Argumente an andere Funktionen, die Rückgabe als Werte von anderen Funktionen und die Zuweisung an Variablen oder das Speichern in Datenstrukturen unterstützt. Einige Programmiersprachentheoretiker benötigen auch Unterstützung für anonyme Funktionen (Funktionsliterale). In Sprachen mit erstklassigen Funktionen haben die Namen von Funktionen keinen Sonderstatus; sie werden wie gewöhnliche Variablen mit einem Funktionstyp behandelt . Der Begriff wurde Mitte der 1960er Jahre von Christopher Strachey im Zusammenhang mit „Funktionen als Bürger erster Klasse“ geprägt.

Erstklassige Funktionen sind eine Notwendigkeit für den funktionalen Programmierstil , bei dem die Verwendung höherwertiger Funktionen gängige Praxis ist. Ein einfaches Beispiel für eine Funktion höherer Ordnung ist die map- Funktion, die als Argumente eine Funktion und eine Liste verwendet und die durch Anwenden der Funktion auf jedes Mitglied der Liste gebildete Liste zurückgibt. Damit eine Sprache map unterstützt , muss sie die Übergabe einer Funktion als Argument unterstützen.

Es gibt bestimmte Implementierungsschwierigkeiten bei der Übergabe von Funktionen als Argumente oder der Rückgabe als Ergebnis, insbesondere wenn nicht-lokale Variablen in verschachtelten und anonymen Funktionen eingeführt werden . Historisch wurden diese als Funarg-Probleme bezeichnet , der Name kommt von "Funktionsargument". In frühen imperativen Sprachen wurden diese Probleme dadurch vermieden, dass entweder Funktionen als Ergebnistypen nicht unterstützt wurden (zB ALGOL 60 , Pascal ) oder verschachtelte Funktionen und damit nicht-lokale Variablen (zB C ) weggelassen wurden . Die frühe funktionale Sprache Lisp verfolgte den Ansatz des dynamischen Bereichs , bei dem sich nicht-lokale Variablen auf die nächste Definition dieser Variablen an dem Punkt beziehen, an dem die Funktion ausgeführt wird, anstatt dort, wo sie definiert wurde. Die richtige Unterstützung für First-Class-Funktionen mit lexikalischem Geltungsbereich wurde in Scheme eingeführt und erfordert, dass Referenzen auf Funktionen als Closures statt als bloße Funktionszeiger behandelt werden , was wiederum eine Garbage Collection erforderlich macht.

Konzepte

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

Funktionen höherer Ordnung: Funktionen als Argumente übergeben

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

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

Sprachen, in denen Funktionen nicht erstklassig sind, ermöglichen es oft trotzdem, Funktionen höherer Ordnung durch die Verwendung von Funktionen wie Funktionszeigern oder Delegaten zu schreiben . In der Sprache C :

void map(int (*f)(int), int x[], size_t n) {
    for (int i = 0; i < n; i++)
        x[i] = f(x[i]);
}

Es gibt eine Reihe von Unterschieden zwischen den beiden Ansätzen, die nicht direkt mit der Unterstützung erstklassiger Funktionen zusammenhängen. Das Haskell-Beispiel arbeitet mit Listen , während das C-Beispiel mit Arrays arbeitet . Beides sind die natürlichsten zusammengesetzten Datenstrukturen in den jeweiligen Sprachen, und die Verwendung des C-Beispiels mit verknüpften Listen hätte es unnötig komplex gemacht. Dies berücksichtigt auch die Tatsache, dass die C-Funktion einen zusätzlichen Parameter benötigt (der die Größe des Arrays angibt). Die C-Funktion aktualisiert das Array an Ort und Stelle und gibt keinen Wert zurück, während in Haskell Datenstrukturen persistent sind (eine neue Liste wird zurückgegeben während das alte intakt gelassen wird.) Das Haskell-Beispiel verwendet Rekursion , um die Liste zu durchlaufen, während das C-Beispiel iteration verwendet . Dies ist wiederum die natürlichste Art, diese Funktion in beiden Sprachen auszudrücken, aber das Haskell-Beispiel hätte leicht als Faltung und das C-Beispiel als Rekursion ausgedrückt werden können. Schließlich hat die Haskell-Funktion einen polymorphen Typ, da dieser von C nicht unterstützt wird, haben wir alle Typvariablen auf den Typ constant fixiert 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:

main = map (\x -> 3 * x + 1) [1, 2, 3, 4, 5]

In einer Sprache, die keine anonymen Funktionen unterstützt, müssen wir sie stattdessen an einen Namen binden:

int f(int x) {
    return 3 * x + 1;
}

int main() {
    int list[] = {1, 2, 3, 4, 5};
    map(f, list, 5);
}

Nicht-lokale Variablen und Closures

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

main = let a = 3
           b = 1
        in map (\x -> a * x + b) [1, 2, 3, 4, 5]

Wenn Funktionen mit bloßen Funktionszeigern dargestellt werden, können wir nicht mehr wissen, wie der Wert außerhalb des Funktionsrumpfs übergeben werden soll, und deshalb muss eine Closure manuell erstellt werden. Daher kann hier nicht von "erstklassigen" Funktionen gesprochen werden.

typedef struct {
    int (*f)(int, int, int);
    int *a;
    int *b;
} closure_t;

void map(closure_t *closure, int x[], size_t n) {
    for (int i = 0; i < n; ++i)
        x[i] = (*closure->f)(*closure->a, *closure->b, x[i]);
}

int f(int a, int b, int x) {
    return a * x + b;
}

void main() {
    int l[] = {1, 2, 3, 4, 5};
    int a = 3;
    int b = 1;
    closure_t closure = {f, &a, &b};
    map(&closure, l, 5);
}

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

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

Wenn wir eine Funktion zurückgeben, geben wir tatsächlich ihren Abschluss zurück. Im C-Beispiel werden alle lokalen Variablen, die von der Closure erfasst werden, den Gültigkeitsbereich verlassen, sobald wir von der Funktion zurückkehren, die die Closure erstellt. Das Erzwingen des Schließens zu einem späteren Zeitpunkt führt zu undefiniertem Verhalten, das möglicherweise den Stack beschädigt. Dies ist als das Aufwärts-Funarg-Problem bekannt .

Variablen Funktionen zuweisen

Das Zuweisen von Funktionen zu Variablen und deren Speicherung in (globalen) Datenstrukturen hat möglicherweise die gleichen Schwierigkeiten wie das Zurückgeben von Funktionen.

f :: [[Integer] -> [Integer]]
f = let a = 3
        b = 1
     in [map (\x -> a * x + b), map (\x -> b * x + a)]

Gleichheit der Funktionen

Da man die meisten Literale und Werte auf Gleichheit testen kann, ist es naheliegend zu fragen, ob eine Programmiersprache das Testen von Funktionen auf Gleichheit unterstützen kann. Bei näherer Betrachtung erscheint diese Frage schwieriger und man muss zwischen mehreren Arten von Funktionsgleichheit unterscheiden:

Dehnungsgleichheit

Zwei Funktionen f und g werden als extensional gleich betrachtet, wenn sie in ihren Ausgaben für alle Eingaben übereinstimmen (∀ x . f ( x ) = g ( x )). Unter dieser Definition von Gleichheit würden beispielsweise zwei beliebige Implementierungen eines stabilen Sortieralgorithmus , wie beispielsweise Einfügungssortierung und Zusammenführungssortierung , als gleich betrachtet. Die Entscheidung über Extensionsgleichheit ist im Allgemeinen unentscheidbar und sogar für Funktionen mit endlichen Domänen oft schwer zu handhaben. Aus diesem Grund implementiert keine Programmiersprache Funktionsgleichheit als Extensionsgleichheit.

Intensionale Gleichheit

Bei intensionaler Gleichheit gelten zwei Funktionen f und g als gleich, wenn sie die gleiche "innere Struktur" haben. Diese Art von Gleichheit könnte in interpretierten Sprachen implementiert werden, indem man den Quellcode der Funktionskörper (wie in Interpreted Lisp 1.5) oder den Objektcode in kompilierten Sprachen vergleicht . Intensionale Gleichheit impliziert extensionale Gleichheit (vorausgesetzt, die Funktionen sind deterministisch und haben keine versteckten Eingaben, wie den Programmzähler oder eine veränderbare globale Variable .)

Referenzgleichheit

Da die Implementierung von extensionaler und intensionaler Gleichheit nicht praktikabel ist, verwenden die meisten Sprachen, die Testfunktionen für Gleichheit unterstützen, Referenzgleichheit. Allen Funktionen oder Closures wird ein eindeutiger Bezeichner zugewiesen (normalerweise die Adresse des Funktionsrumpfs oder des Closures) und die Gleichheit wird basierend auf der Gleichheit des Bezeichners entschieden. Zwei getrennt definierte, aber ansonsten identische Funktionsdefinitionen werden als ungleich betrachtet. Referentielle Gleichheit impliziert intensionale und extensionale Gleichheit. Referentielle Gleichheit unterbricht die referenzielle Transparenz und wird daher in reinen Sprachen wie Haskell nicht unterstützt .

Typentheorie

In der Typentheorie kann der Typ von Funktionen, die Werte des Typs A akzeptieren und Werte des Typs B zurückgeben , als A → B oder B ^{A geschrieben werden} . In der Curry-Howard Korrespondenz , Funktionstypen sind im Zusammenhang logische Implikation ; Die Lambda-Abstraktion entspricht dem Entladen hypothetischer Annahmen und die Funktionsanwendung entspricht der Modus-Ponens- Inferenzregel. Neben dem üblichen Fall des Programmierens von Funktionen verwendet die Typtheorie auch erstklassige Funktionen, um assoziative Arrays und ähnliche Datenstrukturen zu modellieren .

In kategorietheoretischen Darstellungen der Programmierung entspricht die Verfügbarkeit erstklassiger Funktionen der geschlossenen Kategorieannahme . Zum Beispiel entspricht der einfach typisierte Lambda-Kalkül der internen Sprache der kartesischen geschlossenen Kategorien .

Sprachunterstützung

Funktionale Programmiersprachen wie Scheme , ML , Haskell , F# und Scala verfügen alle über erstklassige Funktionen. Als Lisp , eine der frühesten funktionalen Sprachen, entworfen wurde, wurden nicht alle Aspekte erstklassiger Funktionen richtig verstanden, was dazu führte, dass Funktionen dynamisch begrenzt wurden. Die späteren Dialekte Scheme und Common Lisp haben erstklassige Funktionen mit lexikalischem Geltungsbereich.

Viele Skriptsprachen, darunter Perl , Python , PHP , Lua , Tcl /Tk, JavaScript und Io , verfügen über erstklassige Funktionen.

Bei imperativen Sprachen muss zwischen Algol und seinen Nachkommen wie Pascal, der traditionellen C-Familie und den modernen Garbage-Collected-Varianten unterschieden werden. Die Algol-Familie hat verschachtelte Funktionen und Funktionen höherer Ordnung als Argumente zugelassen, aber keine Funktionen höherer Ordnung, die Funktionen als Ergebnisse zurückgeben (außer Algol 68, das dies ermöglicht). Der Grund dafür war, dass nicht bekannt war, wie mit nicht-lokalen Variablen umgegangen werden sollte, wenn als Ergebnis eine nested-Funktion zurückgegeben wurde (und Algol 68 erzeugt in solchen Fällen Laufzeitfehler).

Die C-Familie erlaubte sowohl die Übergabe von Funktionen als Argumente als auch die Rückgabe als Ergebnis, vermied jedoch alle Probleme, indem sie keine verschachtelten Funktionen unterstützte. (Der gcc-Compiler erlaubt sie als Erweiterung.) Da der Nutzen von Rückgabefunktionen hauptsächlich darin liegt, verschachtelte Funktionen zurückzugeben, die nicht-lokale Variablen erfasst haben, werden diese Sprachen im Allgemeinen nicht als Funktionen auf oberster Ebene angesehen -Klassenfunktionen.

Moderne imperative Sprachen unterstützen oft die Garbage-Collection, wodurch die Implementierung erstklassiger Funktionen möglich wird. Erstklassige Funktionen wurden oft erst in späteren Überarbeitungen der Sprache unterstützt, einschließlich C# 2.0 und Apples Blocks-Erweiterung für C, C++ und Objective-C. C++11 hat die Unterstützung für anonyme Funktionen und Closures der Sprache hinzugefügt, aber wegen der Nicht-Garbage-Sammlung der Sprache muss besonders darauf geachtet werden, dass nicht-lokale Variablen in Funktionen als Ergebnisse zurückgegeben werden (siehe unten ).

C++

C++11- Closures können nicht-lokale Variablen durch Copy-Konstruktion, durch Referenz (ohne ihre Lebensdauer zu verlängern) oder durch Move-Konstruktion (die Variable lebt so lange wie die Closure) erfassen . Die erste Option ist sicher, wenn die Closure zurückgegeben wird, aber eine Kopie erfordert und nicht verwendet werden kann, um die ursprüngliche Variable zu ändern (die zum Zeitpunkt des Aufrufs der Closure möglicherweise nicht mehr existiert). Die zweite Option vermeidet möglicherweise eine teure Kopie und ermöglicht es, die ursprüngliche Variable zu ändern, ist jedoch unsicher, falls die Closure zurückgegeben wird (siehe Dangling References ). Die dritte Option ist sicher, wenn die Closure zurückgegeben wird und keine Kopie erfordert, aber auch nicht zum Ändern der Originalvariablen verwendet werden kann.

Java

Java 8 Closures können nur finale oder "effektiv finale" nicht-lokale Variablen erfassen. Die Funktionstypen von Java werden als Klassen dargestellt. Anonyme Funktionen übernehmen den aus dem Kontext abgeleiteten Typ. Methodenreferenzen sind begrenzt. Weitere Informationen finden Sie unter Anonyme Funktion § Java-Einschränkungen .

Lispeln

Lisp-Varianten mit lexikalischem Umfang unterstützen Closures. Varianten mit dynamischem Geltungsbereich unterstützen keine Closures oder benötigen ein spezielles Konstrukt, um Closures zu erstellen.

In Common Lisp kann der Bezeichner einer Funktion im Funktionsnamensraum nicht als Verweis auf einen erstklassigen Wert verwendet werden. Der spezielle Operator functionmuss verwendet werden, um die Funktion als Wert abzurufen: wird (function foo)zu einem Funktionsobjekt ausgewertet. #'fooexistiert als Kurzschreibweise. Um ein solches Funktionsobjekt anzuwenden, muss man die funcallFunktion verwenden: (funcall #'foo bar baz).

Python

Explizite Teilanwendung mit functools.partialseit Version 2.5, und operator.methodcallerseit Version 2.6.

Rubin

Der Bezeichner einer regulären "Funktion" in Ruby (die eigentlich eine Methode ist) kann nicht als Wert verwendet oder übergeben werden. Sie müssen zuerst in ein Methododer Proc-Objekt abgerufen werden , um als erstklassige Daten verwendet zu werden. Die Syntax zum Aufrufen eines solchen Funktionsobjekts unterscheidet sich vom Aufruf regulärer Methoden.

Verschachtelte Methodendefinitionen verschachteln den Gültigkeitsbereich nicht wirklich.

Explizites Curry mit [1].

Siehe auch

• Defunktionalisierung
• bewerten
• Erstklassige Nachricht
• Kappa-Kalkül – ein Formalismus, der erstklassige Funktionen ausschließt
• Mann- oder Jungentest
• Teilantrag

Anmerkungen

Verweise

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

Externe Links

• Erstklassige Funktionen auf Rosetta Code .
• Funktionen höherer Ordnung bei IBM developerWorks