Исчисление шаблонов - Pattern calculus
 | Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. (Ноябрь 2016) (Узнайте, как и когда удалить этот шаблон сообщения) |
Исчисление шаблонов основывает все вычисления на сопоставление с образцом очень общего вида. Нравиться лямбда-исчисление, он поддерживает единообразное лечение оценка функции. Кроме того, он позволяет передавать функции как аргументы и возвращать их как результаты. Кроме того, исчисление шаблонов поддерживает единообразный доступ к внутренней структуре аргументов, будь то пары или списки или же деревья. Кроме того, он позволяет передавать шаблоны в качестве аргументов и возвращать их в качестве результатов. Единый доступ иллюстрируется функцией сопоставления шаблонов размер который вычисляет размер произвольного структура данных. В обозначениях язык программированиябонди, это дается рекурсивная функция
позволять rec размер = | Икс у -> (размер Икс) + (размер у) | Икс -> 1Второй, или случай по умолчанию х -> 1 соответствует шаблону Икспротив аргумента и возвращает 1. Этот случай используется только в том случае, если сопоставление не удалось в первом случае. Первый или особый случай матчи против любых сложный, например, непустой список или пара. Соответствующие привязки Икс к левому компоненту и у к нужному компоненту. Затем корпус кейса складывает размеры этих компонентов вместе.
Подобные методы дают общие запросы для поиска и обновления. Комбинируя таким образом рекурсию и декомпозицию, получаем полиморфизм путей.
Возможность передавать шаблоны в качестве параметров (полиморфизм паттернов) иллюстрируется определением универсального элиминатора. Предположим, что заданы конструкторы Лист для создания листьев дерева, и Считать для конвертации чисел в счетчики. Соответствующие элиминаторы тогда
elimLeaf = | Лист у -> у elimCount = | Считать у -> уНапример, elimLeaf (Лист 3) оценивает 3 так же как и elimCount (счетчик 3).
Эти примеры можно получить, применив универсальный элиминаторЭлим к рассматриваемым конструкторам. Это определяется
Элим = | Икс -> | {у} Икс у -> уСейчас же Элим Лист оценивает | {y} Лист y -> y что эквивалентно elimLeaf. Также элим граф эквивалентно elimCount.
В общем, фигурные скобки {} содержат связанные переменные шаблона, так что Икс бесплатно и у связан в | {y} x y -> y.