Полиморфизм (информатика)
| Полиморфизм |
|---|
| Специальный полиморфизм |
| Параметрический полиморфизм |
| Подтипирование |
В теории языков программирования и теории типов полиморфизм — это использование одного символа для представления нескольких разных типов. [1]
В объектно-ориентированном программировании полиморфизм — это предоставление единого интерфейса сущностям разных типов . [2] Эта концепция заимствована из принципа биологии , согласно которому организм или вид могут иметь множество различных форм или стадий. [3]
Наиболее распространенными основными формами полиморфизма являются:
- Специальный полиморфизм : определяет общий интерфейс для произвольного набора индивидуально указанных типов.
- Параметрический полиморфизм : не указываются конкретные типы и вместо этого используются абстрактные символы, которые могут заменить любой тип.
- Подтипирование (также называемое полиморфизмом подтипа или полиморфизмом включения ): когда имя обозначает экземпляры множества разных классов, связанных некоторым общим суперклассом. [4]
История
[ редактировать ]полиморфных Интерес к системам типов значительно возрос в 1990-х годах, а к концу десятилетия начали появляться практические реализации. Специальный полиморфизм и параметрический полиморфизм были первоначально описаны в книге Кристофера Стрейчи « Фундаментальные концепции языков программирования» . [5] где они указаны как «два основных класса» полиморфизма. Специальный полиморфизм был особенностью Algol 68 , тогда как параметрический полиморфизм был основной особенностью ML системы типов .
В статье 1985 года Питер Вегнер и Лука Карделли ввели термин полиморфизм включения для моделирования подтипов и наследования . [1] назвав Simula первым языком программирования, реализующим эту технологию.
Формы
[ редактировать ]Специальный полиморфизм
[ редактировать ]Кристофер Стрейчи выбрал термин «специальный полиморфизм» для обозначения полиморфных функций, которые можно применять к аргументам разных типов, но которые ведут себя по-разному в зависимости от типа аргумента, к которому они применяются (также известное как перегрузка функции или перегрузка оператора ). [5] Термин « ad hoc » в этом контексте не является уничижительным; это просто относится к тому факту, что эта форма полиморфизма не является фундаментальной особенностью системы типов. В Java приведенном ниже примере Add функции, похоже, работают в целом над двумя типами (целыми и строковыми), если смотреть на вызовы, но компилятор считает их двумя совершенно разными функциями для всех намерений и целей:
class AdHocPolymorphic {
public String add(int x, int y) {
return "Sum: "+(x+y);
}
public String add(String name) {
return "Added "+name;
}
}
public class adhoc {
public static void main(String[] args) {
AdHocPolymorphic poly = new AdHocPolymorphic();
System.out.println( poly.add(1,2) ); // prints "Sum: 3"
System.out.println( poly.add("Jay") ); // prints "Added Jay"
}
}
В динамически типизированных языках ситуация может быть более сложной, поскольку правильную функцию, которую необходимо вызвать, можно определить только во время выполнения.
Неявное преобразование типов также определяется как форма полиморфизма, называемая «полиморфизмом приведения». [1] [6]
Параметрический полиморфизм
[ редактировать ]Параметрический полиморфизм позволяет писать функцию или тип данных в общем виде, чтобы она могла обрабатывать значения единообразно , независимо от их типа. [7] Параметрический полиморфизм — это способ сделать язык более выразительным, сохраняя при этом полную статическую типобезопасность .
Концепция параметрического полиморфизма применима как к типам данных , так и к функциям . Функция, которая может вычислять значения разных типов или применяться к ним, называется полиморфной функцией. Тип данных, который может выглядеть как обобщенный тип (например, список с элементами произвольного типа), называется полиморфным типом данных , как и обобщенный тип, на основе которого создаются такие специализации.
Параметрический полиморфизм широко распространен в функциональном программировании, где его часто называют просто «полиморфизмом». В следующем примере на Haskell показан тип данных параметризованного списка и две параметрически полиморфные функции для них:
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)
Параметрический полиморфизм также доступен в нескольких объектно-ориентированных языках. Например, шаблоны под названием в C++ и D или дженерики в C#, Delphi, Java и Go:
class List<T> {
class Node<T> {
T elem;
Node<T> next;
}
Node<T> head;
int length() { ... }
}
List<B> map(Func<A, B> f, List<A> xs) {
...
}
Джон К. Рейнольдс (а позже Жан-Ив Жирар ) формально разработал это понятие полиморфизма как расширение лямбда-исчисления (называемого полиморфным лямбда-исчислением или системой F ). Любая параметрически полиморфная функция обязательно ограничена в своих возможностях, работая с формой данных, а не с их значением, что приводит к понятию параметричности .
Подтипирование
[ редактировать ]Некоторые языки используют идею подтипирования (также называемую полиморфизмом подтипов или полиморфизмом включения ) для ограничения диапазона типов, которые могут использоваться в конкретном случае полиморфизма. В этих языках подтипирование позволяет написать функцию, принимающую объект определенного типа T , но также работать корректно, если ей передан объект, принадлежащий типу S , являющемуся подтипом T (согласно принципу подстановки Лискова ). . Это отношение типа иногда пишется S <: T . наоборот, T называется супертипом S — пишется T : > S. И Полиморфизм подтипов обычно разрешается динамически (см. ниже).
В следующем примере Java мы создаем подтипы домашних животных для кошек и собак. Процедура letsHear() принимает питомца, но также будет работать корректно, если ему будет передан подтип:
abstract class Pet {
abstract String speak();
}
class Cat extends Pet {
String speak() {
return "Meow!";
}
}
class Dog extends Pet {
String speak() {
return "Woof!";
}
}
static void letsHear(final Pet pet) {
println(pet.speak());
}
static void main(String[] args) {
letsHear(new Cat());
letsHear(new Dog());
}
В другом примере, если Number , Rational и Integer являются такими типами, что Number :> Rational и Number :> Integer ( Rational и Integer как подтипы типа Number , который является их супертипом), функция, написанная для приема Number , будет работают одинаково хорошо как при передаче Integer или Rational, так и при передаче Number . Фактический тип объекта может быть скрыт от клиентов в «черном ящике » и доступен через идентификатор объекта . Фактически, если тип Number является абстрактным , возможно, даже не удастся получить объект, наиболее производным типом которого является Number (см. абстрактный тип данных , абстрактный класс ). Этот конкретный вид иерархии типов известен — особенно в контексте языка программирования Scheme — как числовая башня и обычно содержит гораздо больше типов.
Объектно-ориентированные языки программирования предлагают полиморфизм подтипов с использованием подклассов (также известных как наследование ). В типичных реализациях каждый класс содержит так называемую виртуальную таблицу (сокращенно называемую vtable ) — таблицу функций, реализующих полиморфную часть интерфейса класса, — и каждый объект содержит указатель на виртуальную таблицу своего класса, к которой затем обращаются. всякий раз, когда вызывается полиморфный метод. Этот механизм является примером:
- позднее связывание , поскольку вызовы виртуальных функций не привязываются до момента вызова;
- одинарная диспетчеризация (т. е. полиморфизм с одним аргументом), поскольку вызовы виртуальных функций связываются просто путем просмотра виртуальной таблицы, предоставленной первым аргументом (
thisобъект), поэтому типы времени выполнения других аргументов совершенно не имеют значения.
То же самое касается большинства других популярных объектных систем. Однако некоторые из них, такие как Common Lisp Object System , обеспечивают множественную диспетчеризацию , при которой вызовы методов являются полиморфными по всем аргументам.
Взаимодействие параметрического полиморфизма и подтипирования приводит к концепциям дисперсии и ограниченной количественной оценки .
Полиморфизм строк
[ редактировать ]Полиморфизм строк [8] — это похожая, но отличная концепция от подтипирования. Речь идет о структурных типах . Это позволяет использовать все значения, типы которых имеют определенные свойства, без потери остальной информации о типе.
Политипизм
[ редактировать ]Родственное понятие — политипизм (или универсальность типов данных ). Политипическая функция является более общей, чем полиморфная, и в такой функции «хотя можно обеспечить фиксированные специальные случаи для определенных типов данных, специальный комбинатор отсутствует». [9]
Ранговый полиморфизм
[ редактировать ]Полиморфизм рангов является одной из определяющих особенностей языков программирования массивов , таких как APL . Суть модели рангового полиморфного программирования заключается в неявном рассмотрении всех операций как совокупных операций, которые можно использовать с массивами с произвольным числом измерений. [10] то есть полиморфизм рангов позволяет определять функции для работы с массивами любой формы и размера.
Аспекты реализации
[ редактировать ]Статический и динамический полиморфизм
[ редактировать ]Полиморфизм можно отличить по тому, когда выбрана реализация: статически (во время компиляции) или динамически (во время выполнения, обычно через виртуальную функцию ). Это известно соответственно как статическая диспетчеризация и динамическая диспетчеризация , а соответствующие формы полиморфизма соответственно называются статическим полиморфизмом и динамическим полиморфизмом .
Статический полиморфизм выполняется быстрее, поскольку отсутствуют накладные расходы на динамическую диспетчеризацию, но требуется дополнительная поддержка компилятора. Кроме того, статический полиморфизм позволяет более эффективно выполнять статический анализ компиляторами (особенно для оптимизации), инструментами анализа исходного кода и читателями (программистами). Динамический полиморфизм более гибок, но медленнее — например, динамический полиморфизм допускает утиную типизацию, а динамически подключаемая библиотека может работать с объектами, не зная их полного типа.
Статический полиморфизм обычно возникает при полиморфизме ad hoc и параметрическом полиморфизме, тогда как динамический полиморфизм обычно встречается при полиморфизме подтипа. Однако можно достичь статического полиморфизма с помощью подтипирования за счет более сложного использования метапрограммирования шаблонов , а именно любопытно повторяющегося шаблона шаблона .
Когда полиморфизм раскрывается через библиотеку , статический полиморфизм становится невозможным для динамических библиотек , поскольку нет возможности узнать, какого типа параметры при общего объекта построении . В то время как такие языки, как C++ и Rust, используют мономорфизованные шаблоны, язык программирования Swift широко использует динамическую отправку для создания двоичного интерфейса приложения для этих библиотек по умолчанию. В результате можно использовать больше кода для уменьшения размера системы за счет накладных расходов во время выполнения. [11]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Карделли, Лука ; Вегнер, Питер (декабрь 1985 г.). «О понимании типов, абстракции данных и полиморфизме» (PDF) . Обзоры вычислительной техники ACM . 17 (4): 471–523. CiteSeerX 10.1.1.117.695 . дои : 10.1145/6041.6042 . S2CID 2921816 . : «Полиморфные типы — это типы, операции которых применимы к значениям более чем одного типа».
- ^
Бьерн Страуструп (19 февраля 2007 г.). «Глоссарий C++ Бьярна Страуструпа» .
полиморфизм – предоставление единого интерфейса для сущностей разных типов.
- ^ «Полиморфизм» . Учебные пособия по Java™: Изучение языка Java: интерфейсы и наследование . Оракул . Проверено 08 сентября 2021 г.
- ^ Коналлен, Дж.; Энгл, М.; Хьюстон, К.; Максимчук Р.; Янг, Б.; Буч, Г. (2007). Объектно-ориентированный анализ и проектирование с приложениями (3-е изд.). Пирсон Образование. ISBN 9780132797443 .
- ^ Перейти обратно: а б Стрейчи, Кристофер (2000). «Фундаментальные концепции языков программирования». Вычисления высшего порядка и символьные вычисления . 13 (1/2): 11–49. CiteSeerX 10.1.1.332.3161 . дои : 10.1023/А:1010000313106 . ISSN 1573-0557 . S2CID 14124601 .
- ^ Такер, Аллен Б. (2004). Справочник по информатике (2-е изд.). Тейлор и Фрэнсис. стр. 91–. ISBN 978-1-58488-360-9 .
- ^ Пирс, Британская Колумбия (2002). «23.2 Разновидности полиморфизма» . Типы и языки программирования . МТИ Пресс. стр. 340–1. ISBN 9780262162098 .
- ^ Ванд, Митчелл (июнь 1989 г.). «Вывод типа для конкатенации записей и множественного наследования». Слушания. Четвертый ежегодный симпозиум по логике в информатике . стр. 92–97. дои : 10.1109/LICS.1989.39162 .
- ^ Ламмель, Ральф; Виссер, Йост (2002). «Типизированные комбинаторы для общего обхода». Практические аспекты декларативных языков: 4-й международный симпозиум . Спрингер. стр. 137–154, см. стр. 137–154. 153. CiteSeerX 10.1.1.18.5727 . ISBN 354043092X .
- ^ Слепак, Джастин; Шиверс, Олин; Манолиос, Панайотис (2019). «Семантика рангового полиморфизма». arXiv : 1907.00509 [ cs.PL ].
- ^ Бинесснер, Алексис. «Как Swift добился динамического связывания там, где Rust не смог» .