Que sont les combinateurs et comment sont-ils appliqués aux projets de programmation? (explication pratique)

Que sont les combinateurs?

Je cherche:

• une explication pratique
• des exemples de leur utilisation
• exemples de comment les combinateurs améliorent la qualité / généralité du code

Je ne cherche pas:

• des explications sur les combinateurs qui ne m'aident pas à faire le travail (comme le Y-combinator)

D'un point de vue pratique, les combinateurs sont des sortes de constructions de programmation qui vous permettent de rassembler des éléments de logique de manière intéressante et souvent avancée. Leur utilisation dépend généralement de la possibilité de pouvoir intégrer du code exécutable dans des objets, souvent appelés (pour des raisons historiques) des fonctions lambda ou des expressions lambda, mais votre kilométrage peut varier.

Un exemple simple de combinateur (utile) est celui qui prend deux fonctions lambda sans paramètres et en crée un nouveau qui les exécute en séquence. Le combinateur actuel ressemble à ceci dans le pseudocode générique:

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

La fonction cruciale qui en fait un combinateur est la fonction anonyme (fonction lambda) sur la deuxième ligne. quand vous appelez

a = in_sequence(f, g)

L'objet résultant a n'est pas le résultat de l'exécution de f (), puis de g (), mais il s'agit d'un objet que vous pouvez appeler ultérieurement pour exécuter f () et g () dans l'ordre:

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

Vous pouvez également avoir un combinateur qui exécute deux blocs de code en parallèle:

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

Et puis encore

a = in_parallel(f, g)
a()

La bonne chose est que 'in_parallel' et 'in_sequence' sont tous deux des combinateurs du même type / signature, c'est-à-dire qu'ils prennent tous deux deux objets fonction sans paramètre et en renvoient un nouveau. Vous pouvez alors écrire des choses comme

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

et cela fonctionne comme prévu.

En résumé, les combinateurs vous permettent de construire (entre autres choses) le flux de contrôle de votre programme de manière souple et procédurale. Par exemple, si vous utilisez un combinateur in_parallel (..) pour exécuter le parallélisme dans votre programme, vous pouvez ajouter un débogage associé à cela à la mise en œuvre du combinateur in_parallel lui-même. Plus tard, si vous pensez que votre programme a un bogue lié au parallélisme, vous pouvez simplement réimplémenter in_parallel:

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

et d'un coup, toutes les sections parallèles ont été converties en séquences séquentielles!

Les combinateurs sont très utiles lorsqu'ils sont utilisés correctement.

Le combinateur Y, cependant, n'est pas nécessaire dans la vie réelle. C'est un combinateur qui vous permet de créer des fonctions auto-récursives que vous pouvez facilement créer dans n'importe quelle langue moderne sans le combinateur Y.

Il est faux de dire que le combinateur Y est quelque chose qui ne "contribuera pas à faire le travail". Je l'ai trouvé très utile à plusieurs reprises. Le cas le plus évident est celui où vous devez amorcer rapidement un langage interprété intégré. Si vous fournissez un ensemble minimal de primitives, à savoir sequence, select, call, constet closure allocation, il est déjà suffisant pour la construction d' un complet, un langage complexe arbitraire. Aucune prise en charge particulière de la récursivité n’est nécessaire - elle peut être ajoutée via un combinateur à point fixe. Sinon, vous aurez besoin de primitives beaucoup plus compliquées.

L'obscurcissement est un autre cas évident pour les combinateurs. Un code traduit dans le calcul SKI est pratiquement illisible. Si vous devez réellement obscurcir une implémentation d'un algorithme, envisagez d'utiliser des combinateurs, voici un exemple .

Et, bien entendu, les combinateurs sont un outil important pour la mise en œuvre de langages fonctionnels. L'approche la plus simple (comme dans l'exemple ci-dessus) consiste à utiliser SKI ou un calcul équivalent. Les supercombinateurs sont utilisés dans d'autres implémentations. Ce livre en parle en profondeur.

Ceci est une blague , mais une blague mérite une lecture très attentive, car de nombreuses techniques et théories de programmation arcaniques y sont abordées.

En fouillant un peu, j'ai trouvé une question de StackOverflow, bonne explication de «Combinators» (pour les non mathématiciens) qui est un proche cousin de cette question. Une des réponses a été donnée au blog de Reginald Braithwaite, Homoiconic , qui renvoie à plusieurs exemples utiles de combinateurs dans le code (par exemple, le combinateur K , implémenté par la Object#tapméthode de Ruby - lisez la page pour obtenir des exemples de son utilité).

La page Wikipedia sur la logique combinatoire décrit les combinateurs de manière plus globale.