Тип класса
В информатике класс типов — это конструкция системы типов , поддерживающая специальный полиморфизм . Это достигается за счет добавления ограничений на переменные типа в параметрически полиморфных типах. Такое ограничение обычно включает класс типа T и переменная типа aи означает, что a может быть создан только тип, члены которого поддерживают перегруженные операции, связанные с T.
Классы типов были впервые реализованы на языке программирования Haskell после того, как их впервые предложили Филип Уодлер и Стивен Блотт в качестве расширения «eqtypes» в Standard ML . [1] [2] способ реализации перегруженных арифметических операций и операторов равенства . и изначально были задуманы как принципиальный [3] [2] В отличие от «eqtypes» Standard ML, перегрузка оператора равенства посредством использования классов типов в Haskell не требует обширной модификации интерфейса компилятора или базовой системы типов. [4]
Обзор [ править ]
Классы типов определяются путем указания набора имен функций или констант вместе с соответствующими типами, которые должны существовать для каждого типа, принадлежащего классу. В Haskell типы можно параметризовать; класс типа Eq предназначенный для содержания типов, допускающих равенство, будет объявлен следующим образом:
class Eq a где
( == ) :: a -> a -> Bool
( /= ) :: a -> a -> Bool
где a является одним экземпляром класса типа Eq, и a определяет сигнатуры функций для двух функций (функций равенства и неравенства), каждая из которых принимает два аргумента типа a и вернуть логическое значение.
Переменная типа a имеет вид ( также известен как Type в последней версии GHC ), [5] означает, что вид Eq является
Eq :: Тип -> Ограничение
Объявление можно прочитать как указание «типа a принадлежит классу типов Eq если есть функции с именем (==), и (/=), соответствующих типов, определенных на нем». Затем программист может определить функцию elem (который определяет, находится ли элемент в списке) следующим образом:
elem :: Eq a => a -> [ a ] -> Bool
elem y [] = False
elem y ( x : xs ) = ( x == y ) || элемент y хз
Функция elem имеет тип a -> [a] -> Bool с контекстом Eq a, который ограничивает типы, которые a может варьироваться от тех a которые принадлежат к Eqтип класса. ( Примечание : Хаскель => можно назвать «ограничением класса».)
Программист может сделать любой тип t член данного класса типов C используя объявление экземпляра , которое определяет реализации всех C' методы для конкретного типа t. Например, если программист определяет новый тип данных t, они могут затем сделать этот новый тип экземпляром Eq предоставляя функцию равенства значений типа tлюбым способом, который они считают нужным. Как только они это сделают, они могут использовать функцию elem на [t], то есть списки элементов типа t.
Обратите внимание, что классы типов отличаются от классов объектно-ориентированных языков программирования. В частности, Eq не является типом: не существует такой вещи, как значение типа Eq.
Классы типов тесно связаны с параметрическим полиморфизмом. Например, обратите внимание, что тип elem как указано выше, это будет параметрически полиморфный тип. a -> [a] -> Bool если бы не ограничение класса типа " Eq a =>".
Полиморфизм высшего рода [ править ]
Класс типа не обязательно должен принимать переменную типа вида Typeно могу взять любой. Эти классы типов с более высокими видами иногда называются классами-конструкторами (конструкторы, о которых идет речь, являются конструкторами типов, такими как Maybe, а не конструкторы данных, такие как Just). Примером является Monad сорт:
класс Monad m , где
return :: a -> m a
( >>= ) :: m a -> ( a -> m b ) -> m b
Тот факт, что m применяется к переменной типа, указывает на то, что она имеет вид Type -> Type, то есть он принимает тип и возвращает тип, вид Monad таким образом:
Монада :: ( Тип -> Тип ) -> Ограничение
Классы типов с несколькими параметрами [ править ]
Классы типов допускают несколько параметров типа, поэтому классы типов можно рассматривать как отношения к типам. [6] Например, в стандартной библиотеке GHC класс IArrayвыражает общий интерфейс неизменяемого массива. В этом классе ограничение класса типа IArray a e Значит это a это тип массива, который содержит элементы типа e. (Это ограничение на полиморфизм используется для реализации неупакованных , например, типов массивов.)
Как мультиметоды [ нужна цитата ] Классы типов с несколькими параметрами поддерживают вызов различных реализаций метода в зависимости от типов нескольких аргументов и типов возвращаемых значений. Классы типов с несколькими параметрами не требуют поиска метода для каждого вызова во время выполнения; [7] : минута 25:12 скорее вызываемый метод сначала компилируется и сохраняется в словаре экземпляра класса типа, как и в случае с классами типов с одним параметром.
Код Haskell, использующий классы типов с несколькими параметрами, не является переносимым, поскольку эта функция не является частью стандарта Haskell 98. Популярные реализации Haskell, GHC и Hugs , поддерживают классы типов с несколькими параметрами.
Функциональные зависимости [ править ]
В Haskell классы типов были усовершенствованы, чтобы позволить программисту объявлять функциональные зависимости между параметрами типа — концепция, вдохновленная теорией реляционных баз данных . [8] [9] То есть программист может утверждать, что данное присвоение некоторого подмножества параметров типа однозначно определяет остальные параметры типа. Например, общая монада m который несет параметр состояния типа s удовлетворяет ограничению класса типа Monad.State s m. В этом ограничении существует функциональная зависимость m -> s. Это означает, что для данной монады m типа класса Monad.State, тип состояния, доступный из mопределяется однозначно. Это помогает компилятору в выводе типа , а также помогает программисту в типизированном программировании .
Саймон Пейтон-Джонс возражал против введения функциональных зависимостей в Haskell по причине сложности. [10]
Классы типов и неявные параметры [ править ]
Классы типов и неявные параметры очень похожи по своей природе, хотя и не совсем одинаковы. Полиморфная функция с ограничением класса типа, например:
сумма :: Num a => [ a ] -> a
можно интуитивно рассматривать как функцию, которая неявно принимает экземпляр Num:
sum_ :: Num_ a -> [ a ] -> a
Экземпляр Num_ a по сути, это запись, содержащая определение экземпляра Num a. (Фактически именно так классы типов реализуются под капотом компилятора Glasgow Haskell.)
Однако есть существенное отличие: неявные параметры более гибкие — вы можете передавать разные экземпляры. Num Int. Напротив, классы типов реализуют так называемое свойство согласованности , которое требует, чтобы для любого данного типа был только один уникальный выбор экземпляра. Свойство когерентности делает классы типов в некоторой степени антимодульными, поэтому настоятельно не рекомендуется использовать потерянные экземпляры (экземпляры, определенные в модуле, который не содержит ни класс, ни интересующий тип). С другой стороны, согласованность добавляет языку дополнительный уровень безопасности, давая программисту гарантию того, что две непересекающиеся части одного и того же кода будут использовать один и тот же экземпляр. [11]
Например, упорядоченный набор (типа Set a) требует полного упорядочения элементов (типа a), чтобы функционировать. Об этом может свидетельствовать ограничение Ord a, который определяет оператор сравнения элементов. Однако существует множество способов навести полный порядок. Поскольку алгоритмы множеств обычно нетерпимы к изменениям порядка после создания набора, передача несовместимого экземпляра Ord aк функциям, которые работают на наборе, может привести к неверным результатам (или сбоям). Таким образом, обеспечение согласованности Ord a в этом конкретном сценарии имеет решающее значение.
Экземпляры (или «словари») в классах типов Scala — это просто обычные значения языка, а не совершенно отдельный вид сущностей. [12] [13] Хотя эти экземпляры по умолчанию предоставляются путем поиска подходящих экземпляров в области видимости, которые будут использоваться в качестве неявных фактических параметров для явно объявленных неявных формальных параметров, тот факт, что они являются обычными значениями, означает, что они могут быть предоставлены явно, чтобы устранить неоднозначность. В результате классы типов Scala не удовлетворяют свойству связности и фактически являются синтаксическим сахаром для неявных параметров.
Это пример из группы Cats. [14] документация:
// Класс типа для предоставления текстового представления
типажа Show [ A ] {
def show ( f : A ): String
}
// Полиморфная функция, которая работает только тогда, когда есть неявный
// экземпляр Show[A] доступный
def log [ A ]( a : A )( неявное s : Show [ A ]) = println ( s . show ( a ))
// Экземпляр для String
неявное val stringShow = new Show [ String ] {
def show ( s : String ) = s
}
// Параметр stringShow был вставлен компилятором.
scala > log ( «строка )
строка »
Coq (версия 8.2 и более поздние) также поддерживает классы типов, определяя соответствующие экземпляры. [15] Последние версии Agda 2 также предоставляют аналогичную функцию, называемую «аргументами экземпляра». [16]
подходы к операторов Другие перегрузке
В Standard ML механизм «типов равенства» примерно соответствует встроенному классу типов Haskell. Eq, но все операторы равенства создаются компилятором автоматически. Контроль над процессом со стороны программиста ограничивается указанием того, какие компоненты типов в структуре являются типами равенства, а переменные каких типов в диапазоне полиморфных типов превышают типы равенства.
Модули и функторы SML и OCaml могут играть роль, аналогичную роли классов типов Haskell, причем принципиальным отличием является роль вывода типа, что делает классы типов пригодными для специального полиморфизма. [17] Объектно-ориентированное подмножество OCaml — это еще один подход, который в некоторой степени сравним с подходом к классам типов.
Связанные понятия [ править ]
Аналогичным понятием для перегруженных данных (реализованным в GHC ) является семейство типов . [18]
В C++, в частности, в C++20 имеется поддержка классов типов с использованием Concepts (C++) . В качестве иллюстрации приведенный выше пример класса типов Eq на Haskell можно записать как
шаблон < имя типа T >
концепция Equal =
требует ( T a , T b ) {
{ a == b } -> std :: Convertible_to < bool > ;
{ a != b } -> std :: Convertible_to < bool > ;
};
Классы типов в Clean похожи на Haskell, но имеют немного другой синтаксис.
Rust поддерживает типажи , которые представляют собой ограниченную форму согласованных классов типов. [19]
В Mercury есть классы типов, хотя они не совсем такие, как в Haskell. [ нужны дальнейшие объяснения ]
В Scala классы типов — это идиома программирования , которая может быть реализована с использованием существующих функций языка, таких как неявные параметры, а не отдельной функции языка как таковой. Благодаря тому, как они реализованы в Scala, в случае неоднозначности можно явно указать, какой экземпляр класса типа использовать для типа в определенном месте кода. Однако это не обязательно является преимуществом, поскольку экземпляры классов неоднозначных типов могут быть подвержены ошибкам.
Помощник по доказательству Coq также поддерживает классы типов в последних версиях. В отличие от обычных языков программирования, в Coq любые законы класса типов (например, законы монады), изложенные в определении класса типов, должны быть математически доказаны для каждого экземпляра класса типов перед их использованием.
См. также [ править ]
- Полиморфизм (информатика) (другие виды полиморфизма)
- Язык программирования Haskell (язык, на котором впервые были разработаны классы типов)
- Перегрузка операторов (одно применение классов типов)
- Монада (функциональное программирование) (
Monadэто пример класса типа) - Концепции (C++) (начиная с C++20)
- Руст (язык программирования)
Ссылки [ править ]
- ^ Моррис, Джон Г. (2013). Классы типов и цепочки экземпляров: реляционный подход (PDF) (доктор философии). Департамент компьютерных наук Портлендского государственного университета. дои : 10.15760/etd.1010 .
- ^ Перейти обратно: а б Вадлер, П.; Блотт, С. (1989). «Как сделать специальный полиморфизм менее специальным» . Материалы 16-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования (POPL '89) . Ассоциация вычислительной техники. стр. 60–76. дои : 10.1145/75277.75283 . ISBN 0897912942 . S2CID 15327197 .
- ^ Каес, Стефан (март 1988 г.). «Параметрическая перегрузка в полиморфных языках программирования». Учеб. 2-й Европейский симпозиум по языкам программирования . дои : 10.1007/3-540-19027-9_9 .
- ^ Аппель, AW; МакКуин, Д.Б. (1991). «Стандартный ML Нью-Джерси». В Малушиньском, Дж.; Вирсинг, М. (ред.). Реализация языка программирования и логическое программирование. ПЛИЛП 1991 . Конспекты лекций по информатике. Том. 528. Спрингер. стр. 1–13. CiteSeerX 10.1.1.55.9444 . дои : 10.1007/3-540-54444-5_83 . ISBN 3-540-54444-5 .
- ^
TypeотData.Kindпоявился в версии 8 компилятора Glasgow Haskell. - ^ Haskell Страница MultiParamTypeClasses .
- ^ В GHC ядро C использует сигнатуры типов System F Girard & Reynold для идентификации типизированного случая для обработки на этапах оптимизации. -- Саймон Пейтон-Джонс « В ядро — сжатие Haskell в девять конструкторов» Конференция пользователей Erlang, 14 сентября 2016 г.
- ^ Джонс, Марк П. (2000). «Тип-классы с функциональными зависимостями» . В Смолке Г. (ред.). Языки и системы программирования. ЭСОП 2000 . Конспекты лекций по информатике. Том. 1782. Спрингер. стр. 230–244. CiteSeerX 10.1.1.26.7153 . дои : 10.1007/3-540-46425-5_15 . ISBN 3-540-46425-5 .
- ^ Haskell Страница FunctionalDependities .
- ^ Пейтон-Джонс, Саймон (2006). «MPTC и функциональные зависимости» . Список рассылки Haskell-prime .
- ^ Кметт, Эдвард. Классы типов против всего мира . Бостонская встреча Haskell. Архивировано из оригинала 21 декабря 2021 г.
- ^ Оливейра, Бруно CdS; Мавр, Адриан; Одерский, Мартин (2010). «Классы типов как объекты и неявные выражения» (PDF) . Материалы Международной конференции ACM по языкам и приложениям объектно-ориентированных систем программирования (OOPSLA '10) . Ассоциация вычислительной техники. стр. 341–360. CiteSeerX 10.1.1.205.2737 . дои : 10.1145/1869459.1869489 . ISBN 9781450302036 . S2CID 207183083 .
- ^ «Руководство для неофитов по Scala, часть 12: Классы типов — Дэниел Вестхайде» .
- ^ typelevel.org, Scala Cats
- ^ Кастеран, П.; Созо, М. (2014). «Нежное введение в классы типов и отношения в Coq» (PDF) . CiteSeerX 10.1.1.422.8091 .
- ^ « Моделирование классов типов с аргументами экземпляра ».
- ^ Дрейер, Дерек; Харпер, Роберт; Чакраварти, Мануэль М.Т. (2007). «Классы модульных типов». Материалы 34-го ежегодного симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования (POPL '07) . стр. 63–70. См. стр. 63. дои : 10.1145/1190216.1190229 . ISBN 978-1595935755 . S2CID 1828213 . ТР-2006-03.
- ^ «Семейства GHC/Type — HaskellWiki» .
- ^ Турон, Аарон (2017). «Специализация, согласованность и эволюция API» .
- Пейтон Джонс, Саймон; Джонс, Марк; Мейер, Эрик (май 1997 г.). «Тип-классы: исследование пространства дизайна» . Учеб. Семинар по Haskell ACM SIGPLAN . CiteSeerX 10.1.1.1085.8703 .
Внешние ссылки [ править ]
- «5. Классы типов и перегрузка» . Небольшое введение в Haskell . Июнь 2000 г. Версия 98.
- Курс продвинутого функционального программирования в Утрехтском университете, 74 слайда лекций по классам продвинутого типа . 07.06.2005.
- Реализация и понимание классов типов . 13 ноября 2014 г.