Полиморфизм и обобщенные типы

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

Definition

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

Scope

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

Core questions

• Как обобщенные типы обеспечивают повторное использование без ущерба для типобезопасности?
• Что такое параметричность и какие гарантии она дает без дополнительных усилий?
• Как классы типов систематизируют специальную перегрузку?
• Как компилируются обобщенные определения и какие ограничения могут связывать параметры типа?

Key theories

Параметричность (теорема об абстракции)

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

Теоремы бесплатно

Уодлер показал, что тип параметрически полиморфной функции сам по себе подразумевает «бесплатные теоремы» о ее поведении, что является прямым и практическим следствием параметричности.

Классы типов для принципиальной перегрузки

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

Clinical relevance

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

History

System F, воплощающая параметрический полиморфизм, была независимо открыта Жираром и Рейнольдсом в начале 1970-х годов. ML внедрил полиморфизм с выводом типов в практику. Обзор Карделли и Вегнера 1985 года классифицировал формы полиморфизма, Рейнольдс формализовал параметричность в 1983 году, а классы типов Уодлера и Блотта 1989 года сформировали перегрузку в Haskell и повлияли на трейты и концепции в других языках.

Debates

Стирание типов против реифицированных обобщенных типов

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

Key figures

• John Reynolds
• Jean-Yves Girard
• Philip Wadler
• Luca Cardelli
• Robin Milner

Seminal works

• reynolds1983
• wadler1989free
• wadler1989
• cardelli1985

Frequently asked questions

В чем разница между параметрическим и специальным полиморфизмом?

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

Что дает нам параметричность?

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