Sintaxis y modelo computacional

Importante: este es el tema donde un programa lógico deja de ser «solo lógica». La lectura declarativa dice que el orden no importa; la ejecución real demuestra que sí importa. Dominar esa diferencia es lo que separa a quien escribe programas que funcionan de quien escribe programas que se «cuelgan».

Objetivo de aprendizaje

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

1. Escribir términos, cláusulas y consultas con la sintaxis correcta de Prolog y corregir errores comunes de sintaxis.
2. Describir el modelo de ejecución: lista de metas, base de cláusulas, puntos de elección y búsqueda en profundidad con retroceso.
3. Leer un árbol de búsqueda y predecir el orden en que aparecen las respuestas.
4. Explicar por qué el orden de las cláusulas y de las metas cambia el rendimiento y la terminación, e identificar una recursión por la izquierda.
5. Usar el corte, el condicional y la negación como fallo, y justificar sus riesgos.

Ruta de trabajo del tema

1. Planteamiento inicial

Los dos programas siguientes tienen las mismas dos cláusulas para definir ancestro; solo cambia su orden y la posición de la meta recursiva.

padre(a, b).

% Versión 1: el caso base primero; la recursión consume un arco antes de llamarse.
ancestro(X, Y) :- padre(X, Y).
ancestro(X, Y) :- padre(X, Z), ancestro(Z, Y).

% Versión 2: la meta recursiva va primero.
ancestro(X, Y) :- ancestro(X, Z), padre(Z, Y).
ancestro(X, Y) :- padre(X, Y).

En lógica, ambas versiones dicen lo mismo: «X es ancestro de Y si X es padre de Y, o si hay un Z tal que X es ancestro de Z y Z es padre de Y». Son definiciones equivalentes.

Esta hipótesis se retomará al final del tema.

2. Sintaxis de Prolog

Los términos

Todo en Prolog es un término. Hay cuatro formas, que se reconocen por su aspecto:

Definición — Predicado: conjunto de cláusulas con el mismo nombre y la misma aridad. padre/2 es el predicado padre de dos argumentos; padre/1 es otro, distinto.

Clasifique los términos siguientes.

Operadores y estructuras

Muchas estructuras se escriben con operadores para que sean legibles: 2 + 3 es la estructura +(2, 3). Los operadores tienen precedencia y asociatividad como en matemáticas, de modo que 2 + 3 * 4 es +(2, *(3, 4)). El motor no calcula esas estructuras al leerlas.

Importante: la comparación «menor o igual» se escribe =<, no <=. El símbolo <= no existe en Prolog.

Errores de sintaxis frecuentes

Escriba un programa con alguno de estos errores en la pestaña «Mi programa» y lea el mensaje: el intérprete indica la línea y el símbolo que no esperaba.

3. El modelo de ejecución

El tema 5.1 describió los pasos por separado. Reunidos, forman una máquina sencilla con cuatro componentes:

flowchart TD
  A["Lista de metas"] --> B{"¿Está vacía?"}
  B -- "Sí" --> C["ÉXITO: se muestra la respuesta"]
  B -- "No" --> D["Tomar la primera meta"]
  D --> E{"¿Hay una cláusula cuya cabeza unifique?"}
  E -- "Sí" --> F["Anotar punto de elección si quedan más cláusulas<br/>Reemplazar la meta por el cuerpo"]
  F --> A
  E -- "No" --> G{"¿Quedan puntos de elección?"}
  G -- "Sí" --> H["RETROCESO: deshacer las ligaduras y probar la siguiente cláusula"]
  H --> E
  G -- "No" --> I["FALLO: false"]
  C -. "pedir otra respuesta con ;" .-> G

Definición — Búsqueda en profundidad con retroceso: estrategia que explora una rama del árbol de posibilidades hasta el final antes de probar la siguiente. Prolog siempre prueba las cláusulas en el orden en que están escritas y las metas de izquierda a derecha; no hay ninguna heurística ni aleatoriedad. Por eso el comportamiento es predecible, y por eso el orden importa.

Una comparación con Python

En Python, cuando una función llama a otra, la ejecución sigue una sola línea de ejecución que se apila y desapila (pila de llamadas). En Prolog hay, además, una segunda pila: la de puntos de elección. Cuando una meta falla, no se produce una excepción: simplemente se abandona la rama y se vuelve al último punto de elección.

4. El árbol de búsqueda

Toda consulta define un árbol de búsqueda: cada nodo es una lista de metas por demostrar; cada arista, la elección de una cláusula (con las ligaduras que se hicieron). Las hojas son de tres tipos: éxito (lista vacía, □), fallo (✗, ninguna cláusula sirve) o podadas por un corte. El motor recorre el árbol en profundidad, de izquierda a derecha.

Con todas las soluciones, el motor recorre el árbol completo. Cuente las hojas con cuadro: son las respuestas. Las hojas con ✗ son caminos que no llevaron a ninguna.

Nota: el árbol no está dibujado de antemano: se construye a medida que el motor lo explora. Un árbol infinito (o muy ancho) es la causa de las consultas que no terminan.

5. Orden de las cláusulas y de las metas

La lectura declarativa dice que el orden no cambia el significado. La lectura procedimental dice que sí cambia el comportamiento. Las dos afirmaciones son ciertas: el conjunto de respuestas puede ser el mismo, pero el orden, el trabajo realizado y la terminación pueden variar.

El mismo conjunto de respuestas, otro orden

Una versión que no termina

Vuelva al planteamiento inicial. La Versión 2 pone la meta recursiva primero: para demostrar ancestro(a, b) hay que demostrar ancestro(a, Z), que vuelve a probar la primera cláusula con los mismos argumentos, y así indefinidamente. El motor nunca llega a probar la segunda cláusula, que sí tiene respuesta.

Definición — Recursión por la izquierda: una cláusula recursiva cuya primera meta es una llamada al mismo predicado con los mismos argumentos (o con argumentos que no están más cerca de un caso base). El motor la expande sin avanzar y nunca termina.

Reglas prácticas de escritura:

1. Escriba primero las cláusulas de los casos base y después las recursivas.
2. En la cláusula recursiva, haga que antes de llamarse a sí misma se consuma al menos un paso (un arco, un elemento de la lista).
3. Coloque las comprobaciones lo antes posible, para podar ramas inútiles.

Probar pronto, no probar tarde

La diferencia no está en las respuestas (son las mismas 12 coloraciones) sino en las inferencias: la versión que comprueba cada restricción en cuanto es posible descarta ramas inválidas sin explorarlas. En problemas de búsqueda más grandes, esa diferencia separa lo que termina en un segundo de lo que tarda años.

6. Aritmética

Los números en Prolog son términos como cualquier otro: 2 + 3 es una estructura. Para calcular hay que pedirlo explícitamente.

Importante: is y las comparaciones aritméticas exigen que las variables del lado derecho ya tengan valor. Si no, Prolog informa un error (no un fallo): la ejecución se interrumpe.

Esta es la razón por la que factorial(5, F) funciona y factorial(N, 120) no: las relaciones aritméticas pierden la reversibilidad.

7. El corte y el condicional

El corte (!) es una meta que siempre se cumple, pero tiene un efecto secundario sobre la búsqueda: elimina los puntos de elección creados desde que se llamó al predicado que lo contiene.

Definición — Corte: al ejecutarse, descarta (1) las demás cláusulas del predicado que se estaba demostrando y (2) todos los puntos de elección creados por las metas anteriores del cuerpo. El motor queda «comprometido» con las decisiones tomadas.

% maximo(X, Y, M): M es el mayor de X y Y.
maximo(X, Y, X) :- X >= Y, !.
maximo(_, Y, Y).

Definición — Corte verde y corte rojo: un corte es verde si solo ahorra trabajo (el programa da las mismas respuestas sin él). Es rojo si cambia las respuestas, como en este ejemplo. Los cortes rojos hacen que el programa solo sea correcto con un orden concreto de cláusulas y con ciertos modos de uso; hay que justificarlos y documentarlos.

El condicional: una forma más clara de elegir

La forma ( Condición -> Entonces ; Sino ) elige una sola rama sin dejar puntos de elección. Es la manera recomendada de expresar «si… entonces… sino» en Prolog.

% clasificar(N, C): C es negativo, cero o positivo.
clasificar(N, C) :-
    (   N < 0 -> C = negativo
    ;   N =:= 0 -> C = cero
    ;   C = positivo
    ).

Error común — usar el corte como «return»: el corte no termina la ejecución de una función ni «devuelve» nada. Solo elimina alternativas. Un corte colocado sin entender qué puntos de elección elimina es una fuente de errores difíciles de encontrar.

8. Negación como fallo

Prolog no puede demostrar que algo es falso; solo puede intentar demostrarlo y verificar que no lo logra. El operador \+ implementa esa idea.

Definición — Negación como fallo: \+ M se cumple si la meta M no se puede demostrar con el programa, y falla si se puede. Se basa en la suposición del mundo cerrado.

persona(ana).
persona(luis).
persona(rosa).
casado(luis).

% X es soltero si es persona y NO se puede demostrar que está casado.
soltero(X) :- persona(X), \+ casado(X).

Importante: \+ casado(X) con X sin ligar no pregunta «¿X no está casado?» sino «¿es imposible encontrar alguien casado?». Como Luis está casado, la meta casado(X) se demuestra y su negación falla. Regla práctica: ligue las variables antes de negar.

9. Fallo, error y no terminación

Una consulta puede terminar de cuatro maneras. Distinguirlas es parte de depurar un programa.

Prediga qué ocurrirá con cada consulta.

10. Verificación y reformulación

11. Libreta de trabajo

12. Preguntas de reflexión

1. Dibuje a mano el árbol de búsqueda de la consulta padre(X, Y), padre(Y, Z) con el programa de la familia. ¿Cuántas hojas con éxito tiene y cuántas con fallo? Compárelo con la corrida del laboratorio.
2. Un compañero afirma que «como Prolog es lógica, el orden de las cláusulas no puede cambiar el resultado». Redacte una respuesta que distinga el significado declarativo del comportamiento procedimental, con un ejemplo.
3. Proponga un uso del corte que sea verde y otro que sea rojo. Explique cómo detectaría cada uno.
4. Explique con sus palabras por qué la negación de Prolog no equivale a la negación lógica. ¿En qué tipo de aplicación sería peligroso olvidarlo?
5. Compare la pila de llamadas de Python con la pila de puntos de elección de Prolog. ¿Qué situación del programa vuelve a ejecutar código ya ejecutado?

13. Lecturas recomendadas

• Sterling, L., & Shapiro, E. (1994). The art of Prolog (2nd ed.). MIT Press. (Capítulos sobre el modelo de ejecución y el corte; disponible en la bóveda: 08-Referencias.)
• Clocksin, W. F., & Mellish, C. S. (2003). Programming in Prolog (5th ed.). Springer. (Capítulos sobre el control de la ejecución y el corte; disponible en la bóveda.)
• Bratko, I. (1986). Prolog programming for artificial intelligence. Addison-Wesley. (Disponible en la bóveda: 08-Referencias.)
• Gabbrielli, M., & Martini, S. (2010). Programming languages: principles and paradigms. Springer. (Sección sobre el modelo operacional de Prolog.)
• Kowalski, R. (1979). Algorithm = logic + control. Communications of the ACM, 22(7), 424–436.