Funktionszeiger, Closures und Lambda

Ich lerne gerade etwas über Funktionszeiger und als ich das K & R-Kapitel zu diesem Thema las, war das erste, was mich traf: "Hey, das ist ein bisschen wie ein Abschluss." Ich wusste, dass diese Annahme irgendwie grundlegend falsch ist und nach einer Online-Suche fand ich keine Analyse dieses Vergleichs.

Warum unterscheiden sich Funktionszeiger im C-Stil grundlegend von Verschlüssen oder Lambdas? Soweit ich das beurteilen kann, hat dies damit zu tun, dass der Funktionszeiger immer noch auf eine definierte (benannte) Funktion zeigt, im Gegensatz zu der Praxis, die Funktion anonym zu definieren.

Warum wird die Übergabe einer Funktion an eine Funktion im zweiten Fall, in dem sie nicht benannt ist, als leistungsfähiger angesehen als im ersten Fall, in dem nur eine normale, alltägliche Funktion übergeben wird?

Bitte sagen Sie mir, wie und warum ich falsch liege, die beiden so genau zu vergleichen.

Vielen Dank.

Ein Lambda (oder Abschluss ) kapselt sowohl den Funktionszeiger als auch die Variablen. Aus diesem Grund können Sie in C # Folgendes tun:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

Ich habe dort einen anonymen Delegaten als Abschluss verwendet (die Syntax ist etwas klarer und näher an C als das Lambda-Äquivalent), der lessThan (eine Stapelvariable) in den Abschluss aufgenommen hat. Wenn der Abschluss ausgewertet wird, wird weiterhin auf lessThan (dessen Stapelrahmen möglicherweise zerstört wurde) weiter verwiesen. Wenn ich weniger als ändere, ändere ich den Vergleich:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

lessThanTest(99); // returns true
lessThan = 10;
lessThanTest(99); // returns false

In C wäre dies illegal:

BOOL (*lessThanTest)(int);
int lessThan = 100;

lessThanTest = &LessThan;

BOOL LessThan(int i) {
   return i < lessThan; // compile error - lessThan is not in scope
}

obwohl ich einen Funktionszeiger definieren könnte, der 2 Argumente akzeptiert:

int lessThan = 100;
BOOL (*lessThanTest)(int, int);

lessThanTest = &LessThan;
lessThanTest(99, lessThan); // returns true
lessThan = 10;
lessThanTest(100, lessThan); // returns false

BOOL LessThan(int i, int lessThan) {
   return i < lessThan;
}

Aber jetzt muss ich die 2 Argumente übergeben, wenn ich es bewerte. Wenn ich diesen Funktionszeiger an eine andere Funktion übergeben möchte, bei der lessThan nicht im Geltungsbereich liegt, müsste ich ihn entweder manuell am Leben erhalten, indem ich ihn an jede Funktion in der Kette übergebe oder ihn an eine globale Funktion heraufstufte.

Obwohl die meisten gängigen Sprachen, die Schließungen unterstützen, anonyme Funktionen verwenden, ist dies nicht erforderlich. Sie können Schließungen ohne anonyme Funktionen und anonyme Funktionen ohne Schließungen haben.

Zusammenfassung: Ein Abschluss ist eine Kombination aus Funktionszeiger und erfassten Variablen.

Als jemand, der Compiler für Sprachen mit und ohne "echte" Verschlüsse geschrieben hat, bin ich mit einigen der obigen Antworten respektvoll nicht einverstanden. Ein Lisp-, Scheme-, ML- oder Haskell-Verschluss erstellt keine neue Funktion dynamisch . Stattdessen wird eine vorhandene Funktion wiederverwendet , jedoch mit neuen freien Variablen . Die Sammlung freier Variablen wird oft als Umgebung bezeichnet , zumindest von Theoretikern der Programmiersprache.

Ein Abschluss ist nur ein Aggregat, das eine Funktion und eine Umgebung enthält. Im Standard ML of New Jersey Compiler haben wir einen als Rekord dargestellt; Ein Feld enthielt einen Zeiger auf den Code, und die anderen Felder enthielten die Werte der freien Variablen. Der Compiler hat dynamisch einen neuen Abschluss (keine Funktion) erstellt, indem er einen neuen Datensatz zugewiesen hat, der einen Zeiger auf denselben Code enthält, jedoch unterschiedliche Werte für die freien Variablen aufweist.

Sie können dies alles in C simulieren, aber es ist ein Schmerz im Arsch. Zwei Techniken sind beliebt:

1. Übergeben Sie einen Zeiger auf die Funktion (den Code) und einen separaten Zeiger auf die freien Variablen, sodass der Abschluss auf zwei C-Variablen aufgeteilt wird.

2. Übergeben Sie einen Zeiger auf eine Struktur, wobei die Struktur die Werte der freien Variablen sowie einen Zeiger auf den Code enthält.

Technik Nr. 1 ist ideal, wenn Sie versuchen, eine Art Polymorphismus in C zu simulieren, und Sie den Typ der Umgebung nicht offenlegen möchten - Sie verwenden einen void * -Zeiger, um die Umgebung darzustellen. Beispiele finden Sie in Dave Hansons C-Schnittstellen und -Implementierungen . Technik Nr. 2, die eher dem ähnelt, was in nativen Code-Compilern für funktionale Sprachen geschieht, ähnelt auch einer anderen bekannten Technik ... C ++ - Objekten mit virtuellen Elementfunktionen. Die Implementierungen sind nahezu identisch.

Diese Beobachtung führte zu einem Wisecrack von Henry Baker:

Die Menschen in der Welt von Algol / Fortran beklagten sich jahrelang darüber, dass sie nicht verstanden hätten, welche möglichen Funktionen Funktionsschließungen für eine effiziente Programmierung der Zukunft haben würden. Dann geschah die Revolution der "objektorientierten Programmierung", und jetzt programmieren alle mit Funktionsabschlüssen, außer dass sie sich immer noch weigern, sie so zu nennen.

In C können Sie die Funktion nicht inline definieren, sodass Sie keinen Abschluss erstellen können. Sie geben lediglich einen Verweis auf eine vordefinierte Methode weiter. In Sprachen, die anonyme Methoden / Abschlüsse unterstützen, ist die Definition der Methoden viel flexibler.

Im einfachsten Fall ist Funktionszeigern kein Bereich zugeordnet (es sei denn, Sie zählen den globalen Bereich), wohingegen Abschlüsse den Bereich der Methode enthalten, die sie definiert. Mit Lambdas können Sie eine Methode schreiben, die eine Methode schreibt. Mit Closures können Sie "einige Argumente an eine Funktion binden und dadurch eine Funktion mit niedrigerer Arität erhalten". (entnommen aus Thomas 'Kommentar). Das kann man in C nicht machen.

BEARBEITEN: Hinzufügen eines Beispiels (Ich werde die Actionscript-artige Syntax verwenden, da ich gerade daran denke):

Angenommen, Sie haben eine Methode, die eine andere Methode als Argument verwendet, aber keine Möglichkeit bietet, Parameter an diese Methode zu übergeben, wenn sie aufgerufen wird? Wie zum Beispiel eine Methode, die eine Verzögerung verursacht, bevor die Methode ausgeführt wird, die Sie übergeben haben (dummes Beispiel, aber ich möchte es einfach halten).

function runLater(f:Function):Void {
  sleep(100);
  f();
}

Angenommen, Sie möchten runLater () verwenden, um die Verarbeitung eines Objekts zu verzögern:

function objectProcessor(o:Object):Void {
  /* Do something cool with the object! */
}

function process(o:Object):Void {
  runLater(function() { objectProcessor(o); });
}

Die Funktion, die Sie an process () übergeben, ist keine statisch definierte Funktion mehr. Es wird dynamisch generiert und kann Verweise auf Variablen enthalten, die zum Zeitpunkt der Definition der Methode im Gültigkeitsbereich waren. Es kann also auf 'o' und 'objectProcessor' zugreifen, obwohl diese nicht im globalen Bereich liegen.

Ich hoffe das hat Sinn gemacht.

Schließung = Logik + Umgebung.

Betrachten Sie beispielsweise diese C # 3-Methode:

public Person FindPerson(IEnumerable<Person> people, string name)
{
    return people.Where(person => person.Name == name);
}

Der Lambda-Ausdruck kapselt nicht nur die Logik ("Vergleiche den Namen"), sondern auch die Umgebung, einschließlich des Parameters (dh der lokalen Variablen) "Name".

Weitere Informationen hierzu finden Sie in meinem Artikel über Verschlüsse, der Sie durch C # 1, 2 und 3 führt und zeigt, wie Verschlüsse die Dinge einfacher machen.

In C können Funktionszeiger als Argumente an Funktionen übergeben und als Werte von Funktionen zurückgegeben werden. Funktionen sind jedoch nur auf oberster Ebene vorhanden: Sie können Funktionsdefinitionen nicht ineinander verschachteln. Überlegen Sie, was C benötigt, um verschachtelte Funktionen zu unterstützen, die auf die Variablen der äußeren Funktion zugreifen können, und gleichzeitig Funktionszeiger im Aufrufstapel nach oben und unten senden können. (Um dieser Erklärung zu folgen, sollten Sie die Grundlagen der Implementierung von Funktionsaufrufen in C und den meisten ähnlichen Sprachen kennen: Durchsuchen Sie den Aufrufstapeleintrag auf Wikipedia.)

Was für ein Objekt ist ein Zeiger auf eine verschachtelte Funktion? Es kann nicht nur die Adresse des Codes sein, denn wenn Sie ihn aufrufen, wie greift er auf die Variablen der äußeren Funktion zu? (Denken Sie daran, dass aufgrund der Rekursion möglicherweise mehrere verschiedene Aufrufe der äußeren Funktion gleichzeitig aktiv sind.) Dies wird als Funarg-Problem bezeichnet , und es gibt zwei Unterprobleme: das Downward-Funargs-Problem und das Upward-Funargs-Problem.

Das Problem der Abwärtsfunktionen, dh das Senden eines Funktionszeigers "den Stapel hinunter" als Argument an eine von Ihnen aufgerufene Funktion, ist tatsächlich nicht mit C und GCC inkompatibel unterstützt verschachtelte Funktionen als Abwärtsfunktionen. Wenn Sie in GCC einen Zeiger auf eine verschachtelte Funktion erstellen, erhalten Sie tatsächlich einen Zeiger auf ein Trampolin , einen dynamisch aufgebauten Code, der den statischen Linkzeiger einrichtet und dann die reale Funktion aufruft, die den statischen Linkzeiger für den Zugriff verwendet die Variablen der äußeren Funktion.

Das Problem mit den Aufwärtsfunktionen ist schwieriger. GCC hindert Sie nicht daran, einen Trampolinzeiger existieren zu lassen, nachdem die äußere Funktion nicht mehr aktiv ist (hat keinen Datensatz auf dem Aufrufstapel), und dann könnte der statische Verbindungszeiger auf Müll zeigen. Aktivierungsdatensätze können nicht mehr auf einem Stapel zugeordnet werden. Die übliche Lösung besteht darin, sie auf dem Heap zuzuweisen und ein Funktionsobjekt, das eine verschachtelte Funktion darstellt, nur auf den Aktivierungsdatensatz der äußeren Funktion verweisen zu lassen. Ein solches Objekt wird als Verschluss bezeichnet . Dann muss die Sprache normalerweise die Speicherbereinigung unterstützen, damit die Datensätze freigegeben werden können, sobald keine Zeiger mehr auf sie verweisen.

Lambdas ( anonyme Funktionen ) sind eigentlich ein separates Problem, aber normalerweise können Sie sie in einer Sprache, in der Sie anonyme Funktionen im laufenden Betrieb definieren können, auch als Funktionswerte zurückgeben, sodass sie letztendlich geschlossen werden.

Ein Lambda ist eine anonyme, dynamisch definierte Funktion. In C ... kann man das einfach nicht tun. Was Verschlüsse (oder die Überzeugung der beiden) betrifft, würde das typische Lisp-Beispiel ungefähr so ​​aussehen:

(defun get-counter (n-start +-number)
     "Returns a function that returns a number incremented
      by +-number every time it is called"
    (lambda () (setf n-start (+ +-number n-start))))

In C-Begriffen könnte man sagen, dass die lexikalische Umgebung (der Stapel) von get-countervon der anonymen Funktion erfasst und intern geändert wird, wie das folgende Beispiel zeigt:

[1]> (defun get-counter (n-start +-number)
         "Returns a function that returns a number incremented
          by +-number every time it is called"
        (lambda () (setf n-start (+ +-number n-start))))
GET-COUNTER
[2]> (defvar x (get-counter 2 3))
X
[3]> (funcall x)
5
[4]> (funcall x)
8
[5]> (funcall x)
11
[6]> (funcall x)
14
[7]> (funcall x)
17
[8]> (funcall x)
20
[9]> 

Verschlüsse implizieren, dass eine Variable vom Standpunkt der Funktionsdefinition mit der Funktionslogik verbunden ist, beispielsweise die Möglichkeit, ein Mini-Objekt im laufenden Betrieb zu deklarieren.

Ein wichtiges Problem bei C und Schließungen besteht darin, dass auf dem Stapel zugewiesene Variablen beim Verlassen des aktuellen Bereichs zerstört werden, unabhängig davon, ob eine Schließung auf sie zeigte. Dies würde zu der Art von Fehlern führen, die Menschen erhalten, wenn sie achtlos Zeiger auf lokale Variablen zurückgeben. Schließungen implizieren grundsätzlich, dass alle relevanten Variablen entweder nachgezählt oder durch Müll gesammelte Elemente auf einem Haufen sind.

Ich bin nicht zufrieden damit, Lambda mit Closure gleichzusetzen, weil ich nicht sicher bin, ob Lambdas in allen Sprachen Closures sind. Manchmal denke ich, dass Lambdas nur lokal definierte anonyme Funktionen ohne Bindung von Variablen sind (Python vor 2.1?).

In GCC ist es möglich, Lambda-Funktionen mit dem folgenden Makro zu simulieren:

#define lambda(l_ret_type, l_arguments, l_body)       \
({                                                    \
    l_ret_type l_anonymous_functions_name l_arguments \
    l_body                                            \
    &l_anonymous_functions_name;                      \
})

Beispiel aus der Quelle :

qsort (array, sizeof (array) / sizeof (array[0]), sizeof (array[0]),
     lambda (int, (const void *a, const void *b),
             {
               dump ();
               printf ("Comparison %d: %d and %d\n",
                       ++ comparison, *(const int *) a, *(const int *) b);
               return *(const int *) a - *(const int *) b;
             }));

Die Verwendung dieser Technik beseitigt natürlich die Möglichkeit, dass Ihre Anwendung mit anderen Compilern zusammenarbeitet, und ist anscheinend "undefiniertes" Verhalten, also YMMV.

Der Abschluss erfasst die freien Variablen in einer Umgebung . Die Umgebung bleibt bestehen, auch wenn der umgebende Code möglicherweise nicht mehr aktiv ist.

Ein Beispiel in Common Lisp, wo MAKE-ADDERein neuer Abschluss zurückgegeben wird.

CL-USER 53 > (defun make-adder (start delta) (lambda () (incf start delta)))
MAKE-ADDER

CL-USER 54 > (compile *)
MAKE-ADDER
NIL
NIL

Verwenden der obigen Funktion:

CL-USER 55 > (let ((adder1 (make-adder 0 10))
                   (adder2 (make-adder 17 20)))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder1))
               (print (funcall adder1))
               (describe adder1)
               (describe adder2)
               (values))

10 
20 
30 
40 
37 
57 
77 
50 
60 
#<Closure 1 subfunction of MAKE-ADDER 4060001ED4> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(60 10)
#<Closure 1 subfunction of MAKE-ADDER 4060001EFC> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(77 20)

Beachten Sie, dass die DESCRIBEFunktion zeigt, dass die Funktionsobjekte für beide Abschlüsse gleich sind, die Umgebung jedoch unterschiedlich ist.

Common Lisp macht sowohl Closures als auch reine Funktionsobjekte (solche ohne Umgebung) zu Funktionen, und man kann beide auf die gleiche Weise aufrufen, hier mit FUNCALL.

Der Hauptunterschied ergibt sich aus dem Mangel an lexikalischem Scoping in C.

Ein Funktionszeiger ist genau das, ein Zeiger auf einen Codeblock. Jede Nicht-Stack-Variable, auf die verwiesen wird, ist global, statisch oder ähnlich.

Ein Abschluss, OTOH, hat seinen eigenen Zustand in Form von "äußeren Variablen" oder "Aufwärtswerten". Sie können mit lexikalischem Umfang so privat oder geteilt sein, wie Sie möchten. Sie können viele Abschlüsse mit demselben Funktionscode, aber unterschiedlichen Variableninstanzen erstellen.

Einige Abschlüsse können einige Variablen gemeinsam nutzen und somit die Schnittstelle eines Objekts sein (im OOP-Sinne). Um dies in C zu erreichen, müssen Sie einer Tabelle mit Funktionszeigern eine Struktur zuordnen (das macht C ++ mit einer Klasse vtable).

Kurz gesagt, ein Abschluss ist ein Funktionszeiger und ein Zustand. Es ist ein übergeordnetes Konstrukt

Die meisten Antworten weisen darauf hin, dass Schließungen Funktionszeiger erfordern, möglicherweise auf anonyme Funktionen, aber wie Mark schrieb, können Schließungen mit benannten Funktionen existieren. Hier ist ein Beispiel in Perl:

{
    my $count;
    sub increment { return $count++ }
}

Der Abschluss ist die Umgebung, die die $countVariable definiert . Es steht nur der incrementUnterroutine zur Verfügung und bleibt zwischen den Aufrufen bestehen.

In C ist ein Funktionszeiger ein Zeiger, der eine Funktion aufruft, wenn Sie sie dereferenzieren. Ein Abschluss ist ein Wert, der die Logik einer Funktion und die Umgebung (Variablen und die Werte, an die sie gebunden sind) enthält, und ein Lambda bezieht sich normalerweise auf einen Wert, der ist eigentlich eine unbenannte Funktion. In C ist eine Funktion kein erstklassiger Wert, daher kann sie nicht weitergegeben werden, sodass Sie stattdessen einen Zeiger darauf übergeben müssen. In funktionalen Sprachen (wie Schema) können Sie Funktionen jedoch genauso übergeben, wie Sie einen anderen Wert übergeben