Как работает оценка на основе терминов?

... Какая качественная, практическая разница делает это? В самом деле, какова разница в том, как он оценивает выражения?

Связанная страница содержит много примеров перезаписи терминов, которые могут быть полезны, но на самом деле она не описывает то, что она делает иначе, чем приложение-функция, за исключением того, что она имеет довольно гибкое сопоставление шаблонов (и сопоставление шаблонов, как оно появляется в Haskell и ML - хороший, но не фундаментальный для стратегии оценки). Значения сопоставляются с левой стороной определения и подставляются в правую сторону - это не просто бета-сокращение?

Совпадение шаблонов и подстановка в выходные выражения поверхностно выглядит мне как syntax-rules мне (или даже скромному #define), но главная особенность этого заключается в том, что это происходит раньше, чем во время оценки, в то время как Pure полностью динамичен, и в его оценочной системе нет очевидного разделения фаз (а на самом деле макросистемы Lisp всегда делали большой шум о том, как они не отличаются от приложения-функции). Возможность манипулировать символическими значениями выражения является "cool'n'all", но также кажется артефактом системы динамического типа, а не чем-то основным для стратегии оценки (довольно уверен, что вы можете перегружать операторов в Scheme для работы с символическими значениями, на самом деле вы даже можете сделать это на С++ с шаблонами выражений).

Итак, какова механическая/операционная разница между переписыванием терминов (как используется Pure) и традиционным функциональным приложением в качестве базовой модели оценки, когда замещение происходит в обоих?

Ответы

Ответ 1

Термин переписывания не должен выглядеть как функциональное приложение, но такие языки, как Pure, подчеркивают этот стиль, потому что a) бета-сокращение просто определить как правило перезаписи и b) функциональное программирование - это хорошо понятая парадигма.

Контрпример может представлять собой парадокс доски или кортежа, для которого термин переписывание также хорошо подходит.

Одно практическое различие между бета-редукцией и полным переписыванием терминов заключается в том, что правила перезаписи могут работать только с определением выражения, а не только с его значением. Это включает сопоставление шаблонов в приводимых выражениях:

-- Functional style
map f nil = nil
map f (cons x xs) = cons (f x) (map f xs)

-- Compose f and g before mapping, to prevent traversing xs twice
result = map (compose f g) xs

-- Term-rewriting style: spot double-maps before they're reduced
map f (map g xs) = map (compose f g) xs
map f nil = nil
map f (cons x xs) = cons (f x) (map f xs)

-- All double maps are now automatically fused
result = map f (map g xs)

Обратите внимание, что мы можем сделать это с помощью макросов LISP (или шаблонов С++), поскольку они представляют собой систему перезаписи терминов, но этот стиль размывает LISP четкое различие между макросами и функциями.

CPP #define не является эквивалентным, поскольку он не является безопасным или гигиеническим (sytactically-valid программы могут стать недействительными после предварительной обработки).

Мы также можем определить специальные предложения для существующих функций по мере необходимости, например.

plus (times x y) (times x z) = times x (plus y z)

Еще одно практическое соображение заключается в том, что правила перезаписи должны быть confluent, если мы хотим детерминированных результатов, т.е. мы получаем тот же результат, независимо от того, в каком порядке мы применяем правила в. Никакой алгоритм не может проверить это для нас (он вообще неразрешимый), а пространство поиска слишком велико, чтобы отдельные тесты могли нам рассказать. Вместо этого мы должны убедить себя, что наша система конфликтована каким-то формальным или неформальным доказательством; одним из способов было бы следовать системам, которые уже известны как конфлюентные.

Например, известно, что бета-редукция сливается (через теорему Церковно-Россера), поэтому, если мы напишем все наши правила в стиле бета-версии -обращения, тогда мы можем быть уверены, что наши правила сливаются. Конечно, именно то, что делают языки функционального программирования!