Ejemplo

Sea el programa:

        P <- R, S, T.                   (1)
        R <- M, N.                      (2)
        S <- M.                         (3)
        T <- .                          (4)
        M <- .                          (5)
        N <- .                          (6)

y la cláusula de invocación:

        <- P.

que representa una invocación al procedimiento P. A los efectos de mostrar la evaluación del programa se considerará al conjunto $Q$ que contendrá los nombres de los procedimientos a ser invocados. En la terminología de la interpretación lógica vista en el capítulo anterior, $Q$ constituye el conjunto de objetivos a ser demostrados. Inicialmente:

$$Q = \{ P \}$$

La evolución de los valores de $Q$ a lo largo de la ejecución sería:

$$\begin{array}{llll} Q & = & \{ P \} & \\ Q & = & \{ R, S, ... ... \, \} & \mbox{por invocación al procedimiento (4)} \end{array}$$

Al llegar a una situación donde el conjunto $Q$ sea vacío, no habrá más procedimientos para invocar, y concluye la ejecución.

Ya se ha mencionado que el orden en que aparecen los predicados en el cuerpo de un procedimiento no debe significar, en principio, que con dicho orden los procedimientos serán invocados. Ello implica que al ir construyendo el conjunto $Q$ del ejemplo, en cada paso cuaquiera de los predicados que aparecen son suceptibles de ser invocados. En el caso del ejemplo, cualquiera que sea la elección en cada paso, se obtiene la finalización satisfactoria de la ejecución.

Supóngase ahora que se modifica el programa anterior, agregándose la cláusula:

        N <- F.         (7)

El programa sigue siendo válido, y la ejecución presentada continúa siendo un camino posible en la medida que al invocar el procedimiento N se opte por la definición (6). Sin embargo, si la decisión hubiera recaído en la definición (7), la ejecución hubiese podido continuar, pero se llegaría a un estado representado por:

$$Q = \{ F \}$$

de terminación anormal, al no disponerse de definiciones del procedimiento F.

De lo presentado en el ejemplo puede concluirse lo siguiente:

1. Pueden existir múltiples caminos que conduzcan a una terminación exitosa de la ejecución de un programa.

2. Pueden existir caminos que conduzcan a una terminación anormal de la ejecución.

Además, dado un programa y una invocación, puede suceder que tanto 1. como 2. sean ciertos. Esto significa que la decisión de escoger un predicado para ser activado puede tener capital importancia para obtener una ejecución que culmine exitosamente.

Habiendo presentado en forma general el problema de la invocación de procedimientos se analizará a continuación el papel que juegan las variables en la selección del procedimiento a activar. Se considera nuevamente el programa para la concatenación de listas:

   CONCAT (  [ ] , X,   X   ) <- .                         (1)
   CONCAT ( [X.L], Y, [X.Z] ) <- CONCAT ( L, Y, X ).       (2)

La invocación:

        CONCAT ( [a.[]], [b.[]], W ).

producirá una ejecución que se presenta como evolución del conjunto $Q$:

$$\begin{array}{llll} Q & = & \{ \mathtt{CONCAT([a.[]],[b.[]],... ...\mbox{por proc. (1) con unif. = \texttt{Z:=[b.[]]}} \end{array}$$

Es decir que la ejecución culmina exitosamente, y en el transcurso de la misma se han definido unificadores que van precisando el valor pedido de W. El resultado obtenido es:

        W = [a.[b.[]]]

En el desarrollo de la ejecución no han habido, en este caso, puntos de decisión. Si bien el programa tiene tiene dos procedimientos con el mismo nombre, CONCAT, ha sido el proceso de unificación de parámetros el que ha descartado alternativas durante la ejecución.

Hosted by www.Geocities.ws