Intérprete no determinista

A partir de lo planteado en la sección anterior, puede concluirse que un programa en lógica implica un no determinismo en su evaluación, que se evidencia por los puntos de decisión que aparecen en el transcurso de una ejecución. Parece natural que para explicar el comportamiento de un evaluador de programas en lógica, se utilice un lenguaje que tenga primitivas de no determinismo. En esta sección se presentarán dichas primitivas, y se describirá una máquina no determinista como semántica operacional para describir la evaluación de programas en lógica.

Sea $P$ el conjunto de procedimientos que conforman un programa. Se dispone además de las funciones:

   cabeza : procedimientos -> predicados

cuya semántica es que dado un procedimiento devuelve el predicado del encabezamiento del mismo, y

   cuerpo : procedimientos -> conjunto de predicados

que devuelve los predicados del cuerpo del procedimiento que recibe como argumento.

Sea $Q$ el conjunto de invocaciones de procedimientos. Inicialmente contendrá el (los) predicado(s) dado(s) por el usuario al solicitar una ejecución.

Se dispone de un procedimiento:

   unif ( P1, P2, éxito, $$\theta$$    )$$$$

que intenta resolver los predicados P1 y P2. Si lo consigue devuelve en $\theta$ el unificador más general, y asigna el valor verdadero a éxito. Si la unificación no es posible, éxito toma el valor falso.

Finalmente se tiene la función sust:

$$\begin{array}{l} \mbox{\texttt{sust : conjunto de predicados... ...mbox{\texttt{unificador -> conjunto de predicados}} \end{array}$$

cuya función es aplicar el unificador al conjunto de predicados y devolver el conjunto así obtenido.

El constructor no determinista que se usará es:

        elegir : conjunto => elemento del conjunto

y cuya función es escoger arbitrariamente un elemento de un conjunto. Se utiliza el símbolo «=>» para expresar el no determinismo de la «función».

Una forma de entender el comportamiento de elegir es escribir su significado mediante primitivas más básicas de no determinismo. Supóngase que a los conjuntos los representamos como sucesiones, y se dispone del constructor de programas «O». Si P1 y P2 son dos programas, entonces P1 O P2 es un nuevo programa cuya ejecución será la ejecución de P1, o la ejecución de P2, siendo la decisión entre ambas alternativas arbitraria. Con estos elementos se puede definir la función elegir:

elegir ( sucesión ) :=
        si la sucesión tiene un solo elemento
           entonces devolver ese elemento
        sino ( devolver primer elemento de la sucesión
                O
               elegir ( sucesión sin el primer elemento )
             )

Con todo lo definido, es posible presentar la máquina no determinista para la evaluación de programas en lógica.

Hosted by www.Geocities.ws