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

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

Существует несколько разновидностей полиморфизма. Две принципиально различных из них были описаны Кристофером Стрэчи^[англ.] в 1967 году: это параметрический полиморфизм➤ и ad-hoc-полиморфизм➤, прочие формы являются их подвидами или сочетаниями. Параметрический полиморфизм является истинным, т.к. подразумевает исполнение одного и того же кода для всех допустимых типов аргументов, а ad-hoc-полиморфизм — мнимым, т.к. представляет собой обеспечение косметической однородности потенциально разного исполнимого кода для каждого конкретного типа аргумента^[1][4]. При этом существуют ситуации, где необходимо использование именно ad-hoc-полиморфизма, а не параметрического^[5]. Теория квалифицированных типов объединяет все виды полиморфизма в единую модель.

Широко распространено определение полиморфизма, приписываемое Бьёрну Страуструпу: «один интерфейс (как перечень объявлений) — много реализаций (определений, связываемых с этими объявлениями)»^[6], но под это определение подпадает лишь ad-hoc-полиморфизм (мнимый полиморфизм).

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

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

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

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

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

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

В дальнейшем классификацию уточнил Лука Карделли^{[англ.][10]}, выделив четыре разновидности полиморфизма:

• универсальный
  • параметрический
  • включения (или подтипов^[англ.])➤
• ad-hoc
  • перегрузка
  • приведение типов

В некоторых работах параметрический, ad-hoc- и полиморфизм подтипов выделяются как три самостоятельных класса полиморфизма^[11].

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

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

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

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

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

В следующем примере (язык Паскаль) функции 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.

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

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

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

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

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

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-механизмов; в сообществе C++ его называют «статическим полиморфизмом» (для противопоставления «динамическому полиморфизму»➤).

Формализация параметрического полиморфизма ведёт к понятию параметричности^[англ.], состоящему в возможности предсказывать поведение программ, глядя только на их типы. Например, если функция имеет тип «forall a. a -> a», то без каких-либо дополняющих язык внешних средств можно доказать, что она может быть только тождественной. Поэтому параметричность часто сопровождается лозунгом «теоремы забесплатно» (англ. theorems for free). ^{[15] [16][17]}

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

Наиболее развитые параметрически полиморфные системы (занимающие высшую точку в лямбда-кубе) доводят идею параметричности до возможности полного доказательства корректности программ: они позволяют записывать программы, которые верны по построению, так что прохождение проверки согласования типов само по себе даёт гарантию, что поведение программы соответствует ожидаемому^[19].

Отдельную проблему представляет распространение параметрического полиморфизма на агрегатные типы: размеченные произведения типов (традиционно называемые записями) и размеченные суммы типов (также известные как вариантные типы^[англ.]). Различные «исчисления записей» (англ. record calculi) служат формальной базой для объектно-ориентированного и модульного программирования^[20].

val r = {a = 1, b = true, c = "hello"}
val {a = n, ... = r1} = r
val r2 = {d = 3.14, ... = r1}

Многоточие означает некоторый ряд типизированных полей, то есть абстракцию кода от конкретных типов записей, которые могли бы здесь обрабатываться (причём «длина» этого ряда также может варьироваться). Компиляция полиморфного обращения к полям, которые могут располагаться в разном порядке в разных записях, представляет сложную проблему, как с точки зрения контроля безопасности операций на уровне языка, так и с точки зрения быстродействия на уровне машинного кода. Наивным решением может быть динамический поиск по словарю при каждом обращении (и скриптовые языки его применяют), однако, очевидно, что это чрезвычайно неэффективно. Эта проблема активно исследуется на протяжении уже нескольких десятилетий; построено множество теоретических моделей и практичных систем на их основе, различающихся по выразительной мощности и метатеоретической сложности. Важнейшими достижениями в этой области считаются рядный полиморфизм, предложенный Митчелом Уандом (англ. Mitchell Wand)), и полиморфное исчисление записей, построенное Ацуси Охори (англ. Atsushi Ohori). Более распространённой, но отстающей по многим характеристикам моделью является подтипизация на записях➤.

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

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

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

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

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

Особое место в информатике занимает подтипизация на записях➤.

Подтипизация на записях, также известная как включение или вхождение (subsumption — см. принцип подстановки Барбары Лисков), служит наиболее распространённым теоретическим обоснованием объектно-ориентированного программирования (ООП)^{[29][30][24][31]} (но не единственным — см. #полиморфизм записей и вариантов).

Мартин Абади (Martín Abadi) и Лука Карделли^[англ.] формализовали подтипизацию на записях посредством ограниченной квантификации^[англ.] над параметрически полиморфными типами^[29][30]; при этом параметр типа задаётся неявно^[32].

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

Подтипизация в ширину (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. (Здесь подразумевается структурная^[англ.] семантика системы типов.)

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

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

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

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

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

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][35]. Такие функции традиционно называются «методами». Обобщённой моделью связывания записей с методами является матрица диспетчеризации (dispatch matrix); на практике большинство языков раскладывают её на вектора по строкам либо по столбцам — соответственно, реализуя либо организацию на основе классов (class-based organisation), либо организацию на основе методов (method-based organisation) ^[36]. При этом следует отличать переопределение методов в подтипах (method overriding) от подтипизации функций (functional subtyping). Переопределение методов не связывает их отношениями подтипизации на функциях, но позволяет изменять сигнатуры их типов. При этом возможны три варианта: инвариантное, ковариантное и контравариантное переопределение, и два последних используют подтипизацию своих параметров^[37] (подробнее см. ковариантность и контравариантность). Исчисление Абади — Карделли^[29] рассматривает только инвариантные методы, что необходимо для доказательства безопасности.

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

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

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

Некоторые языки используют своеобразные ad-hoc]решения. Например, система типов языка C++ предусматривает автоматическое приведение типов (то есть является слабой), неполиморфная, эмулирует выделение подтипов^[англ.] через манифестное^[англ.] наследование с инвариантными сигнатурами методов и не поддерживает абстракцию типов (не путать с сокрытием полей). Наследование в C++ реализуется набором ad-hoc-механизмов, однако, его использование называется в сообществе языка «полиморфизмом» (а сокрытие полей — «абстракцией»^[42]). Имеется возможность управлять графом наследования: ромбовидное наследование в C++ называется «виртуальным наследованием» и задаётся явным атрибутом virtual; по умолчанию же осуществляется дублирование унаследованных полей с доступом к ним по квалифицированному имени. Использование такого языка может быть небезопасно — нельзя гарантировать устойчивость программ^[43][37] (язык называется безопасным, если программы на нём, которые могут быть приняты компилятором как правильно построенные, в динамике никогда не выйдут за рамки допустимого поведения ^[44]).

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

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

Например^[46]:

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)

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

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

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

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

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

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

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

Политипизм может быть реализован посредством использования универсального типа данных или полиморфизма высших рангов. Расширение PolyP^[49] языка Haskell представляет собой синтаксическую конструкцию, упрощающую определение политиповых функций в 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 мультиметоды одновременно являются функциями первого класса, что позволяет рассматривать их одновременно и как ограниченно квантифицированные^[англ.], и как обобщённые (истинно полиморфные).

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

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

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

Нотацию параметрического полиморфизма как развитие λ-исчисления (названную системой F) формально описал логик Жан-Ив Жирар^{[англ.][50][51]} (1971 год), независимо от него похожую систему описал информатик Джон С. Рейнольдс^{[англ.][52]} (1974 год).

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

В 1987 году Митчел Уэнд (Mitchel Wand) формализовал рядный полиморфизм➤ и выведение типов для него^[53]; эта работа оказала огромное влияние на последующее развитие систем типов. В том же году Филип Уодлер (англ. Philip Wadler) и Стивен Блотт (Stephen Blott) предложили классы типов➤ для формализации ad-hoc-полиморфизма.

• Каламбур типизации
• Инкапсуляция

• Christopher Strachey. Fundamental Concepts in Programming Languages (англ.). — 1967. Архивировано 12 августа 2017 года.
  • Повторно опубликовано: Christopher Strachey. Fundamental Concepts in Programming Languages (англ.) // Higher-Order and Symbolic Computation. — 2000. — Vol. 13. — P. 11—49. — doi:10.1023/A:1010000313106.
• Jean-Yves Girard. Une Extension de l’Interpretation de Gödel à l’Analyse, et son Application à l'Élimination des Coupures dans l’Analyse et la Théorie des Types (фр.) // Proceedings of the Second Scandinavian Logic Symposium. — Amsterdam, 1971. — P. 63—92. — doi:10.1016/S0049-237X(08)70843-7.
• Jean-Yves Girard. Interprétation fonctionnelle et élimination des coupures de l’arithmétique d’ordre supérieur (фр.). — Université Paris 7, 1972.
• John C. Reynolds. Towards a Theory of Type Structure // Lecture Notes in Computer Science. — Paris: Colloque sur la programmation, 1974. — Т. 19. — С. 408—425. — doi:10.1007/3-540-06859-7_148.
• Luca Cardelli^[англ.], Peter Wegner. On Understanding Types, Data Abstraction, and Polymorphism // ACM Computing Surveys. — New York, USA: ACM, 1985. — Т. 17, вып. 4. — С. 471—523. — ISSN 0360-0300. — doi:10.1145/6041.6042.

• Robert Harper^[англ.]. Introduction to Standard ML. — Carnegie Mellon University, 1986. — ISBN PA 15213-3891.

• Перевод на русский язык: Роберт Харпер^[англ.]. Введение в Стандартный ML. — Carnegie Mellon University, 1986. — 97 с. — ISBN PA 15213-3891.

• Mitchell Wand^[англ.]. Complete type inference for simple objects (англ.) // In Proc. 2nd IEEE Symposium on Logic in Computer Science. — 1987. — P. 37—44.
• Philip Wadler, Stephen Blott. How to make ad-hoc polymorphism less ad hoc (англ.). — 1988.
• Luca Cardelli^[англ.]. Typeful programming (англ.) // IFIP State-of-the-Art Reports. — New York: Springer-Verlag, 1991. — Iss. Formal Description of Programming Concepts. — P. 431—507.
• Martín Abadi, Luca Cardelli^[англ.]. A Semantics of Object Types (англ.). — LICS^[англ.], 1994.

• Luca Cardelli^[англ.]. Type systems (англ.) // Handbook of Computer Science and Engineering. — CRC Press, 1996.

• Ian Joyner. A Critique of C++ and Programming and Language Trends of the 1990s - 3rd Edition // копирайт и список изданий. — 1996.

• John C. Reynolds. Theories of programming languages. — Cambridge University Press, 1998. — ISBN 978-0-521-59414-1 (hardback), 978-0-521-10697-9 (paperback).

• Benjamin Pierce. Types and Programming Languages (англ.). — MIT Press, 2002. — ISBN 0-262-16209-1.
  • Перевод на русский язык: Бенджамин Пирс. Типы в языках программирования (рус.). — Добросвет, 2012. — 680 с. — ISBN 978-5-7913-0082-9.

• John C. Mitchell. Concepts in Programming Languages (англ.). — Cambridge University Press, 2002. — 540 p. — ISBN 978-0-521-78098-8.

• Georg Neis, Derek Dreyer, Andreas Rossberg. Non-Parametric Parametricity (англ.) // ICFP. — ACM, 2009.

• Robert Harper^[англ.]. Practical Foundations for Programming Languages. — version 1.37 (revised 01.11.2014). — licensed under the Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States License., 2012. — 544 с. Архивная копия от 24 октября 2015 на Wayback Machine

• Minsky, Madhavapeddy, Hickey. Real World OCaml: Functional Programming for the Masses (англ.). — O'Reilly Media, 2013. — 510 p. — ISBN 9781449324766.
  • Перевод на русский язык: Мински, Мадхавапедди, Хикки. Программирование на языке OCaml (рус.). — ДМК, 2014. — 536 с. — (Функциональное программирование). — ISBN 978-5-97060-102-0.