pattern matching - ¿Diferencias entre la coincidencia de patrones y la unificación?

pattern-matching unification

Question

Pensé que entendía cómo la comparación de patrones como la que se encuentra en Scala y Haskell es diferente de la unificación que se encuentra en Prolog, pero mi comprensión errónea de Prolog es grande ¿Cuáles son algunos problemas simples que puede resolver uno que no puede ser resuelto por el otro? Gracias

Answer 1

Creo que es útil formalizar los conceptos, en lugar de estudiar un lenguaje específico. La coincidencia y la unificación son conceptos fundamentales que se utilizan en más contextos que la comparación de patrones y el prólogo.

• Un término s coincide con t, si hay una sustitución phi tal que phi (s) = t
• Un término s se unifica con un término t, si hay una sustitución tal que phi (s) = phi (t)

Para dar un ejemplo, inspeccionamos los términos s = f (Y, a) yt = f (a, X) donde X, Y son variables y a es una constante. s no coincide con t, porque no podemos cuantificar universalmente la constante a. Sin embargo, hay un unificador para s y t: phi = {X / a, Y / a}

Answer 2

En Prolog, puedes añadir [3] a [1,2] así:

?- append([1,2], [3], Z).
Z = [1, 2, 3].

Lo bueno de la unificación es que puede usar el mismo código (la definición interna de ''agregar''), pero en su lugar, busque el segundo argumento necesario para obtener el resultado del primer argumento:

?- append([1,2], Y, [1,2,3]).
Y = [3].

En lugar de codificar escribiendo "haz esto, luego hazlo", codificas en Prolog diciendo lo que sabes. Prolog trata los hechos que le das como ecuaciones . La unificación le permite tomar esas ecuaciones y resolver las variables de las que aún no conoce los valores, ya sea en el lado derecho o en el izquierdo.

Así, por ejemplo, puedes escribir un planificador en Prolog, y puedes ejecutarlo "adelante", dándole un plan y haciendo que prediga sus resultados; o puede ejecutarlo "hacia atrás", dándole un conjunto de resultados y haciendo que construya un plan. Incluso puede ejecutarlo de dos maneras al mismo tiempo (si fue cuidadoso en su codificación), especificando un conjunto de objetivos y un conjunto de restricciones en el plan, de manera que pueda decir "Encuentre un plan para llegar al trabajo que no implique tomando el metro ".

Answer 3

Lo siguiente en Scala fallaría en compilarse, ya que es el primer caso en que la rama intenta declarar la variable x dos veces.

(1, 1) match{
   case (x, x) => println("equals")
   case _      => println("not equals")
}

Si Scala usara la unificación en lugar de la coincidencia de patrones, esto tendría éxito e imprimiría "igual a" mientras que

(1, 2) match{
   case (x, x) => println("equals")
   case _      => println("not equals")
}

Imprimiría "no es igual a". Esto se debe a que la unificación fallaría al intentar vincular la variable x a 1 y 2 .

Answer 4

Declaración simple: la coincidencia de patrones es unidireccional, la unificación es bidireccional. Es decir, en Prolog, el lado derecho (el que se compara) puede incluir variables no unidas. Por ejemplo, si tiene dos variables no vinculadas X e Y , esto funcionará bien:

X = Y,
X = 5,
%% Y = 5 now as well

En Erlang (que usa la coincidencia de patrones con sintaxis cerca de Prolog), la línea X = Y producirá un error: la variable ''Y'' is unbound . Tenga en cuenta que X no está enlazado está bien: se supone que debe coincidir con el patrón.

Esto puede ser útil cuando se quiere tratar con valores parcialmente definidos. Un muy buen ejemplo son las listas de diferencias .

Esto es también lo que permite el uso del predicado Prolog en múltiples modos. Por ejemplo, en Scala / Haskell / Erlang, si desea 1) encontrar A ++ B , 2) resolver la ecuación A ++ X == B , o 3) resolver la ecuación X ++ A == B para las listas dadas A y B , necesitas escribir 3 funciones separadas; en Prolog, todos estos trabajos (¡y más!) se realizan por un predicado.