Una forma de ver estos dos conceptos es decir que la coincidencia de patrones es una característica de los lenguajes de programación para combinar la discriminación en constructores y destruir términos (al mismo tiempo que selecciona y nombra localmente fragmentos de términos) de forma segura, compacta y eficiente. La investigación sobre la coincidencia de patrones generalmente se centra en la eficiencia de la implementación, por ejemplo, sobre cómo minimizar el número de comparaciones que tiene que hacer el mecanismo de coincidencia.
Por el contrario, la reescritura de términos es un modelo general de computación que investiga una amplia gama de métodos (potencialmente no deterministas) para reemplazar subterms de expresiones sintácticas (más precisamente, un elemento de un álgebra de términos sobre un conjunto de variables) con otros términos. La investigación sobre los sistemas de reescritura de términos generalmente trata sobre las propiedades abstractas de los sistemas de reescritura, como la confluencia, el determinismo y la terminación, y más específicamente sobre cómo dichas propiedades se conservan o no mediante operaciones algebraicas en los sistemas de reescritura, es decir, en qué medida estas propiedades son compositivas.
Claramente, hay superposiciones conceptuales entre ambos, y la distinción es hasta cierto punto tradicional, más que técnica. Una diferencia técnica es que la reescritura de términos ocurre en contextos arbitrarios (es decir, una regla induce reescrituras para contextos arbitrarios Y sustituciones ), mientras que La coincidencia de patrones en lenguajes modernos como Haskell, OCaml o Scala proporciona solo la reescritura 'en la parte superior' de un término. Creo que esta restricción también se impone en el cálculo de patrones de Jay. Permítanme explicar lo que quiero decir con esta restricción. Con la coincidencia de patrones en el sentido OCaml, Haskell, Scala, no se puede decir algo comoC [ l σ ] → C [ r σ ] C [ . ] σ( l , r )do[ l σ] → C[ r σ]do[ . ]σ
match M with
| C[ x :: _ ] -> printf "%i ...\n" x
| C[ [] ] -> printf "[]"
Que hay C[.]
aqui Se supone que es una variable que se extiende sobre contextos de un solo agujero. Pero los lenguajes como OCaml, Haskell o Scala no le dan a los programadores variables que se extiendan sobre contextos arbitrarios (un agujero), solo variables que se extiendan sobre valores. En otras palabras, en dichos lenguajes no puede coincidir un patrón en una posición arbitraria de un término. Siempre debe especificar la ruta desde la raíz del patrón hasta las partes que le interesan. Creo que la razón clave para imponer esta restricción es que, de lo contrario, la coincidencia de patrones no sería determinista, porque un término podría coincidir con un patrón en Más de una manera. Por ejemplo, el término (true, [9,7,4], "hello", 7)
coincide con el patrón C[7]
de dos maneras, suponiendo que se C[.]
extienda sobre tales contextos.
(Prefiero escribir esto como un comentario, pero no puedo en este momento).
Corríjame si me equivoco, pero por lo que entiendo, una diferencia más entre la coincidencia de patrones y la reescritura de términos, aparte de lo que Martin Berger dijo en su excelente respuesta , es que las reglas de coincidencia de patrones vienen con un orden fijo (en implementaciones como Haskell), mientras que con las reglas de reescritura de términos esto no es necesariamente el caso. Esta característica, como cabría esperar, puede marcar una gran diferencia al considerar el comportamiento (en particular, la terminación) de las reglas (consulte "Una introducción suave a Haskell, Versión 98", sección 4.2 , por ejemplo, o simplemente el factorial ejemplo en "Learn you a Haskell" ).
Las personas más conocedoras de la teoría de la reescritura tendrían más que decir al respecto (por ejemplo, ¿cómo se ajusta exactamente la mecanografía a tal comparación?), Pero, me parece justo estar de acuerdo con Martin Berger, en ese término se puede ver que la reescritura abarca coincidencia de patrones (al menos ya que esto se implementa en lenguajes como Haskell), en la medida en que ambos pueden ser vistos (de manera bastante seca) como dispositivos que simplemente emplean reglas relacionadas con términos.
fuente