Journal Compilateur et Monad Reader

Posté par Aluminium95 le 20 novembre 2015 à 19:35. Licence CC By‑SA.

Étiquettes : aucune

nov.

2015

Sommaire

Architecture générale
Et Monad Reader dans tout ça ?
Monad Reader
- Ah, les belles monades que j'ai
- Conclusion

Bonjour nal,

J'ai eu récemment du écrire un « micro-compilateur » pour un sous-ensemble de C vers du code assembleur x86_64. Un impératif du projet étant d'être écrit en OCaml, j'ai donc opté pour un style fonctionnel de programmation. C'est donc l'occasion de râler parce que « en haskell c'est plus mieux » le fonctionnel ;-).

Ce journal va expliquer pourquoi, en pratique, utiliser une monade de lecture c'est cool en Haskell, et pourquoi, toujours en pratique, ce n'est pas vraiment faisable en OCaml.

Architecture générale

Je ne vais pas ici faire la description complète du sous-ensemble traité, de sa sémantique, ou de la manière dont on code en x86_64. Mais pour comprendre d'où vient la suite, il faut savoir deux trois choses :

En C, on a des variables locales aux fonctions, mais aussi des variables locales aux blocs
En assembleur, il y a trois endroits où mettre des choses :
1. La pile : qui part plus ou moins de la fin de la mémoire, et qui empile des éléments de plus en plus vers le « haut » de la mémoire (adresses décroissantes)
2. Le tas : qui part de la fin du code du programme (qui est en mémoire) et qui part vers les adresses croissantes (donc peut potentiellement rencontrer la pile … si on ne fait pas attention).
3. La section .data du programme, qui est un « trou » de taille fixe dans le code du programme, que l'on peut remplir (on décide de sa taille en écrivant le programme).

Le compilateur devait réserver assez d'espace dans .data pour y mettre les variables globales et les chaînes constantes du programme C. Les variables locales devaient se trouver sur la pile. Le tas n'était pas utilisé par le compilateur, mais l'utilisateur peut lancer la commande malloc qui va faire le travail pour allouer un bloc mémoire sur le tas.

La mémoire RAM contient à peu près cela quand on lance un programme :

début mémoire | .data | code programme | tas ---->                           <---- pile | fin mémoire

Et Monad Reader dans tout ça ?

Et bien on y arrive !
Pour pouvoir retrouver les positions dans .data des variables globales et des chaînes constantes, il faut une table de hashage.
Pour la pile, c'est encore pareil : on fixe un registre qui va contenir le début de notre zone de variables locales (ici %rbp), et on se repère par rapport à lui pour trouver la n-ème variable. La fin de la pile est exactement la valeur du registre %rsp (Stack Pointer).

                          |   VARIABLES LOCALES   | ------AVANT----- | fin mémoire
                          ^ %rsp                  ^ %rbp

On comprend donc que quand on compile, on a besoin d'avoir plus ou moins tout le temps accès à :

La table de correspondance pour les variables globales/chaines constantes (table constante)
La table de correspondance pour les variables locales à la fonction que l'on compile (table qui varie pendant la compilation)
Le nombre de variables ajoutées pour ce bloc-ci de la fonction que l'on compile (pour pouvoir les supprimer à la sortie du bloc)

On arrive à des fonctions qui ont la tête suivante :

type compil_ctx = { globales : ... ; strs : ... ; locales : ... ; autres choses ... };;

let compile_1 ctx ... = ...
let compile_2 ctx ... = ... compile_1 ctx .. 
etc.

Pour simplifier l'écriture du code, toutes les fonctions prennent l'intégralité du contexte de compilation en premier argument (ce qui uniformise le type de fonctions). Seulement, cela fait qu'on se trimballe en permanence ce « ctx » … pas très joli !

De plus « ctx » n'est pas modifiable : c'est une structure de donnée persistante, parce qu'on veut conserver le contexte précédent quand on fait un appel en utilisant un nouveau contexte. Par exemple pour compiler le code suivant :

{
   int i;       // <---- ctx : { Numéro i = 1 }
   {
      int x;    // <---- ctx' : { Numéro i = 1 ; Numéro x = 2 }
   }
   ... code ... // <--- ctx : { Numéro i = 1 } 
   {
      int y;    // <---- ctx'' : { Numéro i = 1 ; Numéro y = 2 }
   }
}

On ne va donc pas en faire une variable globale du programme (ou alors il faut faire une variable globale qui contient la suite des contextes, afin de pouvoir revenir en arrière, et j'ai trouvé ça moche).

Monad Reader

Sortons les mains du cambouis, et regardons un peu ce que l'on a fait. On a un ensemble de fonctions, qui prennent un même premier argument. Si on écrit leur type il est donc :

generalType : ctx -> ...

Or, ce n'est absolument pas facile de le décrire (les « … » peuvent vouloir dire plein de choses). Si on inverse l'ordre des arguments, et qu'on a donc le contexte qui est toujours le dernier argument. Alors toutes les fonctions sont en réalité des fonctions qui ont un type :

'a generalType : ... -> ctx -> 'a

C'est déjà beaucoup mieux, puisque cela revient à dire que ce sont des fonctions quelconques qui retournent un type bien particulier :

type 'a reader_ctx = (ctx -> 'a)

Ce qui est tout à fait logique : on transforme les constantes en applications qui prennent un contexte et retournent une constante, et des fonctions qui retournent un résultat en des retournent un résultat si on leur donne un contexte.

Ah, les belles monades que j'ai

Maintenant qu'on a transformé les constantes, on ne peut plus travailler dessus ! Et bien, il faut s'en occuper. Soient 'a et 'b deux types de constantes, imaginons qu'on ait une fonction f : 'a -> 'b, on peut construire une fonction fmap f : 'a reader_ctx -> 'b reader_ctx

(* f est une fonction de a vers b
 * g est un 'a reader_ctx
 * 
 * On commence par calculer la valeur de g dans le contexte
 * et ensuite on applique f sur son résultat
 *)
let fmap f g = (fun ctx -> let res = g ctx in f res);;

Bon, ok, c'est cool. Mais comment je fais pour composer mes fonctions hein ? Parce qu'au départ, c'est ce qui m'intéresse, pouvoir chaîner des fonctions sans passer explicitement le contexte !

Pour cela il suffit de deux fonctions :

(* transforme un 'a en un 'a reader_ctx *)
let return x = (fun ctx -> x)

(* chaîne deux opérations 
 * x :: 'a reader_ctx 
 * f :: 'a -> 'b reader_ctx 
 * 
 * bind x f :: 'b reader_ctx 
 *)
let bind x f = (fun ctx -> 
                    let res = x ctx in 
                    let newReaderCtx = f res in 
                    newReaderCtx ctx)

Maintenant on peut chaîner des choses !

(* on code des fonctions de base qui utilisent le contexte *) 
let get_var_addr s = (fun ctx -> .... );; 

(* ou des fonctions qui ne dépendent pas du contexte *)
let pushq addr = return (printf "pushq %s" addr);;

(* Et on peut les composer sans passer explicitement le contexte *)
let push_var_on_stack s = 
    bind get_var_addr (* chaine la fonction get_var_addr *)
         (fun addr -> 
              pushq addr);;

(* let push_var_on_stack s = bind get_var_addr pushq *)

let calcul ctx = push_var_on_stack "test_variable" ctx;;

Et là … on rage parce que cela prend plus de caractères que d'écrire la variable ctx partout ! (sauf bien sûr, dans l'exemple que j'ai pris où tout se simplifie …).
On va donc voir du côté de Haskell, qui a une syntaxe dédiée pour écrire des bind facilement, le code traduit est en effet beaucoup plus clair, et rapide à taper :

-- on code des fonctions de base qui utilisent le contexte
get_var_addr s = (\ctx -> ... )

-- ou des fonctions qui ne dépendent pas du contexte 
pushq addr = return (printf "pushq %s" addr) -- REM: ce n'est pas du haskell valide ici 

-- Et on peut les composer sans passer explicitement le contexte
push_var_on_stack s = do 
                         addr <- get_var_addr s 
                         pushq addr

Conclusion

Tout ça pour dire que c'est vraiment beau de pouvoir traduire presque aussi littéralement ce que l'on attend du programme … Tout en ne perdant pas la puissance du code moche avec des « ctx » partout !

PS: c'est une introduction vachement longue pour un truc pas si formidable que cela au final, mais bon, c'était le premier exemple « réel » où j'avais vraiment une envie irrésistible d'utiliser une monade … qui au final ne sert vraiment que si on a une syntaxe adaptée qui va avec ….

# Notation do

Posté par antoyo le 20 novembre 2015 à 20:09. Évalué à -1.
Salut !
En Haskell, on préfère éviter la notation do.
En effet, si l’on prend ton dernier exemple, cela est plus court :
```
push_var_on_stack s = get_var_addr s >>= pushq
```
Ou même (si ma mémoire est bonne) :
```
push_var_on_stack = pushq <=< get_var_addr
```
- [^] # Re: Notation do
  
  Posté par Guillaum (site web personnel) le 20 novembre 2015 à 21:08. Évalué à 6.
  
  Alors, c'est personnel, mais ce n'est pas parce que le pointfree existe et qu'il y a plein d’opérateurs marrant qu'ils faut les utiliser.
  
  Autant je trouve que la version 1 est lisible. Mais (Je me permet de corriger l’opérateur ;) (<=< existe, mais c'est la combinaison de kleishi inverse, enfin bref ;)
  push_var_on_stack = pushq =<< get_var_addrAussi, je crois que Haskell on prefere le camelCase ;)
  - [^] # Re: Notation do
    
    Posté par antoyo le 20 novembre 2015 à 21:40. Évalué à 1.
    Cet article explique pourquoi il vaut mieux l’éviter.
    
    D’ailleurs, je ne dis pas qu’il faut l’éviter à tout prix. Quand je programmais en Haskell, je l’utilisais de temps à autre, mais pourquoi faire ceci :
```
main = do
    line <- getLine
    putStrLn line
```
    quand on peut faire cela :
```
main = do
    getLine >>=
    putStrLn
```
    ?
    
    En passant, merci pour la correction.
    
    P.S.: il est préférable d’utiliser la notation suivante pour créer un block de code Haskell :
```
` ``haskell
main = {- Code Haskell -}
` ``
```
    (sans l’espace entre le premier ` et les deux autres)
    - [^] # Re: Notation do
      
      Posté par Aluminium95 le 21 novembre 2015 à 00:24. Évalué à 3.
      quand on peut faire cela :
      
      main = do getLine >>= putStrLn
      
      Le do ne sert à rien ici par contre, autant écrire main = getLine >>= putStrLn directement ;-).
      - [^] # Re: Notation do
        
        Posté par antoyo le 21 novembre 2015 à 18:31. Évalué à 1.
        
        Tu as raison, c’est ce que je voulais écrire.
- [^] # Re: Notation do
  
  Posté par Aluminium95 le 21 novembre 2015 à 00:19. Évalué à 5.
  Mmh, oui. C'est une question pertinente, sauf que si la syntaxe existe, c'est parce qu'elle permet de simplifier de manière élégante les multiples binds imbriqués.
```
faire_un_calcul_complexe x = do 
                             a <- premiere_etape 
                             deuxieme_etape
                             c <- troisieme_etape a
                             return (a,c)
```
  Qui est quand même bien plus simple que la même chose avec des binds (lisibilité, et le code facilement modifiable) :
```
faire_un_calcul_complexe x =  
                             premiere_etape >>= (\a -> 
                             deuxieme_etape >> 
                             troisieme_etape a >>= (\ b -> 
                             return (a,c)))
```
  La solution, c'est de faire des fonctions très simples, pour que ce soit toujours raisonnable, sauf que dans le cadre d'un compilateur, quand tu veux traduire une opération, la manière naturelle de décrire un while va être triviale avec la notation do (alors que sans, on va utiliser pleins de >> qui ne feront que « décorer » le code de manière inutile) :
```
compile (While e c) = do
                         cond <- makeLabel "COND"
                         body <- makeLabel "BODY"
                         jump cond
                         printLabel body
                         compile c
                         printLabel cond
                         compileExpr e
                         jumpIfNonZero body
```
  Qui se comprend en regardant la « traduction assembleur »
```
[While e do c]
    jmp .COND
.BODY
    [c]
.COND
    [e]
    popq %rax
    cmpq $0, %rax
    jne .BODY
```
  La notation do permet de conserver la même « forme » de traduction, ce qui est pratique à la fois pour la lecture (compréhension) et la modification (on peut facilement permuter deux lignes si on a loupé un truc).
  - [^] # Re: Notation do
    
    Posté par octachron le 21 novembre 2015 à 13:28. Évalué à 1.
    
    Je n'ai été jamais complètement convaincu par la notation do comparé à utiliser directement >>= et >>.
    La notation do est certainement plus élégante, mais bien moins explicite. Pour en revenir à OCaml, il faut tout de même noter qu'il est parfaitement possible d'utiliser >>= plutôt que bind. De même, il existe de nombreuses extensions de syntaxe qui permettent d'utiliser la notation do en OCaml; j'en compte au moins 4 disponibles directement avec opam.
    - [^] # Re: Notation do
      
      Posté par Aluminium95 le 21 novembre 2015 à 14:01. Évalué à 1.
      Je n'ai été jamais complètement convaincu par la notation do comparé à utiliser directement >>= et >>.
      
      Cela dépend vraiment des utilisations, mais dans le cas où on fait énormément de calculs séquentiels, c'est vraiment plus clair. Par exemple, on peut imaginer (encore dans le cadre d'un compilo) écrire le code suivant
      
      compileExpr (Bin o a b) = compileExpr a >> compileExpr b >> popq "%rax" >> popq "%rdx" >> asmBinop o "%rdx" "%rax" >> pushq "%rax" -- Or, c'est pénible à lire, pénible à modifier facilement (couper/coller des lignes, sélectionner des parties du code) -- donc on finit par écrire comme ça pour que cela soit plus pratique : compileExpr (Bin o a b) = compileExpr a >> compileExpr b >> popq "%rax" >> popq "%rdx" >> asmBinop o "%rdx" "%rax" >> pushq "%rax" -- Et on a ré-inventé la notation do en moins bien
      
      La vraie question, c'est si on retire la notation do, pourquoi ne pas retirer les list comprehension ? Parce que c'est exactement la même chose : [ x + y | x <- [1..], y <- maListe ] est parfaitement équivalent à [1..] >>= (\x -> maListe >>= (\y -> return (x + y))) … Je suis presque sûr que la première est bien plus claire, et bien plus utilisée, en fait, elle est même ajoutée dans des langages comme Python (qui n'a pas de monade liste explicite).
      
      nombreuses extensions de syntaxe qui permettent d'utiliser la notation do en OCaml; j'en compte au moins 4 disponibles directement avec opam.
      
      En effet, mais ce n'est pas intégré au langage, il faut gérer cette dépendance si on l'utilise dans un projet, et il faut sélectionner un des 4, qui sont certainement légèrement différents, ce qui demande un travail supplémentaire (et je suis flemmard).
# Monad et do

Posté par Guillaum (site web personnel) le 20 novembre 2015 à 21:19. Évalué à 3.

Quand j'ai découvert Haskell, j'ai cru que c’était le plus beau langage du monde. Ce qui est le cas (a part quelques trucs subtiles).

Puis j'ai compris certains concepts, alors j'ai voulu les appliquer au c++. La première chose que j'ai fais c'est implémenter mon propre Maybe. (qui se nomme std::optional dans c++17 le draft).

Mais en fait, cela n'a AUCUN intérêt sans la do notation malheureusement puisque cela force a chainer des lambdas. Exemple :
maybe<float> doSomething(...) { return doSomethingInt(...).bind([](int ret){ return doSomethingFloat(ret); }); }
# Lien

Posté par max22 le 21 novembre 2015 à 17:38. Évalué à 2.

Pourrais-tu mettre un lien vers le code ?
- [^] # Re: Lien
  
  Posté par Aluminium95 le 21 novembre 2015 à 18:36. Évalué à 1.
  
  Il est tellement moche que je n'oserais pas mettre un lien ;-).
  
  En plus, comme je n'ai pas utilisé des extensions caml, les opérations monadiques sont moches, donc, finalement, je me trimballe le contexte (du coup il n'a pas vraiment de rapport avec ce qui est fait dans le journal).
  
  En revanche, pour ce qui est la sémantique du sous-ensemble, des références x86_64, et les contraintes du projet en général, voilà le lien qui va bien.
  
  Pour finir, je n'ai eu à écrire que la partie « compilation » (donc pas de parsing), et sans aucune obligation de produire du code assembleur « optimisé » à partir de l'AST : en gros c'est plus ou moins traduire de manière naïve chaque construction C en assembleur, et faire le code Caml qui s'en charge. Donc je doute fortement que lire le code serve à quelque chose : une explication écrite de « comment traduire naïvement telle construction » serait bien plus compréhensible (et apporterait autant).
  - [^] # Re: Lien
    
    Posté par Drup le 22 novembre 2015 à 16:23. Évalué à 1. Dernière modification le 22 novembre 2015 à 16:24.
    
    Il est tellement moche que je n'oserais pas mettre un lien
    
    Et tu ne t'es dit a aucun moment que peut être, juste peut être, tu essayais de forcer les idiomes haskell en OCaml ?
    
    La monade reader est un artifice Haskellien pour palier aux restrictions sur les effets de bords. Elle ne sert rigoureusement a rien en caml.
    
    OCaml a ses propres idiomes et essayer d'écrire du Haskell en OCaml termine tout aussi bien que d'essayer d'écrire du C en python. C'est d'autant plus vrai quand tu rends volontairement le code OCaml encore plus lourd qu'il ne devrait l'être.
    - [^] # Re: Lien
      
      Posté par kantien le 22 novembre 2015 à 16:52. Évalué à 2.
      
      La monade reader est un artifice Haskellien pour palier aux restrictions sur les effets de bords. Elle ne sert rigoureusement a rien en caml.
      
      C'est on ne peut plus vrai. OCaml est multi-paradigme, ce qui est, je pense, un avantage. De plus, la persistance ne veut pas dire sans « effet de bord » mais « observationellement immuable », comme l'on fait ici MM. Cochon et Filliâtre pour le problème union-find (avec preuve en coq de la persistance de la structure de données).
      
      Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
    - [^] # Re: Lien
      
      Posté par Aluminium95 le 24 novembre 2015 à 10:14. Évalué à 1.
      
      Je me suis peut-être mal fait comprendre … Mais j'ai bien précisé que vu que le code était moche, j'avais abandonné l'idée, et je passe le contexte en argument des fonctions de manière explicite, ce qui n'est pas ce qui est fait dans le journal (cf: commentaire auquel tu réponds).
      
      J'en suis arrivé exactement à la même conclusion que toi : sans syntaxe adaptée, c'est plus lourd qu'autre chose, et donc je ne l'ai pas utilisé.
      
      Sinon, « peut être, juste peut être » est un peu condescendant je trouve, même si le problème de communication vient probablement de moi.
# Méconnaissance

Posté par Dinosaure (site web personnel) le 22 novembre 2015 à 12:59. Évalué à 4.
En gros, cette article montre seulement que tu ne sais pas définir un opérateur infixe en OCaml:
```
let ( >>= ) = bind
```
- [^] # Re: Méconnaissance
  
  Posté par kantien le 22 novembre 2015 à 16:30. Évalué à 5. Dernière modification le 22 novembre 2015 à 16:31.
  Je ne répond pas pour ajouter quelque chose au commentaire de Dinosaure, mais pour interroger ceux qui l'ont moinsé ? Why ?
  
  Pour rappel, Dinosaure est l'organisateur des rencontres OCaml User In Paris et donc un développeur OCaml expérimenté.
  
  Sa réponse était certes lapidaire, mais on ne peut plus juste.
  Ainsi, après avoir définit son opérateur infixe, le code d'aluminium95 :
```
(* Et on peut les composer sans passer explicitement le contexte *)
let push_var_on_stack s = 
    bind get_var_addr (* chaine la fonction get_var_addr *)
         (fun addr -> 
              pushq addr);;
```
  devient
```
let ( >>= ) = bind;;

let push_var_on_stack s = get_var_addr s >>= pushq;;
```
  comme proposé par le tout premier commentaire, c'est plus compliqué que la notation do ?
  
  En programmation fonctionnelle, on manipule des fonctions et des opérateurs, et donc on les compose (comme en mathématique). On utilise la notation infixe pour les opérateurs de composition, comme le pipe du shell qui en OCaml se définit usuellement :
```
let ( |> ) f g = g f;;

(* exemple *)
# [1; 2; 3] |> List.map (( + ) 2);;
- : int list = [3; 4; 5]
```
  Là où son code Haskell final était :
```
-- Et on peut les composer sans passer explicitement le contexte
push_var_on_stack s = do 
                         addr <- get_var_addr s 
                         pushq addr
```
  Autrement dit on applique la sortie de get_var_addr à pushq, ce qu'exprime justement l'opérateur bind, ou sa version infixe >>=.
  
  Je maintiens que la notation infixe est bien plus compréhensible et lisible quand on raisonne d'un point de vue fonctionnel.
  D'une ce n'est pas plus long à écrire, et un code est bien plus souvent lu qu'il n'est écrit.
  De deux, aluminium écrit trop :
```
(* écrire *)

let _ = fun addr -> pushq addr;;

(*ou écrire *)
pushq;;

(* c'est du pareil au même, son code de base étant donc *)
let push_var_on_stack s = 
    bind (get_var_addr s) pushq;;

(* et en notation infixe *)
let push_var_on_stack s = (get_var_addr s) >>= pushq;;
```
  Un traitement séquentiel n'est rien d'autre qu'une composition de fonctions et d'opérateurs, pourquoi nommé localement le résultat d'une sortie pour le réaffecter immédiatement dans l'entrée de l'opérateur suivant ? Autant dire : je compose les opérateurs.
  
  @ aluminium95 : comme tu es en première année de l'ENS cachan, et donc en région parisienne, un petit tour au OUPS pourrait t'intéresser. À voir avec Dinosaure si le niveau est accessible à un L1.
  
  Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
  - [^] # Re: Méconnaissance
    
    Posté par Aluminium95 le 24 novembre 2015 à 10:47. Évalué à 1.
    Je pense que le moinssage vient du fait que la notation infixe ne change pas « le problème » que j'ai soulevé (enfin, c'est un problème pour moi), qui est ici le fait de devoir construire des « lambda » à chaque appel de bind (ou >>=).
    
    D'ailleurs, même en haskell, pour une longue composition de fonctions, où tous les résultats intermédiaires sont utilisés dans le dernier bloc, c'est vraiment plus pratique d'avoir une syntaxe plus « impérative », plutôt que a >>= (\x -> b >>= (\y -> c >>= (\z -> ...))). Enfin, c'est une question de goûts, mais la notation infixe n'est pas une réponse à ce problème.
    
    Après, oui (comme je l'ai déjà dit dans un autre commentaire), si on fait des fonctions séparées, bien compartimentées, on a pas besoin de créer des lambdas (en fait, ce sont des fonctions normales), et c'est ce que tu proposes : « Autant dire : je compose les opérateurs ». Sauf que parfois, on construit beaucoup d'opérateurs différents … et c'est là que la notation est pratique.
    
    Enfin, dernier argument pour dire que « la notation infixe ne change pas ce problème » (je note quand même que j'ai précisé dans le journal que, comme toujours, j'ai pris pour seul exemple un qui pouvait se simplifier de manière triviale, et pourtant c'est 2ème commentaire à le reprendre et le simplifier …) :
```
let ( >>= ) = bind;;

let push_var_on_stack s = get_var_addr s >>= pushq;;

(* 
 * sans la notation infixe on perd ~ 4 caractères à la louche,
 * quelle victoire !
 *)
let push_var_on_stack s = bind (get_var_addr s) pushq;;
```
    Une petite remarque, comme dans 99% du temps, les fonctions retournaient un unit (et écrivaient dans la sortie le code correspondant), on peut avoir une syntaxe dans le genre : List.fold (>>) (return ()) [ a ; b ; c ; d ; e ; f], qui peut se transformer en un opérateur asm_code_block [ a ; b ; c ; d ... ], qui avec une bonne indentation permet de retrouver la « forme » du code assembleur (et une notation pseudo impérative de caml) et qui est « facilement compréhensible¹ » :
```
asm_code_block [
    popq "%rdi";
    movq "$1" "%rsi";
    call  "printf";
    ...
] ctx
```
    Donc le problème n'est pas « je ne sais pas définir un opérateur infixe en OCaml ».
    
    PS: un autre problème est que l'évaluation n'est pas paresseuse, et donc il faudrait utiliser le module Lazy, en ajoutant une syntaxe encore plus lourde^2, parce que return (Printf.fprintf out "coucou") est différent de (fun _ -> Printf.fprintf out "coucou"), l'un écrit « coucou » à la construction, l'autre à l'exécution du « reader ».
    
    @kantien : pourquoi pas, je ne suis jamais allé dans un meetup jusqu'à présent.
    
    [1] : parce que cela « ressemble » à une sémantique dénotationnelle, du type [code]{contexte} = valeur,nouveau contexte
    [2] : ou en utilisant des extensions de syntaxe pour que return x === return' (lazy x). Mais je viens de voir qu'un commentaire de Michaël en parlait, du coup je ne suis pas catégorique sur ce point.
    - [^] # Re: Méconnaissance
      
      Posté par kantien le 24 novembre 2015 à 12:02. Évalué à 2.
      J'ai toujours le sentiment que, comme te l'a écrit Drup, tu forces des idiomes haskellien en OCaml :
      
      Et tu ne t'es dit a aucun moment que peut être, juste peut être, tu essayais de forcer les idiomes haskell en OCaml ?
      
      La monade reader est un artifice Haskellien pour palier aux restrictions sur les effets de bords. Elle ne sert rigoureusement a rien en caml.
      
      Les monades sont nécessaires en Haskell, entre autre, parce qu'il n'y a pas de paradigme impératif dans ce langage; en OCaml cet usage est inutile. Si tes fonctions ont une sortie de type unit, alors chaîne les avec le point-virgule ;. Tu peux toujours les encadrés dans un bloc begin ... end, si tu veux visualiser cette structure de bloc d'enchaînement de procédure.
      
      Ensuite, multiplier les fonctions anonymes à tout va, c'est laid et cela rend le code difficilement compréhensible. Je préfère l'usage du let ... in pour les définitions locales, ou dans les cas étudiés dans ton article les lambda sont inutiles : réutiliser le nom de la fonction prédéfinie (ce qui s'étend aux applications partielles). Les lambda (ou dans ma préférence les let ... in) n'ont d'intérêt que si la définition est « complexe », c'est pour cela que dans les exemples de ton journal elles ne servaient à rien.
      
      Enfin, j'exprime, ici, non le point de vue d'une programmeur-développeur en OCaml, mais celui d'un mathématicien-logicien. Lorsque je lis du code OCaml, je le fais à travers le prisme de la correspondance de Curry-Howard (ou correspondance preuve-programme). Du code, de ce point de vue, n'est rien d'autre que la preuve d'un énoncé (les types OCalm sont un sous-ensemble de la logique propositionnelle du second ordre). Une fonction est un énoncé qui prend des prémisses d'un certain type et renvoie une conclusion d'un certain type.
      
      De ce point de vue, les fonctions locales (ou lambda fonctions, fonctions anonymes…) sont l'analogue des lemmes : leur donner un nom, par l'intermédiaire d'un let ... in, ou en les définissant dans l'espace de nom du module, permet au lecteur d'en comprendre plus aisément la signification.
      Si son rôle est celui d'un statut de lemme, il n'est pas nécessaire de l'exporter dans l'interface du module, interface qui ne présentera que les propositions et théorèmes importants qu'il contient.
      Ainsi, l'approche fonctionnelle par composition des opérateurs permet de mieux appréhender les raisonnements effectuer par le développeur, et de raisonner sur le code lui-même.
      
      Le problème n'est pas de résoudre ce que tu as exprimé ainsi :
      
      (* * sans la notation infixe on perd ~ 4 caractères à la louche, * quelle victoire ! *)
      
      mais de pouvoir comprendre facilement, à la lecture, le raisonnement de l'auteur. Une preuve tout à fait correcte, mais illisible, voire incompréhensible n'est pas d'une grande utilité. Et pour tout te dire, à la lecture de ton journal, j'ai du m'y reprendre à plusieurs fois pour comprendre où tu voulais en venir. ;-)
      
      Un exemple intéressant, de ce point de vue, est l'article de Gérard Huet sur le zipper. Que ce soit dans la définition de ses structures combinatoires, dans les fonctions qu'il définit (propositions qu'il prouve), les pattern matching comme raisonnement par cas… la lecture du code est limpide. :-)
      
      Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
      - [^] # Re: Méconnaissance
        
        Posté par Aluminium95 le 24 novembre 2015 à 18:41. Évalué à 2.
        
        La monade reader est un artifice Haskellien pour palier aux restrictions sur les effets de bords. Elle ne sert rigoureusement a rien en caml.
        
        D'accord, encore un problème de communication de ma part ! Je ne veux pas forcer l'utilisation de cette méthode en OCaml. Voilà ce qui se passe :
        
        J'ai un problème avec un contexte
        
        Pour simplifier la lecture, l'écriture, la maintenance de mon code je le passe en argument des fonctions (même si elles ne demandent qu'un sous-ensemble des informations du contexte)
        
        Je constate que toutes les fonctions ou presque sont donc de la forme f ctx ... =
        
        Je remarque qu'en haskell ce paradigme aurait permis d'éviter de passer explicitement le contexte
        
        J'essaye de l'appliquer pour constater que c'est vraiment lourd (même si je n'y ai pas mis toute ma volonté, en utilisant des bibliothèques et extensions de syntaxes pour palier à ce problème)
        
        Juste pour préciser, mon contexte est clairement modifiable (compteur de variables sur la pile par exemple) et que mes fonctions sont tout sauf pures (printf). Donc je ne vois pas en quoi l'impératif a un rapport avec ça : au contraire, en haskell, il faut utiliser ReaderT ctx IO pour pouvoir faire ce que je veux (ce qui devient déjà plus lourd).
        
        Donc une fois de plus, hors sujet.
        
        [^] # Re: Méconnaissance
        
        Posté par lasher le 24 novembre 2015 à 22:39. Évalué à 2.
        
        Bon, question conne, mais, lorsque tu utilises tout le temps le même paramètre, est-ce qu'il n'est pas d'usage d'utiliser des fermetures dans ce cas (ou des foncteurs, ou…)? Genre, en Perl:
        
        my %context = ( prop1 => val1, prop2 => val2, ... ); # on fait des trucs avec le contexte, # bla # bla # bla # Puis : my $applyCtxt = sub { my ($funcref, $fieldname) = @_; &$funcref($context{$fieldname}); }; #exemple à la con qui ne sert vraiment à rien for my $fieldname (sort keys %context) for my $func (\&readStuff, \&writeStuff, \&squareMe, \&doTheBoogieWoogie) { &$applyContxt($func, $fieldname); } }
        
        … Chépasichuiclair. J'ai pas relu le journal, donc j'ai peut-être raté une partie du contexte, mais quand je relis ton résumé de ce que tu cherchais à faire, il me semble que ton contexte est « global », et peut donc être « raccourci » par l'utilisation de fermetures. Évidemment, dans le contexte de Perl, il n'y a pas la possibilité de proposer un opérateur infixe qui ferait le pipelining des fonctions comme en OCaml, mais je n'ai pas l'impression que ce soit ce que tu cherchais à faire de toute manière.
        
        Qu'est-ce que j'ai raté ?
        
        [^] # Re: Méconnaissance
        
        Posté par kantien le 25 novembre 2015 à 15:01. Évalué à 1. Dernière modification le 25 novembre 2015 à 15:04.
        
        Effectivement, je ne vois pas trop où tu veux en venir.
        
        Apparemment ton sujet (d'après le lien que tu fournis) est d'écrire un compilateur pour un sous-ensemble du C. L'analyse syntaxique et la construction de l'AST est déjà faite, tu dois juste t'occuper de la génération du code assembleur. Avec ces contraintes, je ne vois toujours pas où est la nécessité de recourir au monad reader, ni à des extensions ou bibliothèques tierces.
        
        Cet ouvrage (Le langage Caml) pourrait te donner des pistes de réflexions, en particulier les chapitres suivants :
        
        Chap 14 : Simulation d'un processeur (développement d'un simulateur de pico-processeur de type RISC avec son langage d'assemblage)
        
        Chap 15 : Compilation de mini-Pascal (compilation d'un sous-ensemble de Pascal pour le processeur du chapitre précédent)
        
        Partie III : Implémentation en Caml d'un langage mini-Caml (ou l'art du bootstrapping)
        
        Le livre date un peu, 1993 (deuxième édition de 2009), mais les problématiques abordées collent parfaitement à ton problème; de plus les auteurs sont : Pierre Weis et Xavier Leroy (le BDFL d'OCaml). ;-)
        
        En espérant que cela te soit utile pour ton projet.
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: Méconnaissance
        
        Posté par chimrod (site web personnel) le 25 novembre 2015 à 20:47. Évalué à 2.
        
        J'ai beaucoup aimé ce livre. Il commence vraiment par expliquer la récursivité des fonctions, et termine par un programme qui se compile lui même… (ça me rappelle un td du cnam, dont l'objet était d'écrire un compilateur ml -> scala en ocaml…). Par contre, pour qqn qui fait déjà du haskell, je pense que le livre ne lui apprendra pas grand chose : le livre ne rentre pas des les concepts de la programmation fonctionnelle (la notion de foncteur, au sens mathématique n'est pas abordée), et se reste trop général, même si les exemples donnés sont amusant.
        
        @Aluminium : dans ton compilateur, tu construis ton AST avec ocamllex/[ocamlyacc|menhir] ? Là encore, il nous faudrait voir le code pour t'aider davantage…
        
        [^] # Re: Méconnaissance
        
        Posté par kantien le 25 novembre 2015 à 21:37. Évalué à 1. Dernière modification le 25 novembre 2015 à 21:39.
        
        C'est un projet de son cursus, il a donné le lien dans ce message. Il doit juste écrire le code qui transforme l'AST en code assembleur.
        L'archive du projet est disponible là, et il faut écrire le fichier compile.ml dont l'interface est imposée par le fichier compile.mli.
        
        Je lui ai conseillé ce livre pour voir comment ils s'y prenaient pour convertir un AST en assembleur (d'où les chapitres 14 et 15). Je ne vois pas l'intérêt de passer par des monades pour faire cela en OCaml.
        
        Comme il est en L3 à l'ENS, je ne crois pas que la théorie des catégories soit encore au programme.
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: Méconnaissance
        
        Posté par Aluminium95 le 26 novembre 2015 à 07:57. Évalué à 1.
        
        En effet, le travail demandé est plutôt trivial (conversion d'un ast déjà généré en code machine valide) : Le journal n'était pas pour demander de l'aide (ça serait plutôt dans un forum que je demanderais ce genre de choses) mais pour dire que mon code caml était plutôt répétitif (chaque appel de fonction demande un contexte, qui change parfois, mais peu souvent) et que la méthode pour « cacher » cet argument, qui marcherait bien en haskell, était bien trop pénible à mettre en place en caml par rapport aux gains (retirer un argument des fonctions).
        
        Bien sûr, si on propose une solution élégante, je suis preneur (même si j'ai déjà rendu le projet, ça peut toujours servir !).
        
        PS: Un camarade a trouvé une solution plutôt élégante, en remarquant que la création d'un nouveau contexte ne se fait que quand on déclare des variables locales à un bloc, et que donc on peut utiliser une variable globale, qui est modifiée quand on entre dans ce bloc, fait un appel récursif pour les différents calculs d'expression (qui utiliseront la variable globale, donc le nouveau contexte), puis la remet « comme avant » à la fin de la compilation du bloc. C'est doublement élégant parce que cela utilise moins de mémoire (enfin, j'en ai l'impression) en plus de virer les contextes dans les appels de fonctions.
        
        Bien sûr, si on propose une solution élégante, je suis preneur (même si j'ai déjà rendu le projet, ça peut toujours servir !).
        
        PS: Un camarade a trouvé une solution plutôt élégante, en remarquant que la création d'un nouveau contexte ne se fait que quand on déclare des variables locales à un bloc, et que donc on peut utiliser une variable globale, qui est modifiée quand on entre dans ce bloc, fait un appel récursif pour les différents calculs d'expression (qui utiliseront la variable globale, donc le nouveau contexte), puis la remet « comme avant » à la fin de la compilation du bloc. C'est doublement élégant parce que cela utilise moins de mémoire (enfin, j'en ai l'impression) en plus de virer les contextes dans les appels de fonctions.
        
        [^] # Re: Méconnaissance
        
        Posté par chimrod (site web personnel) le 26 novembre 2015 à 10:24. Évalué à 3.
        
        Personnellement je ferai tout à l'intérieur d'une fermeture, comme l'évoquait lasher :
        
        Je donne ici le squelette, à compléter bien sûr pour chaque token. Chaque fonction retournant unit (elle modifie l'environnement), et la fonction compile est récursive puisqu'elle pour traiter la liste des instructions jusqu'à la fin :
        
        open Cparse let rec compile out declarations = (** Les fonctions terminales : ne dépendent pas d'un autre fonction de mise en forme *) let print_operator var = function | M_MINUS -> Printf.fprintf out "-%s" var | M_NOT -> Printf.fprintf out "~%s" var | M_POST_INC -> Printf.fprintf out "%s++" var | M_PRE_INC -> Printf.fprintf out "++%s" var | M_POST_DEC -> Printf.fprintf out "%s--" var | M_PRE_DEC -> Printf.fprintf out "--%s" var and print_pred var = function | S_MUL -> () | S_DIV -> () | S_MOD -> () | S_ADD -> () | S_SUB -> () in (** Fonctions de mise en forme qui dépendent de celles déclarées ci-dessus *) (** Traite les déclarations *) let parse_declaration declaration loc = () (** Traite les fonctions *) and parse_function loc st declarations code = () in (** Point d'entrée du printer *) begin match declarations with | [] -> () | Cparse.CDECL (declaration, loc)::tl -> parse_declaration declaration loc; compile out tl | Cparse.CFUN (loc, st, declarations, code)::tl -> parse_function loc st declarations code; compile out tl end
- [^] # Re: Méconnaissance
  
  Posté par Michaël (site web personnel) le 22 novembre 2015 à 16:44. Évalué à 2. Dernière modification le 22 novembre 2015 à 16:45.
  
  En gros, cette article montre seulement que tu ne sais pas définir un opérateur infixe en OCaml […]
  
  Au lieu de le faire à la main, il peut aussi utiliser, lemonade la bibliothèque de monades pétillante dont je suis l'humble auteur. ☺ On peut l'instsaller avec opam et il y a même une documentation en ligne.
  
  Ensuite il faudrait aussi lui conseiller d'utiliser une extension de syntaxe pour les monades, mais je n;en ai pas encore trouvé qui me plaisait tout à fait. Quelqu'un a-t-il une suggestion?
  
  Il pourrait aussi trouver les lens intéressantes, au lieu d'emboîter des monad reader les uns dans les autres!
  - [^] # Re: Méconnaissance
    
    Posté par Aluminium95 le 24 novembre 2015 à 10:55. Évalué à 1.
    
    En effet, c'est assez joli, mais quand tu fais bind tu dois préciser depuis quel module visiblement (j'ai parcouru très rapidement la doc) ? Si on utilise une unique monade (comme dans mon cas) un open ou un renommage peut faire l'affaire, mais sinon, ne trouves-tu pas ça un peu lourd ?
    
    Il pourrait aussi trouver les lens intéressantes
    
    Pour le coup je ne comprend pas à quoi les lens peuvent servir. Je n'ai jamais vraiment touché aux lens, mais ce n'est pas plus dans l'idée de modifier une structure compliquée en appliquant des modificateurs/lecteurs aux différentes parties ? Si tu pouvais éclaircir ce point j'en serais ravi.
    - [^] # Re: Méconnaissance
      
      Posté par Michaël (site web personnel) le 24 novembre 2015 à 11:45. Évalué à 3.
      
      En effet, c'est assez joli, mais quand tu fais bind tu dois préciser depuis quel module visiblement (j'ai parcouru très rapidement la doc) ? Si on utilise une unique monade (comme dans mon cas) un open ou un renommage peut faire l'affaire, mais sinon, ne trouves-tu pas ça un peu lourd ?
      
      C'est exact. En pratique j'utilise un renommage pour les monades sans paramètre (module Maybe = Lemonade_Maybe) ou un nom assez court pour les applications de foncteur (module Success = Lemonade_Success.Make(struct type t = string end)). Ensuite j'emploie toujours le nom qualifié – l'autocomplétion fournie par merlin marche à merveille – et j'ouvre le sous-module Infix qui définit les opérateurs infixes. En général j'utilise let open Maybe.Infix in dans mes fonctions par exemple, ou bien utilise la syntaxe Maybe.Infix.(m >>= f >>= g).
      
      Limiter le nombre de modules ouverts dans un projet augmente la lisibilité du code, même si on peut facilement utiliser merlin pour lever l'ambiguïté sur un type.
      
      Il y a un projet de recherche – malheureusement j'ai perdu les références – qui implémente des modules disons semi-ouverts pour OCaml, qui permettrait au compilateur de choisir un module en fonction du type des arguments d'une fonction pour résoudre la fonction, ce qui serait très intéressant pour le code monadique ainsi que les fonctions de persistance notamment. J'ai cru comprendre que ce travail devrait être intégré au code officiel. Est-ce que quelqu'un a plus de précisions?
    - [^] # Re: Méconnaissance
      
      Posté par Michaël (site web personnel) le 24 novembre 2015 à 11:55. Évalué à 2.
      Désolé j'ai oublié cette partie
      
      Pour le coup je ne comprend pas à quoi les lens peuvent servir. Je n'ai jamais vraiment touché aux lens, mais ce n'est pas plus dans l'idée de modifier une structure compliquée en appliquant des modificateurs/lecteurs aux différentes parties ? Si tu pouvais éclaircir ce point j'en serais ravi.
      
      Les lens permettent, lorsqu'on travaille avec des niveaux d'organisation imbriqués de réduire la dépendance entre les modules. Par exemple si on écrivait
      
      x.A.y.B.z.C.t
      
      on a une dépendance des modules, car A connaît à la fois B et C et B connaît C. Si on a des empilements plus grands, la chaîne de dépendance à un nombre quadratique en le nombre de modules qui apparaissent – parceque 1 + 2 + … + n ~ 1/2 n² pour n grand. Si on utilise de lens on peut faire en sorte que chaque module ne connaisse que ses voisins, on a fortement réduit le couplage de notre programme car la taille des la chaîne de dépendances passe de quadratique à linéaire. Cela signifie que le coût des modifications devient linéaire au lieu de quadratique (imaginions qu'on change la définition du type de C.t par exemple) ce qui est bien.
      
      Pour la monade Reader on peut utiliser les lens pour composer un environnement de plus en plus riche, au lieu d'empiler des monades liées à différents environnements.
# Correctif

Posté par Michaël (site web personnel) le 22 novembre 2015 à 16:48. Évalué à 4.

En dépit de ce que tu sembles croire, les monades sont plutôt bien supportées en OCaml. La différence majeures avec Haskell est que, OCaml utilisant l'évaluation stricte là où Haskell est paresseux, la définition de l'opérateur >> est essentiellement équivalente à la comoposition >|= ignore >>=.
- [^] # Re: Correctif
  
  Posté par Aluminium95 le 24 novembre 2015 à 10:58. Évalué à 1.
  
  Je vais passer pour un inculte, mais que fait >|= exactement ? Et cela veut dire que quand on écrit >> en caml c'est équivalent à >|= ignore >>= en haskell, ou bien c'est l'inverse ?
  - [^] # Re: Correctif
    
    Posté par Michaël (site web personnel) le 24 novembre 2015 à 11:31. Évalué à 3.
    Je vais passer pour un inculte, …
    
    Mais non enfin, pourquoi donc?
    
    L'opérateur >|= est souvent défini comme map pour la monade, avec un order des arguments qui permet de le composer. Ainsi une définition possible est
```
let map m f =
  bind m (fun x -> return (f x))

let ( >|= ) f m =
  map f m
```
    Une manière classique, dans un contexte fonctionnel, de transformer une évaluation stricte en évaluation paresseuse est de la suspendre dans une fermeture, l'expression expr devient fun () -> expr. Ainsi l'opérateur de séquence qui en Haskell a la signature
```
val ( >> ) : 'a t -> 'b t -> 'b t
```
    est plus communément définit en OCaml avec la signature
```
val (  >> ) : 'a t -> (unit -> 'b t) -> 'b t
```
    qui permet d'implémenter effectivement la séquence – l'ordre des évaluations des arguments d'une fonction ou d'un opérateur n'est pas spécifié – sauf pour les raccourcis booléens, c'est la même convention que le C si je ne me trompe pas – de sorte que la première définition ne garantirait pas que la première valeur dans l'ordre de lecture soit effectivement calculée la seconde.
    
    On pourrait aussi bien choisir la signature
```
val (  >> ) : 'a t -> 'b t lazy -> 'b t
```
    mais en pratique c'est la première option qui est retenue, sûrement parceque le code monadique contient beaucoup de fonctions anonymes, et que les suspensions de type fun () -> x s'y intègrent bien.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.