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

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

Существует несколько разновидностей полиморфизма. Две принципиально различных из них были описаны

Общие сведения

Принципиальная возможность для одного и того же кода обрабатывать данные разных типов определяется свойствами

Параметрический полиморфизм^[⇨] является синонимом абстракции типа ^[8]. Он повсеместно используется в функциональном программировании, где он обычно обозначается просто как «полиморфизм».

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

Классификация

Впервые классификацию разновидностей полиморфизма осуществил Кристофер Стрэчи^{[англ.][⇨]}.

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

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

В дальнейшем классификацию уточнил Лука Карделли^{[англ.][10]}, выделив четыре разновидности полиморфизма:

• универсальный
  • параметрический
  • включения (или подтипов^[англ.])^[⇨]
• ad-hoc
  • перегрузка
  • приведение типов

В некоторых работах параметрический, ad-hoc- и полиморфизм подтипов выделяются как три самостоятельных класса полиморфизма^[11].

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

Действительно, 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.

Ограниченные формы параметрического полиморфизма доступны также в некоторых

Параметричность

Формализация параметрического полиморфизма ведёт к понятию

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

Наиболее развитые параметрически полиморфные системы (занимающие высшую точку

Полиморфизм записей и вариантов

Отдельную проблему представляет распространение параметрического полиморфизма на агрегатные типы: размеченные произведения типов (традиционно называемые записями) и размеченные суммы типов (также известные как вариантные типы^[англ.]). Различные «исчисления записей» (англ. record calculi) служат формальной базой для объектно-ориентированного и модульного программирования^[20].

val r = {a = 1, b = true, c = "hello"}
val {a = n, ... = r1} = r
val r2 = {d = 3.14, ... = r1}

Многоточие означает некоторый ряд типизированных полей, то есть

Полиморфизм подтипов

Полиморфизм включения (inclusion polymorphism) является обобщённой формализацией подтипизации^[англ.] и наследования^[21]. Эти понятия не следует путать: подтипы^[англ.] определяют отношения на уровне интерфейсов, тогда как наследование определяет отношения на уровне реализации^[22].

Подтипизация (subtyping), или полиморфизм подтипов (subtype polymorphism), означает, что поведение

Идея подтипов мотивируется увеличением множества типов, которые могут обрабатываться уже написанными функциями, и за счёт этого повышением коэффициента повторного использования кода в условиях сильной типизации (то есть увеличением множества типизируемых программ). Это обеспечивается правилом включения (subsumption rule): «если выражение e принадлежит к типу t' в контексте типизации Г, и выполняется t'<:t, то e принадлежит также и к типу t»^{[25] [26]}.

Отношения подтипизации возможны на самых разных категориях типов: примитивных типах (как Integer <: Number), типах-суммах, типах-произведениях, функциональных типах и др. Более того, Лука Карделли^[англ.] предложил концепцию степенны́х родо́в («power» kinds) для описания подтипизации^[27]: степенью данного типа в слое родо́в (power-kind of the type) он назвал род всех его подтипов^[28].

Особое место в информатике занимает подтипизация на записях^[⇨].

Подтипизация на записях

Подтипизация на

В подтипизации на записях выделяются две разновидности: в ширину и в глубину.

Подтипизация в ширину (width subtyping) подразумевает добавление в запись новых полей. Например:

type Object  = { age: Int }
type Vehicle = { age: Int; speed: Int }
type Bike    = { age: Int; speed: Int; gear: Int; }
type Machine = { age: Int; fuel: String }

С одной стороны, можно записать отношения подтипизации Vehicle <: Object, Bike <: Vehicle (а поскольку подтипизация транзитивна, то и Bike <: Object) и Machine <: Object. С другой стороны, можно говорить, что типы Vehicle, Bike и Machine включают (наследуют) все свойства типа Object. (Здесь подразумевается структурная^[англ.] семантика системы типов.)

Поскольку интуитивно тип зачастую рассматривается как множество значений, то увеличение количества полей в подтипе может выглядеть контринтуитивно с точки зрения теории множеств. В действительности, типы — это не множества ^[33], они предназначены для верификации поведения программ, и идея подтипизации состоит в том, что подтип обладает по меньшей мере свойствами своего супертипа, и таким образом, способен эмулировать его как минимум там, где ожидается объект супертипа^[25]. Или иначе: супертип определяет минимальный набор свойств для множества объектов, и тогда тип, обладающий этими свойствами и, возможно, какими-то другими, формирует подмножество этого множества, а следовательно, является его подтипом^[30].

Отношения подтипов в терминах множеств выглядят более интуитивно в случае с вариантными типами^[34]:

type Day     = mon | tue | wed | thu | fri | sat | sun
type Workday = mon | tue | wed | thu | fri
type WeekEnd = sat | sun

Здесь Workday <: Day и WeekEnd <: Day.

Именование полей позволяет абстрагироваться от порядка их следования в записях (в отличие от кортежей), что даёт возможность строить произвольные направленные ацикличные графы наследования, формализуя множественное наследование^[34]:

type Car = { age: Int; speed: Int; fuel: String }

Теперь Car <: Vehicle и одновременно Car <: Machine. Очевидно также, что Car <: Object (см. ромбовидное наследование).

Подтипизация в глубину (depth subtyping) подразумевает, что типы конкретных полей записи могут подменяться на их подтипы:

type Voyage   = { veh: Vehicle; date: Day }
type Sports   = { veh: Bike;    date: Day }
type Vacation = { veh: Car;     date: WeekEnd }

Из определений выше можно

Методы в подтипах записей

Полноценная поддержка объектно-ориентированного программирования предполагает включение в число полей записей также функций, обрабатывающих значения типов записей, которым они принадлежат^[29][35]. Такие функции традиционно называются «методами». Обобщённой моделью связывания записей с методами является матрица диспетчеризации (dispatch matrix); на практике большинство языков раскладывают её на вектора по строкам либо по столбцам — соответственно, реализуя либо организацию на основе классов (class-based organisation), либо организацию на основе методов (method-based organisation) ^[36]. При этом следует отличать переопределение методов в подтипах (method overriding) от подтипизации функций (functional subtyping). Переопределение методов не связывает их отношениями подтипизации на функциях, но позволяет изменять сигнатуры их типов. При этом возможны три варианта: инвариантное, ковариантное и контравариантное переопределение, и два последних используют подтипизацию своих параметров^[37] (подробнее см. ковариантность и контравариантность). Исчисление Абади — Карделли^[29] рассматривает только инвариантные методы, что необходимо для доказательства безопасности.

Многие объектно-ориентированные языки предусматривают встроенный механизм связывания функций в методы, реализуя таким образом организацию программ на основе классов. Языки, рассматривающие функции как объекты первого класса и типизирующие их (см. функции первого класса, функциональный тип — не путать с типом возвращаемого значения функции), позволяют произвольно выстраивать организацию на основе методов, что обеспечивает возможность производить объектно-ориентированное проектирование без прямой поддержки со стороны языка^[38]. Некоторые языки (например, OCaml) поддерживают обе возможности.

Языки с системами типов, основанными на формальной теории подтипизации (OCaml, проект successor ML), рассматривают системы объектов и системы классов независимо^[39][40]. Это значит, что с объектом связывается прежде всего объектный тип, и лишь при явном указании объектный тип связывается с неким классом. При этом динамическая диспетчеризация^[англ.] осуществляется на уровне объекта, а значит, в таких языках два объекта, относящиеся к одному классу, вообще говоря, могут иметь различный набор методов. Вместе с формально определённой семантикой множественного наследования это даёт непосредственную всестороннюю поддержку примесей.

CLOS реализует матрицу диспетчеризации посредством мультиметодов, то есть динамически диспетчеризуемых методов, полиморфных сразу по нескольким аргументам^[41].

Некоторые языки используют своеобразные ad-hoc]решения. Например,

Система ${\displaystyle F_{<:}^{\omega }}$ является расширением Системы F (не представленным в лямбда-кубе), формализующим ограниченную квантификацию^[англ.] над ти́повыми операторами, распространяя отношения подтипизации с рода * на типы высших родо́в. Существует несколько вариантов системы ${\displaystyle F_{<:}^{\omega }}$, различающихся по выразительной мощности и метатеоретической сложности, но большинство основных идей заложил Лука Карделли^{[англ.][45]}.

Сочетание разновидностей полиморфизма

Классы типов

Класс типов реализует единую независимую таблицу виртуальных методов для множества (

Например[46]:

class Num a where
   (+), (*) :: a -> a -> a
   negate :: a -> a

Это объявление читается так: «Тип a принадлежит классу Num, если на нём определены функции (+), (*) и negate, с заданными сигнатурами».

instance Num Int where
   (+) = addInt
   (*) = mulInt
   negate = negInt

instance Num Float where
   (+) = addFloat
   (*) = mulFloat
   negate = negFloat

Первое объявление читается так: «Существуют функции (+), (*) и negate соответствующих сигнатур, которые определены над типом Int». Аналогично читается второе утверждение.

Теперь можно

square :: Num a => a -> a
square x = x * x

squares3 :: Num a, Num b, Num c => (a, b, c) -> (a, b, c)
squares3 (x, y, z) = (square x, square y, square z)

Типы, допускающие проверку на равенство (equality types)^[англ.] в Haskell реализуются как инстансы класса типов Eq (обобщая переменные типа, допускающего проверку на равенство (equality type variables) из Standard ML):

(==) :: Eq a => a -> a -> Bool

Для снижения рутинного кодирования некоторых часто очевидно необходимых свойств пользовательских типов в Haskell дополнительно предусмотрен синтаксический сахар — конструкция deriving, допустимая для ограниченного набора стандартных классов типов (таких как Eq). (В русскоязычном сообществе её использование нередко путается с понятием «наследования» из-за особенностей перевода слова «derive».)

Обобщённые алгебраические типы данных

Этот раздел исправив и дополнив его.

Политипизм

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

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

Политипизм может быть реализован посредством использования

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

head   :: [a] -> a
(+)    :: Num a => a -> a -> a
length :: Regular d => d a -> Int
sum    :: Regular d => d Int -> Int

Первая функция (head) является полиморфной (параметрически полиморфной

Прочее

История

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

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

Нотацию параметрического полиморфизма как развитие λ-исчисления (названную системой F) формально описал логик Жан-Ив Жирар^{[англ.][50][51]} (1971 год), независимо от него похожую систему описал информатик Джон С. Рейнольдс^{[англ.][52]} (1974 год).

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

В 1987 году Митчел Уэнд (Mitchel Wand) формализовал рядный полиморфизм

• Каламбур типизации
• Инкапсуляция

Примечания

Литература

• Christopher Strachey. Fundamental Concepts in Programming Languages (англ.). — 1967. Архивировано 12 августа 2017 года.
  • Повторно опубликовано: Christopher Strachey. Fundamental Concepts in Programming Languages (англ.) //
    doi:10.1023/A:1010000313106
    .
• Jean-Yves Girard. Une Extension de l’Interpretation de Gödel à l’Analyse, et son Application à l'Élimination des Coupures dans l’Analyse et la Théorie des Types (фр.) // Proceedings of the Second Scandinavian Logic Symposium. — Amsterdam, 1971. — P. 63—92. —
  doi:10.1016/S0049-237X(08)70843-7
  .
• Jean-Yves Girard. Interprétation fonctionnelle et élimination des coupures de l’arithmétique d’ordre supérieur (фр.). — Université Paris 7, 1972.
• John C. Reynolds. Towards a Theory of Type Structure //
  doi:10.1007/3-540-06859-7_148
  .
• doi:10.1145/6041.6042
  .