В компьютерной науке , в меченого союза , также называется вариант , вариант записи , типа выбора , размеченного объединения , несвязное объединение , типа суммы или копроизведением , является структура данных используется для хранения значения , которые могли бы взять на себя несколько различных, но фиксированные, типы . Одновременно может использоваться только один из типов, а тегполе явно указывает, какой из них используется. Его можно рассматривать как тип, имеющий несколько «случаев», каждый из которых должен обрабатываться правильно при манипулировании этим типом. Это критически важно при определении рекурсивных типов данных, в которых некоторый компонент значения может иметь тот же тип, что и само значение, например, при определении типа для представления деревьев, где необходимо различать многоузловые поддеревья и листья. Как и обычные союзы , помеченные союзы могут экономить память, перекрывая области хранения для каждого типа, поскольку одновременно используется только одна.
Описание
Тегированные объединения наиболее важны в функциональных языках, таких как ML и Haskell , где они называются типами данных (см. Алгебраический тип данных ), и компилятор может проверить, что все случаи тегированного объединения всегда обрабатываются, избегая многих типов ошибок. Однако они могут быть построены практически на любом языке и намного безопаснее, чем немаркированные союзы, часто называемые просто союзами, которые похожи, но не отслеживают явно, какой член союза используется в настоящее время.
Помеченные объединения часто сопровождаются концепцией конструктора типа , который похож, но не то же самое, что конструктор для класса. Конструкторы типов создают помеченный тип объединения, учитывая исходный тип тега и соответствующий тип.
Математически помеченные объединения соответствуют непересекающимся или дискриминированным объединениям , обычно записываемым с использованием +. Учитывая элемент несвязного объединения + B , можно определить , пришел ли он из A или B . Если элемент лежит в обоих, будет два различных эффективно копии значения в A + B , один из А и один из B .
В теории типов объединение с тегами называется типом суммы . Типы Sum являются двумя из видов продукции . Условные обозначения различаются, но , как правило , тип суммы + B поставляется с двумя формами введения ( инъекция ) INJ 1 : A → A + B и инъками 2 : В → + B . Форма исключения - это анализ случая, известный как сопоставление с образцом в языках программирования в стиле ML : если e имеет тип A + B, а e 1 и e 2 имеют типпри предположениях x : A и y : B соответственно, то член имеет тип . Тип суммы соответствует интуиционистской логической дизъюнкции при соответствии Карри – Ховарда .
Перечислимого типа можно рассматривать как вырожденный случай: меченого объединение типов единиц . Он соответствует набору конструкторов с нулевым значением и может быть реализован как простая переменная тега, поскольку не содержит дополнительных данных, кроме значения тега.
Многие методы программирования и структуры данных, включая веревку , ленивое вычисление , иерархию классов (см. Ниже), арифметику произвольной точности , кодирование CDR , бит косвенного обращения и другие виды помеченных указателей и т. Д., Обычно реализуются с использованием своего рода помеченного объединения.
Тегированное объединение можно рассматривать как простейший вид формата данных с самоописанием . Тег помеченного объединения можно рассматривать как простейший вид метаданных .
Преимущества и недостатки
Основное преимущество помеченного объединения перед немаркированным объединением состоит в том, что все обращения безопасны, и компилятор может даже проверить, что все обращения обработаны. Объединения без тегов зависят от логики программы для правильной идентификации текущего активного поля, что может привести к странному поведению и трудно обнаруживаемым ошибкам, если эта логика не работает.
Основное преимущество помеченного объединения по сравнению с простой записью, содержащей поле для каждого типа, состоит в том, что оно экономит память за счет перекрытия хранилища для всех типов. Некоторые реализации резервируют достаточно памяти для самого большого типа, в то время как другие динамически регулируют размер помеченного значения объединения по мере необходимости. Когда значение неизменяемо , просто выделить столько памяти, сколько необходимо.
Основным недостатком помеченных объединений является то, что тег занимает место. Поскольку обычно существует небольшое количество альтернатив, тег часто можно сжать до 2 или 3 бита везде, где можно найти место, но иногда даже эти биты недоступны. В этом случае полезной альтернативой могут быть свернутые , вычисленные или закодированные теги , где значение тега динамически вычисляется из содержимого поля объединения. Типичными примерами этого являются использование зарезервированных значений , где, например, функция, возвращающая положительное число, может возвращать -1, чтобы указать на сбой, и контрольные значения , наиболее часто используемые в тегированных указателях .
Иногда немаркированные объединения используются для выполнения преобразований на битовом уровне между типами, которые в C ++ называются преобразованием типов. Союзы с тегами не предназначены для этой цели; обычно новое значение присваивается при изменении тега.
Многие языки в некоторой степени поддерживают универсальный тип данных , который представляет собой тип, включающий каждое значение любого другого типа, и часто предоставляется способ проверить фактический тип значения универсального типа. Иногда их называют вариантами . В то время как универсальные типы данных сравнимы с помеченными союзами по их формальному определению, типичные помеченные союзы включают относительно небольшое количество случаев, и эти случаи формируют разные способы выражения единой согласованной концепции, такой как узел структуры данных или инструкция. Кроме того, ожидается, что каждый возможный случай помеченного объединения будет рассмотрен при его использовании. Значения универсального типа данных не связаны между собой, и не существует приемлемого способа справиться со всеми ними.
Подобно типам опций и обработке исключений , помеченные объединения иногда используются для обработки возникновения исключительных результатов. Часто эти теги складываются в тип как «зарезервированные значения», и их наличие постоянно не проверяется: это довольно частый источник ошибок программирования. Такое использование помеченных объединений можно формализовать как монаду со следующими функциями:
где «value» и «err» - конструкторы типа объединения, A и B - допустимые типы результатов, а E - тип условий ошибки. В качестве альтернативы ту же монаду можно описать с помощью return и двух дополнительных функций, fmap и join :
Примеры
Допустим, мы хотели построить двоичное дерево целых чисел. В ML мы бы сделали это, создав такой тип данных:
дерево типов данных = Leaf | Узел из ( междунар * дерево * дерево )
Это помеченное объединение с двумя случаями: один, лист, используется для завершения пути в дереве и функционирует так же, как нулевое значение в императивных языках. Другая ветвь содержит узел, который содержит целое число, а также левое и правое поддерево. Leaf и Node - это конструкторы, которые позволяют нам создать конкретное дерево, например:
Узел ( 5 , Узел ( 1 , Лист , Лист ), Узел ( 3 , Лист , Узел ( 4 , Лист , Лист )))
что соответствует этому дереву:
Теперь мы можем легко написать безопасную функцию, которая, скажем, подсчитывает количество узлов в дереве:
fun countNodes ( Leaf ) = 0 | countNodes ( Node ( int , left , right )) = 1 + countNodes ( слева ) + countNodes ( справа )
Хронология языковой поддержки
1960-е
В АЛГОЛе 68 помеченные объединения называются объединенными режимами , тег является неявным, и case
конструкция используется для определения, какое поле помечено:
mode node = union (real, int, compl, string);
Пример union
case
использования node
:
узел n: = "1234"; case n in ( real r): print (("real:", r)), ( int i): print (("int:", i)), ( компл. c): print (("компл .:", c)), ( строка s): print (("строка:", s)) out print (("?:", n)) esac
1970-е и 1980-е годы
Хотя в основном только функциональные языки, такие как ML (с 1970-х) и Haskell (с 1990-х), отводят центральную роль помеченным объединениям и имеют право проверять, обрабатываются ли все случаи, другие языки также поддерживают помеченные союзы. Однако на практике они могут быть менее эффективными в нефункциональных языках из-за оптимизаций, включенных компиляторами функциональных языков, которые могут исключить явные проверки тегов и избежать явного хранения тегов . [ необходима цитата ]
Паскаль , Ада и Модула-2 называют их вариантными записями (формально различаемый тип в Аде) и требуют, чтобы поле тега создавалось вручную и значения тегов указывались, как в этом примере Паскаля:
введите shapeKind = ( квадрат , прямоугольник , круг ) ; shape = record centerx : integer ; центр : целое число ; Случай вид : shapeKind из квадрата : ( сторона : целое число ) ; прямоугольник : ( длина , высота : целое число ) ; круг : ( радиус : целое число ) ; конец ;
и этот эквивалент Ады:
Тип Shape_Kind равен ( Квадрат , Прямоугольник , Круг ); тип Shape ( Kind : Shape_Kind ) - это запись Center_X : Integer ; Center_Y : целое число ; case Kind - это когда Square => Side : Integer ; когда Прямоугольник => Длина , Высота : Целое число ; когда Круг => Радиус : Целое число ; конец корпуса ; конец записи ;- Любая попытка доступа к члену, существование которого зависит - от определенного значения дискриминанта, в то время как - дискриминант не является ожидаемым, вызывает ошибку.
В C и C ++ помеченное объединение может быть создано из немаркированных объединений с использованием строгой дисциплины доступа, при которой тег всегда проверяется:
перечисление ShapeKind { квадрат , прямоугольник , круг };struct Shape { int centerx ; int centery ; перечисление ShapeKind kind ; объединение { структура { int сторона ; }; / * Квадрат * / struct { int length , height ; }; / * Прямоугольник * / struct { int radius ; }; / * Круг * / }; };int getSquareSide ( struct Shape * s ) { assert ( s -> вид == квадрат ); вернуть s -> сторона ; }void setSquareSide ( struct Shape * s , int side ) { s -> kind = Square ; s -> сторона = сторона ; }/* и так далее */
Пока доступ к полям объединения осуществляется только через функции, доступ будет безопасным и правильным. Тот же подход можно использовать для закодированных тегов; мы просто декодируем тег и проверяем его при каждом доступе. Если неэффективность этих проверок тегов вызывает беспокойство, они могут быть автоматически удалены в окончательной версии.
C и C ++ также имеют языковую поддержку для одного конкретного помеченного объединения: возможно нулевого указателя . Это можно сравнить с option
типом в ML или Maybe
типом в Haskell, и его можно рассматривать как помеченный указатель : помеченное объединение (с закодированным тегом) двух типов:
- Действительные указатели,
- Тип нулевого указателя только с одним значением
null
, указывающим на исключительное состояние.
К сожалению, компиляторы C не проверяют, всегда ли обрабатывается нулевой регистр, и это особенно распространенный источник ошибок в коде C, поскольку существует тенденция игнорировать исключительные случаи.
2000-е
Один продвинутый диалект C, называемый Cyclone, имеет обширную встроенную поддержку помеченных объединений. [1]
Типы перечислений в языках Rust , Haxe и Swift также работают как помеченные объединения.
Библиотека вариантов от Boost продемонстрировала возможность реализации безопасного помеченного объединения в виде библиотеки на C ++, доступной с помощью объектов функций.
struct display : boost :: static_visitor < void > { void operator () ( int i ) { std :: cout << "Это int со значением" << i << std :: endl ; } void operator () ( const std :: string & s ) { std :: cout << "Это строка со значением" << s << std :: endl ; } };boost :: variant < int , std :: string > v = 42 ; boost :: apply_visitor ( дисплей (), v );boost :: variant < int , std :: string > v = "привет, мир" ; boost :: apply_visitor ( дисплей (), v );
В Scala есть case-классы:
запечатанный абстрактный класс Tree case object Leaf расширяет Tree case class Node ( значение : Int , слева : Tree , справа : Tree ) расширяет Treeval tree = Узел ( 5 , Узел ( 1 , Лист , Лист ), Узел ( 3 , Лист , Узел ( 4 , Лист , Лист )))
Поскольку иерархия классов запечатана, компилятор может проверить, что все случаи обрабатываются в соответствии с шаблоном:
дерево совпадение { случай Узел ( х , _ , _ ) => Println ( "значение верхнего узла уровня:" + х ) Случай лист => Println ( "узел верхнего уровня является листом" ) }
Классы кейсов Scala также допускают повторное использование посредством выделения подтипов:
запечатанный абстрактный класс Shape ( centerX : Int , centerY : Int ) case class Square ( side : Int , centerX : Int , centerY : Int ) extends Shape ( centerX , centerY ) case class Rectangle ( длина : Int , высота : Int , centerX : Int , centerY : Int ) расширяет Shape ( centerX , centerY ) case class Circle ( radius : Int , centerX : Int , centerY : Int ) расширяет Shape ( centerX , centerY )
F # различает союзы:
тип Tree = | Лист | Узел из значения : INT * осталось : дерево * право : Деревопусть tree = Node ( 5 , Node ( 1 , Leaf , Leaf ), Node ( 3 , Leaf , Node ( 4 , Leaf , Leaf )))
Поскольку определенные случаи являются исчерпывающими, компилятор может проверить, что все случаи обрабатываются в соответствии с шаблоном:
сопрягать дерево с | Узел ( x , _, _) -> printfn "значение узла верхнего уровня:% i" x | Leaf -> printfn "узел верхнего уровня - это лист"
Перечисления Haxe также работают как помеченные объединения: [2]
enum Color { Красный ; Зеленый ; Синий ; Rgb ( r : Int , g : Int , b : Int ); }
Их можно сопоставить с помощью выражения switch:
переключатель ( цвет ) { case Red : trace ( «Цвет был красным» ); case Green : trace ( «Цвет был зеленым» ); case Blue : trace ( «Цвет был синий» ); case Rgb ( r , g , b ): trace ( «Цвет имел значение красного цвета» + r ); }
У Nim есть варианты объектов [3], похожие по объявлению на Pascal и Ada:
type ShapeKind = enum skSquare , skRectangle , skCircle Shape = object centerX , centerY : int case kind : ShapeKind of skSquare : side : int of skRectangle : length , height : int of skCircle : radius : int
Макросы можно использовать для эмуляции сопоставления с образцом или для создания синтаксического сахара для объявления вариантов объекта, как здесь показано в пакете patty :
импортная лепешкаproc `~` [ A ] ( a : A ): ref A = новый ( результат ) результат [] = a список вариантов [ A ] : ноль против ( x : A , xs : ref List [ A ] )proc listHelper [ A ] ( xs : seq [ A ] ): List [ A ] = если xs . len == 0 : Nil [ A ] () else : Cons ( xs [ 0 ] , ~ listHelper ( xs [ 1 .. xs . high ] ))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 [] ) ) сумма эха ( список ( 1 , 2 , 3 , 4 , 5 ))
2010-е
В языке Rust имеется обширная поддержка помеченных объединений, называемых перечислениями. [4] Например:
enum Tree { Leaf , Узел ( i64 , Box < Tree > , Box < Tree > ) }
Это также позволяет подбирать соединения:
пусть tree = Tree :: Node ( 2 , Box :: new ( Tree :: Node ( 0 , Box :: new ( Tree :: Leaf ), Box :: new ( Tree :: Leaf ))), Box :: new ( Tree :: Node ( 3 , Box :: new ( Tree :: Leaf )), Box :: new ( Tree :: Node ( 4 , Box :: new ( Tree :: Leaf ), Box :: new ( Tree :: Leaf ))))) );fn add_values ( tree : Tree ) -> i64 { дерево совпадений { Tree :: Node ( v , a , b ) => v + add_values ( * a ) + add_values ( * b ), Дерево :: Лист => 0 }}assert_eq! ( add_values ( дерево ), 9 );
Модель обработки ошибок Rust в значительной степени опирается на эти помеченные объединения, особенно на Option
тип, который имеет значение либо None
или Some(T)
, и Result
тип, который имеет значение либо Ok(T)
или Err(E)
. [5]
Swift также имеет существенную поддержку помеченных объединений через перечисления. [6] Например:
enum Tree { case лист косвенный case node ( Int , Tree , Tree ) }пусть tree = Дерево . узел ( 2 , . узел ( 0 , . лист , . лист ), . узел ( 3 , . лист , . узел ( 4 , . лист , . лист )) )func add_values ( _ tree : Tree ) -> Int { дерево переключателей { case let . узел ( v , a , b ): вернуть v + add_values ( a ) + add_values ( b ) дело . лист : возврат 0 } }assert ( add_values ( дерево ) == 9 )
С помощью TypeScript можно также создавать помеченные объединения. Например:
интерфейс Leaf { тип : "лист" ; значение : строка ; } узел интерфейса { тип : "узел" ; слева : Дерево ; справа : Дерево ; }тип Дерево = Лист | Узелфункция visit ( tree : Tree ) { switch ( tree . type ) { case "leaf" : console . log ( дерево . значение ) break case "node" : visit ( tree . left ) visit ( tree . right ) break } }
Python 3.9 представляет поддержку ввода аннотаций, которые можно использовать для определения помеченного типа объединения (PEP-593 [7] ):
Currency = Annotated [ TypedDict ( 'Currency' , { 'долларов' : float , 'pounds' : float }, total = False ), TaggedUnion , ]
Иерархии классов как помеченные объединения
В типичной иерархии классов в объектно-ориентированном программировании каждый подкласс может инкапсулировать данные, уникальные для этого класса. Метаданные, используемые для поиска виртуального метода (например, указатель объекта vtable в большинстве реализаций C ++), идентифицируют подкласс и поэтому эффективно действуют как тег, идентифицирующий конкретные данные, хранящиеся в экземпляре (см. RTTI ). Конструктор объекта устанавливает этот тег, и он остается постоянным на протяжении всего жизненного цикла объекта.
Тем не менее, иерархия классов включает истинный полиморфизм подтипов ; его можно расширить, создав дополнительные подклассы того же базового типа, которые нельзя было правильно обработать в рамках модели тегов / отправки. Следовательно, обычно невозможно выполнить анализ случая или отправку по «тегу» подобъекта, как это было бы для помеченных объединений. Некоторые языки, такие как Scala, позволяют «запечатать» базовые классы и объединять помеченные объединения с запечатанными базовыми классами.
Смотрите также
- Дискриминатор , тег типа для дискриминируемых объединений в CORBA
- Тип варианта
Рекомендации
- ^ http://cyclone.thelanguage.org/wiki/Tagged%20Unions
- ^ «Использование перечислений - Haxe - кроссплатформенный инструментарий» . Фонд Haxe.
- ^ "Ним Руководство" . nim-lang.org . Проверено 23 января 2020 .
- ^ "Язык программирования Rust" . Mozilla.
- ^ «Ржавчина на примере» . Mozilla.
- ^ «Перечисления - язык программирования Swift (Swift 5.4)» . docs.swift.org . Проверено 28 апреля 2021 .
- ^ «PEP 593 - Гибкие функции и аннотации переменных» . Python.org . Проверено 20.06.2021 .
Внешние ссылки
- boost :: variant - это типизированное дискриминированное объединение C ++
- std.variant - это реализация вариантного типа в D 2.0.