Объединение с тегами

редактировать

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

Содержание

1 Описание
2 Преимущества и недостатки
3 Примеры
4 Хронология языковой поддержки
- 4.1 1960-е
- 4.2 1970-е и 1980-е
- 4.3 2000-е
- 4.4 2010-е годы
5 Иерархии классов как помеченные объединения
6 См. Также
7 Ссылки
8 Внешние ссылки

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

return: A → (A + E) = a ↦ значение a {\ displaystyle {\ text {return}} \ двоеточие A \ to \ left (A + E \ right) = a \ mapsto {\ text {value}} \, a}

\ text {return} \ двоеточие A \ в \ left (A + E \ right) = a \ mapsto \ text {value} \, a

привязка: (A + E) → (A → (B + E)) → ( B + E) знак равно a ↦ е ↦ {err e, если a = err efa ′, если a = значение a ′ {\ displaystyle {\ text {bind}} \ двоеточие \ 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 {case}}}

\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:

fmap: (A → B) → ((A + E) → (B + E)) = f ↦ a ↦ {err е, если a = значение ошибки e (fa '), если a = значение a' {\ displaystyle {\ text {fmap}} \ двоеточие (A \ to B) \ to \ left (\ left (A + E \ right) \ в \ 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{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}}

join: ((A + E) + E) → (A + E) = a ↦ {err e if a = err e err e if a = value (err e) value a ′ if a = value (value a ′) {\ displaystyle {\ text {join}} \ двоеточие ((A + E) + E) \ to (A + E) = a \ mapsto {\ begin {cases} {\ text {err}} \, e {\ t_dv {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 {case} }}

{\text{join}}\colon ((A+E)+E)\to (A+E)=a\mapsto {\begin{cases}{\text{err}}\,e{\t_dv{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 мы бы сделали это, создав такой тип данных:

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

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

Node (5, Node (1, Leaf, Leaf), Node (3, Leaf, Node (4, Leaf, Leaf))))

, который соответствует этому дереву:

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

fun countNodes (Leaf) = 0 | countNodes (Node (int, left, right)) = 1 + countNodes (слева) + countNodes (справа)

Временная шкала языковой поддержки

1960-е

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

modeузел = union (real, int, comp, string );

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

node n: = "1234"; case n in(real r): print (("real:", r)), (int i): print (("int:", i)), (comp c): print ((" Compl: ", c)), (строка s): print ((" string: ", s)) out print ((" ?: ", n)) esac

1970-е и 1980-е

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

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

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

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

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

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

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

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

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

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

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

2000-е годы

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

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

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

отображение структуры: boost :: static_visitor {void operator () (int i) {std :: cout << "It's an int, with value " << i << std::endl; } void operator()(const std::strings) { std::cout << "It's a string, with value " << s << std::endl; } }; boost::variantv = 42; boost :: apply_visitor (дисплей (), v); boost :: variant v = "привет, мир"; boost :: apply_visitor (дисплей (), v);

Scala имеет классы case:

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

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

соответствие дерева {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# имеет различаемые объединения:

тип Tree = | Лист | Узел значения: int * left: Tree * right: Tree let tree = Node (5, Node (1, Leaf, Leaf), Node (3, Leaf, Node (4, Leaf, Leaf)))

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

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

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

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

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

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

Nim имеет варианты объекта, аналогичные объявлению в 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 :

import patty proc `~` [A] (a: A): ref A = new (result) result = a option List [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])) proc list [A] (xs: varargs [A]): List [A] = listHelper (@xs) proc sum (xs: List [int]): int = (block: match xs: Nil: 0 Минусы (y, ys): y + sum (ys)) echo sum (list (1, 2, 3, 4, 5))

2010s

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

enum Tree {Leaf, Node (i64, Box , Box )}

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

let 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), Tree :: Leaf =>0}} assert_eq! (add_values (дерево), 9);

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

С TypeScript можно также создавать помеченные союзы. Например:

interface Leaf {type: "leaf"; значение: строка; } узел интерфейса {тип: "узел"; слева: Дерево; справа: Дерево; } тип Tree = Leaf | Узел функции visit (tree: Tree) {switch (tree.type) {case "leaf": console.log (tree.value) break case "node": visit (tree.left) visit (tree.right) break}}

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

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

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

См. Также

Дискриминатор, тег типа для размеченных объединений в CORBA
Тип варианта

Ссылки

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

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