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

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

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

Чистота языка
Чистота функции
Функциональная
В терминах Рефал-машины
Аппликативная
Комбинаторная
Бесточечная[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], или иногда «статическим полиморфизмом».

Термин «ad hoc полиморфизм» в русской литературе чаще всего переводится как специальный полиморфизм или специализированный полиморфизм.

Для определённых случаев полиморфизма конструкторов типов иногда используется термин «политипизм».

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

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

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

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

В дальнейшем классификацию уточнил Лука Карделли[en][8]:

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

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

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

Однако, первые эксперименты с типобезопасной параметрически полиморфной типизацией (см. Хиндли — Милнер) выявили, что определение специальных реализаций функций для разных типов в некоторых случаях является необходимостью, а не случайностью. Это привело к появлению классов типов[en], позволяющих явно управлять квантификацией переменных типа и за счёт этого перегружать параметрически полиморфные функции, что «делает ad hoc-полиморфизм в меньшей степени ad hoc»[11] (игра слов в английском языке). Однако, термин «ad hoc полиморфизм» сохранился, так как второе значение латинского «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.

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

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

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

Данный полиморфный тип позволяет построить конкретные типы List Int, List String, List List String и т.д., при этом для каждого такого типа будет использоваться одна и та же физическая реализация функций length и map.

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

Полиморфизм подтипов (полиморфизм включения)[править | править вики-текст]

«Полиморфизм подтипов[en]» (англ. subtype polymorphism), или «полиморфизм включения» (англ. inclusion polymorphism), представляет собой концепцию в теории типов, предполагающую использование единого имени (идентификатора) при обращении к объектам нескольких разных классов, при условии, что все они являются подклассами одного общего надкласса (суперкласса). Проще говоря, несколько типов формируют подмножество другого типа (их базового класса) и потому могут использоваться через общий интерфейс.

В полиморфизме включения поведение параметрически полиморфной функции ограничивается множеством типов, связанных в иерархию «супертип — подтип». Эта форма полиформизма является теоретическим основанием объектно-ориентированного программирования[12][13]. Однако, не следует путать выделение подтипов данных[en] с наследованием — подтипы определяют отношения на уровне интерфейсов, тогда как наследование определяет отношения на уровне реализации[14]. В частности, система типов языка С++ не поддерживает выделение подтипов, и наследование в нём реализуется сочетанием ad hoc-механизмов.

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

Возможность объединения подтипизации[en] с параметрическим полиморфизмом в единой теории обеспечивается связанной квантификацией[en] и ковариантностью/контравариантностью (или полярностью) конструкторов типов[12].

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

  • позднего связывания[en], где виртуальные функции не связаны до момента вызова;
  • одиночной диспетчеризации[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. Классы типов не следует путать с классами в объектно-ориентированном программировании: классы типов являются не типами, но категориями типов; их инстансы представляют собой не значения, а типы. Для снижения рутинного кодирования некоторых часто очевидно необходимых свойств пользовательских типов, в Хаскеле предусмотрена встроенная конструкция deriving, допустимая для ограниченного набора стандартных классов типов, которую нередко ошибочно классифицируют как «наследование».

Язык OCaml предоставляет встроенные возможности объектно-ориентированного программирования наряду с классическим языком модулей ML. Однако, классы в OCaml отличаются и от классов в стиле Smalltalk, и от классов в стиле Simula, являясь параметрически полиморфными типами. Определение класса параметризуется переменной типа, делая класс в ОКамле похожим на шаблон класса в С++. Аналогичные возможности реализованы в языке Eiffel. Кроме этого, ОКамл позволяет определять параметрически полиморфные («обобщённые») функции, способные обрабатывать классы, не имеющие родственных связей, так как его система типов имеет структурную[en] семантику. Методы классов в ОКамле могут быть перегружены, но для самостоятельных функций специального полиморфизма не допускается, и даже встроенные арифметические операции для разных примитивных типов записываются синтаксически различным образом:

let a =   5  +   4     (* целое *)
let b = 5.0  +.  4.0   (* вещественное *)

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

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

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

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

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

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

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

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

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

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

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

  1. 1 2 3 Strachey - Fundamental Concepts, 1967
  2. Cardelli - Typeful Programming, 1989, с. 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. Пирс - Типы в языках программирования, 23.2 Разновидности полиморфизма, с. 365
  8. 1 2 Cardelli - On Understanding Types, 1985
  9. Mitchell - Concepts in Programming Languages
  10. Mitchell - Concepts in Programming Languages, 6.4. Polymorphism and overloading, с. 145-151
  11. Wadler - How to make ad-hoc polymorphism less ad hoc
  12. 1 2 Cardelli - On Understanding Types, 6. Bounded Quantification, с. 28
  13. Abadi, Cardelli - Semantics of Object Types
  14. Mitchell - Concepts in Programming Languages, 10.2.6 Inheritance Is Not Subtyping, с. 287
  15. Johan Jeuring Polytypic pattern matching // FPCA. — 1995. — DOI:10.1.1.36.5645.
  16. Ralf Lammel and Joost Visser, «Typed Combinators for Generic Traversal», in Practical Aspects of Declarative Languages: 4th International Symposium (2002), p. 153.
  17. Patrik Jansson, Johan Jeuring PolyP - A Polytypic programming language extension. — Sigplan SPPL, 1997.
  18. Girard - Extension of Type Theory
  19. Girard - Higher-order calculus
  20. Reynolds - Theory of Type Structure
  21. Пирс - Типы в языках программирования, 2012, 1.4 Краткая история, с. 11-13

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