Русская Википедия:Полиморфизм (информатика)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Не путать Шаблон:Нужна статья Шаблон:Полиморфизм Шаблон:Парадигмы программирования Полиморфизм в языках программирования и теории типов — способность функции обрабатывать данные разных типовШаблон:SfnШаблон:SfnШаблон:Sfn.

Существует несколько разновидностей полиморфизма. Две принципиально различных из них были описаны Шаблон:Iw в 1967 году: это параметрический полиморфизмШаблон:Переход и ad-hoc-полиморфизмШаблон:Переход, прочие формы являются их подвидами или сочетаниями. Параметрический полиморфизм является истинным, т.к. подразумевает исполнение одного и того же кода для всех допустимых типов аргументов, а ad-hoc-полиморфизм — мнимым, т.к. представляет собой обеспечение косметической однородности потенциально разного исполнимого кода для каждого конкретного типа аргументаШаблон:SfnШаблон:Sfn. При этом существуют ситуации, где необходимо использование именно ad-hoc-полиморфизма, а не параметрическогоШаблон:Sfn. Теория квалифицированных типов объединяет все виды полиморфизма в единую модель.

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

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

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

Параметрический полиморфизмШаблон:Переход является синонимом абстракции типа Шаблон:Sfn. Он повсеместно используется в функциональном программировании, где он обычно обозначается просто как «полиморфизм».

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

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

Впервые классификацию разновидностей полиморфизма осуществил Шаблон:IwШаблон:Переход.

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

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

В дальнейшем классификацию уточнил Шаблон:IwШаблон:Sfn, выделив четыре разновидности полиморфизма:

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

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

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

Тем не менее, определение специальных реализаций функций для разных типов в некоторых случаях является необходимостью, а не случайностью. Классическими примерами служат реализация арифметических операций (физически различная для целых и чисел с плавающей запятой) и равенства типов, которые на протяжении десятилетий не имели общепринятой универсальной формализации. Решением стали классы типовШаблон:Переход, представляющие собой механизм явного дискретного перечисления допустимых значений переменных типа для статической диспетчеризации в слое типов. Они сводят воедино две разновидности полиморфизма, разделённые Стрэчи, «делая ad-hoc-полиморфизм менее ad hoc»Шаблон:Sfn (игра на двойственности смысла). Дальнейшее обобщение классов типов привело к построению теории квалифицированных типов, единообразно формализующей самые экзотичные системы типов, включая расширяемые записиШаблон:Переход и подтипы.

В отличие от перегрузки и приведения типов, полиморфизм Шаблон:IwШаблон:Переход является истинным полиморфизмом: объектами подтипа можно манипулировать единообразно, как если бы они принадлежали к своим супертипам (но сказанное не верно для языков, реализующих «полиморфизм при наследовании» посредством приведения типов и перегрузки функций, как в случае C++). Наиболее чистым является параметрический полиморфизмШаблон:Переход: один и тот же объект или функция может единообразно использоваться в разных контекстах типизации без изменений, приведений типов или любых других проверок времени исполнения или преобразований. Однако, для этого требуется некое единообразное представление данных (например, посредством указателей)Шаблон:Sfn.

Основные разновидности полиморфизма

Ad-hoc-полиморфизм

Шаблон:Falseredirect 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.

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

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

Параметрический полиморфизм

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

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

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

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.

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

Шаблон:Details

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

Формализация параметрического полиморфизма ведёт к понятию Шаблон:Iw, состоящему в возможности предсказывать поведение программ, глядя только на их типы. Например, если функция имеет тип «forall a. a -> a», то без каких-либо дополняющих язык внешних средств можно доказать, что она может быть только тождественной. Поэтому параметричность часто сопровождается лозунгом «теоремы забесплатно» (Шаблон:Lang-en). Шаблон:Sfn Шаблон:SfnШаблон:Sfn

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

Наиболее развитые параметрически полиморфные системы (занимающие высшую точку в лямбда-кубе) доводят идею параметричности до возможности полного доказательства корректности программ: они позволяют записывать программы, которые верны по построению, так что прохождение проверки согласования типов само по себе даёт гарантию, что поведение программы соответствует ожидаемомуШаблон:Sfn.

Шаблон:Details

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

Отдельную проблему представляет распространение параметрического полиморфизма на агрегатные типы: размеченные произведения типов (традиционно называемые записями) и размеченные суммы типов (также известные как Шаблон:Iw). Различные «исчисления записей» (Шаблон:Lang-en) служат формальной базой для объектно-ориентированного и модульного программированияШаблон:Sfn. 

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

Многоточие означает некоторый ряд типизированных полей, то есть абстракцию кода от конкретных типов записей, которые могли бы здесь обрабатываться (причём «длина» этого ряда также может варьироваться). Компиляция полиморфного обращения к полям, которые могут располагаться в разном порядке в разных записях, представляет сложную проблему, как с точки зрения контроля безопасности операций на уровне языка, так и с точки зрения быстродействия на уровне машинного кода. Наивным решением может быть динамический поиск по словарю при каждом обращении (и скриптовые языки его применяют), однако, очевидно, что это чрезвычайно неэффективно. Эта проблема активно исследуется на протяжении уже нескольких десятилетий; построено множество теоретических моделей и практичных систем на их основе, различающихся по выразительной мощности и метатеоретической сложности. Важнейшими достижениями в этой области считаются рядный полиморфизм, предложенный Шаблон:Нп2), и полиморфное исчисление записей, построенное Ацуси Охори (Шаблон:Lang-en). Более распространённой, но отстающей по многим характеристикам моделью является подтипизация на записяхШаблон:Переход.

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

Шаблон:Details

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

Полиморфизм включения (Шаблон:Lang-en2) является обобщённой формализацией Шаблон:Iw и наследованияШаблон:Sfn. Эти понятия не следует путать: Шаблон:Iw определяют отношения на уровне интерфейсов, тогда как наследование определяет отношения на уровне реализацииШаблон:Sfn.

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

Идея подтипов мотивируется увеличением множества типов, которые могут обрабатываться уже написанными функциями, и за счёт этого повышением коэффициента повторного использования кода в условиях сильной типизации (то есть увеличением множества типизируемых программ). Это обеспечивается правилом включения (Шаблон:Lang-en2): «если выражение e принадлежит к типу t' в контексте типизации Г, и выполняется t'<:t, то e принадлежит также и к типу t»Шаблон:Sfn Шаблон:Sfn.

Отношения подтипизации возможны на самых разных категориях типов: примитивных типах (как Integer <: Number), типах-суммах, типах-произведениях, функциональных типах и др. Более того, Шаблон:Iw предложил концепцию степенны́х родо́в (Шаблон:Lang-en2) для описания подтипизацииШаблон:Sfn: степенью данного типа в слое родо́в (Шаблон:Lang-en2) он назвал род всех его подтиповШаблон:Sfn.

Особое место в информатике занимает подтипизация на записяхШаблон:Переход.

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

Подтипизация на записях, также известная как включение или вхождение (Шаблон:Lang-en2 — см. принцип подстановки Барбары Лисков), служит наиболее распространённым теоретическим обоснованием объектно-ориентированного программирования (ООП)Шаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn (но не единственным — см. #полиморфизм записей и вариантов).

Мартин Абади (Шаблон:Lang-en2) и Шаблон:Iw формализовали подтипизацию на записях посредством Шаблон:Iw над параметрически полиморфными типамиШаблон:SfnШаблон:Sfn; при этом параметр типа задаётся неявноШаблон:Sfn.

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

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

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. (Здесь подразумевается Шаблон:Iw семантика системы типов.)

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

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

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

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

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

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

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

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

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

Из определений выше можно вывести, что Sports <: Voyage и Vacation <: Voyage.

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

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

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

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

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

Некоторые языки используют своеобразные ad-hoc]решения. Например, система типов языка C++ предусматривает автоматическое приведение типов (то есть является слабой), неполиморфная, эмулирует Шаблон:Iw через Шаблон:Iw наследование с инвариантными сигнатурами методов и не поддерживает абстракцию типов (не путать с сокрытием полей). Наследование в C++ реализуется набором ad-hoc-механизмов, однако, его использование называется в сообществе языка «полиморфизмом» (а сокрытие полей — «абстракцией»Шаблон:Sfn). Имеется возможность управлять графом наследования: ромбовидное наследование в C++ называется «виртуальным наследованием» и задаётся явным атрибутом virtual; по умолчанию же осуществляется дублирование унаследованных полей с доступом к ним по квалифицированному имени. Использование такого языка может быть небезопасно — нельзя гарантировать устойчивость программШаблон:SfnШаблон:Sfn (язык называется безопасным, если программы на нём, которые могут быть приняты компилятором как правильно построенные, в динамике никогда не выйдут за рамки допустимого поведения Шаблон:Sfn).

Подтипизация высшего порядка

Система <math>F^\omega_{<:}</math> является расширением Системы F (не представленным в лямбда-кубе), формализующим Шаблон:Iw над ти́повыми операторами, распространяя отношения подтипизации с рода * на типы высших родо́в. Существует несколько вариантов системы <math>F^\omega_{<:}</math>, различающихся по выразительной мощности и метатеоретической сложности, но большинство основных идей заложил Шаблон:IwШаблон:Sfn.

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

Классы типов

Шаблон:Falseredirect Класс типов реализует единую независимую таблицу виртуальных методов для множества (универсально квантифицированных) типов. Этим классы типов отличаются от классов в объектно-ориентированном программировании, где всякий объект всякого (Шаблон:Iw квантифицированного) типа сопровождается указателем на таблицу виртуальных методовШаблон:Sfn. Классы типов являются не типами, но категориями типов; их экземпляры представляют собой не значения, а типы.

НапримерШаблон:Sfn: 

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)

Поскольку операция умножения реализуется физически различным образом для целых и чисел с плавающей запятой, в отсутствии классов типов уже здесь потребовались бы две перегруженные функции square и восемь перегруженных функций squares3, а в реальных программах со сложными структурами данных дублирующегося кода оказывается намного больше. В объектно-ориентированном программировании проблемы такого рода решаются посредством Шаблон:Iw, с соответствующими накладными расходами. Класс типов осуществляет диспетчеризацию статически, сводя параметрическийШаблон:Переход и ad-hoc полиморфизмы в единую модельШаблон:Sfn. С точки зрения параметрического полиморфизма, класс типов имеет параметр (переменную типа), пробегающий множество типов. С точки зрения ad-hoc-полиморфизма, это множество не только дискретно, но и задано явным образом до уровня реализации. Проще говоря, сигнатура square :: Num a => a -> a означает, что функция параметрически полиморфна, но спектр типов её параметра ограничен лишь теми типами, что принадлежат к классу типов Num. Благодаря этому, функция типизируется единственным образом, несмотря на обращение к перегруженной функции из её тела.

Встроенная поддержка классов типов была впервые реализована в языке Haskell, но они также могут быть введены в любой параметрически полиморфный язык путём простого препроцессингаШаблон:Sfn, а также реализованы идиоматически (см., например, язык модулей ML#Реализация альтернативных моделей). Однако, непосредственная поддержка может упрощать автоматическое рассуждение о смысле программ.

Шаблон:Iw в Haskell реализуются как инстансы класса типов Eq (обобщая [[переменная типа#Специальные переменные типа|переменные типа, допускающего проверку на равенство (Шаблон:Lang-en2)]] из Standard ML): 

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

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

Шаблон:Also

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

Шаблон:Main Шаблон:Заготовка раздела

Политипизм

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

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

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

Прочее

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

Статически полиморфно типизированные языки, напротив, могут реализовать разновидности полиморфизма ортогонально (независимо друг от друга), позволяя выстраивать их хитросплетение типобезопасным образом. Например, OCaml поддерживает параметрические классы (по возможностям аналогичные шаблонам классов C++, но верифицируемые без необходимости инстанцирования), их наследование вширь и вглубьШаблон:Переход (в том числе множественное), идиоматическую реализацию классов типовШаблон:Переход (посредством сигнатур — см. соответствующий пример использования языка модулей ML), рядный полиморфизмШаблон:Переход, параметрический полиморфизм рангов выше 1-го (посредством так называемых локально-абстрактных типов, реализующих экзистенциальные типы) и обобщённые алгебраические типы данныхШаблон:Переход.

Шаблон:Also

История

Термин «полиморфизм» происходит от Шаблон:Lang-el («много») и Шаблон:Lang-el2 («форма, облик, устройство»).

Термины «специализированный полиморфизм» и «параметрический полиморфизм» впервые упоминаются в 1967 году в конспекте лекций Шаблон:Iw под названием «Шаблон:Iw»Шаблон:Sfn. В 1985 году Шаблон:Iw и Шаблон:Iw формализовали полиморфизм включения для моделирования Шаблон:Iw и наследованияШаблон:SfnШаблон:Sfn, хотя реализации подтипов и наследования появились намного раньше, в языке Симула в 1967 году. Полиморфизм включения основан на Шаблон:Iw.

Нотацию параметрического полиморфизма как развитие λ-исчисления (названную системой F) формально описал логик Шаблон:IwШаблон:SfnШаблон:Sfn (1971 год), независимо от него похожую систему описал информатик Шаблон:IwШаблон:Sfn (1974 год).

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

В 1987 году Митчел Уэнд (Шаблон:Lang-en2) формализовал рядный полиморфизмШаблон:Переход и выведение типов для негоШаблон:Sfn; эта работа оказала огромное влияние на последующее развитие систем типов. В том же году Шаблон:Нп2 и Стивен Блотт (Шаблон:Lang-en2) предложили классы типовШаблон:Переход для формализации ad-hoc-полиморфизма.

См. также

Примечания

Шаблон:Примечания

Литература

Внешние ссылки

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Статья
  3. ↑ Шаблон:Cite web
  4. ↑ Шаблон:Статья
  5. ↑ Шаблон:Статья
  6. ↑ Шаблон:Статья
  7. ↑ Ralf Lammel and Joost Visser, «Typed Combinators for Generic Traversal», in Practical Aspects of Declarative Languages: 4th International Symposium (2002), p. 153.
  8. ↑ Шаблон:Статья

Шаблон:Выбор языка

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Полиморфизм_(информатика)&oldid=10615742