Uma maneira de analisar esses dois conceitos é dizer que a correspondência de padrões é um recurso das linguagens de programação para combinar a discriminação em termos de construtores e destruir (ao mesmo tempo, selecionar e nomear localmente fragmentos de termos) de maneira segura, compacta e eficiente. A pesquisa sobre correspondência de padrões geralmente se concentra na eficiência da implementação, por exemplo, em como minimizar o número de comparações que o mecanismo de correspondência precisa fazer.
Por outro lado, a reescrita de termos é um modelo geral de computação que investiga uma ampla gama de métodos (potencialmente não determinísticos) de substituição de subtermos de expressões sintáticas (mais precisamente um elemento de uma álgebra de termos sobre algum conjunto de variáveis) por outros termos. A pesquisa em sistemas de reescrita a termo geralmente trata de propriedades abstratas de sistemas de reescrita, como confluência, determinismo e terminação, e mais especificamente sobre como essas propriedades são ou não preservadas por operações algébricas em sistemas de reescrita, ou seja, até que ponto essas propriedades são composicionais.
Claramente, existem sobreposições conceituais entre ambos, e a distinção é, até certo ponto, tradicional e não técnica. Uma diferença técnica é que a reescrita do termo ocorre em contextos arbitrários (ou seja, uma regra induz reescritas para contextos arbitrários E substituições ), enquanto a correspondência de padrões em idiomas modernos como Haskell, OCaml ou Scala fornece apenas a reescrita "na parte superior" de um termo. Acho que essa restrição também é imposta no cálculo padrão de Jay. Deixe-me explicar o que quero dizer com essa restrição. Com a correspondência de padrões no sentido OCaml, Haskell, Scala, você não pode dizer algo como( l , r )C[ l σ] → C[ r σ]C[ . ]σ
match M with
| C[ x :: _ ] -> printf "%i ...\n" x
| C[ [] ] -> printf "[]"
O que tem C[.]
aqui? Supõe-se que seja uma variável que varia em contextos de um orifício. Mas linguagens como OCaml, Haskell ou Scala não fornecem aos programadores variáveis que variam em contextos arbitrários (um orifício), apenas variáveis que variam sobre valores. Em outras palavras, nesses idiomas, você não pode corresponder padrões em uma posição arbitrária em um termo. Você sempre precisa especificar o caminho da raiz do padrão para as partes em que está interessado. Acho que a principal razão para impor essa restrição é que, caso contrário, a correspondência de padrões seria não determinística, porque um termo pode corresponder a um padrão em mais de uma maneira. Por exemplo, o termo (true, [9,7,4], "hello", 7)
corresponde ao padrão C[7]
de duas maneiras, pressupondo que se C[.]
estendesse por esses contextos.
(Prefiro escrever isso como um comentário, mas não posso no momento.)
Me corrija se eu estiver errado, mas, até onde eu entendi, mais uma diferença entre correspondência de padrões e reescrita de termos, além do que Martin Berger disse em sua excelente resposta , é que as regras de correspondência de padrões vêm com uma ordem fixa (em implementações como Haskell), enquanto que com regras de reescrita de termos não é necessariamente o caso. Esse recurso, como seria de esperar, pode fazer muita diferença ao considerar o comportamento (em particular, o término) das regras (consulte "Uma introdução suave a Haskell, versão 98", seção 4.2 , por exemplo, ou apenas o fatorial exemplo em "Aprenda um Haskell" ).
Pessoas mais conhecedoras da teoria da reescrita teriam mais a dizer sobre isso (por exemplo, como a digitação se encaixa exatamente nessa comparação?), Mas parece-me justo concordar com Martin Berger; nesse termo, a reescrita pode incluir correspondência de padrões (pelo menos como isso é implementado em linguagens como Haskell), na medida em que ambos podem ser (bastante secos) vistos como dispositivos que meramente empregam regras relacionadas a termos.
fonte