Один из способов взглянуть на эти две концепции состоит в том, чтобы сказать, что сопоставление с образцом - это особенность языков программирования, позволяющая комбинировать различение в конструкторах и уничтожать термины (одновременно выбирая и локально именуя фрагменты терминов) безопасно, компактно и эффективно. Исследования по сопоставлению с образцом обычно фокусируются на эффективности реализации, например, на том, как минимизировать количество сравнений, которые должен выполнять механизм сопоставления.
Напротив, переписывание терминов - это общая модель вычислений, которая исследует широкий спектр (потенциально недетерминированных) методов замены подтермов синтаксических выражений (точнее, элемента алгебры терминов над некоторым набором переменных) другими терминами. Исследования систем переписывания терминов обычно касаются абстрактных свойств систем перезаписи, таких как слияние, детерминизм и завершение, а более конкретно, о том, как такие свойства сохраняются или не сохраняются алгебраическими операциями над системами перезаписи, т.е. в какой степени эти свойства являются композиционными.
( л , г )С[ l σ] → C[ r σ]С[ . ]σ), в то время как сопоставление с образцом в современных языках, таких как Haskell, OCaml или Scala, предусматривает только переписывание «вверху» термина. Это ограничение также, я думаю, наложено в исчислении паттернов Джея. Позвольте мне объяснить, что я имею в виду под этим ограничением. С сопоставлением с образцом в смысле OCaml, Haskell, Scala вы не можете сказать что-то вроде
match M with
| C[ x :: _ ] -> printf "%i ...\n" x
| C[ [] ] -> printf "[]"
Что C[.]
здесь? Предполагается, что это переменная, охватывающая контексты с одним отверстием. Но языки, такие как OCaml, Haskell или Scala, не предоставляют программистам переменные, которые находятся в произвольном (однопроходном) контексте, а только переменные, которые находятся в разных значениях. Другими словами, в таких языках вы не можете сопоставить шаблон в произвольной позиции в термине. Вы всегда должны указывать путь от корня шаблона к интересующим его частям. Я предполагаю, что основной причиной наложения этого ограничения является то, что в противном случае сопоставление с образцом будет недетерминированным, поскольку термин может соответствовать шаблону в более чем один способ. Например, термин (true, [9,7,4], "hello", 7)
соответствует шаблону C[7]
двумя способами, предполагая, что он C[.]
ранжируется по таким контекстам.
(Я бы лучше написал это как комментарий, но я не могу в настоящее время.)
Поправьте меня, если я ошибаюсь, но, насколько я понимаю, еще одно различие между сопоставлением с образцом и переписыванием терминов, помимо того, что Мартин Бергер сказал в своем превосходном ответе , состоит в том, что правила сопоставления с образцом идут с фиксированным порядком (в реализациях, подобных Haskell's), тогда как с правилами переписывания терминов это не обязательно так. Эта функция, как и следовало ожидать, может иметь большое значение при рассмотрении поведения (в частности, прекращения) правил (см., Например, «Нежное введение в Haskell, версия 98», раздел 4.2 , или просто факториал). пример на "Изучи тебя на Haskell" ).
Люди, более знающие в теории переписывания, могли бы сказать больше об этом (например, как типизация точно соответствует такому сравнению?), Но, мне кажется, справедливо согласиться с Мартином Бергером, в этом смысле можно сказать, что переписывание охватывает сопоставление с образцом (по крайней мере, так как это реализовано в таких языках, как Haskell), в той степени, в которой оба могут (довольно сухо) рассматриваться как устройства, которые просто используют правила, относящиеся к терминам.
источник