20-05-2023
В языках программирования и теории типов полиморфизмом называется способность функции обрабатывать данные разных типов[1][2].
Существует несколько видов полиморфизма. Два наиболее различных из них были описаны Кристофером Стрэчи[en] в 1967 году: это специальный полиморфизм (или «ad hoc полиморфизм») и параметрический полиморфизм. Кратко специальный полиморфизм описывается принципом «много реализаций с похожими интерфейсами», а параметрический полиморфизм — «одна реализация с обобщённым интерфейсом».
Полиморфизм является фундаментальным свойством системы типов. Различают[3] статическую неполиморфную типизацию (потомки Алгола и BCPL), динамическую типизацию (потомки Lisp, Smalltalk, APL) и статическую полиморфную типизацию (потомки ML). Параметрический полиморфизм и динамическая типизация намного существеннее, чем специальный полиморфизм, повышают коэффициент повторного использования кода, поскольку определенная единственный раз функция реализует без дублирования заданное поведение для бесконечного множества вновь определяемых типов, удовлетворяющих требуемым в функции условиям. С другой стороны, временами возникает необходимость обеспечить различное поведение функции в зависимости от типа параметра, и тогда необходимым оказывается специальный полиморфизм.
Параметрический полиморфизм повсеместно используется в функциональном программировании, где он обычно обозначается просто как «полиморфизм». В сообществе же объектно-ориентированного программирования под термином «полиморфизм» обычно подразумевают ad hoc полиморфизм методов классов, связанных в иерархию наследования; а использование параметрического полиморфизма называют обобщённым программированием, или иногда «статическим полиморфизмом».
Термин «полиморфизм» происходит от др.-греч. πολύς («много») и μορφή («форма, облик, устройство»).
Термины «специализированный полиморфизм» и «параметрический полиморфизм» впервые упоминаются в 1967 году в конспекте лекций Кристофера Стрэчи[en] под названием «Фундаментальные основы языков программирования[en]»[1]. В 1985 году Питер Вегнер[en] и Лука Карделли[en] предложили термин «полиморфизм включения» для моделирования подтипов и наследования[4], хотя реализации подтипов и наследования появились намного раньше, в языке Симула в 1967 году.
Нотацию параметрического полиморфизма как развитие лямбда-исчисления (названную полиморфным лямбда-исчислением или Системой F) формально описал Джон С. Рейнольдс[en], и независимо от него Жан-Ив Жирар[en]. Первым языком, целиком основанным на полиморфном лямбда-исчислении, был ML (1973 год); независимо от него параметрические типы были реализованы в CLU (1974 год)[5]. Многие современные языки (С++, Java, C#, D и другие) предоставляют параметрические типы в форме, более или менее близкой к их реализации в CLU.
Если параметру функции сопоставлен ровно один тип, то такая функция называется мономорфной. Многие языки программирования предоставляют синтаксический механизм для назначения нескольким мономорфным функциям единого имени (идентификатора). В этом случае, в исходном коде становится возможным осуществлять вызов функции с фактическими параметрами разных типов, но в скомпилированном коде фактически происходит вызов различных функций. Стрэчи назвал такую возможность ad hoc полиморфизмом (в русской литературе чаще всего переводится как специальный полиморфизм).
Если параметру функции сопоставлено более одного типа, то такая функция называется полиморфной. Разумеется, с каждым фактическим значением может быть связан лишь один тип, но полиморфная функция рассматривает параметр на основе поведения (в частности, его структуры — но не в смысле представления в памяти, а в смысле взаимной организации компонентов структурного типа). В этом случае одно и то же алгоритмическое действие работает с объектами различных типов. Стрэчи назвал такую возможность параметрическим полиморфизмом. Сильно типизированные языки предусматривают возможность описания параметрически полиморфных типов, позволяющих производить статический[en] контроль безопасности использования полиморфных функций. Полиморфный тип синтаксически записывается посредством переменной типа — контекстного идентификатора, пробегающего множество типов.
Развитие языков и систем типов со временем выявило большее разнообразие способов абстрагирования, и в 1985 году классификацию уточнил Лука Карделли[en][4].
Если поведение полиморфной функции ограничивается множеством типов, связанных в иерархию «супертип — подтип», то имеет место полиморфизм включения (или полиморфизм подтипов), тесно связанный с объектно-ориентированным программированием. Связь подтипов[en] с параметрическим полиморфизмом обеспечивается посредством связанной квантификации[en] и ковариантности/контравариантности (или полярности) конструкторов типов.
Кроме того, Карделли относит приведение типов к разновидности ad hoc полиморфизма. Он не заостряет внимание на этом, но причина этого отнесения очевидна: приведение типов осуществляется в случаях, когда функции мономорфны, но вызывающий их код передаёт им значения разных типов, и это вполне попадает под определение ad hoc полиморфизма.
Стрэчи выбрал термин «ad hoc» (лат. спонтанный, случайный) чтобы подчеркнуть, что функции являются на самом деле мономорфными, то есть реализующими частные варианты поведения для каждого конкретного типа, и таким образом, возможность обрабатывать данные разных типов в этом случае эмулируется языком на уровне фронт-енда, а не является фундаментальным свойством его системы типов. После построения безопасной параметрически полиморфной типизации (см. Хиндли—Милнер), вскоре обнаружилось, что определение специальных реализаций функций для разных типов в некоторых случаях является необходимостью, а не случайностью. Тогда полиморфная типизация была расширена классами типов[en], позволяющими перегружать параметрически полиморфные функции, но термин «ad hoc полиморфизм» сохранился, так как второе значение латинского «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.
В динамически типизируемых языках ситуация может быть более сложной, так как выбор требуемой функции для вызова может быть осуществлён только во время исполнения программы.
Параметрический полиморфизм позволяет определять функцию или тип данных обобщённо, так что значения обрабатываются идентично вне зависимости от их типа. Параметрически полиморфная функция использует аргументы на основе поведения, а не значения, апеллируя лишь к необходимым ей свойствам аргументов, что делает её применимой в любом контексте, где тип объекта удовлетворяет заданным требованиям поведения. Таким образом, реализуется концепция параметричности[en]. Развитые системы типов (такие как Хиндли — Милнер) предоставляют механизмы для определения полиморфных типов, что делает использование полифорфных функций более удобным и обеспечивает статическую типобезопасность.
Классическим примером полиморфного типа служит список элементов произвольного типа, для которого во многих языках, типизируемых по Хиндли — Милнеру (большинство статически типизируемых функциональных языках программирования), предоставляется синтаксический сахар. Следующий пример демонстрирует определение нового типа «список» и две параметрически полиморфные функции над ним:
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)
Параметрический полиморфизм также доступен в некоторых императивных (в частности, объектно-ориентированных) языках программирования, где для его обозначения обычно используется термин «обобщённое программирование»:
struct segment { int start; int end; }; int seg_cmpr( struct segment *a, struct segment *b ) { return abs( a->end - a->start ) - abs( b->end - b->start ); } int str_cmpr( char **a, char **b ) { return strcmp( *a, *b ); } struct segment segs[] = { {2,5}, {4,3}, {9,3}, {6,8} }; char* strs[] = { "three", "one", "two", "five", "four" }; main() { qsort( strs, sizeof(strs)/sizeof(char*), sizeof(char*), (int (*)(void*,void*))str_cmpr ); qsort( segs, sizeof(segs)/sizeof(struct segment), sizeof(struct segment), (int (*)(void*,void*))seg_cmpr ); ... }
Функция qsort обрабатывает массивы элементов любого типа, для которого определена функция сравнения. Полиморфное поведение обеспечивается здесь небезопасным образом — посредством явной передачи необходимых свойств типа через бестиповое подмножества языка.
template <typename T> T max(T x, T y) { if (x < y) return y; else return x; } int main() { int a = max(10,15); double f = max(123.11, 123.12); ... }
Здесь определение функции на уровне исходного кода по-прежнему единственно, но в результате компиляции порождается такое количество перегруженных мономорфных функций, с каким количеством типов данных функция вызывается в программе. Другими словами, параметрический полиморфизм на уровне исходного кода транслируется в ad hoc полиморфизм на уровне целевой платформы. Такое превращение называется мономорфизацией (англ. monomorphizing). В данном случае она является вынужденной, так как в системе типов языка отсутствует поддержка полиморфизма (полиморфный язык здесь является статической[en] надстройкой над мономорфным ядром языка). Более развитые системы типов (Хиндли — Милнер) делают мономорфизацию опциональной, то есть позволяют выбирать между сохранением единственности тела полиморфной функции и размножением мономорфных тел. Типичной реализацией параметрически полиморфных типов в них является обёртнутое[en] представление объектов, но эффективно оптимизирующие компиляторы могут выполнять полную мономорфизацию программы (см., например, MLton).
Мономорфизация повышает быстродействие (точнее, делает полиморфизм «бесплатным»), но вместе с тем увеличивает размер выходного машинного кода. Потенциально это может приводить к кратному увеличению объёма получаемого машинного кода (что обычно называют «раздуванием кода»[6]), но за счёт других выводимых из системы типов свойств на практике оно может оказываться незначительным (в MLton увеличение кода за счёт мономорфизации не превышает 30 %[7]).
В объектно-ориентированном программировании полиморфизм подтипов (или полиморфизм включения) представляет собой концепцию в теории типов, предполагающую использование единого имени (идентификатора) при обращении к объектам нескольких разных классов, при условии, что все они являются подклассами одного общего надкласса (суперкласса). Полиморфизм подтипов состоит в том, что несколько типов формируют подмножество другого типа (их базового класса) и потому могут использоваться через общий интерфейс.
Некоторые языки представляют идею подтипов[en] для ограничения спектра типов, применимых в определённом частном случае параметрического полиморфизма. В этих языках полиморфизм подтипов (обычно называемый также динамическим полиморфизмом) позволяет функции, определённой на типе T, также корректно исполняться для аргументов, принадлежащих типу S, являющемуся подтипом T (в соответствии с принципом подстановки Барбары Лисков). Такое отношение типов обычно записывается как S <: T. При этом тип T называется надтипом (или супертипом) для S, что обозначается как T :> S.
Например, если имеются типы Number, Rational и Integer, связанные отношениями Number :> Rational и Number :> Integer, то функция, определённая на типе Number, также сможет принять на вход аргументы типов Integer или Rational, и её поведение будет идентичным. Действительный тип объекта может быть скрыт как «чёрный ящик», и предоставляться лишь по запросу идентификации объекта. На самом деле, если тип Number является абстрактным, то конкретного объекта этого типа даже не может существовать (см. абстрактный тип данных, абстрактный класс). Данная иерархия типов известна — особенно в контексте языка Scheme — как числовая башня[en], и обычно содержит большее количество типов.
Объектно-ориентированные языки программирования реализуют полиморфизм подтипов посредством наследования, то есть определения подклассов. В большинстве реализаций каждый класс содержит т. н. виртуальную таблицу — таблицу функций, реализующих полиморфную часть интерфейса класса — и каждый объект (экземпляр класса) содержит указатель на виртуальную таблицу своего класса, по согласованию с которой производится вызов полиморфного метода. Такой механизм используется в случаях:
То же применимо и к большинству остальных популярных объектных моделей. Некоторые, однако, такие как CLOS, предоставляют множественную диспетчеризацию, в которой метод полиморфен по всем аргументам.
В следующем примере коты и псы являются подтипами животных. Процедура определена для животных, но также будет работать корректно, получив на входе один из подтипов:
abstract class Animal { abstract String talk(); } class Cat extends Animal { String talk() { return "Meow!"; } } class Dog extends Animal { String talk() { return "Woof!"; } } public class MyClass { public static void write(Animal a) { System.out.println(a.talk()); } public static void main(String args[]) { write(new Cat()); write(new Dog()); } }
Некоторые языки совмещают различные формы полиморфизма, порой сложным образом, что формирует самобытную идеологию в них и влияет на применяемые методологии декомпозиции задач.
Например, в Smalltalk любой класс способен принять сообщения любого типа, и либо обработать его самостоятельно (в том числе посредством интроспекции), либо ретранслировать другому классу — таким образом, любой метод формально является параметрически полиморфным, при этом его внутренняя структура может ветвиться по условию динамического типа аргумента, реализуя специальный полиморфизм.
Другим примером сочетания форм полиморфизма являются Классы типов[en] впервые появившиеся в языке Haskell. Например, типы, допускающие проверку на равенство[en] в Хаскеле реализуются как типы, «наследованные» от класса типов Eq. Классы типов не следует путать с классами в объектно-ориентированном программировании: классы типов являются не типами, но категориями типов; их инстансы представляют собой не значения, а типы.
Язык OCaml предоставляет встроенные возможности объектно-ориентированного программирования наряду с классическим языком модулей Standard ML. Однако, классы в OCaml отличаются и от Smalltalk-style, и от Simula-style, являясь параметрически полиморфными типами. Определение класса параметризуется переменной типа, делая класс в ОКамле похожим на шаблон класса в С++. Аналогичные возможности реализованы в языке Eiffel. Кроме этого, ОКамл позволяет определять параметрически полиморфные («обобщённые») функции, способные обрабатывать классы, не имеющие родственных связей, так как его система типов имеет структурную[en] семантику. Методы классов в ОКамле могут быть перегружены, но для самостоятельных функций специального полиморфизма не допускается, и даже встроенные арифметические операции для разных примитивных типов записываются синтаксически различным образом:
let a = 5 + 4 (* целое *) let b = 5.0 +. 4.0 (* вещественное *)
Standard ML воплощает только let-полиморфизм (подвид параметрического полиморфизма, исключающий полиморфизм первого класса). Для ряда встроенных арифметических операций предусмотрен специальный полиморфизм на правах синтаксического сахара, но определять пользовательские перегруженные функции не допускается. Реализация специального полиморфизма в Standard ML осуществляется посредством так называемых «значений, индексированных типами» (англ. type-indexed values), представляющих собой относительно сложный программный трюк. На основе значений, индексированных типами, симулируются подтипы[en], на основе которых строятся различные методики реализации полноценного объектно-ориентированного программирования в Standard ML. Однако, простые иерархии классов можно легко воплотить базовыми конструкциями Standard ML без симулирования подтипов[8].
Для снижения рутинного кодирования некоторых часто очевидно необходимых свойств пользовательских типов, в Хаскеле предусмотрена встроенная конструкция derived, допустимая для ограниченного набора стандартных классов типов, которая также реализует значения, индексированные типами.
Иногда используется термин политипизм или обобщённость типа данных. По сути политипизм означает встроенную в язык поддержку полиморфизма конструкторов типов, предназначенную для унификации программных интерфейсов и повышения повторного использования кода. Примером политипизма является обобщённый алгоритм сопоставления с образцом[9].
По определению, в политиповой функции «хотя и возможно наличие конечного числа ad hoc-ветвей для некоторых типов, но ad hoc-комбинатор отсутствует»[10].
Политипизм может быть реализован посредством использования универсального типа данных или полиморфизма первого порядка. Расширение PolyP[11] языка 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) является политиповой, но не полиморфной (мономорфной над агрегатными типами, принадлежащими классу типов[en] Regular, для которых она, вероятно, вычисляет сумму целых, образующих объект конкретного агрегатного типа).
Параметрический полиморфизм.