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

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

пусть   записи   размер   =    |   x   y   ->   (  размер   x  )   +   (  размер   y  )    |   х   ->   1 

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

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

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

элимлист    =   |    Лист   y   ->   y   elimCount   =   |   Посчитайте   y   ->   y 

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

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

элим   =   |   х   ->   |   {  y  }   х   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 .