L'objectif de cette séance est d'étendre le langage A6000 avec des structures définies par l'utilisateur. On veut autoriser une déclaration de la forme
struct id (ty₁ f₁; ...; tyₙ fₙ;)qui définit un nouveau type nommé id pour une structure de données comportant des champs f₁ à fₙ respectivement de types ty₁ à tyₙ. On manipulera de telles structures avec trois opérations de base :
- new id() crée une structure de type id dont les champs ne sont pas initialisés.
- t.f renvoie le contenu du champ f de la structure t.
- t.f := v affecte la valeur v au champ f de la structure t.
1. Description
1.1. Extension du langage source
1.1.1. Lexique
Le langage contient les nouveaux mots-clés struct et new ainsi que le nouveau symbole terminal . (point).
1.1.2. Grammaire
Un programme est maintenant constitué d'un ensemble de déclarations de structures et d'un ensemble de définitions de fonctions. La règle du non-terminal [prog] est modifiée, et on a un nouveau non-terminal [struct_decl] pour les déclarations de structures.
[struct_decl] ← struct {id} ( { [field_decl] }* )
[field_decl] ← [typ] {id} ;
[prog] ← { [struct_decl] }* { [fun_decl] }*
Les grammaires des expressions et des emplacements sont étendues chacune
d'une nouvelle construction, pour la création d'une structure et l'accès
à un champ d'une structure.
[expression] ← ...
| new {id} ( )
[location] ← ...
| [expression] . {id}
La règle [location] ← [expression] . {id} doit être plus
prioritaire que les règles liées aux autres formes d'expressions.
Enfin, la grammaire des types est étendue d'une nouvelle construction pour les types des structures :
[typ] ← ...
| ( {id} )
Notez que ces types sont indiqués entre parenthèses pour éviter un conflit
dans la grammaire.
1.1.3. Sémantique
Une structure est constituée de plusieurs champs, chaque champ f contenant une valeur d'un type donné ty. Le nombre et les caractéristiques des champs d'une structure de type id sont donné par la déclaration struct id ( ... ) correspondante.
Une expression new id() produit une structure de type id dont les champs ne sont pas initialisés. Le résultat de cette expression est la structure elle-même.
Une expression e.f renvoie la valeur contenue dans le champ de nom f de la structure produite par l'évaluation de e.
Une instruction e₁.f := e₂ stocke la valeur de l'expression e₂ dans le champ de nom f de la structure produite par l'évaluation de e₁.
Comme pour les tableaux, le test d'égalité t == u ne s'intéresse pas au contenu des structures t et u mais à leur identité.
1.2. Extension du compilateur
À l'intérieur du compilateur, l'objectif sera de représenter aussi vite que possible ces nouvelles constructions comme des cas particuliers de manipulation de tableaux. En l'occurrence, il n'y aura rien à modifier dans le compilateur au-delà de l'étape UntypedAst.
1.2.1. Syntaxes abstraites
Dans la syntaxe abstraite SourceAst, on a un nouveau type f_access = expression * string et on introduit de nouveaux constructeurs :
- TypStruct of string dans le type typ,
- NewRecord of string dans le type expression, et
- FieldAccess of f_access dans le type location.
type program = {
functions: (string * function_info) list;
structs: (string * struct_info) list
}
and struct_info = (string * typ) list
Ces modifications sont répercutée sur la syntaxe typée TypedAst.
1.2.2. Représentations
Dans la syntaxe UntypedAst, on représentera :
- une structure de type id comme un tableau dont la taille correspond au nombre de champs des structures de ce type, et
- un accès t.f comme un accès dans un tableau à la case dont l'indice correspond au champ f.
Cette traduction pourra être intégralement faite dans le module TypedtoUntyped. À partir de l'étape UntypedAst, il ne sera plus nécessaire de conserver aucune référence aux structures ni à leurs types.
2. Travail attendu
Vous devez modifier les parties avant de votre compilateur, jusqu'au module UntypedAst non inclus, pour intégrer ces nouveaux aspects :
- Déclaration de types de structures
- Création d'une nouvelle structure non initialisée d'un type donné
- Lecture de la valeur contenue dans un champ d'une structure
- Écriture d'une nouvelle valeur dans un champ d'une structure
3. Extensions
3.1. Champs immuables
Ajouter la possibilité d'annoter une déclaration de structure pour indiquer que certains champs ne doivent pas être modifiés (c'est-à-dire ne peuvent être la cible d'une instruction t.f := e).
Étendre la vérification des types pour effectivement interdire les écritures dans de tels champs immuables.
3.2. Initialisation
Étendre la syntaxe pour permettre de créer une structure dont tout ou partie des champs sont initialisés avec des valeurs passées en paramètres. Les valeurs pourront être explicitement associées à certains champs.
3.3. Égalité structurelle guidée par les types
L'égalité structurelle =, déjà évoquée dans une extension des tableaux, ne s'intéresse pas à l'identité des objets complexes mais à leur contenu. Autrement dit, si a et b sont des valeurs immédiates (entières ou booléennes), = est équivalent à ==, tandis que si a et b sont des structures, alors a = b vaut true si et seulement s'il s'agit de deux structures du même type, et si pour tout champ f on a de plus a.f = b.f (de même en cas de tableaux, les tailles et contenus doivent correspondre). Cette opération donne false si les deux opérandes sont de genres ou de tailles incompatibles.
La solution proposée précédemment consistait à écrire du code assembleur pour parcourir et comparer deux structures. Cependant, on peut gérer ceci à un niveau beaucoup plus haut en se basant sur les types des objets et en traduisant l'opération a = b en une expression faisant intervenir == :
- Si a et b ont des types différents, traduire en false.
- Si a et b sont du même type de base, traduire en a == b.
- Si a et b sont du même type structuré, traduire en une conjonction des a.fᵢ = b.fᵢ (et appliquer récursivement la traduction). Le cas des tableaux est similaire.
Remarque : une autre approche similaire consisterait à traiter = de la même manière qu'une fonction surchargée, mais il y a une petite subtilité.
Ajouter au langage un opérateur = d'égalité structurelle.
3.4. Sous-typage (prépare à l'introduction des objets)
On veut permettre de déclarer qu'un nouveau type de structure S étend un type de structure déjà défini S₀ : en plus de ses champs propres, S contient tous les champs déclarés dans S₀ ; en outre, une structure de type S peut être utilisée à la place d'une structure de type S₀ (par exemple lorsqu'une fonction a un paramètre formel de type S₀).
3.4.1. Extensions de structures
Étendre le langage pour introduire ces mécanismes, en suivant les quelques principes suivants :
- La vérification des types doit être assouplie pour qu'une structure étendue soit considérée comme compatible avec la structure d'origine.
- Faire qu'un champ f d'une structure S soit associé à la même case du bloc dans les structures S et dans toutes ses extensions.
- En cas d'ambiguïté au niveau des fonctions surchargées, sélectionner une fonction arbitraire parmi les fonctions compatibles.
3.4.2. Transtypage
Intégrer une opération de transtypage pour modifier le type apparent d'une expression, en suivant les principes suivants :
- Un transtypage vers un type plus général réussi toujours.
- Un transtypage vers un type étendu génère un test dynamique.
- Un transtypage vers un type incomparable est rejeté lors de la phase de vérification des types.