Практика функционального программирования

Аннотация: Статья рассматривает важную идиому программирования — алгебраический тип данных (АТД). Приводится теоретическая база, которая лежит в основе практического применения АТД в различных языках программирования. Прикладные аспекты рассматриваются на языке функционального программирования Haskell, а также кратко на некоторых других языках программирования.

Algebraic Data Types (ADT) is an important programming idiom. A theoretical background is given that forms a foundation for practical application of ADT in various programming languages. Practical aspects of ADTs are discussed using Haskell and are also briefly outlined for certain other programming languages.

Обсуждение статьи ведётся по адресу
http://community.livejournal.com/fprog/2921.html.

Введение

В 1903 году английский математик Бертран Рассел предложил антиномию в рамках языка классической («наивной») теории множеств Георга Кантора, которая показала несовершенство введённого им определения множества: «множество есть многое, мыслимое как единое»¹ [10, 11]:

Пусть K — множество всех множеств, которые не содержат сами себя в качестве своего подмножества. Ответ на вопрос «содержит ли K само себя в качестве подмножества?» не может быть дан в принципе. Если ответом является «да», то, по определению, такое множество не должно быть элементом K. Если же «нет», то, опять же по определению, оно должно быть элементом самого себя.

В общем, куда ни кинь — всюду клин. Ситуация парадоксальна.

Данная антиномия (более известная под названием «парадокс Рассела») поколебала основы математики и формальной логики, что вынудило ведущих математиков того времени начать поиск методов её разрешения. Было предложено несколько направлений, начиная от банального отказа от теоретико-множественного подхода в математике и ограничения в использовании кванторов (интуиционизм, основоположником которого был голландский математик Лёйтзен Брауэр), до попыток аксиоматической формализации теории множеств (аксиоматика Цермело — Френкеля, аксиоматика Неймана — Бернайса — Гёделя и некоторые другие). На сегодняшний день аксиоматические теории множеств, дополненные аксиомой выбора или другими аналогичными аксиомами, как раз и служат одним из возможных оснований современной математики.

Позже австрийский философ Курт Гёдель показал, что для достаточно сложных формальных систем всегда найдутся формулы, которые невозможно вывести (доказать) в рамках данной формальной системы — первая теорема Гёделя о неполноте [7]. Данная теорема позволила ограничить поиски формальных систем, дав математикам и философам понимание того, что в сложных системах всегда будут появляться антиномии, подобные той, что предложил Б. Рассел.

В конечном итоге парадокс Рассела и запущенные им направления исследований в рамках формальных систем привели к появлению теории типов, которая, наряду с упомянутыми аксиоматическими теориями множеств и интуиционизмом, является одним из способов разрешения противоречий наивной теории множеств. Сегодня под теорией типов понимается некоторая формальная система, дополняющая наивную теорию множеств [12]. Теория типов описывает области определений и области значений функций — такие множества элементов, которые могут быть значениями входных параметров и возвращаемыми результатами функций. Общее понимание теории типов в рамках информатики заключается в том, что обрабатываемые данные имеют тот или иной тип, то есть принадлежат определённому множеству возможных значений².

В частности, решение приведённой в начале статьи антиномии было предложено самим Б. Расселом как раз в рамках теории типов. Решение основано на том, что множество (класс) и его элементы относятся к различным логическим типам, тип множества выше типа его элементов. Однако многие математики того времени не приняли это решение, считая, что оно накладывает слишком жёсткие ограничения на математические утверждения.

В рамках общей теории типов разработано определённое количество теорий, абстракций и идиом, описывающих различные способы представления множеств значений и множеств определений функций. Одна из них — алгебраический тип данных (другими важнейшими теориями в рамках дискретной математики являются комбинáторная логика, λ-исчисление и теория рекурсивных функций) [9, 14, 13]. Именно эта идиома и является предметом рассмотрения настоящей статьи, поскольку она имеет серьёзное прикладное значение в информатике в целом и в функциональном программировании в частности. К примеру, в языке Haskell любой непримитивный тип данных является алгебраическим.

Вместе с тем надо отметить, что в «чистой» математике типы рассматриваются как некие объекты манипуляции. Например, в типизированном λ-исчислении, в котором явно вводится понятие типа, типы изучаются исключительно как синтаксические сущности. Типы в типизированном λ-исчислении — это не «множества значений», а просто «бессмысленные» наборы символов и правила манипуляции ими.

К примеру, если говорить о простом типизированном λ-исчислении, то в нём даже нет констант типов вроде Int, Bool и т. д. Типы  λ-исчисления — это выражения специального вида, составленные из значков (→), (*) и круглых скобок «(» и «)» по простым правилам:

1. * — тип;
2. если α и β — типы, то (α → β) — тип.

Другими словами, типы — это строки вида * → (* → *) → *. Именно строки, а не множества значений. Иногда, конечно, вводят и константы типов, но принципиальной разницы это не вносит.

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

1  Мотивация

Перед рассмотрением теоретических основ АТД имеет смысл сравнить реализацию этой идиомы на языке программирования, в котором в явном виде это понятие отсутствует (например, язык семейства C) с описанием того же АТД на языке, где это понятие является естественным (наиболее «продвинутым» в отношении АТД является язык Haskell).

Например, пусть имеется задача реализовать тип данных, представляющий двоичное дерево³, при этом такой тип должен предоставлять разработчику возможности построить определённые дополнительные механизмы контроля внутренней структуры данных и доступа ним, к примеру — осуществлять проверки корректности значений, присваиваемых отдельным внутренним полям. Далее эти дополнительные требования к типам будут рассмотрены во всех подробностях.

Пусть имеется обычное определение структуры, при помощи которой выражается двоичное дерево (в таком дереве данные, по сути, хранятся только в узловых вершинах; «листовой» считается вершина, у которой оба поддерева пусты):

Этот вариант определения не совсем подходит для описанных целей, потому что для доступа к элементам этой структуры, а также для разнообразных проверок целостности и непротиворечивости, потребуется писать дополнительные функции⁴. Как бы сделать так, чтобы транслятор автоматически делал за разработчика «чёрную работу» по созданию вспомогательных программных конструкций?

Структуру Tree можно переопределить примерно следующим образом (впрочем, это — не совсем корректное переопределение, поскольку в этом случае данные будут храниться только в листовых вершинах, а не в любых вершинах дерева; тем не менее, такое переопределение вполне достаточно для целей статьи):

В этом определении имеются два взаимозависимых элемента: объединение data и перечисление selector. Первый элемент содержит данные об узле дерева, а второй идентифицирует тип первого элемента. Если в качестве значения в объединении data содержится поле value, то значением элемента selector должно быть LEAF. Соответственно, если в первом элементе находится структура branches, скрывающая в себе два указателя на такие же двоичные деревья (левое и правое поддерево), то во втором элементе должно быть значение NODE. Опять налицо необходимость иметь внешние по отношению к этому определению инструменты, которые следят за семантической непротиворечивостью значений типа⁵.

Разработчику придётся в явном виде писать примерно такие функции для доступа на запись к полям определённой выше структуры:

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

Итак видно, что определение типа Tree в языке типа C получилось достаточно громоздким, но при этом была решена важная задача — здесь явно определена возможность выбора между двумя альтернативами: (value, LEAF) и (branches, NODE). Такой тип позволяет, по сути, хранить совершенно разнородные данные в зависимости от своего назначения в каждом конкретном случае — для листовых элементов двоичного дерева хранятся числовые значения, для узловых — указатели на левое и правое поддеревья соответственно. Для понимания того, какой именно тип используется в каждом таком конкретном случае, имеются «метки» из перечисления selector. Но цена этого — дополнительные «метки» и множество явно описываемых проверок в функциях доступа.

А вот определение того же типа данных на языке программирования Haskell:

Это определение описывает тип, который может быть представлен двумя видами значений (все такие виды разделены символом вертикальной черты (|)). Первый вид значений, помеченный «меткой» Leaf, представляет собой целое число, хранимое в листовой вершине двоичного дерева. Второй вид значений — узловая вершина дерева, хранящая ссылки на левое и правое поддеревья (соответственно, используется метка Node).

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

Здесь переменная типов α является «заменителем» для любого другого типа (можно даже придумать ситуацию, когда в листовых вершинах двоичного дерева хранятся двоичные деревья и т. д. до бесконечности⁶). В языках типа C (C++, C#, Java и др.) для этих же целей можно воспользоваться шаблонами, и заинтересованный читатель может самостоятельно реализовать такой шаблон, а также функцию для контроля целостности значений к нему (после чего можно будет сравнить определения, хотя бы по количеству использованных скобок).

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

Можно подвести итоги о преимуществам АТД, выделив явные положительные моменты в использовании этой идиомы функционального программирования:

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

Для понимания отличительных особенностей и преимуществ АТД в программировании далее будут представлены теоретические аспекты этого понятия (с применением нескольких математических формул уровня первого курса технического вуза), после чего в двух последних разделах будут приведены способы реализации теоретического понятия в прикладных языках программирования. Основное повествование ведётся на языке Haskell, даётся краткое описание той части синтаксиса языка, которая связана с АТД. Для других языков программирования, где явно реализованы АТД, просто приводятся примеры определений.

2  Теоретические основы

В теории есть два способа описания АТД. Первый использует теоретико-множественный подход и соответствующую нотацию. Ознакомление с этим аспектом позволит уяснить, как именно развивалось это понятие, и как оно попало в информатику. Второй использует специально разработанную нотацию для так называемого синтаксически-ориентированного конструирования типов и функций для их обработки (нотация Ч. Хоара). Данная нотация позволяет уже более или менее читабельно описывать на математическом языке типы данных в рамках теории типов. Интересно видеть, как данная нотация была преобразована при реализации языков программирования.

2.1  Определение АТД

Алгебраический тип данных неформально можно определить как множество значений, представляющих собой некоторые контейнеры, внутри которых могут находиться значения каких-либо иных типов (в том числе и значения того же самого типа — в этом случае имеет место рекурсивный АТД). Множество таких контейнеров и составляет сам тип данных, множество его значений.

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

С теоретической точки зрения алгебраическим типом данных является размеченное объединение множеств (иначе называемое «дизъюнктным объединением»)⁷, под которым понимается видоизменённая классическая операция объединения — такая операция приписывает каждому элементу нового множества метку (или индекс), по которой можно понять, из какого конкретно множества элемент попал в объединение. Соответственно, каждый из элементов размеченного объединения в свою очередь является декартовым произведением некоторых иных множеств.

Пусть есть набор множеств A_i, i ∈ I, из которых создаётся их размеченное объединение. В этом случае под размеченным объединением понимается объединение пар:

Здесь (x, i) — упорядоченная пара, в которой элементу x приписан индекс множества, из которого элемент попал в размеченное объединение. В свою очередь каждое из множеств A_i канонически вложено в размеченное объединение, то есть пересечения канонических вложений A_i^* всегда пусты, даже в случаях, когда пересечения исходных множеств содержат какие-либо элементы. Другими словами, каноническое вложение имеет вид:

а потому

Итак, АТД — это размеченное объединение, то есть элементы такого типа с математической точки зрения представляют собой пары (x, i), где i — индекс множества (метка типа), откуда взят элемент x. Но чем являются сами элементы x? Теория говорит о том, что эти элементы являются декартовыми произведениями множеств, которые содержатся внутри контейнеров A_i. То есть, каждое множество A_i, из которых собирается размеченное объединение, является декартовым произведением некоторого (возможно, нулевого) числа множеств. Именно эти множества и считаются «вложенными» в контейнер АТД, вложение обеспечивает операция декартова произведения.

Другими словами, каждое множество A_i представляет собой декартово произведение:

где множества A_ik, k = 1, n являются произвольными (в том числе нет ограничений на рекурсивную вложенность). Поскольку элементами декартова произведения множеств являются кортежи вида

в целом АТД можно записать как

В общем случае декартово произведение вообще может быть представлено пустым кортежем. Тогда считается, что соответствующий контейнер A_i не содержит никаких значений внутри себя, а в размеченное объединение канонически вкладывается единственный элемент этого множества — ((), i). Данная ситуация возможна тогда, когда в АТД включается метка i ради самой себя, то есть в АТД содержится нуль-арное каноническое множество A_i^*, имеющее единственный элемент. Обычно это требуется для определения перечислений (эта ситуация и её реализация будут продемонстрированы далее в статье).

Для лучшего понимания того, что представляет собой АТД, можно представить общую формулу произвольного АТД в виде диаграммы. Сообразуясь с формулой 1, произвольный АТД можно изобразить так, как показано на рис. 1.

---

Рис. 1: Схема произвольного АТД

---

В качестве примера АТД в математической нотации можно рассмотреть тип Tree, введённый ранее:

Данный тип есть размеченное объединение двух множеств Leaf и Node, так что A₁ ≡ Leaf, A₂ ≡ Node. Множество A₁ есть декартово произведение одного произвольного множества a. Значения этого множества «упаковываются» в контейнер A₁. Соответственно, множество A₂ есть декартово произведение двух одинаковых множеств Tree(a), то есть налицо рекурсивное определение АТД.

2.2  Синтаксически-ориентированное конструирование

Как было показано выше, при создании АТД используются две операции: декартово произведение и размеченное объединение. Эти операции вместе с понятиями теории типов были взяты за основу так называемого синтаксически-ориентированного подхода к конструированию типов, предложенного Чарльзом Энтони Хоаром [1]. Дополнительно о типах в языках программирования можно прочесть в [5].

Данный подход предлагает более удобную нотацию для представления типов, нежели формальные математические записи в теоретико-множественной нотации. В данной нотации типы именуются словами английского языка, начинающимися с заглавной буквы, причём конкретные типы имеют вполне конкретные названия: List, Tree и т. д., а переменные типов (то есть такие обозначения, вместо которых можно подставлять произвольный тип) — просто буквы с начала алфавита, возможно с индексами: A, B, C₁, C_n и т. п.

Также в качестве ключевых слов в нотации Ч. Хоара используются слова constructors, selectors, parts и predicates (а также эти же слова в форме единственного числа). Данные ключевые слова используются для ввода наименований отдельных «элементов» АТД. Под «элементами» АТД понимаются различные сущности в составе типа — отдельные размеченные множества и типы, упакованные в контейнеры.

• Конструкторы (constructors) — это наименования функций, создающих декартовы произведения из состава АТД.
• Селекторы (selectors) — это специальные утилитарные функции, обеспечивающие получение отдельных значений из декартовых произведений.
• Части (parts) — наименования отдельных канонических множеств размеченного объединения.
• Предикаты (predicates) — функции, позволяющие идентифицировать принадлежность заданного значения конкретному множеству из состава размеченного объединения.

Далее в настоящем разделе каждый из этих элементов описывается более подробно.

Наконец, два символа, (+) и (×), используются для записи определений типов. Знак (+) обозначает размеченное объединение, а знак (×) используется для обозначения декартова произведения.

В качестве примера определения АТД в данной нотации можно привести классическое определение АТД «список элементов типа A»:
List(A) = NIL + (A × List(A))

nil, prefix = constructors List(A)
head, tail = selectors List(A)
NIL, nonNIL = parts List(A)
null, nonNull = predicates List(A)

Здесь A — произвольный тип данных, так называемая переменная типов, вместо которой в конкретных случаях можно подставлять любой необходимый тип. Например, если необходимо иметь список целых чисел, то достаточно подставить Int вместо всех вхождений символа A.

На представленном примере можно пояснить основные понятия нотации синтаксически-ориентированного конструирования. Первая строка определения описывает сам тип List(A). Список — это размеченное объединение пустого списка NIL и декартова произведения элемента типа A со списком таких же элементов. Значением типа List(A) может быть либо пустой список, либо непустой, который есть пара (декартово произведение двух множеств), первым элементом которой является значение обёртываемого типа, а вторым — список (в том числе и пустой). Это значит, что «в конце» каждого конечного списка должен находиться пустой список как базис рекурсии.

Следующие четыре строки определяют «элементы» АТД «список». Первая из них определяет два конструктора, каждый из которых соответствует одной из частей размеченного объединения. Конструктор nil создаёт пустой список NIL, конструктор prefix создаёт непустой список соответственно. Этот конструктор принимает на вход значение заданного типа и список, а возвращает пару, первым элементом которой является указанное значение, вторым — список. Следовательно, типы конструкторов можно определить так⁸:
#nil = List(A)
#prefix = A → (List(A) → List(A))

Таким образом, тип конструктора типа A_i, являющегося декартовым произведением типов A_i1, A_i2, … × A_in, определяется формулой:

то есть конструктор одного декартова произведения принимает на вход значения «оборачиваемых» типов (тех, которые помещаются в контейнер), а возвращает значение целевого, своего АТД⁹. Все части АТД, каждая из которых есть декартово произведение, имеют по одному конструктору. Сам АТД является в таком случае размеченным объединением частей, а части обозначаются ключевым словом parts.

Для всех конструкторов, которые создают «контейнеры», имеются так называемые селекторы. Селектор — это функция, которая возвращает одно определённое значение из контейнера. В случае типа List(A) селекторы есть только у части nonNIL (непустой список). Первый селектор head возвращает голову списка, то есть значение типа A, а второй tail — хвост списка, то есть второй элемент пары в декартовом произведении. Типы селекторов можно понять по их назначению:
#head = List(A) → A
#tail = List(A) → List(A)

Другими словами, каждый селектор имеет тип вида A → A_ik, и такой селектор принимает на вход значение типа АТД, а возвращает заданное значение из контейнера. Селекторы имеют место только для декартовых произведений, а для каждой части типа имеется столько селекторов, сколько типов упаковывается в соответствующий контейнер. Для каждой части типа верно следующее равенство, называемое «аксиомой тектоничности»¹⁰:

где s_i1, s_i2, … s_ini — селекторы соответствующих компонентов декартова произведения.

Уже упомянутые части типа — это множества, включённые в АТД посредством размеченного объединения. Для АТД определяются предикаты, при помощи которых можно выявить, к какому конкретно множеству в рамках размеченного объединения относится значение. Наличие таких предикатов — одно из свойств размеченности объединения. Соответственно, сколько в АТД частей, столько и предикатов. Части задаются ключевым словом parts, предикаты — predicates. Для предикатов верна следующая аксиома:

Наличие такой аксиомы необходимо для того, чтобы для произвольного значения АТД можно было выявить ту конкретную часть, к которой это значение принадлежит. Далее можно будет применять селекторы конкретной части (применение селекторов к значению из другой части приведёт к ошибке согласования типов — необходимо помнить о типе селекторов). Соответственно, при реализации в языках программирования такие предикаты позволяют использовать механизм сопоставления с образцом (подробно рассказывается ниже в разделе про язык Haskell).

Нотация Ч. Э. Хоара также позволяет представлять АТД в виде диаграмм, на которых представлено древовидное описание структуры АТД. Такие деревья состоят из двух или трёх уровней. На первом уровне изображается вершина АТД с его наименованием. На втором уровне перечисляются части типа. Если часть представляет собой декартово произведение, то для данной части на третьем уровне перечисляются типы компонентов части. Рёбра дерева, ведущие с первого на второй уровень, помечаются наименованиями предикатов. Соответственно, рёбра, ведущие со второго на третий уровень, помечаются наименованиями селекторов.

Произвольный АТД выглядит так, как показано на рис. 2.

---

Рис. 2: Древовидное представление АТД

---

В качестве примера представления АТД в виде дерева можно привести диаграмму для типа List(A), показанную на рис. 3. На приведённой диаграмме пунктирной линией показано рекурсивное включение типа List(A) в качестве одного из своих компонентов.

---

Рис. 3: Древовидное представление типа List(A)

---

2.3  Примеры описания АТД

В заключение теоретического введения можно привести ряд примеров определений различных АТД. Так, следующее определение используется для типа с поэтическим названием «розовый куст»¹¹:
Rose(A) = NIL + A × List(Rose(A))

nil, rose = constructors Rose(A)
node, branch = selectors Rose(A)
NIL, Rose = parts Rose(A)
null, isRose = predicates Rose(A)

Вот определение типа с названием «верёвка» (данный тип представляет собой список элементов с чередующимися типами A и B):
Rope(A, B) = NIL + B × (Rope(B, A))

nil, rope = constructors Rope(A, B)
element, twisted = selectors Rope(A, B)
NIL, Twist = parts Rope(A, B)
null, isTwisted = predicates Rope(A, B)

А вот и определение двоичного дерева, в вершинах которого находятся элементы типа A¹²:
Tree(A) = Empty + A × Tree(A) × Tree(A)

empty, node = constructors Tree(A)
element, left, right = selectors Tree(A)
Empty, Node = parts Tree(A)
isEmpty, isNode = predicates Tree(A)

Ну а определение двоичного дерева, приведенного в разделе 1, выглядит так:
Tree(A) = A + Tree(A) × Tree(A)

leaf, node = constructors Tree(A)
element, left, right = selectors Tree(A)
Leaf, Node = parts Tree(A)
isLeaf, isNode = predicates Tree(A)

Как видно из примеров, ничего особенно сложного в нотации синтаксически-ориентированного конструирования АТД нет. Стоит отметить, что абстрактная математическая нотация сегодня используется крайне редко, поскольку можно воспользоваться одним из языков программирования, в котором поддерживается понятие АТД.

3  АТД в языке программирования Haskell

Одним из языков программирования, где наиболее полно и близко к теории синтаксически-ориентированного конструирования представлены алгебраические типы данных, является функциональный язык Haskell. В связи с этим для изучения применения АТД в прикладном программировании имеет смысл обратить пристальное внимание на синтаксис этого языка. Далее в этом разделе будет кратко рассмотрен общий вид определения АТД с некоторыми примерами, пояснён механизм сопоставления с образцами, а также приведена классификация АТД.

3.1  Общий вид определения АТД в языке Haskell

Как уже упоминалось, в языке Haskell любой непримитивный тип данных является алгебраическим¹³. АТД вводятся в программу при помощи ключевого слова data, использование которого определяется следующим образом [2]:

data [context =>]   simpletype = constrs   [deriving],

где:

• context — контекст применения переменных типов (необязательная часть определения);
• simpletype — наименование типа с перечислением всех переменных типов, использующихся во всех конструкторах АТД (если переменные типов не используются, то ничего не указывается);
• constrs — перечень конструкторов АТД, разделённых символом (|) (данный символ соответствует операции размеченного объединения);
• deriving — перечень классов, для которых необходимо автоматически построить экземпляры определяемого типа (необязательная часть определения).

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

Наименование АТД и все его конструкторы по обязательным соглашениям о наименовании, принятым в языке Haskell, должны начинаться с заглавной буквы. Наименование типа и наименования его конструкторов находятся в разных пространствах имён, поэтому в качестве наименования одного из конструкторов можно вполне использовать слово, являющееся наименованием всего типа (эта ситуация часто используется в случаях, когда у определяемого АТД один конструктор). После наименования типа, как уже было сказано, должны быть перечислены все переменные типов, использующиеся в конструкторах, причём переменные типов опять же по соглашениям должны начинаться со строчной буквы (обычно в практике используются начальные буквы латинского алфавита — a, b и т. д., в некоторых специальных нотациях языка используются строчные греческие буквы α, β и т. д.).

В некоторых случаях конструктор АТД может иметь специальное наименование, составленное из небуквенных символов. Для определения такого конструктора его наименование должно начинаться с символа двоеточия (:). Способ использования подобных конструкторов ограничен — они должны быть бинарными и использоваться в инфиксной форме (то есть располагаться между своими аргументами). Впрочем, любой бинарный конструктор, как и произвольная бинарная функция, может быть записан в инфиксной форме посредством заключения его наименования в обратные апострофы (‘). Возвращаясь к конструкторам с небуквенными наименованиями, можно отметить, что сам символ (:) является одним из конструкторов типа «список». Его формальное определение таково:

Это определение не является правильным с точки зрения синтаксиса языка Haskell, но оно вшито в таком виде в ядро языка, чтобы вид списков в языке был более или менее удобным для восприятия (таким образом, переопределить конструктор (:) нельзя). Если определять список самостоятельно, то определение этого типа будет выглядеть примерно так:

Как можно заметить, каждый конструктор типа начинается с заглавной буквы (Nil и List), причём второй конструктор совпадает по наименованию с наименованием всего типа (как уже сказано, наименования типов и их конструкторов лежат в разных пространствах имён и употребляются в различных контекстах, поэтому неоднозначностей в интерпретации наименований не возникает, чем удобно воспользоваться). Первый конструктор пустой, зато второй определяет декартово произведение двух типов: некоторого типа α (здесь символ α — переменная типов) и типа List α, причём в данном случае в качестве аргумента конструктора используется наименование АТД. Это важно чётко понимать для уяснения сути определения. Определение могло бы быть переписано таким образом (второй конструктор называется в традиции языка Lisp):

А вот как, к примеру, определяется специальный тип для представления обычных дробей (данный тип определён в стандартном модуле Prelude)¹⁴:

Здесь, как видно, применён бинарный инфиксный конструктор. Этот конструктор принимает на вход два значения, а возвращает их связанную упорядоченную пару. Данная пара является представлением дроби. Соответственно, для значений этого типа определены такие селекторы (наименования приведенных функций переводятся с английского языка как «числитель» и «знаменатель» соответственно):

Из этих определений видно, что функции-селекторы как бы раскладывают АТД на элементы, возвращая тот из них, который требуется по сути функции. Другими словами, селекторы в языке Haskell аналогичны функциям-аксессорам или операторам доступа к полям данных в других языках программирования. Например, запись «denominator n» в языке Haskell аналогична записи «n.denominator()» в языке Java.

3.2  Сопоставление с образцом

Представленные выше функции numerator и denominator показывают один важнейший механизм, реализованный в языке Haskell — сопоставление с образцами. Этот механизм используется в языке в нескольких аспектах, одним из главных является сопоставление с образцами при определении функций. Этот аспект необходимо рассмотреть более внимательно.

«Образцом» называется выражение, в котором некоторые или все поля декартова произведения (если декартово произведение не пусто, то есть конструктор не представляет собой простую метку размеченного объединения) заменены свободными переменными¹⁵ для подстановки конкретных значений таким образом, что при сопоставлении происходит означивание параметров образца — однозначное приписывание переменным образца конкретных значений. Для АТД образцом является указание одного из конструкторов с перечислением переменных или конкретных значений в качестве его полей.

Сопоставление с образцом проходит следующим образом. Из всех клозов функции¹⁶ выбирается первый по порядку, сопоставление со всеми образцами которого произошло успешно. Успешность заключается в корректном сопоставлении конкретных входных аргументов функции с соответствующими образцами. Сопоставление, как уже сказано, должно происходить однозначно и непротиворечиво. Константа сопоставляется только с такой же константой, свободной переменной в образце присваивается конкретное значение.

Этот процесс можно пояснить на примере. Пусть есть определение функции:

Здесь первая строка является сигнатурой, описывающей тип функции, вторая и третья — два клоза функции head соответственно. Сигнатура функции может не указываться в исходных кодах, так как строго типизированный язык Haskell имеет механизмы для однозначного вычисления типа любого объекта в наиболее общей форме (соответственно, наличие или отсутствие сигнатур функций не влияет на их работоспособность). Впрочем, многие разработчики говорят о том, что наличие сигнатур функций рядом с определениями позволяет более чётко понимать смысл и суть функции.

Первый клоз определяет значение функции в случае, если на вход функции подан пустой список. Как видно, функция предназначена для возвращения первого элемента («головы») списка, а потому для пустого списка её применение ошибочно. Используется системная функция error. Второй клоз применим для случаев, когда список не является пустым. Непустой список, как уже говорилось в теоретической части — это пара, первым элементом которой является некоторое значение, а вторым — список оставшихся элементов, «хвост» списка. В языке Haskell эти элементы декартова произведения соединяются при помощи конструктора (:), что и представлено в образце. Две свободные переменные — x и xs — это параметры образца, которые получают конкретные значения в случае корректного применения функции. Например:

сопоставит с переменной x конкретное значение 1, а с переменной xs — значение [2, 3]. Соответственно, результатом выполнения функции будет значение переменной x, то есть 1.

Приведённый пример можно понимать и по-другому. Раз список есть пара, созданная при помощи конструктора (:), то список [1, 2, 3] может быть представлен как (1:[2, 3]), а ещё вернее как (1:(2:(3:[]))). В данном случае вызов head [1, 2, 3] приведёт к следующей последовательности вычислений:

или, что то же самое:

В конечном итоге, поскольку свободная переменная xs не участвует в вычислении результата, оптимизирующий транслятор языка, основанного на ленивых вычислениях, проведёт такое преобразование¹⁷:

Итогом вычислений будет значение переменной x, то есть 1.

Теперь можно рассмотреть более сложный пример. Пусть определён АТД для представления бинарного дерева (такой же, как в теоретической части):

Вот функция, которая вычисляет максимальную глубину заданного дерева. Уже по виду определения АТД можно сказать, что у неё должно быть не менее двух клозов, по одному на каждый конструктор АТД:

Первый клоз функции определяет её значение для первого конструктора АТД Tree, то есть для пустого дерева. Второй клоз определяет значение функции уже для непустого дерева. У непустого дерева есть хранимый в узле элемент и два поддерева — левое и правое. Функции depth хранимый в узле элемент неинтересен, а потому в образце применена «маска подстановки» для неиспользуемых элементов АТД — (_). Этот символ при сопоставлении с образцами означает, что на его место может быть подставлено всё, что угодно. Кроме того, это единственный символ, который можно использовать несколько раз в одном образце. Два других компонента конструктора Node, l и r, сопоставляются с левым и правым поддеревьями соответственно.

Процесс сопоставления с образцом устроен таким образом, что не требует от значений АТД быть быть величинами, над которыми определена операция сравнения¹⁸ — возможность выбора конкретной части АТД обеспечивается наличием предикатов (необходимо вспомнить аксиому для предикатов АТД). Вместе с тем это накладывает дополнительные ограничения — нельзя написать определение функции, подобное следующему:

Здесь во втором клозе в образцах переменная x используется два раза, что недопустимо в образцах.

Таким образом, при сопоставлении с образцом происходит сравнение конструктора поданного на вход функции значения с конструктором в образце. Это значит, что технология сопоставления с образцом является очень мощной и гибкой при определении функций — она не требует явного определения функций сравнения величин.

3.3  Классификация АТД

Остаётся кратко упомянуть о дополнительной классификации АТД в языке Haskell. При помощи АТД определяются любые типы данных, включая те, для которых в других языках программирования имеются отдельные ключевые слова. Например, простое перечисление на языке Haskell выражается как АТД, все конструкторы которого пусты:

Декартовым типом называется такой АТД, который имеет только один конструктор декартова произведения (иногда декартов тип называют также типом-произведением). Приведённый ранее пример типа Ratio представляет собой декартов тип. Обычно декартовы типы используются для определения записей с именованными полями. Для этих целей в языке Haskell имеется специальная синтаксическая конструкция:

В приведённом случае транслятором языка будут автоматически сгенерированы функции доступа к перечисленным полям декартова типа, имеющие такие же наименования, как и поля. Так, если есть переменная ts типа Timestamp, то вызов выражения year ts позволит получить из этой переменной значение первого поля в декартовом произведении. Использование выражения ts\{year = 1984\} позволяет установить значение первого компонента декартова произведения. Символ равенства (=) здесь означает не присваивание, а копирование объекта с установкой в определённых полях новых значений (впрочем, оптимизирующие трансляторы могут действительно делать замену в соответствующих ячейках памяти в случаях, если известно, что старый объект больше не будет использован).

Ещё одним специфическим АТД является тип-сумма. Такой тип состоит из набора конструкторов, каждый из которых «обёртывает» только одно значение. Ближайшим аналогом такого типа в языках типа C является объединение (ключевое слово union). Например:

data SourceCode = ISBN String -- Код книги.
                | ISSN String -- Код периодического издания.

Наконец, осталось упомянуть, что приведённое деление АТД на типы в языке Haskell достаточно условно. Никто не запрещает сделать АТД, в котором тринадцать конструкторов будут пустыми, а четырнадцатый представлять собой структуру с именованными полями. Таким образом видно, что сама по себе концепция АТД позволяет достаточно гибко представлять типы данных в языках программирования.

Более подробно с АТД и методиками программирования на языке Haskell с их применением можно ознакомиться в книге [8].

4  АТД в других языках программирования

Помимо рассмотренного в предыдущем разделе языка Haskell  концепция АТД явно реализована в следующих языках программирования (перечень дан по алфавиту)¹⁹:

• F#;
• Hope;
• Nemerle;
• OCaml и большинство языков семейства ML;
• Scala;
• Visual Prolog.

В этом разделе кратко рассмотрены особенности использования АТД в перечисленных языках программирования.

В языке программирования F# АТД реализованы ограниченно исключительно в виде безопасных с точки зрения типизации размеченных объединений (union), то есть все АТД в языке F# являются типами-суммами. Например:

Язык Hope стал первым языком программирования, в котором концепция АТД и механизм сопоставления с образцами были реализованы в полной мере. Этот язык вдохновлял разработчиков последующих языков программирования — Miranda и Haskell. Синтаксис языка Hope достаточно необычен, но само понятие АТД отражено в нём в полном объёме. Для размеченного объединения используется символ (++), для декартова произведения — символ (#). Типы в декартовых произведениях заключаются в скобки. Например, для бинарного дерева АТД определяется так:

Язык Nemerle является C-подобным языком программирования для платформы .NET, основное достоинство которого заключается в поддержке как объектно-ориентированной, так и функциональной парадигм программирования (впрочем, язык Haskell также позволяет это делать, особенно его объектно-ориентированные потомки Mondrian, O’Haskell и Haskell++). АТД в языке Nemerle называются вариантами и полностью соответствуют теории синтаксически-ориентированного конструирования Ч. Э. Хоара. Синтаксис же несколько необычен для C-подобного языка:

Как видно, размеченному объединению соответствует символ (|), а декартову произведению — символ (;). Наименования полей в декартовых произведениях обязательны.

Язык OCaml является одним из серии языков ML, который использует функциональную, объектно-ориентированную и процедурную парадигмы программирования. Само семейство языков ML имеет достаточно серьёзный вес в мире функционального программирования, а потому без реализации АТД в этих языках не обошлось²⁰. В этом языке, как и в языке Haskell, применяется параметрический полиморфизм (использование переменных типов).

Вот как, к примеру, определяется АТД для представления колоды карт:

Теоретическая концепция АТД реализована в OCaml в полном объёме. Размеченное объединение как обычно представляется символом (|), а декартово произведение — символом (*). В АТД могут быть как пустые декартовы произведения, так и полноценные, а также их произвольная комбинация.

Язык Scala является Java-подобным мультипарадигменным языком программирования (как обычно заявляются объектно-ориентированная, функциональная, процедурная парадигмы). АТД в этом языке реализованы достаточно своеобразно при помощи концепции класса. Тем не менее эта реализация полностью соответствует теории. Для представления АТД и использования технологии сопоставления с образцами используется специальный вид классов:

Декларации за ключевыми словами case class являются таким специальным видом классов, каждый из которых представляет конструктор декартова произведения того АТД, также представимого в виде класса, который он расширяет. Синтаксис достаточно необычен, но о позволяет использовать всю силу концепции АТД.

Если case class Expression объявить как sealed, то компилятор сможет проверять полноту разбора случаев при сопоставлении с образцом типа Expression, зато в противном случае разработчик сможет расширять множество выражений, добавив, к примеру, тип выражений Product. Таким образом, Scala поддерживает модульные декларации case class, но может и давать определенные гарантии корректности.

Наконец, язык Visual Prolog является наследником логического языка Prolog, в котором реализована объектно-ориентированная парадигма программирования, а также некоторые особенности функциональной парадигмы. Данный язык позволяет реализовывать графические приложения при помощи описания логики их работы в виде предикатов.

В этом языке для определения типов используется понятие «домен», то есть область определения предиката. Можно определять сложные домены так, чтобы предикаты могли принимать значения любого типа, а не не только true и false («истина» и «ложь»). При определении домена в виде АТД символ (;) используется для размеченного объединения, а (,) —для декартова произведения, причём элементы последнего должны быть заключены в круглые скобки после наименования конструктора. Вот пара примеров:

В данном примере домен category является перечислением, составленным из четырёх констант. Домен tree представляет собой обычный АТД, состоящий из трёх конструкторов, первые два из которых представляют собой декартовы произведения двух соответствующих компонентов.

Таков краткий обзор реализаций концепции АТД в различных языках программирования. Он демонстрирует, что АТД могут быть успешно использованы в различных подходах к построению программных средств.

Заключение

Алгебраические типы данных являются достаточно мощным и универсальным средством для описания структур данных при программировании. Понимание теоретических основ этой концепции позволит прикладным программистам глубже осознавать процессы, происходящие в разрабатываемых ими программных средствах. Более того, на практике, концепция АТД во многих случаях даёт разработчикам программных средств возможность избавиться от синтаксического мусора в определениях типов и увидеть суть структур данных на ранних этапах разработки программ.

Список литературы

[1]

Hoare C. A. R. Dahl O.-J., Dijkstra E. W. Structured Programming. Academic Press, 1972.

[2]

Jones S. P. et al. Haskell 98 Language and Libraries. The Revised Report. Academic Press, 2002.

[3]

Cantor G. Beitrage zur Begrundung der transfiniten Mengenlehre. Math. Ann., 46, 1895.

[4]

Robin Milner. A calculus of communicating systems. Springer (LNCS 92), 1980.

[5]

Benjamin C. Pierce. Types and Programming Languages. MIT Press, 2002. (имеется перевод книги на русский язык http://newstar.rinet.ru/~goga/tapl/).

[6]

Зефиров С. А. Лень бояться. Журнал «Практика функционального программирования», 1(1), 2009.

[7]

Успенский В. А. Теорема Гёделя о неполноте. Наука, М., 1982.

[8]

Душкин Р. В. Справочник по языку Haskell. ДМК Пресс, М., 2008.

[9]

Клини С. К. Введение в метаматематику. ИЛ, М., 1957.

[10]

Гарднер М. А ну-ка, догадайся! Мир, М., 1984.

[11]

Розанова М.С. Современная философия и литература. Творчество Бертрана Рассела. Издательский дом Санкт-Петербургского государственного университета, СПб., 2004.

[12]

Уайтхед А. Н. Основания математики. Изд-во «Самарский университет», Самара, 1954.

[13]

Петер Р. Рекурсивные функции. ИЛ, М., 1954.

[14]

Вольфенгаген В. Э. Методы и средства вычислений с объектами. Аппликативные вычислительные системы. АО «Центр ЮрИнфоР», М., 2004.

1

Впрочем, Г. Кантор дал достаточно чёткое математическое определение множества [3]:
Unter einer «Menge» verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objekten m unserer Anschauung oder unseres Denkens (welche die «Elemente» von M genannt werden) zu einem Ganzen.
«Под «множеством» мы понимаем произвольную коллекцию M в целом, состоящую из отдельных объектов m (которые называются «элементами» M»), которые существуют в нашем представлении или мыслях». Данное определение показывает, что Г. Кантор заложил основы перехода математики от туманных размышлений к точным символическим формулировкам.

2

Вместе с тем, типы в информатике появились из-за необходимости сопоставлять идентификатору внутреннее представление идентифицируемого объекта. Типы в информатике и типы в математике — это немного разные понятия. Понятие типов в информатике основано на математическом понятии, но не совсем тождественно ему (имеются расширения, необходимые для практических применений). Робин Милнер, автор и главарь разработчиков функционального языка ML, был одним из первых, кто попытался применить математические типы для выбора внутреннего представления программных сущностей [4], что породило определённую путаницу.

3

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

4

Например, для данного конкретного определения необходимо написать служебную функцию проверки того, что указатели l и r ненулевые, а если и нулевые, то эта ситуация корректна (нулевые указатели на дочерние поддеревья могут быть только у листовых вершин).

5

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

6

В информатике такие деревья называются «деревьями высшего порядка» (англ. high-order trees).

7

Для заинтересованных читателей имеет смысл дать англоязычное наименование термина — tagged union или disjoint union.

8

Запись #x означает «тип значения x» (в теории типов функции также имеют типы, поэтому в качестве значения x может выступать и функция).

9

Здесь необходимо отметить, что в теории и функциональном программировании имеется понятие «обобщённого алгебраического типа данных» (ОАТД), конструкторы которого могут в общем случае возвращать значения не своего типа.

10

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

11

Необходимо отметить, что тип Rose(A) взят из Standard Template Library. Этот тип являются достаточно широко используемым контейнерным типом. Впрочем, в STL имеются определения огромного количества контейнерных типов, заинтересованному читателю рекомендуется использовать STL для оттачивания своих навыков в определении АТД. Это поможет дополнительно осознать преимущества и выгоды АТД.

12

Это определение отличается от того определения двоичного дерева, которое рассмотрено в начале статьи — здесь в каждом узле дерева находится определённое значение, а листовые вершины отличаются от узловых тем, что оба поддерева пусты.

13

Впрочем, с одной стороны, примитивные типы также могут быть представлены в виде конечных или бесконечных перечислений, что делает возможным их определение посредством АТД. С другой стороны, в языке Haskell имеется понятие «функциональный тип», то есть тип функции как программной сущности (не тип значения, возвращаемого функцией, а именно тип функции). Примеры функциональных типов приведены в теоретическом разделе (см., например, стр. ??); в языке программирования Haskell используются именно такие типы функций.

14

Определение, конечно, несколько иное, но, как было заявлено ранее, особенности системы типизации языка Haskell в настоящей статье рассматриваться не будут.

15

Свободной называется такая переменная, которая встречается в теле функции, но при этом не является параметром этой функции.

16

Клозом (от англ. clause) называется одна запись в определении, определяющая значение функции для конкретного набора входных параметров.

17

О ленивой стратегии вычислений можно прочесть в статье [6] и дополнительных источниках, в том числе перечисленных в указанной статье.

18

В терминах Haskell — типы не обязаны быть экземплярами класса Ord.

19

В список не включён язык Miranda как прародитель языка Haskell. В этих языках синтаксис для определения АТД практически совпадает.

20

Собственно, некоторые концепции уже упомянутого языка F# также были основаны на языке OCaml, что видно из синтаксиса

Этот документ был получен из L^AT_EX при помощи H^EV^EA

© 2009—2011  «Практика функционального программирования»ISSN 2075-8456