Обобщенный алгебраический тип данных - Generalized algebraic data type
В функциональное программирование, а обобщенный алгебраический тип данных (GADT, также первоклассный фантомный тип,[1] защищенный рекурсивный тип данных,[2] или же тип с указанием равенства[3]) является обобщением параметрический алгебраические типы данных.
Обзор
В GADT конструкторы продукта (называемые конструкторы данных в Haskell ) могут предоставить явное создание экземпляра ADT в качестве экземпляра типа их возвращаемого значения. Это позволяет определять функции с более сложным типом поведения. Для конструктора данных Haskell 2010 возвращаемое значение имеет экземпляр типа, подразумеваемый созданием экземпляра параметров ADT в приложении конструктора.
- Параметрический ADT, не являющийся GADTданные Список а = Ноль | Минусы а (Список а)целые числа = Минусы 12 (Минусы 107 Ноль) - тип целых чисел - List Intструны = Минусы "лодка" (Минусы "док" Ноль) - тип строк - строка списка- GADTданные Expr а куда EBool :: Bool -> Expr Bool EInt :: Int -> Expr Int EEqual :: Expr Int -> Expr Int -> Expr Boolоценка :: Expr а -> аоценка е = дело е из EBool а -> а EInt а -> а EEqual а б -> (оценка а) == (оценка б)expr1 = EEqual (EInt 2) (EInt 3) - тип expr1 - Expr BoolRet = оценка expr1 - ret является ложнымВ настоящее время они реализованы в GHC компилятор как нестандартное расширение, используемое, среди прочего, Мопсов и Darcs. OCaml изначально поддерживает GADT, начиная с версии 4.00.[4]
Реализация GHC обеспечивает поддержку параметров типа, определяемых количественно, и локальных ограничений.
История
Ранняя версия обобщенных алгебраических типов данных была описана Августссон и Петерссон (1994) и на основе сопоставление с образцом в ALF.
Обобщенные алгебраические типы данных были введены независимо Чейни и Хинце (2003) и ранее Си, Чен и Чен (2003) как расширение ML 'песок Haskell с алгебраические типы данных.[5] Оба по сути эквивалентны друг другу. Они похожи на индуктивные семейства типов данных (или же индуктивные типы данных) нашел в Coq с Исчисление индуктивных конструкций и другие языки с зависимой типизацией, по модулю зависимых типов и за исключением того, что последние имеют дополнительный ограничение позитивности что не применяется в GADT.[6]
Зульцманн, Wazny & Stuckey (2006) представил расширенные алгебраические типы данных которые объединяют GADT вместе с экзистенциальные типы данных и тип класс ограничения, введенные Перри (1991), Лойфер и Одерский (1994) и Лойфер (1996).
Вывод типа в отсутствие какого-либо программиста аннотации типов является неразрешимый[7] и функции, определенные над GADT, не допускают основные типы в целом.[8] Тип реконструкции требует нескольких компромиссов в дизайне и является областью активных исследований (Пейтон Джонс, Уошберн и Вейрих, 2004 г.; Пейтон Джонс и др. 2006 г.; Pottier & Régis-Gianas 2006; Зульцманн, Шрайверс и Стаки 2006; Симоне и Поттье 2007; Schrijvers et al. 2009 г.; Lin & Sheard 2010a; Лин и Шард 2010b; Витиниотис, Пейтон Джонс и Шрайверс 2010; Vytiniotis et al. 2011 г.).
Приложения
Приложения GADT включают общее программирование, языки программирования моделирования (абстрактный синтаксис высшего порядка ), поддерживая инварианты в структуры данных, выражая ограничения в встроенные предметно-ориентированные языки, и моделирующие объекты.[9]
Абстрактный синтаксис высшего порядка
Важное применение GADT - это встраивание абстрактный синтаксис высшего порядка в тип безопасный мода. Вот вложение просто типизированное лямбда-исчисление с произвольным набором базовые типы, кортежи и комбинатор с фиксированной точкой:
данные Лам :: * -> * куда Поднимать :: а -> Лам а - ^ поднятое значение Пара :: Лам а -> Лам б -> Лам (а, б) - ^ продукт Лам :: (Лам а -> Лам б) -> Лам (а -> б) - ^ лямбда-абстракция Приложение :: Лам (а -> б) -> Лам а -> Лам б - ^ приложение функции Исправить :: Лам (а -> а) -> Лам а - ^ фиксированная точкаИ типобезопасная функция оценки:
оценка :: Лам т -> тоценка (Поднимать v) = vоценка (Пара л р) = (оценка л, оценка р)оценка (Лам ж) = Икс -> оценка (ж (Поднимать Икс))оценка (Приложение ж Икс) = (оценка ж) (оценка Икс)оценка (Исправить ж) = (оценка ж) (оценка (Исправить ж))Факториальную функцию теперь можно записать как:
факт = Исправить (Лам (ж -> Лам (у -> Поднимать (если оценка у == 0 тогда 1 еще оценка у * (оценка ж) (оценка у - 1)))))оценка(факт)(10)Мы бы столкнулись с проблемами при использовании обычных алгебраических типов данных. Удаление параметра типа привело бы к экзистенциальной количественной оценке поднятых базовых типов, что сделало бы невозможным написать оценщик. С параметром типа мы все равно будем ограничены одним базовым типом. Кроме того, неправильно сформированные выражения, такие как Приложение (Lam (x -> Lam (y -> App x y))) (Lift True) можно было бы сконструировать, хотя они имеют неверный тип, используя GADT. Правильно сформированный аналог - Приложение (Lam (x -> Lam (y -> App x y))) (Lift (z -> True)). Это потому, что тип Икс является Лам (а -> б), выведенный из типа Лам конструктор данных.
Смотрите также
Примечания
- ^ Чейни и Хинце 2003.
- ^ Си, Чен и Чен 2003.
- ^ Шеард и Пашалич 2004.
- ^ «OCaml 4.00.1». ocaml.org.
- ^ Чейни и Хинце 2003, п. 25.
- ^ Чейни и Хинце 2003 С. 25–26.
- ^ Пейтон Джонс, Уошберн и Вейрих, 2004 г., п. 7.
- ^ Schrijvers et al. 2009 г., п. 1.
- ^ Пейтон Джонс, Уошберн и Вейрих, 2004 г., п. 3.
дальнейшее чтение
- Приложения
- Аугустссон, Леннарт; Петерссон, Кент (сентябрь 1994 г.). «Семьи глупого типа» (PDF). Цитировать журнал требует
| журнал =(помощь)CS1 maint: ref = harv (связь) - Чейни, Джеймс; Хинце, Ральф (2003). «Первоклассные фантомные типы». Технический отчет CUCIS TR2003-1901. Корнелл Университет. HDL:1813/5614.CS1 maint: ref = harv (связь)
- Си, Хунвэй; Чен, Чиянь; Чен, Ганг (2003). Защищенные рекурсивные конструкторы типов данных. Материалы 30-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования (POPL'03). ACM Press. С. 224–235. CiteSeerX 10.1.1.59.4622. Дои:10.1145/604131.604150. ISBN 978-1581136289.CS1 maint: ref = harv (связь)
- Шеард, Тим; Пашалич, эмир (2004). «Мета-программирование со встроенным равенством типов». Труды Четвертого международного семинара по логическим структурам и метаязыкам (LFM'04), Корк. 199: 49–65. Дои:10.1016 / j.entcs.2007.11.012.CS1 maint: ref = harv (связь)
- Семантика
- Патрисия Йоханн и Нил Гани (2008). «Основы структурного программирования с помощью GADT».
- Ари Мидделкооп, Аце Дейкстра и С. Доаитсе Свиерстра (2011). «Экономичная спецификация для GADT: система F с первоклассными доказательствами равенства». Вычисление высшего порядка и символическое вычисление.
- Тип реконструкции
- Пейтон Джонс, Саймон; Уошберн, Джеффри; Вейрих, Стефани (2004). «Шаткие типы: вывод типов для обобщенных алгебраических типов данных» (PDF). Технический отчет MS-CIS-05-25. Пенсильванский университет.CS1 maint: ref = harv (связь)
- Пейтон Джонс, Саймон; Витиниотис, Димитриос; Вейрих, Стефани; Уошберн, Джеффри (2006). «Простой вывод типа на основе объединения для GADT» (PDF). Труды Международной конференции ACM по функциональному программированию (ICFP'06), Портленд.CS1 maint: ref = harv (связь)
- Зульцманн, Мартин; Wazny, Джереми; Стаки, Питер Дж. (2006). «Платформа для расширенных алгебраических типов данных». В Hagiya, M .; Вадлер, П. (ред.). 8-й Международный симпозиум по функциональному и логическому программированию (FLOPS 2006). Конспект лекций по информатике. 3945. С. 46–64.CS1 maint: ref = harv (связь)
- Зульцманн, Мартин; Шрайверс, Том; Стаки, Питер Дж. (2006). «Вывод основного типа для классов многопараметрических типов в стиле GHC». В Кобаяси, Наоки (ред.). Языки и системы программирования: 4-й Азиатский симпозиум (APLAS 2006). Конспект лекций по информатике. 4279. С. 26–43.CS1 maint: ref = harv (связь)
- Шрайверс, Том; Пейтон Джонс, Саймон; Зульцманн, Мартин; Витиниотис, Димитриос (2009). «Полный и разрешимый вывод типа для GADT» (PDF). Труды Международной конференции ACM по функциональному программированию (ICFP'09), Эдинбург.CS1 maint: ref = harv (связь)
- Линь, Чуан-кай (2010). Практический вывод типа для системы типов GADT (PDF) (Докторская диссертация). Государственный университет Портленда.CS1 maint: ref = harv (связь)
- Другой
- Эндрю Кеннеди и Клаудио В. Руссо. «Обобщенные алгебраические типы данных и объектно-ориентированное программирование». В материалах 20-й ежегодной конференции ACM SIGPLAN по объектно-ориентированному программированию, системам, языкам и приложениям. ACM Press, 2005.
внешняя ссылка
- Страница обобщенных алгебраических типов данных на Haskell вики
- Обобщенные алгебраические типы данных в Руководстве пользователя GHC
- Обобщенные алгебраические типы данных и объектно-ориентированное программирование
- GADT - Haskell Prime - Trac
- Статьи о выводе типов для GADT, библиография Саймон Пейтон Джонс
- Вывод типа с ограничениями, библиография Саймон Пейтон Джонс
- Эмуляция GADT на Java с помощью леммы Йонеды