Unión etiquetada

En informática , una unión etiquetada , también llamada variante , registro de variante , tipo de elección , unión discriminada , unión disjunta , tipo de suma o coproducto , es una estructura de datos utilizada para contener un valor que podría adoptar varios tipos diferentes, pero fijos. Solo uno de los tipos puede estar en uso en cualquier momento, y un campo de etiqueta indica explícitamente qué tipo está en uso. Puede considerarse como un tipo que tiene varios "casos", cada uno de los cuales debe manejarse correctamente cuando se manipula ese tipo. Esto es fundamental para definir tipos de datos recursivos, en los que algún componente de un valor puede tener el mismo tipo que ese valor, por ejemplo, al definir un tipo para representar árboles , donde es necesario distinguir subárboles y hojas de múltiples nodos. Al igual que las uniones ordinarias , las uniones etiquetadas pueden ahorrar almacenamiento al superponer áreas de almacenamiento para cada tipo, ya que solo se usa uno a la vez.

Descripción

Las uniones etiquetadas son más importantes en lenguajes de programación funcional como ML y Haskell , donde se denominan tipos de datos (consulte tipo de datos algebraicos ) y el compilador puede verificar que siempre se manejan todos los casos de una unión etiquetada, evitando muchos tipos de errores. Los tipos de suma comprobada en tiempo de compilación también se usan ampliamente en Rust , donde se denominan enum . Sin embargo, se pueden construir en casi cualquier lenguaje de programación y son mucho más seguras que las uniones sin etiquetar, a menudo llamadas simplemente uniones, que son similares pero no rastrean explícitamente qué miembro de una unión está actualmente en uso.

Las uniones etiquetadas suelen ir acompañadas del concepto de constructor , que es similar pero no igual a un constructor de una clase . Un constructor es una función o expresión que produce un valor del tipo de unión etiquetada, dada una etiqueta y un valor del tipo correspondiente.

Matemáticamente, las uniones etiquetadas corresponden a uniones disjuntas o discriminadas , que se escriben generalmente con +. Dado un elemento de una unión disjunta A + B , es posible determinar si proviene de A o de B . Si un elemento se encuentra en ambos, habrá dos copias efectivamente distintas del valor en A + B , una de A y otra de B .

En teoría de tipos , una unión etiquetada se denomina tipo suma . Los tipos suma son el dual de los tipos producto . Las notaciones varían, pero por lo general el tipo suma $A + B$ viene con dos formas de introducción ( inyecciones ) $inj 1 : A \to A + B$ y $inj 2 : B \to A + B$ . La forma de eliminación es el análisis de casos, conocido como coincidencia de patrones en lenguajes de estilo ML : si $e$ tiene tipo $A + B$ y $e 1$ y $e 2$ tienen tipo bajo los supuestos $x$ $:$ $A$ e $y$ $:$ $B$ respectivamente, entonces el término tiene tipo . El tipo suma corresponde a la disyunción lógica intuicionista bajo la correspondencia de Curry-Howard . ${\estilo de visualización \tau}$ ${\mathsf {caso}}\ e\ {\mathsf {de}}\ x\Rightarrow e_{1}\mid y\Rightarrow e_{2}$ ${\estilo de visualización \tau}$

Un tipo enumerado puede considerarse un caso degenerado: una unión etiquetada de tipos unitarios . Corresponde a un conjunto de constructores nulos y puede implementarse como una variable de etiqueta simple, ya que no contiene datos adicionales además del valor de la etiqueta.

Muchas técnicas de programación y estructuras de datos, incluidas rope , la evaluación perezosa , la jerarquía de clases (ver más abajo), la aritmética de precisión arbitraria , la codificación CDR , el bit de indirección y otros tipos de punteros etiquetados , generalmente se implementan utilizando algún tipo de unión etiquetada.

Una unión etiquetada puede considerarse como el tipo más simple de formato de datos autodescriptivos . La etiqueta de la unión etiquetada puede considerarse como el tipo más simple de metadatos .

Ventajas y desventajas

La principal ventaja de una unión etiquetada sobre una unión sin etiquetar es que todos los accesos son seguros y el compilador puede incluso comprobar que se manejan todos los casos. Las uniones sin etiquetar dependen de la lógica del programa para identificar correctamente el campo activo en ese momento, lo que puede generar un comportamiento extraño y errores difíciles de encontrar si esa lógica falla.

La principal ventaja de una unión etiquetada sobre un registro simple que contiene un campo para cada tipo es que ahorra almacenamiento al superponer el almacenamiento para todos los tipos. Algunas implementaciones reservan suficiente almacenamiento para el tipo más grande, mientras que otras ajustan dinámicamente el tamaño de un valor de unión etiquetada según sea necesario. Cuando el valor es inmutable , es sencillo asignar tanto almacenamiento como sea necesario.

La principal desventaja de las uniones etiquetadas es que la etiqueta ocupa espacio. Dado que normalmente hay un pequeño número de alternativas, la etiqueta a menudo se puede comprimir en 2 o 3 bits donde se pueda encontrar espacio, pero a veces incluso estos bits no están disponibles. En este caso, una alternativa útil puede ser las etiquetas plegadas , calculadas o codificadas , donde el valor de la etiqueta se calcula dinámicamente a partir del contenido del campo de unión. Ejemplos comunes son el uso de valores reservados , donde, por ejemplo, una función que devuelve un número positivo puede devolver -1 para indicar un fallo, y valores centinela , que se utilizan con mayor frecuencia en punteros etiquetados .

En ocasiones, las uniones sin etiquetar se utilizan para realizar conversiones a nivel de bits entre tipos, llamadas conversiones de reinterpretación en C++. Las uniones etiquetadas no están pensadas para este fin; normalmente, se asigna un nuevo valor cada vez que se cambia la etiqueta.

Muchos lenguajes admiten, hasta cierto punto, un tipo de datos universal , que es un tipo que incluye todos los valores de todos los demás tipos, y a menudo se proporciona una forma de probar el tipo real de un valor del tipo universal. A veces se los denomina variantes . Si bien los tipos de datos universales son comparables a las uniones etiquetadas en su definición formal, las uniones etiquetadas típicas incluyen una cantidad relativamente pequeña de casos, y estos casos forman diferentes formas de expresar un único concepto coherente, como un nodo o una instrucción de estructura de datos. Además, existe la expectativa de que se tratará cada caso posible de una unión etiquetada cuando se use. Los valores de un tipo de datos universal no están relacionados y no hay una forma factible de tratarlos todos.

Al igual que los tipos de opciones y el manejo de excepciones , las uniones etiquetadas se utilizan a veces para manejar la ocurrencia de resultados excepcionales. A menudo, estas etiquetas se incorporan al tipo como valores reservados y su ocurrencia no se verifica de manera consistente: esta es una fuente bastante común de errores de programación. Este uso de las uniones etiquetadas se puede formalizar como una mónada con las siguientes funciones:

{\text{retorno}}\colon A\to \left(A+E\right)=a\mapsto {\text{valor}}\,a

{\text{bind}}\colon \left(A+E\right)\to \left(A\to \left(B+E\right)\right)\to \left(B+E\right)=a\mapsto f\mapsto {\begin{cases}{\text{err}}\,e&{\text{si}}\ a={\text{err}}\,e\\f\,a'&{\text{si}}\ a={\text{valor}}\,a'\end{cases}}

donde "value" y "err" son los constructores del tipo union, A y B son tipos de resultados válidos y E es el tipo de condiciones de error. Alternativamente, la misma mónada puede describirse mediante return y dos funciones adicionales, fmap y join :

{\text{fmap}}\colon (A\a B)\a \left(\left(A+E\right)\a \left(B+E\right)\right)=f\mapsto a\mapsto {\begin{cases}{\text{err}}\,e&{\text{si}}\ a={\text{err}}\,e\\{\text{valor}}\,{\text{(}}\,f\,a'\,{\text{)}}&{\text{si}}\ a={\text{valor}}\,a'\end{cases}}

{\text{join}}\colon ((A+E)+E)\to (A+E)=a\mapsto {\begin{cases}{\text{err}}\,e&{\mbox{si}}\ a={\text{err}}\,e\\{\text{err}}\,e&{\text{si}}\ a={\text{valor}}\,{\text{(err}}\,e\,{\text{)}}\\{\text{valor}}\,a'&{\text{si}}\ a={\text{valor}}\,{\text{(valor}}\,a'\,{\text{)}}\end{cases}}

Ejemplos

Digamos que queremos construir un árbol binario de números enteros. En ML, lo haríamos creando un tipo de datos como este:

tipo de datos  árbol  =  Hoja  |  Nodo  de  ( int  *  árbol  *  árbol )

Esta es una unión etiquetada con dos casos: uno, la hoja, se utiliza para terminar una ruta del árbol y funciona de forma muy similar a como lo haría un valor nulo en lenguajes imperativos. La otra rama contiene un nodo, que contiene un entero y un subárbol izquierdo y derecho. Leaf y Node son los constructores, que nos permiten producir un árbol particular, como:

Nodo ( 5 ,  Nodo ( 1 ,  Hoja ,  Hoja ),  Nodo ( 3 ,  Hoja ,  Nodo ( 4 ,  Hoja ,  Hoja )))

que corresponde a este árbol:

Ahora podemos escribir fácilmente una función de tipos seguros que, por ejemplo, cuente el número de nodos en el árbol:

fun  countNodes ( Hoja )  =  0  |  countNodes ( Nodo ( int ,  izquierda ,  derecha ))  =  1  +  countNodes ( izquierda )  +  countNodes ( derecha )

Cronología del soporte lingüístico

Década de 1960

En ALGOL 68 , las uniones etiquetadas se denominan modos unidos , la etiqueta es implícita y la caseconstrucción se utiliza para determinar qué campo está etiquetado:

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

Ejemplo de uso de union caseof node:

nodo n := "1234"; caso n en ( r real ): print(("real:", r)), ( int i): imprimir(("int:", i)), ( compl c): imprimir(("compl:", c)), ( cadena s): print(("cadena:", s)) out print(("?:", n)) esac

Década de 1970 y 1980

Los lenguajes de programación funcional como ML (de la década de 1970) y Haskell (de la década de 1990) otorgan un papel central a las uniones etiquetadas y tienen la capacidad de verificar que se gestionen todos los casos. Algunos otros lenguajes también admiten uniones etiquetadas.

Pascal , Ada y Modula-2 los llaman registros variantes ( tipo formalmente discriminado en Ada) y requieren que el campo de etiqueta se cree manualmente y que se especifiquen los valores de etiqueta, como en este ejemplo de Pascal:

tipo formaKind = ( cuadrado , rectángulo , círculo ) ; forma = registro centrox : entero ; centroy : entero ; caso tipo : formaKind de cuadrado : ( lado : entero ) ; rectángulo : ( ancho , alto : entero ) ; círculo : ( radio : entero ) ; fin ;

y este equivalente de Ada:

tipo  Shape_Kind  es  ( Cuadrado ,  Rectángulo ,  Círculo ); tipo  Shape  ( Tipo  : Shape_Kind )  es  registro  Centro_X  :  Entero ;  Centro_Y  :  Entero ;  caso  Tipo  es  cuando  Cuadrado  =>  Lado  :  Entero ;  cuando  Rectángulo  =>  Ancho ,  Alto  :  Entero ;  cuando  Círculo  =>  Radio  :  Entero ;  fin  caso ; fin registro ;-- Cualquier intento de acceder a un miembro cuya existencia depende -- de un cierto valor del discriminante, mientras que el -- discriminante no es el esperado, genera un error.

En C y C++ , se puede crear una unión etiquetada a partir de uniones no etiquetadas utilizando una disciplina de acceso estricta donde la etiqueta siempre se verifica:

enumeración ShapeKind { Cuadrado , Rectángulo , Círculo };      struct Forma { int centrox ; int centroy ; enumeración FormaKind tipo ; unión { struct { int lado ; }; /* Cuadrado */ struct { int ancho , alto ; }; /* Rectángulo */ struct { int radio ; }; /* Círculo */ }; };                               int getSquareSide ( struct Forma * s ) { assert ( s -> tipo == Cuadrado ); return s -> lado ; }         void setSquareSide ( struct Forma * s , int lado ) { s -> tipo = Cuadrado ; s -> lado = lado ; }            /* etcétera */

Mientras solo se acceda a los campos de unión a través de las funciones, los accesos serán seguros y correctos. Se puede utilizar el mismo enfoque para las etiquetas codificadas; simplemente decodificamos la etiqueta y luego la verificamos en cada acceso. Si la ineficiencia de estas verificaciones de etiquetas es un problema, es posible que se eliminen automáticamente en la versión final.

C y C++ también tienen soporte de lenguaje para una unión etiquetada en particular: el puntero posiblemente nulo . Esto se puede comparar con el optiontipo en ML o el Maybetipo en Haskell, y se puede ver como un puntero etiquetado : una unión etiquetada (con una etiqueta codificada) de dos tipos:

Punteros válidos,
Un tipo de puntero nulo con un solo valor, null, que indica una condición excepcional.

Lamentablemente, los compiladores de C no verifican que el caso nulo se gestione siempre. Esta es una fuente de errores particularmente común en el código C, ya que existe una tendencia a ignorar los casos excepcionales.

Década de 2000

Un dialecto avanzado de C, llamado Cyclone , tiene un amplio soporte integrado para uniones etiquetadas. ^[1]

Los tipos de enumeración en los lenguajes Rust , Haxe y Swift también funcionan como uniones etiquetadas.

La biblioteca de variantes de Boost C++ Libraries demostró que era posible implementar una unión etiquetada segura como una biblioteca en C++, visitable mediante objetos de función.

struct display : boost :: static_visitor < void > { void operator ()( int i ) { std :: cout << "Es un int, con valor " << i << std :: endl ; }                operador void () ( const std :: string & s ) { std :: cout << "Es una cadena, con valor " << s << std :: endl ; } };            boost :: variante < int , std :: string > v = 42 ; boost :: apply_visitor ( display (), v );     boost :: variant < int , std :: string > v = "hola mundo" ; boost :: apply_visitor ( display (), v );

Scala tiene clases de casos:

clase abstracta sellada Objeto de caso Árbol Hoja extiende la clase de caso Árbol Nodo ( valor : Int , izquierda : Árbol , derecha : Árbol ) extiende Árbol                val árbol = Nodo ( 5 , Nodo ( 1 , Hoja , Hoja ), Nodo ( 3 , Hoja , Nodo ( 4 , Hoja , Hoja )))

Como la jerarquía de clases está sellada, el compilador puede verificar que todos los casos se manejen en una coincidencia de patrones:

coincidencia de árbol { caso Nodo ( x , _ , _ ) => println ( "valor del nodo de nivel superior: " + x ) caso Hoja => println ( "el nodo de nivel superior es una hoja" ) }

Las clases de caso de Scala también permiten la reutilización a través de subtipos:

clase abstracta sellada Forma ( centroX : Int , centroY : Int ) clase de caso Cuadrado ( lado : Int , centroX : Int , centroY : Int ) extiende Forma ( centroX , centroY ) clase de caso Rectángulo ( longitud : Int , altura : Int , centroX : Int , centroY : Int ) extiende Forma ( centroX , centroY ) clase de caso Círculo ( radio : Int , centroX : Int , centroY : Int ) extiende Forma ( centroX , centroY )

F# tiene uniones discriminadas:

tipo Árbol = | Hoja | Nodo de valor : int * izquierda : Árbol * derecha : Árbol               sea árbol = Nodo ( 5 , Nodo ( 1 , Hoja , Hoja ), Nodo ( 3 , Hoja , Nodo ( 4 , Hoja , Hoja )))

Como los casos definidos son exhaustivos, el compilador puede verificar que todos los casos se manejen en una coincidencia de patrones:

árbol de coincidencias con | Nodo ( x , _, _) -> printfn "valor del nodo de nivel superior: %i" x | Hoja -> printfn "el nodo de nivel superior es una hoja"

Las enumeraciones de Haxe también funcionan como uniones etiquetadas: ^[2]

enumeración Color { Rojo ; Verde ; Azul ; Rgb ( r : Int , g : Int , b : Int ); }

Estos se pueden hacer coincidir usando una expresión de cambio:

switch ( color ) { case Rojo : trace ( "El color era rojo" ); case Verde : trace ( "El color era verde" ); case Azul : trace ( "El color era azul" ); case RGB ( r , g , b ): trace ( "El color tenía un valor rojo de " + r ); }

Nim tiene variantes de objeto ^[3] similares en declaración a las de Pascal y Ada:

tipo ShapeKind = enumeración skSquare , skRectangle , skCircle Forma = objeto centerX , centerY : int caso tipo : ShapeKind de skSquare : lado : int de skRectangle : longitud , altura : int de skCircle : radio : int

Las macros se pueden utilizar para emular la coincidencia de patrones o para crear sintaxis simplificada para declarar variantes de objetos, como se ve aquí tal como las implementa el paquete patty:

hamburguesa de importación proc `~` [ A ] ( a : A ): ref A = new ( resultado ) resultado [] = a         variante Lista [ A ] : Nil Cons ( x : A , xs : ref Lista [ A ] )       proc listHelper [ A ] ( xs : seq [ A ] ) : Lista [ A ] = si xs.len == 0 : Nil [ A ] ( ) de lo contrario : Cons ( xs [ 0 ] , ~ listHelper ( xs [ 1..xs.high ] ) )              lista de procedimientos [ A ] ( xs : varargs [ A ] ): Lista [ A ] = listHelper ( @ xs )     proc suma ( xs : Lista [ int ] ): int = ( bloque : coincidencia xs : Nil : 0 Cons ( y , ys ): y + suma ( ys [] ) )              echo suma ( lista ( 1 , 2 , 3 , 4 , 5 ))

Década de 2010

Se agregan enumeraciones en Scala 3, ^[4] lo que nos permite reescribir los ejemplos anteriores de Scala de manera más concisa:

enumeración Árbol [ + T ]: caso Hoja caso Nodo ( x : Int , izquierda : Árbol [ T ], derecha : Árbol [ T ])          enumeración Forma ( centroX : Int , centroY : Int ): caso Cuadrado ( lado : Int , centroX : Int , centroY : Int ) extiende Forma ( centroY , centroX ) caso Rectángulo ( longitud : Int , altura : Int , centroX : Int , centroY : Int ) extiende Forma ( centroX , centroY ) caso Círculo ( radio : Int , centroX : Int , centroY : Int ) extiende Forma ( centroX , centroY )

El lenguaje Rust tiene un amplio soporte para uniones etiquetadas, llamadas enumeraciones. ^[5] Por ejemplo:

enumeración  Árbol { Hoja , Nodo ( i64 , Caja < Árbol > , Caja < Árbol > ) }

También permite la coincidencia en uniones:

sea árbol = Árbol :: Nodo ( 2 , Caja :: nuevo ( Árbol :: Nodo ( 0 , Caja :: nuevo ( Árbol :: Hoja ), Caja :: nuevo ( Árbol :: Hoja ))), Caja :: nuevo ( Árbol :: Nodo ( 3 , Caja :: nuevo ( Árbol :: Hoja ), Caja :: nuevo ( Árbol :: Nodo ( 4 , Caja :: nuevo ( Árbol :: Hoja ), Caja :: nuevo ( Árbol :: Hoja ))))) );            fn  add_values ( árbol : Árbol )  -> i64  { match árbol { Árbol :: Nodo ( v , a , b ) => v + add_values ( * a ) + add_values ( * b ), Árbol :: Hoja => 0 } }                assert_eq! ( add_values ( arbol ), 9 );

El modelo de manejo de errores de Rust depende en gran medida de estas uniones etiquetadas, especialmente el Option<T>tipo, que es Noneo Some(T), y el Result<T, E>tipo, que es Ok(T)o Err(E). ^[6]

Swift también tiene un soporte sustancial para uniones etiquetadas a través de enumeraciones. ^[7] Por ejemplo:

enumeración  Árbol  {  caso  hoja  caso indirecto  nodo ( Int , Árbol , Árbol ) }   sea  árbol  =  Árbol . nodo (  2 ,  . nodo ( 0 ,  . hoja ,  . hoja ),  . nodo ( 3 ,  . hoja ,  . nodo ( 4 ,  . hoja ,  . hoja )) )func  add_values ( _tree  : Árbol ) - > Int { cambiar árbol { caso let.node ( v , a , b ) : return v + add_values ( a ) + add_values ( b )                   caso  . hoja :  devuelve  0  } }afirmar ( add_values ( árbol )  ==  9 )

Con TypeScript también es posible crear uniones etiquetadas. Por ejemplo:

interfaz Hoja { tipo : "hoja" ; }     interfaz Nodo { tipo : "nodo" ; valor : número ; izquierda : Árbol ; derecha : Árbol ; }           tipo Árbol = Hoja | Nodo     const root : Tree = { kind : "nodo" , valor : 5 , izquierda : { kind : "nodo" , valor : 1 , izquierda : { kind : "hoja" }, derecha : { kind : "hoja" } }, derecha : { kind : "nodo" , valor : 3 , izquierda : { kind : "hoja" }, derecha : { kind : "nodo" , valor : 4 , izquierda : { kind : "hoja" }, derecha : { kind : "hoja" } } } }                                                      función visita ( árbol : Árbol ) { cambiar ( árbol . tipo ) { caso "hoja" : romper caso "nodo" : consola . registro ( árbol . valor ) visita ( árbol . izquierda ) visita ( árbol . derecha ) romper } }

Python 3.9 introduce soporte para anotaciones de tipificación que se pueden usar para definir un tipo de unión etiquetado (PEP-593 ^[8] ):

Moneda  =  Anotado [  TypedDict ( 'Moneda' ,  { 'dólares' :  float ,  'libras' :  float },  total = False ),  TaggedUnion , ]

C++17 introduce std::variant y constexpr si

usando Árbol = std :: variant < struct Hoja , struct Nodo > ;      struct Leaf { std :: string valor ; }; struct Node { Árbol * izquierda = nullptr ; Árbol * derecha = nullptr ; };            struct Transverser { plantilla < nombre_tipo T > void operador () ( T && v ) { si constexpr ( std :: es_mismo_v < T , Hoja &> ) { std :: cout << v . valor << " \n " ; } de lo contrario si constexpr ( std :: es_mismo_v < T , Nodo &> ) { si ( v . izquierda != nullptr ) std :: visita ( Transverser {}, * v . izquierda );                               if ( v . right != nullptr ) std :: visit ( Transverser {}, * v . right ); } else { // La expresión !sizeof(T) siempre es falsa static_assert ( ! sizeof ( T ), "¡visitante no exhaustivo!" ); }; } }; /*Árbol bosque = ...;  std::visit(Transverser{}, bosque);*/

Jerarquías de clases como uniones etiquetadas

En una jerarquía de clases típica en programación orientada a objetos , cada subclase puede encapsular datos exclusivos de esa clase. Los metadatos utilizados para realizar la búsqueda de métodos virtuales (por ejemplo, el puntero de tabla virtual del objeto en la mayoría de las implementaciones de C++) identifican la subclase y, por lo tanto, actúan de manera efectiva como una etiqueta que identifica los datos almacenados por la instancia (consulte RTTI ). El constructor de un objeto establece esta etiqueta y permanece constante durante la vida útil del objeto.

Sin embargo, una jerarquía de clases implica un verdadero polimorfismo de subtipos . Se puede ampliar creando más subclases del mismo tipo base, que no se podrían manejar correctamente con un modelo de etiqueta/envío. Por lo tanto, normalmente no es posible realizar análisis de casos o envíos en la "etiqueta" de un subobjeto como se haría para las uniones etiquetadas. Algunos lenguajes como Scala permiten que las clases base estén "selladas" y unifican las uniones etiquetadas con las clases base selladas.

Véase también

Discriminador , la etiqueta de tipo para sindicatos discriminados en CORBA
Tipo de variante (COM)

Referencias

^ "Ciclón: Sindicatos etiquetados".
^ "Uso de enumeraciones - Haxe - El kit de herramientas multiplataforma". Fundación Haxe.
^ "Manual de Nim". nim-lang.org . Consultado el 23 de enero de 2020 .
^ "Referencia del lenguaje Scala 3: Enumeraciones". El equipo de Scala.
^ "El lenguaje de programación Rust". Mozilla.
^ "El óxido con el ejemplo". Mozilla.
^ "Enumeraciones: el lenguaje de programación Swift (Swift 5.4)". docs.swift.org . Consultado el 28 de abril de 2021 .
^ "PEP 593 - Anotaciones flexibles de funciones y variables". Python.org . Consultado el 20 de junio de 2021 .

Enlaces externos

boost::variant es una unión discriminada de tipos seguros de C++
std.variant es una implementación del tipo variante en D 2.0