Теговый союз

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

Описание

Теговые объединения наиболее важны в языках функционального программирования , таких как 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$ имеют тип $\tau$ в предположениях $x : A$ и $y : B$ соответственно, то член ${\mathsf {case}}\ e\ {\mathsf {of}}\ x\Rightarrow e_{1}\mid y\Rightarrow e_{2}$ имеет тип $\tau$ . Тип суммы соответствует интуиционистской логической дизъюнкции при соответствии Карри-Ховарда .

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

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

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

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

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

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

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

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

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

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

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

Не удалось проанализировать (SVG (MathML можно включить через плагин браузера): неверный ответ («Расширение Math не может подключиться к Restbase.») с сервера «http://localhost:6011/en.wikipedia.org/v1/»:) : {\ displaystyle \ text {bind} \ двоеточие \ влево ( A + E \ вправо) \ в \ влево (A \ в \ влево (B + E \ вправо) \ вправо) \ в \ влево ( B + E \ вправо ) = 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 :

{\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 мы бы сделали это, создав такой тип данных:

datatype tree = Leaf
              | Node of (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(left) + countNodes(right)

График языковой поддержки

1960-е годы

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

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

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

node n := "1234";
 
case n in
  (real r):   print(("real:", r)),
  (int i):    print(("int:", i)),
  (compl c):  print(("compl:", c)),
  (string s): print(("string:", 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 of
                   square : (side : integer);
                   rectangle : (width, height : integer);
                   circle : (radius : integer);
	      end;

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

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;

-- Any attempt to access a member which existence depends
-- on a certain value of the discriminant, while the
-- discriminant is not the expected one, raises an error.

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

enum ShapeKind { Square, Rectangle, Circle };

struct Shape {
    int centerx;
    int centery;
    enum ShapeKind kind;
    union {
        struct { int side; };           /* Square */
        struct { int width, height; }; /* Rectangle */
        struct { int radius; };         /* Circle */
    };
};

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;
}

/* and so on */

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

В 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 operator()(int i)
    {
        std::cout << "It's an int, with value " << i << std::endl;
    }

    void operator()(const std::string& s)
    {
        std::cout << "It's a string, with value " << s << std::endl;
    }
};

boost::variant<int, std::string> v = 42;
boost::apply_visitor(display(), v);

boost::variant<int, std::string> v = "hello world";
boost::apply_visitor(display(), v);

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

sealed abstract class Tree
case object Leaf extends Tree
case class Node(value: Int, left: Tree, right: Tree) extends Tree

val tree = Node(5, Node(1, Leaf, Leaf), Node(3, Leaf, Node(4, Leaf, Leaf)))

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

tree match {
  case Node(x, _, _) => println("top level node value: " + x)
  case Leaf          => println("top level node is a leaf")
}

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

sealed abstract class 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# есть дискриминационные союзы:

type Tree =
  | Leaf
  | Node of value: int * left: Tree * right: Tree

let tree = Node(5, Node(1, Leaf, Leaf), Node(3, Leaf, Node(4, Leaf, Leaf)))

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

match tree with
| Node (x, _, _) -> printfn "top level node value: %i" x
| Leaf           -> printfn "top level node is a leaf"

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

enum Color {
  Red;
  Green;
  Blue;
  Rgb(r:Int, g:Int, b:Int);
}

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

switch (color) {
  case Red: trace("Color was red");
  case Green: trace("Color was green");
  case Blue: trace("Color was blue");
  case Rgb(r, g, b): trace("Color had a red value of " +r);
}

У Нима есть варианты объектов ^[3] объявление аналогично объявлениям в Паскале и Аде:

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

variant 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
    Cons(y, ys): y + sum(ys[])
)

echo sum(list(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 {
    Leaf,
    Node(i64, Box<Tree>, Box<Tree>)
}

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

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 {
    match tree {
        Tree::Node(v, a, b) => v + add_values(*a) + add_values(*b),
        Tree::Leaf => 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
    indirect case node(Int, Tree, Tree)
}

let tree = Tree.node(
    2,
    .node(0, .leaf, .leaf),
    .node(3, .leaf, .node(4, .leaf, .leaf))
)

func add_values(_ tree: Tree) -> Int {
    switch tree {
    case let .node(v, a, b):
        return v + add_values(a) + add_values(b)

    case .leaf:
        return 0
    }
}

assert(add_values(tree) == 9)

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

interface Leaf { kind: "leaf"; }

interface Node { kind: "node"; value: number; left: Tree; right: Tree; }

type Tree = Leaf | Node

const root: Tree = {
  kind: "node",
  value: 5,
  left: {
    kind: "node",
    value: 1,
    left: { kind: "leaf" },
    right: { kind: "leaf" }
  },
  right: {
    kind: "node",
    value: 3,
    left: { kind: "leaf" },
    right: {
      kind: "node",
      value: 4,
      left: { kind: "leaf" },
      right: { kind: "leaf" }
    }
  }
}

function visit(tree: Tree) {
    switch (tree.kind) {
        case "leaf":
            break
        case "node":
            console.log(tree.value)
            visit(tree.left)
            visit(tree.right)
            break 
    } 
}

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

Currency = Annotated[
    TypedDict('Currency', {'dollars': float, 'pounds': float}, total=False),
    TaggedUnion,
]

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

using Tree = std::variant<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
    {
      // The !sizeof(T) expression is always false
      static_assert(!sizeof(T), "non-exhaustive visitor!");
    };
  }
};
/*Tree forest = ...;
  std::visit(Transverser{}, forest);*/

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

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

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

См. также

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

Ссылки

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

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

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

[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 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v т и Типы данных
неинтерпретированный	Кусочек Байт Шаг Попробуйте Слово Битовый массив
Числовой	Произвольная точность или bignum Сложный Десятичный Фиксированная точка Плавающая точка Пониженная точность Минипоплавок Половинная точность bfloat16 Одинарная точность Двойная точность Четырехкратная точность Восьмеричная точность Повышенная точность Длинный дабл Целое число подписанность Интервал Рациональный
Указатель	Адрес физический виртуальный Ссылка
Текст	Характер Нить завершающийся нулем
Композитный	Алгебраический тип данных обобщенный Множество Ассоциативный массив Сорт Зависимый Равенство Индуктивный Пересечение Список Объект метаобъект Тип опции Продукт Запись или структура Уточнение Набор Союз отмеченный
Другой	логическое значение Нижний тип Коллекция Перечислимый тип Исключение Тип функции Непрозрачный тип данных Рекурсивный тип данных Семафор Транслировать Строго типизированный идентификатор Тип верха Тип класса Пустой тип Тип устройства Пустота
Связанный темы	Абстрактный тип данных Бокс Структура данных Общий Добрый метакласс Параметрический полиморфизм Примитивный тип данных Интерфейс Подтипирование Тип конструктора Преобразование типов Типовая система Теория типов Переменная