Исчисление шаблонов

Исчисление шаблонов основывает все вычисления на сопоставлении шаблонов очень общего типа. Как и лямбда-исчисление , он поддерживает единообразный подход к оценке функции . Кроме того, это позволяет функциям быть передаются как аргументы и возвращаются как результаты. Кроме того, исчисление шаблонов поддерживает единый доступ к внутренней структуре аргументов, будь то пары или списки или деревья . Кроме того, он позволяет передавать шаблоны в качестве аргументов и возвращено как результаты. Равномерный доступ иллюстрируется функция сопоставления с образцом size который вычисляет размер произвольная структура данных . В обозначениях языка программирования Bondi он задается рекурсивной функцией

let rec size = 
 | x y -> (size x) + (size y) 
 | x -> 1

Второй, или случай по умолчанию x -> 1 соответствует шаблону x против аргумента и возвращает 1. Этот case используется только в том случае, если сопоставление не удалось в первом случае. первое или особое совпадение с любым соединением , например как непустой список или пару. Соответствующие привязки x к левому компоненту и y к нужному компоненту. Затем в тело корпуса добавляется размеры этих компонентов вместе взятые.

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

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

elimLeaf  = |  Leaf y -> y 
elimCount = | Count y -> y

Например, elimLeaf (Leaf 3) оценивается как 3 как и elimCount (Count 3).

Эти примеры можно получить, применив общий элиминатор elim рассматриваемым конструкторам. Это определяется

elim = | x -> | {y} x y -> y

Сейчас elim Leaf оценивается как | {y} Leaf y -> y что эквивалентно elimLeaf. Также elim Count эквивалентно elimCount.

В общем, фигурные скобки {} содержат связанные переменные узор, так что x бесплатно и y связан в | {y} x y -> y.

Внешние ссылки

• Архивное зеркало ссылок ниже (которых больше нет в сети)
• Джей, К. Барри (ноябрь 2004 г.). «Узорное исчисление» . АКМ Транс. Программа. Ланг. Сист . 26 (6): 911–937. дои : 10.1145/1034774.1034775 . S2CID   14252624 . — оригинальная статья, но не самая общая.
• Джей, Б.; Кеснер, Д. (2006). «Чистое шаблонное исчисление». В Сестофте, П. (ред.). Языки и системы программирования. ЭСОП 2006 . Конспекты лекций по информатике. Том. 3924. Спрингер. стр. 100–114. дои : 10.1007/11693024_8 . hdl : 10453/1684 . ISBN  978-3-540-33096-7 .
• Джей, Барри (2009). Шаблонное исчисление: вычисления с функциями и структурами . Спрингер. дои : 10.1007/978-3-540-89185-7 . ISBN  978-3-540-89185-7 .
• сайт исследования языка программирования Bondi
• Гивен-Уилсон, Т.; Горла, Д.; Джей, Б. (2010). «Исчисление параллельных шаблонов». В Калуде, CS; Сассоне, В. (ред.). Теоретическая информатика. ТКС 2010 . ИФИП: Достижения в области информационных и коммуникационных технологий. Том. 323. Спрингер. дои : 10.1007/978-3-642-15240-5_18 . ISBN  978-3-642-15240-5 .