Discussion :

[james-mi]

en flanant un peu du côté d'Haskell, j'ai découvert, via un excellent tutoriel d'Hal Daumé, les monades.

Coïncidence, Matias Giovannini publie sur son blog monads are plug-ins : très clair, très instructif !

Néanmoins, en tant que programmeur peu expérimenté, je me demande pour quels types d'appli cette approche est utile ...

Avez vous des idées ? de l'expérience ?

Et quelqu'un sait-il si cette approche en OCaml est aussi puissante que les monades natives d'haskell ?

P.S. : pour creuser le sujet, google renvoie sur plusieurs documents traitant de OCaml et monades, par exemple :
http://dutherenverseauborddelatable....ons-for-ocaml/
http://http://enfranchisedmind.com/b...ial-for-ocaml/
http://codemiscellany.blogspot.com/2...-in-ocaml.html

http://www.reddit.com/r/programming/...ook_at_monads/
ou encore
http://ocaml.janestcapital.com/?q=node/23

ajout ultérieur :
tuto excellent sur les monades en Haskell
You Could Have Invented Monads! (And Maybe You Already Have.)
et peut-être :
Nuclear waste
ou encore :
"Probably one of the most well-written academic papers I’ve read"

[gasche]

Et quelqu'un sait-il si cette approche en OCaml est aussi puissante que les monades natives d'haskell ?

Ben, oui, ce sont des monades. Les monades ne sont d'ailleurs pas vraiment "natives" en Haskell puisqu'elles s'implémentent dans des bibliothèques (dont certaines sont très magiques et reposent sur des trucs louches du dedans, mais ça reste en dehors du coeur du langage). Seul le sucre syntaxique est au niveau "inclus dans le langage" (en OCaml il est externalisé par camlp4).

Il m'arrive d'utiliser des monades quand elles sont avantageuses pour un code. Pour ce qui est des problèmes de performance, il y a des gens qui essaient de définir les opérateurs monadiques comme des macros camlp4 pour que les trucs "évidents" soient inlinés au camlp4-time, et ça marche plutôt bien (il y a une mesure de performances plutôt convaincante dans un paper de l'auteur de dutherenverseauborddelatable).

Les monades sont moins présentes en OCaml parce que les effets de bords y sont autorisés (et n'affectent pas le typage, etc.). Elles restent des outils utiles pour la modularisation (c'est ce qu'a montré Giovannini dans son post), et sont donc régulièrement utilisées.

Cependant, d'après mon expérience (limitée), on a plus tendance à découvrir des monades dans son code après plusieurs étapes de refactorisation, "par hasard", et les résultats obtenus comme cela sont plus naturels que ceux des gens qui se disent "il me faut une monade" avant de commencer à coder. D'ailleurs parfois on tombe sur une structure différente, et on obtient autre chose qu'une monade (elles sont sous les projecteurs, mais il y a de nombreux autres objets dignes d'intérêts : comonades, monoïdes, arrows, applicative functors...).

[LLB]

Néanmoins, en tant que programmeur peu expérimenté, je me demande pour quels types d'appli cette approche est utile ...

En Haskell, le premier intérêt est la monade IO pour les entrées sorties. Pour Caml, c'est un peu différent, vu que ce n'est pas un langage pur (en Haskell, on peut pister les effets de bord grâce aux monades, ce qui n'est pas le cas pour Caml).

F# possède aussi des monades, ça me semble assez proche des exemples Caml que j'ai vus (la syntaxe est un peu différente). Les deux utilisations les plus convaincantes pour F# sont la bibliothèque asynchrone et FParsec, bibliothèque de parsing très sympa.

Un intérêt est de construire un mini-langage spécifique, contrôlé par la monade. Exemple avec FParsec :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let simple: Parser<_> =
    parse {let! a = letter
           do!  skipChar ','
           let! b = letter
           return a, b}

Ce code parse une lettre, suivie de ',' puis d'une autre lettre. Si le flux ne contient pas de lettre au début, ou s'il manque la virgule, le code s'interrompt automatiquement (et la position de l'erreur est mémorisée).

Si on voulait obtenir la même chose sans monade, il faudrait que chaque appel de fonction prenne en argument une fonction anonyme qui indique l'appel suivant. Bref, beaucoup d'appels imbriqués et ce serait très moche / dur à maintenir.

Ici, c'est la monade qui gère tout. On écrit du code qui ressemble à du F# classique, mais il est exécuté différemment. C'est elle qui décide si elle exécute la ligne suivante, ou non. C'est aussi elle qui transmet l'état (ici, la position dans le flux) de façon transparente.


Je ne sais pas s'il y a d'autres bibliothèques Haskell qui seraient intéressantes à porter en Caml ou F#, avec des monades. Des suggestions ?

[gasche]

Et bien, la monade Writer par exemple peut être intéressante (faire des calculs en "loggant" des choses tout du long), ou des monades non-déterministes, etc. Les monades sont aussi assez pratiques pour manipuler les continuations. L'article auquel je faisais référence utilise des monades pour faire passer des exceptions.

[gorgonite]

les monades sont un beau moyen de faire du CPS en Caml sans alourdir le code

[gasche]

À mon avis, on n'a pas encore exploité tout le potentiel côté sucre syntaxique. Pour l'instant on a le sucre Haskellien (do ... <- ...) disponible, mais je pense que la vieille syntaxe "let!", qui a été repris par F#, est en fait plus adaptée à la syntaxe ML.

Il y a encore un peu de recherche de ce point de vue là (la question de l'intégration avec d'autres extensions syntaxiques se pose, etc.), mais je pense qu'on pourrait arriver à quelque chose de plus flexible encore que les Workflows F# (qui sont assez peu extensibles au niveau de la syntaxe du DSL, pour ce que j'en ai vu), et qui intègre élégamment les monades.

[LLB]

Ce qui est intéressant, c'est que l'on peut copier directement du code F# classique dans une monade. Les mot-clés habituels sont disponibles : let, use, if, for, while, do, en plus des mot-clés spécifiques (let!, do!, use!, return, return!). Mais tu as raison, on est limité à cette syntaxe (le sucre est intégré au compilateur, et non à un préprocesseur externe).

[gasche]

Oui et non, parce que cela dépend de ce que tu appelles "mettre son code dans une monade". Si tu veux affecter ton code par l'action de la monade (ce qui est en général l'intérêt des zones monadiques), il faudra quand même transformer tes let en let!, etc.

C'est un compromis qui se respecte : l'autre approche serait de traduire directement (dans la zone DSL) "let" en Bind, et d'avoir un mot clé spécifique pour "le let normal", mais ce n'est pas un meilleur choix non plus, parce que les programmeurs préfèrent en général être prudent et utiliser explicitement les effets monadiques et pas l'inverse.

(Et sinon, je suis intéressé par une réponse dans le papa-forum)

[SpiceGuid]

Je ne me suis jamais penché sur la question, c'est sans doute trop abstrait pour moi.
Par contre j'en ai probablement déjà utilisé, comme jadis monsieur Jourdain.

Tout petit extrait d'un interpréteur où j'ai caché l'implémentation des opérations de lecture/écriture (y-a-t-il monade ou pas ?) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
type lisp_expr =
  ...
  | Load of unit -> lisp_obj
  | Save of lisp_obj -> unit * lisp_expr
  ...

[gasche]

Euh à priori, non. Déjà une monade est définie à partir d'un foncteur (un type paramétré à un paramètre avec une fonction "map"), donc tu aurais au mieux une spécialisation monomorphe d'une moande.

En plus, dans ton cas la modification de l'état du monde (qui s'effectue dans l'entrée/sortie et est représentée ici par le type unit) est implicite, alors que les monades sont justement très explicites dans leurs manipulations (c'est du "très explicite factorisé dans une bibliothèque à l'interface simple pour le programmeur").

Par ailleurs, il ne faut pas chercher les monades que dans les types d'entrée/sortie, car elles peuvent servir à bien d'autre choses. Si tu es curieux de savoir s'il y en a dans ton code (c'est très amusant, mais ça ne va pas te changer la vie), il faut que tu commences par regarder tes types paramétrés, ou alors les types facilement généralisables. Si tu as un type paramétré 'a t, voire en plus une fonction 'a -> 'a t qui ne "fait pas grand chose", c'est un bon début.

Enfin, ce n'est pas non plus la peine de chercher des monades "partout". On m'a récemment demandé si un bout de code utilisait des monades et euh, j'ai été bien embêté parce que la plupart du temps la réponse est entre "non", "oui la monade triviale identité har har har" et "euh si vous me donnez deux heures je peux sans doute généraliser à fond, trouver une monade et écrire un blog post dessus". C'est un peu comme si tu prenais un bout de code de Programmation Orientée Objet au hasard et que tu demandes à son auteur "montre moi un Design Pattern dans ton code" (il y a des gens qui prennent assez au sérieux l'analogique monade/design_pattern, mais en tout cas en matière de "truc fashion super pour blogger", c'est réussi).

[james-mi]

Je ne sais pas s'il y a d'autres bibliothèques Haskell qui seraient intéressantes à porter en Caml ou F#, avec des monades. Des suggestions ?

Peut-être dans ce tuto excellent qui explique les biblios Haskell et leur utilisation concrête ?

[SpiceGuid]

http://www.haskell.org/arrows/
http://www.haskell.org/ghc/docs/late...rol-Arrow.html

Je trouve que les arrows sont plus fonctionelles dans l'esprit, et par conséquent bien plus "familières" (je n'ai pas dit plus "naturelles") que les monades.

Code Caml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
module type ArrowRequirements = sig
  type ('a,'b) arrow
  val  make : ('a -> 'b) -> ('a,'b) arrow 
  val  (>>>) : ('a,'b) arrow -> ('b,'c) arrow -> ('a,'c) arrow
  val  first : ('a,'b) arrow -> ('a * 'c,'b * 'c) arrow 
end;;

Mon petit doigt me dit que:

• le type arrow désigne simplement un bidule-truc qui se comporte un peu comme la flèche
• étant donné une fonction 'a -> 'b le constructeur make nous fabrique une flèche α → β
• étant données une flèche α → β et une flèche β → γ l'opérateur de composition (>>>) nous donne une flèche α → γ
• étant données une flèche α → β et un type γ l'opération first nous donne une flèche α × γ → β × γ, si j'ai bien compris il s'agirait d'un moyen de combiner α → β avec l'identité γ → γ

Mais mon petit doigt se trompe (trop) souvent.

Il y aurait éventuellement un opérateur de boucle qui semble fonctionner à l'inverse de l'opérateur first puisqu'il nous donne la flèche α → β à partir de la flèche α × γ → β × γ (toujours si j'en crois mon petit doigt).

Tout cela me paraît assez raisonnable, il ne me reste plus qu'à assimiler l'algèbre qu'il y a derrière

[Twinside]

...
(elles sont sous les projecteurs, mais il y a de nombreux autres objets dignes d'intérêts : comonades, monoïdes, arrows, applicative functors...).

Punaise j'ai essayé de transformer pendant 2h à un code qui ressemblait fortement à quelque chose de monadique, sans arriver à rien, alors qu'il me fallait une comonade....

Typiquement en partant d'un AST avec des identifieurs en string pour arriver à un AST avec des index vers la table des symboles tout en trimballant l'environnement autour :]

Si j'ai le temps je vais tenter de le réecrire tient

[SpiceGuid]

si en 2h tu as compris les co-monades alors tu n'as probablement pas perdu ton temps

Edit:

Ce que mon petit doigt me dit sur les monades:

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
module type MonadRequirements = sig
    type 'a t
    val  bind : 'a t -> ('a -> 'b t) -> 'b t
    val  return : 'a -> 'a t
end;;

• return est un constructeur pour le type t
• bind sert à mapper 'a t vers 'b t
• dans son usage élémentaire bind se comporte comme un let, il sert à lier une valeur à une variable
• dans son usage élémentaire return se comporte comme in, il construit une nouvelle valeur à l'aide des variables liées par bind

Un intérêt est de construire un mini-langage spécifique, contrôlé par la monade. Exemple avec FParsec :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let simple: Parser<_> =
    parse {let! a = letter
           do!  skipChar ','
           let! b = letter
           return a, b}

Quand on peut facilement remplacer bind par let et return par in pourquoi s'en priver ?
Le même exemple à l'aide du module Lex:

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let simple () =
 let  a = Lex.demand_char ()
 and () = Lex.demand_mono ','
 and  b = Lex.demand_char ()
 in  a,b

[gasche]

Les flèches sont nettement plus compliquées que les monades. En particulier, les équations sur les flèches (comme les "lois" des monades), c'est à dire les conditions de naturalité qu'une flèche doit nécessairement vérifier pour qu'elle se "comporte bien", sont complexes, et encore en mouvement (il est sorti un paper il y a un an ou deux apportant de nouvelles perspectives sur la question; pour ce qui est théorique, même en info c'est pas mal bleeding edge).

Si tu trouves les flèches plus naturelles que les monades, voici une image qui est peut-être pas complètement fausse, et qui pourrait t'aider : l'idée des flèches c'est d'avoir des machins de style 'a -> 'b, mais d'ajouter des fonctionnalités (du bling bling) en sous-main pour faire des choses magiques sans que le programmeur s'embête. Une flèche, ça peut rajouter du bling des deux côtés d'une fonction : en entrée ('a), et en sortie ('b); les fonctions permettent de "rajouter le bling de base" autour d'une fonction pure, de combiner des fonctions avec bling, etc.

Une monade, c'est un peu pareil, mais il n'y a du bling que d'un seul côté. Ce qui correspond à une ('a, 'b) arrow, c'est une 'a -> ('b monad). C'est une présentation (formellement, les flèches de Kleisli) qui n'est pas exactement celle des monades en Haskell, mais qui lui est équivalente. Dans ce point de vue, tu peux analyser bind et return ainsi :
- return : ajoute du bling "à la fin" (par analogie avec 'a -> 'b m)
- bind : permet de composer le bling (si tu as ('a -> 'b m) et ('b -> 'c m), pour obtenir un ('a -> 'c m) tu utilises un bind intermédiaire).

Selon cette vision des choses, les monades c'est des fonctions avec bling "seulement à la fin", alors que les arrows ont du bling des deux côtés. Ça explique pourquoi les monades sont plus simples; ça explique aussi pourquoi on a besoin des arrows : dans certain cas, on a besoin de bling aussi au début (par exemple pour des parsers, cf. le paper d'introductions aux arrows).

[SpiceGuid]

Pour les concepts catégoriques comme les foncteurs, la naturalité, l'adjonction, il y a l'introduction de Fokkinga (voir mon hébergement), où c'est très très bien expliqué (ce qui ne veut pas dire que je maîtrise tout hein ).

[SpiceGuid]

Ce code parse une lettre, suivie de ',' puis d'une autre lettre. Si le flux ne contient pas de lettre au début, ou s'il manque la virgule, le code s'interrompt automatiquement (et la position de l'erreur est mémorisée).

Ça c'est typiquement le boulot d'un raise, non ?

Si on voulait obtenir la même chose sans monade, il faudrait que chaque appel de fonction prenne en argument une fonction anonyme qui indique l'appel suivant. Bref, beaucoup d'appels imbriqués et ce serait très moche / dur à maintenir.

Une fois résumé par spiceguid ça donnerait ceci:

• pourquoi utiliser une exception là où je peux faire du CPS ?
• et du coup: pourquoi faire du CPS là où je peux utiliser des monad combinators ?

Faites quand même attention à réserver les solutions peu accessibles aux problèmes peu accessibles, on a pas tant de débutants (motivés) qu'on puisse se permettre de les pousser vers des solutions radicales dont la motivation originale est quand même de contourner une conception radicale (et sans doute plus cohérente) qui n'est pas celle de Caml et encore moins de F#.