lenguajes logicos
DESCRIPTION
LENGUAJES LOGICOS. IMPLEMENTACION CALCULO DE PREDICADOS PROLOG. Intérpretes/Compiladores de Lenguajes Lógicos (PROLOG). Las diferencias de implementación de un lenguaje lógico son provocadas por El manejo del desconocido necesario para la implementación de la unificación. - PowerPoint PPT PresentationTRANSCRIPT
1
LENGUAJES LOGICOS
IMPLEMENTACION
CALCULO DE PREDICADOS
PROLOG
2
Intérpretes/Compiladores de Lenguajes Lógicos (PROLOG)
• Las diferencias de implementación de un lenguaje lógico son provocadas por– El manejo del desconocido necesario para
la implementación de la unificación.
– El no determinismo y su implementación mediante vuelta atrás (backtracking).
• Actualmente las implemetaciones de compiladores de PROLOG se basan en la máquina de Warren o variantes.
• Ejemplo de no determinismo
member(X,[X|L]).
member(X,[_|L]):-member(X,L).
member(Y,[1,2,3,4,5])?
Y=1,2,3,4,5
3
Ambito
La Máquina de Warren
TR: cabeza del trail
E: ámbito activo
B: punto de elección activo
B0:
H:Final del Heap
HB:Final del Heap de la última
bifurcación no determinista
S: ayuda a la unificación
P: contador de programa
CP: continuación
Areade código
Heap
Trail
PDL
CPP
SHB
H
B0B
E
TR
Punto de elección
Pila
4
Máquina de Warren (II)
• La máquina tiene un conjunto de registros Xn (variables globales para uso temporal
• Yn son las variables que se guardan en el ámbito
• An son los argumentos que se guardan al final de la pila.
• Heap– <ref,dirección> Es una referencia a donde
se encuentra el valor
– <str,dirección> es un apuntador a un nodo
– functor/n: es la cabecera de un functor con n argumentos. Ej. p(a,b) : p/2
– átomo/0: es un átomo o functor con cero argumentos.
• predicado/n: especifica un predicado con n argumentos
5
Representación de los Functors
• Representar el functor:
p(Z,h(Z,W),f(W)).
• Instrucciones de
creaciónput_structure f/n,Xi
Heap[H]=<STR,H+1>
Heap[H+1]=f/n
Xi=Heap[H]
H=H+2
set_variable Xi
Heap[H]=<REF,H>
Xi=Heap[H]
H=H+1
set_value Xi
Heap[H]=Xi
H=H+1
<STR,1>h/2
<REF,2><REF,3><STR,5>
f/1<REF,3><STR,8>
p/3<REF,2><STR,1><STR,5>11
109876543210
6
Celdas en el Heap
• Celda variable– <REF, k> k es la dirección donde se guarda
el “valor”
• Celda estructura– <STR, k> k es la dirección donde se guarda
el functor (nodo)
• Celda functor– nombre/n nombre del functor y número de
elementos
– Los elementos le siguen inmediatamente
• Celda átomo– nombre/0 nombre del atomo y número de
elementos 0
• Desconocido– <REF, k> k es la dirección de el mismo
7
Código de creación de Functores
• Crear el functor:
p(Z,h(Z,W),f(W)).
• Códigoput_structure h/2,X3
set_variable X2
set_variable X5
put_structure f/1,X4
set_value X5
put_structure p/3,X1
set_value X2
set_value X3
set_value X4
• Asignación de los registrosX1=p(X2,X3,X4)X2=ZX3=h(X2,X5)X4=f(X5)X5=W
<STR,1>h/2
<REF,2><REF,3><STR,5>
f/1<REF,3><STR,8>
p/3<REF,2><STR,1><STR,5>11
109876543210
8
Instrucciones de Unificación (I)
get_structure f/n,Xiaddr=deref(Xi)
switch (STORE[addr]) {
case <REF,_>:
HEAP[H]=<STR,H+1>
HEAP[H+1]=f/n;
bind(addr,H)
H=H+2;
mode=WRITE;
break;
case <STR,a>:
if (HEAP[a]=f/n) {
S=a+1;
mode=READ;
}
else fail=True;
break;
default: fail=true
}
unify_variable Xi
unify_value Xi
9
Instrucciones de Unificación (II)
unify_variable Xiswitch (mode) {
case READ:
Xi=HEAP[S];
break;
case WRITE:
HEAP[H]=<REF,H>;
Xi=HEAP[H]
H=H+1;
break;
}
S=S+1;
unify_value Xiswitch (mode) {
case READ:
unify(Xi,S);
break;
case WRITE:
HEAP[H]=Xi;
H=H+1;
}
S=S+1;
10
Unificación
void unify(a1,a2)
{
push(a1,PDL);push(a2,PDL);
fail=false;
while (!empty(PDL) && !fail) {
d1=deref(pop(PDL)); d2=deref(pop(PDL));
if (d1!=d2) {
<t1,v1>=STORE[d1];<t2,v2>=STORE[d2];
if (t1==REF || t2==REF) bind(d1,d2)
else {
f1/n1=STORE[v1];f2/n2=STORE[v2];
if (f1==f2 && n1==n2) {
for (i=1;i<=n1;++i) {
push(v1+i,PDL);
push(v2+i,PDL);
}
} else fail=true;
}
}
}
}
11
Código de Unificación Functores
• Unificar el functor:p(Z,h(Z,W),f(W)).
• Códigoget_structure p/3,X1unify_variable X2unify_variable X3unify_variable X4get_structure h/2,X3unify_value X2unify_variable X5get_structure f/1,X4unify_value X5
• Asignación de los registrosX1=p(X2,X3,X4) Valor a unificar con p(…)X2=ZX3=h(X2,X5)X4=f(X5)X5=W
12
Instrucciones de Llamada a un Predicado
• put_variable Xn,AiHeap[H]=<Ref,H>
Xn=Heap[H]
Ai=Heap[H]
H=H+1
• put_value Xn,Ai Ai=Xn
• get_value Xn,Ai unify(Xn,Ai)
• put_structure f/n,AiHeap[H]=f/n
Ai=<STR,H>
H=H+1
• Call p/nCP=P+instruction_size(P)
P=@(p/n) (dirección del código del predicado p con n argumentos)
• ProceedP=CP
13
Llamada a un Predicado
• Fuente: p(Z,h(Z,W),f(W))?• Código
put_variable X4,A1
put_structure h/2,A2
set_value X4
set_variable X5
put_structure f/1,A3
set_value X5
call p/3
• ArgumentosA1=Z
A2=h(Z,W)
A3=f(W)
14
Código de un Predicado
• Hecho: p(f(X),h(Y,f(a)),Y).• Código:
get_structure f/1,A1
unify_variable X4
get_structure h/2,A2
unify_variable X5
unify_variable X6
get_value X5,A3
get_structure f/1,X6
unify_variable X7
get_structure a/0,X7
proceed
• ArgumentosA1=f(X)
A2=h(Y,f(a))
A3=Y
15
Código de una Regla
• P0(…):-p1(…),…,pn(…).
• Estructura del códigoallocate N
leer argumentos de p0
poner los argumentos de p1
call p1
…
poner los argumentos de pn
call pn
deallocate
• Al llamar a otros predicados se pierden los valores de Xi y para solucionarlo se guardan los valores en los registros permanentes Yi– allocate N reserva N registros Yi
– deallocate los “libera”
16
CE (ámbito de continuación)
n (número de variables permanentes)Y1Y2...Yn
CP (apuntador a la continuación)E
Ámbito
• Lo crea la instrucción allocate y lo destruye deallocate
• Contiene las variables necesarias para ejecutar una regla.
• Allocateif (E>B) newE=E+STACK[E+2 ] +3
else newE=B+STACK[B] +7
STACK[newE]=E;
STACK[newE+1]=CP;
STACK[newE+2]=N;
E=newE;
P=P+instruction_size(P);
• deallocateP=STACK[E+1];
E=STACK[E];
17
Código de una Regla
• P(X,Y):-q(X,Z),r(Z,Y).P/2: allocate 2
get_variable X3, A1
get_variable Y1, A2
put_value X3, A1
put_variable Y2, A2
call q/2
put_value Y2, A1
put_value Y1, A2
call r/2
deallocate
18
Implementación de las Bifurcaciones no Deterministas
• La implementación del no determinismo se base en las instrucciones:– try_me_else siguiente regla
• Crea un bloque de activación de un punto de elección.
• En caso que se produzca un fallo transfiere la ejecución a la regla siguiente.
– retry_me_else siguiente regla• Se ejecuta después de una vuelta atrás.
• Deshace las instanciaciones y cambios de estado producidos después de ejecutar try_me_else o retry_me_else
• En caso que se produzca un fallo transfiere la ejecución a la regla siguiente
– trust_me• Se ejecuta después de una vuelta atrás.
• Deshace las instanciaciones y cambios de estado producidos después de ejecutar try_me_else o retry_me_else
• Elimina el bloque de activación de un punto de elección.
19
Ejemplo de Bifurcación no Determinista
• Fuentep(X,a).
p(b,X).
p(X,Y):-p(X,a),p(b,Y).
• Códigotry_me_else L1
get_variable X3,A1
get_structure a/0,A2
proceed
L1: retry_me_else L2
get_structure b/0,A1
get_variable X3,A2
proceed
L2: trust_me
allocate 1
get_variable X3,A1
put_value Y1,A1
put_structure a/0,A2
call p/2
deallocate
20
Punto de Elección
• Lo crea la instrucción try_me_else y lo destruye trust_me
• Contiene los registros de la máquina para poder recuperar el estado en caso de vuelta atrás.
n (número de argumentos)A1A2…An
CE (ámbito de continuación)CP (apuntador a la continuación)
B (anterior punto de elección)BP (siguiente regla)
TR (apuntador al camino)H (apuntador al heap)
B