Помеченный союз

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

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{\text{return}}\colon A\to \left(A+E\right)=a\mapsto {\text{value}}\,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{if}}\ a={\text{err}}\,e\\f\,a'&{\text{if}}\ a={\text{value}}\,a'\end{cases}}

где "value" и "err" — конструкторы типа union, A и B — допустимые типы результатов, а E — тип условий ошибки. С другой стороны, та же монада может быть описана return и двумя дополнительными функциями, fmap и join :

{\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}}

{\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 * дерево * дерево )

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

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

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

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

fun  countNodes ( Leaf )  =  0  |  countNodes ( Node ( int ,  left ,  right ))  =  1  +  countNodes ( left )  +  countNodes ( right )

Хронология языковой поддержки

1960-е

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

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

Пример использования union caseдля node:

узел n := "1234"; случай n в ( действительном r): print(("действительном:", r)), ( целое i): печать(("целое:", i)), ( компл с): print(("компл:", с)), ( строка s): print(("строка:", s)) out print(("?:", n)) esac

1970-е и 1980-е годы

Функциональные языки программирования , такие как ML (с 1970-х) и Haskell (с 1990-х) отводят центральную роль тегированным объединениям и имеют возможность проверять, что все случаи обработаны. Некоторые другие языки также поддерживают тегированные объединения.

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

type shapeKind = ( square , rectangle , circle ) ; shape = record centerx : integer ; centery : integer ; case kind : shapeKind квадрата : ( side : integer ) ; прямоугольника : ( width , height : integer ) ; круга : ( radius : integer ) ; end ;

и этот эквивалент на Аде:

type  Shape_Kind  is  ( Square ,  Rectangle ,  Circle ); type  Shape  ( Kind  : Shape_Kind )  is  record  Center_X  :  Integer ;  Center_Y  :  Integer ;  case  Kind  is  when  Square  =>  Side  :  Integer ;  when  Rectangle  =>  Width ,  Height  :  Integer ;  when  Circle  =>  Radius  :  Integer ;  end  case ; end record ;-- Любая попытка доступа к члену, существование которого зависит от определенного значения дискриминанта, при этом -- дискриминант не является ожидаемым, приводит к ошибке.

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

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

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

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

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

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

2000-е

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

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

Библиотека вариантов из Boost C++ Libraries продемонстрировала возможность реализации безопасного тегированного объединения в виде библиотеки на 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 :: variation < int , std :: string > v = 42 ; boost :: apply_visitor ( display (), v );     boost :: variation < int , std :: string > v = "привет мир" ; boost :: apply_visitor ( display (), v );

В Scala есть классы case:

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

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

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

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

запечатанный абстрактный класс Shape ( centerX : Int , centerY : Int ) case class Square ( side : Int , centerX : Int , centerY : Int ) extends Shape ( centerX , centerY ) case class Rectangle ( length : Int , height : Int , centerX : Int , centerY : Int ) extends Shape ( centerX , centerY ) case class Circle ( radius : Int , centerX : Int , centerY : Int ) extends Shape ( centerX , centerY )

F# дискриминирует профсоюзы:

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

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

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

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

enum Color { Красный ; Зеленый ; Синий ; Rgb ( r : Int , g : Int , b : Int ); }

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

switch ( color ) { case Red : trace ( "Цвет был красным" ); case Green : trace ( "Цвет был зеленым" ); case Blue : trace ( "Цвет был синим" ); case Rgb ( r , g , b ): trace ( "Цвет имел красное значение " + r ); }

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

тип ShapeKind = enum skSquare , skRectangle , skCircle Shape = object centerX , centerY : int случай kind : ShapeKind из skSquare : side : int из skRectangle : length , height : int из skCircle : radius : int

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

импортная котлета процедура `~` [ A ] ( a : A ): ссылка A = новый ( результат ) результат [] = a         Список вариантов [ A ] : Ноль минусов ( x : A , xs : ссылка Список [ A ] )       proc listHelper [ A ] ( xs : seq [ A ] ): Список [ A ] = если xs . len == 0 : Nil [ A ] () иначе : Cons ( xs [ 0 ] , ~ listHelper ( xs [ 1 .. xs . high ] ))              список процедур [ A ] ( xs : varargs [ A ] ): Список [ 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-е

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

enum Tree [ + T ]: case Leaf case Node ( x : Int , left : Tree [ T ], right : Tree [ T ])          enum Shape ( centerX : Int , centerY : Int ): case Square ( side : Int , centerX : Int , centerY : Int ) extends Shape ( centerY , centerX ) case Rectangle ( length : Int , height : Int , centerX : Int , centerY : Int ) extends Shape ( centerX , centerY ) case Circle ( radius : Int , centerX : Int , centerY : Int ) extends Shape ( centerX , centerY )

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

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

Он также позволяет выполнять сопоставление по объединениям:

пусть дерево = Дерево :: Узел ( 2 , Ящик :: новый ( Дерево :: Узел ( 0 , Ящик :: новый ( Дерево :: Лист ), Ящик :: новый ( Дерево :: Лист ))), Ящик :: новый ( Дерево :: Узел ( 3 , Ящик :: новый ( Дерево :: Лист ), Ящик :: новый ( Дерево :: Узел ( 4 , Ящик :: новый ( Дерево :: Лист ), Ящик :: новый ( Дерево :: Лист )))))) );            fn  add_values ( дерево : Дерево )  -> i64  { сопоставление дерева { Дерево :: Узел ( v , a , b ) => v + add_values ( * a ) + add_values ( * b ), Дерево :: Лист => 0 } }                assert_eq! ( add_values ( tree ), 9 );

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

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

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

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

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

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

Валюта  =  Аннотированный [  TypedDict ( 'Валюта' ,  { 'доллары' :  число с плавающей точкой ,  'фунты' :  число с плавающей точкой },  total = False ),  TaggedUnion , ]

C++17 вводит std::variant и constexpr if

использование Tree = std :: variation < struct Leaf , struct Node > ;      struct Leaf { std :: string value ; }; struct Node { Tree * left = nullptr ; Tree * right = nullptr ; };            struct Transverser { template < typename T > void Operator ()( T && v ) { if constexpr ( std :: is_same_v < T , Leaf &> ) { std :: cout << v . value << " \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 ), "неисчерпывающий посетитель!" ); }; } }; /*Tree forest = ...;  std::visit(Transverser{}, forest);*/

Иерархии классов как помеченные объединения

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

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

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

Дискриминатор , тег типа для дискриминируемых союзов в CORBA
Тип варианта (COM)

Ссылки

^ «Циклон: отмеченные союзы».
^ «Использование перечислений — Haxe — кроссплатформенный инструментарий». Haxe Foundation.
^ "Руководство по Nim". nim-lang.org . Получено 2020-01-23 .
^ "Справочник языка Scala 3: Перечисления". Команда Scala.
^ "Язык программирования Rust". Mozilla.
^ «Rust на примере». Mozilla.
^ «Перечисления — язык программирования Swift (Swift 5.4)». docs.swift.org . Получено 28.04.2021 .
^ "PEP 593 — Гибкие аннотации функций и переменных". Python.org . Получено 20 июня 2021 г. .

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

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