Prolog Language
Listas de diferencia
Buscar..
Introducción
Las listas de diferencias en Prolog denotan el concepto de conocer la estructura de una lista hasta cierto punto . El resto de la lista puede dejarse sin consolidar hasta la evaluación completa de un predicado. Una lista donde se desconoce su final se conoce como una lista abierta , terminada por un agujero . Esta técnica es especialmente útil para validar sintaxis complejas o gramáticas.
Las conocidas gramáticas de cláusula definida (DCG) utilizan listas de diferencias para operar bajo el capó.
Uso básico
Consideremos el predicado sumDif/2 , verificado si la estructura de una lista coincide con varias restricciones. El primer término representa la lista para analizar y el segundo término otra lista que contiene la parte de la primera lista que desconocemos para nuestras restricciones.
Para la demostración, sumDif/2 reconoce una expresión aritmética para sumar n enteros.
sumDif([X, +|OpenList], Hole) :-
integer(X),
sumDif(OpenList, Hole).
Sabemos que el primer elemento de la lista para validar es un entero, aquí ilustrado con X , seguido del símbolo de la suma ( + ). El resto de la lista que aún debe procesarse más adelante ( OpenList ) se deja sin validar en ese nivel. Hole representa la parte de la lista que no necesitamos validar.
Demos otra definición del predicado sumDif/2 para completar la validación de la expresión aritmética:
sumDif([X|Hole], Hole) :-
integer(X).
Esperamos un entero llamado X directamente al inicio de la lista abierta. Curiosamente, el resto del Hole de la lista se desconoce y ese es el propósito de las listas de diferencias: la estructura de la lista se conoce hasta cierto punto.
Finalmente, la pieza faltante viene cuando se evalúa una lista:
?- sumDif([1,+,2,+,3], []).
true
Esto es cuando se usa el predicado que menciona el final de la lista, aquí [] , indica que la lista no contiene elementos adicionales.
Evaluar una expresión aritmética.
Definamos una gramática que nos permita realizar adiciones, multiplicaciones con el uso de paréntesis. Para agregar más valor a este ejemplo, vamos a calcular el resultado de la expresión aritmética. Resumen de la gramática:
expresión → veces
expresión → veces '+' expresión
tiempos → elemento
tiempos → elemento '*' veces
elemento → "entero"
elemento → '(' expresión ')'
Todos los predicados tienen una aridad de 3, porque necesitan abrir la lista, el agujero y el valor de la expresión aritmética.
expression(Value, OpenList, FinalHole) :-
times(Value, OpenList, FinalHole).
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
times(Value, OpenList, FinalHole) :-
element(Value, OpenList, FinalHole).
times(TimesValue, OpenList, FinalHole) :-
element(Value1, OpenList, ['*'|Hole1]),
times(Value2, Hole1, FinalHole),
TimesValue is Value1 * Value2.
element(Value, [Value|FinalHole], FinalHole) :-
integer(Value).
element(Value, ['('|OpenList], FinalHole) :-
expression(Value, OpenList, [')'|FinalHole]).
Para explicar adecuadamente el principio de los agujeros y cómo se calcula el valor, tomemos la segunda expression cláusula:
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
La lista abierta es denotada por el predicado OpenList . El primer elemento a validar es lo que viene antes del símbolo de adición ( + ) . Cuando se valida el primer elemento, es seguido directamente por el símbolo de adición y por la continuación de la lista, llamada Hole1 . Sabemos que Hole1 es el siguiente elemento para validar y puede ser otra expression , por Hole1 tanto, Hole1 es el término dado a la expression predicado.
El valor siempre está representado en el primer término. En esta cláusula, se define por la suma del Value1 (todo antes del símbolo de adición) y el Value2 (todo después del símbolo de suma).
Finalmente, la expresión puede ser evaluada.
?- expression(V, [1,+,3,*,'(',5,+,5,')'], []).
V = 31