A.3.3 Influencia del modelo procesal en el modelo funcional

A.3.3. Influencia del modelo procesal en el modelo funcional

El ideal de la programación lógica es que la máquina que ejecuta el programa interprete exclusivamente su significado lógico, y que, por tanto, dé los mismos resultados para dos programas que, aunque distintos, sean lógicamente equivalentes. Pero cuando lo que tenemos como «máquina lógica» es un intérprete (o compilador) de Prolog programado sobre una máquina convencional las cosas dejan de ser ideales, y es preciso tener conocimiento del modelo procesal para escribir programas correctos. Veámoslo en el ejemplo de los jefes y los superiores, pero ahora, para simplificar la presentación de los procesos, supondremos que sólo hay tres hechos:

H1: jefe(ana,eva).

H2: jefe(eva,pepe).

H3: jefe(eva,paco).

Consideremos cuatro maneras diferentes de escribir las reglas para definir superior:

Versión 1:

R1: superior(X,Y) :- jefe(X,Y).
R2: superior(X,Y) :- jefe(X,Z),superior(Z,Y).

Versión 2:

R1: superior(X,Y) :- jefe(X,Z),superior(Z,Y).
R2: superior(X,Y) :- jefe(X,Y).

Versión 3:

R1: superior(X,Y) :- jefe(X,Y).
R2: superior(X,Y) :- superior(X,Z),jefe(Z,Y).

Versión 4:

R1: superior(X,Y) :- superior(X,Z),jefe(Z,Y).
R2: superior(X,Y) :- jefe(X,Y).

La primera de las versiones es la que ya habíamos utilizado, pero obsérvese que las cuatro son lógicamente equivalentes. Analicemos, en cada caso, el proceso que seguiría la máquina para la consulta:

?- superior(ana,paco).

cuya respuesta debe ser «YES» .

En el caso de la versión 1, la Figura A.7 resume el proceso. Como la regla R1 fracasa para el objetivo inicial, se prueba con la R2, que lo descompone en los subobjetivos «jefe(ana,Z)» y «superior(Z,paco)» . H1 satisface al primero con la sustitución eva/Z, lo que convierte al segundo en «superior(eva,paco)» , que se satisface por aplicación sucesiva de R1 y H3.

pict

Figura A.7:

Proceso de búsqueda para superior(ana,paco) con la versión 1 de las reglas para definir superior(X,Y)

pict

Figura A.8:

Proceso de búsqueda para superior(ana,paco) con la versión 2 de las reglas para definir superior(X,Y)

pict

Figura A.9:

Proceso de búsqueda para superior(ana,paco) con la versión 3 de las reglas para definir superior(X,Y)

En la versión 2 hay un cambio que declarativamente no afecta, pero cuyas consecuencias procesales se aprecian a simple vista en la Figura A.8. Si el lector sigue la secuencia de objetivos y subobjetivos observará que todo ello se produce como consecuencia del mecanismo de búsqueda del intérprete, que siempre va mirando los hechos y las reglas aplicables «de arriba abajo» . Ello le conduce a tratar de satisfacer a los objetivos sucesivos empezando siempre con la regla recursiva, y únicamente cuando ha agotado las posibilidades acude a la no recursiva. Si en lugar de tres hubiese cientos de hechos, las operaciones de búsqueda se multiplicarían.

La versión 3 difiere de la 1 en que la recursividad de R1 se hace por la izquierda, no por la derecha. En este caso, ello no influye en el número de operaciones de búsqueda del procesador, como indica la Figura A.9. No ocurre así si la consulta contiene variables. Dejamos como ejercicio al lector el comprobar que ante una consulta como, por ejemplo:

?- superior(X,paco).

el intérprete daría las dos respuestas (X=eva y X=ana) y después entraría en un bucle (buscando más respuestas).

pict

Figura A.10:

Proceso de búsqueda para superior(ana,paco) con la versión 4 de las reglas para definir superior(X,Y)

Pero veamos lo que ocurre con la versión 4 (Figura A.10). Debido al orden de las reglas y a la recursividad por la izquierda de R1 se genera una búsqueda sin fin. En efecto, el objetivo inicial, «superior(ana,paco)» , trata de satisfacerse por R1, que lo descompone en «superior(ana,Z)» y «jefe(Z,paco)» . Al tratar de satisfacer al primero el procesador escoge de nuevo R1, que lo descompone en «superior(ana,Z1)» y «jefe(Z1,Z)» , y así sucesivamente. El resultado es que el proceso no termina nunca: en cada paso por R1 añade un subobjetivo nuevo a la secuencia de los pendientes. En la práctica ocurrirá que la zona de memoria reservada para la pila en la que se van guardando las sustituciones y los puntos de retroceso se verá desbordada, y el procesador generará un mensaje de error.

DIT-ETSIT-UPM

Portada