Полиморфная рекурсия - Polymorphic recursion
В Информатика, полиморфная рекурсия (также называемый Типичность Милнера – Майкрофта или Исчисление Милнера – Майкрофта) относится к рекурсивный параметрически полиморфный функция где параметр типа изменяется при каждом рекурсивном вызове вместо того, чтобы оставаться постоянным. Вывод типа для полиморфной рекурсии эквивалентно полуобъединение и поэтому неразрешимый и требует использования полуалгоритм или программист аннотации типов.[1]
Пример
Вложенные типы данных
Рассмотрим следующие вложенный тип данных:
данные Вложенный а = а :<: (Вложенный [а]) | Эпсилонинфиксный 5 :<:вложенный = 1 :<: [2,3,4] :<: [[5,6],[7],[8,9]] :<: ЭпсилонФункция длины, определенная для этого типа данных, будет полиморфно рекурсивной, поскольку тип аргумента изменится с Вложенный к Вложенный [a] в рекурсивном вызове:
длина :: Вложенный а -> Intдлина Эпсилон = 0длина (_ :<: хз) = 1 + длина хзОбратите внимание, что Haskell обычно подразумевает подпись типа для такой простой функции, как эта, но здесь ее нельзя пропустить, не вызывая ошибки типа.
Высшие типы
![[значок]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Май 2012 г.) |
Приложения
Анализ программы
В типовой анализ программ полиморфная рекурсия часто необходима для достижения высокой точности анализа. Известные примеры систем, использующих полиморфную рекурсию, включают системы Дюссарта, Хенглейна и Моссина. анализ времени связывания[2] и Тофте-Талпин региональное управление памятью система.[3] Поскольку эти системы предполагают, что выражения уже были напечатаны в базовой системе типов (не обязательно с использованием полиморфной рекурсии), вывод может быть снова сделан разрешимым.
Структуры данных, обнаружение ошибок, графические решения
Структуры данных функционального программирования часто используют полиморфную рекурсию для упрощения проверки ошибок типов и решения проблем с помощью неприятных «средних» временных решений, которые поглощают память в более традиционных структурах данных, таких как деревья. В двух следующих цитатах Окасаки (стр. 144–146) приводит пример МИНУСОВ в Haskell при этом система полиморфных типов автоматически помечает ошибки программиста.[4] Рекурсивный аспект заключается в том, что определение типа гарантирует, что внешний конструктор имеет один элемент, второй - пару, третий - пару пар и т. Д. Рекурсивно, устанавливая шаблон автоматического поиска ошибок в типе данных. Робертс (стр. 171) приводит родственный пример в Ява, используя Учебный класс для представления кадра стека. Приведенный пример является решением Ханойская башня проблема, в которой стек имитирует полиморфную рекурсию с начальной, временной и конечной структурой замещения вложенного стека.[5]
Смотрите также
Примечания
- ^ Хенглейн 1993.
- ^ Дуссар, Дирк; Хенглейн, Фриц; Моссин, Кристиан. «Полиморфная рекурсия и квалификация подтипа: полиморфный анализ времени связывания в полиномиальное время». Труды 2-го Международного симпозиума по статическому анализу (SAS).
- ^ Тофте, Мадс; Талпин, Жан-Пьер (1994). «Реализация типизированного λ-исчисления вызова по значению с использованием стека регионов». POPL '94: Материалы 21-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования. Нью-Йорк, Нью-Йорк, США: ACM. С. 188–201. Дои:10.1145/174675.177855. ISBN 0-89791-636-0.
- ^ Крис Окасаки (1999). Чисто функциональные структуры данных. Нью-Йорк: Кембридж. п. 144. ISBN 978-0521663502.
- ^ Эрик Робертс (2006). Рекурсивное мышление с помощью Java. Нью-Йорк: Вили. п.171. ISBN 978-0471701460.
дальнейшее чтение
- Меертенс, Ламберт (1983). «Инкрементальная проверка полиморфного типа в B» (PDF). Симпозиум ACM по принципам языков программирования (POPL), Остин, Техас.
- Майкрофт, Алан (1984). Схемы полиморфных типов и рекурсивные определения. Международный симпозиум по программированию, Тулуза, Франция. Конспект лекций по информатике. 167. С. 217–228. Дои:10.1007/3-540-12925-1_41. ISBN 978-3-540-12925-7.
- Хенглейн, Фриц (1993). «Вывод типа с полиморфной рекурсией». Транзакции ACM по языкам и системам программирования. 15 (2): 253–289. CiteSeerX 10.1.1.42.3091. Дои:10.1145/169701.169692.
- Кфури, А.Дж.; Тюрин, Дж .; Уржичин, П. (апрель 1993 г.). «Реконструкция типа при наличии полиморфной рекурсии». Транзакции ACM по языкам и системам программирования. 15 (2): 290–311. Дои:10.1145/169701.169687. ISSN 0164-0925.
- Майкл И. Шварцбах (июнь 1995 г.). «Вывод полиморфного типа». Технический отчет BRICS-LS-95-3.
- Эммс, Мартин; Лайсс, Ганс (1996). «Расширение средства проверки типов для SML с помощью полиморфной рекурсии - доказательство правильности». Технический отчет 96-101.
- Ричард Берд и Ламберт Меертенс (1998). «Вложенные типы данных».
- К. Васконселлос, Л. Фигейредо, К. Камарао (2003). «Практический вывод типов для полиморфной рекурсии: реализация на Haskell». Журнал универсальных компьютерных наук.
- Л. Фигейредо, К. Камарао. «Вывод типа для полиморфных рекурсивных определений: спецификация в Haskell».
- Халлетт, Дж. Дж; Кфоури, А. Дж. (Июль 2005 г.). «Примеры программирования, требующие полиморфной рекурсии». Электронные заметки по теоретической информатике. 136: 57–102. Дои:10.1016 / j.entcs.2005.06.014. ISSN 1571-0661.
внешняя ссылка
- Стандартный ML с полиморфной рекурсией Ганса Лайсса, Мюнхенский университет
 | Этот компьютерное программирование -связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |