URL: https://linuxfr.org/users/aluminium95/journaux/compilateur-et-monad-reader Title: Compilateur et Monad Reader Authors: Aluminium95 Date: 2015年11月20日T19:35:20+01:00 License: CC By-SA Tags: Score: 23 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 : 1. En C, on a des variables locales aux fonctions, mais aussi des variables locales aux blocs 2. 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 à : 1. La table de correspondance pour les variables globales/chaines constantes (table constante) 2. La table de correspondance pour les variables locales à la fonction que l'on compile (table qui varie pendant la compilation) 3. 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 : ```ocaml 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 : ```c { 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 : ```ocaml 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 : ```ocaml '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 : ```ocaml 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` ```ocaml (* 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 : ```ocaml (* 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 ! ```ocaml (* 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 : ```haskell -- 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 ....

AltStyle によって変換されたページ (->オリジナル) /