Conceptos fundamentales

Importante: este tema es el más abstracto de la unidad, porque presenta un modelo de ejecución diferente al de todos los lenguajes anteriores. Se recomienda avanzar con las animaciones abiertas y predecir cada paso antes de verlo. La comprensión llega al repetir el mismo mecanismo en ejemplos distintos, no al leerlo una sola vez.

Objetivo de aprendizaje

Al concluir este tema, el estudiante será capaz de:

1. Identificar y escribir hechos, reglas y consultas, y leerlos en lenguaje natural.
2. Explicar qué es una variable lógica y en qué se diferencia de una variable de Python.
3. Unificar dos términos a mano, paso a paso, y decidir si unifican.
4. Describir un paso de resolución y seguir la lista de metas de una consulta hasta su éxito o su fallo.
5. Explicar qué es un punto de elección y qué ocurre en un retroceso, y justificar por qué «false» significa «no se pudo demostrar».

Ruta de trabajo del tema

1. Planteamiento inicial

En Python, el signo = significa asignar: x = 3 guarda el valor 3 en x, y una asignación posterior (x = 4) cambia el valor. En Prolog también existe un signo =, pero significa otra cosa. Considere la consulta:

?- f(X, b) = f(a, Y).

No se ha definido ninguna variable antes. A la izquierda hay una variable X y la constante b; a la derecha, la constante a y una variable Y.

Esta hipótesis se retomará después de estudiar la unificación.

2. Hechos, reglas y consultas

Un programa lógico se compone de tres tipos de oraciones. Dos de ellas forman el programa (el conocimiento) y la tercera es la pregunta que se le hace.

Definición — Cláusula: hecho o regla. Una cláusula tiene una cabeza (lo que se afirma o define) y, en las reglas, un cuerpo formado por una o más metas separadas por comas. Un hecho es una regla sin cuerpo. En lógica, estas cláusulas se llaman cláusulas de Horn (o cláusulas definidas) y representan implicaciones: «si todas las metas del cuerpo se cumplen, la cabeza se cumple».

Definición — Meta (o submeta): una afirmación que el motor debe demostrar. Una consulta es una lista de metas; el cuerpo de una regla también.

Dos lecturas del mismo programa

Una regla puede leerse de dos maneras. Ambas son correctas y complementarias:

Tip: al escribir un programa, use la lectura declarativa para convencerse de que es correcto, y la procedimental para anticipar si termina y cuánto trabajo hace.

Una base de conocimiento con datos de una escuela

% Hechos: cursa(Persona, Materia).
cursa(ana, paradigmas).
cursa(luis, paradigmas).
cursa(ana, bases).
cursa(rosa, bases).

% Regla: A y B son compañeros si cursan una misma materia M y son personas distintas.
compañeros(A, B) :- cursa(A, M), cursa(B, M), A \= B.

Ejecute primero las consultas con una variable: el motor devuelve todos los valores que las hacen verdaderas. Active «Todas las soluciones» para reproducir lo que hace el signo ; en la consola de Prolog.

3. Variables lógicas

En los paradigmas anteriores, una variable es un nombre ligado a un valor que puede cambiar (una caja que se sobrescribe). En Prolog, una variable lógica es una incógnita: un hueco que se llena una vez, con un valor que hace verdadera la consulta.

Definición — Variable anónima: el guion bajo _ es una variable cuyo valor no importa. Cada aparición de _ es una variable distinta; sirve para escribir «cualquier cosa» sin darle nombre.

Error común — pensar que una variable «guarda un resultado»: en Prolog no se guarda nada; se descubre qué valor hace verdadera la afirmación. Por eso no tiene sentido escribir X = X + 1: la afirmación sería «X es igual a la estructura X+1», que no se cumple (y que además crea un término infinito).

4. Unificación

La unificación es el mecanismo central de Prolog: sustituye a la asignación, al paso de parámetros, a la selección de casos y a la construcción de estructuras.

Definición — Unificación: dos términos unifican si existe una sustitución (una asignación de términos a variables) que los vuelve idénticos. Esa sustitución se llama unificador. Cuando existe, hay uno más general, que no liga variables innecesariamente.

Las reglas de la unificación

El algoritmo trabaja con una lista de ecuaciones del tipo «término = término» y una sustitución. Toma la primera ecuación y aplica la regla que corresponde:

Observe y ejecute el algoritmo. Active «Predecir la regla de cada paso» para anticipar cuál se aplicará.

Nota: la unificación no calcula. 2 + 3 y 5 no unifican porque el primero es una estructura (el símbolo + con dos argumentos) y el segundo es un número. Para calcular se usa is, que se estudia en el tema 5.2.

Casos que conviene conocer

• Una variable repetida obliga a la igualdad: p(X, X) unifica con p(1, Y) (con Y = 1), pero no con p(1, 2).
• Las listas son estructuras: [H|T] unifica con [1, 2, 3] ligando H = 1 y T = [2, 3]; no unifica con [].
• Los átomos solo unifican con el mismo átomo: las comillas no cambian el átomo (a y 'a' son el mismo).
• Un entero no unifica con un real: 1 y 1.0 son términos distintos.
• Sin verificación de ocurrencia, X = f(X) tiene éxito y construye un término infinito. Los sistemas reales la omiten por velocidad; el laboratorio permite activarla.

Decida usted si unifican y compare con el algoritmo.

Error común — pensar que = asigna: en Prolog X = 5 es una meta que se cumple si X y 5 unifican. Si X ya está ligada a 7, la meta falla; no cambia nada. Cambiar un valor ya ligado es imposible: lo único que se puede hacer es retroceder y probar otra rama.

5. Resolución

Con la unificación ya se puede explicar cómo el motor demuestra una consulta.

Definición — Paso de resolución: dada una lista de metas por demostrar, (1) se toma la primera; (2) se busca, en orden, una cláusula cuya cabeza unifique con ella (usando una copia de la cláusula con variables nuevas, para que no se mezclen con las de otros usos); (3) la meta se reemplaza por el cuerpo de esa cláusula, aplicando la sustitución a toda la lista. Si la cláusula es un hecho, la meta simplemente desaparece. La consulta se demuestra cuando la lista de metas queda vacía.

La variante de resolución que usa Prolog (con selección de la primera meta y de las cláusulas en orden) se llama resolución SLD.

Una corrida de escritorio manual

Se demuestra abuelo(juan, Z) con el programa de la familia (cuatro hechos de padre y la regla abuelo). La cláusula usada se renombra con un subíndice (X₁, Y₁…) para distinguir sus variables de las de la consulta.

Observe tres cosas: la regla se instancia con variables nuevas; el cuerpo reemplaza a la meta; y los hechos que no unifican se descartan sin más (no se «equivocan»). Ahora ejecute la misma consulta en el laboratorio y active la predicción: en cada paso se le pide anticipar si la cabeza de la cláusula unifica con la meta.

Nota: el árbol de la derecha dibuja las mismas decisiones: cada arista es una cláusula elegida y cada nodo, la lista de metas que resulta. El tema 5.2 lo estudia con detalle.

6. Retroceso y puntos de elección

El paso 3 de la tabla anterior tuvo que probar tres hechos hasta encontrar uno que unificara. En general, una meta puede unificar con más de una cláusula, y cualquiera de ellas podría llevar a una demostración. El motor elige la primera y anota que quedaron otras: eso es un punto de elección.

Definición — Punto de elección: lugar de la búsqueda donde quedan cláusulas por probar. Se anota junto con el estado de las ligaduras y de la lista de metas en ese momento.

Definición — Retroceso (backtracking): cuando una meta falla (o cuando se pide otra solución), el motor vuelve al último punto de elección, deshace todas las ligaduras hechas desde entonces, y continúa con la siguiente cláusula. Si no quedan puntos de elección, la consulta falla.

En la consola de Prolog, después de mostrar una respuesta, escribir ; pide otra: eso provoca un retroceso. Active «Todas las soluciones» y observe cada retroceso en la corrida.

Importante: el retroceso deshace las ligaduras, no el efecto de las operaciones de salida. Si una meta ya imprimió algo con write, retroceder no lo borra. Por eso las operaciones de entrada y salida rompen la lectura declarativa del programa.

7. Mundo cerrado

Cuando una consulta responde false, ¿significa que la afirmación es falsa? No necesariamente.

Definición — Suposición del mundo cerrado: todo lo que no se puede demostrar con el programa se considera falso. Es razonable para una base de datos completa (si «Juan» no figura en la lista de empleados, no es empleado) y peligroso cuando el conocimiento es incompleto. Es la base de la negación como fallo que se estudia en el tema 5.2.

8. Reversibilidad: una relación, varias preguntas

Los tres mecanismos juntos explican la sorpresa del tema 5.0. Como la unificación es simétrica (no distingue entre «entrada» y «salida»), una misma definición puede usarse para verificar un par, para completar uno de sus elementos o para enumerar todos.

Observe la relación concatenar (la unión de listas): con el mismo código se puede unir dos listas, quitar un sufijo, quitar un prefijo y partir una lista de todas las maneras posibles. Ninguna de las otras funciones del curso (en Python ni en Haskell) puede hacerlo.

Nota: la reversibilidad no es universal. Un predicado que usa is o comparaciones numéricas solo funciona en un sentido, porque la aritmética exige valores ya conocidos. Los programas que usan is pierden esa propiedad; los que solo usan unificación la conservan.

9. Errores frecuentes y verificación

Error común — olvidar que cada uso de una regla tiene variables nuevas: las variables de una cláusula son locales a esa cláusula. Si el nombre X aparece en dos reglas distintas, no hay relación entre ellas.

Error común — esperar que las respuestas lleguen en un orden «inteligente»: el motor responde en el orden en que aparecen las cláusulas. Cambiar el orden de los hechos cambia el orden de las respuestas.

Error común — creer que el programa «recuerda» ligaduras anteriores: al retroceder, las ligaduras se deshacen. Para conservar resultados de varias respuestas hay que recogerlos con predicados como findall (tema 5.3).

Error común — olvidar el punto al final de la consulta: en la consola de Prolog, la consulta termina con punto; sin él, el sistema espera más texto.

10. Libreta de trabajo

11. Preguntas de reflexión

1. Escriba tres hechos y una regla sobre un tema que le interese (música, deportes, materias). Léalos en voz alta con las dos lecturas, declarativa y procedimental. ¿Cuál lectura le ayuda más a detectar errores?
2. Unifique a mano f(X, g(Y, X)) con f(h(Z), g(2, W)). Escriba las ecuaciones en cada paso y la sustitución final. Después compruébelo en el laboratorio.
3. Explique por qué, en una consulta con varias respuestas, la segunda respuesta no «conoce» las ligaduras de la primera. ¿Qué mecanismo lo garantiza?
4. ¿Qué diferencia hay entre decir que padre(luis, ana) es falso y que Prolog responde false? Dé un ejemplo de una base de datos donde la diferencia pueda causar un error en una aplicación.
5. Compare la unificación con tres mecanismos que ya conoce: la asignación, el paso de parámetros y la selección con if. ¿Qué papel cumple la unificación en cada caso?

12. Lecturas recomendadas

• Sterling, L., & Shapiro, E. (1994). The art of Prolog (2nd ed.). MIT Press. (Disponible en la bóveda: 08-Referencias.)
• Clocksin, W. F., & Mellish, C. S. (2003). Programming in Prolog (5th ed.). Springer. (Disponible en la bóveda.)
• Gabbrielli, M., & Martini, S. (2010). Programming languages: principles and paradigms. Springer. (Capítulo sobre el paradigma lógico: unificación y resolución SLD.)
• Robinson, J. A. (1965). A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1), 23–41. (Origen de la unificación y la resolución.)
• Kowalski, R. (1974). Predicate logic as programming language. Proceedings of IFIP Congress, 569–574. (Origen de la interpretación procedimental de las cláusulas de Horn.)