Открыть главное меню

Изменения

м
орфография, стандартизации, избыточные выделения по замеченному
{{Парадигмы программирования}}
{{не путать|Полиморфизм компьютерных вирусов}}
В'''Полиморфизм''' в [[язык программирования|языках программирования]] и [[Теория типов|теории типов]] '''полиморфизмом''' называется — способность [[функция (программирование)|функции]] обрабатывать данные разных [[Тип данных|типов]]{{sfn|Strachey|1967}}{{sfn|Cardelli|1991|с=3}}{{sfn|Пирс|2012|loc=22.7. Полиморфизм через let|с=354}}.
 
Существует несколько разновидностей полиморфизма. Две принципиально различных из них были описаны {{iw|Стрэчи, Кристофер|Кристофером Стрэчи|en|Christopher Strachey}} в [[1967 год в науке|1967 году]]у: это [[параметрический полиморфизм]]{{переход|#Параметрический полиморфизм|text}} и [[ad -hoc полиморфизм|{{nobr|ad hoc}} -полиморфизм]]{{переход|#Ad -hoc -полиморфизм|text}}, причём первая является истинной формой, а вторая - — мнимой{{sfn|Strachey|1967}}{{sfn|Cardelli|1985|с=6}}; прочие формы являются их подвидами или сочетаниями. Параметрический полиморфизм подразумевает исполнение одного и того же кода для всех допустимых типов аргументов, тогда как ad-hoc-полиморфизм подразумевает исполнение потенциально разного кода для каждого типа или подтипа аргумента. [[Бьёрн Страуструп]] определил полиморфизм как «''один интерфейс — много реализаций''»<ref>{{cite web
В [[язык программирования|языках программирования]] и [[Теория типов|теории типов]] '''полиморфизмом''' называется способность [[функция (программирование)|функции]] обрабатывать данные разных [[Тип данных|типов]]{{sfn|Strachey|1967}}{{sfn|Cardelli|1991|с=3}}{{sfn|Пирс|2012|loc=22.7. Полиморфизм через let|с=354}}.
 
Существует несколько разновидностей полиморфизма. Две принципиально различных из них были описаны {{iw|Стрэчи, Кристофер|Кристофером Стрэчи|en|Christopher Strachey}} в [[1967 год]]у: это [[параметрический полиморфизм]]{{переход|#Параметрический полиморфизм|text}} и [[ad hoc полиморфизм|{{nobr|ad hoc}} полиморфизм]]{{переход|#Ad hoc полиморфизм|text}}, причём первая является истинной формой, а вторая - мнимой{{sfn|Strachey|1967}}{{sfn|Cardelli|1985|с=6}}; прочие формы являются их подвидами или сочетаниями.
 
Параметрический полиморфизм подразумевает исполнение '''одного и того же''' кода для всех допустимых типов аргументов, тогда как {{nobr|ad hoc}} полиморфизм подразумевает исполнение потенциально '''разного''' кода для каждого типа или подтипа аргумента.
 
[[Бьерн Страуструп]] определил полиморфизм как «''один интерфейс — много реализаций''»<ref>{{cite web
| автор = [[Страуструп, Бьёрн|Bjarne Stroustrup]].
| title = C++ Glossary
| archivedate =
| ref = Bjarne Stroustrup's C++ Glossary
}}</ref>, но это определение покрывает лишь ad -hoc -полиморфизм.
 
== Общие сведения ==
}}</ref> статическую неполиморфную типизацию (потомки [[Алгол]]а и [[BCPL]]), динамическую типизацию (потомки [[Lisp]], [[Smalltalk]], [[APL (язык программирования)|APL]]) и статическую [[полиморфизм типов|полиморфную типизацию]] (потомки [[ML]]). Использование {{nobr|ad hoc}} полиморфизма наиболее характерно для неполиморфной типизации. Параметрический полиморфизм и динамическая типизация намного существеннее, чем {{nobr|ad hoc}} полиморфизм, повышают коэффициент [[повторное использование кода|повторного использования кода]], поскольку определённая единственный раз функция реализует без дублирования заданное поведение для бесконечного множества вновь определяемых типов, удовлетворяющих требуемым в функции условиям. С другой стороны, временами возникает необходимость обеспечить различное поведение функции в зависимости от типа параметра, и тогда необходимым оказывается специальный полиморфизм.
 
[[Параметрический полиморфизм]]{{переход|#параметрический полиморфизм|text}} является синонимом '''абстракции типа''' {{sfn|Harper|2012|loc=20.1 System F|с=172}}. Он повсеместно используется в [[функциональное программирование|функциональном программировании]], где он обычно обозначается просто как «полиморфизм».
 
В сообществе [[объектно-ориентированное программирование|объектно-ориентированного программирования]] под термином «полиморфизм» обычно подразумевают [[наследование (программирование)|наследование]], а использование параметрического полиморфизма называют [[обобщённое программирование|обобщённым программированием]]{{sfn|Пирс|2012|loc=23.2 Разновидности полиморфизма|с=365}}, или иногда «статическим полиморфизмом».
 
== Классификация ==
Впервые классификацию разновидностей полиморфизма осуществил {{iw|Стрэчи, Кристофер|Кристофер Стрэчи|en|Christopher Strachey}}{{переход|#История|text}}.
 
Если параметру функции сопоставлен ровно один тип, то такая функция называется '''мономорфной'''. Многие языки программирования предоставляют синтаксический механизм для назначения нескольким мономорфным функциям единого имени (идентификатора). В этом случае, в исходном коде становится возможным осуществлять вызов функции с фактическими параметрами разных типов, но в скомпилированном коде фактически происходит вызов ''различных'' функций (см. [[перегрузка процедур и функций]]). {{iw|Стрэчи, Кристофер|Стрэчи|en|Christopher Strachey}} назвал такую возможность «''{{nobr|ad -hoc}} -полиморфизмом''»{{переход|#ad hoc полиморфизм|text}}.
 
Если параметру функции сопоставлено более одного типа, то такая функция называется '''полиморфной'''. Разумеется, с каждым фактическим значением может быть связан лишь один тип, но полиморфная функция рассматривает параметры на основе внешних свойств, а не их собственной организации и содержания. Стрэчи назвал такую возможность «''параметрическим полиморфизмом''»{{переход|#параметрический полиморфизм|text}}.
 
В дальнейшем классификацию уточнил {{iw|Карделли, Лука|Лука Карделли|en|Luca Cardelli}}{{sfn|Cardelli|1985}}, выделив четыре разновидности полиморфизма:
* универсальный
** параметрический
** [[параметрический полиморфизм|параметрический]]{{переход|#параметрический полиморфизм|text}}
** включения (или {{iw|Выделение подтипов данных|подтипов|en|Subtyping}}){{переход|#Полиморфизм подтипов|text}}
* ad-hoc
* {{nobr|ad hoc}}{{переход|#ad hoc полиморфизм|text}}
** [[перегрузка функций|перегрузка]]
** [[приведение типов]]
 
ДжонВ Митчел{{sfn|Mitchell|2002}}некоторых выделяет три разновидности полиморфизма как независимые:работах параметрический{{переход|#параметрический полиморфизм|text}}, ad -hoc{{переход|#ad- hocи полиморфизм|text}} иподтипов подтипов{{переход|#Полиморфизмвыделяются подтипов|text}}как три самостоятельных класса полиморфизма{{sfn|Mitchell|2002|loc=6.4. Polymorphism and overloading|с=145—151}}.
 
Двойственность содержаниясмысла термина {{nobr|«''ad hoc» (с одной стороны — «спонтанный, непродуманный, сделанный по полиморфизм''случаю»}}, с другой — «специальный, устроенный конкретно для данной цели или данного случая») долгие годы была заслуженной{{sfn|Wadler|1988|с=1—2}}. Стрэчи выбрал этот термин, руководствуясь первым значением — в, работе он подчеркиваетподчёркивав, что при {{nobr|ad -hoc}} -полиморфизме нет единого систематичного способа вывести тип результата из типа аргументов, и хотя возможно построение определённого набора правил для сужения спектра его поиска, но эти правила по своей природе являются спонтанными как по содержанию, так и по контексту применения{{sfn|Strachey|1967}}.
Латинский фразеологизм {{nobr|«[[ad hoc]]»}} (буквально «''к случаю''») имеет двойственное значение:
# спонтанный, непродуманный, сделанный «на коленке»
# специальный, устроенный конкретно для данной цели или данного случая
 
Действительно, [[ad -hoc -полиморфизм]] не является ''истинным'' полиморфизмом{{sfn|Cardelli|1985|loc=1.3. Kinds of Polymorphism|с=6}}. [[Перегрузка функций]] даёт не «'''''значение''', имеющее множество типов''», а «'''''символ''', имеющий множество типов''», но значения, [[Идентификатор|идентифицируемые]] этим символом, имеют ''разные'' (потенциально {{nobr|не совместимые}}несовместимые) типы. Аналогично, [[приведение типов]] не является истинным полиморфизмом: кажется, будто оператор принимает значения множества типов, но значения должны быть ''преобразованы'' к некоторому представлению до того, как он сможет их использовать, так что на самом деле оператор работает лишь над одним типом (то есть имеет один тип). Более того, [[тип возвращаемого значения]] здесь не зависит от [[Параметр (программирование)|типа входного параметра]], как в случае параметрического полиморфизма.
Двойственность содержания термина {{nobr|«''ad hoc полиморфизм''»}} долгие годы была заслуженной{{sfn|Wadler|1988|с=1—2}}. Стрэчи выбрал этот термин, руководствуясь первым значением — в работе он подчеркивает, что при {{nobr|ad hoc}} полиморфизме нет единого систематичного способа вывести тип результата из типа аргументов, и хотя возможно построение определённого набора правил для сужения спектра его поиска, но эти правила по своей природе являются спонтанными как по содержанию, так и по контексту применения{{sfn|Strachey|1967}}.
 
Тем не менее, определение специальных реализаций функций для разных типов в некоторых случаях является ''необходимостью'', а не случайностью. Классическими примерами служат реализация арифметических операций (физически различная для [[Целый тип|целых]] и [[Число с плавающей запятой|чисел с плавающей запятой]]) и {{iw|Интуиционистская теория типов#Равенство типов|равенства типов|en|Intuitionistic type theory#Equality type}}, которые на протяжении десятилетий не имели общепринятой универсальной формализации. Решением стали классы типов{{переход|#Классы типов|text}}, представляющие собой механизм явного дискретного перечисления допустимых значений [[Переменная типа|переменных типа]] для статической диспетчеризации в слое типов. Они сводят воедино две разновидности полиморфизма, разделённые СтречиСтрэчи, «''делая {{nobr|ad -hoc -полиморфизм}} менее {{nobr|ad hoc}}''»{{sfn|Wadler|1988|с=1—2}} ([[игра слов|игра]] на двойственности смысла). Дальнейшее обобщение классов типов привело к построению теории [[Параметрический полиморфизм#Квалифицированный тип|квалифицированных типов]], единообразно формализующей самые экзотичные системы типов, включая расширяемые записи{{переход|#Полиморфизм структурных типов|text}} и подтипы.
Действительно, [[ad hoc полиморфизм]] не является ''истинным'' полиморфизмом{{sfn|Cardelli|1985|loc=1.3. Kinds of Polymorphism|с=6}}. [[Перегрузка функций]] даёт не «'''''значение''', имеющее множество типов''», а «'''''символ''', имеющий множество типов''», но значения, [[Идентификатор|идентифицируемые]] этим символом, имеют ''разные'' (потенциально {{nobr|не совместимые}}) типы. Аналогично, [[приведение типов]] не является истинным полиморфизмом: кажется, будто оператор принимает значения множества типов, но значения должны быть ''преобразованы'' к некоторому представлению до того, как он сможет их использовать, так что на самом деле оператор работает лишь над одним типом (то есть имеет один тип). Более того, [[тип возвращаемого значения]] здесь не зависит от [[Параметр (программирование)|типа входного параметра]], как в случае параметрического полиморфизма.
 
В отличие от [[перегрузка функций|перегрузки]] и [[приведение типов|приведения типов]], полиморфизм {{iw|Выделение подтипов данных|подтипов|en|Subtyping}}{{переход|#Полиморфизм подтипов|text}} является ''истинным'' полиморфизмом: объектами подтипа можно манипулировать единообразно, как если бы они принадлежали к своим супертипам (но сказанное не верно для языков, реализующих «''полиморфизм при наследовании''» посредством [[приведение типов|приведения типов]] и [[перегрузка функций|перегрузки функций]], как в случае [[С++]]). Наиболее ''чистым'' является [[параметрический полиморфизм]]{{переход|#параметрический полиморфизм|text}}: один и тот же объект или функция может единообразно использоваться в разных контекстах типизации без изменений, приведений типов или любых других проверок времени исполнения или преобразований. Однако, для этого требуется некое единообразное представление данных (например, посредством [[указатель (программирование)|указателей]]).{{sfn|Cardelli|1985|с=6}}.
Тем не менее, определение специальных реализаций функций для разных типов в некоторых случаях является ''необходимостью'', а не случайностью. Классическими примерами служат реализация арифметических операций (физически различная для [[Целый тип|целых]] и [[Число с плавающей запятой|чисел с плавающей запятой]]) и {{iw|Интуиционистская теория типов#Равенство типов|равенства типов|en|Intuitionistic type theory#Equality type}}, которые на протяжении десятилетий не имели общепринятой универсальной формализации. Решением стали классы типов{{переход|#Классы типов|text}}, представляющие собой механизм явного дискретного перечисления допустимых значений [[Переменная типа|переменных типа]] для статической диспетчеризации в слое типов. Они сводят воедино две разновидности полиморфизма, разделённые Стречи, «''делая {{nobr|ad hoc полиморфизм}} менее {{nobr|ad hoc}}''»{{sfn|Wadler|1988|с=1—2}} ([[игра слов|игра]] на двойственности смысла). Дальнейшее обобщение классов типов привело к построению теории [[Параметрический полиморфизм#Квалифицированный тип|квалифицированных типов]], единообразно формализующей самые экзотичные системы типов, включая расширяемые записи{{переход|#Полиморфизм структурных типов|text}} и подтипы.
 
В отличие от [[перегрузка функций|перегрузки]] и [[приведение типов|приведения типов]], полиморфизм {{iw|Выделение подтипов данных|подтипов|en|Subtyping}}{{переход|#Полиморфизм подтипов|text}} является ''истинным'' полиморфизмом: объектами подтипа можно манипулировать единообразно, как если бы они принадлежали к своим супертипам (но сказанное не верно для языков, реализующих «''полиморфизм при наследовании''» посредством [[приведение типов|приведения типов]] и [[перегрузка функций|перегрузки функций]], как в случае [[С++]]). Наиболее ''чистым'' является [[параметрический полиморфизм]]{{переход|#параметрический полиморфизм|text}}: один и тот же объект или функция может единообразно использоваться в разных контекстах типизации без изменений, приведений типов или любых других проверок времени исполнения или преобразований. Однако, для этого требуется некое единообразное представление данных (например, посредством [[указатель (программирование)|указателей]]).{{sfn|Cardelli|1985|с=6}}
 
== Основные разновидности полиморфизма ==
 
=== {{якорь|Специальный полиморфизм}} Ad -hoc -полиморфизм ===
{{falseredirect|Ad -hoc -полиморфизм|:en:Ad hoc polymorphism|англ.}}
[[{{якорь|Специальный полиморфизм}}Ad -hoc]] -полиморфизм (в русской литературе чаще всего переводится как «{{lang-ru2|специальный полиморфизм}}» или «{{lang-ru2|специализированный полиморфизм}}», хотя оба варианта не всегда верны{{переход|#Классификация|text}}) поддерживается во многих языках посредством [[перегрузка функций|перегрузки функций и методов]], а в [[Сильная и слабая типизация|слабо типизированных]] — также посредством [[Приведение типов|приведения типов]].
 
[[Ad hoc]] полиморфизм (в русской литературе чаще всего переводится как «{{lang-ru2|специальный полиморфизм}}» или «{{lang-ru2|специализированный полиморфизм}}», хотя оба варианта не всегда верны{{переход|#Классификация|text}}) поддерживается во многих языках посредством [[перегрузка функций|перегрузки функций и методов]], а в [[Сильная и слабая типизация|слабо типизированных]] — также посредством [[Приведение типов|приведения типов]].
 
В следующем примере (язык [[PascalПаскаль (язык программирования)|Паскаль]]) функции <code>Add</code> выглядят как реализующие одну и ту же функциональность над разными типами, но компилятор определяет их как две совершенно разные функции.
<source lang=pascal>
program Adhoc;
В [[динамическая типизация|динамически типизируемых языках]] ситуация может быть более сложной, так как выбор требуемой функции для вызова может быть осуществлён только во время исполнения программы.
 
[[перегрузка функций|Перегрузка]] — представляет собой ''[[синтаксис (программирование)|синтаксический]]'' механизм, позволяющий по единому идентификатору вызывать разные функции{{sfn|Cardelli|1985|с=5—6}}. [[Приведение типов]] — [[семантика (программирование)|семантический]] механизм, осуществляемый для преобразования фактического типа аргумента к ожидаемому функцией, при отсутствии которого произошла бы [[ошибка типизации]]. То есть, при вызове функции с приведением типа происходит исполнение различного кода для различных типов (предваряющего вызов самой функции){{sfn|Cardelli|1985|с=5—6}}.
 
[[Приведение типов]] представляет собой ''[[семантика (программирование)|семантический]]'' механизм, осуществляемый для преобразования фактического типа аргумента к ожидаемому функцией, при отсутствии которого произошла бы [[ошибка типизации]]. То есть, при вызове функции с приведением типа происходит исполнение различного кода для различных типов (предваряющего вызов самой функции){{sfn|Cardelli|1985|с=5—6}}.
 
=== Параметрический полиморфизм ===
{{main|Параметрический полиморфизм}}
 
Параметрический полиморфизм позволяет определять функцию или тип данных обобщённо, так что значения обрабатываются идентично вне зависимости от их типа. Параметрически полиморфная функция использует аргументы на основе поведения, а не значения, апеллируя лишь к необходимым ей свойствам аргументов, что делает её применимой в любом контексте, где тип объекта удовлетворяет заданным требованиям поведения.
 
Развитые [[система типов|системы типов]] (такие как [[Система типов Хиндли — Милнера|система Хиндли — МилнерМилнера]]) предоставляют механизмы для определения [[полиморфизм типов|полиморфных типов]], что делает использование полиморфных функций более удобным и обеспечивает статическую [[типобезопасность]]. Такие системы являются системами типов второго порядка, добавляющими к системам типов первого порядка (используемым в большинстве [[процедурное программирование|процедурных языков]]) параметризацию типов (посредством [[переменная типа|ти́повой переменной]]) и [[абстрактный тип данных|абстракцию типов]] (посредством [[переменная типа#Связывание и квантификация переменных типа|экзистенциальной квантификации]] над ними). В системах типов второго порядка нет непосредственной необходимости в поддержке [[примитивный тип|примитивных типов]], так как они могут быть выражены посредством более развитых средств.{{sfn|Cardelli|1996|loc=5 Second-order Type Systems|с=25}}
 
Классическим примером полиморфного типа служит ''[[список (программирование)|список]] элементов произвольного типа'', для которого во многих языках, типизируемых по [[Система типов Хиндли — Милнера|Хиндли — Милнеру]] (большинство [[Статическая типизация|статически типизируемых]] [[функциональное программирование|функциональных языков программирования]]), предоставляется [[синтаксический сахар]]. Следующий пример демонстрирует определение нового [[Алгебраический тип данных|алгебраического типа]] «параметрически полиморфный [[список (программирование)|список]]» и двух функций над ним:
<source lang=haskell>
data List a = Nil | Cons a (List a)
map f (Cons x xs) = Cons (f x) (map f xs)
</source>
При подстановке в [[переменная типа|ти́повую переменную]] <code>a</code> конкретных типов <code>Int</code>, <code>String</code> и т. д. так далее будут построены, соответственно, конкретные типы <code>List Int</code>, <code>List String</code> и т. д так далее. Эти конкретные типы, в свою очередь, снова могут быть подставлены в эту [[переменная типа|ти́повую переменную]], порождая типы <code>List List String</code>, <code>List (Int, List String)</code> и т. д так далее. При этом для всех объектов всех построенных типов будет использоваться ''одна и та же'' физическая реализация функций <code>length</code> и <code>map</code>.
 
Ограниченные формы параметрического полиморфизма доступны также в некоторых [[императивный язык программирования|императивных]] (в частности, [[объектно-ориентированный язык программирования|объектно-ориентированных]]) языках программирования, где для его обозначения обычно используется термин «[[обобщённое программирование]]». В частности, в языке [[Си (язык программирования)|Си]] нетипизированный параметрический полиморфизм традиционно обеспечивается за счёт использования нетипизированного [[указатель (программирование)|указателя]] <code>void*</code>, хотя возможна и типизированная форма. Использование [[Шаблоны C++|шаблонов C++]] внешне похоже на параметрический полиморфизм, но семантически реализуется сочетанием [[ad -hoc полиморфизм|ad hoc]]-механизмов; в сообществе [[С++]] его называют «''статическим полиморфизмом''» (для противопоставления «''динамическому полиморфизму''»{{переход|#Подтипизация на записях|text}}).
 
{{details|параметрический полиморфизм в Си и С++}}
 
==== Параметричность ====
Формализация параметрического полиморфизма ведёт к понятию {{iw|Параметричность|параметричности|en|parametricity}}, состоящему в возможности предсказывать поведение программ, глядя только на их типы. Например, если функция имеет тип «<code>forall a. a -> a</code>», то без каких-либо дополняющих язык внешних средств можно [[доказательство (математика)|доказать]], что она может быть ''только'' [[Тождественное отображение|тождественной]]. Поэтому параметричность часто сопровождается лозунгом «''теоремы забесплатно''» ({{lang-en|theorems for free}}). {{sfn|Harper|2012|loc=20.3 Parametricity overview|с=177}} {{sfn|Harper|2012|loc=49 Parametricity|с=495—508}}{{sfn|Пирс|2012|loc=23.9 Параметричность|с=384—385}}
{{main|:en:Parametricity|l1=Параметричность{{ref-en}}}}
 
Важным следствием этого является также ''независимость представлений'' ({{lang-en|representation independence}}), означающее, что функции над [[абстрактный тип данных|абстрактным типом]] нечувствительны к его структуре, и различные реализации этого типа могут свободно подменять друг друга (даже в рамках одной программы), не влияя на поведение этих функций {{sfn|Harper|2012|loc=21.4 Representation Independence|с=188}}.
Формализация параметрического полиморфизма ведёт к понятию {{iw|Параметричность|параметричности|en|parametricity}}, состоящему в возможности предсказывать поведение программ, глядя только на их типы. Например, если функция имеет тип «<code>forall a. a -> a</code>», то без каких-либо дополняющих язык внешних средств можно [[доказательство (математика)|доказать]], что она может быть ''только'' [[Тождественное отображение|тождественной]]. Поэтому параметричность часто сопровождается лозунгом «''теоремы забесплатно''» ({{lang-en|theorems for free}}). {{sfn|Harper|2012|loc=20.3 Parametricity overview|с=177}} {{sfn|Harper|2012|loc=49 Parametricity|с=495—508}}{{sfn|Пирс|2012|loc=23.9 Параметричность|с=384—385}}
 
Наиболее развитые параметрически полиморфные системы (см.занимающие высшую точку [[лямбда-куб]], [[зависимый тип|зависимыев типылямбда-кубе]]) доводят идею {{iw|Параметричность|параметричности|en|parametricity}} до возможности [[формальная верификация|полного доказательства корректности]] программ: они позволяют записывать программы, которые ''верны по построению'', так что прохождение [[проверка согласования типов|проверки согласования типов]] само по себе даёт ''гарантию'', что поведение программы соответствует ожидаемому{{sfn|Пирс|2012|loc=30.5 Идем дальше: зависимые типы|с=489—493}}.
Важным следствием этого является также ''независимость представлений'' ({{lang-en|representation independence}}), означающее, что функции над [[абстрактный тип данных|абстрактным типом]] нечувствительны к его структуре, и различные реализации этого типа могут свободно подменять друг друга (даже в рамках одной программы), не влияя на поведение этих функций {{sfn|Harper|2012|loc=21.4 Representation Independence|с=188}}.
 
Наиболее развитые параметрически полиморфные системы (см. [[лямбда-куб]], [[зависимый тип|зависимые типы]]) доводят идею {{iw|Параметричность|параметричности|en|parametricity}} до возможности [[формальная верификация|полного доказательства корректности]] программ: они позволяют записывать программы, которые ''верны по построению'', так что прохождение [[проверка согласования типов|проверки согласования типов]] само по себе даёт ''гарантию'', что поведение программы соответствует ожидаемому{{sfn|Пирс|2012|loc=30.5 Идем дальше: зависимые типы|с=489—493}}.
 
{{details|зависимый тип}}
 
==== {{якорь|Полиморфизм структурных типов}} Полиморфизм записей и вариантов ====
{{якорь|Полиморфизм структурных типов}}Отдельную проблему представляет распространение параметрического полиморфизма на агрегатные типы: размеченные [[тип-произведение|произведения типов]] (традиционно называемые [[запись (тип данных)|записями]]) и размеченные [[тип-сумма|суммы типов]] (также известные как {{iw|Вариантный тип данных|вариантные типы|en|Variant type}}). Различные «исчисления [[запись (тип данных)|записей]]» ({{lang-en|record calculi}}) служат формальной базой для [[Объектно-ориентированное программирование|объектно-ориентированного]] и [[модульное программирование|модульного]] программирования{{sfn|Reynolds|1998|loc=16. Subtypes and Intersection Types. Bibliographic Notes|с=376}}.
 
<source lang="sml">
val r2 = {d = 3.14, ... = r1}
</source>
Многоточие означает некоторый '''''ряд''''' типизированных полей, то есть [[Абстракция (информатика)|абстракцию]] кода от конкретных типов записей, которые могли бы здесь обрабатываться (причём «длина» этого ряда также может варьироваться). Компиляция полиморфного обращения к полям, которые могут располагаться в разном порядке в разных записях, представляет сложную проблему, как с точки зрения [[типобезопасность|контроля безопасности операций]] на уровне языка, так и с точки зрения быстродействия на уровне машинного кода. Наивным решением может быть динамический поиск по словарю при каждом обращении (и скриптовые языки его применяют), однако, очевидно, что это чрезвычайно неэффективно. Эта проблема активно исследуется на протяжении уже нескольких десятилетий; построено множество теоретических моделей и практичных систем на их основе, различающихся по выразительной мощности и метатеоретической сложности. Важнейшими достижениями в этой области считаются '''[[рядный полиморфизм''']], предложенный {{нп2|Уанд, Митчел|Митчелом Вандом ([[:Уандом|en:Mitchell Wand|Mitchell Wand{{ref-en}}]]), и '''[[полиморфное исчисление записей''']], построенное Ацуси Охори ({{lang-en|Atsushi Ohori}}). Более распространённой, но отстающей по многим характеристикам моделью является подтипизация на записях{{переход|#Подтипизация на записях|text}}.
 
Поддержка полиморфизма записей в той или иной форме может открывать в полиморфном языке такие возможности, как {{iw|Сообщение высшего порядка|сообщения высшего порядка|en|Higher order message}} (наиболее мощную форму [[Объектно-ориентированное программирование|объектно-ориентированного программирования]]), бесшовное [[встраиваемый язык|встраивание]] операций над элементами [[базы данных|баз данных]] ([[SQL]]) в код на языке общего назначения, и др., вплоть до ''расширяемого программирования'' (то есть программирования, свободного от {{iw|Проблема выражения|проблемы выражения|en|Expression problem}}), гарантии отсутствия [[обработка исключений|необработанных исключений]] в программах и определённых форм [[метапрограммирование|метапрограммирования]].
 
=== Полиморфизм подтипов ===
'''''Полиморфизм включения''''' ({{lang-en2|inclusion polymorphism}}) является обобщённой формализацией {{iw|выделение подтипов данных|подтипизации|en|Subtyping}} и [[наследование (программирование)|наследования]]{{sfn|Cardelli |1985}}. Эти понятия не следует путать: {{iw|выделение подтипов данных|подтипы|en|Subtyping}} определяют отношения на уровне интерфейсов, тогда как наследование определяет отношения на уровне реализации{{sfn|Mitchell|2002|loc=10.2.6 Inheritance Is Not Subtyping|с=287}}.
{{main|:en:Subtyping|l1=Выделение подтипов данных{{ref-en}}}}
 
'''Полиморфизм включения''' ({{lang-en2|inclusion polymorphism}}) является обобщённой формализацией {{iw|выделение подтипов данных|подтипизации|en|Subtyping}} и [[наследование (программирование)|наследования]]{{sfn|Cardelli |1985}}. Эти понятия не следует путать: {{iw|выделение подтипов данных|подтипы|en|Subtyping}} определяют отношения на уровне интерфейсов, тогда как наследование определяет отношения на уровне реализации{{sfn|Mitchell|2002|loc=10.2.6 Inheritance Is Not Subtyping|с=287}}.
 
Подтипизация ({{lang-en2|subtyping}}), или полиморфизм подтипов ({{lang-en2|subtype polymorphism}}), означает, что поведение [[параметрический полиморфизм|параметрически полиморфной]]{{переход|#параметрический полиморфизм|text}} функции ограничивается множеством типов, ограниченных в иерархию «супертип — подтип»{{sfn| Cardelli|1991|}}{{sfn|Cardelli|1985}}{{sfn|Пирс|2012|loc=15 Подтипы|с=193}}. Например, если имеются типы <code>Number</code>, <code>Rational</code> и <code>Integer</code>, ограниченные отношениями <code>Number :> Rational</code> и <code>Number :> Integer</code>, то функция, определённая на типе <code>Number</code>, также сможет принять на вход аргументы типов <code>Integer</code> или <code>Rational</code>, и её поведение будет идентичным. Действительный тип объекта может быть скрыт как «чёрный ящик», и предоставляться лишь по запросу идентификации объекта. На самом деле, если тип <code>Number</code> является абстрактным, то конкретного объекта этого типа даже не может существовать (см. [[абстрактный класс]], но не следует путать с [[абстрактный тип данных|абстрактным типом данных]]). Данная иерархия типов известна (особенно в контексте языка [[Scheme (язык программирования)|Scheme]]) как {{iw|числовая башня||en|Numerical tower}}, и обычно содержит большее количество типов.
 
Идея подтипов мотивируется увеличением множества типов, которые могут обрабатываться уже написанными функциями, и за счёт этого повышением коэффициента [[повторное использование кода|повторного использования кода]] в условиях [[сильная и слабая типизация|сильной типизации]] (то есть увеличением множества [[типобезопасность|типизируемых]] программ). Это обеспечивается '''правилом включения''' ({{lang-en2|subsumption rule}}): «''если выражение <code>e</code> принадлежит к типу <code>t'</code> в контексте типизации <code>Г</code>, и выполняется <code>t'<:t</code>, то <code>e</code> принадлежит также и к типу <code>t</code>''»{{sfn|Пирс|2012|loc=15. Подтипы|с=193}} {{sfn|Harper|2012|loc=23.1. Subsumption|с=208}}.
Отношения подтипизации возможны на самых разных категориях типов: [[примитивный тип|примитивных типах]] (как <code>Integer <: Number</code>), [[тип-сумма|типах-суммах]], [[тип-произведение|типах-произведениях]], [[функциональный тип|функциональных типах]] и др. Более того, {{iw|Карделли, Лука|Лука Карделли|en|Luca Cardelli}} предложил концепцию степенны́х [[Род (теория типов)|родо́в]] ({{lang-en2|«power» kinds}}) для описания подтипизации{{sfn|Пирс|2012|loc=1.4 Краткая история|с=11—13}}: ''степенью'' данного типа в слое [[Род (теория типов)|родо́в]] ({{lang-en2|power-kind of the type}}) он назвал [[Род (теория типов)|род]] всех его подтипов{{sfn| Cardelli|1991|loc=6. Power kinds|с=32}}.
 
Особое место в информатике занимает подтипизация на [[запись (тип данных)|записях]]{{переход|#Подтипизация на записях|text}}.
 
==== Подтипизация на записях ====
В подтипизации на [[запись (тип данных)|записях]] выделяются две разновидности: в ширину и в глубину.
 
'''Подтипизация в ширину''' ({{lang-en2|width subtyping}}) подразумевает добавление в [[запись (тип данных)|запись]] новых полей. Например:
<source>
type Object = { age: Int }
С одной стороны, можно записать отношения подтипизации <code>Vehicle <: Object</code>, <code>Bike <: Vehicle</code> (а поскольку подтипизация [[транзитивность|транзитивна]], то и <code>Bike <: Object</code>) и <code>Machine <: Object</code>. С другой стороны, можно говорить, что типы <code>Vehicle</code>, <code>Bike</code> и <code>Machine</code> ''включают'' (наследуют) все свойства типа <code>Object</code>. (Здесь подразумевается {{iw|структурная система типов|структурная|en|Structural type system}} семантика [[система типов|системы типов]].)
 
Поскольку интуитивно ''тип'' зачастую рассматривается как ''множество значений'', то увеличение количества полей в ''подтипе'' может выглядеть контр-интуитивноконтринтуитивно с точки зрения [[теория множеств|теории множеств]]. В действительности, типы — это ''не'' множества {{sfn|Harper|2012|loc=Chapter 16. Recursive Types|с=132}}, они предназначены для верификации поведения программ, и идея подтипизации состоит в том, что подтип обладает ''по меньшей мере'' свойствами своего супертипа, и таким образом, способен эмулировать его ''как минимум'' там, где ожидается объект супертипа{{sfn|Пирс|2012|loc=15. Подтипы|с=193}}. Или иначе: супертип определяет ''минимальный'' набор свойств для множества объектов, и тогда тип, обладающий этими свойствами и, возможно, какими-то другими, формирует подмножество этого множества, а следовательно, является его подтипом{{sfn|Cardelli|1985|loc=6. Bounded Quantification|с=28}}.
 
Отношения подтипов в терминах множеств выглядят более интуитивно в случае с [[тип-сумма|вариантными типами]]{{sfn| Cardelli|1991|с=35—37}}:
 
===== Методы в подтипах записей =====
Полноценная поддержка [[объектно-ориентированное программирование|объектно-ориентированного программирования]] предполагает включение в число полей [[запись (тип данных)|записей]] также [[функция (программирование)|функций]], обрабатывающих значения типов записей, которым они принадлежат{{sfn|Abadi, Cardelli|1994}}{{sfn|Cardelli|1985|loc=2.3. Basic Types, Structured Types and Recursion|с=12—14}}. Такие функции традиционно называются «'''[[метод (программирование)|методами]]'''». Обобщённой моделью связывания записей с методами является матрица диспетчеризации ({{lang-en2|dispatch matrix}}); на практике большинство языков раскладывают её на вектора по строкам либо по столбцам — соответственно, реализуя либо организацию на основе классов ({{lang-en2|class-based organisation}}), либо организацию на основе методов ({{lang-en2|method-based organisation}}) {{sfn|Harper|2012|loc=Chapter 25. Dynamic Dispatch|с=229}}. При этом следует отличать ''переопределение методов в подтипах'' ({{lang-en2|method overriding}}) от ''подтипизации функций'' ({{lang-en2|functional subtyping}}). Переопределение методов не связывает их отношениями подтипизации на функциях, но позволяет изменять сигнатуры их типов. При этом возможны три варианта: инвариантное, [[Ковариантность и контравариантность (программирование)|ковариантное и контравариантное]] переопределение, и два последних используют подтипизацию своих параметров{{sfn|Joyner|1996|loc=3.38 Signature Variance|с=35}} (подробнее см. [[Ковариантность и контравариантность (программирование)|ковариантность и контравариантность]]). Исчисление Абади — Карделли{{sfn|Abadi, Cardelli|1994}} рассматривает только [[Ковариантность и контравариантность (программирование)|инвариантные]] методы, что необходимо для доказательства [[типобезопасность|безопасности]].
 
Многие [[объектно-ориентированное программирование|объектно-ориентированные языки]] предусматривают встроенный механизм связывания [[функция (программирование)|функций]] в [[метод (программирование)|методы]], реализуя таким образом организацию программ на основе классов. Языки, рассматривающие функции как [[объект первого класса|объекты первого класса]] и [[система типов|типизирующие]] их (см. [[функции первого класса]], [[функциональный тип]] — не путать с [[тип возвращаемого значения|типом возвращаемого значения функции]]), позволяют произвольно выстраивать организацию на основе методов, что обеспечивает возможность производить [[объектно-ориентированное проектирование]] без прямой поддержки со стороны языка<ref name="MLton_OOP">[http://www.mlton.org/ObjectOrientedProgramming Object-Oriented Programming in Standard ML]</ref>. Некоторые языки (например, [[OCaml]]) поддерживают обе возможности.
}}</ref>.
 
Некоторые языки используют своеобразные [[ad -hoc]]-решения. Например, [[система типов]] языка [[С++]] предусматривает автоматическое [[приведение типов]] (то есть является [[сильная и слабая типизация|слабой]]), {{nobr|не [[полиморфизм типов|полиморфная]]}}, эмулирует {{iw|Выделение подтипов данных|выделение подтипов|en|Subtyping}} через {{iw|Манифестная типизация|манифестное|en|Manifest typing}} наследование с [[Ковариантность и контравариантность (программирование)|инвариантными]] сигнатурами методов и не поддерживает абстракцию типов (не путать с [[Сокрытие (программирование)|сокрытием]] полей). [[наследование (программирование)|Наследование]] в [[С++]] реализуется набором {{nobr|ad hoc-механизмов}}, однако, его использование называется в сообществе языка «полиморфизмом» (а [[Сокрытие (программирование)|сокрытие]] полей — «абстракцией»{{sfn|Joyner|1996|loc=2.8 Encapsulation|с=8}}). Имеется возможность управлять графом наследования: [[ромбовидное наследование]] в С++ называется «''виртуальным наследованием''» и задаётся явным атрибутом <code>virtual</code>; по умолчанию же осуществляется дублирование унаследованных полей с доступом к ним по квалифицированному имени. Использование такого языка может быть [[типобезопасность|небезопасно]] — нельзя гарантировать устойчивость программ{{sfn|Mitchell|2002|loc=6.2.1 Type Safety|с=132—133}}{{sfn|Joyner|1996|loc=3.38 Signature Variance|с=35}} (язык называется [[типобезопасность|безопасным]], если программы на нём, которые могут быть приняты компилятором как правильно построенные, в динамике никогда не выйдут за рамки допустимого поведения {{sfn|Harper|2012|loc=Chapter 4. Statics|с=35}}).
 
==== Подтипизация высшего порядка ====
«''Система <math>F^\omega_{<:}</math>''» (читается «''F-саб-омега''») является расширением [[Система F|Системы F]] (не представленным в [[лямбда-куб]]е), формализующим {{iw|ограниченная квантификация|ограниченную квантификацию|en|Bounded quantification}} над [[конструктор типов|ти́повыми операторами]], распространяя отношения подтипизации с [[Род (теория типов)|рода]] <code>*</code> на типы высших [[Род (теория типов)|родо́в]]. Существует несколько вариантов системы <math>F^\omega_{<:}</math>, различающихся по выразительной мощности и метатеоретической сложности, но большинство основных идей заложил {{iw|Карделли, Лука|Лука Карделли|en|Luca Cardelli}}{{sfn|Пирс|2012|loc=31. Подтипы высших порядков|с=495}}.
 
== Сочетание разновидностей полиморфизма ==
 
=== Классы типов ===
{{falseredirect|Класс типов|:en:Type class|англ.}}<!--
[['''''Класс типов]]''''' реализует единую независимую таблицу виртуальных методов для множества ([[Параметрический полиморфизм|универсально]] [[переменная типа#Связывание и квантификация переменных типа|квантифицированных]]) типов. Этим классы типов отличаются от [[класс (объектно-ориентированное программирование)|классов]] в [[Объектно-ориентированное программирование|объектно-ориентированном программировании]], где всякий объект всякого ({{iw|ограниченная квантификация|ограниченно|en|Bounded quantification}} [[переменная типа#Связывание и квантификация переменных типа|квантифицированного]]) типа сопровождается указателем на таблицу виртуальных методов{{sfn|Wadler|1988|с=3}}. Классы типов являются не типами, но категориями типов; их экземпляры представляют собой не значения, а типы.
{{main|:en:Type class|l1=Классы типов{{ref-en}}}}-->
 
[[Класс типов]] реализует единую независимую таблицу виртуальных методов для множества ([[Параметрический полиморфизм|универсально]] [[переменная типа#Связывание и квантификация переменных типа|квантифицированных]]) типов. Этим классы типов отличаются от [[класс (объектно-ориентированное программирование)|классов]] в [[Объектно-ориентированное программирование|объектно-ориентированном программировании]], где всякий объект всякого ({{iw|ограниченная квантификация|ограниченно|en|Bounded quantification}} [[переменная типа#Связывание и квантификация переменных типа|квантифицированного]]) типа сопровождается указателем на таблицу виртуальных методов{{sfn|Wadler|1988|с=3}}. Классы типов являются не типами, но категориями типов; их экземпляры представляют собой не значения, а типы.
 
Например{{sfn|Wadler|1988|с=3}}:
 
=== Политипизм ===
{{main|:en:Generic programming#Functional languages|l1=Обобщённое программирование#Функциональные языки{{ref-en}}}}
 
Иногда используется термин «политипизм» или «обобщённость типа данных». По сути политипизм означает встроенную в язык поддержку полиморфизма [[конструктор типов|конструкторов типов]], предназначенную для унификации программных интерфейсов и повышения [[повторное использование кода|повторного использования кода]]. Примером политипизма является обобщённый алгоритм [[сопоставление с образцом|сопоставления с образцом]]<ref>{{статья
|автор = Johan Jeuring
}}</ref>.
 
По определению, в политиповой функции «''хотя и возможно наличие конечного числа {{nobr|ad -hoc}}-ветвей для некоторых типов, но {{nobr|ad -hoc}}-комбинатор отсутствует''»<ref>Ralf Lammel and Joost Visser, «Typed Combinators for Generic Traversal», in ''Practical Aspects of Declarative Languages: 4th International Symposium'' (2002), p. 153.</ref>.
 
Политипизм может быть реализован посредством использования [[Высший тип|универсального типа данных]] или [[Параметрический полиморфизм#Полиморфизм высших рангов|полиморфизма высших рангов]]. [[Встраиваемый язык|Расширение]] PolyP<ref>{{статья
 
== История ==
Термин «полиморфизм» происходит от ''др.{{lang-греч.'' el|πολύς}} («много») и {{lang-el2|μορφή}} («форма, облик, устройство»).
 
Термины «специализированный полиморфизм» и «параметрический полиморфизм» впервые упоминаются в [[1967 год]]у в конспекте лекций {{iw|Стрэчи, Кристофер|Кристофера Стрэчи|en|Christopher Strachey}} под названием «{{iw|Фундаментальные основы языков программирования||en|Fundamental Concepts in Programming Languages}}»{{sfn|Strachey|1967}}. В [[1985 год]]у {{iw|Вегнер, Питер|Питер Вегнер|en|Peter Wegner}} и {{iw|Карделли, Лука|Лука Карделли|en|Luca Cardelli}} формализовали полиморфизм включения для моделирования {{iw|Выделение подтипов данных|подтипов|en|Subtyping}} и [[наследование (программирование)|наследования]]{{sfn|Cardelli|1985}}{{sfn|Пирс|2012|loc=1.4 Краткая история|с=11—13}}, хотя реализации подтипов и наследования появились намного раньше, в языке [[Симула]] в [[1967 год]]у. Полиморфизм включения основан на {{iw|ограниченная квантификация|ограниченной квантификации|en|Bounded quantification}}.
 
== См. также ==
* [[Типобезопасность]]
* [[Система типов]]
* [[Каламбур типизации]]
* [[Ковариантность и контравариантность (программирование)|Ковариантность и контравариантность]]
* [[Инкапсуляция (программирование)|Инкапсуляция]]
* [[Наследование (программирование)|Наследование]]
 
== Примечания ==
{{примечания|32em}}
 
== Литература ==