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

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

В языках программирования и теории типов полиморфизмом называется способность функции обрабатывать данные разных типов[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[источник?], наряду с понятиями наследования и инкапсуляции. Спустя несколько лет был разработан первый стандарт объектно-ориентированного программирования — подмножество Common Lisp Object System языка Common Lisp.

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

Cпециальный (ad hoc) полиморфизм[править | править вики-текст]

Если функция описывает разные реализации (возможно, с различным поведением) для ограниченного набора явно заданных типов и их комбинаций, это называется специальным полиморфизмом (ad hoc polimorphism). Специальный полиморфизм поддерживается во многих языках посредством перегрузки функций и методов.

Термин «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)

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

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

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

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

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] надстройкой над мономорфным ядром языка). Более развитые системы типов (Хиндли — Милнер) делают мономорфизацию опциональной, то есть позволяют выбирать между сохранением единственности тела полиморфной функции и размножением мономорфных тел. Например, для языка Standard ML компилятор SML/NJ[5] сохраняет тела функций единственными, в то время как 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], и обычно содержит большее количество типов.

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

  • позднего связывания[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. Классы типов не следует путать с классами в объектно-ориентированном программировании: классы типов являются не типами, но категориями типов; их инстансы представляют собой не значения, а типы.

Язык 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, допустимая для ограниченного набора стандартных классов типов, которая также реализует значения, индексированные типами.

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

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

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

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

  1. 1 2 C. Strachey — Fundamental Concepts in Programming Languages
  2. Cardelli - Typeful Programming, 1989, с. 3
  3. Andrew W. Appel A Critique of Standard ML. — Princeton University, 1992.
  4. Cardelli - On Understanding Types, 1985
  5. Компилятор Standard ML Of New Jersey
  6. Компилятор MLton
  7. Stephen Weeks Whole-Program Compilation in MLton. — 2006.
  8. [mlton.org/ObjectOrientedProgramming Object-Oriented Programming in Standard ML]
  9. Ralf Lammel and Joost Visser, «Typed Combinators for Generic Traversal», in Practical Aspects of Declarative Languages: 4th International Symposium (2002), p. 153.

Ссылки[править | править вики-текст]

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