OCaml et type option : des variables dans un mini interpréteur

Bonjour

Je m’intéresse au type option de OCaml en suivant ce « cours - TP » . Il y est notamment proposé de réaliser un petit interpréteur capable de réaliser des opérations arithmétiques sur des entiers. Comme suggéré en fin de cours, je souhaite ajouter à ce petit « langage » des variables. Je copie ici l’exemple donné par le cours qui montre le résultat attendu :

# eval [("x", 3)] (Neg (Add (Const 2, Var "x")));;
- : int option = Some (-5)

Il s’agit, lors de l’interprétation, de chercher la valeur de la variable x dans une liste passée en paramètre. Voici ma fonction find qui, à un nom de variable associe sa valeur :

let rec find x l = match l with
| [] -> None
| (y1,y2)::ys when x = y1 -> Some y2
| y::ys -> find x ys

Une fois cette fonction réalisée, le TP suggère de modifier la fonction d’évaluation pour traiter les variables, en utilisant l’opérateur (>>=) que j’ai pour ma part codé sous son nom bind (je fais assez peu de programmation et l’utilisation d’opérateurs définis dans le code est encore un peu compliquée pour moi) :

let bind x f = match x with
| None -> None
| Some y -> f y ;;

Voici enfin la définition de mon type expr et de la fonction d’évaluation :

type expr =
| Const of int
| Add of expr * expr
| Neg of expr
| Var of string

let rec eval l e = match e with
| Const n -> Some n
| Var v -> find v l
| Neg e1 -> bind (eval l e1) (fun x -> Some (-x))
| Add (e1, e2) -> bind (eval l e1) (fun x -> bind (eval l e2) (fun y -> Some (x + y)))

Le retour de l’exemple de l’énoncé est correct :

# eval [("x", 3)] (Neg (Add (Const 2, Var "x")));; 
- : int option = Some (-5)

J’ai pourtant l’impression que quelque chose ne va pas. L’énoncé demande en effet de prendre en compte les variables en utilisant l’opérateur bind… ce que je n’ai pas fait. Mon code est-il correct ? Où est censé intervenir l’opérateur bind dans l’évaluation des variables ?

Questions complémentaires : la fonction d’évaluation prend deux arguments : la liste des variables et l’expression à évaluer. Cela me semble un peu lourd de se trimballer dans tous les appels récursifs cette liste de variables, pourrait-on récrire la fonction en évitant cela ? Par ailleurs, que se passe-t-il si cette liste est suffisamment grande ? Notre interpréteur ne pourrait-il pas être très lent à partir d’une certaine taille de liste ? Quelle structure de données pourrait être adaptée à la gestion d’une très grande table de variables ?

Je vous remercie par avance pour vos lumières !

Salut,

J’ai pourtant l’impression que quelque chose ne va pas. L’énoncé demande en effet de prendre en compte les variables en utilisant l’opérateur bind…

Mais si : ton programme est capable d’évaluer les expressions contenant des variables, et il utilise la fonction bind pour cela. Et en lisant le code, il me semble que c’est exactement ce qu’un prof voudrait voir.

Permets-moi de te montrer comment définir l’opérateur infixe >>= comme un synonyme de bind permet d’écrire eval autrement, sous une forme considérée généralement comme plus élégante :

let rec eval l e = match e with
| Const n -> Some n
| Var v -> find v l
| Neg e1 -> eval l e1 >>= fun x -> Some (-x)
| Add (e1, e2) ->
    eval l e1 >>= fun x ->
    eval l e2 >>= fun y ->
    Some (x + y)

Questions complémentaires : la fonction d’évaluation prend deux arguments : la liste des variables et l’expression à évaluer. Cela me semble un peu lourd de se trimballer dans tous les appels récursifs cette liste de variables, pourrait-on récrire la fonction en évitant cela ?

C’est en effet un peu lourd mais il n’y a pas vraiment de moyen de l’éviter. On pourrait bien sûr utiliser une liste globale au lieu d’un argument de la fonction, mais ça se mariera très mal avec le style fonctionnel d’OCaml si on veut rajouter à ton langage la possibilité de définir des variables à l’intérieur des expressions, par exemple, tandis que c’est très facile à rajouter avec la façon de faire actuelle.

Il existe une façon de passer l’environnement de façon plus implicite, avec une technique qu’on appelle une monade de lecture (reader monad), qui est une autre instance de l’idée générale de la fonction bind. Je serais ravi de t’en parler si ça t’intéresse, mais je trouve qu’en général ça complique le code pour pas grand-chose (et dans ce petit code, ça paraît surdimensionné).

Au cas où c’est pas clair, l’intérêt de bind c’est d’avoir un code beaucoup plus concis que le code suivant, qui est équivalent et qui est la solution qu’on a tendance à écrire naturellement quand on ne connait pas les monades :

let rec eval l e = match e with
| Const n -> Some n
| Var v -> find v l
| Neg e1 ->
  (
    match eval l e1 with
    | Some x -> Some (-x)
    | None -> None
  )
| Add (e1, e2) ->
  (
    match eval l e1 with
    | Some x ->
      (
        match eval l e2 with
        | Some y -> Some (x + y)
        | None -> None
      )
    | None -> None
  )

Merci pour tes réponses précises otini. Je vais donc adopter l’opérateur (>>=) puisqu’il semble être omniprésent lorsqu’on parle de monades !

Mais si : ton programme est capable d’évaluer les expressions contenant des variables, et il utilise la fonction bind pour cela.

C’est justement le sens de ma question. Dans le code, sauf erreur de ma part, l’évaluation des variables ne fait pas appel à bind, puisque la ligne concernée de la fonction d’évaluation appelle la fonction find, qui est indépendante de bind :

| Var v -> find v l

Il me semblait être passé à côté de quelque chose, puisque l’énoncé du TP indique :

• Commencez par programmer une fonction valeur x l qui va chercher la valeur correspondant à la chaîne x dans la liste de couples l. Vous pouvez réutiliser la fonction find définie précédemment, ou réécrire une fonction explicitement récursive.
• Adaptez ensuite eval pour qu’elle sache traiter les variables. Grâce à (»=), trois lignes suffisent !

Je pense saisir (au moins une partie) de l’intérêt de bind qui est la propagation des résultats mais surtout des erreurs. Puisque tu le proposes, je suis preneur d’éléments sur la monade de lecture qui pourrait nous éviter de passer la liste des variables en paramètre à chaque appel

C’est en effet un peu lourd mais il n’y a pas vraiment de moyen de l’éviter. On pourrait bien sûr utiliser une liste globale au lieu d’un argument de la fonction, mais ça se mariera très mal avec le style fonctionnel d’OCaml.

Je ne suis pas tout à fait d’accord, pour moi on peut écrire

let eval env expr =
  let rec eval' = function
  | Const n -> Some n
  | Var v -> find v env
  | Neg e1 -> eval' e1 >>= fun x -> Some (-x)
  | Add (e1, e2) ->
      eval' e1 >>= fun x ->
      eval' e2 >>= fun y ->
      Some (x + y)
  in eval' expr

et c’est raisonnable et idiomatique. (En fait je nommerais les deux fonctions eval, mais quand on n’a jamais vu ce motif il vaut mieux les distinguer pour la lisibilité.)

Par contre, c’est vrai que cette approche ne marche que quand le paramètre env est constant dans tous les appels récursifs. Si on ajoute une construction pour ajouter des variables au vol, j’aurais tendance à revenir au style initial. On peut éventuellement faire aussi:

let rec eval env expr =
  let eval' e = eval env e in
  match expr with
  | Const n -> Some n
  | Var v -> find v env
  | Neg e1 -> eval' e1 >>= fun x -> Some (-x)
  | Add (e1, e2) ->
    eval' e1 >>= fun x ->
    eval' e2 >>= fun y ->
    Some (x + y)

qui est utile quand la plupart des cas utilisent le même environnement, mais certains le modifient.

Ce n’est pas lié mais les versions récentes de OCaml ont un tout petit peu de sucre pour les monades, les "opérateurs de bindings" définissables par l’utilisateur:

let ( let* ) = Option.bind
let return v = Some v

let rec eval env expr =
  let eval' e = eval env e in
  match expr with
  | Const n -> return n
  | Var v -> List.assoc_opt v env
  | Neg e1 ->
    let* x = eval' e1 in
    return (-x)
  | Add (e1, e2) ->
    let* x = eval' e1 in
    let* y = eval' e2 in
    return (x + y)

Je ne suis pas tout à fait d’accord, pour moi on peut écrire […]

C’est vrai, maintenant que tu le dis… Autant pour moi.

Merci pour vos réponses. Effectivement gasche, ta première proposition est une solution courante en OCaml, je n’y avais pas pensé dans ce contexte.

Pour m’entraîner à ce concept de monades qui, si je comprends bien, permet de séparer proprement la propagation d’un résultat et la gestion des erreurs, j’ai essayé de « monadiser » un code qui parse des maths à pile.

open Genlex 

let (>>=) x f = match x with
| None -> None
| Some y -> f y 

let lexer chaine =
    let jetons = ["+" ; "-" ; "*" ; "/"] in
    make_lexer jetons (Stream.of_string chaine) 
    
let calcul op a b = match op with
| "+" -> Some (a+b)
| "-" -> Some (a-b)
| "*" -> Some (a*b)
| "/" -> if b = 0 then None else Some (a/b) 
    
let rec parse pile stream = match stream with parser
| [< '(Int n) ; r >] -> parse ((Some n) :: pile) r
| [< '(Kwd op) ; r >] -> let x1::x2::xs = pile in
                            parse ((x1 >>= fun y -> x2 >>= fun z -> calcul op y z)::xs) r
| [< >] -> pile 

let evaluation chaine =
    let resultat = parse [] (lexer chaine) in
    List.hd resultat

Un exemple (n’oubliez pas de charger dynlink.cma et camlp4o.cma si vous voulez tester) :

# evaluation "2 3 4 * +" ;;
- : int option = Some 14

Le code initial, qui se contente de la gestion des erreurs par le système d’exceptions d’OCaml, est sensiblement le même, à la différence de la fonction calcul :

let calcul op a b = match op with
| "+" -> a+b
| "-" -> a-b
| "*" -> a*b
| "/" -> a/b 

et de la ligne 21, qui est plus simplement : parse (calcul op x1 x2)::xs r (et la ligne 19 ne contient évidemment pas le constructeur Some).

Cette solution est-elle satisfaisante / pertinente ? En particulier, peut-on dire que le concept de monades est bien appliqué ? Finalement, en OCaml, monades et type option sont donc systématiquement liés ?

Le code est correct, mais dans l’esprit, il me semblerait plus pertinent de manipuler une pile de type int list plutôt que int option list. En effet, dès qu’on a un None sur la pile, ça veut dire que 1. quelque chose s’est mal passé et 2. toute opération utilisant le résultat va mal se passer aussi. Donc autant court-circuiter tout le reste des calculs et remonter une erreur. Ce que le type option, manipulé comme une monade, permet justement de faire facilement.

Pour m’entraîner à ce concept de monades qui, si je comprends bien, permet de séparer proprement la propagation d’un résultat et la gestion des erreurs

Finalement, en OCaml, monades et type option sont donc systématiquement liés ?

Pas nécessairement. Les monades sont une façon de programmer qui permet de rendre implicite du code auxiliaire dans une séquence d’opérations. Ce que j’appelle « code auxiliaire » c’est des actions mécaniques qu’on a envie d’écrire une bonne fois pour toutes et de ne plus avoir à gérer. Ça peut être des choses aussi variées que :

• la gestion d’erreurs (type option, type ('res, 'err) maybe_error = Ok of 'res | Error of 'err) ;
• la tenue à jour d’un état qui peut évoluer au cours des opérations, sans pour autant devoir utiliser une variable mutable (monade d’état). Exemples : la pile d’une machine à pile (eh oui !), un journal qui enregistre chaque opération réalisée. Ça peut aussi être un état en lecture seule, comme l’environnement l de ton premier message.
• Appliquer une suite d’opérations qui peuvent chacune renvoyer plusieurs valeurs (si on a du non-déterminisme, ou des calculs parallèles) en laissant une monade gérer les multiples états intermédiaires ;
• en programmation concurrente, si on a un type 'a thread qui représente un thread qui, quand il aura terminé, renverra un 'a ; on peut demander à faire l’opération f de type 'a -> 'b sur le futur résultat en question. On obtient alors un 'b thread. Autrement dit, thread est une monade.
• Je suis à peu près sûr que j’en oublie.

Concrètement, une monade se résume à un type paramétré 'a m (comme par exemple 'a option) et à l’existence de deux fonctions :

• une fonction de type 'a m -> ('a -> 'b m) -> 'b m, généralement appelée >>= ou bind ;
• une fonction de type 'a -> 'a m, généralement appelée return.

Ces fonctions doivent être reliées par quelques propriétés simples pour qu’on considère qu’on a vraiment une monade mais je laisse ça de côté, on peut le trouver partout et c’est pas très intéressant.

J’essaierai de donner un exemple d’une monade de lecture un peu plus tard.

Donc une monade de lecture, c’est une technique de code qui repose sur le type suivant :

type 'a m = env -> 'a

où env est le type (string * int) list (par exemple). Un 'a m est simplement une fonction qui prend un environnement et renvoie un 'a. Maintenant, supposons que c’est effectivement une monade et qu’on a un return et un bind pour ce type.

J’ai repris ton code d’évaluation d’expressions et l’ai modifié pour qu’il utilise une monade de lecture, au lieu de passer l en argument d’eval. Au passage, j’ai enlevé le type option, parce qu’avoir deux monades dans le même code n’est pas très pratique, en particulier en OCaml. Maintenant, si une variable n’est pas trouvée dans l’environnement, eval va lever une exception Not_found.

type env = (string * int) list

let rec find key = function
| [] -> raise Not_found
| (key', v) :: r -> if key = key' then v else find key r

module Reader : sig
  type 'a m
  val (>>=) : 'a m -> ('a -> 'b m) -> 'b m
  val return : 'a -> 'a m
end = struct
  type 'a m = env -> 'a

  let return x = (* ... *)

  let (>>=) x f = (* ... *)
end

open Reader

type expr =
| Const of int
| Add of expr * expr
| Neg of expr
| Var of string

let rec eval (e : expr) : int m = match e with
| Const n -> return n
| Var v -> find v
| Neg e1 ->
    eval e1 >>= fun x -> return (-x)
| Add (e1, e2) ->
    eval e1 >>= fun x ->
    eval e2 >>= fun y ->
    return (x + y)

De façon assez agréable, il n’y a presque rien à modifier par rapport à ton programme où la monade était option. À présent, le passage de l’environnement dans eval est implicite et laissé aux fonctions monadiques. Le nouveau type de eval est expr -> int m, c’est-à-dire expr -> env -> int. Presque le même qu’avant, en somme.

Tu remarques qu’on peut voir find comme étant de type string -> int m.

J’ai pas mis l’implémentation de return et (>>=) parce que ça peut être un exercice rigolo

Bon, comme annoncé, pas de changements révolutionnaires dans cet exemple. Mais parfois, en remarquant que les opérations que tu fais relèvent des monades, tu peux sérieusement clarifier et raccourcir ton code.