Quelles sont les autres manières de déclarer être manipulées dans un langage purement fonctionnel en plus de Monads?

J’ai donc commencé à envelopper Monads (utilisé dans Haskell). Je suis curieux de savoir comment d’autres méthodes ou états peuvent être manipulés dans un langage purement fonctionnel (à la fois en théorie et dans la réalité). Par exemple, il existe un langage logique appelé “mercure” qui utilise la “saisie par effet”. Dans un programme tel que haskell, comment fonctionne le typage des effets? Comment fonctionnent les autres systèmes?

Il y a plusieurs questions différentes impliquées ici.

Premièrement, IO et State sont des choses très différentes. State est facile à faire vous-même: transmettez simplement un argument supplémentaire à chaque fonction et renvoyez un résultat supplémentaire, et vous avez une “fonction avec état”; Par exemple, mettez a -> b dans a -> s -> (b,s) .

Il n’y a pas de magie ici: Control.Monad.State fournit un wrapper qui facilite le travail avec les “actions d’état” du formulaire s -> (a,s) , ainsi qu’un tas de fonctions d’assistance, mais c’est tout.

I / O, de par sa nature, doit avoir une certaine magie dans sa mise en œuvre. Mais il y a beaucoup de façons d’exprimer les E / S dans Haskell qui n’impliquent pas le mot “monade”. Si nous avions un sous-ensemble de Haskell tel quel, et que nous voulions inventer IO à partir de rien, sans rien savoir des monades, nous pourrions faire beaucoup de choses.

Par exemple, si tout ce que nous voulons faire, c’est imprimer sur stdout, nous pourrions dire:

 type PrintOnlyIO = Ssortingng main :: PrintOnlyIO main = "Hello world!" 

Et puis, un RTS (runtime system) qui évalue la chaîne et l’imprime. Cela nous permet d’écrire n’importe quel programme Haskell dont les E / S consistent entièrement à imprimer sur stdout.

Ce n’est pas très utile, cependant, car nous voulons l’interactivité! Alors, inventons un nouveau type d’E / S qui le permet. La chose la plus simple qui vient à l’esprit est

 type InteractIO = Ssortingng -> Ssortingng main :: InteractIO main = map toUpper 

Cette approche d’IO nous permet d’écrire n’importe quel code qui lit à partir de stdin et écrit sur stdout (le Prelude est livré avec une fonction interact :: InteractIO -> IO () qui le fait).

C’est beaucoup mieux, car cela nous permet d’écrire des programmes interactifs. Mais il est toujours très limité par rapport à toutes les IO que nous voulons faire, et également très sujet aux erreurs (si nous essayons accidentellement de lire trop loin dans stdin, le programme va simplement bloquer jusqu’à ce que l’utilisateur tape plus).

Nous voulons pouvoir faire plus que lire stdin et écrire stdout. Voici comment les premières versions de Haskell ont fait les E / S, à peu près:

 data Request = PutStrLn Ssortingng | GetLine | Exit | ... data Response = Success | Str Ssortingng | ... type DialogueIO = [Response] -> [Request] main :: DialogueIO main resps1 = PutStrLn "what's your name?" : GetLine : case resps1 of Success : Str name : resps2 -> PutStrLn ("hi " ++ name ++ "!") : Exit 

Lorsque nous écrivons la main , nous obtenons un argument de liste paresseuse et renvoyons une liste paresseuse. La liste paresseuse que nous PutStrLn s a des valeurs comme PutStrLn s et GetLine ; Après avoir donné une valeur (demande), nous pouvons examiner l’élément suivant de la liste (réponse), et le RTS organisera la réponse à notre requête.

Il y a des manières de rendre le travail avec ce mécanisme plus agréable, mais comme vous pouvez l’imaginer, l’approche devient assez difficile assez rapidement. De plus, il est sujet aux erreurs de la même manière que le précédent.

Voici une autre approche beaucoup moins sujette aux erreurs et conceptuellement très proche du comportement de Haskell IO:

 data ContIO = Exit | PutStrLn Ssortingng ContIO | GetLine (Ssortingng -> ContIO) | ... main :: ContIO main = PutStrLn "what's your name?" $ GetLine $ \name -> PutStrLn ("hi " ++ name ++ "!") $ Exit 

L’essentiel est que, au lieu de prendre une “liste paresseuse” de réponses comme un grand argument au début du processus principal, nous faisons des requêtes individuelles qui acceptent un argument à la fois.

Notre programme est maintenant juste un type de données normal – un peu comme une liste liée, sauf que vous ne pouvez pas simplement le parcourir normalement: lorsque le RTS interprète main , il rencontre parfois une valeur comme GetLine qui contient une fonction; alors il doit obtenir une chaîne de stdin en utilisant la magie RTS et transmettre cette chaîne à la fonction avant de pouvoir continuer. Exercice: Ecrire interpret :: ContIO -> IO () .

Notez qu’aucune de ces implémentations n’implique un “passage du monde”. “Passage du monde” n’est pas vraiment la façon dont les E / S fonctionnent dans Haskell. L’implémentation réelle du type IO dans GHC implique un type interne appelé RealWorld , mais ce n’est qu’un détail d’implémentation.

Actual Haskell IO ajoute un paramètre de type afin que nous puissions écrire des actions qui “produisent” des valeurs arbitraires – il ressemble donc davantage aux data IO a = Done a | PutStr Ssortingng (IO a) | GetLine (Ssortingng -> IO a) | ... data IO a = Done a | PutStr Ssortingng (IO a) | GetLine (Ssortingng -> IO a) | ... data IO a = Done a | PutStr Ssortingng (IO a) | GetLine (Ssortingng -> IO a) | ... Cela nous donne plus de flexibilité, car nous pouvons créer des “actions IO ” qui produisent des valeurs arbitraires.

(Comme Russell O’Connor le fait remarquer , ce type est juste une monade libre. Nous pouvons écrire une instance Monad facilement pour cela.)


D’où viennent les monades, alors? Il s’avère que nous n’avons pas besoin de Monad pour I / O, et nous n’avons pas besoin de Monad pour l’état, alors pourquoi en avons-nous besoin? La réponse est que nous ne le faisons pas. Il n’y a rien de magique dans la classe de type Monad .

Cependant, lorsque nous travaillons avec IO et State (et les listes et les fonctions et Maybe et les parsingurs et le style de continuation-passes et …) assez longtemps, nous finissons par comprendre qu’ils se comportent de manière similaire à certains égards. Nous pourrions écrire une fonction qui imprime chaque chaîne dans une liste, et une fonction qui exécute tous les calculs avec état dans une liste et en transite l’état, et ils se ressemblent beaucoup.

Comme nous n’aimons pas écrire beaucoup de code similaire, nous voulons un moyen de l’abstraire; Monad se révèle être une excellente abstraction, car elle nous permet d’abstraire de nombreux types qui semblent très différents, mais qui fournissent néanmoins de nombreuses fonctionnalités utiles (y compris tout ce qui se trouve dans Control.Monad ).

Étant donné bindIO :: IO a -> (a -> IO b) -> IO b et returnIO :: a -> IO a , nous pourrions écrire n’importe quel programme IO dans Haskell sans jamais penser aux monades. Mais nous finirions probablement par reproduire beaucoup de fonctions dans Control.Monad , comme mapM et forever et when et (>=>) .

En implémentant l’API Monad commune, nous utilisons le même code pour travailler avec les actions IO que nous faisons avec les parsingurs et les listes. C’est vraiment la seule raison pour laquelle nous avons la classe Monad – pour capturer les similitudes entre les différents types.

Une autre approche majeure consiste à taper l’unicité , comme dans Clean . La petite histoire est que les descripteurs à énoncer (y compris le monde réel) ne peuvent être utilisés qu’une seule fois, et que les fonctions qui accèdent à l’état mutable renvoient un nouveau descripteur. Cela signifie qu’une sortie du premier appel est une entrée d’une seconde, forçant l’évaluation séquentielle.

Le typage des effets est utilisé dans le compilateur Disciple pour Haskell, mais pour autant que je le sache, il faudrait beaucoup de travail de compilation pour l’activer, par exemple, dans le GHC. Je laisserai la discussion des détails à ceux qui sont mieux informés que moi.

Eh bien, d’abord, quel est l’état? Il peut se manifester sous la forme d’une variable mutable, ce que vous n’avez pas dans Haskell. Vous avez uniquement des références mémoire (IORef, MVar, Ptr, etc.) et des actions IO / ST pour y agir.

Cependant, l’État lui-même peut aussi être pur. Pour accuser réception de la révision du type «Stream»:

 data Stream a = Stream a (Stream a) 

C’est un stream de valeurs. Cependant, une autre façon d’interpréter ce type est une valeur variable:

 stepStream :: Stream a -> (a, Stream a) stepStream (Stream x xs) = (x, xs) 

Cela devient intéressant lorsque vous permettez à deux stream de communiquer. Vous obtenez alors la catégorie d’automates Auto:

 newtype Auto ab = Auto (a -> (b, Auto ab)) 

C’est vraiment comme Stream , sauf que maintenant, à chaque instant, le stream obtient une valeur d’entrée de type a . Cela forme une catégorie, donc un instant d’un stream peut avoir sa valeur à partir du même instant d’un autre stream.

Une fois de plus une interprétation différente de ceci: vous avez deux calculs qui changent avec le temps et vous leur permettez de communiquer. Ainsi, chaque calcul a un état local. Voici un type isomorphe à Auto :

 data LS ab = forall s. LS s ((a, s) -> (b, s)) 

Jetez un oeil à une histoire de Haskell: être paresseux avec la classe . Il décrit deux approches différentes pour faire des E / S dans Haskell, avant que les monades ne soient inventées: les suites et les stream.

Il existe une approche appelée programmation réactive fonctionnelle qui représente les valeurs et / ou les stream d’événements variables dans le temps en tant qu’abstraction de première classe. Un exemple récent qui me vient à l’esprit est Elm (il est écrit en Haskell et a une syntaxe similaire à Haskell).

Cela ne peut pas être (pas si par “état” vous voulez dire “comportement variable E / S ou mutable comme dans un langage procédural”). En premier lieu, vous devez comprendre d’où vient l’utilisation des monades pour les variables mutables ou les E / S. Malgré la croyance populaire, les E / S monadiques ne proviennent pas de langages comme Haskell, mais de langages tels que ML. Eugenio Moggi a développé les monades originales en étudiant l’utilisation de la théorie des catégories pour la sémantique dénotationnelle des langages fonctionnels impurs comme le langage ML. Pour voir pourquoi, considérez qu’une monade (dans Haskell) peut être classée par trois propriétés:

  • Il existe une distinction entre les valeurs (dans Haskell, de type a ) et les expressions (dans Haskell, de type IO a ).
  • Toute valeur peut être transformée en une expression (dans Haskell, en convertissant x pour return x ).
  • Toute fonction sur des valeurs (renvoyant une expression) peut être appliquée à une expression (dans Haskell, en calculant f =<< a ).

Ces propriétés sont évidemment vraies pour (au moins) la sémantique dénotationnelle de tout langage fonctionnel impur:

  • Une expression , comme print "Hello, world!\n" , peut avoir des effets secondaires, mais sa valeur , telle que () , ne le peut pas. Nous devons donc faire une distinction entre les deux cas dans la sémantique dénotationnelle.
  • Une valeur, telle que 3 , peut être utilisée partout où une expression est requirejse. Ainsi, notre sémantique dénotationnelle nécessite une fonction pour transformer une valeur en une expression.
  • Une fonction prend des valeurs comme arguments (les parameters formels d'une fonction dans un langage ssortingct n'ont pas d'effets secondaires), mais peuvent être appliqués à une expression. Nous avons donc besoin d'un moyen d'appliquer une fonction (de retour d'expression) de valeurs à une expression.

Ainsi, toute sémantique dénotationnelle pour un langage fonctionnel (ou procédural) impur aura la structure d'une monade sous le capot, même si cette structure n'est pas explicitement utilisée pour décrire le fonctionnement des E / S dans le langage.

Qu'en est-il des langages purement fonctionnels?

Il y a quatre manières principales de faire des E / S dans des langages purement fonctionnels, que je connais (en pratique) (encore une fois, se limiter aux E / S de type procédural; le FRP est vraiment un paradigme différent):

  • E / S monadiques
  • Les continuations
  • Unicité / types linéaires
  • Dialogues

Les E / S monadiques sont évidentes. La suite basée sur les E / S ressemble à ceci:

 main k = print "What is your name? " $ getLine $ \ myName -> print ("Hello, " ++ myName ++ "\n") $ k () 

Chaque action d'E / S prend une «continuation», effectue son action, puis appelle en queue (sous le capot) la suite. Donc, dans le programme ci-dessus:

  • print "What is your name? "
  • getLine s'exécute, puis
  • print ("Hello, " ++ myName ++ "\n") s'exécute, puis
  • k s'exécute (ce qui renvoie le contrôle au système d'exploitation).

La suite monade est une amélioration syntaxique évidente de ce qui précède. Plus significativement, sémantiquement , je ne peux voir que deux manières de faire fonctionner les E / S dans ce qui précède:

  • Faites en sorte que les actions d'E / S (et les suites) renvoient un "type d'E / S" décrivant les E / S que vous souhaitez effectuer. Maintenant, vous avez une monade d'E / S (suite basée sur monad) sans le wrapper newtype.
  • Faites en sorte que les actions d'E / S (et les suites) renvoient essentiellement () et exécutent les E / S comme un effet secondaire de l'appel des opérations individuelles (par exemple, print , getLine , etc.). Mais si l'évaluation d'une expression dans votre langue (qui est la partie droite de la définition main ci-dessus) a un effet secondaire, je ne considérerais pas cela comme purement fonctionnel.

Qu'en est-il de l'unicité / types linéaires? Celles-ci utilisent des valeurs spéciales de "jeton" pour représenter l'état du monde après chaque action et imposer le séquençage. Le code ressemble à ceci:

 main w0 = let w1 = print "What is your name? " w0 (w2, myName) = getLine w1 w3 = print $ "Hello, " ++ myName ++ "!\n" in w3 

La différence entre les types linéaires et les types d’unicité est que dans les types linéaires , le résultat doit être w3 (il doit être de type World ), alors que dans les types d’unicité , le résultat pourrait être w3 `seq` () . w3 doit juste être évalué pour que les E / S se produisent.

Encore une fois, la monade d'état est une amélioration syntaxique évidente de ce qui précède. Plus significativement, sémantiquement , vous avez encore deux choix:

  • Effectuez les opérations d'E / S, telles que print et getLine , de façon ssortingcte dans l'argument World (l'opération précédente s'exécute en premier et l'effet secondaire (pour que les E / S aient un effet secondaire sur leur évaluation). vous avez des effets secondaires de l'évaluation, à mon avis, ce n'est pas vraiment fonctionnel.
  • Le type Make the World représente réellement les E / S à effectuer. Cela a le même problème que l'implémentation IO de GHC avec des programmes récursifs. Supposons que nous modifions le résultat de main en main w3 . Maintenant, main queue main appelle elle-même. Toute fonction qui s'appelle elle-même, dans un langage purement fonctionnel, n'a pas de valeur (est juste une boucle infinie); C'est un fait de base sur la façon dont la sémantique dénotationnelle de la récursivité fonctionne dans un langage pur. Encore une fois, je ne considérerais aucun langage qui aurait enfreint cette règle (en particulier pour un type de données «spécial» comme World ) comme étant purement fonctionnel.

Donc, vraiment, l'unicité ou les types linéaires a) produisent des programmes plus clairs / plus propres si vous les encapsulez dans un état monadique et b) ne sont pas réellement un moyen de faire des E / S dans un langage purement fonctionnel après tout.

Qu'en est-il des dialogs? C'est la seule façon de faire des E / S (ou, techniquement, des variables mutables, bien que ce soit beaucoup plus difficile) qui soit à la fois purement fonctionnelle et indépendante des monades. Cela ressemble à ceci:

 main resps = [ PrintReq "What is your name? ", GetLineReq, PrintReq $ "Hello, " ++ myName ++ "!\n" ] where LineResp myName = resps !! 1 

Cependant, vous remarquerez quelques inconvénients de cette approche:

  • Il n'est pas clair d'intégrer les procédures d'E / S dans cette approche.
  • Vous devez utiliser l'indexation numérique ou positionnelle pour trouver la réponse correspondant à une requête donnée, ce qui est assez fragile.
  • Il n'y a pas de moyen évident de cibler une réponse sur les actions après sa réception; Si ce programme utilisait en quelque sorte myName avant d'émettre la requête getLine correspondante, le compilateur accepterait votre programme mais il se bloquerait à l'exécution.

Un moyen simple de résoudre tous ces problèmes consiste à insérer des dialogs dans des suites, comme ceci:

 type Cont = [Response] -> [Request] print :: Ssortingng -> Cont -> Cont print msg k resps = PrintReq msg : case resps of PrintResp () : resps1 -> k resps1 getLine :: (Ssortingng -> Cont) -> Cont getLine k resps = GetLineReq : case resps of GetLineResp msg : resps1 -> k msg resps1 

Le code semble maintenant identique au code de l’approche de passage continu à l’E / S donnée précédemment. En fait, les dialogs constituent un excellent type de résultat pour vos continuations dans un système d'E / S basé sur la continuation, ou même dans un système d'E / S monadiques basé sur monad. Cependant, en convertissant de nouveau en continuations, le même argument s'applique, de sorte que même si le système d’exécution utilise des boîtes de dialog en interne, les programmes doivent toujours être écrits de manière monadique en E / S.