it-swarm-eu.dev

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

Was sind Kombinatoren?

Ich suche:

  • eine praktische Erklärung
  • beispiele, wie sie verwendet werden
  • 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)
53
user39685

Aus praktischer Sicht sind Kombinatoren eine Art Programmierkonstrukt, mit dem Sie Logikelemente auf interessante und oft fortgeschrittene Weise zusammenstellen können. Die 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. Ihr Kilometerstand kann jedoch variieren.

Ein einfaches Beispiel für einen (nützlichen) Kombinator ist einer, der zwei Lambda-Funktionen ohne Parameter übernimmt und eine neue erstellt, die sie 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, wenn zuerst f() und dann g () ausgeführt wird. Es ist jedoch ein Objekt, das Sie später aufrufen können, um f() auszuführen. und g() nacheinander:

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

In ähnlicher Weise können Sie dann einen Kombinator verwenden, 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, d. H. 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 Kombinatoren den Kontrollfluss Ihres Programms (unter anderem) prozedural und flexibel gestalten. Wenn Sie beispielsweise den Kombinator in_parallel (..) verwenden, um Parallelität in Ihrem Programm auszuführen, können Sie der Implementierung des Kombinators in_parallel selbst ein diesbezügliches Debugging hinzufügen. Wenn Sie später den Verdacht haben, dass Ihr Programm einen Parallelitätsfehler aufweist, können Sie in_parallel einfach neu implementieren:

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

und mit einem Strich wurden alle parallelen Abschnitte in sequentielle umgewandelt!

Kombinatoren sind sehr nützlich, wenn sie richtig verwendet 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 ohne den Y-Kombinator problemlos in jeder modernen Sprache erstellen.

56
antti.huima

Es ist falsch, den Y-Kombinator als etwas zu brandmarken, das "nicht dazu beiträgt, die Arbeit zu erledigen". Ich habe es bei einer Reihe von Gelegenheiten sehr nützlich gefunden. Der offensichtlichste Fall ist, wenn Sie schnell bootstrap eine eingebettete interpretierte Sprache) ausführen müssen. Wenn Sie einen minimalen Satz von Grundelementen bereitstellen, nämlich sequence, select, call, const und ein closure allocation reicht es bereits aus, um eine vollständige, willkürlich komplexe Sprache aufzubauen. Es ist keine spezielle Unterstützung für die Rekursion erforderlich - sie kann über einen Festpunktkombinator 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 eine Implementierung eines Algorithmus wirklich verschleiern müssen, sollten Sie Kombinatoren verwenden, hier ein Beispiel .

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 äquivalente Berechnung. Superkombinatoren werden in einigen anderen Implementierungen verwendet. Dieses Buch spricht ausführlich darüber.

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.

10
SK-logic

Beim Stöbern fand ich eine StackOverflow-Frage, Gute Erklärung für „Kombinatoren“ (für Nicht-Mathematiker) das ist ein enger Verwandter dieser Frage. Eine der Antworten zeigte auf Reginald Braithwaites Blog Homoiconic , der auf mehrere nützliche Beispiele für Kombinatoren im Code verweist (z. B. der K-Kombinator , implementiert von Ruby's Object#tap Methode - Lesen Sie auf der Seite Beispiele, warum dies nützlich ist.

Die Wikipedia-Seite zu Combinatory Logic beschreibt Kombinatoren globaler.

8
Aidan Cully