2009 → Выпуск 3

Полиморфизм в языке Haskell

Душкин Роман

Аннотация:
Статья предлагает к рассмотрению одно из мощнейших и перспективных средств программирования — полиморфизм, — на примере его использования в функциональном языке программирования Haskell. Описаны различные виды полиморфизма: параметрический со своими подвидами, а также перегрузка имён функций (так называемый «ad-hoc полиморфизм», или «специальный полиморфизм»).

Polymorphism is perceived to be one of the most powerful programming concepts. Various types of polymorphism are known: parametric, name overloading, ad-hoc or special, to name a few. This article provides comprehensive description of all of them, with illustrations in Haskell.

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

Введение

Статья продолжает цикл публикаций, посвящённых системе типов, принятой в функциональной парадигме программирования. Данный цикл начат в статье [19] во втором выпуске журнала.

Полиморфизм (от греч. πολύ — «много» и μορφή — «форма», «многообразный») в программировании — это возможность использования в одном и том же контексте различных программных сущностей (объектов, типов данных и т. д.) с одинаковым интерфейсом.

С самого начала применения понятия «полиморфизм» в информатике и программировании были теоретически обоснованы и разработаны различные виды полиморфизма. На рис. 1 приведена общая классификация видов полиморфизма, основанная на работах [6, 10, 13].

Рис. 1: Классификация видов полиморфизма в языках программирования

Изначально полиморфизм в языках программирования был неформально описан британским учёным К. Стрейчи в своих лекциях [12], после чего уже американский учёный области компьютерных наук Дж. Рейнольдс формально классифицировал полиморфизм на два больших типа [11]: параметрический полиморфизм и ad-hoc полиморфизм (специальный полиморфизм). Ранние работы Дж. Рейнольдса и французского логика Ж.-И. Жирара [7] ввели в научный оборот типизированное λ-исчисление второго порядка (так называемая «система F»). В дальнейшем формальная система F стала основой для использования параметрического полиморфизма в таких функциональных языках программирования, как Haskell и ML [10]. Наконец, голландский логик Х. П. Барендрегт, известный своими фундаментальными работами по λ-исчислению [16, 5], ввёл в научный оборот понятие λ-куба, при помощи которого структуризировал 8 систем типов, используемых как в теории, так и на практике [4].

Приведённым на диаграмме видам полиморфизма можно дать следующие упрощённые определения:

Универсальный полиморфизм (universal polymorphism) — в противоположность специальному полиморфизму, объединяет параметрический полиморфизм и наследование в один вид полиморфизма в соответствии с [6]. Мы вводим понятие «универсального полиморфизма» в дополнение к классификации полиморфизма, данной в лекциях [12].
1. Параметрический полиморфизм (parametric polymorphism) — это возможность определения обобщённых структур данных и функций, поведение которых не зависит от типов значений, которыми они оперируют. В случае типов данных (конкретнее, алгебраических типов данных, которые, как показано в [19], можно интерпретировать в качестве контейнерных типов) значения произвольных типов могут тем или иным образом использоваться внутри контейнеров (непосредственно содержаться в контейнерах, либо содержимое контейнеров будет иметь какую-либо зависимость от таких произвольных типов¹). В случае функций именно поведение функции не зависит от типов передаваемых таким функциям значений в качестве входных параметров.
  Классификация параметрического полиморфизма основана на ограничении ранга полиморфизма и на ограничении использования типовых переменных (по аналогии с терминами «строковая переменная», «булевская переменная» и др.). Впрочем, параметрический полиморфизм может реализовываться и без использования типовых переменных в принципе.
  1. Непредикативный полиморфизм (impredicative polymorphism) — позволяет инстанцировать типовые переменные при конкретизации произвольными типами, в том числе и полиморфными.
  2. Предикативный полиморфизм (predicative polymorphism) — в отличие от непредикативного полиморфизма инстанцирование типовых переменных при конкретизации типа может производиться только неполиморфными (мономорфными) типами, которые иногда называются «монотипами».
  3. Полиморфизм ранга * (rank * polymorphism) — вместо символа подстановки * могут использоваться значения «1», «k» и «N». В полиморфизме первого ранга (этот тип полиморфизма ещё называют «предварённым полиморфизмом» или «let-полиморфизмом») типовые переменные могут получать конкретные значения мономорфных типов. Полиморфизм ранга k предполагает, что в формулах, описывающих λ-термы, квантор всеобщности (∀) может стоять не более чем перед k стрелками. Данный класс полиморфизма выделен потому, что при k = 2 проблема вывода типов разрешима, в то время как при k > 2 эта проблема неразрешима. Наконец, полиморфизм высшего ранга (или полиморфизм ранга N) определяется тем, что кванторы всеобщности могут стоять перед произвольным количеством стрелок.
2. Наследование (subtyping polymorphism или inclusion polymorphism) — в объектно-ориентированном программировании классы (объекты) могут наследовать свойства классов-родителей так, что с точки зрения использования классы-потомки имеют те же самые наименования методов и свойств (а в случае, когда не используются перегруженные виртуальные методы, потомки имеют и те же самые реализации методов). В других парадигмах программирования под наследованием могут пониматься несколько иные средства языков программирования.
Специальный (ad-hoc) полиморфизм (ad-hoc polymorphism), который ещё называется полиморфизмом специального вида или «перегрузкой имён», позволяет давать одинаковые имена программным сущностям с различным поведением. Такой полиморфизм широко используется в математике, когда сходные математические операции получают одни и те же знаки (например, арифметические знаки (+), (-), (×) и (/) используются для обозначения операций сложения, вычитания, умножения и деления соответственно для произвольных чисел — целых, вещественных, комплексных и др.).
1. Перегрузка (overloading) — объединяющее понятие, которое включает в себя ограниченный полиморфизм и перегрузку имён функций.
  1. Ограниченный полиморфизм (bounded polymorphism) — регламентирует отношение «тип — подтип», когда ограниченно полиморфный тип должен быть подтипом некоторого более общего типа. В частном случае на типовые переменные накладываются ограничения, выглядящие как набор интерфейсных функций, которые должны быть определены для типов, потенциально участвующих в подстановке. Тем самым для полиморфного типа определяется набор функций, идентификаторы которых одинаковы для всех конкретных типов, которые могут быть подставлены в полиморфный тип при конкретизации. В функциональном программировании ограниченный полиморфизм часто используется совместно с параметрическим.
  2. Перегрузка имён функций (function names overloading) — перегрузка имён в смысле C++, когда разные функции с одинаковыми идентификаторами могут принимать разные наборы аргументов различных типов. Все такие функции должны быть определены до компиляции. Каждая такая функция при компиляции получает новый идентификатор, который зависит от количества и типов её аргументов.
2. Приведение типов (coercion) — неявное приведение типов операндов при передаче их значений в функции. В языке C++ можно, например, складывать значения типов int и float, при этом значения типа int будут неявно преобразованы компилятором к типу float так, чтобы результат сложения также был этого типа.

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

1 Параметрический полиморфизм в языке Haskell

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

В качестве примера можно привести сигнатуры некоторых функций, работающих со списками значений:

reverse :: [α] -> [α]

В этом примере функция reverse принимает на вход одно значение, которое имеет тип «список элементов типа α».

append :: [α] -> [α] -> [α]

Функция append принимает на вход уже два таких параметра. Здесь важно то, что оба входных параметра и результат, возвращаемый функцией, имеют один и тот же тип, а потому алгебраический тип данных «список» параметризуется одной и той же переменной.

zip :: [α] -> [β] -> [(α, β)]

Третья функция, zip, принимает на вход списки, элементы которых могут иметь различные типы. Результатом работы этой функции является список пар, первое значение в которых имеет тип такой же, как и у элементов первого списка, а второе значение имеет тип такой же, как и элементы второго списка. Само собой разумеется, что данные типы могут как совпадать, так и быть различны, на что указывает использование двух различных переменных типов — α и β.

Другими словами, для параметрического полиморфизма вводится формализация, которая позволяет связывать не только простые переменные, но и типовые переменные. Ранее была упомянута «система F», которая и предлагает такую формализацию. Данная система вводит дополнительную нотацию и семантику для λ-исчисления, при помощи которой вводятся типовые переменные. В этой нотации запись #x = α следует читать как «значение x имеет тип α». Например, для тождественной функции λ x.x запись с указанием типа α аргумента x выглядит следующим образом:

# Λ α.λ x^α.x = ∀ α.α → α (1)

Данная запись обозначает, что в сигнатуру функции λ x.x вводится типовая переменная α (данная переменная вводится при помощи символа (Λ), поскольку она определяет тип значений, то есть сущность более высокого порядка, нежели простые значения, переменные для которых вводятся при помощи символа (λ)). Вместо этой переменной α может быть подставлен любой конкретный тип данных при конкретизации функции, например, (((λ x.x)_Integer)1), где 1 — это элемент множества целых чисел. Здесь вместо типовой переменной α при вычислении результата будет подставлен тип Integer.

Квантор всеобщности (∀) в формуле 1 обозначает, что тип α может быть любым, на него не накладывается никаких ограничений. Ограничения на используемые типы тесно связаны с ad-hoc полиморфизмом и будут рассмотрены в следующем разделе.

В языке Haskell используется непредикативный параметрический полиморфизм первого ранга (для стандарта Haskell-98 [8]). Специализированные расширения компилятора GHC позволяют использовать непредикативный параметрический полиморфизм высших рангов. Далее в примерах будет показан только полиморфизм, согласующийся со стандартом Haskell-98, а полиморфизм высших рангов и его реализация в языке Haskell будут рассмотрены в будущих статьях.

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

Простой список значений произвольного типа определяется просто (необходимо напомнить, что в стандарте Haskell-98 определена специальная синтаксическая форма для удобной работы со списком):

data List α = Nil | Cons α (List α)

Здесь типовая переменная α может принимать произвольное значение. При её инстанцировании она может быть замещена любым другим типом данных, но стандарт Haskell-98 предполагает, что этот тип данных уже будет мономорфным. Не должно вводить в заблуждение то, что в языке Haskell можно обрабатывать списки списков, списки деревьев, списки функций, списки действий ввода-вывода; при этом уровень вложенности может быть не ограничен, так что можно обрабатывать и списки списков списков и т. д. Такое состояние дел относится к любому полиморфному типу данных, в определении которого используются типовые переменные.

Дальнейшие примеры. Двусвязный список можно определить так:

data LList α = Nil | LCons (LList α) α (LList α)

Данное определение с точностью до наименования конструкторов и порядка следования элементов декартова произведения в конструкторе LCons совпадает с определением двоичного дерева:

data Tree α = Nil | Node α (Tree α) (Tree α)

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

Также имеет смысл отметить, что реализация двусвязного списка в языке Haskell должна быть ленивой. Это связано с тем, что конструктор этой структуры данных вполне может замкнуть двусвязный список в «кольцо» так, что ни начала, ни конца уже будет не найти. Получится структура, аналогичная бесконечному односвязному списку List, а бесконечные структуры данных всегда должны обрабатываться лениво. Детально о методиках обработки таких структур данных в языке Haskell можно ознакомиться на официальном сайте языка [2].

Ассоциативный массив может быть реализован как в виде специального вида списка, так и в виде отдельного типа данных (впрочем, отдельный тип данных в этом примере использовать нецелесообразно):

type AArray α β = [(α, β)] data AArray α β = ANil | AArray α β (Aarray α β)

Дерево произвольной степени ветвления определяется примерно так же, как и двоичное:

data ATree α = ANil | ANode α [ATree α]

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

data MTree α β = MTree α [MEdge α β] data MEdge α β = MEdge β (MTree α β)

Наконец, список значений двух различных типов, при этом на нечётных позициях находятся значения первого типа, а на чётных значения второго типа (так называемая «верёвка», которая используется даже в стандартной библиотеке C++):

data Rope α β = Nil | Twisted α (Rope β α)

Может показаться, что в языке Haskell используется полиморфизм второго ранга. Если в качестве типовых переменных подставляются такие же полиморфные типы, то, вполне вероятно, могут возникать такие примеры, как список двоичных деревьев, который определяется следующим образом:

type ListOfTrees α = [Tree α]

Либо дерево произвольной размерности, в узлах которого находятся списки:

type TreeOfLists α = ATree [α]

В этих случаях при инстанцировании типовой переменной α происходит подстановка не полиморфного, а мономорфного типа Tree α или [α] соответственно, при этом типовая переменная α уже связана полученным инстанцированием контейнерного полиморфного типа.

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

Для закрепления материала осталось дать примеры определений утилитарных функций, работающих с подобными полиморфными типами данных. Далее рассматриваются определения функций, сигнатуры которых приведены в начале статьи — reverse, append и zip.

reverse :: [α] -> [α] reverse [] = [] reverse (x:xs) = append (reverse xs) [x]

Как видно из этого примера, функция reverse совершенно не принимает во внимание тип значений, которые хранятся в передаваемом ей на вход списке. Эти значений могут быть произвольного типа, функции reverse абсолютно всё равно, какой список обращать. Всё, что она делает, это разбивает входной список на элементы и соединяет их в обратном порядке, используя для этого функцию для конкатенации двух списков append, определение которой выглядит так:

append :: [α] -> [α] -> [α] append [] l = l append (x:xs) l = x:(append xs l)

Функция append также не обращает внимания на типы значений во входных списках. Главное, чтобы они были одинаковыми, поскольку результирующий список должен состоять из элементов обоих входных списков. Одинаковость типов значений в двух входных и результирующем списках определяется тем, что в сигнатуре функции указана одна типвая переменная α. В качестве примера использования нескольких типовых переменных можно привести определение следующей функции:

zip :: [α] -> [β] -> [(α, β)] zip (x:xs) (y:ys) = (x, y) : (zip xs ys) zip _ _ = []

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

Таким образом, видно, что параметрический полиморфизм позволяет определять типы и функции, которые реализуют обобщённые алгоритмы обработки структур данных, не зависящие от конкретных типов обрабатываемых значений. Данная техника позволяет разработчику программного обеспечения рассматривать код на более высоком уровне абстракции, не углубляясь в принципы обработки конкретных типов. В совокупности с техникой разработки сверху вниз [15] параметрический полиморфизм позволяет разработчику существенно повысить эффективность своей работы.

2 Ad-hoc полиморфизм в языке Haskell

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

Впервые на подобный вид полиморфизма указали в своей работе [6] Л. Карделли и П. Вегнер. Причина введения ограниченного полиморфизма была в том, что некоторые функции требуют от используемых в них типов значений наличия определённой семантики, реализуемой посредством специальных функций из интерфейса. Подобные ситуации с требованиями к типам данных возникают постоянно в различных задачах.

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

В языке Haskell для этих целей используются классы типов.

Класс типов представляет собой интерфейс, то есть набор сигнатур функций без определений². В определениях алгебраических типов данных и сигнатурах функций можно указывать ограничения на используемые типовые переменные (именно об этом было упомянуто в статье [19] при рассмотрении структуры определения алгебраических типов). Такие ограничения означают, что соответствующая переменная типов должна инстанциироваться только такими типами, для которых реализованы функции класса.

Предлагается рассмотреть такой пример. Кроме обычной аристотелевой логики с двумя значениями истинности, в математике разработаны альтернативные логики; например, многозначные логики Я. Лукасевича [9] или бесконечнозначная нечёткая логика Л. А. Заде [14]. Несмотря на разнообразие построенных логических теорий, все они должны отвечать одинаковым фундаментальным требованиям. Это и есть их «интерфейс». К нему относятся базисные логические операции — обычно это операции отрицания, конъюнкции и дизъюнкции. На языке Haskell этот факт описывается следующим образом:

class Logic α where not :: α -> α (&&) :: α -> α -> α (||) :: α -> α -> α

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

test_deMorgan :: (Eq α, Logic α) => α -> α -> Bool test_deMorgan x y = (not (x && y)) == ((not x) || (not y))

Теперь значения любого типа данных, который может представлять логические значения истинности и допускает сравнение значений на равенство, могут быть переданы на вход функции test_deMorgan для проверки. Конечно, данная функция проверяет правило де Моргана только для двух конкретных значений, а не для всей области определения логических значений истинности, принятой в конкретной логической теории, но на данном примере можно понять смысл ad-hoc полиморфизма в языке Haskell.

Итак, сигнатура функции test_deMorgan требует, чтобы для типовой переменной α были реализованы функции not, (&&) и (||) — это требование записывается как Logic α в контексте сигнатуры (другое ограничение, Eq α, требует наличия операций сравнения для типа α). Разработчик может использовать три упомянутые операции без всяких сомнений — их наличие для типа α гарантировано. Если эти операции не определены, то код просто не скомпилируется.

Как же использовать новый класс и утилитарную функцию test_deMorgan к нему? Для этого необходимо определить так называемый экземпляр класса для заданных типов данных, для которых требуется исполнения указанного интерфейса. Первым типом, для которого необходимо определение экземпляра класса Logic, является тип Bool. Экземпляр определяется следующим образом:

instance Logic Bool where not False = True not True = False True && True = True _ && _ = False False || False = False _ || _ = True

Здесь видно, что для типа Bool определяются уже конкретные реализации интерфейсных функций, описанных в классе Logic. При вызове нашей функции

> test_deMorgan True True True > and $ map (uncurry . test_deMorgan) [(x, y) | x <- [True, False], y <- [True, False]] True

автоматически выбираются конкретизированные функции (&&) и (||), реализованные для типа Bool. Заинтересованные читатели могут самостоятельно попытаться реализовать экземпляры класса Logic для типов, представляющих другие виды значений истинности (для этого также придётся определить и сами типы данных, представляющие значения альтернативных логик).

В этом и проявляется ad-hoc полиморфизм в языке Haskell. Класс Logic может быть связан со многими типами данных, но для всех них будут использоваться методы классов с абсолютно одинаковыми наименованиями. Перегрузка идентификаторов функций налицо.

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

class (Eq α, Show α) => Num α where (+) :: α -> α -> α (-) :: α -> α -> α (*) :: α -> α -> α negate :: α -> α abs :: α -> α signum :: α -> α fromInteger :: Integer -> α x - y = x + negate y negate x = 0 - x

Как видно, ограничения на типовые переменные могут находиться не только в сигнатурах функций, но и в определениях классов и типов. Здесь приведены два ограничения — тип α должен иметь функции для сравнения величин (класс Eq) и функции для преобразования величин в строку (класс Show). Далее приводятся сигнатуры семи функций (в том числе трёх инфиксных операций), которые должны быть определены для любого типа, который будет удовлетворять требованиям ограничений на возможность производить арифметические операции. Чтобы минимизировать количество определений конкретизированных функций, можно выражать одни интерфейсные функции через другие. Так, разность выражается через сложение с отрицанием, а отрицание выражается через разность. Само собой разумеется, что при определении экземпляра необходимо реализовать либо метод negate, либо операцию (-) — что-то одно выражается через другое. Например, можно определить тип для представления комплексных чисел, над которыми определены арифместические операции, после чего определить для этого типа экземпляр класса Num. В этом случае к значениям типа для комплексных чисел можно будет применять все перечисленные ранее интерфейсные функции из класса Num. Это делается следующим образом:

data Num α => Complex α = Complex α alpha

instance Num α => Num (Complex α) where (Complex x1 y1) + (Complex x2 y2) = Complex (x1 + x2) (y1 + y2) (Complex x1 y1) - (Complex x2 y2) = Complex (x1 - x2) (y1 - y2) ...

Может показаться, что понятие класса в функциональном программировании соответствует понятию интерфейс в программировании объектно-ориентированном. Действительно, можно провести некоторые аналогии, хотя имеются и серьёзные отличия. Подробно о подобии и различии между классами типов и интерфейсами можно ознакомиться в книге [18] и статье [17], а также на официальном сайте языка Haskell [1]. Также дополнительно о проблемах, которые могут возникать при использовании специального полиморфизма, можно ознакомится в статье [13].

3 Полиморфизм в других языках программирования

Б. Страуструп, автор языка C++, назвал полиморфизм одним из четырёх «столпов объектно-ориентированного программирования» [21] (другие столпы — абстракция, инкапсуляция и наследование)³. Все современные объектно-ориентированные языки программирования реализуют полиморфизм в том или ином виде. Ниже будут приведены более конкретные примеры.

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

Начать рассмотрение примеров можно с ad-hoc полиморфизма, как наиболее широко распространённой техники в языке C++. С одной стороны имеет место перегрузка имён функций, когда функции, получающие на вход значения различных типов, могут иметь одинаковые наименования. Этот случай не очень интересен в рамках настоящей статьи, поскольку на самом деле здесь имеет место только поверхностное, внешнее проявление ad-hoc полиморфизма — функции имеют одинаковые наименования только для разработчика. Транслятор языка преобразует такие одинаковые имена функций во внутреннее представление, в котором учитываются и типы получаемых на вход параметров.

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

Приводить примеры определения иерархии классов в языке C++ смысла нет — читатели могут найти их в любом учебнике по этому языку или какому-либо подобному языку программирования. Более интересным является использование в языке C++ так называемых шаблонов. Вся библиотека STL для языка C++ реализована при помощи этого механизма, что и немудрено, поскольку большинство типов в этой библиотеке являются контейнерными, а от контейнерных типов естественно ожидать возможность хранить внутри себя значения произвольных типов. Шаблоны могли бы стать для языка C++ средством реализации именно параметрического полиморфизма, поскольку в них используется обычное для такого типа полиморфизма понятие типовой переменной. Однако, к сожалению, шаблоны стали лишь «синтаксическим сахаром» для сокращения исходного кода при определении одинаковых функций, работающих с различными типами данных, поскольку компилятором языка все шаблоны «разворачиваются» в многочисленные определения программных сущностей по одной для каждого использованного в исходном коде типа. Для более детального понимания, что это такое, можно рассмотреть несколько примеров.

Например, вот как определяется в библиотеке STL тип «двусвязный список»:

template<class T> class list;

Здесь идентификатор T используется в качестве типовой переменной, которая определяет тип значений, которые будут храниться внутри таких двусвязных списков. Второй параметр (типовая переменная) шаблона Allocator в рассмотрении настоящей статьи не важен, так как относится к модели управления памятью в языке C++. Определение методов шаблонного класса list не принимает во внимание действительный тип значений, которые хранятся в списке, но оперируют именно типовой переменной T. Это позволяет хранить в списке значения произвольного типа, абсолютно также, как это происходит и для функциональных языков — при определении такого списка в нём специфицируется конкретный тип хранимых значений (определяется двусвязный список целых чисел):

std::list<int> primes;

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

int sum (std::list<int> iList) { int result = 0; for (std::list<int>::iterator i = iList.begin (); i != iList.end (); ++i) { result += *i; } return result; }

А как быть, если необходима функция, которая возвращает сумму вещественных чисел? Её определение практически идентично приведённому ранее:

float sum (std::list<float> iList) { float result = 0.0; for (std::list<float>::iterator i = iList.begin (); i != iList.end (); ++i) { result += *i; } return result; }

Как видно, обе функции различаются только типом значений — значений элементов входного списка и возвращаемого значения. Более того, в определении этих двух функций уже используется полиморфизм операции (+) в языке C++. Это значит, что, в принципе, можно написать обобщённую функцию для сложения значений произвольных типов — главное, чтобы для них была определена операция сложения (ну и заодно должно быть определено начальное нулевое значение). На помощь приходят шаблоны:

template<class T> T sum (std::list<T> iList) { T result = 0; for (std::list<T>::iterator i = iList.begin (); i != iList.end (); ++i) { result += *i; } return result; }

Главная проблема, которая возникает при использовании такой функции, заключается в том, что необходимо каким-то образом контролировать наличие определённой операции сложения для типа T. В принципе, компилятор языка поможет в этом вопросе, выдав сообщения об ошибках в случаях, когда необходимые определения отсутствуют, но тем не менее разработчик должен помнить, что необходимо реализовать требуеме операции. Но как быть в случае, например, необходимости написания функции, которая «сворачивает» заданный список в конечное значение при помощи переданной на вход бинарной операции? Здесь уже надо немного исхитриться:

template<class T> typedef T (*binary) (T, T); template<class T> T foldl (list<T> iList, T zero, binary<T> op) { T result = zero; for (std::list<T>::iterator i = iList.begin (); i != iList.end (); ++i) { result = (*op) (result, *i); } return result; }

Таким образом, шаблоны в языке C++ представляют собой удобное средство краткого описания многочисленных определений. И хотя, как уже сказано в языке C++ шаблоны, которые могли бы стать проявлениями параметрического полиморфизма в полной мере, компилятором преобразуются в наборы функций с перегруженными именами, для разработчика внешне такие шаблоны являются одним из способов реализации именно параметрического полиморфизма. Также в дополнение к библиотеке STL можно рекомендовать к изучению библиотеку Boost, в которой реализовано множество функциональных алгоритмов и контейнерных типов данных. Для изучения методов метапрограммирования на языке C++ при помощи шаблонов рекомендуется книга [3].

Ту же самую задачу, что представлена выше, но в более правильном свете, решают так называемые «генерики» (англ. generics) в языке Java или C#. Заинтересованный читатель может попытаться решить представленную задачу на языках, которые он использует в своей практике. Автор и редакция журнала будут благодарны читателям, которые пришлют свои решения. Лучшие решения будут опубликованы на официальном web-сайте журнала.

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

sum_int :: [Int] -> Int sum_int l = sum_int' l 0 where sum_int' [] r = r sum_int'(i:is) r = sum_int' is (r + i)

sum_float :: [Float] -> Float sum_float l = sum_float' l 0 where sum_float' [] r = r sum_float'(f:fs) r = sum_float' fs (r + f)

sum :: Num α => [α] -> α sum [] = error "No elements in input list." sum (x:xs) = sum' xs x where sum' [] r = r sum'(y:ys) r = sum' ys (r + y)

foldl :: (α -> β -> α) -> α -> [β] -> α foldl f z l = foldl' l z where foldl' [] r = r foldl' (x:xs) r = foldl' xs (f r x)

Несколько моментов требуют пояснения:

Во всех вышеперечисленных определениях используется идиома аккумулятора (накапливающего параметра), который реализован через определение локальной функции (часть после ключевого слова where). Данная технология позволяет выполнять вычисления в постоянном объёме памяти несмотря на рекурсию. Аккумулятором называется один из входных параметров локальной функции (в данных примерах — r), в котором накапливается результат вычислений.
Ограничение Num α в сигнатуре функции sum поразумевает, что для типа α определены арифметические операции, в том числе и операция (+) (как это было показано в предыдущем разделе). К сожалению, этот класс не определяет нулевого элемента в типе (это делает класс Monoid, детальное рассмотрение которого приведено в статье [20]), поэтому функции sum приходится использовать в качестве нулевого элемента голову списка. С этим и связано то, что для пустого списка функция не определена (при попытке такого вызова выводится сообщение об ошибке).
Функция foldl определена в стандартном модуле Prelude (там её определение несколько отличается, здесь форма определения видоизменена для единообразия). Операция свёртки широко используется в обработке списков. Более того, определение свёртки можно расширить для произвольного рекурсивного типа данных.

Заключение

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

Одной из таких проблем является хранение в алгебраических типах данных значений произвольных типов. Например, список может содержать значения не только одного конкретного типа (список целых чисел, список строк, список деревьев с размеченными дугами и т. д.), но и произвольный набор произвольных значений. В языке Lisp такой список является естественной структурой данных, однако язык Haskell стандарта Haskell-98 с его строгой типизацией не позволяет создавать подобные структуры.

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

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

[1]: Oop vs type classes. Статья в Haskell Wiki (en), http://www.haskell.org/haskellwiki/OOP_vs_type_classes.
[2]: Tying the knot. Статья в Haskell Wiki (en), http://www.haskell.org/haskellwiki/Tying_the_Knot.
[3]: David Abrahams and Aleksey Gurtovoy. C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond (C++ in Depth Series). Addison-Wesley Professional, 2004.
[4]: H. P. Barendregt. Introduction to generalized type systems. J. Funct. Program., 1(2):125–154, 1991.
[5]: H. P. Barendregt. Lambda calculi with types. pages 117–309, 1992.
[6]: Luca Cardelli and Peter Wegner. On understanding types, data abstraction, and polymorphism. ACM Computing Surveys, 17:471–522, 1985.
[7]: Jean-Yves Girard, Yves Lafont, and Paul Taylor. Proofs and Types, volume 7 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1989.
[8]: Simon P. et al. Jones. Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, December 2002.
[9]: Jan Łukasiewicz. Aristotle’s Syllogistic from the Standpoint of Modern Formal Logic. Oxford University Press, 1987.
[10]: Benjamin C. Pierce. Types and Programming Languages. The MIT Press, Cambridge, Massachusetts, 2002. в сети Интернет по адресу http://newstar.rinet.ru/~goga/tapl/ опубликован перевод книги на русский язык.
[11]: John C. Reynolds. Theories of programming languages. Cambridge University Press, New York, NY, USA, 1999.
[12]: Christopher Strachey. Fundamental concepts in programming languages. Higher Order Symbol. Comput., 13(1-2):11–49, 2000.
[13]: Philip Wadler and Stephen Blott. How to make ad-hoc polymorphism less ad hoc. In 16’th ACM Symposium on Principles of Programming Languages, Austin, Texas, January 1989.
[14]: L. A. Zadeh. Fuzzy sets and systems. In Fuzzy Sets Fuzzy Logic and Fuzzy Systems: Selected Papers by Lofti A. Zadeh, Advances in Fuzzy Systems-Application and Theory Vol 6, World Scientific, pages 35–43, 1965.
[15]: Астапов Д. Е. Давно не брал я в руки шашек. «Практика функционального программирования», 1(1):51–76, 2009.
[16]: Барендрегт Х. П. Ламбда-исчисление. Его синтаксис и семантика. М.: Мир, 1985.
[17]: Душкин Р. В. Объектно-ориентированное и функциональное программирование. «Потенциал», 26(2):40–50, 2007.
[18]: Душкин Р. В. Функциональное программирование на языке Haskell. М.: ДМК Пресс, 2007.
[19]: Душкин Р. В. Алгебраические типы данных и их использование в программировании. «Практика функционального программирования», 2(2):86–105, 2009.
[20]: Пипони Д. Моноиды в Haskell и их использование. «Практика функционального программирования», 1(1):77–86, 2009. «Haskell Monoids and their Uses», пер. с англ. К. В. Заборского.
[21]: Страуструп Б. Язык программирования C++. М.: Бином, 1999.

1: В качестве примера параметризуемого алгебраического типа данных, в котором значения типа-параметра не содержатся, а используются иным образом, можно привести несколько надуманное, но имеющее смысл и право на существование определение data Function a b = F (a -> b).
2: Здесь необходимо дополнительно отметить, что в языке Haskell можно задавать определения интерфейсных функций, используемые по умолчанию. Такие определения будут использованы тогда, когда для некоторого типа данных определения функций опущены.
3: Б. Страуструп в этом определении имел в виду именно специальный полиморфизм, который был изначально реализован в языке C++. Как уже показано, специальный полиморфизм — это не единственный вид полиморфизма, а потому создатель языка C++ говорил о более узком понятии, чем то, которое описывается в настоящей статье.
4: Также надо отметить, что в определённых объектно-ориентированных языках программирования для некоторых видов определений перекрытие методов классов-родителей в классах-потомках обязательно.
5: Необходимо отметить, что свёртка — это широко используемая идиома в функциональном программировании, причём определяемая не только для списков, но и в общем для произвольных рекурсивных типов данных. При помощи свёртки списка можно выразить очень многие функции над списком, результатом которых является одиночное значение. Например, сумма элементов списка sum может быть выражена через свёртку как sum = foldl (+) 0.

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

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