Полиморфизм (информатика)

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Полиморфизм (программирование)»)
Перейти к: навигация, поиск
Парадигмы программирования
 • Императивная
(контрастирует с декларативной)
Процедурная
Структурная
Аспектно-ориентированная
Объектно-ориентированная
Агентно-ориентированная
Компонентно-ориентированная
Прототипно-ориентированная
Обобщённое программирование

 • Декларативная
(контрастирует с императивной)

Чистота языка
Чистота функции
Функциональная
В терминах Рефал-машины
Аппликативная
Комбинаторная
Бесточечная[en]
(чистая конкатенативная)
Логическая
Ограничениями

 • Конкатенативная
 • Векторная[en]
 • Метапрограммирование

Языково-ориентированная
Предметно-ориентированная
Пользователями[en]
Автоматизация процесса программирования
Рефлексивность
Гомоиконность[en]

 • Связанные темы

Программирование в крупном и мелком масштабе[en]
Модульность
Полиморфизм
Продолжения и CPS[en]*
Параллелизм и конкурентность

 • Методы и алгоритмы

Автоматное
Динамическое
Потоков данных
Событийно-ориентированное
Реактивное
Сервис-ориентированное

В языках программирования и теории типов полиморфизмом называется способность функции обрабатывать данные разных типов[1][2][3].

Существует несколько разновидностей полиморфизма. Две наиболее различных из них были описаны Кристофером Стрэчи[en] в 1967 году: это ad hoc полиморфизм>>> и параметрический полиморфизм>>>.

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

Определение полиморфизма как «один интерфейс — много реализаций», популяризованное Бьерном Страуструпом[4], относится к ad hoc полиморфизму, но в действительности, ad hoc полиморфизм не является истинным полиморфизмом[5]>>>.

Общие сведения[править | править вики-текст]

Полиморфизм является фундаментальным свойством системы типов. Различают[6] статическую неполиморфную типизацию (потомки Алгола и BCPL), динамическую типизацию (потомки Lisp, Smalltalk, APL) и статическую полиморфную типизацию (потомки ML). Использование ad hoc полиморфизма наиболее характерно для неполиморфной типизации. Параметрический полиморфизм и динамическая типизация намного существеннее, чем ad hoc полиморфизм, повышают коэффициент повторного использования кода, поскольку определенная единственный раз функция реализует без дублирования заданное поведение для бесконечного множества вновь определяемых типов, удовлетворяющих требуемым в функции условиям. С другой стороны, временами возникает необходимость обеспечить различное поведение функции в зависимости от типа параметра, и тогда необходимым оказывается специальный полиморфизм.

Параметрический полиморфизм>>> является синонимом абстракции типа[7]. Он повсеместно используется в функциональном программировании, где он обычно обозначается просто как «полиморфизм».

В сообществе объектно-ориентированного программирования под термином «полиморфизм» обычно подразумевают наследование, а использование параметрического полиморфизма называют обобщённым программированием[8], или иногда «статическим полиморфизмом».

Классификация[править | править вики-текст]

Впервые классификацию разновидностей полиморфизма осуществил Кристофер Стрэчи[en]>>>.

Если параметру функции сопоставлен ровно один тип, то такая функция называется мономорфной. Многие языки программирования предоставляют синтаксический механизм для назначения нескольким мономорфным функциям единого имени (идентификатора). В этом случае, в исходном коде становится возможным осуществлять вызов функции с фактическими параметрами разных типов, но в скомпилированном коде фактически происходит вызов различных функций (см. перегрузка процедур и функций). Стрэчи[en] назвал такую возможность «ad hoc полиморфизмом»>>>.

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

В дальнейшем классификацию уточнил Лука Карделли[en][9], выделив четыре разновидности полиморфизма:

Джон Митчел[10] выделяет три разновидности полиморфизма как независимые: параметрический>>>, ad hoc>>> и подтипов>>>[11].

Латинский фразеологизм «ad hoc» (буквально «к случаю») имеет двойственное значение:

  • 1) спонтанный, непродуманный, сделанный «на коленке»
  • 2) специальный, устроенный конкретно для данной цели или данного случая

Двойственность содержания термина «ad hoc полиморфизм» долгие годы была заслуженной[12]. Стрэчи выбрал этот термин, руководствуясь первым значением — в работе он подчеркивает, что при ad hoc полиморфизме нет единого систематичного способа вывести тип результата из типа аргументов, и хотя возможно построение определённого набора правил для сужения спектра его поиска, но эти правила по своей природе являются спонтанными как по содержанию, так и по контексту применения[1].

Действительно, ad hoc полиморфизм не является истинным полиморфизмом[5]. Перегрузка функций даёт не «значение, имеющее множество типов», а «символ, имеющий множество типов», но значения, идентифицируемые этим символом, имеют разные (потенциально не совместимые) типы. Аналогично, приведение типов не является истинным полиморфизмом: кажется, будто оператор принимает значения множества типов, но значения должны быть преобразованы к некоторому представлению до того, как он сможет их использовать, так что на самом деле оператор работает лишь над одним типом (то есть имеет один тип). Более того, тип возвращаемого значения здесь не зависит от типа входного параметра, как в случае параметрического полиморфизма.

Тем не менее, определение специальных реализаций функций для разных типов в некоторых случаях является необходимостью, а не случайностью. Классическими примерами служат реализация арифметических операций (физически различная для целых и чисел с плавающей запятой) и равенства типов[en], которые на протяжении десятилетий не имели общепринятой универсальной формализации. Решением стали классы типов>>>, представляющие собой механизм явного дискретного перечисления допустимых значений переменных типа для статической диспетчеризации в слое типов. Это сводит воедино две разновидности полиморфизма, разделённые Стречи, и «делает ad hoc полиморфизм менее ad hoc»[12] (игра на двойственности смысла).

В отличие от перегрузки и приведения типов, полиморфизм подтипов[en]>>> является истинным полиморфизмом: объектами подтипа можно манипулировать единообразно, как если бы они они принадлежали к своим супертипам (но сказанное не верно для языков, реализующих «полиморфизм при наследовании» посредством приведения типов, как в случае С++). Наиболее чистым является параметрический полиморфизм>>>: один и тот же объект или функция может единообразно использоваться в разных контекстах типизации без изменений, приведений типов или любых других проверок времени исполнения или преобразований. Однако, для этого требуется некое единообразное представление данных (например, посредством указателей).[13]

Основные разновидности полиморфизма[править | править вики-текст]

Ad hoc полиморфизм[править | править вики-текст]

Ad hoc полиморфизм (в русской литературе чаще всего переводится как «специальный полиморфизм» или «специализированный полиморфизм», хотя оба варианта не всегда верны>>>) поддерживается во многих языках посредством перегрузки функций и методов, а в слабо типизированных — также посредством приведения типов.

В следующем примере (язык Pascal) функции Add выглядят как реализующие одну и ту же функциональность над разными типами, но компилятор определяет их как две совершенно разные функции.

program Adhoc;

function Add( x, y : Integer ) : Integer;
begin
    Add := x + y
end;

function Add( s, t : String ) : String;
begin
    Add := Concat( s, t )
end;

begin
    Writeln(Add(1, 2));
    Writeln(Add('Hello, ', 'World!'));
end.

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

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

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

Параметрический полиморфизм[править | править вики-текст]

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

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

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

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

length :: List a -> Integer
length Nil = 0
length (Cons x xs) = 1 + length xs

map :: (a -> b) -> List a -> List b
map f Nil = Nil
map f (Cons x xs) = Cons (f x) (map f xs)

При подстановке в ти́повую переменную a конкретных типов Int, String и т. д. будут построены, соответственно, конкретные типы List Int, List String и т. д. Эти конкретные типы, в свою очередь, снова могут быть подставлены в эту ти́повую переменную, порождая типы List List String, List (Int, List String) и т. д. При этом для всех объектов всех построенных типов будет использоваться одна и та же физическая реализация функций length и map.

Параметрический полиморфизм также доступен в некоторых императивных (в частности, объектно-ориентированных) языках программирования, где для его обозначения обычно используется термин «обобщённое программирование». В частности, в языке Си нетипизированный параметрический полиморфизм традиционно обеспечивается за счёт использования нетипизированного указателя void*, хотя возможна и типизированная форма. Использование шаблонов C++ внешне похоже на параметрический полиморфизм, но семантически реализуется сочетанием ad hoc-механизмов; в сообществе С++ его называют «статическим полиморфизмом» (для противопоставления «динамическому полиморфизму»>>>).

Рядный полиморфизм[править | править вики-текст]

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

# let area sq = sq#width * sq#width ;;
val area : < width : int; .. > -> int = <fun>

Многоточие означает, что в данной записи существуют и другие поля, помимо упомянутых. Ранние диалекты ML требовали полного статического разрешения информации о типе, то есть однозначного определения мономорфного типа записи. Другими словами, такая запись в них являлась не более чем синтаксическим сахаром, называемым «универсальным образцом»[17] (конкретный синтаксис может различаться).

В дальнейшем>>> было формализовано выведение и согласование типов в общем случае. Многоточие стало означать специальную переменную типа, которую называют «рядной переменной»[18] (row variable) или «рядной ти́повой переменной» (row type variable), подразумевая, что в данный контекст подставим целый ряд значений некоторых типов (а не одно значение некоторого типа, как в большинстве разновидностей полиморфизма), а соответствующую разновидность полиморфизма называют рядным полиморфизмом (row polymorpshism).

Поддержка рядного полиморфизма имеется в современных версиях OCaml[18].

Рядный полиморфизм является частным случаем параметрического полиморфизма>>> — запись становится истинно полиморфной — поэтому его также называют «полиморфизмом записей» (record polymorphism), что может приводить к путанице с «полиморфизмом подтипов на записях»>>> (subtype polymorphism on records), представляющим независимую концепцию. Подтипизация в полиморфном языке существенно усложняет систему типов[19]; рядный полиморфизм проще в реализации, и при отсутствии подтипизации предоставляет достаточную выразительность для применения объектно-ориентированного проектирования, хотя и с большей трудоёмкостью (OCaml поддерживает обе возможности).

Замечание — Митчел Уэнд[en], считающийся автором рядного полиморфизма[20], заимствовал термин «row» (рус. ряд, цепочка, строка) из Алгола-68, где он означал множество представлений. В контексте Алгола в русскоязычной литературе этот термин традиционно переводился как «мультивид». Встречается также вариант перевода «row variables» как «строчные переменные»[21], вызывающий путаницу со строчными буквами в строковых типах.

Полиморфная рекурсия[править | править вики-текст]

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

Полиморфизм подтипов[править | править вики-текст]

Полиморфизм включения (inclusion polymorphism) является обобщённой формализацией подтипизации[en] и наследования[9]. Эти понятия не следует путать: подтипы[en] определяют отношения на уровне интерфейсов, тогда как наследование определяет отношения на уровне реализации[23].

Подтипизация (subtyping), или полиморфизм подтипов (subtype polymorphism), означает, что поведение параметрически полиморфной>>> функции ограничивается множеством типов, связанных в иерархию «супертип — подтип»[24][9][25]. Например, если имеются типы Number, Rational и Integer, связанные отношениями Number :> Rational и Number :> Integer, то функция, определённая на типе Number, также сможет принять на вход аргументы типов Integer или Rational, и её поведение будет идентичным. Действительный тип объекта может быть скрыт как «чёрный ящик», и предоставляться лишь по запросу идентификации объекта. На самом деле, если тип Number является абстрактным, то конкретного объекта этого типа даже не может существовать (см. абстрактный класс, но не следует путать с абстрактным типом данных). Данная иерархия типов известна (особенно в контексте языка Scheme) как числовая башня[en], и обычно содержит большее количество типов.

Идея подтипов мотивируется увеличением множества типов, которые могут обрабатываться уже написанными функциями, и за счёт этого повышением коэффициента повторного использования кода в условиях сильной типизации (то есть увеличением множества типизируемых программ). Это обеспечивается правилом включения (subsumption rule): «если выражение e принадлежит к типу t' в контексте типизации Г, и выполняется t'<:t, то e принадлежит также и к типу t»[26][27].

Отношения подтипизации возможны на самых разных категориях типов: примитивных типах (как Integer <: Number), типах-суммах, типах-произведениях, функциональных типах и др. Более того, Лука Карделли[en] предложил концепцию степенны́х родо́в («power» kinds) для описания подтипизации[21]: степенью данного типа в слое родо́в (power-kind of the type) он назвал род всех его подтипов[28].

Важным частным случаем подтипизации является подтипизация на записях>>>.

Подтипизация на записях[править | править вики-текст]

Подтипизация на записях (не путать с полиморфизмом записей>>>), также известная как включение или вхождение (subsumption — см. принцип подстановки Барбары Лисков), является теоретическим обоснованием объектно-ориентированного программирования (ООП)[29][30][25][18]. Формально её отношения с параметрическим полиморфизмом описываются ограниченной квантификацией[en] и ковариантностью/контравариантностью (или полярностью) конструкторов типов[30]. Проще говоря, супертипы в ООП представляют собой параметрические типы, параметр которых задаётся неявно[31].

В подтипизации на записях выделяются две разновидности: в ширину и в глубину.

Подтипизация в ширину (width subtyping) подразумевает добавление в запись новых полей. Например:

type Object  = { age: Int }
type Vehicle = { age: Int; speed: Int }
type Bike    = { age: Int; speed: Int; gear: Int; }
type Machine = { age: Int; fuel: String }

С одной стороны, можно записать отношения подтипизации Vehicle <: Object, Bike <: Vehicle (а поскольку подтипизация транзитивна, то и Bike <: Object) и Machine <: Object. С другой стороны, можно говорить, что типы Vehicle, Bike и Machine включают (наследуют) все свойства типа Object. (Здесь подразумевается структурная[en] семантика системы типов.)

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

Отношения подтипов в терминах множеств выглядят более интуитивно в случае с вариантными типами[32]:

type Day     = mon | tue | wed | thu | fri | sat | sun
type Workday = mon | tue | wed | thu | fri
type WeekEnd = sat | sun

Здесь Workday <: Day и WeekEnd <: Day.

Именование полей позволяет абстрагироваться от порядка их следования в записях (в отличие от кортежей), что даёт возможность строить произвольные направленные ацикличные графы наследования, формализуя множественное наследование[32]:

type Car = { age: Int; speed: Int; fuel: String }

Теперь Car <: Vehicle и одновременно Car <: Machine. Очевидно также, что Car <: Object (см. ромбовидное наследование).

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

type Voyage   = { veh: Vehicle; date: Day }
type Sports   = { veh: Bike;    date: Day }
type Vacation = { veh: Car;     date: WeekEnd }

Из определений выше можно вывести, что Sports <: Voyage и Vacation <: Voyage.

Методы в подтипах записей[править | править вики-текст]

Полноценная поддержка объектно-ориентированного программирования предполагает включение в число полей записей также функций, обрабатывающих значения типов записей, которым они принадлежат[29][33]. Такие функции традиционно называются «методами». Обобщённой моделью связывания записей с методами является матрица диспетчеризации (dispatch matrix); на практике большинство языков раскладывают её на вектора по строкам либо по столбцам — соответственно, реализуя либо организацию на основе классов (class-based organisation), либо организацию на основе методов (method-based organisation)[34]. При этом следует отличать переопределение методов в подтипах (method overriding) от подтипизации функций (functional subtyping). Переопределение методов не связывает их отношениями подтипизации на функциях, но позволяет изменять сигнатуры их типов. При этом возможны три варианта: инвариантное, ковариантное и контравариантное переопределение, и два последних используют подтипизацию своих параметров[35] (подробнее см. ковариантность и контравариантность).

Многие объектно-ориентированные языки предусматривают встроенный механизм связывания функций в методы, реализуя таким образом организацию программ на основе классов. Языки, рассматривающие функции как объекты первого класса и типизирующие их (см. функции первого класса, функциональный тип — не путать с типом возвращаемого значения функции), позволяют произвольно выстраивать организацию на основе методов, что обеспечивает возможность производить объектно-ориентированное проектирование без прямой поддержки со стороны языка[36]. Некоторые языки (например, OCaml) поддерживают обе возможности.

Языки с системами типов, основанными на формальной теории подтипизации (OCaml, проект successor ML), рассматривают системы объектов и системы классов независимо[37][38]. Это значит, что с объектом связывается прежде всего объектный тип, и лишь при явном указании объектный тип связывается с неким классом. При этом динамическая диспетчеризация[en] осуществляется на уровне объекта, а значит, в таких языках два объекта, относящиеся к одному классу, вообще говоря, могут иметь различный набор методов. Вместе с формально определённой семантикой множественного наследования это даёт непосредственную всестороннюю поддержку примесей.

CLOS реализует матрицу диспетчеризации посредством мультиметодов, то есть динамически диспетчеризуемых[en] методов, полиморфных сразу по нескольким аргументам[39].

Некоторые языки используют своебразные ad hoc-решения. Например, система типов языка С++ предусматривает автоматическое приведение типов (то есть является слабой), не полиморфная, не поддерживает выделение подтипов[en] и абстракцию типов (не путать с сокрытием полей) и определяет инвариантность сигнатур методов. Наследование в С++ реализуется набором ad hoc-механизмов, однако, его использование называется в сообществе языка «полиморфизмом» (а сокрытие полей — «абстракцией»[40]). Использование такого языка может быть небезопасно (нельзя гарантировать устойчивость программ)[41][35]. В качестве особенности можно отметить наличие в С++ (неформализуемой) возможности управлять графом наследования: ромбовидное наследование в С++ называется «виртуальным наследованием» и задаётся явным атрибутом virtual; по умолчанию же осуществляется дублирование унаследованных полей с доступом к ним по квалифицированному имени.

Подтипизация высшего порядка[править | править вики-текст]

«Система F^\omega_{<:}» (читается «F-саб-омега») является расширением Системы F (не представленным в лямбда-кубе), формализующим ограниченную квантификацию[en] над ти́повыми операторами, распространяя отношения подтипизации с рода * на типы высших родо́в. Существует несколько вариантов системы F^\omega_{<:}, различающихся по выразительной мощности и метатеоретической сложности, но большинство основных идей заложил Лука Карделли[en][42].

Сочетание разновидностей полиморфизма[править | править вики-текст]

Классы типов[править | править вики-текст]

Класс типов реализует единую независимую таблицу виртуальных методов для множества (универсально квантифицированных) типов. Этим классы типов отличаются от классов в объектно-ориентированном программировании, где всякий объект всякого (ограниченно[en] квантифицированного) типа сопровождается указателем на таблицу виртуальных методов[43]. Классы типов являются не типами, но категориями типов; их инстансы представляют собой не значения, а типы.

Например[43]:

class Num a where
   (+), (*) :: a -> a -> a
   negate :: a -> a

Это объявление читается так: «Тип a принадлежит классу Num, если на нём определены функции (+), (*) и negate, с заданнами сигнатурами».

instance Num Int where
   (+) = addInt
   (*) = mulInt
   negate = negInt

instance Num Float where
   (+) = addFloat
   (*) = mulFloat
   negate = negFloat

Первое объявление читается так: «Существуют функции (+), (*) и negate соответствующих сигнатур, которые определены над типом Int». Аналогично читается второе утверждение.

Теперь можно корректно типизировать следующие функции (причём выведение типов разрешимо):

square :: Num a => a -> a
square x = x * x

squares3 :: Num a, Num b, Num c => (a, b, c) -> (a, b, c)
squares3 (x, y, z) = (square x, square y, square z)

Класс типов сводит параметрический>>> и ad hoc>>> полиморфизм в единую модель[12]. С точки зрения параметрического полиморфизма, класс типов имеет параметр (переменную типа), пробегающий множество типов. С точки зрения ad hoc полиморфизма, это множество не только дискретно, но и задано явным образом до уровня реализации. Благодаря этому, функция типизируется единственным образом, несмотря на обращение к перегруженной функции из её тела. В отсутствии классов типов в данном случае потребовались бы две перегруженные функции square и восемь перегруженных функций squares3объектно-ориентированном программировании эта проблема решается посредством динамической диспетчеризации[en], с соответствующими накладными расходами).

Встроенная поддержка классов типов была впервые реализована в языке Haskell, но они также могут быть введены в любой параметрически полиморфный язык путём простого препроцессинга[12], а также реализованы идиоматически (см., например, язык модулей ML#Реализация альтернативных моделей).

Типы, допускающие проверку на равенство (equality types)[en] в Хаскеле реализуются как инстансы класса типов Eq (обобщая переменные типа, допускающего проверку на равенство (equality type variables) из Standard ML):

(==) :: Eq a => a -> a -> Bool

Для снижения рутинного кодирования некоторых часто очевидно необходимых свойств пользовательских типов в Хаскеле дополнительно предусмотрен синтаксический сахар — конструкция deriving, допустимая для ограниченного набора стандартных классов типов (таких как Eq). (В русскоязычном сообществе её использование нередко путается с понятием «наследования» из-за особенностей перевода слова «derive».)

Обобщённые алгебраические типы данных[править | править вики-текст]

Политипизм[править | править вики-текст]

Иногда используется термин «политипизм» или «обобщённость типа данных». По сути политипизм означает встроенную в язык поддержку полиморфизма конструкторов типов, предназначенную для унификации программных интерфейсов и повышения повторного использования кода. Примером политипизма является обобщённый алгоритм сопоставления с образцом[44].

По определению, в политиповой функции «хотя и возможно наличие конечного числа ad hoc-ветвей для некоторых типов, но ad hoc-комбинатор отсутствует»[45].

Политипизм может быть реализован посредством использования универсального типа данных или полиморфизма высших рангов. Расширение PolyP[46] языка Haskell представляет собой синтаксическую конструкцию, упрощающую определение политиповых функций в Хаскеле.

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

head   :: [a] -> a
(+)    :: Num a => a -> a -> a
length :: Regular d => d a -> Int
sum    :: Regular d => d Int -> Int

Первая функция (head) является полиморфной (параметрически полиморфной>>>), вторая (инфиксный оператор «+») — перегруженной (ad hoc полиморфной>>>), третья и четвёртая — политиповыми: переменная типа d в их определении варьируется над конструкторами типов. При этом, третья функция (length) является политиповой и полиморфной (предположительно, она вычисляет «длину» для некоторого множества полиморфных агрегатных типов — например, количество элементов в списках и в деревьях), а четвёртая (sum) является политиповой, но не полиморфной (мономорфной над агрегатными типами, принадлежащими классу типов Regular, для которых она, вероятно, вычисляет сумму целых, образующих объект конкретного агрегатного типа).

Прочее[править | править вики-текст]

Динамически типизируемые языки единообразно представляют разновидности полиморфизма, что формирует самобытную идеологию в них и влияет на применяемые методологии декомпозиции задач. Например, в Smalltalk любой класс способен принять сообщения любого типа, и либо обработать его самостоятельно (в том числе посредством интроспекции), либо ретранслировать другому классу — таким образом, любой метод формально является параметрически полиморфным, при этом его внутренняя структура может ветвиться по условию динамического типа аргумента, реализуя специальный полиморфизм. В CLOS мультиметоды одновременно являются функциями первого класса, что позволяет рассматривать их одновременно и как ограниченно квантифицированные[en], и как обобщённые (истинно полиморфные).

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

История[править | править вики-текст]

Термин «полиморфизм» происходит от др.-греч. πολύς («много») и μορφή («форма, облик, устройство»).

Термины «специализированный полиморфизм» и «параметрический полиморфизм» впервые упоминаются в 1967 году в конспекте лекций Кристофера Стрэчи[en] под названием «Фундаментальные основы языков программирования[en]»[1]. В 1985 году Питер Вегнер[en] и Лука Карделли[en] формализовали полиморфизм включения для моделирования подтипов[en] и наследования[9][21], хотя реализации подтипов и наследования появились намного раньше, в языке Симула в 1967 году. Полиморфизм включения основан на ограниченной квантификации[en].

Нотацию параметрического полиморфизма как развитие лямбда-исчисления (названную полиморфным лямбда-исчислением или Системой F) формально описал логик Жан-Ив Жирар[en][47][48] (1971 год), независимо от него похожую систему описал информатик Джон С. Рейнольдс[en][49] (1974 год).

Первым языком, целиком основанным на полиморфном лямбда-исчислении, был ML (1973 год); независимо от него параметрические типы были реализованы в CLU (1974 год)[21]. Многие современные языки (С++, Java, C#, D и другие) предоставляют параметрические типы в форме, более или менее близкой к их реализации в CLU.

В 1987 году Митчел Уэнд (Mitchel Wand) формализовал рядный полиморфизм>>> и выведение типов для него[20]. Несколькими годами ранее свою модель рядного полиморфизма предложил Лука Карделли[en], но она не завоевала популярности, так как выведение типов для неё неразрешимо.

В 1987 году Филип Вадлер[en] (Philip Wadler) и Стивен Блотт (Stephen Blott) предложили классы типов>>> для формализации ad hoc полиморфизма>>>.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 3 Strachey - Fundamental Concepts, 1967.
  2. Cardelli - Typeful Programming, с. 3.
  3. Пирс - Типы в языках программирования, 22.7. Полиморфизм через let, с. 354.
  4. C++ Glossary (February 19, 2007).
  5. 1 2 Cardelli - On Understanding Types, 1.3. Kinds of Polymorphism, с. 6.
  6. Andrew W. Appel A Critique of Standard ML. — Princeton University, 1992.
  7. Harper - Practical Foundations for Programming Languages, 20.1 System F, с. 172.
  8. Пирс - Типы в языках программирования, 23.2 Разновидности полиморфизма, с. 365.
  9. 1 2 3 4 Cardelli - On Understanding Types.
  10. Mitchell - Concepts in Programming Languages.
  11. Mitchell - Concepts in Programming Languages, 6.4. Polymorphism and overloading, с. 145-151.
  12. 1 2 3 4 Wadler - How to make ad-hoc polymorphism less ad hoc, с. 1-2.
  13. Cardelli - On Understanding Types, с. 6.
  14. 1 2 Cardelli - On Understanding Types, с. 5-6.
  15. Пирс - Типы в языках программирования, 23.9 Параметричность, с. 384-385.
  16. Cardelli - Type systems, 5 Second-order Type Systems, с. 25.
  17. Harper - Intro to SML.
  18. 1 2 3 Мински в переводе ДМК, Подтипизация, с. 259.
  19. Пирс - Типы в языках программирования, 16. Метатеория подтипов, с. 225.
  20. 1 2 Wand - type inference for objects.
  21. 1 2 3 4 Пирс - Типы в языках программирования, 1.4 Краткая история, с. 11-13.
  22. Пирс - Типы в языках программирования, Глава 22. Реконструкция типов. Раздел 22.8. Дополнительные замечания, с. 362.
  23. Mitchell - Concepts in Programming Languages, 10.2.6 Inheritance Is Not Subtyping, с. 287.
  24. Cardelli - Typeful programming.
  25. 1 2 Пирс - Типы в языках программирования, 15 Подтипы, с. 193.
  26. 1 2 Пирс - Типы в языках программирования, 15. Подтипы, с. 193.
  27. Harper - Practical Foundations for Programming Languages, 23.1. Subsumption, с. 208.
  28. Cardelli - Typeful Programming, 6. Power kinds, с. 32.
  29. 1 2 Abadi, Cardelli - Semantics of Object Types.
  30. 1 2 3 Cardelli - On Understanding Types, 6. Bounded Quantification, с. 28.
  31. Cardelli - On Understanding Types, с. 9.
  32. 1 2 Cardelli - Typeful Programming, с. 35-37.
  33. Cardelli - On Understanding Types, 2.3. Basic Types, Structured Types and Recursion, с. 12-14.
  34. Harper - Practical Foundations for Programming Languages, Chapter 25. Dynamic Dispatch, с. 229.
  35. 1 2 Joyner, 1996, 3.38 Signature Variance, с. 35.
  36. Object-Oriented Programming in Standard ML
  37. Мински в переводе ДМК, Глава 11. Объекты, с. 253.
  38. The ML2000 Working Group. Principles and a Preliminary Design for ML2000. — 1999.
  39. Castagna, Ghelli, Longo. A calculus for overloaded functions with subtyping. // Information and Computation. — Academic press, 1995. — Т. 117, вып. 1. — С. 115–135. — DOI:10.1006/inco.1995.1033.
  40. Joyner, 1996, 2.8 Encapsulation, с. 8.
  41. Mitchel - Concepts in Programming Languages, 2004, 6.2.1 Type Safety, с. 132-133.
  42. Пирс - Типы в языках программирования, 31. Подтипы высших порядков, с. 495.
  43. 1 2 Wadler - How to make ad-hoc polymorphism less ad hoc, с. 3.
  44. Johan Jeuring Polytypic pattern matching // FPCA. — 1995. — DOI:10.1.1.36.5645.
  45. Ralf Lammel and Joost Visser, «Typed Combinators for Generic Traversal», in Practical Aspects of Declarative Languages: 4th International Symposium (2002), p. 153.
  46. Patrik Jansson, Johan Jeuring PolyP - A Polytypic programming language extension. — Sigplan SPPL, 1997.
  47. Girard - Extension of Type Theory.
  48. Girard - Higher-order calculus.
  49. Reynolds - Theory of Type Structure.

Литература[править | править вики-текст]

  • Перевод на русский язык: Роберт Харпер[en]. Введение в Стандартный ML. — Carnegie Mellon University, 1986. — 97 с. — ISBN PA 15213-3891.
  • Перевод на русский язык: Мински, Мадхавапедди, Хикки. Программирование на языке OCaml. — ДМК, 2014. — 536 с. — (Функциональное программирование). — ISBN 978-5-97060-102-0.