Prolog

Jaime Sánchez Hernández
Departamento de Sistemas Informáticos y Computación
Universidad Complutense de Madrid

email: jaime@sip.ucm.es

PROLOG

1 / 101

Sintaxis de Prolog
Un programa Prolog es un conjunto de cl´usulas de Hernández
a
Jaime Sánchez Horn (hechos
Departamento de Sistemas Informáticos y Computación
y reglas) donde:
Universidad Complutense de Madrid
email:jaime@sip.ucm.es
Todas las cla´sulas acaban con .
u
El s´
ımbolo ← se escribe como :- que se lee como si
(condicional). En los hechos no es necesario (basta poner el
´tomo y .)
a
Los nombres de predicado y funci´n siguen las pautas
o
habituales de los identificadores pero comienzan con
min´scula .
u
Los nombres de variable tambi´n siguen esas pautas, pero
e
comienzan por may´scula .
u
Los´tomos en el cuerpo de las reglas se separan mediante
a
comas , que se leen como y.
Ejecutar un programa no tiene sentido como tal (en principio).
Lo que se hace es plantear objetivos a resolver.
A partir de ahora utilizaremos esta notaci´n.
o
2 / 101

Funci´n de selecci´n y b´squeda
o
o
u
Jaime Sánchez Hernández
Departamento de Sistemas Informáticos y Computación
UniversidadComplutense de Madrid

La funci´n de selecci´n devuelve siempre el primer ´tomo del
o
o
a
objetivo empezando por la izquierda. email: jaime@sip.ucm.es
Para resolver un objetivo G el algoritmo elemental ser´
ıa:
mientras G no sea cierto
elegir una (variante de una) regla de P aplicable a G
reducir G por resoluci´n
o

Pero en un paso de reducci´n pueden existir varias (variantes
o
de)cla´sulas aplicables a G . Por ello surgue el concepto de
u
´rbol de b´squeda: Prolog ensaya las distintas cla´sulas
a
u
u
aplicables a G de manera secuencial y cada uno de estos
ensayos da lugar a una rama de dicho ´rbol.
a
3 / 101

´
Arboles de b´squeda
u
Dado un programa Prolog y un objetivo G (asumimos selecci´n del
Jaime Sánchez Hernández o
Departamento de Sistemas Informáticos yComputación
primer ´tomo de la izquierda), el ´rbol de b´squeda paraMadrides un
a
a
u
G
Universidad Complutense de
email: jaime@sip.ucm.es
´rbol que:
a
tiene G como ra´
ız
para cada cl´usula C de P aplicable a G existe una rama
a
correspondiente al ´rbol de b´squeda del SLD-resolvente de G
a
u
y (una variante cualquiera de) C . Adem´s etiquetaremos las
a
ramas con la sustituci´ncorrespondiente y la cla´sula C
o
u
aplicada.
En otras palabras: un ´rbol de b´squeda es un ´rbol con objetivos
a
u
a
en los nodos y cuyas ramas representan los posibles c´mputos, i.e.,
o
las posibles cla´sulas a aplicar.
u
Nota: no confundir ´rbol de b´squeda con los ´rboles de derivaci´n SLD que hemos
a
u
a
o
visto anteriormente (los ´rboles de resoluci´n corresponden solo a unarama de los
a
o
´rboles de b´squeda).
a
u
4 / 101

Ejemplo
Jaime Sánchez Hernández
Departamento de Sistemas Informáticos y Computación
Universidad Complutense de Madrid

Trabajemos con un grafo m´s peque˜o y el correspondiente
a
n
email: jaime@sip.ucm.es
programa Prolog:
a

c

A1
A2
A3
A4

b

d

:
:
:
:

arco(a,b).
arco(a,c).
arco(a,d).
arco(c,d).

C1 :camino(X,X).
C2 : camino(X,Y):- arco(X,Z), camino(Z,Y).

A continuaci´n presentamos el ´rbol de b´squeda para el objetivo
o
a
u
camino(X,d).

5 / 101

Ejemplo (cont.)
Jaime Sánchez Hernández

camino(X,d)

Departamento de Sistemas Informáticos y Computación
C2 , [X1 /X, Y1 /d]
Universidad Complutense de Madrid

C1 , [X/d, X1 /d]

A1 ,[X/a,Z1 /b]

[X/a,Z1 /c]

camino(b,d)

A2A3

camino(c,d)

camino(d,d)

arco(b,Z2 ),camino(Z2 ,d)

arco(c,Z2 ),camino(Z2 ,d)

fallo

camino(d,d)
C1

A4 ,[X/c,Z1 /d]

[X/a,Z1 /d]

C1

´xito
e

email: jaime@sip.ucm.es

arco(X,Z1 ), camino(Z1 ,d)

´xito
e

´xito
e

camino(d,d)

C2
arco(d,Z3 ),camino(Z3 ,d)

fallo

C1
´xito
e

C2
arco(d,Z3 ),camino(Z3 ,d)

fallo

C2
arco(d,Z3...