Discussion :

[gomisse]

La programmation fonctionnelle avancé,

Le code ci-dessous Il contient la définition des types de base ainsi que le lexer et le parser pour transformer les chaîınes de caractèeres en expressions.

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
type variable = string and typvar = string
type valeur =
| Entier of int
| Reel of float
| Booleen of bool
type expr =
| Val of valeur
| Somme of expr * expr  (* a+b *)
| Mult of expr * expr  (* a*b *)
| Non of expr
| Ou of expr * expr
| Et of expr * expr
| Egal of expr * expr (* e1=e2 ? *)
| PlusGrand of expr * expr (* e1 > e2 ? *)
| Ifte of expr * expr * expr (* Si e1 Alors e2 Sinon e3 *)
 | Var of variable  (* décommenter pour q2 *)
| Def of variable * expr * expr (* Soit x = e1 dans e2 *) 
          (* décommenter pour q4 *)
| Fonction of variable * expr     (* x -> e *)    (* décommenter pour q6 *)
 
type type_ =
| TEntier
| TReel
| TBooleen
(* | TVar of typvar  (* alpha, beta *)
   | TFonction of type_ * type_ *)
 
 
(***************    Parser (+Genlex)     ************)
 
open Genlex
let lexer = make_lexer ["+";"*";"(";")";"soit";"Soit";"dans";"=";
		       "non";"ou";"et";">";"vrai";"faux";"->";
                       "Si";"si";"Alors";"alors";"Sinon";"sinon"]
 
let rec stream_to_list s =
  match Stream.peek s with
  | None -> []
  | Some a -> Stream.junk s;a::(stream_to_list s)
 
exception Syntax_error of string * token list
 
(* TODO :
   utiliser camlp4 pour pouvoir utiliser directement "parser" les Stream !
*)
 
let parse liste = (* liste : token list *)
  let rec parse_expr =
    function
    | (Int n)::r -> (Val (Entier n)),r
    | (Float x)::r -> (Val (Reel x)),r
    | (Kwd "vrai")::r -> (Val (Booleen true)),r
    | (Kwd "faux")::r -> (Val (Booleen false)),r
    | (Kwd "non")::r ->
      let e,fin = parse_expr r in (Non e),fin
    | (Kwd "(")::r -> parse_closing r
      (* parenthèse ouvrante : déléguer. *)
    | (Kwd "Si")::r | (Kwd "si")::r -> parse_if r
  | (Ident s)::r -> (Var s),r    (* décommenter pour q2 *)
    | (Kwd "Soit")::r | (Kwd "soit")::r -> parse_let r 
                  (* décommenter pour q4 *)
      (* définition : déléguer. *)
    | e -> raise (Syntax_error ("expr",e))
  and parse_closing expr =
    (* expr dans des parenthèses. Rq : on peut en fermer trop.*)
    let (e,l) = parse_full expr in
      match l with
      | (Kwd ")")::r -> (e,r)
      | _ -> raise (Syntax_error ("closing",l))
 and parse_let =          (* décommenter pour q4 *)
    function
    | (Ident s)::(Kwd "=")::r ->
      begin
        let e1,ein = parse_expr r in
        match ein with
	| (Kwd "dans")::rr ->
	  let e2,fin = parse_expr rr in Def(s,e1,e2),fin
        | _ -> raise (Syntax_error ("dans",ein))
      end
    | e -> raise (Syntax_error ("let",e)) 
  and parse_if expr =
    let (e,l) = parse_expr expr in
    match l with
    | (Kwd "Alors")::r | (Kwd "alors")::r -> parse_then e r
    | _ -> raise (Syntax_error ("if",expr))
  and parse_then test expr =
    let etrue,l = parse_expr expr in
    match l with
    | (Kwd "Sinon")::r | (Kwd "sinon")::r ->
      let efalse,fin = parse_expr r in Ifte (test,etrue,efalse),fin
    | _ -> raise (Syntax_error ("then",l))
  and parse_full expr =  (* expr complète *)
    let (e1,l) = parse_expr expr in
    match l with
    | [] -> e1,l
    | (Kwd ")")::_ -> e1,l (* parenthèse fermante remontée à parse_closing. *)
    | (Kwd "+")::r -> let e2,rr = parse_full r in (Somme (e1,e2)),rr
    | (Kwd "*")::r -> let e2,rr = parse_full r in (Mult (e1,e2)),rr
    | (Kwd "ou")::r -> let e2,rr = parse_full r in (Ou (e1,e2)),rr
    | (Kwd "et")::r -> let e2,rr = parse_full r in (Et (e1,e2)),rr
    | (Kwd "=")::r -> let e2,rr = parse_full r in (Egal (e1,e2)),rr
    | (Kwd ">")::r -> let e2,rr = parse_full r in (PlusGrand (e1,e2)),rr
   | (Kwd "->")::r -> let e2,rr = parse_full r in
                      begin                        (* décommenter pour q6 *)
                        match e1 with
                        | Var s -> (Fonction (s,e2)),rr
                        | _ -> raise (Syntax_error ("fun",r))
                      end 
    | _ -> raise (Syntax_error ("full",l))
  in fst (parse_full liste)
 
let string_to_expr s = parse (stream_to_list (lexer (Stream.of_string s)))

1/ Ecrire les fonctions type_of_value et type_of_expr qui typent une valeur et une expression.

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
type type_ =
| TEntier
| TReel
| TBooleen
;;
exception Type_error ;;
(* | TVar of typvar  (* alpha, beta *)
   | TFonction of type_ * type_ *)
let  type_of_value= function 
 | Entier a ->TEntier
 | Reel   b ->TReel
 | Booleen c-> if(c=true ||false) then TBooleen else raise(Type_error) 
 |v -> raise  Type_error 
 ;;
Entier 2;;
type_of_value (Entier 2);;
 
 
 
let rec type_of_expr =  function 
  | Val v -> ( type_of_value  v)
  | Somme  (v1,v2) -> 
    begin
      match (type_of_expr v1),(type_of_expr v2) with
        | TEntier,TEntier -> TEntier
        | TEntier,TBooleen -> raise  Type_error
        | TEntier,TReel   ->  raise  Type_error
        | TBooleen,TEntier -> raise  Type_error
        | TEntier,TBooleen -> raise  Type_error
        | TReel,TBooleen  -> raise  Type_error
        | TReel,TEntier   ->  raise  Type_error
        | TBooleen,TBooleen -> TBooleen
        | TReel,TReel -> TReel
    end  
  | Mult (v1,v2)  -> 
    begin
      match (type_of_expr v1),(type_of_expr v2) with
	| TEntier,TEntier -> TEntier
	| TEntier,TBooleen -> raise  Type_error
	| TEntier,TReel   ->  raise  Type_error
	| TBooleen,TEntier -> raise Type_error
	| TEntier,TBooleen -> raise Type_error
	| TReel,TBooleen  -> raise Type_error
	| TReel,TEntier   ->  raise  Type_error
	| TBooleen,TBooleen -> TBooleen
	| TReel,TReel -> TReel
    end
 
  | Non  b -> 
    if (type_of_expr b) != TBooleen
    then raise Type_error
    else TBooleen  
  | Ou (b1,b2) ->
    if((type_of_expr b1)!=TBooleen  && (type_of_expr b2)!= TBooleen)
    then raise  Type_error
    else TBooleen  
  | Et (b1,b2) ->
     if((type_of_expr b1)!= TBooleen && (type_of_expr b2)!= TBooleen)
    then raise  Type_error 
 
    else TBooleen
  | Egal (v1,v2) ->
    if((type_of_expr v1)= (type_of_expr v2)) 
    then TBooleen
    else  raise  Type_error                    
  | PlusGrand  (v1,v2) ->  
    if((type_of_expr v1)= (type_of_expr v2)) 
    then TBooleen
    else raise  Type_error        
  |Ifte (v1,v2,v3) -> 
    if(type_of_expr v1) = TBooleen
    then 
      if (type_of_expr v2) = (type_of_expr v3)
      then (type_of_expr v3)
      else raise Type_error 
    else  raise Type_error
;;

Question sur laquelle je souhaite de l'aide : Le typage a maintenant besoin de prendre en param`etre un environnement de type. Modifier les
fonctions précédentes (type_of_value, type_of_expr )pour gérer les variables.

Code :

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

1
2
3
4
5
6
7
8
9
 type type_ =
| TEntier
| TReel
| TBooleen
| TVar of typvar  (* alpha, beta *)
| TFonction of type_ * type_ 
 
let   type_of_value type environnement  (* qui retourne un type dans l'environnement *)
let rec type_of_expr   expression environnement (* retourne une pression dan l'environnement *)

[SpiceGuid]

Je vois déjà quelques erreurs dans type_of_value et type_of_expr.

Liste non exhaustive :

Code :

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

1
2
3
4
5
6
7
8
# type_of_value (Booleen false);;
Exception: Type_error.
 
# type_of_expr (Ou (Val (Booleen true),Val(Entier 1)));;
- : type_ = TBooleen
 
# type_of_expr (Somme (Val (Booleen true),Val (Booleen true)));;
- : type_ = TBooleen

Corrige tous les warnings, ils cachent potentiellement d'autres erreurs.
Pour te faciliter la tâche, au lieu d'écrire :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
    begin
      match (type_of_expr v1),(type_of_expr v2) with
        | TEntier,TEntier -> TEntier
        | TEntier,TBooleen -> raise  Type_error
        | TEntier,TReel   ->  raise  Type_error
        | TBooleen,TEntier -> raise  Type_error
        | TEntier,TBooleen -> raise  Type_error
        | TReel,TBooleen  -> raise  Type_error
        | TReel,TEntier   ->  raise  Type_error
        | TReel,TReel -> TReel
    end

Tu peux écrire :

Code :

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

1
2
3
4
        ( match type_of_expr v1,type_of_expr v2 with
        | TEntier,TEntier -> TEntier
        | TReel,TReel -> TReel
        | _ -> raise Type_error )

Quant à ta question principale.
Il va falloir ajouter les cas Var et Fonction dans type_of_expr.
Ton environnement de type est probablement une liste associative qui à chaque variable de type TVar associe un type_. À l'aide de cet environnement on te demande de substituer tous les TVar dans un type_ complet.

val type_of_type : type_ -> environnement -> type_ = <fun>

[gomisse]

Merci pour votre aide. c 'est résolu .