Question Existe-t-il une applicabilité réelle pour la monade de continuation en dehors de l'utilisation académique?


(visiteurs ultérieurs: deux réponses à cette question donnent toutes les deux une excellente idée, si vous êtes intéressé, vous devriez probablement les lire toutes les deux, mais je ne pouvais qu'exiger une limitation de SO)

De toutes les discussions que je trouve en ligne sur la monade de continuation, soit ils expliquent comment il pourrait être utilisé avec des exemples triviaux, soit ils expliquent que c'est un élément fondamental, comme dans cet article sur Mère de toutes les monades est la continuation monad.

Je me demande s'il y a des possibilités d'application en dehors de cette plage. Je veux dire, est-il sensé d’envelopper une fonction récursive ou une récursivité mutuelle dans une monade de continuation? Est-ce que cela aide à la lisibilité?

Voici une version F # du mode continuation extraite de ce post SO:

type ContinuationMonad() =
    member this.Bind (m, f) = fun c -> m (fun a -> f a c)
    member this.Return x = fun k -> k x

let cont = ContinuationMonad()

Est-ce simplement un intérêt académique, par exemple pour aider à comprendre les monades ou les constructeurs de calcul? Ou existe-t-il une applicabilité dans le monde réel, une sécurité de type supplémentaire ou contournent-ils les problèmes de programmation typiques difficiles à résoudre autrement?

I.e., le suite monad avec appel / cc de Ryan Riley montre qu'il est complexe de gérer les exceptions, mais cela n'explique pas quel problème il essaie de résoudre et les exemples ne montrent pas pourquoi il a besoin spécifiquement de cette monade. Certes, je ne comprends tout simplement pas ce que ça fait, mais ça peut être un trésor!

(Remarque: je ne suis pas intéressé à comprendre comment fonctionne la monade de continuation, je pense que je le comprends bien, je ne vois tout simplement pas quel problème de programmation cela résout.)


11
2017-12-17 20:27


origine


Réponses:


La matière "mère de toutes les monades" n'est pas purement académique. Dan Piponi fait référence à Andrzej Filinski Représentant des monades, un bon papier. Le résultat est que si votre langue a des continuations délimitées (ou peut les imiter avec call/cc et un seul morceau d'état mutable) alors vous pouvez de manière transparente ajouter tout effet monadique à n'importe quel code. En d'autres termes, si vous avez des continuations délimitées et pas d'autres effets secondaires, vous pouvez mettre en place état mutable (global) ou exceptions ou retour en arrière du non déterminisme ou de la concurrence coopérative. Vous pouvez faire chacun de ceux-ci simplement en définissant quelques fonctions simples. Pas de transformation globale ni de besoin. En outre, vous ne payez que les effets secondaires lorsque vous les utilisez. Il s'avère que les Schemers avaient complètement raison à propos de call/cc être très expressif.

Si votre langue ne comporte pas de continuations délimitées, vous pouvez les obtenir via la monade de continuation (ou mieux la monade de continuation à double canon). Bien sûr, si vous voulez écrire dans le style monadic de toute façon - ce qui est une transformation globale - pourquoi ne pas simplement utiliser la monade souhaitée dès le départ? Pour Haskellers, c'est généralement ce que nous faisons, mais il y a toujours des avantages à utiliser la monade de continuation dans de nombreux cas (même si elle est cachée). Un bon exemple est le Maybe/Option monad est comme avoir des exceptions sauf qu'il n'y a qu'un seul type d'exception. Fondamentalement, cette monade capture le motif de retour d'un "code d'erreur" et le vérifie après chaque appel de fonction. Et c'est exactement ce que fait la définition typique, sauf par «appel de fonction». Je parlais de chaque étape (monadique) du calcul. Autant dire que cela est assez inefficace, surtout quand la grande majorité du temps, il n’ya pas d’erreur. Si vous réfléchissez Maybe dans la monade de continuation cependant, alors que vous devez payer le coût du code CPSed (que GHC Haskell gère étonnamment bien), vous ne payez que pour vérifier le "code d'erreur" dans les endroits où il est important, à savoir catch déclarations. En Haskell, le Codensity monad que danidiaz mentionné est un meilleur choix parce que le dernier Ce que Haskellers veut, c’est faire en sorte que des effets arbitraires puissent être entrelacés de manière transparente dans leur code.

Comme danidiaz a également mentionné, de nombreuses monades sont plus facilement ou plus efficacement mises en œuvre en utilisant essentiellement une monade de continuation ou une variante. La recherche de retour en arrière est un exemple. Bien que ce ne soit pas la dernière nouveauté, l’un de mes papiers préférés Variables logiques saisies dans Haskell. Les techniques utilisées étaient également utilisées dans le langage de description du matériel câblé. Aussi de Koen Claesson est La monade de concurrence d'un homme pauvre. Les utilisations plus modernes des idées dans cet exemple incluent: la monade du parallélisme déterministe dans Haskell Une monade pour le parallélisme déterministe et gestionnaires d'E / S évolutifs Combinaison d'événements et de threads pour des services réseau évolutifs. Je suis sûr que je peux trouver des techniques similaires utilisées à Scala. S'il n'était pas fourni, vous pourriez utiliser un monad de continuation pour implémenter des flux de travail asynchrones dans F #. En fait, Don Syme les références exactement les mêmes papiers que je viens de mentionner. Si vous pouvez sérialiser des fonctions mais que vous n'avez pas de continuations, vous pouvez utiliser une monade de continuation pour les obtenir et faire le type de programmation continue de série rendu populaire par des systèmes comme Bord de mer. Même sans continuations sérialisables, vous pouvez utiliser le modèle (essentiellement identique à async) pour au moins éviter les rappels tout en stockant les continuations localement et en envoyant uniquement une clé.

En fin de compte, relativement peu de personnes en dehors des Haskellers utilisent des monades à quelque titre que ce soit, et comme je l’ai mentionné plus tôt, les Haskellers ont tendance à utiliser des monades plus contournables que les monades de continuation. Néanmoins, les monades de continuation ou de continuation monad comme les choses, en particulier pour la programmation asynchrone, deviennent moins rares. Comme C #, F #, Scala, Swift et même Java commencent à intégrer une programmation monadique ou au moins monadique, ces idées seront plus largement utilisées. Si les développeurs Node étaient plus au courant de cela, ils se seraient peut-être rendu compte que vous pouviez avoir votre gâteau et le manger aussi en ce qui concerne la programmation pilotée par les événements.


5
2017-12-19 01:12



Pour fournir une réponse plus directe, spécifique à F # (même si Derek a déjà couvert cela), le continuation monad capture à peu près le cœur de la façon dont workflows asynchrones travail.

Une monade de continuation est une fonction qui, lorsqu'elle est donnée suite, appelle éventuellement la suite du résultat (elle peut ne jamais l'appeler ou l'appeler à plusieurs reprises):

type Cont<'T> = ('T -> unit) -> unit

Les calculs asynchrones F # sont un peu plus complexes - ils prennent la suite (en cas de succès), les suites d'exceptions et d'annulation, et incluent également le jeton d'annulation. En utilisant une définition légèrement simplifiée, la bibliothèque principale F # utilise (voir la définition complète ici):

type AsyncParams =
    { token : CancellationToken
      econt : exn -> unit
      ccont : exn -> unit } 

type Async<'T> = ('T -> unit) * AsyncParams -> unit

Comme vous pouvez le voir, si vous ignorez AsyncParams, c'est à peu près la monade de continuation. En F #, je pense que les monades "classiques" sont plus utiles comme source d'inspiration que comme mécanisme d'implémentation directe. Ici, la suite monad fournit un modèle utile pour gérer certains types de calculs - et avec de nombreux aspects spécifiques à l’async, l’idée principale peut être utilisée pour implémenter des calculs asynchrones.

Je pense que ceci est assez différent de la façon dont les monades sont utilisées dans les travaux académiques classiques ou dans Haskell, où elles ont tendance à être utilisées «telles quelles» et à être composées de différentes manières pour construire des monades plus complexes.

C'est peut-être juste mon opinion personnelle, mais je dirais que la monade de continuation n'est pas pratique en soi, mais elle est la base de quelques idées très pratiques. (Tout comme le calcul lambda n'est pas vraiment utile en soi, mais cela peut être considéré comme une source d'inspiration pour de jolis langages pratiques!)


6
2017-12-19 14:08



Je trouve certainement plus facile de lire une fonction récursive implémentée en utilisant la monade de continuation que celle implémentée en utilisant la récursion explicite. Par exemple, compte tenu de ce type d'arbre:

type 'a Tree = 
| Node of 'a * 'a Tree * 'a Tree
| Empty

voici une façon d'écrire un pli ascendant sur un arbre:

let rec fold e f t = cont {
    match t with
    | Node(a,t1,t2) ->
        let! r1 = fold e f t1
        let! r2 = fold e f t2
        return f a r1 r2
    | Empty -> return e
}

Ceci est clairement analogue à un pli naïf:

let rec fold e f t =
    match t with
    | Node(a,t1,t2) ->
        let r1 = fold e f t1
        let r2 = fold e f t2
        f a r1 r2
    | Empty -> return e

sauf que le pli naïf fera exploser la pile quand on l'appelle sur un arbre profond car ce n'est pas la queue récursive, alors que le pli écrit en utilisant la suite monad ne le fera pas. Vous pouvez bien sûr écrire la même chose en utilisant des continuations explicites, mais à mes yeux, la quantité d'encombrement qu'elles ajoutent détourne la structure de l'algorithme (et les mettre en place n'est pas complètement infaillible):

let rec fold e f t k = 
    match t with
    | Node(a,t1,t2) -> 
        fold e f t1 (fun r1 ->
        fold e f t2 (fun r2 ->
        k (f r1 r2)))
    | Empty -> k e

Notez que pour que cela fonctionne, vous devez modifier votre définition de ContinuationMonad inclure

member this.Delay f v = f () v

2
2017-12-21 18:33