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

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

В языках программирования и теории типов полиморфизмом называется единообразная обработка разнотипных данных.

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

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

Если же код написан отвлеченно от конкретного типа данных и потому может свободно использоваться с любыми новыми типами, имеет место параметрический полиморфизм. Джон С.Рейнольдс, и независимо от него Жан-Ив Жирар формально описали эту нотацию как развитие лямбда-исчисления (названную полиморфным лямбда-исчислением или Системой F). Параметрический полиморфизм широко используется в статически типизируемых функциональных языках программирования. В объектно-ориентированном сообществе программирование с использованием параметрического полиморфизма называется обобщённым программированием.

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

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

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

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

Термин «полиморфизм» происходит от др.-греч. πολύς («много») и μορφή («форма, облик, устройство»). Термин впервые упоминается в конспекте лекций Кристофера Стрэчи под названием «Фундаментальные основы языков программирования». Впервые полиморфизм реализован в языке ML, наряду с понятиями наследования и инкапсуляции. Спустя несколько лет подмножество Common Lisp Object System языка Common Lisp было стандартизировано, став первым стандартом объектно-ориентированного программирования.

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

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

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

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

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[2] сохраняет тела функций единственными, в то время как MLton[3] выполняет полную мономорфизацию программы. В таких языках увеличение размера машинного кода может оказываться незначительным за счёт других выводимых из системы типов свойств (так, в MLton увеличение кода за счёт мономорфизации не превышает 30 %[4])

Специализированный (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.

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

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

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

Некоторые языки представляют идею подтипов[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());
    } 
}

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

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

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

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