Unión etiquetada

En informática , una unión etiquetada , también llamada variante , registro variante , tipo de elección , unión discriminada , unión disjunta , tipo suma o coproducto , es una estructura de datos que se utiliza para contener un valor que podría tomar varios valores diferentes, pero fijos. tipos. Sólo uno de los tipos puede estar en uso a la vez y un campo de etiqueta indica explícitamente qué tipo está en uso. Se puede considerar 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 utiliza una a la vez.

Descripción

Las uniones etiquetadas son más importantes en lenguajes de programación funcionales como ML y Haskell , donde se denominan tipos de datos (ver tipo de datos algebraicos ) y el compilador puede verificar que todos los casos de una unión etiquetada siempre se manejan, evitando muchos tipos de errores. Los tipos de suma verificada en tiempo de compilación también se usan ampliamente en Rust , donde se denominan enum . Sin embargo, pueden construirse 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 al constructor de una clase . Un constructor es una función o expresión que produce un valor del tipo de unión etiquetado, dada una etiqueta y un valor del tipo correspondiente.

Matemáticamente, las uniones etiquetadas corresponden a uniones disjuntas o discriminadas , normalmente escritas usando +. 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 de suma son los tipos duales de productos . Las notaciones varían, pero normalmente el tipo de suma $A + B$ viene con dos formas de introducción ( inyecciones ) $inj 1 : A \to A + B$ e $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 según la correspondencia Curry-Howard . $\tau$ ${\mathsf {caso}}\ e\ {\mathsf {de}}\ x\Rightarrow e_{1}\mid y\Rightarrow e_{2}$ $\tau$

Un tipo enumerado puede verse como un caso degenerado: una unión etiquetada de tipos de unidades . 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 la cuerda , la evaluación diferida , 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 verse como el tipo más simple de formato de datos autodescriptivo . La etiqueta de la unión etiquetada puede verse como el tipo de metadatos más simple .

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 verificar que se manejen todos los casos. Las uniones sin etiquetar dependen de la lógica del programa para identificar correctamente el campo actualmente activo, lo que puede provocar 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 etiquetado 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 siempre que haya espacio, pero a veces ni siquiera estos bits están disponibles. En este caso, una alternativa útil pueden ser 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 falla, y valores centinela , que se usan con mayor frecuencia en punteros etiquetados .

A veces, las uniones sin etiquetar se utilizan para realizar conversiones a nivel de bits entre tipos, lo que se denomina reinterpretación de conversiones en C++. Las uniones etiquetadas no están destinadas a 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 les llama 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 un número relativamente pequeño de casos, y estos casos forman diferentes formas de expresar un único concepto coherente, como un nodo de estructura de datos o una instrucción. Además, existe la expectativa de que todos los casos posibles de unión etiquetada se aborden cuando se utilice. Los valores de un tipo de datos universal no están relacionados y no existe una forma viable de tratarlos todos.

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

{\text{return}}\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{casos}{\text{err}}\,e&{\text{if}}\ a={\text{err}}\,e\\f\, a'&{\text{if}}\ a={\text{valor}}\,a'\end{casos}}

donde "valor" y "err" son los constructores del tipo de unión, 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\to B)\to \left(\left(A+E\right)\to \left(B+E\right)\right)=f\mapsto a\mapsto {\begin{casos}{\text{err}}\,e&{\text{if}}\ a={\text{err}}\,e\\{\text{valor}}\, {\text{(}}\,f\,a'\,{\text{)}}&{\text{if}}\ a={\text{valor}}\,a'\end{casos} }

{\text{unirse}}\colon ((A+E)+E)\to (A+E)=a\mapsto {\begin{casos}{\text{err}}\,e&{\ mbox{if}}\ a={\text{err}}\,e\\{\text{err}}\,e&{\text{if}}\ a={\text{valor}}\,{ \text{(err}}\,e\,{\text{)}}\\{\text{valor}}\,a'&{\text{if}}\ a={\text{valor}} \,{\text{(valor}}\,a'\,{\text{)}}\end{casos}}

Ejemplos

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

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

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

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 con seguridad de tipos que, por ejemplo, cuente el número de nodos en el árbol:

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

Cronología del soporte lingüístico

década de 1960

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

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

Ejemplo de uso para union casede node:

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

Décadas de 1970 y 1980

Los lenguajes de programación funcionales como ML (de los años 1970) y Haskell (de los años 1990) otorgan un papel central a las uniones etiquetadas y tienen el poder de verificar que todos los casos sean manejados. Algunos otros idiomas 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 se especifiquen los valores de etiqueta, como en este ejemplo de Pascal:

tipo formaKind = ( cuadrado , rectángulo , círculo ) ; forma = centro de registrox : entero ; central : entero ; tipo de caso : formaTipo de cuadrado : ( lado : entero ) ; rectángulo : ( ancho , alto : entero ) ; círculo : ( radio : entero ) ; fin ;

y este equivalente de Ada:

el tipo  Shape_Kind  es  ( Cuadrado ,  Rectángulo ,  Círculo ); escriba  Forma  ( Tipo  : Forma_Tipo )  es  el registro  Centro_X  :  Integer ;  Centro_Y  :  Entero ;  case  Tipo  es  cuando  Cuadrado  =>  Lado  :  Entero ;  cuando  Rectángulo  =>  Ancho ,  Alto  :  Entero ;  cuando  Círculo  =>  Radio  :  Entero ;  caso final  ; registro final ;-- Cualquier intento de acceder a un miembro cuya existencia depende -- de un determinado 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 sin etiquetar utilizando una disciplina de acceso estricta donde la etiqueta siempre se verifica:

enum ShapeKind { Cuadrado , Rectángulo , Círculo };      estructura Forma { int centerx ; int centralizado ; enum ShapeKind tipo ; unión { estructura { int lado ; }; /* Cuadrado */ struct { int ancho , alto ; }; /* Rectángulo */ struct { int radio ; }; /* Círculo */ }; };                               int getSquareSide ( estructura Forma * s ) { afirmar ( s -> tipo == Cuadrado ); regresar s -> lado ; }         void setSquareSide ( estructura Forma * s , int lado ) { s -> tipo = Cuadrado ; s -> lado = lado ; }            /* etcétera */

Siempre que 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 etiquetas codificadas; simplemente decodificamos la etiqueta y luego la verificamos en cada acceso. Si le preocupa la ineficiencia de estas comprobaciones de etiquetas, 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:

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

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

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 variante de las bibliotecas Boost C++ demostró que era posible implementar una unión etiquetada segura como una biblioteca en C++, visitable mediante objetos de función.

visualización de estructura : 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 ; } };            impulso :: variante < int , std :: cadena > v = 42 ; impulso :: apply_visitor ( pantalla (), v );     impulso :: variante < int , std :: cadena > v = "hola mundo" ; impulso :: apply_visitor ( display (), v );

Scala tiene clases de casos:

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

Debido a que la jerarquía de clases está sellada, el compilador puede verificar que todos los casos se manejen siguiendo un patrón:

coincidencia de árbol { case Node ( x , _ , _ ) => println ( "valor de nodo de nivel superior: " + x ) case Leaf => println ( "el nodo de nivel superior es una hoja" ) }

Las clases de casos de Scala también permiten la reutilización mediante subtipificación:

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# ha discriminado sindicatos:

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

Debido a que los casos definidos son exhaustivos, el compilador puede verificar que todos los casos se manejen siguiendo un patrón:

combinar árbol con | Nodo ( x , _, _) -> printfn "valor de 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 combinar usando una expresión de cambio:

switch ( color ) { case Red : trace ( "El color era rojo" ); case Green : trace ( "El color era verde" ); case Blue : 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 = enum skSquare , skRectangle , skCircle Shape = objeto centerX , centerY : int case tipo : ShapeKind de skSquare : lado : int de skRectangle : longitud , altura : int de skCircle : radio : int

Las macros se pueden usar para emular la coincidencia de patrones o para crear azúcar sintáctico para declarar variantes de objetos, como se ve aquí implementado por el paquete patty:

importar empanada proc `~` [ A ] ( a : A ): ref A = nuevo ( resultado ) resultado [] = a         Lista de variantes [ A ] : Nil Cons ( x : A , xs : lista ref [ A ] )       proc listHelper [ A ] ( xs : seq [ A ] ): Lista [ A ] = if xs . len == 0 : Nil [ A ] () else : Contras ( xs [ 0 ] , ~ listHelper ( xs [ 1 .. xs . alto ] ))              lista de procesos [ A ] ( xs : varargs [ A ] ): Lista [ A ] = listHelper ( @ xs )     suma de proceso ( xs : Lista [ int ] ): int = ( bloque : coincidencia xs : Nil : 0 Contras ( y , ys ): y + suma ( ys [] ) )              suma de eco ( lista ( 1 , 2 , 3 , 4 , 5 ))

década de 2010

Las enumeraciones se agregan 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 ])          enum 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 la Forma ( centroX , centroY ) case Círculo ( radio : Int , centroX : Int , centroY : Int ) extiende la Forma ( centroX , centroY )

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

enum  Árbol { Hoja , Nodo ( i64 , Caja < Árbol > , Caja < Árbol > ) }

También permite casar sobre uniones:

let árbol = Árbol :: Nodo ( 2 , Cuadro :: nuevo ( Árbol :: Nodo ( 0 , Cuadro :: nuevo ( Árbol :: Hoja ), Cuadro :: nuevo ( Árbol :: Hoja ))), Cuadro :: nuevo ( Árbol :: Nodo ( 3 , Cuadro :: nuevo ( Árbol :: Hoja ), Cuadro :: nuevo ( Árbol :: Nodo ( 4 , Cuadro :: nuevo ( Árbol :: Hoja ), Cuadro :: nuevo ( Árbol :: Hoja ))))) );            fn  add_values ( árbol : Árbol )  -> i64  { árbol de coincidencia { Árbol :: Nodo ( v , a , b ) => v + add_values ( * a ) + add_values ( * b ), Árbol :: Hoja => 0 } }                afirmar_eq! ( add_values ( árbol ), 9 );

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

Swift también cuenta con un apoyo sustancial para los sindicatos etiquetados mediante enumeraciones. ^[7] Por ejemplo:

enum  Tree  {  case  leaf  caso indirecto  nodo ( Int , Tree , Tree ) }   let  árbol  =  Árbol . nodo (  2 ,  . nodo ( 0 ,  . hoja ,  . hoja ),  . nodo ( 3 ,  . hoja ,  . nodo ( 4 ,  . hoja ,  . hoja )) )func  add_values ( _tree  : Tree ) - > Int { switch tree { case let . nodo ( v , a , b ): devolver v + agregar_valores ( a ) + agregar_valores ( b )                   caso  . hoja :  devolver  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     raíz constante : árbol = { tipo : "nodo" , valor : 5 , izquierda : { tipo : "nodo" , valor : 1 , izquierda : { tipo : "hoja" }, derecha : { tipo : "hoja" } }, derecha : { tipo : "nodo" , valor : 3 , izquierda : { tipo : "hoja" }, derecha : { tipo : "nodo" , valor : 4 , izquierda : { tipo : "hoja" }, derecha : { tipo : "hoja" } } } }                                                      función visitar ( árbol : árbol ) { cambiar ( árbol . tipo ) { caso "hoja" : romper caso "nodo" : consola . iniciar sesión ( árbol . valor ) visitar ( árbol . izquierda ) visitar ( árbol . derecha ) romper } }

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

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

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

usando Árbol = std :: variante < estructura Hoja , estructura Nodo > ;      estructura Hoja { std :: valor de cadena ; }; estructura Nodo { Árbol * izquierda = nullptr ; Árbol * derecha = nullptr ; };            struct Transverser { plantilla < nombre de tipo T > operador vacío ()( T && v ) { if constexpr ( std :: is_same_v < T , Leaf &> ) { std :: cout << v . valor << " \n " ; } else if constexpr ( std :: is_same_v < T , Node &> ) { if ( v . left != nullptr ) std :: visit ( Transverser {}, * v . left );                               if ( v . right != nullptr ) std :: visita ( Transverser {}, * v . right ); } else { // La expresión !sizeof(T) siempre es falsa static_assert ( ! sizeof ( T ), "¡visitante no exhaustivo!" ); }; } }; /*Bosque de árboles = ...;  std::visita(Transversor{}, bosque);*/

Jerarquías de clases como sindicatos etiquetados

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 vtable del objeto en la mayoría de las implementaciones de C++) identifican la subclase y, por lo tanto, actúan efectivamente 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 toda la vida del objeto.

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

Ver también

Discriminador , la etiqueta 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 Hax.
^ "Manual de Nim". nim-lang.org . Consultado el 23 de enero de 2020 .
^ "Referencia del lenguaje Scala 3: enumeraciones". El equipo Scala.
^ "El lenguaje de programación Rust". Mozilla.
^ "Ó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 - Función flexible y anotaciones variables". Python.org . Consultado el 20 de junio de 2021 .

enlaces externos

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