El procesador de Prolog está en todo momento tratando de satisfacer algún objetivo. Un «objetivo» es un predicado, y «satisfacerse» es lo mismo que decir «el predicado es verdadero» . Por empezar con un ejemplo trivial, supongamos que sólo hay dos hechos:
H2: blanco(leche).
Si se hace la consulta:
?- blanco(leche).
|
el objetivo inicial es «blanco(leche)» . El procesador busca en las definiciones (hechos y reglas; en este caso, sólo los dos hechos) «de arriba abajo» ; H1 no le sirve, pero sí H2, que coincide exactamente con la consulta. Entonces, el objetivo se satisface, y el procesador responde «YES» . Sin embargo, con la consulta «?- blanco(carbón)» (o con cualquier argumento que no sea «nieve» ni «leche» ) el procesador no encuentra ningún modo de satisfacer al objetivo, y responde «NO» . En el primer caso se dice que la búsqueda tiene éxito, y en el segundo, que fracasa.
Si el objetivo contiene variables, entonces puede haber varias maneras de satisfacerlo. Así, ante la consulta:
?- blanco(X).
|
el procesador encuentra, al comparar con H1, que se satisface si X toma el valor «nieve» , y después, comparando con H2, ve que también se satisface para X=leche, y, en consecuencia, da las dos respuestas (dos éxitos).
Pasemos a un ejemplo un poco más complicado, el de los «jefes» y «superiores» del Apartado A.2. Ante la consulta (objetivo inicial):
?- jefe(a2,b3).
|
el procesador explora (siempre «de arriba abajo» ), y al llegar a H4 tiene éxito y responde «YES» . Pero supongamos que ese hecho (H4) no figurase declarado. En tal caso, llegaría al final y fracasaría, respondiendo «NO» . Por otra parte, si la consulta contiene variables, puede satisfacerse de varias maneras. La consulta:
?- jefe(a2,X).
|
se satisface primero por H3 (para X=a3), luego por H4 (para X=b3) y finalmente por H5 (para X=c3), y el procesador da esas tres respuestas. Sin embargo, esta otra:
?- jefe(X,a3).
|
sólo se satisface, con H3, para X=a2.
Hasta aquí sólo hemos considerado el caso de que la consulta incluya un objetivo, pero también puede ser de la forma:
?- jefe(a1,a2),jefe(a2,a3).
|
Ahora el objetivo inicial consta de dos subobjetivos. El procesador tratará de satisfacer al primero, y, si tiene éxito, pasará al segundo. El primero se satisface por H1, por lo que lo quita de la lista de subobjetivos pendientes y empieza con el segundo (siempre desde H1 hacia abajo). Como H3 lo satisface, el objetivo inicial (conjunción de los dos subobjetivos) tiene éxito (respuesta: «YES» ).
Consideremos la consulta:
?- jefe(a1,X),jefe(X,d3).
|
(«¿quién es el individuo, si lo hay, que, siendo subordinado de a1, es, a su vez, jefe de d3?» ). Como antes, el procesador comenzará tratando de satisfacer al primer subobjetivo, «jefe(a1,X)» . Y encuentra una primera posibilidad con H1, para X=a2. Pasa entonces a ver si se satisface el segundo subobjetivo, pero tiene que ser para X=a2, es decir, en este momento trata de satisfacer «jefe(a2,d3)» . Tras explorar todos los hechos y todas las reglas no encuentra ninguna cabeza que diga tal cosa. Por tanto, fracasa. Pero esto no quiere decir que el objetivo inicial haya fracasado; simplemente, que X=a2 no sirve. Por tanto, retrocede al punto en el cual había hecho la hipótesis X=a2, y busca otra manera de satisfacer a «jefe(a1,X)» . Como ya se ha visto que con H1 se fracasa, sigue adelante, y encuentra otra posibilidad con H2 (X=b2). Entonces el segundo subobjetivo se convierte en «jefe(b2,c3)» . Empieza desde el principio (desde H1) y ve que se satisface al llegar a H6. En este momento, la búsqueda para el objetivo inicial tiene éxito, y este éxito se ha conseguido atribuyendo a X el valor b2. Y esa es la respuesta que da el procesador: «X=b2» . El proceso no termina aquí, porque el procesador no puede saber que no hay más valores de X que cumplan la condición: sigue tratando de satisfacer «jefe(a1,X)» desde H3. En este caso no hay más posibilidades, y la búsqueda termina. Pero si a1 tuviese más subordinados, es decir, si, por ejemplo, añadiésemos el hecho «jefe(a1,c2)» , el procesador ligaría X a c2, trataría de satisfacer «jefe(c2,d3)» , etc.
La Figura A.4 resume gráficamente el proceso descrito en el párrafo anterior. Cada nodo corresponde a un objetivo o a una conjunción de subobjetivos. El nodo sombreado indica un fracaso, y el cuadrado un éxito. La ramificación del nodo raíz corresponde a las dos posibilidades de satisfacción del primero de los subobjetivos.
Veamos ahora un ejemplo con listas. Recordemos la definición de miembro de una lista:
miembro([X|Y],X).
miembro([Y|Z],X) :- miembro(Z,X). |
Ante la consulta
?- miembro([1,2,3],M).
|
el procesador prueba con la primera cláusula, haciendo X=1, Y=[2,3], y la cláusula se satisface para M=1. Prueba luego la segunda cláusula, con Y=1, Z=[2,3], lo que le lleva al subobjetivo «miembro([2,3],M)» , que la primera cláusula satisface para M=2. De nuevo mira para ver si la segunda cláusula es aplicable, y lo es, con Y=2, Z=[3], formándose el subobjetivo «miembro([3],M)» , que la primera cláusula satisface, con M=X=3, Y=[]. Finalmente, al tratar de satisfacer este último subobjetivo con la regla, hace Y=3, Z=[] y obtiene el subobjetivo «miembro([],M)» , que fracasa. Cada vez que la búsqueda tiene éxito el procesador da como respuesta el valor de M.
La descomposición en subobjetivos va teniendo lugar, normalmente, de manera recursiva durante todo el proceso. Recordando nuevamente los hechos y las reglas dados en los Apartados A.2.1 y A.2.2 para definir «jefe» y «superior» , supongamos que se hace la consulta:
?- superior(a1,a4).
|
En la Figura A.5 se indica la sucesión de estados por los que va pasando el proceso. La Figura A.6 da la misma información en forma gráfica.
En el estado 3 del proceso, por ejemplo, un subobjetivo se descompone en dos. Si la regla R2 se utilizase más veces de manera recursiva, el segundo de los subobjetivos de descompondría en otros dos, el segundo de éstos en otros dos, etc.
A lo largo de esta exposición sobre ejemplos particulares han aparecido ya los elementos procesales básicos: la atribución de valores a variables (esto es un caso particular de unificación) y el retroceso. Analicémoslos con un poco más de detalle.
DIT-ETSIT-UPM
