Représentation des données ========================== Contraintes sur les représentations de données: ----------------------------------------------- Opérations nécessaires: - est-ce qu'une racine est un pointeur dans le tas? est_ptr(r) - quels sont les pointeurs contenus dans un bloc? fils(p) - quelle est la taille d'un bloc? taille(p) Un exemple d'implémentation: - Les pointeurs sont alignés sur un mot ==> multiples de 4 ==> bit de poids faible à 0. Les non-pointeurs (e.g. des entiers n) sont codés par 2n+1 ==> bit de poids faible à 1. Donc: est_ptr(r) = (r & 1 == 0) && (r >= début_du_tas) && (r <= fin_du_tas) Ça s'appelle le ``tagging'' des représentations. Remarque: l'arithmétique sur entiers est un peu compliquée mais quand même efficace: repr(x+y) = repr(x) + repr(y) - 1 repr(x+1) = repr(x) + 2 repr(x*y) = (repr(x) - 1) * (repr(y) >> 1) + 1 Tests naturels: if x>=y ... devient if repr(x) >= repr(y) ... - Les blocs ont un mot d'en-tête (juste avant r) qui contient la taille du bloc et un bit structuré / non structuré: taille(p) = entête(p).taille fils(p) = if entête(p).structuré then { field_i(p) | 0 <= i < taille(p) && est_ptr(field_i(p)) } else 0 Remarque: on gâche un mot par objet... Variante: le schéma BIBOP (big bag of pages). Le tas est divisé en pages contenant des objets de même taille et de même nature (structuré / non-structuré). taille(p) = page(p).taille fils(p) = if page(p).structuré then ... else 0 Plus compact mais plus compliqué à gérer. Variante: les GC conservatifs(Boehm, Bartlett): pas de codage des entiers, et opérations approximatives. est_ptr(r) = (r >= début_du_tas) && (r <= fin_du_tas) taille(p), fils(p) : utilise un bitmap du tas (1 bit par mot). Détermine une assez bonne approximation des "vrais" pointeurs (peu d'entiers ressemblent à des pointeurs!), mais interdit de déplacer les objets (ni copie ni compaction: M&S strict). Aussi: certaines optimisations du compilateur peuvent "casser" le GC. Encodage des types de données ML: --------------------------------- * Entiers 31 bits: immédiats, tag 1 dans le bit de poids faible * Caractères, booléens, ... : comme des entiers * Entiers 32 bits: boxed (alloués dans un bloc non structuré et représentés via un pointeur) * Flottants (32 ou 64 bits): boxed * Chaînes: bloc non structuré * Tableaux: bloc structuré * N-uplets, records: bloc structuré * Types concrets: - constructeurs constants: numérotés par des petits entiers - constructeurs avec arguments: bloc structuré avec 1 champ de plus pour stocker le constructeur (ou astuces pour mettre le constructeur dans l'en-tête) * Fermetures: comme un N-uplet Pour les pointeurs infixes: en-têtes à l'intérieur du bloc. Peut-on faire mieux? -------------------- On voudrait bien: * Entiers 32 bits non alloués * Flottants 32 et 64 bits non alloués Pour ce faire: ne pas attacher d'infos aux valeurs, mais utiliser des infos séparées de type statique. Si typage statique monomorphe (Pascal, C): on communique les types statiques au GC. est_ptr(r: tau) = tau = int || tau = bool || tau = char fils(p: tau) = match tau with string -> 0 | tau1 * tau2 -> { field1(p) : tau1; field2(p) : tau2 } | tau list -> if p = [] then 0 else { field1(p) : tau; field2(p) : tau list } | ... taille(p: tau) = match tau with tau1 * tau2 -> 2 | tau list -> if p = [] then 0 else 2 | string -> taille_chaîne(p) | ... Ca permet d'autres optimisations, comme par exemple: * Utiliser les registres flottants pour passer les arguments et résultats flottants des fonctions * Manipuler les paires, triplets non alloués (on transporte les 2 ou 3 composantes dans 2 ou 3 registres) Tout cela est impossible sans informations de typage statique, car le générateur de code doit savoir la taille (nombre de composantes) et le type (entier/pointeur/flottant) des objets manipulés pour compiler une affectation un accès dans un tableau un appel de fonction Si typage statique non monomorphe (polymorphisme, types abstraits): les types statiques ne coincident pas avec les types dynamiques! let f x = x impossible de déterminer la taille de x, les registres utilisés, racine ou pas racine? Solutions: 1- Représentations uniformes à la Lisp 2- Restrictions sur le langage source Exple: Modula-3: un type abstrait doit être implémenté par un pointeur 3- Reconstruction dynamique des types Passer en argument supplémentaire aux fn polymorphes la "valeur" de leurs paramètres de types. Problème: ça coûte cher de passer les infos ça coûte cher de les exploiter (GC, mais surtout conventions d'appel) 4- Dupliquer le code des fonctions polymorphes et des foncteurs en autant de version que de types avec lesquels ils sont utilisés (les caractéristiques du système de types de ML garantissent que le nombre de version spécialisées est fini). Problème: augmentation de la taille du code et du temps de compilation la production des versions spécialisées ne peut se faire que sur un programme complet, au moment du link. 5- Représentations mixtes et coercions. Si type statique monomorphe: représentation à la C. On passe à des représentations uniformes quand le type statique devient non monomorphe: variable de type (entrée dans une fn polymorphe) nom de type abstrait (sortie du module implémentant le type abstrait) On revient aux représentations à la C quand le type statique redevient monomorphe: retour d'une fonction polymorphe entrée dans le module implémentant le type abstrait Insertion de coercions d'un type à un autre (compatibles) pour changer les représentations: C(e, int, alpha) = tag_int(e) C(e, alpha, int) = untag_int(e) C(e, float, alpha) = box_float(e) C(e, alpha, float) = unbox_float(e) C(e, t->s, t'->s') = fun x -> let y = C(x, t', t) in let r = e x in C(r, s, s') C(e, t * s, t' * s') = (C(fst(e), t, t'), C(snd(e), s, s')) C(e, alpha * beta, gamma) = box_pair(e) C(e, gamma, alpha * beta) = unbox_pair(e) Coercions insérée quand on instancie une variable polymorphe: E |- x : forall alpha. tau --------------------------- C(x, tau, tau[alpha<-sigma]) E |- x : tau[alpha <- sigma] Et aussi quand on abstrait un type: struct : sig type alpha = sigma type alpha let x = ... val x: tau C(x, tau[alpha <- sigma], tau) ... ... end end Exemple: let f x = (x, x) let p = f 3.1415 devient let p = C(f, alpha -> alpha * alpha, float -> float * float) 3.1415 C(f, ...) = fun x -> let y = box(x) in let r = f y in (unbox_float(fst(unbox_pair(r))), unbox_float(snd(unbox_pair(r)))) D'où après beta-reduction: let p = let r = f (box 3.1415) in (unbox_float(fst(unbox_pair(r))), unbox_float(snd(unbox_pair(r))))