Syndicat tagué

En informatique , une union étiquetée , également appelée variante , enregistrement de variante , type de choix , union discriminée , union disjointe , type de somme ou coproduit , est une structure de données utilisée pour contenir une valeur qui peut prendre plusieurs types différents, mais fixes. Un seul de ces types peut être utilisé à un moment donné, et un champ d'étiquette indique explicitement quel type est utilisé. On peut la considérer comme un type qui a plusieurs « cas », chacun devant être traité correctement lorsque ce type est manipulé. Cela est essentiel pour définir des types de données récursifs, dans lesquels certains composants d'une valeur peuvent avoir le même type que cette valeur, par exemple pour définir un type pour représenter des arbres , où il est nécessaire de distinguer les sous-arbres multi-nœuds et les feuilles. Comme les unions ordinaires , les unions étiquetées peuvent économiser de l'espace de stockage en chevauchant les zones de stockage pour chaque type, puisqu'une seule est utilisée à la fois.

Les unions étiquetées sont particulièrement importantes dans les langages de programmation fonctionnels tels que ML et Haskell , où elles sont appelées types de données (voir type de données algébrique ) et le compilateur peut vérifier que tous les cas d'une union étiquetée sont toujours traités, évitant ainsi de nombreux types d'erreurs. Les types de sommes vérifiées au moment de la compilation sont également largement utilisés dans Rust , où ils sont appelés enum . Ils peuvent cependant être construits dans presque tous les langages de programmation et sont beaucoup plus sûrs que les unions non étiquetées, souvent simplement appelées unions, qui sont similaires mais ne suivent pas explicitement quel membre d'une union est actuellement utilisé.

Les unions marquées sont souvent accompagnées du concept de constructeur , qui est similaire mais pas identique à un constructeur pour une classe . Un constructeur est une fonction ou une expression qui produit une valeur du type union marquée, à partir d'une balise et d'une valeur du type correspondant.

Mathématiquement, les unions étiquetées correspondent à des unions disjointes ou discriminées , généralement écrites en utilisant +. Étant donné un élément d'une union disjointe A + B , il est possible de déterminer s'il provient de A ou de B . Si un élément se trouve dans les deux, il y aura deux copies effectivement distinctes de la valeur dans A + B , l'une de A et l'autre de B .

En théorie des types , une union étiquetée est appelée type somme . Les types somme sont le dual des types produit . Les notations varient, mais généralement le type somme A + B est accompagné de deux formes d'introduction ( injections ) inj ₁ : A → A + B et inj ₂ : B → A + B. La forme d'élimination est l'analyse de cas, connue sous le nom de correspondance de motifs dans les langages de type ML : si e est de type A + B et e ₁ et e 2 sont de type sous les hypothèses x : A et y : B respectivement, alors le terme est de type . Le type somme correspond à la disjonction logique _{intuitionniste} sous la correspondance Curry-Howard .

Un type énuméré peut être vu comme un cas dégénéré : une union étiquetée de types unitaires . Il correspond à un ensemble de constructeurs nullaires et peut être implémenté comme une simple variable d'étiquette, car il ne contient aucune donnée supplémentaire en plus de la valeur de l'étiquette.

De nombreuses techniques de programmation et structures de données, y compris la corde , l'évaluation paresseuse , la hiérarchie de classes (voir ci-dessous), l'arithmétique de précision arbitraire , le codage CDR , le bit d'indirection et d'autres types de pointeurs étiquetés , sont généralement implémentées à l'aide d'une sorte d'union étiquetée.

Une union étiquetée peut être considérée comme le type le plus simple de format de données autodescriptif . L'étiquette de l'union étiquetée peut être considérée comme le type le plus simple de métadonnées .

Le principal avantage d'une union balisée par rapport à une union non balisée est que tous les accès sont sûrs et que le compilateur peut même vérifier que tous les cas sont traités. Les unions non balisées dépendent de la logique du programme pour identifier correctement le champ actuellement actif, ce qui peut entraîner un comportement étrange et des bogues difficiles à trouver si cette logique échoue.

Le principal avantage d'une union balisée par rapport à un simple enregistrement contenant un champ pour chaque type est qu'elle économise de l'espace de stockage en superposant le stockage pour tous les types. Certaines implémentations réservent suffisamment d'espace de stockage pour le type le plus grand, tandis que d'autres ajustent dynamiquement la taille d'une valeur d'union balisée selon les besoins. Lorsque la valeur est immuable , il est simple d'allouer juste assez d'espace de stockage selon les besoins.

Le principal inconvénient des unions étiquetées est que l'étiquette occupe de l'espace. Comme il existe généralement un petit nombre d'alternatives, l'étiquette peut souvent être compressée en 2 ou 3 bits partout où il y a de la place, mais parfois même ces bits ne sont pas disponibles. Dans ce cas, une alternative utile peut être les étiquettes pliées , calculées ou codées , où la valeur de l'étiquette est calculée dynamiquement à partir du contenu du champ d'union. Des exemples courants sont l'utilisation de valeurs réservées , où, par exemple, une fonction renvoyant un nombre positif peut renvoyer -1 pour indiquer un échec, et les valeurs sentinelles , le plus souvent utilisées dans les pointeurs étiquetés .

Parfois, les unions non étiquetées sont utilisées pour effectuer des conversions au niveau des bits entre les types, appelées conversions de réinterprétation en C++. Les unions étiquetées ne sont pas destinées à cet usage ; en général, une nouvelle valeur est attribuée à chaque fois que la balise est modifiée.

De nombreux langages prennent en charge, dans une certaine mesure, un type de données universel , qui est un type qui inclut toutes les valeurs de tous les autres types, et souvent un moyen est fourni pour tester le type réel d'une valeur du type universel. Ceux-ci sont parfois appelés variantes . Alors que les types de données universels sont comparables aux unions étiquetées dans leur définition formelle, les unions étiquetées typiques incluent un nombre relativement faible de cas, et ces cas constituent différentes manières d'exprimer un concept cohérent unique, tel qu'un nœud de structure de données ou une instruction. En outre, on s'attend à ce que chaque cas possible d'une union étiquetée soit traité lorsqu'elle est utilisée. Les valeurs d'un type de données universel ne sont pas liées et il n'existe aucun moyen réalisable de les traiter toutes.

Comme les types d'options et la gestion des exceptions , les unions étiquetées sont parfois utilisées pour gérer l'occurrence de résultats exceptionnels. Souvent, ces balises sont intégrées au type en tant que valeurs réservées , et leur occurrence n'est pas systématiquement vérifiée : c'est une source assez courante d'erreurs de programmation. Cette utilisation des unions étiquetées peut être formalisée sous forme de monade avec les fonctions suivantes :

où « value » et « err » sont les constructeurs du type union, A et B sont des types de résultats valides et E est le type des conditions d'erreur. Alternativement, la même monade peut être décrite par return et deux fonctions supplémentaires, fmap et join :

Supposons que nous voulions construire un arbre binaire d'entiers. En ML, nous le ferions en créant un type de données comme celui-ci :

type de données 
arbre 
= 
Feuille 
| 
Nœud 
de 
( int 
* 
arbre 
* 
arbre )

Il s'agit d'une union étiquetée avec deux cas : l'un, la feuille, est utilisé pour terminer un chemin de l'arbre et fonctionne à peu près comme une valeur nulle dans les langages impératifs. L'autre branche contient un nœud, qui contient un entier et un sous-arbre gauche et droit. Leaf et Node sont les constructeurs, qui nous permettent de produire réellement un arbre particulier, tel que :

Noeud ( 5 , 
Noeud ( 1 , 
Feuille , 
Feuille ), 
Noeud ( 3 , 
Feuille , 
Noeud ( 4 , 
Feuille , 
Feuille )))

qui correspond à cet arbre :

Nous pouvons maintenant facilement écrire une fonction typesafe qui, par exemple, compte le nombre de nœuds dans l'arbre :

fun 
countNodes ( Leaf ) 
= 
0 
| 
countNodes ( Node ( int , 
gauche , 
droite )) 
= 
1 
+ 
countNodes ( gauche ) 
+ 
countNodes ( droite )

Dans ALGOL 68 , les unions marquées sont appelées modes unis , la balise est implicite et la caseconstruction est utilisée pour déterminer quel champ est marqué :

mode node = union (real, int, compl, string);

Exemple d'utilisation union casede node:

nœud n := "1234"; cas n dans ( réel r) : print(("réel :", r)), ( int i): print(("int:", i)), ( compl c): print(("compl:", c)), ( chaîne s) : print(("chaîne :", s)) out print(("? :", n)) esac

Les langages de programmation fonctionnels tels que ML (des années 1970) et Haskell (des années 1990) accordent un rôle central aux unions étiquetées et ont le pouvoir de vérifier que tous les cas sont traités. D'autres langages prennent également en charge les unions étiquetées.

Pascal , Ada et Modula-2 les appellent des enregistrements variants ( type formellement discriminé en Ada) et nécessitent que le champ de balise soit créé manuellement et que les valeurs de balise soient spécifiées, comme dans cet exemple Pascal :

type shapeKind = ( carré , rectangle , cercle ) ; forme = enregistrement centerx : entier ; centery : entier ; cas type : shapeKind de carré : ( côté : entier ) ; rectangle : ( largeur , hauteur : entier ) ; cercle : ( rayon : entier ) ; fin ;

et cet équivalent Ada :

type 
Shape_Kind 
est 
( Carré , 
Rectangle , 
Cercle ); 
type 
Shape 
( Kind 
: Shape_Kind ) 
est 
enregistrement 
Center_X 
: 
Entier ; 
Center_Y 
: 
Entier ; 
cas 
Kind 
est 
lorsque 
Carré 
=> 
Côté 
: 
Entier ; 
lorsque 
Rectangle 
=> 
Largeur , 
Hauteur 
: 
Entier ; 
lorsque 
Cercle 
=> 
Rayon 
: 
Entier ; 
fin 
de cas ; 
fin d'enregistrement ;
-- Toute tentative d'accéder à un membre dont l'existence dépend 
d'une certaine valeur du discriminant, alors que le 
discriminant n'est pas celui attendu, génère une erreur.

En C et C++ , une union balisée peut être créée à partir d'unions non balisées en utilisant une discipline d'accès stricte où la balise est toujours vérifiée :

enum ShapeKind { Carré , Rectangle , Cercle };
struct Shape { int centerx ; int centery ; enum ShapeKind kind ; union { struct { int side ; }; /* Carré */ struct { int width , height ; }; /* Rectangle */ struct { int radius ; }; /* Cercle */ }; };
int getSquareSide ( struct Shape * s ) { assert ( s -> kind == Carré ); return s -> côté ; }
void setSquareSide ( struct Shape * s , int side ) { s -> kind = Carré ; s -> side = côté ; }
/* et ainsi de suite */

Tant que les champs d'union ne sont accessibles que via les fonctions, les accès seront sûrs et corrects. La même approche peut être utilisée pour les balises codées ; nous décodons simplement la balise puis la vérifions à chaque accès. Si l'inefficacité de ces vérifications de balises est un problème, elles peuvent être automatiquement supprimées dans la version finale.

C et C++ prennent également en charge une union étiquetée particulière : le pointeur éventuellement nul . Cela peut être comparé au optiontype dans ML ou au Maybetype dans Haskell, et peut être vu comme un pointeur étiqueté : une union étiquetée (avec une balise codée) de deux types :

• Pointeurs valides,
• Un type de pointeur nul avec une seule valeur, null, indiquant une condition exceptionnelle.

Malheureusement, les compilateurs C ne vérifient pas que le cas nul est toujours traité. Il s'agit d'une source d'erreurs particulièrement courante dans le code C, car il existe une tendance à ignorer les cas exceptionnels.

Un dialecte avancé de C, appelé Cyclone , dispose d'un support intégré étendu pour les unions étiquetées.

Les types d'énumération dans les langages Rust , Haxe et Swift fonctionnent également comme des unions étiquetées.

La bibliothèque de variantes des bibliothèques Boost C++ a démontré qu'il était possible d'implémenter une union balisée sécurisée en tant que bibliothèque en C++, visitable à l'aide d'objets de fonction.

struct display : boost :: static_visitor < void > { void operator ()( int i ) { std :: cout << "C'est un int, avec la valeur " << i << std :: endl ; }
void operator ()( const std :: string & s ) { std :: cout << "C'est une chaîne, avec la valeur " << s << std :: endl ; } };
boost :: variant < int , std :: string > v = 42 ; boost :: apply_visitor ( display (), v );
boost :: variant < int , std :: string > v = "bonjour le monde" ; boost :: apply_visitor ( display (), v );

Scala a des classes de cas :

classe abstraite scellée Objet de cas d'arbre Feuille étend la classe de cas d'arbre Node ( valeur : Int , gauche : Arbre , droite : Arbre ) étend l'arbre
val tree = Noeud ( 5 , Noeud ( 1 , Feuille , Feuille ), Noeud ( 3 , Feuille , Noeud ( 4 , Feuille , Feuille )))

Étant donné que la hiérarchie des classes est scellée, le compilateur peut vérifier que tous les cas sont traités dans une correspondance de modèle :

correspondance d'arbre { case Node ( x , _ , _ ) => println ( "valeur du nœud de niveau supérieur : " + x ) case Leaf => println ( "le nœud de niveau supérieur est une feuille" ) }

Les classes de cas de Scala permettent également la réutilisation via le sous-typage :

classe abstraite scellée Shape ( centerX : Int , centerY : Int ) classe de cas Square ( côté : Int , centerX : Int , centerY : Int ) étend Shape ( centerX , centerY ) classe de cas Rectangle ( longueur : Int , hauteur : Int , centerX : Int , centerY : Int ) étend Shape ( centerX , centerY ) classe de cas Circle ( rayon : Int , centerX : Int , centerY : Int ) étend Shape ( centerX , centerY )

F# a discriminé les syndicats :

type Tree = | Feuille | Noeud de valeur : int * gauche : Tree * droite : Tree
laissez l'arbre = Noeud ( 5 , Noeud ( 1 , Feuille , Feuille ), Noeud ( 3 , Feuille , Noeud ( 4 , Feuille , Feuille )))

Étant donné que les cas définis sont exhaustifs, le compilateur peut vérifier que tous les cas sont traités dans une correspondance de modèle :

arbre de correspondance avec | Node ( x , _, _) -> printfn "valeur du nœud de niveau supérieur : %i" x | Leaf -> printfn "le nœud de niveau supérieur est une feuille"

Les énumérations de Haxe fonctionnent également comme des unions étiquetées :

enum Couleur { Rouge ; Vert ; Bleu ; Rgb ( r : Int , g : Int , b : Int ); }

Ceux-ci peuvent être mis en correspondance à l'aide d'une expression de commutation :

switch ( color ) { case Red : trace ( "La couleur était rouge" ); case Green : trace ( "La couleur était verte" ); case Blue : trace ( "La couleur était bleue" ); case Rgb ( r , g , b ): trace ( "La couleur avait une valeur rouge de " + r ); }

Nim possède des variantes d'objet similaires dans leur déclaration à celles de Pascal et Ada :

type 
ShapeKind = enum skSquare , skRectangle , skCircle Shape = objet centerX , centerY : int cas kind : ShapeKind de skSquare : side : int de skRectangle : length , height : int de skCircle : radius : int

Les macros peuvent être utilisées pour émuler la correspondance de modèles ou pour créer du sucre syntaxique pour déclarer des variantes d'objet, vues ici comme implémentées par le package patty :

galette d'importation
proc `~` [ A ] ( a : A ): ref A = nouveau ( résultat ) résultat [] = a
variante Liste [ A ] : Nil Cons ( x : A , xs : ref Liste [ A ] )
proc listHelper [ A ] ( xs : seq [ A ] ): Liste [ A ] = si xs . len == 0 : Nil [ A ] () sinon : Cons ( xs [ 0 ] , ~ listHelper ( xs [ 1 .. xs . high ] ))
liste de procédures [ A ] ( xs : varargs [ A ] ): Liste [ A ] = listHelper ( @ xs )
proc sum ( xs : Liste [ int ] ): int = ( bloc : correspondance xs : Nil : 0 Cons ( y , ys ): y + sum ( ys [] ) )
echo somme ( liste ( 1 , 2 , 3 , 4 , 5 ))

Les énumérations sont ajoutées dans Scala 3, nous permettant de réécrire les exemples Scala précédents de manière plus concise :

enum Tree [ + T ]: case Leaf case Node ( x : Int , gauche : Tree [ T ], droite : Tree [ T ])
enum Shape ( centerX : Int , centerY : Int ) : case Square ( side : Int , centerX : Int , centerY : Int ) extends Shape ( centerY , centerX ) case Rectangle ( length : Int , height : Int , centerX : Int , centerY : Int ) extends Shape ( centerX , centerY ) case Circle ( rayon : Int , centerX : Int , centerY : Int ) extends Shape ( centerX , centerY )

Le langage Rust offre un support étendu pour les unions étiquetées, appelées énumérations. Par exemple :

enum 
Tree { Feuille , Noeud ( i64 , Boîte < Arbre > , Boîte < Arbre > ) }

Il permet également de faire des matching sur les unions :

laissez arbre = Arbre :: Nœud ( 2 , Boîte :: nouveau ( Arbre :: Nœud ( 0 , Boîte :: nouveau ( Arbre :: Feuille ), Boîte :: nouveau ( Arbre :: Feuille ))), Boîte :: nouveau ( Arbre :: Nœud ( 3 , Boîte :: nouveau ( Arbre :: Feuille ), Boîte :: nouveau ( Arbre :: Nœud ( 4 , Boîte :: nouveau ( Arbre :: Feuille ), Boîte :: nouveau ( Arbre :: Feuille ))))) );
fn 
add_values ​​( arbre : Arbre ) -> i64 
{ 
correspondance arbre { Arbre :: Nœud ( v , a , b ) => v + add_values ​​( * a ) + add_values ​​( * b ), Arbre :: Feuille => 0 } }
assert_eq! ( add_values ( arbre ), 9 );

Le modèle de gestion des erreurs de Rust s'appuie largement sur ces unions étiquetées, en particulier le Option<T>type, qui est soit Noneou Some(T), et le Result<T, E>type, qui est soit Ok(T)ou Err(E).

Swift offre également un support substantiel pour les unions étiquetées via des énumérations. Par exemple :

enum 
Tree 
{ 
case 
feuille 
indirecte 
case 
noeud ( Int , 
Tree , 
Tree ) 
}
laissez 
arbre 
= 
Arbre . nœud ( 
2 , 
. nœud ( 0 , 
. feuille , 
. feuille ), 
. nœud ( 3 , 
. feuille , 
. nœud ( 4 , 
. feuille , 
. feuille )) 
)
func 
add_values ( _tree 
: Arbre ) - > Int { switch tree { case let.node ( v , a , b ) : return v + add_values ( a ) + add_values ( b )​
cas 
. feuille : 
retour 
0 
} 
}
assert ( add_values ( arbre ) 
== 
9 )

Avec TypeScript, il est également possible de créer des unions étiquetées. Par exemple :

interface Feuille { genre : "feuille" ; }
interface Node { kind : "node" ; value : number ; left : Tree ; right : Tree ; }
type Arbre = Feuille | Noeud
const root : Tree = { kind : "node" , value : 5 , left : { kind : "node" , value : 1 , left : { kind : "leaf" }, right : { kind : "leaf" } }, right : { kind : "node" , value : 3 , left : { kind : "leaf" }, right : { kind : "node" , value : 4 , left : { kind : "leaf" }, right : { kind : "leaf" } } } }
fonction visite ( arbre : arbre ) { commutateur ( arbre . genre ) { cas "feuille" : pause cas "nœud" : console . log ( arbre . valeur ) visite ( arbre . gauche ) visite ( arbre . droite ) pause } }

Python 3.9 introduit la prise en charge des annotations de typage qui peuvent être utilisées pour définir un type d'union étiqueté (PEP-593 ) :

Devise 
= 
Annoté [ 
TypedDict ( 'Devise' , 
{ 'dollars' : 
float , 
'livres' : 
float }, 
total = False ), 
TaggedUnion , 
]

C++17 introduit std::variant et constexpr si

en utilisant Tree = std :: variant < struct Leaf , struct Node > ;
struct Leaf { std :: string value ; }; struct Node { Tree * left = nullptr ; Tree * right = nullptr ; };
struct Transverser { template < typename T > void operator ()( T && v ) { if constexpr ( std :: is_same_v < T , Leaf &> ) { std :: cout << v . value << " " ; } else if constexpr ( std :: is_same_v < T , Node &> ) { if ( v . left != nullptr ) std :: visit ( Transverser {}, * v . left );
if ( v . right != nullptr ) std :: visit ( Transverser {}, * v . right ); } else { // L'expression !sizeof(T) est toujours fausse static_assert ( ! sizeof ( T ), "visiteur non-exhaustif !" ); }; } }; /*Arbre forêt = ...;  std::visit(Transverser{}, forest);*/

Dans une hiérarchie de classes typique en programmation orientée objet , chaque sous-classe peut encapsuler des données propres à cette classe. Les métadonnées utilisées pour effectuer la recherche de méthode virtuelle (par exemple, le pointeur vtable de l'objet dans la plupart des implémentations C++) identifient la sous-classe et agissent donc efficacement comme une balise identifiant les données stockées par l'instance (voir RTTI ). Le constructeur d'un objet définit cette balise, et elle reste constante tout au long de la durée de vie de l'objet.

Néanmoins, une hiérarchie de classes implique un véritable polymorphisme de sous-type . Elle peut être étendue en créant d'autres sous-classes du même type de base, qui ne pourraient pas être gérées correctement dans un modèle de balise/répartition. Par conséquent, il n'est généralement pas possible d'effectuer une analyse de cas ou une répartition sur la « balise » d'un sous-objet comme on le ferait pour les unions étiquetées. Certains langages tels que Scala permettent de « sceller » les classes de base et d'unifier les unions étiquetées avec des classes de base scellées.