Discussion :

[Zefjo_EttaRomm]

Bonjour,

Je suis débutant en Caml / Ocaml et je suis actuellement le cours suivant : https://www.lri.fr/~paulin/LGL/docs/polycaml-etuds.pdf

Je suis à l'exercice 50, je n'ai pas l'impression d'avoir eu de problème mais je souhaite avoir quelques avis dont la façon dont j'ai codé. J'essaie de m'approprier la vision du fonctionnel, si vous avez du temps pour me lire (c'est un peu long), et des conseils à me donner, c'est avec plaisir.

Sans attendre voici les questions et les réponses :

1. Décrire un type boolexpr pour représenter des expressions booléennes construites sur les constantes True et False, les opérateurs And, Or et Not, et les variables booléennes.

Code :

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

1
2
3
4
5
6
7
8
type op_unaire = Not;;
type op_binaire = And | Or;;
 
type boolexpr =
| Boolean of bool
| Var of string
| Op_unaire of op_unaire * boolexpr
| Op_binaire of op_binaire * boolexpr * boolexpr;;

2. Écrire une fonction qui évalue une expression dans un environnement de valeurs booléennes, c’est-
à-dire une liste de couples (nom de variable, booléen). Utiliser la fonction List.assoc.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
let rec evalue_bool env expr =
match expr with
| Boolean(bool1) -> bool1
| Var(chaine) -> 
    (try (List.assoc chaine env)
     with Not_found -> raise (Variable_non_definie chaine))
| Op_unaire(op1, expr_bool) -> 
    (match op1 with
    | Not -> not (evalue_bool env expr_bool))
| Op_binaire(op1, expr_bool1, expr_bool2) -> 
    (match op1 with
    | Or -> (evalue_bool env expr_bool1) || (evalue_bool env expr_bool2)
    | And -> (evalue_bool env expr_bool1) && (evalue_bool env expr_bool2));;

3.
Donner une fonction qui prend un boolexpr et qui retourne la liste de toutes ses variables. Une
variable qui se trouve plusieurs fois dans l’expression doit apparaître une seule fois dans la liste.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
let rec retourne_liste_variable_int = function
 | Boolean(bool1) -> []
 | Var(chaine) -> [chaine]
 | Op_unaire(_, expr_bool) -> (retourne_liste_variable expr_bool)
 | Op_binaire(_, expr_bool1, expr_bool2) -> (retourne_liste_variable expr_bool1)@(retourne_liste_variable expr_bool2);;
 
let rec supp_doublon l1 l2 =
match l1 with
| [] -> l2
| h::t -> if (List.mem h l2)
          then (supp_doublon t l2)
          else (supp_doublon t (h::l2));;
 
let retourne_liste_variable expr_bool = supp_doublon (retourne_liste_variable_int expr_bool) [];;

La plupart de mes problèmes ont été sur cette question, d'abord, la complexité est bien sûr pas optimiser (table hachage / arbre binaire de recherche serait mieux que l2) mais n'y a-t-il pas même possibilité de faire cela de manière plus élégante, sans même passé par l2 (sans avoir une complexité trop mauvaise).

4. Écrire une fonction qui retourne, pour une liste de variables, la liste de tous les environnements
avec valeurs booléennes pour ces variables.

Code :

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

1
2
3
4
5
6
7
8
9
10
let rec liste_env l =
 let ajoute_liste_var var l = 
		(match l with
		| [] -> [[(var, true)]; [(var, false)]]
		| t::[] -> [(var, true)::t ; (var, false)::t]
		| h::t -> ((var, true)::h)::(((var, false)::h)::(ajoute_liste_var var t))) 
in match l with
| [] -> []
| t::[] -> ajoute_liste_var t []
| h::t -> ajoute_liste_var h (liste_env t);;

5. Écrire une fonction pour_tous de type ’a list -> (’a -> bool) -> bool tel que
(pour_tous l f) retourne true si et seulement si f x retourne true pour tous les éléments
x de la liste l.

Code :

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

1
2
3
4
let rec pour_tous l f =
match l with
| [] -> true
| h::t -> if (f h) then (pour_tous t f) else false;;

6. Écrire une fonction qui prend une expression du type boolexpr et qui retourne true si cette
expression est une tautologie, c’est-à-dire si l’évaluation de cette expression retourne true pour
tous les environnements.

Code :

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

1
2
3
let est_totologie expr =
 let fonction_evaluation env = evalue_bool env expr in
 pour_tous (liste_env (retourne_liste_variable expr)) fonction_evaluation;;

7. (J'ai pas trouvé comment insérer du LaTeX, désolé).
En utilisant le fait que
not(and(x,y)) = or(not(x), not(y))
not(or(x,y)) = and(not(x), not(y))
not(not(x)) = x
écrire une fonction qui prend une expression du type boolexpr et retourne une expression du type boolexpr équivalente où il n’y a plus de Not sauf si appliqué directement à une variable.
Par exemple, la fonction appliqué à l’expression not(and(x, or(y, z))
doit retourner or(not(x), and(not(y), not(z))).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
let rec transf_boolexpr = function
| Boolean(bool1) -> Boolean(bool1)
| Var(x) -> Var(x)
| Op_unaire(op1, expr1) -> 
    (match op1 with
    | Not -> (match expr1 with
         | Op_unaire(Not, expr2) -> expr2
         | Op_binaire(And, expr2, expr3) -> Op_binaire(Or, transf_boolexpr (Op_unaire(Not, expr2)), transf_boolexpr (Op_unaire(Not, expr3)))
         | Op_binaire(Or, expr2, expr3) -> Op_binaire(And, transf_boolexpr (Op_unaire(Not, expr2)), transf_boolexpr (Op_unaire(Not, expr3)))
         | _ -> Op_unaire(Not, expr1))
    | _ -> Op_unaire(op1, transf_boolexpr expr1))
| Op_binaire(op1, expr1, expr2) -> Op_binaire(op1, transf_boolexpr expr1, transf_boolexpr expr2);;

Là encore, je trouve mon code assez long, y avait-il possibilité de faire beaucoup plus simple (à part supposé que le seul opérateur unaire est le not ici) ?

Merci d'avance.

[TchoubiTchoub]

Bonjour,

Je suis débutant en Caml / Ocaml et je suis actuellement le cours suivant : https://www.lri.fr/~paulin/LGL/docs/polycaml-etuds.pdf

Je suis à l'exercice 50, je n'ai pas l'impression d'avoir eu de problème mais je souhaite avoir quelques avis dont la façon dont j'ai codé.

Parfait, c'est parti !

J'essaie de m'approprier la vision du fonctionnel, si vous avez du temps pour me lire (c'est un peu long), et des conseils à me donner, c'est avec plaisir.

Sans attendre voici les questions et les réponses :

1. Décrire un type boolexpr pour représenter des expressions booléennes construites sur les constantes True et False, les opérateurs And, Or et Not, et les variables booléennes.

Code :

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

1
2
3
4
5
6
7
8
type op_unaire = Not;;
type op_binaire = And | Or;;
 
type boolexpr =
| Boolean of bool
| Var of string
| Op_unaire of op_unaire * boolexpr
| Op_binaire of op_binaire * boolexpr * boolexpr;;

Bon, ici, ce que vous avez fait est tout à fait correct (si ce n'est que vous n'êtes pas censé pouvoir utiliser le type bool d'OCaml ) mais peut devenir rapidement illisible avec des matchs imbriqués dans des matchs. Autant écrire directement

Code :

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

1
2
3
4
5
6
7
8
type boolexpr =
  | True
  | False
  | Var of string
  | Not of boolexpr
  | And of boolexpr * boolexpr
  | Or of boolexpr * boolexpr;;
;;

2. Écrire une fonction qui évalue une expression dans un environnement de valeurs booléennes, c’est-
à-dire une liste de couples (nom de variable, booléen). Utiliser la fonction List.assoc.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
let rec evalue_bool env expr =
match expr with
| Boolean(bool1) -> bool1
| Var(chaine) -> 
    (try (List.assoc chaine env)
     with Not_found -> raise (Variable_non_definie chaine))
| Op_unaire(op1, expr_bool) -> 
    (match op1 with
    | Not -> not (evalue_bool env expr_bool))
| Op_binaire(op1, expr_bool1, expr_bool2) -> 
    (match op1 with
    | Or -> (evalue_bool env expr_bool1) || (evalue_bool env expr_bool2)
    | And -> (evalue_bool env expr_bool1) && (evalue_bool env expr_bool2));;

Avec mon type cela devient donc :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
let rec evalue_bool env = function
  | True -> true
  | False -> false
  | Var v -> 
      (try List.assoc v env
       with Not_found -> raise (Variable_non_definie v))
  | Not e -> not (evalue_bool env e)
  | Or (e1, e2) -> evalue_bool env e1 || evalue_bool env e2
  | And (e1, e2) -> evalue_bool env e1 && evalue_bool env e2;;

Pas grand chose à dire si ce n'est que :

• Lorsque vous n'avez qu'un constructeur les parenthèses sont optionnelles (Not e, par exemple),
• Du fait de la priorité des opérateurs infixes (situés entre deux expressions) vous pouvez supprimer les parenthèses autour de vos expressions mais ça c'est surtout une question de goût,
• Si vos variables ont une très faible portée, rien ne sert de leur donner un nom trop long,
• La définition de votre propre exception est une très bonne chose.

3.
Donner une fonction qui prend un boolexpr et qui retourne la liste de toutes ses variables. Une
variable qui se trouve plusieurs fois dans l’expression doit apparaître une seule fois dans la liste.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
let rec retourne_liste_variable_int = function
 | Boolean(bool1) -> []
 | Var(chaine) -> [chaine]
 | Op_unaire(_, expr_bool) -> (retourne_liste_variable expr_bool)
 | Op_binaire(_, expr_bool1, expr_bool2) -> (retourne_liste_variable expr_bool1)@(retourne_liste_variable expr_bool2);;
 
let rec supp_doublon l1 l2 =
match l1 with
| [] -> l2
| h::t -> if (List.mem h l2)
          then (supp_doublon t l2)
          else (supp_doublon t (h::l2));;
 
let retourne_liste_variable expr_bool = supp_doublon (retourne_liste_variable_int expr_bool) [];;

Idem, il faut que je réécrive pour que mon code corresponde à mon type (et comme ça on verra un exemple de multiple patterns :

Code :

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

1
2
3
4
5
6
7
8
9
 let rec retourne_liste_variable = function
  | True | False -> []
  | Var v -> [v]
  | Not e -> retourne_liste_variable e
  | And (e1, e2) | Or (e1, e2) -> 
     let lv1 = retourne_liste_variable e1 in
     let lv2 = retourne_liste_variable e2 in
     List.fold_left (fun acc e -> 
         if List.mem e acc then acc else e :: acc) lv2 lv1;;

Par rapport à votre code, quelques changements :

• Vous avez sûrement une erreur car vous appelez récursivement retourne_list_variable alors que votre fonction s'appelle retourne_liste_variable_int,
• Il n'est possible d'avoir des doublon que lorsqu'on a des opérateurs binaires, autant faire le tri immédiatement.

La plupart de mes problèmes ont été sur cette question, d'abord, la complexité est bien sûr pas optimiser (table hachage / arbre binaire de recherche serait mieux que l2) mais n'y a-t-il pas même possibilité de faire cela de manière plus élégante, sans même passé par l2 (sans avoir une complexité trop mauvaise).

4. Écrire une fonction qui retourne, pour une liste de variables, la liste de tous les environnements
avec valeurs booléennes pour ces variables.

Code :

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

1
2
3
4
5
6
7
8
9
10
let rec liste_env l =
 let ajoute_liste_var var l = 
        (match l with
        | [] -> [[(var, true)]; [(var, false)]]
        | t::[] -> [(var, true)::t ; (var, false)::t]
        | h::t -> ((var, true)::h)::(((var, false)::h)::(ajoute_liste_var var t))) 
in match l with
| [] -> []
| t::[] -> ajoute_liste_var t []
| h::t -> ajoute_liste_var h (liste_env t);;

C'est une très belle question d'algorithmique ! Si on y regarde de plus prêt cette question revient à créer l'ensemble des mots binaires de taille fixée (c'est le problème des sous-parties d'un ensemble, aussi).

Code :

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

1
2
3
4
5
6
7
 
let liste_env l =
  List.fold_left (fun acc v ->
      let tlv = List.map (fun lv -> (v, true) :: lv) acc in
      let flv = List.map (fun lv -> (v, false) :: lv) acc in
      List.rev_append tlv flv
    ) [[]] l;;

Et c'est une très belle utilisation des itérateurs.
ATTENTION ! Il faut bien mettre comme accumulateur la liste contenant une liste vide qui est différente de la liste vide sinon on renverra toujours une liste vide.
De plus, j'utilise rev_append qui est récursive terminale plutôt que @ qui ne l'est pas.
L'idée est la même que la vôtre mais plutôt que de réfléchir en terme de concaténations j'ai réfléchi en terme d'itérations (ce que je veux c'est que pour chaque nouvelle variable et environnement je crée deux environnements dont l'un contient ma variable liée à vrai et l'autre à faux).
Votre solution fonctionne mais si vous la relisez dans deux mois vous vous demanderez sûrement pourquoi et peut-être même ce qu'elle fait.

5. Écrire une fonction pour_tous de type ’a list -> (’a -> bool) -> bool tel que
(pour_tous l f) retourne true si et seulement si f x retourne true pour tous les éléments
x de la liste l.

Code :

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

1
2
3
4
let rec pour_tous l f =
match l with
| [] -> true
| h::t -> if (f h) then (pour_tous t f) else false;;

Code :

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

1
2
3
4
5
 
let rec pour_tous l f =
  match l with
    | [] -> true
    | h::t -> f h && pour_tous t f;;

OCaml a des opérateurs booléens paresseux donc && s'arrête si son membre gauche s'évalue à faux et || s'arrête si celui-ci s'évalue à true. Rien de plus à dire.

6. Écrire une fonction qui prend une expression du type boolexpr et qui retourne true si cette
expression est une tautologie, c’est-à-dire si l’évaluation de cette expression retourne true pour
tous les environnements.

Code :

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

1
2
3
let est_totologie expr =
 let fonction_evaluation env = evalue_bool env expr in
 pour_tous (liste_env (retourne_liste_variable expr)) fonction_evaluation;;

Franchement, rien à dire !

7. (J'ai pas trouvé comment insérer du LaTeX, désolé).
En utilisant le fait que
not(and(x,y)) = or(not(x), not(y))
not(or(x,y)) = and(not(x), not(y))
not(not(x)) = x
écrire une fonction qui prend une expression du type boolexpr et retourne une expression du type boolexpr équivalente où il n’y a plus de Not sauf si appliqué directement à une variable.
Par exemple, la fonction appliqué à l’expression not(and(x, or(y, z))
doit retourner or(not(x), and(not(y), not(z))).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
let rec transf_boolexpr = function
| Boolean(bool1) -> Boolean(bool1)
| Var(x) -> Var(x)
| Op_unaire(op1, expr1) -> 
    (match op1 with
    | Not -> (match expr1 with
         | Op_unaire(Not, expr2) -> expr2
         | Op_binaire(And, expr2, expr3) -> Op_binaire(Or, transf_boolexpr (Op_unaire(Not, expr2)), transf_boolexpr (Op_unaire(Not, expr3)))
         | Op_binaire(Or, expr2, expr3) -> Op_binaire(And, transf_boolexpr (Op_unaire(Not, expr2)), transf_boolexpr (Op_unaire(Not, expr3)))
         | _ -> Op_unaire(Not, expr1))
    | _ -> Op_unaire(op1, transf_boolexpr expr1))
| Op_binaire(op1, expr1, expr2) -> Op_binaire(op1, transf_boolexpr expr1, transf_boolexpr expr2);;

Là encore, je trouve mon code assez long, y avait-il possibilité de faire beaucoup plus simple (à part supposé que le seul opérateur unaire est le not ici) ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
let rec transf_boolexpr e = match e with
| True | False | Var _ -> e
| Not e -> 
    begin
      match e with
        | True -> False
        | False -> True
        | Var _ -> Not e
        | Not e' -> transf_boolexpr e'
        | And (e1, e2) -> 
            let e1 = transf_boolexpr (Not e1) in
            let e2 = transf_boolexpr (Not e2) in
            Or (e1, e2)
        | Or (e1, e2) -> 
            let e1 = transf_boolexpr (Not e1) in
            let e2 = transf_boolexpr (Not e2) in
            And (e1, e2)
    end
| And (e1, e2) -> And (transf_boolexpr e1, transf_boolexpr e2)
| Or (e1, e2) -> Or (transf_boolexpr e1, transf_boolexpr e2);;

Ici on voit que votre solution consistant à avoir un constructeur Op_binaire permet de répéter moins de code donc c'est à vous de voir ce que vous préférez.
De plus, c'était peut-être un piège mais transf_boolexpr (Not (Not e)) ne donne pas e mais transf_boolexpr e
Pour la curiosité, au cas où, c'est ce qu'on appelle une NNF (forme normale de négation)

Bon courage pour la suite, vous avez l'air d'être assez à l'aise avec la fonctionnelle.

P.S. : Si vous voulez vous amuser vous pouvez recommencer mais avec le type boolexpr suivant :

Code :

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

1
2
3
4
5
6
7
8
 
type boolexpr =
  | True
  | False
  | Var of string
  | Not of boolexpr
  | And of boolexpr list
  | Or of boolexpr list;;

[Zefjo_EttaRomm]

Merci pour cette réponse, c'est exactement ce que je voulais !

Notamment pour les questions 3 et 4, j'ai du mal à utiliser les fold_left (je n'y pense pas particulièrement) et c'est un super exemple. Je n'ai vu que rapidement les accumulateurs (car pas présenté dans le pdf que j'ai pris) mais je les avais vu avec le tutoriel ici-même (l'approche qualité avec Ocaml) et la solution est vraiment courte en les utilisant, là aussi il faut que je prenne le réflexe de les utiliser quand ils peuvent être intéressant.

Pour la question 7 : l.4 et l.18 vous utilisez des mots-clefs "begin" and "end" qui correspondent plutôt à des parenthèses dans mon code (l.5 et l.11), y a-t-il une différence entre les deux, si oui laquelle ?

J'essaierai avec des List de boolexpr à l'occasion, je continue mon chemin car j'ai encore pas mal de bases à assimiler !

[TchoubiTchoub]

Aucune différence entre begin end et (), à ma connaissance. Encore une fois, c'est une question de goût

Il vous reste beaucoup à assimiler ? Vous allez avoir un cours de OCaml l'année prochaine ?

[Zefjo_EttaRomm]

Sur le pdf que je suis, il me reste les parties suivantes :
- Entrées-sorties
- Compilation et programmation modulaire
- Aspect impératifs du langage
- Analyse syntaxique avec CamlLex et CamlYacc

Et je pense refaire quelques exercices pour m'exercer (rien de mieux que la pratique).

J'ai un cours sur les langages de programmation et compilation l'année prochaine effectivement où je vais utiliser le Caml. Une mise à niveau va avoir lieu en début d'année, mais je pense que ça va être assez rapide donc je préfère prendre les devants. Le Caml m'intéressait depuis un moment en plus.

Mais il y a d'autres choses que j'aimerai voir vite fait : Git et apprendre à utiliser quelque chose pour le code (Emacs / Vim) car je suis toujours sur gedit en général.

Merci de votre aide en tout cas, je mets le sujet en "résolu".

[TchoubiTchoub]

Sur le pdf que je suis, il me reste les parties suivantes :
- Entrées-sorties
- Compilation et programmation modulaire
- Aspect impératifs du langage
- Analyse syntaxique avec CamlLex et CamlYacc

Et je pense refaire quelques exercices pour m'exercer (rien de mieux que la pratique).

J'ai un cours sur les langages de programmation et compilation l'année prochaine effectivement où je vais utiliser le Caml. Une mise à niveau va avoir lieu en début d'année, mais je pense que ça va être assez rapide donc je préfère prendre les devants. Le Caml m'intéressait depuis un moment en plus.

Mais il y a d'autres choses que j'aimerai voir vite fait : Git et apprendre à utiliser quelque chose pour le code (Emacs / Vim) car je suis toujours sur gedit en général.

Merci de votre aide en tout cas, je mets le sujet en "résolu".

A moins que je me trompe, votre cours a lieu aujourd'hui, non ? Ca c'est si vous êtes à Paris XI

Dans ce cas je vous conseille emacs

Sinon il y a une autre fac qui fait faire de la compil avec OCaml.