UNIVERSIDAD DE LOS ANDES
COORDINACION GENERAL DE ESTUDIOS INTERACTIVOS A DISTANCIA
MERIDA - VENEZUELA
Curso de Lógica y Matemática
Postgrado en Modelado y Simulación de Sistemas
MANUAL de PROLOG - BRATKO
ESTRUCTURAS DE DATOS DE PROLOG
En este punto podemos hablar más formalmente de las estructuras de datos (suponiendo que las secciones anteriores han sido cubiertas). El término (term) es la estructura de datos básica en PROLOG. Es decir, todas las cosas incluyendo un programa y los datos puede ser expresados en forma de término. Hay cuatro tipos básicos de términos en PROLOG: variables, términos compuestos, átomos y números. El siguiente diagrama muestra la correlación entre ellos también como ejemplos de los términos correspondientes:
término
|-- var {X , Y}
|-- nonvar {a,1,f(a),f(X)}
|-- compuesto {f(a),f(X)}
|-- atómico {a, 1}
|-- átomo {a}
|-- número {1}
Es posible usar los predicados var, nonvar, compuesto, atómico, átomo y numero para probar el tipo del término dado (ver copiar_term abajo). PROLOG también provee predicados predefinidos para accesar la estructura de términos nonvar y también para construir términos.
arg(N,Term,Arg)
- obtiene el argumento N th del término (get(2,f(a,b,c),X) -> X=b)
- coloca el argumento N th del término (get(2,f(X,Y,Z),b) -> f(X,b,Z))
functor(Term,Functor,NumberOfArgs)
- obtiene el nombre de la función y el número de argumentos desde el término (functor(f(a,b),F,N) -> F=f,N=2)
- construye el término con la función dada y el número de argumentos libres (functor(F,f,2) -> F=f(_,_))
=..
- descompone la estructura del término hacia la lista (f(a,b)=..X -> X=[f,a,b])
- construye el término desde la lista dada (T=..[f,a,X] -> T=f(a,X))
name(Text,List)
- convierte el nombre hacia la lista de códigos (name(abc,Y) -> Y=[97,98,99])
- construye el nombre desde la lista de códigos (name(X,[97,98,99]) -> X=abc)
Si alguien necesita copiar un término (copiar tiene la misma estructura como el término original pero introduce nuevas variables), es posible usar el predicado copiar_term/2 el cual está incorporado en la mayoría de los sistemas PROLOG. Sin embargo, es directo escribir un código de copiar_term en PROLOG usando los predicados mencionados arriba.
copiar_term(A,B) :- cp(A,[],B,_).
cp(A,Vars,A,Vars) :-
atómico(A).
cp(V,Vars,NV,NVars) :-
var(V),registrar_var(V,Vars,NV,NVars).
cp(Term,Vars,NTerm,NVars) :-
compuesto(Term),
Term=..[F|Args], % descomponer el término
cp_args(Args,Vars,NArgs,NVars),
NTerm=..[F|NArgs]. % construye copia del término
cp_args([H|T],Vars,[NH|NT],NVars) :-
cp(H,Vars,NH,SVars),
cp_args(T,SVars,NT,NVars).
cp_args([],Vars,[],Vars).
Durante el copiado alguien tiene que recordar las copias de variables las cuales pueden ser usadas adicionalmente durante el copiado. Por lo tanto, el registro de las copias de las variables es mantenido.
registrar_var(V,[X/H|T],N,[X/H|NT]) :-
V\==X, % variables diferentes
registrar_var(V,T,N,NT).
registrar_var(V,[X/H|T],H,[X/H|T]) :-
V==X. % variables iguales
registrar_var(V,[],N,[V/N]).
Aquí está un ejemplo que clarifica la noción de copiar un término:
f(X,g(X)) es copia de f(Y,g(Y)) pero no de f(U,g(V)).
UNIFICACIÓN
Unificación es un mecanismo fundamental en todos los lenguajes de programación lógica y crucial en el PROLOG. Con unificación se trata de encontrar la mayoría de sustituciones generales de variables en dos términos tal que después de aplicar ésta sustitución a ambos términos, los términos lleguen a ser iguales. Para unificar los términos A y B, uno puede fácilmente invocar la unificación incorporada A=B. Tratar de unificar términos diferentes para ver lo que la noción de "unificación" realmente significa. Otra vez, es directo escribir código PROLOG de unificación (usamos '=' para probar la igualdad de dos términos atómicos o para unificar la variable con el término solamente).
unificar(A,B) :-
atómico(A),atómico(B),A=B.
unificar(A,B) :-
var(A),A=B. % sin occurs check
unificar(A,B) :-
nonvar(A),var(B),A=B. % sin occurs check
unificar(A,B) :-
compuesto(A),compuesto(B),
A=..[F|ArgsA],B=..[F|ArgsB],
unificar_args(ArgsA,ArgsB).
unificar_args([A|TA],[B|TB]) :-
unificar(A,B),
unificar_args(TA,TB).
unificar_args([],[]).
¿Averiguastes lo que significa "chequeo de ocurrencia"? OK, intenta unificar los siguientes términos X y f(X). ¿Qué sucede? La mayoría de los sistemas PROLOG llenarán la memoria completa ya que tratarán de construir el término infinito f(f(f(...))) el cual debería ser el resultado de la unificación. Tales sistemas PROLOG no incorporan chequeo de ocurrencia (occurs check) debido a su consumo de tiempo. El occurs check comprueba la ocurrencia de la variable X en el término T (el cual no es una variable) durante la unificación de X y T. Pero, en general, hacer esto es difícil y consume mucho tiempo de procesamiento.
OPERADORES
Escribir términos en la forma funcion(arg1,arg2,...) no es frecuentemente apropiado desde el punto de vista humano. Sólo compara las siguientes dos transcripciones de la misma cláusula PROLOG:
p(X,Z) :- q(X,Y),r(Y,Z),s(Z).
' :- '(p(X,Z),(','(q(X,Y),','(r(Y,Z),s(Z))))).
¿Cuál prefieres?
Para simplificar la entrada de términos, PROLOG introduce los operadores para permitir el "azúcar sintáctico", es decir, una forma más natural de escribir términos. Los Operadores son usados con términos binarios y unarios solamente. Ellos permiten colocar la localización de la función (prefijo, infijo, posfijo), la característica asociativa y, finalmente, la prioridad entre operadores.
op(Prioridad, Apariencia, Nombre)
| |
| -- xfy, yfx, xfx, fx, fy, xf, yf
-- El número más alto tiene la prioridad más baja
En lugar de explicar el significado de la definición de arriba, mira el siguiente ejemplo.
op(400,yfx,'*'). % a*b*c significa ((a*b)*c)
op(500,yfx,'+').
op(500,yfx,'-'). % cuidado a-b-c significa ((a-b)-c)
op(700,xfx,'=') % no es posible escribir a=b=c
op(900,fy,not). % uno puede escribir not not a
% significa not(not(a))
not 1=2+3+4*5 es equivalente a:
not(1=((2+3)+(4*5)))
not('='(1,'+'('+'(2,3),'*'(4,5)))).
Nota que los números indicando prioridad pueden ser diferentes en diversas implementaciones de PROLOG ( Los números en el ejemplo de arriba son tomados desde el PROLOG abierto para Macintosh).
Importante!
La definición de operador no es un nuevo programa para
operador sino la "llamada" del objetivo op. Así,
si tu quieres definir un operador en el programa, debes escribir
:- op(400,yfx,'*').
Los Términos son la base de PROLOG.