Crean máquina de pila para ejecutar lógica computacional

Las máquinas abstractas para programas lógicos son un mecanismo conceptual que permite ejecutar definiciones relacionales como programas computacionales. En términos simples, una regla de inferencia como 'plus 0 N N' o 'plus (s N) M (s P)' define la relación de suma entre números, pero no esintrínsecamente un programa ejecutable; necesita ser 'ejecutada' mediante una máquina que busca respuestas específicas. La máquina de pila (stack machine) propuesta en el texto transforma estas relaciones en estados transitivos: recibe una consulta como 'plus N M X' y, mediante transiciones de estado, busca el valor de X que satisfy la relación. El aspecto crítico aquí es la 'asignación de modo', es decir, decidir qué posiciones de la relación son entradas vs. salidas. Con modo i/i/o (dos entradas, una salida) la máquina implementa suma; con modo i/o/i implementa resta (el famoso 'retroceso' de programas lógicos); y con modo o/o/i genera todos los pares de números que suman un resultado dado (no determinista). Este proceso de conversión de semántica operacional (reglas de inferencia) a máquinas abstractas tiene un propósito práctico enorme: permite implementar características avanzadas como parcialidad, no determinismo, excepciones y efectos en lenguajes de programación lógica. El trabajo de Hannan y Miller (1992) formalizó esta transformación, permitiendo verificación automática deCorrectitud. Hoy en día, este enfoque es relevante para implementadores de lenguajes y teóricos de la computación que trabajan con semántica de lenguajes.