Теговый союз

Структура данных, используемая для хранения значения, которое может принимать несколько разных, но фиксированных типов.

В информатике тегированное объединение , также называемое вариантом , вариантной записью , типом выбора , дискриминируемым объединением , непересекающимся объединением , типом суммы или копроизведением , представляет собой структуру данных, используемую для хранения значения, которое может принимать несколько разных, но фиксированных типов. . В любой момент времени может использоваться только один из типов, и поле тега явно указывает, какой из них используется. Его можно рассматривать как тип, имеющий несколько «случаев», каждый из которых должен корректно обрабатываться при манипулировании этим типом. Это имеет решающее значение при определении рекурсивных типов данных, в которых некоторый компонент значения может иметь тот же тип, что и это значение, например, при определении типа для представления деревьев, где необходимо различать многоузловые поддеревья и листья. Как и обычные объединения , тегированные объединения могут экономить место, перекрывая области хранения для каждого типа, поскольку одновременно используется только один из них.

Описание

Теговые объединения наиболее важны в языках функционального программирования , таких как ML и Haskell , где они называются типами данных (см. Алгебраический тип данных ), и компилятор может проверить, что все случаи тегового объединения всегда обрабатываются, избегая многих типов ошибок. Типы проверяемых сумм во время компиляции также широко используются в Rust , где они называются enum . Однако их можно создать практически на любом языке программирования , и они намного безопаснее, чем немаркированные объединения, часто называемые просто объединениями, которые похожи, но не отслеживают явно, какой член объединения используется в данный момент.

Теговые объединения часто сопровождаются концепцией конструктора типа , который похож , но не совпадает с конструктором класса . Конструкторы типов создают тип объединения тегов, учитывая исходный тип тега и соответствующий тип.

Математически тегированные союзы соответствуют непересекающимся или дискриминируемым союзам , обычно записываемым с помощью +. По элементу непересекающегося союза A + B можно определить, произошел ли он из A или B. Если элемент находится в обоих, будут две фактически различные копии значения в A + B : одна из A и одна из B.

В теории типов тегированное объединение называется типом суммы . Типы сумм являются двойственными типами продуктов . Обозначения различаются, но обычно тип суммы A + B имеет две формы введения ( инъекции ) inj ₁ : A → A + B и inj ₂ : B → A + B . Формой исключения является анализ прецедентов, известный как сопоставление с образцом в языках стиля ML : если e имеет тип A + B , а e ₁ и e ₂ имеют тип при предположениях x : A и y : B соответственно, тогда термин имеет тип . Тип суммы соответствует интуиционистской логической дизъюнкции при соответствии Карри-Ховарда . ${\displaystyle \tau }$ ${\displaystyle {\mathsf {case}}\ e\ {\mathsf {of}}\ x\Rightarrow e_{1}\mid y\Rightarrow e_{2}}$ ${\displaystyle \tau }$

Перечислимый тип можно рассматривать как вырожденный случай: тегированное объединение типов единиц . Он соответствует набору нулевых конструкторов и может быть реализован как простая переменная тега, поскольку он не содержит никаких дополнительных данных, кроме значения тега.

Многие методы программирования и структуры данных, включая веревку , отложенное вычисление , иерархию классов (см. ниже), арифметику произвольной точности , CDR-кодирование , бит косвенности и другие виды тегированных указателей и т. д. обычно реализуются с использованием некоторого рода тегированного объединения.

Объединение тегов можно рассматривать как простейший вид формата данных с самоописанием . Тег тегированного объединения можно рассматривать как простейший вид метаданных .

Преимущества и недостатки

Основное преимущество тегированного объединения перед нетегированным объединением заключается в том, что любой доступ безопасен, и компилятор может даже проверить, что все случаи обработаны. Объединения без тегов зависят от логики программы, позволяющей правильно идентифицировать активное в данный момент поле, что может привести к странному поведению и труднообнаружимым ошибкам, если эта логика не сработает.

Основное преимущество объединения с тегами перед простой записью , содержащей поле для каждого типа, заключается в том, что оно экономит пространство за счет перекрытия хранилища для всех типов. Некоторые реализации резервируют достаточно места для самого большого типа, в то время как другие динамически корректируют размер значения тегированного объединения по мере необходимости. Когда значение неизменяемо , можно легко выделить столько места, сколько необходимо.

Основным недостатком объединений с тегами является то, что тег занимает место. Поскольку обычно существует небольшое количество альтернатив, тег часто можно сжать в 2 или 3 бита везде, где есть место, но иногда даже эти биты недоступны. В этом случае полезной альтернативой могут быть свернутые , вычисляемые или закодированные теги , где значение тега динамически вычисляется из содержимого поля объединения. Распространенными примерами этого являются использование зарезервированных значений , где, например, функция, возвращающая положительное число, может возвращать -1, указывая на сбой, и контрольные значения , чаще всего используемые в помеченных указателях .

Иногда нетегированные объединения используются для выполнения преобразований между типами на уровне битов, что в C++ называется переинтерпретацией приведения. Теговые союзы не предназначены для этой цели; обычно новое значение присваивается при каждом изменении тега.

Многие языки в некоторой степени поддерживают универсальный тип данных , который включает в себя все значения всех других типов, и часто предоставляется способ проверить фактический тип значения универсального типа. Их иногда называют вариантами . Хотя универсальные типы данных по формальному определению сравнимы с тегированными объединениями, типичные теговые объединения включают относительно небольшое количество случаев, и эти случаи образуют разные способы выражения одной связной концепции, такой как узел структуры данных или инструкция. Кроме того, ожидается, что каждый возможный случай объединения тегов будет рассмотрен при его использовании. Значения универсального типа данных не связаны друг с другом, и не существует реального способа справиться со всеми ними.

Подобно типам опций и обработке исключений , тегированные объединения иногда используются для обработки исключительных результатов. Часто эти теги сворачиваются в тип как зарезервированные значения , и их появление не проверяется последовательно: это довольно распространенный источник ошибок программирования. Такое использование тегированных объединений можно формализовать как монаду со следующими функциями:

${\displaystyle {\text{return}}\colon A\to \left(A+E\right)=a\mapsto {\text{value}}\,a}$

${\displaystyle {\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{if}}\ a={\text{err}}\,e\\f\,a'&{\text{if}}\ a={\text{value}}\,a'\end{cases}}}$

где «value» и «err» — конструкторы типа объединения, A и B — допустимые типы результатов, а E — тип условий ошибки. Альтернативно, та же монада может быть описана с помощью return и двух дополнительных функций, fmap и join :

${\displaystyle {\text{fmap}}\colon (A\to B)\to \left(\left(A+E\right)\to \left(B+E\right)\right)=f\mapsto a\mapsto {\begin{cases}{\text{err}}\,e&{\text{if}}\ a={\text{err}}\,e\\{\text{value}}\,{\text{(}}\,f\,a'\,{\text{)}}&{\text{if}}\ a={\text{value}}\,a'\end{cases}}}$

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

Примеры

Допустим, мы хотим построить двоичное дерево целых чисел. В ML мы бы сделали это, создав такой тип данных:

 дерево  типов данных =  Лист  |  Узел  ( int * дерево * дерево ) _     

Это объединение с тегами в двух случаях: один, лист, используется для завершения пути дерева и действует так же, как нулевое значение в императивных языках. Другая ветвь содержит узел, содержащий целое число, а также левое и правое поддерево. Leaf и Node — это конструкторы, которые позволяют нам создавать конкретное дерево, например:

Узел ( 5 ,  Узел ( 1 ,  Лист ,  Лист ),  Узел ( 3 ,  Лист ,  Узел ( 4 ,  Лист ,  Лист )))

что соответствует этому дереву:

Дерево, созданное вышеуказанными конструкторами

Теперь мы можем легко написать типобезопасную функцию, которая, скажем, подсчитывает количество узлов в дереве:

весело  countNodes ( Лист )  =  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)), ( compl c): print(("compl:", c)), ( строка s): print(("строка:", s)) out print(("?:", n)) esac

1970-е и 1980-е годы

Хотя в первую очередь только функциональные языки программирования, такие как ML (с 1970-х годов) и Haskell (с 1990-х годов), отводят центральную роль теговым объединениям и имеют возможность проверять обработку всех случаев, другие языки также поддерживают теговые объединения. Однако на практике они могут быть менее эффективными в нефункциональных языках из-за оптимизации, обеспечиваемой компиляторами функциональных языков, которые могут исключить явные проверки тегов и избежать явного хранения тегов . ^{[ нужна цитата ]}

Pascal , Ada и Modula-2 называют их вариантными записями (формально различаемый тип в Ada) и требуют, чтобы поле тега было создано вручную и указаны значения тега, как в этом примере Pascal:

введите shapeKind = ( квадрат , прямоугольник , круг ) ; форма = запись centerx : целое число ; центр : целое число ; Вид случая : формаВид квадрата : ( сторона : целое число ) ; прямоугольник : ( ширина , высота : целое число ) ; круг : ( радиус : целое число ) ; конец ;                                    

и этот эквивалент Ada:

тип  Shape_Kind  (  Квадрат , Прямоугольник , Круг ) ;  тип Shape ( Kind : Shape_Kind ) — запись Center_X : Integer ; Center_Y : целое число ; Case Kind — это когда Square => Side : Integer ; когда Прямоугольник => Ширина , Высота : Целое число ; когда Круг => Радиус : Целое число ; конец дела ; завершить запись ;                                    -- Любая попытка получить доступ к члену, существование которого зависит -- от определенного значения дискриминанта, в то время как -- дискриминант не является ожидаемым, вызывает ошибку.

В C и C++ тегированный союз может быть создан из нетегированного объединения с использованием строгой дисциплины доступа, при которой тег всегда проверяется:

enum ShapeKind { Квадрат , Прямоугольник , Круг };      struct Shape { int centerx ; интервал по центру ; перечисление ShapeKind kind ; объединение { структура { int сторона ; }; /* Square */ struct { int width , height ; }; /* Прямоугольник */ struct { int radius ; }; /* Круг */ }; };                               int getSquareSide ( struct Shape * s ) { assert ( s -> kind == Square ); вернуть s -> сторона ; }         void setSquareSide ( struct Shape * s , intside ) { s - > kind = Square ; s -> сторона = сторона ; }            /* и так далее */

Пока доступ к полям объединения осуществляется только через функции, доступ будет безопасным и правильным. Тот же подход можно использовать для закодированных тегов; мы просто декодируем тег и затем проверяем его при каждом доступе. Если неэффективность этих проверок тегов вызывает беспокойство, они могут быть автоматически удалены в окончательной версии.

В C и C++ также имеется языковая поддержка одного конкретного объединения тегов: возможно нулевого указателя . Его можно сравнить с optionтипом в ML или Maybeтипом в Haskell и рассматривать как тегированный указатель : тегированное объединение (с закодированным тегом) двух типов:

• Действительные указатели,
• Тип нулевого указателя только с одним значением, nullуказывающим на исключительное состояние.

К сожалению, компиляторы C не проверяют, всегда ли обрабатывается нулевой случай, и это особенно распространенный источник ошибок в коде C, поскольку существует тенденция игнорировать исключительные случаи.

2000-е

Один из продвинутых диалектов C, называемый Cyclone , имеет обширную встроенную поддержку теговых объединений. ^[1]

Типы перечислений в языках Rust , Haxe и Swift также работают как тегированные объединения.

Библиотека вариантов из библиотек Boost C++ продемонстрировала возможность реализации безопасного объединения тегов в виде библиотеки на C++, доступной для посещения с использованием объектов-функций.

struct display : boost :: static_visitor < void > { void оператор ()( int i ) { std :: cout << "Это int со значением " << i << std :: endl ; }                void оператор ()( const std :: string & s ) { std :: cout << "Это строка со значением " << s << std :: endl ; } };            boost :: variant < int , std :: string > v = 42 ; boost :: apply_visitor ( display (), v );     boost :: variant < int , std :: string > v = "привет, мир" ; boost :: apply_visitor ( display (), v );     

В Scala есть классы случаев:

запечатанный абстрактный класс Tree Case object Leaf расширяет Tree Case class Node ( значение : Int , слева : Tree , справа : Tree ) расширяет Tree                дерево val = Узел ( 5 , Узел ( 1 , Лист , Лист ), Узел ( 3 , Лист , Узел ( 4 , Лист , Лист )))           

Поскольку иерархия классов изолирована, компилятор может проверить, что все случаи обрабатываются в соответствии с шаблоном:

сопоставление дерева { case Node ( x , _ , _ ) => println ( «значение узла верхнего уровня: « + x ) case Leaf => println ( «узел верхнего уровня является листом» ) }              

Классы регистров Scala также допускают повторное использование посредством подтипирования:

запечатанный абстрактный класс Shape ( centerX : Int , centerY : Int ) класс случая Square ( сторона : Int , centerX : Int , centerY : Int ) расширяет форму ( centerX , centerY ) класс корпуса Rectangle ( длина : Int , высота : Int , centerX : Int , centerY : Int ) расширяет форму ( centerX , centerY ) класс корпуса Circle ( radius : Int , centerX : Int , centerY : Int ) расширяет форму ( centerX , centerY )                                      

В F# есть дискриминационные союзы:

тип Дерево = | Лист | Узел значения : int * слева : Дерево * справа : Дерево _               пусть дерево = Узел ( 5 , Узел ( 1 , Лист , Лист ), Узел ( 3 , Лист , Узел ( 4 , Лист , Лист )))           

Поскольку определенные случаи являются исчерпывающими, компилятор может проверить, что все случаи обрабатываются в соответствии с шаблоном:

дерево совпадений с | Узел ( x , _, _) -> printfn «значение узла верхнего уровня: %i» x | Leaf -> printfn «узел верхнего уровня является листом»              

Перечисления Haxe также работают как тегированные объединения: ^[2]

перечисление Цвет { Красный ; Зеленый ; Синий ; Rgb ( r : Int , g : Int , b : Int ); }        

Их можно сопоставить с помощью выражения переключателя:

переключатель ( цвет ) { case Red : трассировка ( «Цвет был красный» ); case Green : трассировка ( «Цвет был зеленый» ); case Blue : трассировка ( «Цвет был синий» ); case Rgb ( r , g , b ): трассировка ( «Цвет имел красное значение « + r ); }                 

В Nim есть варианты объектов ^[3] , аналогичные по объявлению тем, что есть в Паскале и Аде:

тип ShapeKind = enum skSquare , skRectangle , skCircle Shape = объект centerX , centerY : int тип случая : ShapeKind из skSquare : сторона : int из skRectangle : длина , высота : int из skCircle : радиус : int                            

Макросы можно использовать для эмуляции сопоставления с образцом или для создания синтаксического сахара для объявления вариантов объекта, как показано здесь, как это реализовано пакетом patty:

импортная котлета proc `~` [ A ] ( a : A ): ref A = новый ( результат ) результат [] = a         Список вариантов [ A ] : Nil Cons ( x : A , xs : ref List [ A ] )       proc listHelper [ A ] ( xs : seq [ A ] ): List [ A ] = if xs . len == 0 : Nil [ A ] () else : Cons ( xs [ 0 ] , ~ listHelper ( xs [ 1 .. xs . high ] ))              список процедур [ A ] ( xs : varargs [ A ] ): List [ A ] = listHelper ( @ xs )     proc sum ( xs : List [ int ] ): int = ( блок : match xs : Nil : 0 Cons ( y , ys ): y + sum ( ys [] ) )              эхо- сумма ( список ( 1 , 2 , 3 , 4 , 5 ))     

2010-е годы

Перечисления добавлены в Scala 3, ^[4] , что позволяет нам более кратко переписать предыдущие примеры Scala:

enum Tree [ + T ]: регистр Leaf Case Node ( x : Int , слева : Tree [ T ], справа : Tree [ T ])          enum Shape ( centerX : Int , centerY : Int ): регистр Square ( сторона : Int , centerX : Int , centerY : Int ) расширяет форму ( centerY , centerX ) регистр Rectangle ( длина : Int , высота : Int , centerX : Int , centerY : Int ) расширяет форму ( centerX , centerY ) Case Circle ( радиус : Int , centerX : Int , centerY : Int ) расширяет форму ( centerX , centerY )                                    

В языке Rust имеется обширная поддержка объединений тегов, называемых перечислениями. ^[5] Например:

enum  Tree { Лист , Узел ( i64 , Box < Дерево > , Box < Дерево > ) }     

Он также позволяет сопоставлять союзы:

let Tree = Дерево :: Узел ( 2 , Коробка :: новый ( Дерево :: Узел ( 0 , Коробка :: новый ( Дерево :: Лист ), Коробка :: новый ( Дерево :: Лист ))), Коробка :: новый ( Дерево :: Узел ( 3 , Коробка :: новый ( Дерево :: Лист ), Коробка :: новый ( Дерево :: Узел ( 4 , Коробка :: новый ( Дерево :: Лист ), Коробка :: новый ( Дерево :: Лист )))) ) );            fn  add_values ​​( tree : Tree )  -> i64  { match Tree { Tree :: Node ( v , a , b ) => v + add_values ​​( * a ) + add_values ​​( * b ), Tree :: Leaf => 0 } }                утверждать_eq! ( add_values ​​( дерево ), 9 ); 

Модель обработки ошибок в Rust во многом опирается на эти теговые объединения, особенно на Option<T>тип (или Noneили Some(T)) и Result<T, E>тип (или Ok(T)или) Err(E). ^[6]

Swift также имеет существенную поддержку тегированных объединений посредством перечислений. ^[7] Например:

enum  Tree  {  лист случая  косвенный узел случая ( Int , Tree , Tree ) }     пусть  дерево  =  Дерево . узел (  2 ,  . узел ( 0 ,  . лист ,  . лист ),  . узел ( 3 ,  . лист ,  . узел ( 4 ,  . лист ,  . лист )) )func  add_values ​​( _tree  : Tree ) - > Int {  дерево переключения { case let . узел ( v , a , b ): return v + add_values ​​( a ) + add_values ​​( b )                  случай  . лист :  вернуть  0  } }утверждать ( add_values ​​( дерево )  ==  9 )

С помощью TypeScript также можно создавать теговые объединения. Например:

интерфейс Leaf { kind : "leaf" ; }     интерфейс Node { kind : "узел" ; значение : число ; слева : Дерево ; справа : Дерево ; }           тип Дерево = Лист | Узел     const root : Tree = { вид : "узел" , значение : 5 , влево : { вид : "узел" , значение : 1 , влево : { вид : "лист" }, вправо : { вид : "лист" } }, вправо : { вид : "узел" , значение : 3 , влево : { вид : "лист" }, вправо : { вид : "узел" , значение : 4 , влево : { вид : "лист" }, вправо : { вид : "лист" } } } }                                                      посещение функции ( дерево : Дерево ) { переключатель ( дерево . вид ) { случай "лист" : разрыв случая "узел" : консоль . журнал ( дерево . значение ) посещение ( дерево . влево ) посещение ( дерево . вправо ) перерыв } }                  

В Python 3.9 появилась поддержка ввода аннотаций, которые можно использовать для определения типа объединения тегов (PEP-593 ^[8] ):

Валюта  =  Аннотация [  TypedDict ( 'Currency' ,  { 'доллары' :  float ,  'фунты' :  float },  total = False ),  TaggedUnion , ]

В C++17 представлены std::variant и constexpr, если

используя Tree = std :: variant < struct Leaf , struct Node > ;      struct Leaf { std :: строковое значение ; }; struct Node { Дерево * left = nullptr ; Дерево * вправо = nullptr ; };            struct Transverser { шаблон < имя_типа T > void оператор ()( T && v ) { if constexpr ( std :: is_same_v < T , Leaf &> ) { std :: cout << v . значение << " \n " ; } 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 { // Выражение !sizeof(T) всегда ложно static_assert ( ! sizeof ( T ), "неполный посетитель!" ); }; } }; /*Деревянный лес = ...;  std::visit(Transverser{}, Forest);*/             

Иерархии классов как тегированные объединения

В типичной иерархии классов объектно-ориентированного программирования каждый подкласс может инкапсулировать данные, уникальные для этого класса. Метаданные, используемые для поиска виртуальных методов (например, указатель vtable объекта в большинстве реализаций C++), идентифицируют подкласс и поэтому эффективно действуют как тег, идентифицирующий конкретные данные, хранящиеся в экземпляре (см. RTTI ). Конструктор объекта устанавливает этот тег, и он остается постоянным на протяжении всего существования объекта.

Тем не менее, иерархия классов включает в себя настоящий полиморфизм подтипов ; его можно расширить путем создания дополнительных подклассов того же базового типа, которые невозможно правильно обработать в рамках модели тегов/отправки. Следовательно, обычно невозможно выполнить анализ вариантов или отправку «тега» подобъекта, как это было бы сделано для тегированных объединений. Некоторые языки, такие как Scala , позволяют «запечатывать» базовые классы и объединять тегированные объединения с запечатанными базовыми классами.

Смотрите также

• Дискриминатор , тег типа для дискриминируемых объединений в CORBA .
• Тип варианта (COM)

Рекомендации

1. «Циклон: Союзы с тегами» .
2. «Использование перечислений - Haxe - Кроссплатформенный набор инструментов» . Фонд Хаксе.
3. "Руководство Нима" . nim-lang.org . Проверено 23 января 2020 г.
4. «Справочник по языку Scala 3: перечисления» . Команда Скала.
5. «Язык программирования Rust». Мозилла.
6. «Ржавчина на примере». Мозилла.
7. «Перечисления — язык программирования Swift (Swift 5.4)» . docs.swift.org . Проверено 28 апреля 2021 г.
8. «PEP 593 — Гибкие функции и аннотации переменных» . Python.org . Проверено 20 июня 2021 г.

Внешние ссылки

• boost::variant — это типобезопасное дискриминируемое объединение C++.
• std.variant — это реализация варианта типа в D 2.0.