Полиморфизм (информатика) - Polymorphism (computer science)

Не путать с Полиморфный код.
Полиморфизм
Специальный полиморфизм
Параметрический полиморфизм
Подтип

В языки программирования и теория типов, полиморфизм предоставление единого интерфейс организациям различных типы[1] или использование одного символа для представления нескольких различных типов.[2]

Наиболее известные основные классы полиморфизма:

  • Специальный полиморфизм: определяет общий интерфейс для произвольного набора индивидуально указанных типов.
  • Параметрический полиморфизм: когда один или несколько типов указаны не по имени, а с помощью абстрактных символов, которые могут представлять любой тип.
  • Подтип (также называемый полиморфизм подтипа или же полиморфизм включения): когда имя обозначает экземпляры множества разных классов, связанных каким-то общим суперклассом.[3]

История

Интерес к полиморфным системы типов значительно развился в 1960-х, а практические реализации начали появляться к концу десятилетия. Специальный полиморфизм и параметрический полиморфизм были первоначально описаны в Кристофер Стрейчи с Фундаментальные концепции языков программирования[4], где они указаны как «два основных класса» полиморфизма. Специальный полиморфизм был особенностью Алгол 68, в то время как параметрический полиморфизм был ключевой особенностью ML система типов.

В статье 1985 г. Питер Вегнер и Лука Карделли ввел термин полиморфизм включения моделировать подтипы и наследование,[2] цитируя Симула как первый язык программирования, который его реализовал.

Типы

Специальный полиморфизм

Основная статья: Специальный полиморфизм

Кристофер Стрейчи выбрал термин специальный полиморфизм для обозначения полиморфных функций, которые могут применяться к аргументам разных типов, но ведут себя по-разному в зависимости от типа аргумента, к которому они применяются (также известный как перегрузка функции или же перегрузка оператора ).[5] Период, термин "для этого случая "в этом контексте не является уничижительным; это просто относится к тому факту, что этот тип полиморфизма не является фундаментальной особенностью системы типов. Паскаль / Delphi пример ниже, Добавлять При просмотре вызовов функции кажутся общими для разных типов, но компилятор считает, что это две совершенно разные функции для всех целей и задач:

программа Для этого случая;функция Добавлять(Икс, у : Целое число) : Целое число;начинать    Добавлять := Икс + уконец;функция Добавлять(s, т : Нить) : Нить;начинать    Добавлять := Concat(s, т)конец;начинать    Writeln(Добавлять(1, 2));                   (* Печать "3" *)    Writeln(Добавлять('Привет, ', «Млекопитающие!»));    (* Печать «Здравствуйте, млекопитающие!» *)конец.

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

Неявное преобразование типа также была определена как форма полиморфизма, называемая «полиморфизмом принуждения».[2][6]

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

Основная статья: Параметрический полиморфизм

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

Концепция параметрического полиморфизма применима как к типы данных и функции. Функция, которая может оценивать значения различных типов или применяться к ним, известна как полиморфная функция. Тип данных, который может иметь обобщенный тип (например, список с элементами произвольного типа) обозначается полиморфный тип данных как обобщенный тип, из которого сделаны такие специализации.

Параметрический полиморфизм повсеместно используется в функциональном программировании, где его часто называют просто «полиморфизмом». Следующий пример в Haskell показывает тип данных параметризованного списка и две параметрически полиморфные функции для них:

данные Список а = Ноль | Минусы а (Список а)длина :: Список а -> Целое числодлина Ноль         = 0длина (Минусы Икс хз) = 1 + длина хзкарта :: (а -> б) -> Список а -> Список бкарта ж Ноль         = Нолькарта ж (Минусы Икс хз) = Минусы (ж Икс) (карта ж хз)

Параметрический полиморфизм также доступен в нескольких объектно-ориентированных языках. Например, шаблоны в C ++ и D или под названием дженерики в C #, Delphi и Java:

учебный класс Список<Т> {    учебный класс Узел<Т> {        Т элем;        Узел<Т> следующий;    }    Узел<Т> голова;    int длина() { ... }}Список<B> карта(Func<А, B> ж, Список<А> хз) {    ...}

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

Подтип

Основная статья: Подтип

В некоторых языках используется идея подтип (также называемый полиморфизм подтипа или же полиморфизм включения), чтобы ограничить диапазон типов, которые могут использоваться в конкретном случае полиморфизма. В этих языках подтипирование позволяет написать функцию, которая принимает объект определенного типа. Т, но также работают правильно, если передан объект, принадлежащий типу S это подтип Т (согласно Принцип подстановки Лискова ). Это отношение типов иногда записывают S <: Т. Наоборот, Т считается супертип из S- написано Т :> S. Полиморфизм подтипа обычно разрешается динамически (см. Ниже).

В следующем примере мы делаем кошек и собак подтипами животных. Процедура LetHear () принимает животное, но также будет работать правильно, если ему будет передан подтип:

Абстрактные учебный класс Животное {    Абстрактные Нить разговаривать();}учебный класс Кот расширяет Животное {    Нить разговаривать() {        возвращаться "Мяу!";    }}учебный класс Собака расширяет Животное {    Нить разговаривать() {        возвращаться "Гав!";    }}статический пустота LetHear(окончательный Животное а) {    println(а.разговаривать());}статический пустота главный(Нить[] аргументы) {    LetHear(новый Кот());    LetHear(новый Собака());}

В другом примере, если Число, Рациональный, и Целое число такие типы, что Число :> Рациональный и Число :> Целое число, функция, написанная так, чтобы Число будет работать одинаково хорошо при прохождении Целое число или же Рациональный как когда прошел Число. Фактический тип объекта может быть скрыт от клиентов в черный ящик, и доступ через объект личность Фактически, если Число тип Абстрактные, может оказаться невозможным даже достать в руки объект, наиболее извлеченный тип Число (видеть абстрактный тип данных, абстрактный класс ). Этот конкретный вид иерархии типов известен - особенно в контексте Язык программирования схем -как числовая башня, и обычно содержит гораздо больше типов.

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

  • позднее связывание, потому что вызовы виртуальных функций не привязываются до момента вызова;
  • разовая отправка (т.е. полиморфизм с одним аргументом), потому что вызовы виртуальных функций привязываются просто путем просмотра таблицы vtable, предоставленной первым аргументом ( это object), поэтому типы времени выполнения других аргументов совершенно не важны.

То же самое и с большинством других популярных объектных систем. Некоторые, однако, такие как Общая объектная система Lisp, предоставлять множественная отправка, при котором вызовы методов полиморфны в все аргументы.

Взаимодействие между параметрическим полиморфизмом и подтипами приводит к концепции отклонение и ограниченная количественная оценка.

Полиморфизм строк

Основная статья: Полиморфизм строк
Смотрите также: Утка печатает

Полиморфизм строк[8] это похожее, но отличное от подтипа понятие. Это касается структурные типы. Он позволяет использовать все значения, типы которых имеют определенные свойства, без потери оставшейся информации о типе.

Политипизм

Основная статья: Общее программирование § Функциональные языки

Связанная концепция политипизм (или же универсальность типа данных). Политипическая функция является более общей, чем полиморфная, и в такой функции, «хотя можно предоставить фиксированные специальные случаи для определенных типов данных, специальный комбинатор отсутствует».[9]

Аспекты реализации

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

Основные статьи: Статический полиморфизм, Поздняя привязка, и Динамическая отправка

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

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

Статический полиморфизм обычно возникает при специальном полиморфизме и параметрическом полиморфизме, тогда как динамический полиморфизм является обычным для полиморфизма подтипа. Однако можно достичь статического полиморфизма с выделением подтипов за счет более сложного использования метапрограммирование шаблона, а именно любопытно повторяющийся шаблон шаблона.

Когда полиморфизм раскрывается через библиотека, статический полиморфизм становится невозможным для динамические библиотеки поскольку нет способа узнать, какие типы параметров, когда общий объект построено. В то время как такие языки, как C ++ и Rust, используют мономорфные шаблоны, Язык программирования Swift широко использует динамическую отправку для создания двоичный интерфейс приложения для этих библиотек по умолчанию. В результате можно совместно использовать больше кода для уменьшения размера системы за счет накладных расходов времени выполнения.[10]

Смотрите также

Рекомендации

  1. ^ Бьярне Страуструп (19 февраля 2007 г.). "Глоссарий C ++ Бьярна Страуструпа". полиморфизм - предоставление единого интерфейса для сущностей разных типов.
  2. ^ а б c Карделли, Лука; Вегнер, Питер (Декабрь 1985 г.). «О понимании типов, абстракции данных и полиморфизма» (PDF). Опросы ACM Computing. 17 (4): 471–523. CiteSeerX  10.1.1.117.695. Дои:10.1145/6041.6042. ISSN  0360-0300.: «Полиморфные типы - это типы, операции которых применимы к значениям более чем одного типа».
  3. ^ Буч и др., 2007 г. Объектно-ориентированный анализ и дизайн с приложениями. Эддисон-Уэсли.
  4. ^ Стрейчи, Кристофер (2000). «Основные понятия языков программирования». Вычисление высшего порядка и символическое вычисление. 13 (1/2): 11–49. CiteSeerX  10.1.1.332.3161. Дои:10.1023 / А: 1010000313106. ISSN  1573-0557.
  5. ^ Кристофер Стрейчи. Фундаментальные концепции языков программирования (PDF). www.itu.dk. Kluwer Academic Publishers. Архивировано из оригинал (PDF) на 2017-08-12. Получено 2012-10-13.
  6. ^ Аллен Б. Такер (28 июня 2004 г.). Справочник по информатике, второе издание. Тейлор и Фрэнсис. С. 91–. ISBN  978-1-58488-360-9.
  7. ^ Пирс, Б. С. 2002 Типы и языки программирования. MIT Press.
  8. ^ Палочка, Митчелл (июнь 1989 г.). «Вывод типа для объединения записей и множественного наследования». Ход работы. Четвертый ежегодный симпозиум по логике в компьютерных науках. С. 92–97. Дои:10.1109 / LICS.1989.39162.
  9. ^ Ральф Ламмель и Йост Виссер, «Типизированные комбинаторы для универсального обхода», в Практические аспекты декларативных языков: 4-й международный симпозиум (2002), стр. 153.
  10. ^ Бесснер, Алексис. "Как Swift добился динамического связывания там, где не смог Rust".

внешняя ссылка