Contrôle de types

Les types en programmation

Expressions de types

Un contrôleur de types

Equivalence de types

Conversions de types

Généricité

Les types en programmation

Les types sont une caractéristique des langages évolués

Représentation des structures de données

Permet la détection d'erreurs

Contrôle de types statique (à la compilation)

Contrôle de types dynamique (à l'exécution)

Langages à objets : enrichissement des possibilités de typage

... codefinal

analyseursyntaxique

contrôleur de types

générateur de code

intermédiaire

générateur de code

final

Expressions de types

Expressions représentant les types des objets

Types de base

booléen, caractère, entier, réel... et type vide

Constructeurs de types

tableaux, pointeurs... voir planche suivante

Noms de types

nécessaires pour les types à définition récursive (exemple : liste chaînée)

Variables de types

nécessaires pour la généricité (fonctions sur les types)

Constructeurs de typesTableau

tableau(I, T) : tableaux d'éléments de type T indicés par des indices de type I

Produit

T1 T2 : couples d'un élément de type T1 et d'un de type T2

Enregistrement

De même plus des noms pour les champs

Pointeur

pointeur(T) : pointeurs sur un objet de type T

Fonction

D R : fonctions de D (type du paramètre) dans R (type de la valeur de retour)

Expressions de typesOn peut aussi représenter les expressions de types par des arbres

ou des graphes acycliques orientés (directed acyclic graph, DAG)

char char

pointeur

integer

char

pointeur

integer

char char pointer(integer)

Un contrôleur de types

P --> D ; E

D --> T id ; D

D --> T --> B C

B --> char | int

C --> [ num ] C

C --> E --> literal | num | id | E mod E | E [ E ]

literal : constante de type caractère

Schéma de traduction

P --> { sommet := new Env() ; } D ; E

D --> T id ; { sommet.mettre(id.name, T.type) ; } D

D -->

T --> B { t := B.type ; } C { T.type := C.type ; }

B --> char { B.type := caractère ; }

B --> int { B.type := entier ; }

C --> { C.type := t ; }

C --> [ num ] C {C.type := tableau(num.val, C1.type) ; }

Type d'une expression

E --> literal E.type := char ;

E --> num E.type := integer ;

E --> id E.type := lookup(id.name) ;

E --> E mod E E.type := if (E1.type = integer

and E2.type = integer)

integer else error() ;

E --> E [ E ] E.type := if (E1.type = tableau(s,t)

and E2.type = integer)

t else error() ;

Type d'une instruction

S --> id = E S.type := if (id.type = E.type)

void else error() ;

S --> if ( E ) S S.type := if (E.type = boolean)

S1.type else error() ;

S --> while ( E ) S S.type := if (E.type = boolean)

S1.type else error() ;

S --> S ; S S.type := if (S1.type = void

and S2.type = void)

void else error() ;

Type d'une fonction

E --> E ( E ) E.type := if (E1.type = st

and E2.type = s)

t else error() ;

Déclarations de types en CLe type des fonctions tient compte de la valeur de retour, mais

pas du type des paramètres

D R

frenvoie(R)

Pour construire un type à partir d'un type fonction, on construit d'abord un type pointeur sur fonction

tableau(frenvoie(int)) int tab[ ]() non

tableau(pointeur(frenvoie(int))) int (* tab[ ])() oui

La déclaration se fait à l'envers par rapport à l'expression de type

Déclarations de types en C

int (* tab[ ])() int type de base

(* tab[ ])() déclarateur (Dtor) Dtor

Dtor

*

( Dtor

)(

)

Dtor

][Dtor

tab

tableau

pointeur

frenvoie

int

déclarateur expression de type

marque de fonction

marque de pointeur

marque de tableau

Schéma de traductionP --> D ; E

D --> D ; D

D --> basic Dtor { addType(Dtor.id,

Dtor.constr || basic.type) ; }

basic --> char { basic.type := char ; }

basic --> int { basic.type := integer ; }

Dtor --> Dtor [ ] { Dtor.constr := Dtor1.constr || array ;

Dtor.id := Dtor1.id ; }

Dtor --> Dtor ( ) { Dtor.constr := Dtor1.constr || freturns ;

Dtor.id := Dtor1.id ; }

Schéma de traductionDtor --> * Dtor { Dtor.constr := Dtor1.constr || pointer ;

Dtor.id := Dtor1.id ; }

Dtor --> ( Dtor ) { Dtor.constr := Dtor1.constr ;

Dtor.id := Dtor1.id ; }

Dtor --> id { Dtor.constr := "" ; Dtor.id := id.entry ; }

Pour déclarer plusieurs variables avec le même type de base :

D --> basic { list.basic := basic.type ;} list

list --> Dtor { addType(Dtor.id, Dtor.constr || list.basic) ; }

list --> { list1.basic := list.basic ;} list , Dtor {

addType(Dtor.id, Dtor.constr || list.basic) ; }

Equivalenced'expressions de types

Vérification de l'équivalence

boolean equiv(s, t) {

if (s et t sont du même type de base) return true ;

else if (s == tableau(s1, s2) && t == tableau(t1, t2))

return equiv(s1, t1) && equiv(s2, t2) ;

etc.

On tolère une différence comme les dimensions d'un tableau passé en paramètre

Equivalenced'expressions de types

Deux types d'équivalence

- structurelle : quand on tombe sur un nom de type, on le remplace par l'expression qu'il représente puis on continue la comparaison

- nominale : quand on tombe sur un nom de type, on le compare directement

Equivalenced'expressions de types

Exemple d'implémentation pour le langage C

Pour plus d'efficacité on teste d'abord l'égalité sur une expression simplifiée codée par un entier

On ne tient pas compte des dimensions des tableaux ni des types des paramètres des fonctions

Codage des constructeurs de types

pointer() array() freturns()

01 10 11

Codage des types de base

boolean char integer real

0000 0001 0010 0011

Conversions de typesL'addition des réels et l'addition des entiers sont des opérations

distinctes car la représentation des données est distincte

Exemple : l'expression x + i où x est un réel et i un entier nécessite une conversion

Traduction en représentation postfixe :

x i intToReal real+

où real+ désigne l'addition des réels

Conversions implicites (coercion)

faites par le compilateur

Conversions explicites (casting)

exemple en C : (float) 10

Conversions implicites

E --> num E.type := integer ;

E --> num.num E.type := real ;

E --> id E.type := lookup(id.entry) ;

E --> E op E E.type := if (E1.type=integer

and E2.type=integer)

integer ;

else if (E1.type=integer

and E2.type=real)

real ;

etc.

Surcharge des opérateursCas où un même symbole représente plusieurs opérateurs

L'opérateur à appliquer est choisi en fonction du contexte

Exemple : + désigne l'addition des entiers ou des matrices

On considère un opérateur comme une fonction

Schéma de traduction pour calculer les types possibles d'une expression

E --> id E.types := lookup(id.entry)

E --> E ( E ) E.types := { t | il existe un s dans E2.types tel que

st est dans E1.types }

Surcharge des opérateursExemple : l'opérateur * peut prendre des opérandes entiers ou

complexes et le résultat peut être entier ou complexe

E.types={i, c}

E.types={i}*.types=

{iii, iic, ccc}

53

E.types={i}

Surcharge des méthodes en Javaclass A {

int a, b; A(int a, int b){this.a = a; this.b = b; }

} class B{

private A couple; B(int a, int b){couple = new A(a,b); } B(A couple){this.couple = new A(couple.a, couple.b); } A getA( ){ return couple;} void ajouter(int inc){getA().a += inc; getA().b += inc; } void ajouter(B couple){

this.getA().a += couple.getA().a; this.getA().b += couple.getA().b; }

}

Surcharge des méthodes en Java

Définitions de plusieurs méthodes de même nom dans la même classe ou interface (ou par héritage)

Les méthodes surchargées diffèrent par leur signature

Signature d'une méthode : nombre, ordre et type des paramètres formels void ajouter(int inc){ void ajouter(B couple){

Surcharge des méthodes en JavaB c1 = new B(3, 5); B c2; System.out.println("c1=" + c1); c1.ajouter(5); System.out.println("c1=" + c1); c2 = new B(c1.getA()); c2.ajouter(c1);

Sélection de la méthode pour un appel

Utilisation du type des paramètres effectifs

S'ils correspondent exactement à la signature d'une des méthodes, elle est sélectionnée

Le type de retour n'intervient pas

Surcharge des méthodes en Java

Sélection de la méthode pour un appel

Utilisation du type des paramètres effectifs

S'ils ne correspondent exactement à la signature d'aucune des méthodes, on cherche des correspondances par conversion de type

Sélection de méthode surchargée

Exemple d'algorithme de sélection de méthode surchargée

S'il n'y a pas de correspondance exacte avec une des signatures concurrentes, on utilise les conversions ascendantes

double

float

byte

...

interface

classe mère

classe fille

...

Sélection de méthode surchargéepour chaque signature concurrente s {

distance (s) = 0 ;

pour chaque paramètre

distance (s) +=

nombre de conversions ascendantes directes pour

passer du type du paramètre effectif au type du

paramètre formel ; }

calculer la distance minimale m ;

s'il existe une seule signature s telle que distance(s) == m

sélectionner s ;

sinon erreur de syntaxe ;

Fonctions génériquesFonctions dont les paramètres ou la valeur de retour sont de type

non précisé

Exemples

L'opérateur & du C : si E est de type t, alors & E est de type pointer(t)

Les fonctions génériques du langage ADA

Certaines fonctions en langage CAML

ExempleCalcul de la longueur d'une liste

Exemple non générique en C

typedef struct cell { int info ; struct cell * link ; } cell ;

int length(cell * list) {

int len = 0 ;

while (list) { len ++ ; list = list -> link ; }

return len ; }

On est obligé de connaître le type des éléments de la liste pour déclarer le type cell et la fonction

Exemple

Exemple générique en ML

fun length(list) =

if null(list) then 0

else length(tl(list)) + 1 ;

null() et tl() sont prédéfinies

Un langage avec généricitéP --> D ; E

D --> D ; D | id : Q

Q --> typeVar . Q | T

T --> basicType

| unaryConstructor ( T )

| typeVar

| T T

| T T

| ( T )

E --> E ( E ) | E , E | id

ExempleDéclaration de la fonction de déréférencement

deref : . pointer() ;

Déclaration d'un pointeur

q : pointer(pointer(integer)) ;

Arbre syntaxique de l'expression deref(deref(q))

apply.type=

deref.type=.pointer()

q.type=pointer(pointer(integer))

apply.type=

deref.type=.pointer()

ExempleDes occurrences distinctes d'une fonction générique n'ont pas

nécessairement le même type

Les types des variables doivent être unifiés

Ils ne peuvent plus être déterminés à partir de leurs constituants

apply.type==integer

deref.type=.pointer()

q.type=pointer(pointer(integer))

apply.type==pointer(integer)

deref.type=.pointer()