En informática , una unión etiquetado , también llamado una variante , registro variante , tipo de elección , la unión discriminada , unión de la desunión , de tipo suma o co-producto , es una estructura de datos se utiliza para mantener un valor que podría asumir varias diferentes, pero fijas, los tipos . Solo uno de los tipos puede estar en uso a la vez, y una etiquetaEl campo indica explícitamente cuál está en uso. Se puede pensar en 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 el valor en sí, 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 una a la vez.
Descripción
Las uniones etiquetadas son más importantes en lenguajes 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 se manejen siempre, evitando muchos tipos de errores. Sin embargo, pueden construirse en casi cualquier idioma y son mucho más seguros que los sindicatos sin etiquetar, a menudo llamados simplemente sindicatos, que son similares pero no llevan un registro explícito de qué miembro del sindicato está actualmente en uso.
Las uniones etiquetadas suelen ir acompañadas del concepto de un constructor de tipos , que es similar pero no igual al constructor de una clase. Los constructores de tipos producen un tipo de unión etiquetado, dado el tipo de etiqueta inicial y el tipo correspondiente.
Matemáticamente, las uniones etiquetadas corresponden a uniones disjuntas o discriminadas , generalmente escritas con +. Teniendo en cuenta un elemento de una unión disjunta A + B , es posible determinar si procedía de A o B . Si un elemento mentiras tanto, habrá dos copias efectivamente distintas del valor en A + B , uno de A y uno de B .
En la teoría de tipos , una unión etiquetada se denomina tipo de suma . Los tipos de suma son el dual de los tipos de productos . Notaciones varían, pero por lo general el tipo de suma A + B viene con dos formas de introducción ( inyecciones ) inj 1 : A → A + B y inj 2 : B → A + B . La forma de eliminación es el análisis de caso, conocido como la coincidencia de patrones en estilo ML lenguajes de programación: si e tiene tipo A + B y e 1 y e 2 tener Tipobajo los supuestos x : A e y : B respectivamente, entonces el término tiene tipo . El tipo de suma corresponde a la disyunción lógica intuicionista bajo la correspondencia Curry-Howard .
Un tipo enumerado puede verse como un caso degenerado: una unión etiquetada de tipos de unidades . Corresponde a un conjunto de constructores nulares 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, incluida la cuerda , 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 , etc., generalmente se implementan usando 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 no etiquetada es que todos los accesos son seguros y el compilador puede incluso comprobar que se gestionan todos los casos. Las uniones no etiquetadas dependen de la lógica del programa para identificar correctamente el campo activo actualmente, lo que puede resultar en 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 una pequeña cantidad de alternativas, la etiqueta a menudo se puede comprimir en 2 o 3 bits siempre que se pueda encontrar espacio, pero a veces incluso estos bits no 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 de esto 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, llamadas conversiones de reinterpretación en C ++. Las uniones etiquetadas no están diseñadas para este propósito; 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 cualquier otro tipo y, a menudo, se proporciona una forma de probar el tipo real de un valor del tipo universal. A veces se les 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 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 una 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 usan para manejar la ocurrencia de resultados excepcionales. A menudo, estas etiquetas se doblan en el tipo como "valores reservados", y su aparición no se comprueba de forma coherente: 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:
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 :
Ejemplos de
Digamos que queremos construir un árbol binario de enteros. En ML, haríamos esto creando un tipo de datos como este:
árbol de tipo 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 como lo haría un valor nulo en 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 de seguridad de tipos que, digamos, cuente el número de nodos en el árbol:
fun countNodes ( Leaf ) = 0 | countNodes ( Node ( int , izquierda , derecha )) = 1 + countNodes ( izquierda ) + countNodes ( derecha )
Cronología del soporte lingüístico
1960
En ALGOL 68 , las uniones etiquetadas se denominan modos unidos , la etiqueta está implícita y la case
construcción se utiliza para determinar qué campo está etiquetado:
mode node = union (real, int, compl, string);
Ejemplo de uso union
case
de node
:
nodo n: = "1234"; caso n en ( r real ): print (("real:", r)), ( int i): print (("int:", i)), ( compl c): print (("compl:", c)), ( String s): print (( "cadena", s)) fuera de impresión (( "?:", n)) esac
1970 y 1980
Aunque principalmente solo los lenguajes funcionales como ML (de la década de 1970) y Haskell (de la década de 1990) otorgan un papel central a los sindicatos etiquetados y tienen el poder de verificar que se manejen todos los casos, otros lenguajes también admiten los sindicatos etiquetados. Sin embargo, en la práctica, pueden ser menos eficientes en lenguajes no funcionales debido a las optimizaciones habilitadas por los compiladores de lenguajes funcionales que pueden eliminar verificaciones de etiquetas explícitas y evitar el almacenamiento explícito de etiquetas . [ cita requerida ]
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 los valores de etiqueta se especifiquen, como en este ejemplo de Pascal:
tipo shapeKind = ( cuadrado , rectángulo , círculo ) ; forma = centro de registro x : entero ; centery : entero ; tipo de caso : forma Tipo de cuadrado : ( lado : entero ) ; rectángulo : ( largo , alto : entero ) ; círculo : ( radio : entero ) ; terminar ;
y este Ada equivalente:
type Shape_Kind es ( Cuadrado , Rectángulo , Círculo ); tipo Shape ( Tipo : Shape_Kind ) es el registro Center_X : Integer ; Center_Y : Entero ; tipo de caso es cuando Cuadrado => Lado : Entero ; cuando Rectángulo => Longitud , Altura : Entero ; cuando Círculo => Radio : Entero ; caso final ; registro final ; - Cualquier intento de acceder a un miembro cuya existencia depende - de un valor particular 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 usando una disciplina de acceso estricta donde la etiqueta siempre está marcada:
enum ShapeKind { Cuadrado , Rectángulo , Círculo };estructura Forma { int centerx ; int centery ; enum ShapeKind kind ; union { estructura { int lado ; }; / * Cuadrado * / struct { int longitud , altura ; }; / * Rectángulo * / struct { int radio ; }; / * Círculo * / }; };int getSquareSide ( estructura Forma * s ) { aseverar ( s -> tipo == Cuadrado ); return s -> lado ; }void setSquareSide ( struct Shape * s , int side ) { s -> kind = Square ; s -> lado = lado ; }/* y así */
Siempre que a los campos de unión solo se acceda a través de las funciones, los accesos serán seguros y correctos. El mismo enfoque se puede utilizar para etiquetas codificadas; simplemente decodificamos la etiqueta y luego la revisamos en cada acceso. Si le preocupa la ineficacia 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 puede compararse con el option
tipo en ML o el Maybe
tipo en Haskell, y puede verse 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.
Desafortunadamente, los compiladores de C no verifican que siempre se maneje el caso nulo, y esta es una fuente de errores particularmente frecuente 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 incorporado 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 ha demostrado que era posible implementar una unión etiquetada segura como una biblioteca en C ++, visitable mediante objetos de función.
estructura de visualización : boost :: static_visitor < void > { void operator () ( int i ) { std :: cout << "Es un int, con valor" << i << std :: endl ; } operador vacío () ( const std :: string & s ) { std :: cout << "Es una cadena, con valor" << s << std :: endl ; } };boost :: variant < 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 caja de árbol La hoja se extiende Clase de caja de á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 )))
Debido a que la jerarquía de clases está sellada, el compilador puede verificar que todos los casos se manejen en una coincidencia de patrón:
coincidencia de árbol { case Node ( x , _ , _ ) => println ( "valor del 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 subtipos:
clase abstracta sellada Forma ( centerX : Int , centerY : Int ) clase de caja Cuadrado ( lado : Int , centerX : Int , centerY : Int ) se extiende Shape ( centerX , centerY ) clase de caja Rectángulo ( longitud : Int , altura : Int , centerX : Int , centerY : Int ) extiende Shape ( centerX , centerY ) clase de caja Circle ( radio : Int , centerX : Int , centerY : Int ) extiende Shape ( centerX , centerY )
F # ha discriminado a los sindicatos:
tipo Árbol = | Hoja | Nodo de valor : int * izquierda : árbol * derecha : árbollet tree = Node ( 5 , Node ( 1 , Leaf , Leaf ), Node ( 3 , Leaf , Node ( 4 , Leaf , Leaf )))
Debido a que los casos definidos son exhaustivos, el compilador puede verificar que todos los casos se manejen en una coincidencia de patrón:
emparejar árbol con | Node ( 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]
enum Color { Red ; Verde ; azul ; Rgb ( r : Int , g : Int , b : Int ); }
Estos se pueden combinar mediante una expresión de cambio:
switch ( color ) { case Red : trace ( "El color era rojo" ); caso Verde : traza ( "El color era verde" ); caso Azul : traza ( "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 tipo de caso : 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, que se ven aquí como implementadas por el paquete patty :
importar empanadaproc `~` [ A ] ( a : A ): ref A = nuevo ( resultado ) resultado [] = a Lista de variantes [ A ] : cero Contras ( x : A , xs : lista de referencias [ A ] )proc listHelper [ A ] ( xs : seq [ A ] ): Lista [ A ] = si xs . len == 0 : Nil [ A ] () else : Contras ( xs [ 0 ] , ~ listHelper ( xs [ 1 .. xs . alto ] ))proc list [ A ] ( xs : varargs [ A ] ): List [ A ] = listHelper ( @ xs )proc sum ( xs : List [ int ] ): int = ( block : match xs : Nil : 0 Cons ( y , ys ): y + sum ( ys [] ) ) suma de eco ( lista ( 1 , 2 , 3 , 4 , 5 ))
2010
El lenguaje Rust tiene un amplio soporte para uniones etiquetadas, llamadas enumeraciones. [4] Por ejemplo:
enum Tree { hoja , Nodo ( i64 , Caja < Árbol > , Caja < Árbol > ) }
También permite emparejar en uniones:
dejar á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 { árbol de coincidencias { Árbol :: Nodo ( v , a , b ) => v + agregar_valores ( * a ) + agregar_valores ( * b ), Árbol :: Hoja => 0 }}asert_eq! ( agregar_valores ( árbol ), 9 );
El modelo de manejo de errores de Rust se basa ampliamente en estas uniones etiquetadas, especialmente el Option
tipo, que es None
o Some(T)
, y el Result
tipo, que es Ok(T)
o Err(E)
. [5]
Swift también tiene un apoyo sustancial para los sindicatos etiquetados a través de enumeraciones. [6] Por ejemplo:
enum Tree { case leaf nodo de caso indirecto ( Int , Tree , Tree ) } let tree = Árbol . nodo ( 2 , . nodo ( 0 , . hoja , . hoja ), . nodo ( 3 , . hoja , . nodo ( 4 , . hoja , . hoja )) )func add_values ( _ árbol : Árbol ) -> Int { árbol de cambio { caso let . nodo ( v , a , b ): devuelve v + agregar_valores ( a ) + agregar_valores ( b ) caso . hoja : retorno 0 } }afirmar ( agregar_valores ( árbol ) == 9 )
Con TypeScript también es posible crear uniones etiquetadas. Por ejemplo:
interfaz Hoja { tipo : "hoja" ; valor : cadena ; }interfaz Nodo { tipo : "nodo" ; izquierda : árbol ; derecha : árbol ; }tipo Árbol = Hoja | Nodofunción visita ( árbol : Árbol ) { interruptor ( árbol . tipo ) { caso "hoja" : consola . log ( árbol . valor ) caso de ruptura "nodo" : visita ( árbol . izquierda ) visita ( árbol . derecha ) romper } }
Jerarquías de clases como uniones etiquetadas
En una jerarquía de clases típica en la 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 como una etiqueta que identifica los datos particulares almacenados por la instancia (ver 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 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, generalmente no es posible realizar análisis de casos o enviar 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 unifican uniones etiquetadas con clases base selladas.
Ver también
- Discriminator , el tipo de etiqueta para sindicatos discriminados en CORBA
- Tipo de variante
Referencias
- ^ http://cyclone.thelanguage.org/wiki/Tagged%20Unions
- ^ "Uso de Enums - Haxe - El kit de herramientas multiplataforma" . Fundación Haxe.
- ^ "Manual de Nim" . nim-lang.org . Consultado el 23 de enero de 2020 .
- ^ "El lenguaje de programación Rust" . Mozilla.
- ^ "Moho con el ejemplo" . Mozilla.
- ^ "Enumeraciones - El lenguaje de programación Swift (Swift 5.4)" . docs.swift.org . Consultado el 28 de abril de 2021 .
enlaces externos
- boost :: variant es una unión discriminada segura de tipos de C ++
- std.variant es una implementación del tipo de variante en D 2.0