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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Развитие языков и систем типов со временем выявило большее разнообразие способов абстрагирования, и в 1985 году классификацию уточнил Лука Карделли[en].

Согласно Карделли[6], каждая из двух форм полиморфизма делится на две подформы:

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

В полиморфизме включения (или полиморфизме подтипов[en]) поведение функции ограничивается множеством типов, связанных в иерархию «супертип — подтип». Эта форма полиформизма составляет один из трёх «китов» объектно-ориентированного программирования.

Соотношение подтипов[en] с параметрическим полиморфизмом описывается связанной квантификацией[en] и ковариантностью/контравариантностью (или полярностью) конструкторов типов.

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

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

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

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

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

Cпециальный (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)

Параметрический полиморфизм также доступен в некоторых императивных (в частности, объектно-ориентированных) языках программирования, где для его обозначения обычно используется термин «обобщённое программирование»:

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 (язык Си) способна обрабатывать массивы элементов любого типа, для которого определена функция сравнения[9]. Полиморфное поведение обеспечивается здесь небезопасным образом — посредством явной передачи необходимых свойств типа через бестиповое подмножество языка[10]. Тем не менее, в Си возможно идиоматическое воспроизведение типизированного параметрического полиморфизма без использования void*[11].

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). В данном случае она является вынужденной, так как в системе типов языка отсутствует поддержка полиморфизма — полиморфный язык (см. Шаблоны C++) здесь является статической[en] надстройкой над мономорфным ядром языка[8]. Более развитые системы типов (Хиндли — Милнер) делают мономорфизацию опциональной, то есть позволяют выбирать между сохранением единственности тела полиморфной функции и размножением мономорфных тел. Типичной реализацией параметрически полиморфных типов в них является обёртнутое[en] представление объектов, но эффективно полнопрограммно-оптимизирующие компиляторы могут выполнять мономорфизацию и дефункционализацию[en] программы (см. MLton).

Мономорфизация повышает быстродействие (точнее, делает полиморфизм «бесплатным»), но вместе с тем увеличивает размер выходного машинного кода. Потенциально это может приводить к кратному увеличению объёма получаемого машинного кода (что обычно называют «раздуванием кода»[12]), но за счёт других выводимых из системы типов свойств на практике оно может оказываться незначительным (в MLton увеличение кода за счёт мономорфизации не превышает 30 %[13]).

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

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

Однако, не следует путать выделение подтипов с наследованием — подтипы определяют отношения на уровне интерфейсов, тогда как наследование определяет отношения на уровне реализации[14]. Например, в языке С++ подтипы семантически не поддерживаются, и наследование реализуется сочетанием ad hoc механизмов.

Некоторые языки представляют идею подтипов[en] для ограничения спектра типов, применимых в определённом частном случае параметрического полиморфизма. В этих языках полиморфизм подтипов (обычно называемый также динамическим полиморфизмом) позволяет функции, определённой на типе T, также корректно исполняться для аргументов, принадлежащих типу S, являющемуся подтипом T (в соответствии с принципом подстановки Барбары Лисков). Такое отношение типов обычно записывается как S <: T. При этом тип T называется надтипом (или супертипом) для S, что обозначается как T :> S.

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

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

  • позднего связывания[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   (* вещественное *)

Standard ML поддерживает только let-полиморфизм (подвид параметрического полиморфизма, исключающий полиморфизм первого класса). Для ряда встроенных арифметических операций предусмотрена перегрузка функций на правах синтаксического сахара, но определять пользовательские перегруженные функции не допускается. Реализация ad hoc полиморфизма в Standard ML осуществляется посредством так называемых «значений, индексированных типами» (англ. type-indexed values), представляющих собой эмуляцию подобия классов типов[en]. На основе значений, индексированных типами, симулируются подтипы[en], на основе которых строятся различные методики реализации полноценного объектно-ориентированного программирования в Standard ML. Однако, простые иерархии классов можно легко воплотить базовыми конструкциями Standard ML без симулирования подтипов[15].

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

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

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

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

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

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

  1. 1 2 C. Strachey — Fundamental Concepts in Programming Languages
  2. Cardelli - Typeful Programming, 1989, с. 3
  3. Pierce, 22.7. Полиморфизм через let, с. 354
  4. Andrew W. Appel A Critique of Standard ML. — Princeton University, 1992..
  5. Pierce, 23.2 Разновидности полиморфизма, с. 365
  6. 1 2 Cardelli - On Understanding Types, 1985
  7. Pierce, 2012, 1.4 Краткая история, с. 11-13
  8. 1 2 Mitchell - Concepts in Programming Languages, 6.4. Polymorphism and overloading, с. 145-151
  9. Керниган Б., Ритчи Д. Язык программирования Си = The C programming language. — 2-е изд. — Вильямс, 2007. — С. 304. — ISBN 0-13-110362-8., Глава 5.11. Указатели на функции
  10. Appel - A Critique of Standard ML, 1992, с. 5
  11. Truly polymorphic lists in C
  12. Scott Meyers. Code Bloat due to Templates. comp.lang.c++.moderated. Usenet (16 мая 2002). Проверено 19 января 2010.
  13. Stephen Weeks Whole-Program Compilation in MLton. — 2006.
  14. Mitchell - Concepts in Programming Languages, 10.2.6 Inheritance Is Not Subtyping, с. 287
  15. [mlton.org/ObjectOrientedProgramming Object-Oriented Programming in Standard ML]
  16. Johan Jeuring Polytypic pattern matching // FPCA. — 1995. — DOI:10.1.1.36.5645.
  17. Ralf Lammel and Joost Visser, «Typed Combinators for Generic Traversal», in Practical Aspects of Declarative Languages: 4th International Symposium (2002), p. 153.
  18. Patrik Jansson, Johan Jeuring PolyP - A Polytypic programming language extension. — Sigplan SPPL, 1997..

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