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
EXPRESIONES ARITMÉTICAS
En esta clase trabajaremos con expresiones aritméticas en forma simbólica, lo cual es natural para PROLOG. Primero escribimos un programa para evaluar expresiones aritméticas y entonces desarrollar un simple compilador el cual traduce una expresión aritmética hacia un código lineal para un mecanismo de pila.
EVALUACIÓN
Podemos fácilmente evaluar la expresión aritmética usando el evaluador incorporado de PROLOG.
eval_ingenua(Expr,Res) :- Res is Expr.
Sin embargo, para propósitos de éste tutorial preferimos el siguiente evaluador el cual atraviesa la estructura del término evaluado. Note, la descomposición natural del término a través de la unificación y las funciones incorporadas +,-,*. Para simplificar el problema, omitimos el operador división(/).
eval(A+B,CV) :- eval(A,AV),eval(B,BV),CV is AV+BV.
eval(A-B,CV) :- eval(A,AV),eval(B,BV),CV is AV-BV.
eval(A*B,CV) :- eval(A,AV),eval(B,BV),CV is AV*BV.
eval(Num,Num) :- numero(Num).
Ahora, podemos fácilmente extender el programa de arriba para permitir "variables" en el término evaluado. Esas variables son representadas por átomos de PROLOG como a, b o c, así ellos no corresponden a variables PROLOG. Por supuesto, tenemos que notificar los valores de las variables al programa evaluador. Así, la lista de pares variable / valor también como la expresión evaluada es pasada al evaluador. Para obtener el valor de la variable dada utilizamos la función miembro que es definido en una de las clases anteriores.
eval_v(A+B,CV,Vars) :- eval_v(A,AV,Vars),eval_v(B,BV,Vars),CV is AV+BV.
eval_v(A-B,CV,Vars) :- eval_v(A,AV,Vars),eval_v(B,BV,Vars),CV is AV-BV.
eval_v(A*B,CV,Vars) :- eval_v(A,AV,Vars),eval_v(B,BV,Vars),CV is AV*BV.
eval_v(Num,Num,Vars) :- numero(Num).
eval_v(Var,Valor,Vars) :- atomo(Var),miembro(Var/Valor,Vars).
Intenta ?-eval_v(2*a+b,Val,[a/1,b/5]) para probar el programa de arriba.
COMPILACIÓN
La evaluación de expresiones aritméticas puede ser fácilmente extendida hacia generar código lineal para algún mecanismo de pila abstracto. Usamos un mecanismo de pila con las siguientes instrucciones:
sacar(X)- coloca un elemento X en el tope de la pila
meter(X)- remueve el elemento X del tope de la pila
sumar,restar,(*)times(X,Y,Z)- calcula el valor correspondiente de Z a partir de los números X,Y
obt_valor(X,V)- obtiene el valor de la variable X desde memoria
col_valor(X,V)- coloca el valor de la variable X en memoria
X,Y,Z,V son asumidos como registros permanentes del mecanismo de pila.
Notar, que usamos el acumulador para recoger el código y éste es realmente generado desde el final al comienzo.
expr_gen(A+B,InCode,OutCode) :-
expr_gen(B,[sacar(X),sacar(Y),sumar(X,Y,Z),meter(Z)|InCode],TempCode),
expr_gen(A,TempCode,OutCode).
expr_gen(A-B,InCode,OutCode) :-
expr_gen(B,[sacar(X),sacar(Y),restar(X,Y,Z),meter(Z)|InCode],TempCode),
expr_gen(A,TempCode,OutCode).
expr_gen(A*B,InCode,OutCode) :-
expr_gen(B,[sacar(X),sacar(Y),times(X,Y,Z),meter(Z)|InCode],TempCode),
expr_gen(A,TempCode,OutCode).
expr_gen(Num,InCode,[meter(Num)|InCode]) :- numero(Num).
expr_gen(Var,InCode,[obt_valor(Var,Valor),meter(Valor)|InCode]) :- atomo(Var).
Si podemos generar el código para evaluar expresiones es fácil adicionar un generador por asignación. El programa compilado es una lista de asignaciones entonces.
prog_gen([A=Expr|Rest],InCode,Code) :-
atomo(A),
prog_gen(Rest,InCode,TempCode),
expr_gen(Expr,[sacar(X),col_valor(A,X)|TempCode],Code).
prog_gen([],Code,Code).
Ahora, escribimos un interpretador de código máquina generado. El interpretador usa Pila para evaluar expresiones aritméticas y Memoria para recordar los valores de las variables. El código PROLOG del interpretador sigue naturalmente la semántica de las instrucciones usadas: sacar, meter, sumar, restar, times, obt_valor y col_valor.
eval_prog([meter(X)|Code],Pila,Memoria) :-
eval_prog(Code,[X|Pila],Memoria).
eval_prog([sacar(X)|Code],[X|Pila],Memoria) :-
eval_prog(Code,Pila,Memoria).
eval_prog([sumar(X,Y,Z)|Code],Pila,Memoria) :-
Z is X+Y,
eval_prog(Code,Pila,Memoria).
eval_prog([restar(X,Y,Z)|Code],Pila,Memoria) :-
Z is X-Y,
eval_prog(Code,Pila,Memoria).
eval_prog([times(X,Y,Z)|Code],Pila,Memoria) :-
Z is X*Y,
eval_prog(Code,Pila,Memoria).
eval_prog([obt_valor(X,Valor)|Code],Pila,Memoria) :-
miembro(X/Valor,Memoria),
eval_prog(Code,Pila,Memoria).
eval_prog([col_valor(X,Valor)|Code],Pila,Memoria) :-
col_valor(X,Valor,Memoria,NuevaMemoria)
eval_prog(Code,Pila,NuevaMemoria).
eval_prog([],Pila,Memoria) :-
imprimir_Memoria(Memoria).
El colocar el valor de la variable no es tan directo como obtener el valor de la variable usando miembro. Si la variable está en la memoria, su valor tiene que ser cambiado, sino un nuevo par variable / valor es agregado a la memoria.
col_valor(X,Valor,[X/_|T],[X/Valor|T]).
col_valor(X,Valor,[Y/V|T],[Y/V|NuevoT) :-
X\=Y,col_valor(X,Valor,T,NuevoT).
col_valor(X,Valor,[],[X/Valor]).
Finalmente, cuando el interpretador eval_prog encuentra el final del código el cual es indicado por la lista vacía, imprime los contenidos de la memoria, es decir, los valores de todas las variables las cuales son usadas en el programa.
imprimir_Memoria([X/Valor|T]) :-
write(X=Valor),nl,imprimir_Memoria(T).
imprimir_Memoria([]) :- nl.
Para encapsular el generador compilador /código y el evaluador interpretador/código, introducimos la siguiente cláusula.
ejecutar(Prog) :-
prog_gen(Prog,[],Code),
eval_prog(Code,[],[]).
Puedes intentar ?-ejecutar([a=5,b=a+2,a=3*a+b]) para probar el programa. Pero, si uno usa la variable con un valor indefinido, ejemplo, ?-ejecutar([a=b+2])? El programa falla. Mejorar el programa en una forma que imprima un mensaje notificando las variables indefinidas durante la interpretación o mejor, detectará las variables indefinidas durante la compilación.
OPTIMIZACIÓN
Mire el código generado por prog_gen. ¿Es posible optimizar el código en alguna forma? Por supuesto, es posible. Aquí está un ejemplo de tal optimizador trivial el cual remueve todos los pares sucesivos meter-sacar y unifica sus argumentos. Está claro que si un elemento es metido a una pila y otro elemento es sacado desde la misma pila entonces inmediatamente ambos elementos son iguales (por unificación).
optimizar([meter(X),sacar(Y)|T],OptCode) :-
X=Y,
optimizar(T,OptCode).
optimizar([H|T],[H|OptCode]) :-
optimizar(T,OptCode).
optimizar([],[]).
Ahora, insertamos el optimizador entre el generador y el ejecutor para obtener la ejecución del programa optimizado.
opt_ejecutar(Prog) :-
prog_gen(Prog,[],Code),
optimizar(Code,OptCode),
eval_prog(OptCode,[],[]).
¿Te gustó la aplicación presentada arriba? Si es así, puedes extenderlo a tu gusto desarrollando un compilador y ejecutor completo para un lenguaje de programación escogido. Por ejemplo, pensar en incorporar una construcción si-entonces-sino para el lenguaje de arriba.
PROLOG es un lenguaje de programación ideal para manejar datos simbólicos.