Понимание алгебраических данных и типов кодат в функциональном программировании
7 июля 2025 г.Таблица ссылок
Введение
Перевод на последовательное исчисление
2.1 Арифметические выражения
2.2 Пусть привязки
2.3 Определения верхнего уровня
2.4 Алгебраические данные и типы кодов
2.5 первоклассные функции
2.6 Операторы управления
Оценка в контексте
3.1 Контексты оценки для развлечения
3.2 Сосредоточение внимания на оценке в сердечнике
Правила печати
4.1 Правила печати для развлечения
4.2 Правила печати для Core
4.3 Тип. Звукость
Понимание
5.1 Контексты оценки являются первым классом
5.2 Данные двойные до кодата
5.3 LET-связы
5.4 Трансформация случая
5.5 Прямой и косвенный потребители
5.6 Позвоните в запас, вызовов и eta-laws
5.7 Линейная логика и двойственность исключений
Связанная работа
Заключение, заявление о доступности данных и подтверждение
A. Взаимосвязь с последовательным исчислением
B. Правила набора развлечений
C. Оперативная семантика лейбла/goto
Ссылки
2.4 Алгебраические данные и типы кодов
Теперь мы расширяем веселье и основное с двумя новыми функциями: алгебраические данные и типы кодат. Алгебраические типы данных знакомы с большинства типичных языков функционального программирования. Типы алгебраических кодат [Hagino 1989] немного более необычны; Они определяются набором наблюдений или методов, называемых деструкторами и очень похожи на интерфейсы в объектно-ориентированном программировании [Cook 2009]. Мы вводим их обоих в одном и том же разделе, потому что они помогают проиллюстрировать некоторые глубокие теоретические двойственности и симметрию последовательного исчисления и 𝜆𝜇𝜇 𝜆𝜇𝜇-калькулуса.
Чтобы познакомиться с нашим синтаксисом, давайте сначала кратко рассмотрим два коротких примера. Следующее определение рассчитывает сумму по списку, которую он получает в качестве входных данных.
дефектСумма (𝑥) ≔случай𝑥из{Nil ⇒ ⌜0⌝, минусы (𝑦, 𝑦𝑠) ⇒ 𝑦 + sum (𝑦𝑠)}
Это происходит путем сопоставления шаблонов с использованием случая ... {...} конструкции, которая является совершенно стандартной. В качестве примера типов кода, рассмотрите это определение:
дефектПовторите (𝑥) ≔коказ{hd ⇒ 𝑥, tl ⇒ repeat (𝑥)}
Он строит бесконечный поток, элементы которого все такие же, как вход 𝑥 функции. Поток определяется двумя деструкторами, HD дает головку потока, а TL дает оставшийся поток без головы. Поток сконструирован сопоставлением Copattern [Abel et al. 2013] Использование Cocase {...} Construct.
2.4.1 Типы данных.Давайте рассмотрим другой пример, чтобы лучше понять общий синтаксис:
дефектСмена (𝑥) ≔случай𝑥из{Tup (𝑦, 𝑧) ⇒ tup (𝑧, 𝑦)}
В ядре, алгебраические типы данных в основном обрабатываются так же, как и в веселье. Основное отличие заключается в том, что проверка больше не является частью выражения случая. Вместо этого выражение случая является потребителем, а проверка - производитель, который затем объединяется в утверждении. Это именно то, что делается в переводе. Когда случай и конструктор встречаются, существует возможность для вычисления, потребление построенного термина и продолжая с соответствующей правой стороны выражения случая. Это также объясняет нашу терминологию производителей и потребителей. Конструкторы создают или, другими словами, создают структуры данных, в то время как случаи разрушают или употребляют их.
Однако есть еще одна разница. Конструкторы в ядре теперь также могут принимать потребителей в качестве аргументов, которые не так уж и веселья. Примером этого является тип отрицания типа 𝜏, который может быть сформулирован как тип данных с одним конструктором, принимающим потребителя типа 𝜏 в качестве аргумента. Программа, использующая этот тип, можно найти в разделе 7.2 Ostermann et al. [2022].
Веселье-это язык по вызову, который проявляется в том, что значение алгебраического типа данных состоит из конструктора, применяемого к другим значениям. Случай выражения случая 𝑡 {. Полем .} может быть оценен только в том случае, если проверка 𝑡 является значением, поэтому это означает, что это должен быть конструктор, аргументы которых являются значениями в правиле оценки.
Оценка в ядре проводится так же, только с измененным термином проверки, чтобы стать производителем сокращения. Обратите внимание, что все потребители в ядре являются ковалентами (поэтому аргументы деструкторов в определении ковалеев не являются шрифтом Fraktur), поэтому для того, чтобы термин конструктора был значением, только его аргументы производителя должны быть значениями. Это также означает, что требование о том, чтобы потребительские аргументы конструктора были ковалентными, несущественно удовлетворены правилом оценки в ядре.
Пример 2.4.Перевод свопа (включая упрощение) дается
def Swap (𝑥; 𝛼) ≔ ⟨𝑥 | case {tup (𝑦, 𝑧) ⇒ ⟨tup (𝑧, 𝑦) | 𝛼⟩}⟩
Оценка с аргументом TUP (⌜2⌝, ⌜3⌝) и ⋆ затем продолжается, как мы ожидаем
⟨Tup (⌜2⌝, ⌜3⌝) | case {tup (𝑦, 𝑧) ⇒ ⟨tup (𝑧, 𝑦) | ⋆⟩}⟩ ⊲tup (⌜3⌝, ⌜2⌝) | ⋆⟩
2.4.2 Типы кодат.Чтобы продемонстрировать синтаксис для кодатов дальше, рассмотрим определение
def Swap_lazy (𝑥) ≔ Cocase {fst ⇒ 𝑥.snd, snd ⇒ 𝑥.fst}
Для развлечений кода, проверка расположена в термине деструктора вместо коказы, обратной для типов данных. Так что теперь деструкторы - это потребители, а коказы являются производителями. Это отражается в переводе, который снова разделяет проверку, поскольку в основных типах кодат и сопоставление Copattern идеально двойные к типам данных и сопоставлению рисунков.
Все деструкторы, которые мы использовали здесь, не имеют параметров производителя, но это просто из -за выбора примеров. В следующем разделе мы увидим пример деструктора с параметром производителя. Более того, во время перевода каждый деструктор наделен дополнительным параметром потребителя, который снова определяет, как выполнение продолжается после вызова деструктора (и, таким образом, связано окружающим 𝜇). Для конструкторов это не требуется, так как мы можем использовать одну и ту же переменную потребителя непосредственно в каждой ветви случая (аналогично IFZ [2]), потому что проверка и случай находятся в одном и том же выражении. Десрукторы (а также конструкторы) в ядре могут иметь даже более одного параметра потребителя. Пример этого приведен в разделе 5.7.
Оценка проводится аналогично типам данных, с ролями случаев и конструкторов обращаются вспять для кокасов и деструкторов. Обратите внимание, однако, что для оценки в ядре аргументы производителя деструктора также должны быть ценностями, поэтому для деструктора недостаточно быть ковалом (каким он всегда есть). Мы вернемся к этой тонкости в разделе 3.
Пример 2.5.Перевод SWAP_LAZY выполняется аналогично для обмена.
def swap_lazy (𝑥; 𝛼) ≔ ⟨cocase {fst (𝛽) ⇒ ⟨𝑥 | SND (𝛽)⟩, SND (𝛽) ⇒ ⟨𝑥 | fst (𝛽)⟩} | 𝛼⟩
Теперь возьмите 𝑝 = Cocase {fst (𝛼) ⇒ ⟨⌜1⌝ | 𝛼⟩, snd (𝛼) ⇒ ∗ (⌜2⌝, ⌜3⌝; 𝛼)} и оценить Swap_lazy с SND, чтобы получить свой первый элемент:
swap_lazy (𝑝; snd (⋆)) ⊲ ⟨cocase {fst (𝛽) ⇒ ⟨𝑝 | SND (𝛽)⟩, SND (𝛽) ⇒ ⟨𝑝 | fst (𝛽)⟩} | SND (⋆)⟩
⊲ ⟨𝑝 | fst (⋆)⟩ ⊲ ⟨⌜1⌝ | ⋆⟩
Поскольку коказы являются ценностями независимо от их правых сторон (в отличие от конструкторов), мы можем применить Destructor SND без сначала оценивая продукт ∗ (⌜2⌝, ⌜3⌝; 𝛼). Для пар мы не могли этого сделать, так как TUP (⌜1⌝, ∗ (⌜2⌝, ⌜3⌝; 𝛼)) не является значением, поэтому его аргументы должны быть оцениваются в первую очередь. Вот почему этот тип Codata называется Lazy Pair, поскольку он позволяет не оценивать свое содержимое в отличие от обычных пар.
Этот раздел показал важное свойство Core, которое не придерживается удовольствия. Данные и типы кодов ядра полностью симметричны: синтаксис для случаев такой же, как и синтаксис для коказы, и то же самое относится и к конструкторам и деструкторам. Причиной этой глубокой симметрии является та же самая причина, которая делает последовательное исчисление более симметричным, чем естественным выводом, но в определении 2.5 мы можем наблюдать его на языке программирования.
Авторы:
(1) Дэвид Биндер, Университет Тюбингена, Германия;
(2) Марко Цшенке, Университет Тюбингена, Германия;
(3) Мариус Мюллер, Университет Тюбингена, Германия;
(4) Клаус Остерманн, Университет Тюбингена, Германия.
Эта статья есть
[2] Мы могли бы также смоделировать IFZ в качестве случая, моделируя числа как тип данных. Но поскольку IFZ совсем напрямую соответствует инструкции машины, естественно сделать его утверждением, как объяснено в разделе 2.1.
Оригинал