Was sind Kombinatoren und wie werden sie auf Programmierprojekte angewendet? (praktische Erklärung)

Was sind Kombinatoren?

Ich suche:

• eine praktische Erklärung
• Beispiele für ihre Verwendung
• Beispiele dafür, wie Kombinatoren die Qualität / Allgemeinheit von Code verbessern

Ich suche nicht:

• Erklärungen von Kombinatoren, die mir nicht helfen, meine Arbeit zu erledigen (wie der Y-Kombinator)

Aus praktischer Sicht sind Kombinatoren Programmierkonstrukte, mit denen Sie Logikstücke auf interessante und oft fortgeschrittene Weise zusammenstellen können. Ihre Verwendung hängt in der Regel von der Möglichkeit ab, ausführbaren Code in Objekte zu packen, die häufig (aus historischen Gründen) als Lambda-Funktionen oder Lambda-Ausdrücke bezeichnet werden. Ihre Laufleistung kann jedoch variieren.

Ein einfaches Beispiel für einen (nützlichen) Kombinator ist einer, der zwei Lambda-Funktionen ohne Parameter verwendet und eine neue erstellt, die diese nacheinander ausführt. Der eigentliche Kombinator sieht im generischen Pseudocode folgendermaßen aus:

func in_sequence(first, second):
  lambda ():
    first()
    second()

Das Entscheidende, was dies zu einem Kombinator macht, ist die anonyme Funktion (Lambda-Funktion) in der zweiten Zeile; wenn du anrufst

a = in_sequence(f, g)

Das resultierende Objekt a ist nicht das Ergebnis der Ausführung von zuerst f () und dann g (). Es ist jedoch ein Objekt, das Sie später aufrufen können, um f () und g () nacheinander auszuführen:

a() // a is a callable object, i.e. a function without parameters

Sie können auch einen Kombinator haben, der zwei Codeblöcke parallel ausführt:

func in_parallel(first, second):
  lambda ():
    t1 = start_thread(first)
    t2 = start_thread(second)
    wait(t1)
    wait(t2)

Und dann wieder

a = in_parallel(f, g)
a()

Das Coole ist, dass 'in_parallel' und 'in_sequence' beide Kombinatoren mit demselben Typ / derselben Signatur sind, dh beide nehmen zwei parameterlose Funktionsobjekte und geben ein neues zurück. Sie können dann tatsächlich Dinge wie schreiben

a = in_sequence(in_parallel(f, g), in_parallel(h, i))

und es funktioniert wie erwartet.

Grundsätzlich können Sie mit Hilfe von Kombinatoren den Kontrollfluss Ihres Programms (unter anderem) prozedural und flexibel gestalten. Wenn Sie zum Beispiel den Kombinator in_parallel (..) verwenden, um die Parallelität in Ihrem Programm auszuführen, können Sie der Implementierung des Kombinators in_parallel selbst das zugehörige Debugging hinzufügen. Wenn Sie später den Verdacht haben, dass Ihr Programm einen Fehler im Zusammenhang mit Parallelität aufweist, können Sie in_parallel einfach neu implementieren:

in_parallel(first, second):
  in_sequence(first, second)

und mit einem schlag wurden alle parallelen abschnitte in sequentielle umgewandelt!

Kombinatoren sind sehr nützlich, wenn sie richtig eingesetzt werden.

Der Y-Kombinator wird jedoch im wirklichen Leben nicht benötigt. Es ist ein Kombinator, mit dem Sie selbstrekursive Funktionen erstellen können, und Sie können sie problemlos in jeder modernen Sprache ohne den Y-Kombinator erstellen.

Es ist falsch, Y-combinator als etwas zu bezeichnen, das "nicht dazu beiträgt, die Arbeit zu erledigen". Ich habe es bei mehreren Gelegenheiten als sehr nützlich empfunden. Der naheliegendste Fall ist, wenn Sie schnell eine eingebettete interpretierte Sprache booten müssen. Wenn Sie eine minimale Menge von Primitiven bieten, nämlich sequence, select, call, constund closure allocationist es bereits ausreichend für eine vollständige, beliebige komplexe Sprache aufzubauen. Es ist keine spezielle Unterstützung für die Rekursion erforderlich. Sie kann über einen Festkomma-Kombinator hinzugefügt werden. Andernfalls benötigen Sie viel kompliziertere Grundelemente.

Ein weiterer offensichtlicher Fall für Kombinatoren ist die Verschleierung. Ein in den SKI-Kalkül übersetzter Code ist praktisch nicht lesbar. Wenn Sie die Implementierung eines Algorithmus wirklich verschleiern müssen, ziehen Sie die Verwendung von Kombinatoren in Betracht. Hier ein Beispiel .

Und Kombinatoren sind natürlich ein wichtiges Werkzeug für die Implementierung funktionaler Sprachen. Der einfachste Ansatz (wie im obigen Beispiel) ist über SKI oder eine entsprechende Berechnung. Superkombinatoren werden in einigen anderen Implementierungen verwendet. In diesem Buch wird ausführlich darüber gesprochen.

Dies ist ein Witz , aber ein Witz, der eine sehr sorgfältige Lektüre wert ist, da dort viele arkane Programmiertechniken und Theorien behandelt werden.

Beim Stöbern habe ich eine StackOverflow-Frage gefunden, eine gute Erklärung für „Combinators“ (für Nicht-Mathematiker) , die ein enger Verwandter dieser Frage ist. Eine der Antworten wies auf Reginald Braithwaites Blog Homoiconic hin , der auf einige nützliche Beispiele für Kombinatoren im Code verweist (z. B. den nach Rubys Object#tapMethode implementierten K-Kombinator - lesen Sie auf der Seite nach, warum er nützlich ist).

Die Wikipedia-Seite zu Combinatory Logic beschreibt Kombinatoren globaler.