Полиморфи́зм в языках программирования и теории типов — способность функции обрабатывать данные разных типов.
Существует несколько разновидностей полиморфизма. Две принципиально различных из них были описаны Кристофером Стрэчи в 1967 году: это параметрический полиморфизм и ad-hoc-полиморфизм, прочие формы являются их подвидами или сочетаниями. Параметрический полиморфизм является истинным, так как подразумевает исполнение одного и того же кода для всех допустимых типов аргументов, а ad-hoc-полиморфизм — мнимым, так как представляет собой обеспечение косметической однородности потенциально разного исполнимого кода для каждого конкретного типа аргумента. При этом существуют ситуации, где необходимо использование именно ad-hoc-полиморфизма, а не параметрического. Теория квалифицированных типов объединяет все виды полиморфизма в единую модель.
Широко распространено определение полиморфизма, приписываемое Бьёрну Страуструпу: «один интерфейс (как перечень объявлений) — много реализаций (определений, связываемых с этими объявлениями)», но под это определение подпадает лишь ad-hoc-полиморфизм (мнимый полиморфизм).
Общие сведения Принципиальная возможность для одного и того же кода обрабатывать данные разных типов определяется свойствами системы типов языка. С этой точки зрения различают статическую неполиморфную типизацию (потомки Алгола и BCPL), динамическую типизацию (потомки Lisp, Smalltalk, APL) и статическую полиморфную типизацию (потомки ML). Использование ad-hoc-полиморфизма наиболее характерно для неполиморфной типизации. Параметрический полиморфизм и динамическая типизация намного существеннее, чем ad-hoc-полиморфизм, повышают коэффициент повторного использования кода, поскольку определённая единственный раз функция реализует без дублирования заданное поведение для бесконечного множества вновь определяемых типов, удовлетворяющих требуемым в функции условиям. С другой стороны, временами возникает необходимость обеспечить различное поведение функции в зависимости от типа параметра, и тогда необходимым оказывается специальный полиморфизм.
Параметрический полиморфизм является синонимом абстракции типа . Он повсеместно используется в функциональном программировании, где он обычно обозначается просто как «полиморфизм».
В сообществе объектно-ориентированного программирования под термином «полиморфизм» обычно подразумевают наследование, а использование параметрического полиморфизма называют обобщённым программированием, или иногда «статическим полиморфизмом».
Классификация Впервые классификацию разновидностей полиморфизма осуществил Кристофер Стрэчи.
Если параметру функции сопоставлен ровно один тип, то такая функция называется мономорфной. Многие языки программирования предоставляют синтаксический механизм для назначения нескольким мономорфным функциям единого имени (идентификатора). В этом случае, в исходном коде становится возможным осуществлять вызов функции с фактическими параметрами разных типов, но в скомпилированном коде фактически происходит вызов различных функций (см. перегрузка процедур и функций). Стрэчи назвал такую возможность «ad-hoc-полиморфизмом».
Если параметру функции сопоставлено более одного типа, то такая функция называется полиморфной. Разумеется, с каждым фактическим значением может быть связан лишь один тип, но полиморфная функция рассматривает параметры на основе внешних свойств, а не их собственной организации и содержания. Стрэчи назвал такую возможность «параметрическим полиморфизмом».
В дальнейшем классификацию уточнил , выделив четыре разновидности полиморфизма: универсальный параметрический включения (или ) ad-hoc перегрузка приведение типов
В некоторых работах параметрический, ad-hoc- и полиморфизм подтипов выделяются как три самостоятельных класса полиморфизма.
Двойственность смысла термина «ad hoc» (с одной стороны — «спонтанный, непродуманный, сделанный по случаю», с другой — «специальный, устроенный конкретно для данной цели или данного случая») долгие годы была заслуженной. Стрэчи выбрал этот термин, руководствуясь первым значением, подчёркивая, что при ad-hoc-полиморфизме нет единого систематичного способа вывести тип результата из типа аргументов, и хотя возможно построение определённого набора правил для сужения спектра его поиска, но эти правила по своей природе являются спонтанными как по содержанию, так и по контексту применения.
Действительно, ad-hoc-полиморфизм не является истинным полиморфизмом. Перегрузка функций даёт не «значение, имеющее множество типов», а «символ, имеющий множество типов», но значения, идентифицируемые этим символом, имеют разные (потенциально несовместимые) типы. Аналогично, приведение типов не является истинным полиморфизмом: кажется, будто оператор принимает значения множества типов, но значения должны быть преобразованы к некоторому представлению до того, как он сможет их использовать, так что на самом деле оператор работает лишь над одним типом (то есть имеет один тип). Более того, тип возвращаемого значения здесь не зависит от типа входного параметра, как в случае параметрического полиморфизма.
Тем не менее, определение специальных реализаций функций для разных типов в некоторых случаях является необходимостью, а не случайностью. Классическими примерами служат реализация арифметических операций (физически различная для целых и чисел с плавающей запятой) и равенства типов, которые на протяжении десятилетий не имели общепринятой универсальной формализации. Решением стали классы типов, представляющие собой механизм явного дискретного перечисления допустимых значений переменных типа для статической диспетчеризации в слое типов. Они сводят воедино две разновидности полиморфизма, разделённые Стрэчи, «делая ad-hoc-полиморфизм менее ad hoc» (игра на двойственности смысла). Дальнейшее обобщение классов типов привело к построению теории квалифицированных типов, единообразно формализующей самые экзотичные системы типов, включая расширяемые записи и подтипы.
В отличие от перегрузки и приведения типов, полиморфизм является истинным полиморфизмом: объектами подтипа можно манипулировать единообразно, как если бы они принадлежали к своим супертипам (но сказанное не верно для языков, реализующих «полиморфизм при наследовании» посредством приведения типов и перегрузки функций, как в случае C++). Наиболее чистым является параметрический полиморфизм: один и тот же объект или функция может единообразно использоваться в разных контекстах типизации без изменений, приведений типов или любых других проверок времени исполнения или преобразований. Однако, для этого требуется некое единообразное представление данных (например, посредством указателей).
Основные разновидности полиморфизма
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.
В динамически типизируемых языках ситуация может быть более сложной, так как выбор требуемой функции для вызова может быть осуществлён только во время исполнения программы.
Перегрузка — синтаксический механизм, позволяющий по единому идентификатору вызывать разные функции. Приведение типов — семантический механизм, осуществляемый для преобразования фактического типа аргумента к ожидаемому функцией, при отсутствии которого произошла бы ошибка типизации. То есть, при вызове функции с приведением типа происходит исполнение различного кода для различных типов (предваряющего вызов самой функции).
Параметрический полиморфизм
Параметрический полиморфизм позволяет определять функцию или тип данных обобщённо, так что значения обрабатываются идентично вне зависимости от их типа. Параметрически полиморфная функция использует аргументы на основе поведения, а не значения, апеллируя лишь к необходимым ей свойствам аргументов, что делает её применимой в любом контексте, где тип объекта удовлетворяет заданным требованиям поведения.
Развитые системы типов (такие как система Хиндли — Милнера) предоставляют механизмы для определения полиморфных типов, что делает использование полиморфных функций более удобным и обеспечивает статическую типобезопасность. Такие системы являются системами типов второго порядка, добавляющими к системам типов первого порядка (используемым в большинстве процедурных языков) параметризацию типов (посредством ти́повой переменной) и абстракцию типов (посредством экзистенциальной квантификации над ними). В системах типов второго порядка нет непосредственной необходимости в поддержке примитивных типов, так как они могут быть выражены посредством более развитых средств.
Классическим примером полиморфного типа служит список элементов произвольного типа, для которого во многих языках, типизируемых по Хиндли — Милнеру (большинство статически типизируемых функциональных языков программирования), предоставляется синтаксический сахар. Следующий пример демонстрирует определение нового алгебраического типа «параметрически полиморфный список» и двух функций над ним: 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», то без каких-либо дополняющих язык внешних средств можно доказать, что она может быть только тождественной. Поэтому параметричность часто сопровождается лозунгом «теоремы забесплатно» ().
Важным следствием этого является также независимость представлений (), означающее, что функции над абстрактным типом нечувствительны к его структуре, и различные реализации этого типа могут свободно подменять друг друга (даже в рамках одной программы), не влияя на поведение этих функций .
Наиболее развитые параметрически полиморфные системы (занимающие высшую точку в лямбда-кубе) доводят идею параметричности до возможности полного доказательства корректности программ: они позволяют записывать программы, которые верны по построению, так что прохождение проверки согласования типов само по себе даёт гарантию, что поведение программы соответствует ожидаемому.
Полиморфизм записей и вариантов