5.3    Secuencia en expresiones no aritméticas.

Además del orden de ejecución en la evaluación de expresiones aritméticas, en los lenguajes están presentes otros formatos de expresiones.

Una operación crucial en lenguajes como SNOBOL4, Prolog y ML es el pattern matching. En SNOBOL4 la operación tiene éxito cuando un patrón predefinido parea con un substring en una variable, el cual es substituido por otro string. Por ejemplo:

La gramática siguiente reconoce palíndromos de longitud impar sobre el alfabeto 0 y 1:

El reconocimiento de la cadena válida 00100 tiene lugar así:

A₁ coincide o parea con el centro 1
A₂ coincide o parea con 0A₁0
A₃ coincide o parea con 0A₂0

De esta forma se crea el árbol de derivación de 00100:

En este ejemplo los patrones serán los lados derechos de las producciones de la gramática. La operación de pattern matching consiste entonces en parear un patrón con un substring del string que se está analizando y substituirlo por a_i.

Mientras que SNOBOL4 emplea el reemplazo de substrings en su pattern matching, Prolog utiliza el concepto de una relación como un conjunto de n-tuplas como mecanismo de concordancia. Mediante la especificación de casos conocidos de estas relaciones (instancias o hechos), es posible deducir otros casos. Por ejemplo, se puede considerar la relación Padre de con las siguientes instancias:

Padre de (Juan,María)
Padre de (Susana,María)
Padre de (Carlos,Juan)
Padre de (Ana,Juan)

Para encontrar al padre de María se escribe la relación Padre de (X,María) y Prolog tratará de asignar un valor a X a partir del contenido del conjunto conocido de hechos de su base de datos e inferirá que X puede ser Juan o Susana.

El poder de Prolog está en la construcción de relaciones que se pueden inferir de manera lógica a partir de un conjunto conocido de hechos. Por ejemplo, de nuestro conjunto conocido:

Abuelo de (X,Y) <- Padre de (X,Z), Padre de (Z,Y) luego Abuelo de (X,María) entregará Carlos o Ana.