Langage de Programmation 2 (LP2 ) - RICM3 Cours 7 Inf 351rence de type, Makefile, R 351f

Pascal Lafourcade

Description

Langage de Programmation 2 (LP2)Langage de Programmation 2 (LP2)RICM3Cours 7Inférence de type, Makefile, Référence, mutablePascal LafourcadePolytech2009 - 20101 / 56Langage de Programmation 2 (LP2)PlanTypage suiteTypage des exceptionsBilanUnificationTerms and MessagesUnificationVérification de types polymorphesSytème FSystème de Hindley-MilnerInférence de TypeConclusion2 / 56Langage de Programmation 2 (LP2)Typage suiteTypage du filtrage (match)type t = C of T ×...T |... | C of T ×...T1 1,1 1,n p p,1 p,n1 pPosons  match E with . ..M = |C (x ,...x ) → Ei 1 n ii . ..où chaque expression E dépend de x ...x .i 1 niE :t ∀i,1≤i≤p, Γ;x 7!T ...x 7!T ⊢ E :T1 p,1 n p,n ii iΓ ⊢ M :T4 / 56Langage de Programmation 2 (LP2)Typage suiteTypage du matchExemple : fact II# let rec fact n = match n with| 0 -> 1| n -> n* (fact (n-1));;val fact : int -> int = 5 / 56Langage de Programmation 2 (LP2)Typage suiteTypage des exceptionsExceptionstry E with| ListeVide→ E1| Alarme (n, b)→ E (n,b) = T (une expression)2| Not_found→ E3| Division_by_zero→ E4E, E , E (n,b), E , E , ... doivent avoir le même type,1 2 3 4qui est le type de l’expression entière T.E :t E :t E (n,b) :t E :t E :t1 2 3 4T :t6 / 566Langage de Programmation 2 (LP2)BilanRappel des règles de typageΓ ⊢ 0 : intΓ;x7!t ⊢ x :tΓ ⊢ x :t x =yΓ;y7!u ⊢ x :tΓ ⊢ B : bool Γ ⊢ E :t Γ ⊢ E :t1 2Γ ⊢ (if B then E else E ) :t1 2Γ ⊢ A :t Γ ⊢ B :uΓ ⊢ (A,B) :t×uΓ ⊢ E :T ... Γ ⊢ E ...

Informations

• Publié par: Thyam
• Nombre de lectures: 56
• Langue: English

Extrait

LangagedeProgrammation2L(2P)

Langage de Programmation 2 RICM3 Cours 7 Inférence de type, Makefile, Référence,

Pascal Lafourcade

Polytech

2009 - 2010

(LP2)

mutable

1 / 56

LnaagegderPgo

Plan

rammatino2(LP2)

Typage suite Typage des exceptions

Bilan

Unification Terms and Messages Unification

Vérification de types polymorphes Sytème F Système de Hindley-Milner

Inférence de Type

Conclusion

2 / 56

Lnag Ty a p g a e g d e e s P ui r t o e rgmamation2L(2P)

Typage du filtrage (match)

typet=C 1 ofT 11 ×  T 1n 1 |  |C p ofT p1 ×  T pn p

Posons

 matchEwith M=   . |C i (x 1    x n i )→E i   . où chaque expressionE i dépend dex 1   x n i .

E:t

∀i1≤i≤pΓ;x 1 7→T p1   x n i 7→T pn i ⊢E i :T Γ⊢M:T

4/56

Lnag yT a p g a e g d e e s P ui r t o e rgmaamtino2L(2P)

Typage du match

Exemple : fact II

# let rec fact n = match n with | 0 -> 1 | n -> n* (fact (n-1)) ; ; val fact : int -> int = <fun>

5

/

56

ngagLarogredePnoitamma yT )2PL(2 itsugepa edagyp e T oitpsn nsio ceEx exesptce 566/

E:tE 1 :tE 2 (nb) :tE 3 :tE 4 :t T:t

(une expression)

tryEwith |ListeVide→E 1 |Alarme(n,b)→E 2 (nb) |Not_found→E 3 |Division_by_zero→E 4 E,E 1 ,E 2 (nb),E 3 ,E 4 ,  doivent avoir lemêmetype, qui est le type de l’expression entièreT.

T

=

Lang Bi a l g a e n deProgrmaamitno2L(2P)

Rappel des règles de typage

Γ⊢0:int

Γ;x7→t⊢x:t Γ⊢x:tx6=y Γ;y7→u⊢x:t Γ⊢B:boolΓ⊢E 1 :tΓ⊢E 2 :t Γ⊢(ifBthenE 1 elseE 2 ) :t Γ⊢A:tΓ⊢B:u Γ⊢(AB) :t×u Γ⊢E 1 :T 1   Γ⊢E n :T n Γ⊢ {c 1 =E 1 ;  c n =E n }:r

Pour touti1≤i≤n,

Γ⊢E:r Γ⊢Ec i :T i

8/56

Lnag Bi a l g a e n deProgrmaamtino2L(2P)

Rappel des règles de typage

E:t

Γ⊢A:t→uΓ⊢B:t Γ⊢A B:u

Γx7→t⊢E:u Γ⊢funx→E:t→u

Γ⊢A:tΓx7→t⊢B:u Γ⊢letx=AinB:u

Γx7→t⊢A:tΓx7→t⊢B:u Γ⊢let recx=AinB:u

∀i1≤i≤pΓ;x 1 7→T p1   x n i 7→T pn i Γ⊢M:T=match

⊢

E i :T

9/65

Lang Bi a l g a e n deProgrmaamitno2(L2P)

En somme, qu’est-ce qu’un type ?

Moyens de construction élémentaires : (principesd’introduction)

Indiquent les valeurs du type (infos non réductibles) ◮ produits (ex. record Pascal, struct C, {} Ocaml, * ML) ◮ sommes (sommes ML, articles avec variantes Pascal) ◮ exponentielles (fonctions, tableaux)

Procédés d’utilisation élémentaires : (principesd’élimination)

◮ produits (projections, champs) ◮ sommes (filtrage) ◮ exponentielles (application)

Symétrie introduction / élimination

10 / 56

(fnusuop,pessuopq)seu(|Oq)p,tn→E (t,p)qO→nu(finpe,nieq) |Ou(p,q)→Open,(finei)q

Chercher l’erreur... et la corriger ...par typage pousse ( Neg(Neg(Neg(Et(Vrai,Var("x"))))) ) ; ;

Exercice : repousser les négations vers les extrémités* typeboolexpr= |Vrai|Faux|Varofstring|Negofboolexpr |Etofboolexpr*boolexpr|Ouofboolexpr*boolexpr

2/1

typeboolexprnf= |Vrainf|Fauxnf|Varnfofstring|Negnfofboolexprnf |Etnfofboolexprnf*boolexprnf|Ounfofboolexprnf*boolexprnf

56 lan 2(LP2) Bi noitammargorPedeagngLa E|(t,p)qE→nt(fopussep,pousseq)|E aV(f(fnr | ))v (geN→np)p|ieg(Ne→pp) V|ra iafn aVnrv(→)|Varf(v)Negn(v)→ aF→iarV| uaF| fnxu nfuxFax→Vrx→au|F nie=funconletrec →irViafn itno V|ar etluf=eitcnpcerssuo

Lnaageg

Bilan

derPgorammation

Solution*

2(LP2)

(Analyse

par

typage)

14

/

56

◮ Thearityof a symbolf∈ FisArity(f) ◮ The set of symbols of aritypis denoted byF p . ◮ Elements of arity0,1 . ., .pare respectively called constants, unary, . . .p-ary symbols.

◮ Fis a finite set ◮ Arityis a mapping fromFintoN ◮ (FArity)is aranked alphabetorsignaturedenotedΣ

Definition

eMssasdneTmr itnoifica 2) Un 2(LPtionammargorPedegagnLa rAti gase y

16 / 56