Was bedeutet "komponiert nicht"?

35

Ich sehe viele Texte, insbesondere funktionale Programmiertexte, die behaupten, dass bestimmte CS-Konzepte "nicht komponieren" . Beispiele sind: Sperren komponieren nicht, Monaden komponieren nicht.

Es fällt mir schwer, genau die Bedeutung dieses Satzes zu finden. Wenn ich an Komposition denke, denke ich entweder an Funktionskomposition oder an Objektaggregation (wie in "Komposition vor Vererbung bevorzugen"), aber das scheint nicht der Sinn zu sein, in dem die Leute es hier verwenden.

Kann jemand erklären, was dieser Ausdruck bedeutet, wenn er in Ausdrücken wie den beiden obigen (dh Sperren und Monaden) verwendet wird?

Rechnung
quelle
Es hat eine engere Bedeutung für die Funktionszusammensetzung als für die Objektaggregation.
Andres F.
Grob und informell, wenn Sie zwei verschiedene Dinge haben, die Schlösser verwenden, ist es schwierig, sie zusammenzuhalten. (Bei Sperren ist es schwierig, auf Deadlocks zu verzichten. Bei Monaden können die Typen kompliziert werden.)
user253751

Antworten:

35

Wenn Leute sagen "X komponiert nicht", bedeutet "komponieren" eigentlich nur "zusammensetzen", und was und wie man sie zusammensetzt, kann sehr unterschiedlich sein, je nachdem, was genau "X" ist.

Wenn sie "nicht komponieren" sagen, können sie auch ein paar leicht unterschiedliche Dinge bedeuten:

  1. Sie können nicht zwei Xs zusammen, Punkt.
  2. Sie können zwei Xs zusammenfügen, aber das Ergebnis ist möglicherweise kein X (IOW: X ist unter Komposition nicht geschlossen .)
  3. Sie können zwei Xs zusammenfügen, aber das resultierende X funktioniert möglicherweise nicht so, wie Sie es erwarten.

Ein Beispiel für # 1 sind Parser mit Scannern / Lexern. Möglicherweise hören Sie den Satz "Scanner / Lexer komponieren nicht". Das stimmt eigentlich nicht. Was sie bedeuten, ist "Parser, die eine separate Lexing-Stufe verwenden, komponieren nicht".

Warum sollten Sie Parser erstellen? Stellen Sie sich vor, Sie sind ein IDE-Anbieter wie JetBrains, die Eclipse Foundation, Microsoft oder Embarcadero und möchten eine IDE für ein Webframework erstellen. In der typischen Webentwicklung mischen wir oft Sprachen. Sie haben HTML-Dateien mit <script>Elementen, die ECMAScript und enthalten<style>Elemente, die CSS enthalten. Sie haben Vorlagendateien, die HTML, eine Programmiersprache und eine Metasyntax für Vorlagensprachen enthalten. Sie möchten keine unterschiedlichen Syntaxmarker für "Python", "In eine Vorlage eingebettetes Python", "CSS", "CSS in HTML", "ECMASCript", "ECMAScript in HTML", "HTML", "HTML in" schreiben eine Vorlage ", und so weiter und so fort. Sie möchten einen Syntax-Textmarker für Python, einen für HTML und einen für die Vorlagensprache schreiben und die drei dann zu einem Syntax-Textmarker für eine Vorlagendatei zusammensetzen.

Ein Lexer parst jedoch die gesamte Datei in einen Strom von Token, was nur für diese eine Sprache Sinn macht. Der Parser für die andere Sprache kann nicht mit den Tokens arbeiten, die der Lexer übergibt. Beispielsweise werden Python-Parser in der Regel so geschrieben, dass der Lexer die Einrückung nachverfolgt und Fälschungen INDENTund DEDENTToken in den Token-Stream einfügt, sodass der Parser kontextfrei ist, obwohl Pythons Syntax dies nicht ist. Ein HTML-Lexer ignoriert jedoch Whitespace vollständig, da es in HTML keine Bedeutung hat.

Ein scannerloser Parser, der lediglich Zeichen liest, kann den Zeichenstrom an einen anderen Parser weiterleiten, der ihn dann zurückgibt und so die Komposition erheblich vereinfacht.

Ein Beispiel für # 2 sind Zeichenfolgen mit darin enthaltenen SQL-Abfragen. Sie können zwei Zeichenfolgen verwenden, in denen jeweils eine syntaktisch korrekte SQL-Abfrage enthalten ist. Wenn Sie die beiden Zeichenfolgen jedoch verketten, ist das Ergebnis möglicherweise keine syntaktisch korrekte SQL-Abfrage. Deshalb haben wir Abfrage algebras wie ARel, was tun compose.

Schlösser sind ein Beispiel für # 3. Wenn Sie zwei Programme mit Sperren haben und diese zu einem einzigen Programm kombinieren, haben Sie immer noch ein Programm mit Sperren, aber selbst wenn die beiden ursprünglichen Programme völlig korrekt und frei von Deadlocks und Rennen waren, muss das resultierende Programm dies nicht unbedingt haben Eigentum. Die korrekte Verwendung von Sperren ist eine globale Eigenschaft des gesamten Programms und wird beim Erstellen von Programmen nicht beibehalten. Dies unterscheidet sich von zum Beispiel Transaktionen, die tun compose. Ein Programm, das Transaktionen korrekt verwendet, kann mit einem anderen solchen Programm zusammengesetzt werden und ergibt ein kombiniertes Programm, das Transaktionen korrekt verwendet.

Jörg W. Mittag
quelle
1
Mit anderen Worten, "komponiert nicht" bedeutet "bildet keine Halbgruppe" (oder, etwas stärker, ein Monoid).
Jon Purdy
Ich bin nicht sicher, ob Associtaivity erforderlich ist, also eher wie ein Magma (was ich vor 3 Sekunden buchstäblich gelernt habe :-D)
Jörg W Mittag
Wenn Sie jedoch jemanden fragen, was er meint, wenn er sagt "Sperren komponieren nicht", sind Sie sich ziemlich sicher, dass er nicht antwortet "Ich meine, dass der Satz korrekter gleichzeitiger Programme mit Sperren und die Kompositionsoperation ein Magma bilden". .
Jörg W Mittag
Hah natürlich nicht. Nur eine alternative Formulierung. Ich habe das Gefühl, dass Assoziativität erforderlich ist, um das „flache“ Gefühl der Komposition aufrechtzuerhalten, aber kein starkes Argument, um dies zu untermauern.
Jon Purdy
20

Composability bedeutet, dass Sie Programmkomponenten einfach und zuverlässig miteinander kombinieren können, um größere Komponenten und komplexere Funktionen zu erhalten.

Einige Dinge, die helfen, Komponenten zusammensetzbarer zu machen:

  1. Idempotenz. Eine idempotente Funktion erzeugt immer dieselbe Ausgabe oder dieselben Nebenwirkungen, wenn sie mehrmals mit denselben Parameterwerten aufgerufen wird. Dies verbessert die Kompositionsfähigkeit, da das Ergebnis eines Funktionsaufrufs vorhersehbar ist.

  2. Referentielle Transparenz. Ein referenziell transparenter Ausdruck wird immer zum gleichen Ergebnis ausgewertet. Dies verbessert die Kompositionsfähigkeit, da identische Ausdrücke gegeneinander ausgetauscht werden können und Ausdrücke unabhängig voneinander (dh in verschiedenen Threads) berechnet werden können, ohne Sperren zu verwenden.

  3. Unveränderlichkeit. Der Status eines unveränderlichen Objekts kann nach seiner Erstellung nicht mehr geändert werden. Dies verbessert die Kompositionsfähigkeit, da Sie sich auf einen stabilen Wert des Objekts verlassen können, ohne sich Sorgen machen zu müssen, ob eine Funktion oder ein Objekt irgendwo den Status des Objekts geändert hat, nachdem es erstellt wurde.

  4. Reinheit. Reine Funktionen haben keine Nebenwirkungen. Sie haben nur eine Eingabe und eine Ausgabe, wodurch sie komponierbarer sind, da Sie die Ausgabe einer Funktion in die Eingabe einer anderen Funktion einfügen können, ohne sich Gedanken darüber machen zu müssen, ob sich etwas außerhalb der Funktion geändert hat.

Sperren werden nicht komponiert, da sie ein externes Element sind, auf das Sie sich verlassen müssen, wenn Sie zwei Operationen miteinander kombinieren, die einen bestimmten Status gemeinsam haben, und dies aus den unterschiedlichsten Gründen, die mit der Komplexität der Verwendung von Sperren zusammenhängen.

Der Satz "Monaden komponieren nicht" ergibt für mich keinen Sinn. Der springende Punkt bei einer Monade ist es, einen Zustand wie die Tastatureingabe oder die Bildschirmausgabe in eine reinere, mathematische Form umzuwandeln, die in der Tat komponierbarer ist.

Robert Harvey
quelle
4
Ich denke, stackoverflow.com/questions/7040844/… macht einen guten Job und erklärt, was "Monaden komponieren nicht" wahrscheinlich bedeutet, obwohl ich der Meinung bin, dass Monaden viel komponierbarer sind als Schlösser.
Ixrec
Ihre Stichpunkte für "referentielle Transparenz" und "Reinheit" sind eigentlich die beiden Reinheitsanforderungen . Der Begriff "referentielle Transparenz" sollte vermieden werden, da er nicht genau definiert ist .
BlueRaja - Danny Pflughoeft
1
Eine Monade ist eine algebraische Struktur mit bestimmten Operationen. Was Sie in Ihrem letzten Absatz beschrieben haben, ist der IOTyp, der "zustandsbehaftete Aktionen" wie Tastatureingaben erfasst. Werte des IOTyps zu tun, in der Tat, compose, aber es ist die ganze Art IO , die eine Monade ist. Dieser Typ kann nicht mit anderen Typen kombiniert werden, die Monaden wie beispielsweise der Listentyp sind. Das heißt, wir können nicht systematisch einen Typ erzeugen, IO . Listder sich sowohl IO als auch Listgleichzeitig verhält . Ist das sinnvoll? Ich bin mir nicht sicher, ob ich es gut erklärt habe.
Tikhon Jelvis