Quelle est la signification de «ne compose pas»?

35

Je vois beaucoup de textes, en particulier des textes de programmation fonctionnels, affirmant que certains concepts CS "ne composent pas" . Les exemples sont: les serrures ne composent pas, les monades ne composent pas.

J'ai eu du mal à trouver exactement le sens de cette phrase. Quand je pense à la composition, je pense à la composition de fonction ou à l'agrégation d'objets (comme dans "privilégier la composition à l'héritage"), mais cela ne semble pas être le sens dans lequel les gens l'utilisent ici.

Quelqu'un peut-il expliquer le sens de cette expression lorsqu'elle est utilisée dans des expressions telles que les deux exemples ci-dessus (c'est-à-dire, serrures et monades)?

Facture
la source
C'est plus proche du sens de la composition fonctionnelle que de l'agrégation d'objets.
Andres F.
De manière approximative et informelle, si vous utilisez deux éléments distincts qui utilisent des verrous, il est difficile de les coller ensemble. (dans le cas des verrous, il est difficile de se passer des impasses; dans le cas des monades, les types peuvent se compliquer)
user253751

Réponses:

35

Lorsque les gens disent "X ne compose pas", ce qu'ils entendent par "composer" signifie en réalité simplement "assemblé", et quoi et comment vous les assemblez peut être très différent, en fonction de ce que "X" est exactement.

En outre, quand ils disent "ne compose pas", ils peuvent signifier des choses légèrement différentes:

  1. Vous ne pouvez pas mettre deux X ensemble, tout simplement.
  2. Vous pouvez mettre deux X ensemble, mais le résultat peut ne pas être un X (IOW: X n'est pas fermé sous composition .)
  3. Vous pouvez assembler deux X, mais le résultat X risque de ne pas fonctionner comme prévu.

Un exemple pour # 1 est les analyseurs avec les scanners / lexers. Vous pourriez entendre la phrase "les scanners / lexeurs ne composent pas". Ce n'est pas vraiment vrai. Ce qu'ils veulent dire, c'est "un analyseur qui utilise une étape de lexing distincte ne compose pas".

Pourquoi voudriez-vous composer des analyseurs? Imaginez que vous soyez un fournisseur IDE tel que JetBrains, Eclipse Foundation, Microsoft ou Embarcadero, et que vous souhaitez créer un environnement de développement intégré (IDE) pour un framework Web. Dans le développement Web typique, nous mélangeons souvent des langues. Vous avez des fichiers HTML avec des <script>éléments contenant ECMAScript et<style>éléments contenant CSS. Vous avez des fichiers de modèle contenant HTML, un langage de programmation et une métasyntaxe de langage de modèle. Vous ne voulez pas écrire différents surligneurs de syntaxe pour "Python", "Python incorporé dans un modèle", "CSS", "CSS dans HTML", "ECMASCript", "ECMAScript dans HTML", "HTML", "HTML dans un modèle ", et ainsi de suite. Vous souhaitez écrire un surligneur de syntaxe pour Python, un pour HTML, un pour le langage de modèle, puis composer les trois en un surligneur de syntaxe pour un fichier de modèle.

Cependant, un lexer analyse l'intégralité du fichier dans un flux de jetons, ce qui n'a de sens que pour cette langue. L'analyseur de l'autre langue ne peut pas fonctionner avec les jetons que le lexer le transmet. Par exemple, les analyseurs syntaxiques Python sont généralement écrits de manière à ce que le lexer garde une trace de l'indentation et injecte des faux INDENTet des DEDENTjetons dans le flux de jetons, permettant ainsi à l'analyseur d'être sans contexte, même si la syntaxe de Python ne l'est pas. Un lexer HTML ignorera toutefois complètement les espaces, car il n'a aucune signification en HTML.

Cependant, un analyseur sans scanner, qui lit simplement des caractères, peut transmettre le flux de caractères à un analyseur différent, qui peut ensuite le restituer, ce qui les rend beaucoup plus faciles à composer.

Un exemple pour # 2 est les chaînes contenant des requêtes SQL. Vous pouvez avoir deux chaînes, chacune contenant une requête SQL syntaxiquement correcte, mais si vous concaténez les deux chaînes, le résultat risque de ne pas être une requête SQL syntaxiquement correcte. Voilà pourquoi nous avons requête algèbres comme ARel, qui font Compose.

Les serrures sont un exemple de # 3. Si vous avez deux programmes avec des verrous et que vous les combinez en un seul programme, vous avez toujours un programme avec des verrous, mais même si les deux programmes originaux étaient complètement corrects, sans impasses ni courses, le programme résultant ne possède pas nécessairement ce programme. propriété. L'utilisation correcte des verrous est une propriété globale de l'ensemble du programme et une propriété qui n'est pas conservée lorsque vous composez des programmes. Ceci est différent de, par exemple, des transactions qui font Compose. Un programme qui utilise correctement les transactions peut être composé avec un autre programme de ce type et donnera un programme combiné qui utilise correctement les transactions.

Jörg W Mittag
la source
1
En d'autres termes, “ne compose pas” signifie “ne forme pas de semi-groupe” (ou, légèrement plus fortement, un monoïde).
Jon Purdy
Je ne suis pas sûr que l’association soit nécessaire. C’est donc plutôt un magma (que j’ai appris littéralement il ya 3 secondes :-D)
Jörg W Mittag
Cependant, si vous demandez à quelqu'un ce qu'il veut dire quand il dit "les verrous ne composent pas", je suis presque sûr qu'ils ne répondront pas "je veux dire que l'ensemble des programmes concurrents corrects avec des verrous et l'opération de composition forment un magma" .
Jörg W Mittag le
Hah, bien sûr que non. Juste un phrasé alternatif. J'ai le sentiment que l'associativité est nécessaire pour maintenir le sentiment de composition «à plat», mais aucun argument solide ne le conforte.
Jon Purdy
20

La composabilité signifie que vous pouvez facilement et de manière fiable combiner des composants de programme pour produire des composants plus volumineux et des fonctionnalités plus complexes.

Quelques choses qui aident à rendre les composants plus composables:

  1. Idempotence. Une fonction idempotente produira toujours la même sortie ou les mêmes effets secondaires, si elle est appelée plusieurs fois avec les mêmes valeurs de paramètre. Cela améliore la composabilité, car le résultat d'un appel de fonction est prévisible.

  2. Transparence référentielle. Une expression référentiellement transparente sera toujours évaluée au même résultat. Cela améliore la composabilité en permettant de substituer des expressions identiques les unes aux autres et en permettant aux expressions d'être calculées indépendamment les unes des autres (c'est-à-dire sur des threads différents) sans utiliser de verrous.

  3. Immutabilité. L'état d'un objet immuable ne peut pas être changé une fois qu'il est créé. Cela améliore la composabilité, car vous pouvez compter sur une valeur stable de l'objet, sans vous soucier de savoir si une fonction ou un objet a modifié l'état de l'objet après sa création.

  4. Pureté. Les fonctions pures n'ont pas d'effets secondaires. Ils ont seulement une entrée et une sortie, ce qui les rend plus composables car vous pouvez insérer la sortie d'une fonction dans l'entrée d'une autre fonction sans vous soucier de savoir si quelque chose en dehors de la fonction a changé.

Les verrous ne composent pas, car ils constituent un élément extérieur sur lequel vous devez compter lorsque vous combinez deux opérations partageant un même état et pour toutes sortes de raisons liées à la complexité inhérente à l'utilisation des verrous.

L'expression "les monades ne composent pas" n'a pas beaucoup de sens pour moi. L’intérêt d’une monade est de prendre quelque chose d’état, comme une entrée au clavier ou une sortie à l’écran, et de le transformer en une forme mathématique plus pure, qui est en fait plus facilement composable.

Robert Harvey
la source
4
Je pense que stackoverflow.com/questions/7040844/ ... explique sans doute ce que "les monades ne composent pas" signifie probablement, bien que je convienne que les monades sont beaucoup plus composables que les serrures.
Ixrec
Vos puces pour "transparence référentielle" et "pureté" sont en réalité les deux exigences de la pureté . Le terme "transparence référentielle" devrait être évité car il n'est pas bien défini .
BlueRaja - Danny Pflughoeft
1
Une monade est une structure algébrique avec certaines opérations. Ce que vous avez décrit dans votre dernier paragraphe est le IOtype qui capture les "actions avec état" comme la saisie au clavier. Les valeurs du IOtype composent effectivement, mais c'est le type entier IO qui est une monade. Ce type ne compose pas avec d'autres types qui sont des monades comme, par exemple, le type de liste. Autrement dit, nous ne pouvons pas produire systématiquement un type IO . Listqui se comporte comme les deux IO et Listsimultanément. Cela a-t-il du sens? Je ne suis pas sûr de bien l'expliquer.
Tikhon Jelvis