Détendez les contraintes d'ordre dans le calcul monadique

Question

Voici un peu de grain à moudre.

Lorsque j'écris le code monadique, la monade impose une commande sur les opérations effectuées. Par exemple, si j'écris dans la monade IO:

do a <- doSomething
   b <- doSomethingElse
   return (a + b)

je sais doSomething sera exécuté avant doSomethingElse.

Maintenant, considérez le code équivalent dans une langue comme c:

return (doSomething() + doSomethingElse());

La sémantique de C ne spécifie pas réellement quel ordre ces deux appels de fonction seront évalués, de sorte que le compilateur est libre de déplacer les choses au fur et à mesure de son plaisir.

Ma question est la suivante: Comment pourrais-je écrire le code monadique à Haskell qui laisse également cet ordre d'évaluation non défini? Idéalement, je profiterais de certains avantages lorsque l'optimiseur de mon compilateur examine le code et commence à déplacer les choses.

Voici quelques techniques possibles qui ne font pas le travail, mais sont dans le bon "esprit":

• Écrivez le code dans style fonctoriel, c'est-à-dire, écrivez plus doSomething doSomethingElse et laisser plus Planifiez les appels monadiques. Inconvénients: vous perdez le partage sur les résultats des actions monadiques, et plus Prend toujours une décision sur le moment où les choses finissent par être évaluées.
• Utilisation Io paresseux, C'est, unsafeInterleaveIO, qui explique la planification des demandes paresseuses de l'évaluation. Mais paresseux est différent de strict avec l'ordre indéfini: en particulier, je veux que toutes mes actions monadiques soient exécutées.
• IO paresseux, combiné avec immédiatement tous les arguments. En particulier, seq n'impose pas les contraintes de commande.

En ce sens, je veux quelque chose de plus flexible que la commande monadique mais moins flexible que la paresse à part entière.

Answer 1

Ce problème de sur-séquentinage du code de monade est connu comme le "Problème de monades commutatifs".

Les monades commutatives sont des monades pour lesquelles l'ordre des actions ne fait aucune différence (ils se déplacent), c'est-à-dire que le code suivant:

do a <- f x
   b <- g y
   m a b

est le même que:

do b <- g y
   a <- f x
   m a b

Il y a beaucoup de monades qui se déplacent (par exemple Maybe, Random). Si la monade est commutative, les opérations capturées à l'intérieur peuvent être calculées en parallèle, par exemple. Ils sont très utiles!

Cependant, nous Je n'ai pas une bonne syntaxe pour les monades qui se rendent, pourtant beaucoup de gens ont demandé Pour une telle chose - c'est toujours un problème de recherche ouverte.

En passant, les fonds applicatifs nous donnent une telle liberté de réorganiser les calculs, cependant, vous devez abandonner la notion de bind (comme suggestions pour EG liftM2 Afficher).

Answer 2

C'est un hack sale sale, mais il semble que cela devrait me faire l'affaire.

{-# OPTIONS_GHC -fglasgow-exts #-}
{-# LANGUAGE MagicHash #-}
module Unorder where
import GHC.Types

unorder :: IO a -> IO b -> IO (a, b)
unorder (IO f) (IO g) = IO $ \rw# ->
           let (# _, x #) = f rw#
               (# _, y #) = g rw#
           in (# rw# , (x,y) #)

Étant donné que cela met le non-déterminisme entre les mains du compilateur, il devrait se comporter "correctement" (c'est-à-dire non déterministe) en ce qui concerne également les problèmes de flux (c'est-à-dire les exceptions).

D'un autre côté, nous ne pouvons pas tirer le même tour des monades les plus standard telles que State et Either a Puisque nous comptons vraiment sur une action effrayante à une distance disponible en jouant avec le RealWorld jeton. Pour obtenir le bon comportement, nous aurions besoin d'une annotation disponible pour l'optimiseur qui indiquait que nous allions bien avec un choix non déterministe entre deux alternatives non équivalentes.

Answer 3

La sémantique de C ne spécifie pas réellement quel ordre ces deux appels de fonction seront évalués, de sorte que le compilateur est libre de déplacer les choses au fur et à mesure de son plaisir.

Mais si doSomething() provoque un effet secondaire qui changera le comportement de doSomethingElse()? Voulez-vous vraiment que le compilateur gâche la commande? (Indice: non) Le fait que vous êtes dans une monade suggère que cela peut être le cas. Votre note que "vous perdez le partage sur les résultats" le suggère également.

Cependant, notez que Monadic ne signifie pas toujours séquencé. Ce n'est pas exactement ce que vous décrivez, mais vous pouvez être intéressé par le Par-monade, ce qui vous permet d'exécuter vos actions en parallèle.

Vous êtes intéressé à laisser la commande non définie afin que le compilateur puisse l'optimiser comme par magie pour vous. Peut-être plutôt que vous devriez utiliser quelque chose comme la par-monade pour indiquer les dépendances (certaines choses doivent inévitablement se produire avant d'autres), puis laisser le reste fonctionner en parallèle.

Note latérale: ne confondez pas Haskell return être quelque chose comme C return