A.4.4. Control del mecanismo de retroceso

Estudiemos el proceso ante la consulta

La primera regla llama al objetivo «ordenada([3,2,1])» , que fracasa. Por tanto, el procesador prueba con la segunda regla, con la unificación [3,2,1]/L, X/Lord. El subobjetivo «burbuja([3,2,1],L1)» tiene éxito con [2,1,3]/L1, y se llama a «orden_bur([2,1,3],X)» . La primera regla fracasa, y al probar la segunda se hace la unificación [2,1,3]/L, X/Lord. «burbuja([2,1,3],L1)» tiene ahora éxito con [1,2,3]/L1 y se prueba «orden_bur([1,2,3],X)» . En este momento, el procesador encuentra un éxito con la primera regla para [1,2,3]/X, y como X es la variable de la consulta, responde «X=[1,2,3]» . Pero el proceso no acaba aquí, porque el procesador no sabe que no hay más respuestas, y todavía tiene posibilidades: prueba con la segunda regla a satisfacer «orden_bur([1,2,3],X)» , lo que le lleva a los subobjetivos «burbuja([1,2,3],L1)» y «orden_bur(L1,X)» . El primero tiene éxito con [1,2,3]/L1, y el segundo (con la primera regla) con [1,2,3]/X. Por tanto, ha obtenido «otra» solución, y la escribe, y así indefinidamente.

(En los otros programas de ordenación no ocurría este fenómeno, porque el problema original se iba reduciendo sucesivamente al de ordenar una lista más pequeña, o dos listas más pequeñas en el caso de «quicksort» , terminándose al llegar a la lista vacía).

Pues bien, hay un «predicado» llamado corte, que no tiene argumentos, que siempre se satisface, y que se escribe «!» , cuyo efecto lateral es que inhibe el retroceso, descartando posibles alternativas de unificación. La cabeza de la regla que contiene «!» en su cuerpo se llama «objetivo padre» del «objetivo corte» . Al satisfacer «!» el procesador ya no prueba más unificaciones para el objetivo padre, ni en esta ni en otras reglas que lo tengan como cabeza.

Para arreglar la situación descrita en el ejemplo anterior basta con reescribir la primera regla así:

Mientras «ordenada(L)» no se satisfaga, el procesador no llega a «ver» el corte; por tanto, sigue con la segunda regla. En el momento en que L esté ordenada pasará al siguiente subobjetivo, «!» , que se satisface y por tanto se satisface el objetivo padre (y se da la respuesta), y ya no trata de satisfacerlo más veces.

En caso de «orden_log» sólo se obtiene una respuesta, pero si la lista inicial está ya ordenada, tras dar la respuesta el procesador sigue buscando permutaciones. Si queremos hacer «abortar» la búsqueda tras la respuesta basta con poner el «corte» :

El uso de «!» no siempre es tan fácil como indican estos ejemplos. Veamos otro. Ante la consulta «?- es_jefe(X)» del Apartado A.2.1 no se obtienen sólo las cuatro respuestas que allí se indican, sino:

(Repite cada jefe tantas veces como subordinados tiene). Veamos cómo arreglar las reglas

para que cada jefe aparezca una sola vez.

Si escribimos la primera así:

sólo obtenemos la primera respuesta, X=a1, ya que el corte impide que el procesador siga buscando las otras soluciones para «es_jefe(X)» . Lo mismo ocurre si dejamos la primera como está y la segunda así:

ya que tras el primer éxito de «jefe(Y,X)» (para a1/Y, a2/X) el corte impide que se sigan buscando soluciones para «subordinado» , y, por tanto, para «es_jefe» , puesto que éste se reduce simplemente a «subordinado» .

La solución está en «generar» los jefes en la primera regla y ver con la segunda si tienen subordinados, incluyendo en ésta el corte:

Esta es «casi» la solución, pero las respuestas que da se repiten, como en la primera versión. En efecto, para cada pareja (X,Y) que satisface a «jefe(X,Y)» la segunda regla lo confirma. Lo que hemos de hacer es, una vez generada la pareja (X,Y) tal que «jefe(X,Y)» se satisface, llamar a «subordinado» (con su corte, para que sólo dé una respuesta), pero con una variable distinta a Y:

De este modo, para cada X puede haber varios Y que satisfagan a «jefe(X,Y)» , pero «subordinado(Z,X)» sólo devuelve un valor de Z, que es el que se unifica con Y.

El lector podrá advertir con este ejemplo que el diseño de programas en Prolog que sean eficientes y que tengan el comportamiento deseado no es tarea trivial. Se hace a veces una analogía entre el «corte» y el «goto» de los lenguajes procedimentales, en el sentido de que son mecanismos potentes pero de uso peligroso.

Otro predicado de control, dual del «corte» , es el «fallo» , que se escribe «fail» . Cuando el procesador de objetivos encuentra este predicado devuelve siempre un fracaso y desencadena el retroceso. Veamos para qué puede servir. El lector que esté probando los ejemplos habrá observado otra anomalía, que se produce en el ejemplo dado más arriba para generar frases:

En efecto, ante la consulta «?- sentencias.» el ordenador no da las cuatro respuestas, sino sólo la primera. La explicación es fácil: el objetivo de la consulta no contiene variables, luego en cuanto se satisface se acaba el proceso. Y se satisface en cuanto se encuentra que la sustitución [’Espana’,es,’Espana’]/X satisface a «sentencia(X)» ; entonces «escr_lista» se satisface con los predicados «write» , «tab» y «nl» que tienen como efecto lateral escribir «Espana es Espana» . Podríamos hacer que la búsqueda continuase mediante la conversión de la cabeza de la primera regla en «sentencias(X)» , pero entonces obtendríamos como salida después de cada sentencia su versión como lista (X=[’Espana’,es,’Espana’], etc.). Pues bien, basta con incluir un fail en la regla:

para obtener las cuatro soluciones. En efecto, «fail» hace que fracase «sentencias» , pero antes el efecto secundario de «escr_lista(X)» ya ha escrito la primera sentencia («Espana es Espana» ). Como «fail» provoca el retroceso, el procesador busca otra unificación para X, encuentra la segunda ([’Espana’,es,un,estado]/X), la escribe («Espana es un estado» ), y así hasta agotar todas las posibles unificaciones.

Veamos, para terminar esta pequeña inmersión en el mundo de la programación en Prolog, un ejemplo de uso combinado de «corte» y «fallo» . Volvamos al ejemplo de los «jefes» y «superiores» , y consideremos un nuevo predicado, «ausente(X)» , que será verdadero si el individuo X está ausente. Supongamos que tenemos dos hechos más que se añaden a los ocho que ya teníamos sobre «jefes» :

(Así, por ejemplo, a4 tiene como superiores a a1, a2 y b3, pero sólo el primero no está ausente).

Supondremos también que nuestro procesador no tiene definido el operador «not» (o no queremos usarlo; de hecho, el operador se implementa con el procedimiento que vamos a ver).

Queremos ahora definir el predicado «sup_pres(X,Y)» tal que sea verdadero en el caso de que X sea superior de Y y además X no esté ausente. Las reglas:

no son correctas. En efecto, si X está ausente, el fail de la primera regla hará que fracase «sup_pres(X,Y)» , pero la segunda regla hace que tenga éxito. Tenemos que cortar la búsqueda en el momento en que ausente(X) tenga éxito, y para ello basta reescribir así la primera regla:

Ahora bien, estas reglas nos sirven para «comprobar» , pero no para «generar» . Por ejemplo:

(Con a1/X, a4/Y en la primera regla, fracasa «ausente(a1)» , por lo que no se llega al corte; la segunda regla remite al subobjetivo «superior(a1,a4)» , que satisfacen las reglas para «superior» ).

(En la primera regla, «ausente(a2)» tiene éxito; el siguiente subobjetivo es «!» que tambien tiene éxito e inhibe el retroceso para buscar más soluciones, y finalmente «fail» hace que fracase el objetivo).

Pero:

Ante esta última consulta se debería haber obtenido «X=a1» . No ha sido así porque ahora la primera regla trata de satisfacerse con «ausente(X)» , que se satisface con a2/X, y debido a la combinación «!,fail» fracasa el objetivo y no se sigue buscando.

Esto puede solucionarse definiendo aparte otro predicado, «presente(X)» , y escribiendo «sup_pres» a partir de él:

Obsérvese que «presente(X)» tiene éxito si «ausente(X)» fracasa, y viceversa. Esta es la forma de definir en Prolog la negación. Pero es una negación que no tiene exactamente el sentido que se le da en lógica. Volveremos sobre ello en el Apartado A.5.5. Y obsérvese también que con el operador «not» bastaría con la regla:

 DIT-ETSIT-UPM