LANGAGES FONCTIONNELS LANGAGES FONCTIONNELS
Tels ML Miranda

LES REGLES DE TYPE
Typage fort (strict)
Impossible d'appliquer un objet dans un contexte interdit
condition testée par le compilateur

TYPAGE IMPLICITE
Pas d'obligation de déclarer les types! Le compilateur peut (doit) calculer quels sont les types de chaque (identificateur, expression)

f x = x+1; x est entier et f est entier  ®  entier

f  [ ] =  0;  f(h:t) = h; f est [entier] ®   entier

f [ ] L2  =  [ ]; f L1 [ ] = [ ];
      f (h1:t1) (h2:t2) = (h1+h2:f t1 t2)
f est [entier] ®   [entier] ®   [entier]

( X ®  Y ®  Z équivaut à X ® (Y ®  Z) est à peu près le type d'une fonction de deux paramètres)

POLYMORPHISME
Un objet peut avoir plusieurs types possibles; le bon type est choisi (par le compilateur) selon le contexte:

l [ ] = 0; l (h:t) = 1+l  t
l (longueur) peut être [entier]  ®  entier ou [char]  ®  entier etc.

On écrit le type de l: [a]  ®  entier

Un deuxième exemple: concaténation:
conc [ ] L = L; conc (h:t) L = (h:conc t L)
avec type [a]  ®  [a]  ®  [a]

(A noter que tout a devra être substitué par le même type)

paire  [ ] [ ] = [ ];
      paire (h1:t1) (h2:t2) = ((h1,h2):paire t1 t2)
avec type [a]  ®  [b]  ® [(a,b)]

(Aussi des constructeurs polymorphes de types; arbre int, arbre char, etc.)

COMMENT DECIDER LES TYPES?
Pour décider le type d'une fonction définie (f):

 

RESOLUTION DES EQUATIONS
Il faut trouver (si possible) une substitution (fonction des identificateurs de type aux expressions de type) qui vérifie toutes les équations

On prend les équations dans n'importe quel ordre et résout chacun en rajoutant à la substitution les informations trouvées

Si un coté d'une équation est une variable, on rajoute à la substitution que cette variable donne le type de l'autre coté

Si les deux types sont construits par le même constructeur de types (par exemple liste ou fonction), on rajoute des équations pour les types utilisés dans la construction

Sinon erreur

Terminaison garantie

EVALUATION PARESSEUSE
Le mode d'évaluation où on n'évalue un paramètre que quand (si) la fonction dépend de sa valeur
et on n'évalue que les parties d'une structure dont dépend la fonction

Exemple:
sommepremiers  (h1:t1) (h2:t2) = h1+h2 peut être évalué sans évaluer t1 et t2

Permet même la manipulation (raisonnable) de structures infinies!
puissances2  i = (i:puissances2 2*i)
sommepremiers (puissances2 4)  (puissances2 16) calcule 20.

Evaluation paresseuse est standard en Miranda et d'autres langages.




File translated from TEX by TTH, version 3.05.
On 28 Apr 2003, 09:58.