Размеченные объединения: структура данных с вариантами типов

Введение

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

Описание

Тегированные объединения наиболее важны в функциональных языках программирования, таких как ML и Haskell, где они называются типами данных (см. алгебраический тип данных), и компилятор может проверить, что все случаи тегированного объединения всегда обрабатываются, избегая многих типов ошибок. Типы с проверкой суммы во время компиляции также широко используются в Rust, где они называются `enum`. Однако их можно построить практически на любом языке программирования, и они намного безопаснее нетегированных объединений, часто называемых просто объединениями, которые похожи, но не отслеживают, какой член объединения в настоящее время используется. Тегированные объединения часто сопровождаются концепцией конструктора, который похож, но не идентичен конструктору для класса. Конструктор — это функция или выражение, которое производит значение тегированного типа объединения, заданное тегом и значением соответствующего типа. Математически тегированные объединения соответствуют непересекающимся или дискриминированным объединениям, обычно записываемым с помощью +. Для элемента непересекающегося объединения A + B можно определить, из A он или из B. Если элемент принадлежит обоим, в A + B будет две фактически различные копии значения, одна из A и одна из B. В теории типов тегированное объединение называется типом суммы. Типы суммы являются двойственными типам произведений. Обозначения различаются, но обычно тип суммы A + B включает две формы введения (инъекции): inj1: A → A + B и … Форма устранения — это анализ случаев, известный как сопоставление с образцом в языках в стиле ML: если e имеет тип A + B, а e1 и e2 имеют тип при предположениях x: A и y: B соответственно, то термин имеет тип. Тип суммы соответствует интуиционистскому логическому дизъюнкции в соответствии с соответствием Карри — Ховарда. Перечисляемый тип можно рассматривать как вырожденный случай: тегированное объединение типов-единиц. Он соответствует набору конструкторов с нулевыми аргументами и может быть реализован как простая переменная тега, поскольку не содержит дополнительных данных, кроме значения тега. Многие методы программирования и структуры данных, включая rope, ленивые вычисления, иерархию классов (см. ниже), арифметику произвольной точности, кодирование CDR, бит косвенности и другие виды помеченных указателей, обычно реализуются с использованием того или иного тегированного объединения. Тегированное объединение можно рассматривать как простейший вид самоописываемого формата данных. Тег тегированного объединения можно рассматривать как простейший вид метаданных.

Tagged unions are most important in functional programming languages such as ML and Haskell, where they are called datatypes (see algebraic data type) and the compiler can verify that all cases of a tagged union are always handled, avoiding many types of errors. Compile time checked sum types are also extensively used in Rust, where they are called enum. They can, however, be constructed in nearly any programming language, and are much safer than untagged unions, often simply called unions, which are similar but do not explicitly track which member of a union is currently in use. Tagged unions are often accompanied by the concept of a constructor, which is similar but not the same as a constructor for a class. A constructor is a function or an expression that produces a value of the tagged union type, given a tag and a value of the corresponding type. Mathematically, tagged unions correspond to disjoint or discriminated unions, usually written using +. Given an element of a disjoint union A + B, it is possible to determine whether it came from A or B. If an element lies in both, there will be two effectively distinct copies of the value in A + B, one from A and one from B. In type theory, a tagged union is called a sum type. Sum types are the dual of product types. Notations vary, but usually the sum type A + B comes with two introduction forms (injections) inj1: A → A + B and The elimination form is case analysis, known as pattern matching in ML style languages: if e has type A + B and e1 and e2 have type under the assumptions x: A and y: B respectively, then the term has type The sum type corresponds to intuitionistic logical disjunction under the Curry–Howard correspondence. An enumerated type can be seen as a degenerate case: a tagged union of unit types. It corresponds to a set of nullary constructors and may be implemented as a simple tag variable, since it holds no additional data besides the value of the tag. Many programming techniques and data structures, including rope, lazy evaluation, class hierarchy (see below), arbitrary precision arithmetic, CDR coding, the indirection bit, and other kinds of tagged pointers, are usually implemented using some sort of tagged union. A tagged union can be seen as the simplest kind of self describing data format. The tag of the tagged union can be seen as the simplest kind of metadata.

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

Основное преимущество маркированного союза над немаркированным союзом заключается в том, что все обращения к данным безопасны, и компилятор может даже проверить, что все возможные случаи обработаны. Немаркированные союзы полагаются на логику программы для правильной идентификации текущего активного поля, что может привести к непредсказуемому поведению и трудноуловимым ошибкам, если эта логика окажется неверной. Основное преимущество маркированного союза перед простой записью, содержащей поле для каждого типа, заключается в экономии памяти за счет совместного использования памяти для всех типов. Некоторые реализации резервируют достаточно памяти для самого большого типа, в то время как другие динамически изменяют размер маркированного союза по мере необходимости. Когда значение неизменно, можно выделить ровно столько памяти, сколько требуется. Главный недостаток маркированных союзов – метка занимает место. Поскольку обычно число альтернатив невелико, метку часто можно уместить в 2 или 3 бита, где только возможно, но иногда даже этих битов недостаточно. В этом случае полезной альтернативой могут быть свернутые, вычисленные или закодированные метки, когда значение метки динамически вычисляется на основе содержимого поля союза. Распространенными примерами являются использование зарезервированных значений, когда, например, функция, возвращающая положительное число, может вернуть 1 для обозначения ошибки, и сигнальные значения, чаще всего используемые в меченных указателях. Иногда немаркированные союзы используются для выполнения преобразований на уровне битов между типами, называемых reinterpret_cast в C++. Маркированные союзы не предназначены для этой цели; обычно новое значение присваивается при изменении метки. Многие языки в той или иной степени поддерживают универсальный тип данных, который включает в себя все значения всех других типов, и часто предоставляется способ проверки фактического типа значения универсального типа. Их иногда называют вариантами. Хотя универсальные типы данных сопоставимы с маркированными союзами в их формальном определении, типичные маркированные союзы включают относительно небольшое количество случаев, и эти случаи представляют собой различные способы выражения единой согласованной концепции, такие как узел структуры данных или инструкция. Кроме того, предполагается, что каждый возможный случай маркированного союза будет обработан при его использовании. Значения универсального типа данных не связаны между собой, и нет практического способа обработать их все. Как и типы Option и обработка исключений, маркированные союзы иногда используются для обработки исключительных результатов. Часто эти метки включаются в тип в качестве зарезервированных значений, и их появление не всегда проверяется последовательно: это довольно распространенный источник ошибок программирования. Это использование маркированных союзов можно формализовать как монаду со следующими функциями: где "value" и "err" – конструкторы типа союза, A и B – допустимые типы результатов, а E – тип условий ошибки. В качестве альтернативы, та же монада может быть описана функцией return и двумя дополнительными функциями, fmap и join:

The primary advantage of a tagged union over an untagged union is that all accesses are safe, and the compiler can even check that all cases are handled. Untagged unions depend on program logic to correctly identify the currently active field, which may result in strange behavior and hard to find bugs if that logic fails. The primary advantage of a tagged union over a simple record containing a field for each type is that it saves storage by overlapping storage for all the types. Some implementations reserve enough storage for the largest type, while others dynamically adjust the size of a tagged union value as needed. When the value is immutable, it is simple to allocate just as much storage as is needed. The main disadvantage of tagged unions is that the tag occupies space. Since there are usually a small number of alternatives, the tag can often be squeezed into 2 or 3 bits wherever space can be found, but sometimes even these bits are not available. In this case, a helpful alternative may be folded, computed or encoded tags, where the tag value is dynamically computed from the contents of the union field. Common examples are the use of reserved values, where, for example, a function returning a positive number may return 1 to indicate failure, and sentinel values, most often used in tagged pointers. Sometimes, untagged unions are used to perform bit level conversions between types, called reinterpret casts in C++. Tagged unions are not intended for this purpose; typically a new value is assigned whenever the tag is changed. Many languages support, to some extent, a universal data type, which is a type that includes every value of every other type, and often a way is provided to test the actual type of a value of the universal type. These are sometimes referred to as variants. While universal data types are comparable to tagged unions in their formal definition, typical tagged unions include a relatively small number of cases, and these cases form different ways of expressing a single coherent concept, such as a data structure node or instruction. Also, there is an expectation that every possible case of a tagged union will be dealt with when it is used. The values of a universal data type are not related and there is no feasible way to deal with them all. Like option types and exception handling, tagged unions are sometimes used to handle the occurrence of exceptional results. Often these tags are folded into the type as reserved values, and their occurrence is not consistently checked: this is a fairly common source of programming errors. This use of tagged unions can be formalized as a monad with the following functions:

where "value" and "err" are the constructors of the union type, A and B are valid result types and E is the type of error conditions. Alternately, the same monad may be described by return and two additional functions, fmap and join:

Классовые иерархии как маркированные союзы

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