Pensar en relaciones

Importante: pasar de la programación funcional o de la orientada a objetos a la lógica no es aprender una sintaxis nueva: es dejar de dar órdenes. En los dos paradigmas anteriores la persona que programa decide cómo se calcula el resultado; en el paradigma lógico solo describe qué es verdad, y el sistema busca por su cuenta. Es normal que al principio parezca que «el programa no hace nada». Este tema avanza despacio, con ejemplos que se repiten en los tres paradigmas, y con una receta de trabajo que se aplica a cada caso.

Objetivo de aprendizaje

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

1. Distinguir una solución algorítmica (instrucciones y funciones que calculan un valor) de una solución lógica (hechos y reglas que describen relaciones) para un mismo problema.
2. Aplicar un método de seis pasos para interpretar un problema como individuos, relaciones, hechos, reglas y preguntas.
3. Escribir hechos, reglas y consultas sencillas en Prolog y leerlos en voz alta como oraciones.
4. Explicar por qué una misma definición puede responder preguntas en varias direcciones, y por qué una función de Python no puede hacerlo.
5. Reconocer los errores típicos de quien viene de otros paradigmas y verificar una solución con casos positivos, casos negativos y casos límite.

Ruta de trabajo del tema

1. Planteamiento inicial

Considere una pequeña base de datos familiar. Se sabe que Juan es padre de Luis y de Ana, que Luis es padre de Pedro y que Ana es madre de Rosa. Se pide un programa que responda a la pregunta «¿quiénes son los abuelos de Rosa?».

Una persona con experiencia en Python lo resolvería de inmediato con un diccionario y dos ciclos anidados:

hijos = {"juan": ["luis", "ana"], "luis": ["pedro"], "ana": ["rosa"]}

def abuelos_de(nieto):
    resultado = []
    for abuelo in hijos:
        for padre in hijos[abuelo]:
            if nieto in hijos.get(padre, []):
                resultado.append(abuelo)
    return resultado

La función responde bien, pero solo una pregunta. Si ahora se necesitan también «¿de quiénes es abuelo Juan?» y «¿es Juan abuelo de Rosa?», la intuición indica que habrá que escribir más código.

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

2. Dos maneras de pensar el mismo problema

Una analogía conocida: las reglas de un juego y el árbitro

Piense en las reglas de un juego de mesa. El reglamento no dice cómo ganar: dice qué movimientos son válidos y cuándo se gana. Si se le pregunta al árbitro «¿es válido este movimiento?», responde sí o no; si se le pregunta «¿qué movimientos son válidos desde aquí?», los enumera. El reglamento es uno solo; las preguntas son muchas. Un programa lógico es un reglamento, y quien lo ejecuta es el árbitro.

Una analogía más cercana al curso: una base de datos. En SQL no se escribe «recorra la tabla fila por fila»; se escribe qué filas se desean, y el motor decide cómo encontrarlas. Prolog lleva esa idea más lejos: las reglas pueden definir relaciones nuevas a partir de otras y hasta llamarse a sí mismas.

Primero la función: una pregunta, una función

Ejecute la función abuelos_de y observe cómo los ciclos recorren el diccionario y cómo resultado se va llenando.

Ahora la pregunta contraria. No basta con cambiar un argumento: la función abuelos_de no puede dar los nietos.

Nota: en Python cada función fija qué argumentos son datos y cuál es el resultado. Para responder otra pregunta sobre los mismos datos hay que escribir otra función, aunque la definición de «abuelo» sea la misma.

Ahora la relación: una definición, todas las preguntas

La misma información se escribe en Prolog como hechos (lo que se sabe) y una regla (lo que se deduce). Lea la regla en voz alta: «X es abuelo de Z si X es padre de algún Y y ese Y es padre de Z».

% Hechos: lo que se sabe del mundo. «padre(X, Y)» se lee: X es padre de Y.
padre(juan, luis).
padre(juan, ana).
padre(luis, pedro).
padre(ana, rosa).

% Regla: X es abuelo de Z si X es padre de alguien (Y) que es padre de Z.
abuelo(X, Z) :- padre(X, Y), padre(Y, Z).

Active la predicción para anticipar, en cada paso, si la cabeza de la cláusula elegida unifica con la meta. Aún no hace falta entender el mecanismo completo: el tema 5.1 lo desarrolla.

La sorpresa: la misma regla responde las otras preguntas

No se escribió ninguna función nueva. Solo se cambió la consulta. Ejecute los tres programas de la pestaña: preguntar los nietos de Juan, preguntar quién es abuelo de Rosa y verificar un par concreto.

Definición — Relación: conjunto de tuplas de individuos que cumplen una condición. «abuelo» es la relación formada por todos los pares (abuelo, nieto). A diferencia de una función, una relación no distingue entre entradas y salidas: los argumentos que se dejan sin valor son las incógnitas de la consulta.

Esta propiedad se llama reversibilidad y es una de las ideas más importantes del paradigma. No todas las definiciones la conservan (la aritmética, por ejemplo, la pierde), pero las que describen relaciones puras la tienen de manera natural.

3. El método de seis pasos

Pensar en relaciones se aprende con una receta que se repite. Estos son los seis pasos; en las secciones siguientes se aplican a tres problemas.

Tip: el paso 3 se puede comprobar leyendo la regla en voz alta con la palabra «si» en lugar de «:-» y «y» en lugar de la coma. Si la oración no es verdadera en español, la regla tampoco lo será en Prolog.

4. Caso A: parentesco

Problema. Dado el árbol familiar, definir las relaciones «abuelo» y «hermano».

Paso 1. Individuos y relaciones. Individuos: juan, luis, ana, pedro, rosa. Relación dada: padre(X, Y) (X es padre de Y). Relaciones por definir: abuelo(X, Z) y hermano(X, Y).

Paso 2. Hechos. Los cuatro de padre.

Paso 3. Reglas. «X es abuelo de Z si X es padre de Y y Y es padre de Z.» «X es hermano de Y si tienen el mismo padre P.»

Paso 4. Preguntas. hermano(luis, H) debería responder H = ana. hermano(pedro, H) no debería responder nada (Pedro no tiene hermanos registrados).

Paso 5. Prueba y fallo. Ejecute el primer intento de la regla hermano, escrita tal como se dijo en el paso 3.

Paso 6. Revisión. La regla ingenua no dice que X y Y deban ser personas distintas. Un programa lógico hace exactamente lo que dice, no lo que se quiso decir. La condición X \= Y («X y Y no unifican») corrige el error.

% Hechos
padre(juan, luis).
padre(juan, ana).
padre(luis, pedro).
padre(ana, rosa).

% Reglas
abuelo(X, Z) :- padre(X, Y), padre(Y, Z).
hermano(X, Y) :- padre(P, X), padre(P, Y), X \= Y.

Error común — olvidar una condición implícita: en lenguaje natural, «hermano» presupone «otra persona». En Prolog nada se presupone. Cuando una relación devuelve respuestas de más, casi siempre falta una condición.

5. Caso B: rutas entre ciudades

Problema. Se conocen los vuelos directos entre algunas ciudades. Se desea saber si es posible viajar de una ciudad a otra con escalas y, si es posible, por qué ciudades.

Paso 1. Individuos y relaciones. Individuos: tijuana, guadalajara, cdmx, cancun. Relación dada: vuelo(A, B) (hay un vuelo directo de A a B). Relaciones por definir: alcanzable(A, B) y ruta(A, B, Camino).

Paso 2. Hechos. Cuatro vuelos.

Paso 3. Reglas. Dos casos: «B es alcanzable desde A si hay un vuelo directo de A a B» (caso base) y «B es alcanzable desde A si hay un vuelo de A a una ciudad C desde la cual B es alcanzable» (caso recursivo). La estructura es la misma de la recursión matemática: un caso base y un caso que se reduce al anterior.

Definición — Argumento de salida: en Prolog no existe «devolver un valor». Cuando se desea un resultado (como el camino de una ruta), se agrega un argumento más a la relación y se deja como variable en la consulta. El motor lo llena al demostrar la relación.

La misma solución en Python. La función que obtiene las rutas debe decidir el orden de exploración, acumular listas de respuestas y combinar los resultados de las llamadas recursivas.

Las tres soluciones, una junto a la otra. Python (orientado a objetos y funcional se parecen en esto), Haskell y Prolog responden la misma pregunta. Ejecútelas y analice las diferencias.

Importante: el programa de vuelos supone que el grafo no tiene ciclos. Si existiera un vuelo de Cancún a Tijuana, la regla recursiva podría dar vueltas indefinidamente. En el tema 5.2 se estudia por qué ocurre y cómo evitarlo; en el 5.3 se verá que Datalog, un subconjunto de Prolog, lo resuelve por su semántica.

6. Caso C: colorear un mapa

Problema. Colorear con tres colores (rojo, verde y azul) cuatro estados del noroeste de México (Baja California, Sonora, Chihuahua y Sinaloa) de modo que dos estados vecinos nunca tengan el mismo color. Las vecindades son: Baja California con Sonora, Sonora con Chihuahua, Sonora con Sinaloa y Chihuahua con Sinaloa.

Paso 1. Individuos y relaciones. Individuos: los tres colores y los cuatro estados. Relación dada: color(C). Relación por definir: mapa(BC, Son, Chih, Sin), que se cumple cuando cada variable es un color y las vecinas difieren.

Paso 3. Reglas. Una sola regla: «hay una coloración válida si cada estado tiene un color y los vecinos tienen colores distintos».

La versión de Python prueba combinaciones: genera las 81 posibles con cuatro ciclos y se queda con las que cumplen las condiciones.

La versión de Prolog describe las condiciones. El motor genera los colores y, cuando una condición falla, retrocede y prueba otro color.

% Los colores disponibles.
color(rojo).
color(verde).
color(azul).

% Una coloración es válida si los estados vecinos tienen colores distintos.
% Vecinos: BC-Son, Son-Chih, Son-Sin, Chih-Sin.
mapa(BC, Son, Chih, Sin) :-
    color(BC), color(Son), BC \= Son,
    color(Chih), Chih \= Son,
    color(Sin), Sin \= Son, Sin \= Chih.

Nota: el programa de Prolog no contiene ningún ciclo y tampoco contiene el orden en que se prueban los colores. Contiene el conocimiento del problema: qué es un color, cuándo dos estados pueden coexistir. La búsqueda la pone el motor. Esta separación entre qué y cómo es el sentido de la frase de Kowalski «algoritmo = lógica + control».

7. De Python a Prolog: tabla de traducción

Muchas dificultades iniciales se resuelven con un diccionario de equivalencias. Conviene tenerlo a la vista mientras se escribe el primer programa.

8. Errores frecuentes al cambiar de paradigma

Error común — buscar el «return»: preguntar «¿dónde devuelvo el resultado?». En Prolog el resultado es un argumento de la relación; se obtiene con una variable en la consulta.

Error común — pensar que = es asignación: en Prolog X = 5 no «guarda» 5 en X: unifica X con 5. Si X ya valía 7, la meta falla (no cambia el valor). El tema 5.1 estudia la unificación.

Error común — escribir el programa como una receta: intentar decir al motor cómo buscar. Se debe describir qué relación se cumple y confiar en el motor; el orden de las metas importa para el rendimiento y la terminación, pero no es el «guion» de la solución.

Error común — confundir mayúsculas y minúsculas: Juan es una variable; juan es una constante. Un error de capitalización cambia por completo el significado de una cláusula.

Error común — creer que false significa «es falso»: significa «no puedo demostrarlo con lo que sé». El programa conoce solo los hechos que contiene (suposición del mundo cerrado).

Error común — olvidar el punto final: toda cláusula termina con .; sin él, la siguiente línea se interpreta como parte de la misma cláusula y aparece un error de sintaxis.

Clasifique las siguientes afirmaciones según el paradigma al que corresponden.

9. Verificación y reformulación

10. Libreta de trabajo

11. Preguntas de reflexión

1. Elija una situación cotidiana con reglas (el reglamento de la escuela, un juego, una receta con restricciones alimentarias) y escríbala como individuos, hechos y reglas. ¿Qué preguntas podría hacerle?
2. En el caso A, ¿qué otras condiciones implícitas del lenguaje natural podrían faltar en una definición de «primo» o de «tío»? Escriba la regla y detecte, con consultas, qué respuestas de más produce.
3. Explique, con sus palabras, por qué una función de Python no puede responder «¿quién es abuelo de Rosa?» con el mismo código que responde «¿de quién es abuelo Juan?».
4. En el caso C, el programa describe las condiciones y el motor realiza la búsqueda. ¿Qué ventajas y qué riesgos tiene delegar la búsqueda en el motor?
5. Describa un problema de otra materia (por ejemplo, horarios de clases sin traslapes) que se exprese de manera natural como hechos, reglas y restricciones.

12. Lecturas recomendadas

• Sebesta, R. (2015). Concepts of programming languages (11th ed.), capítulo sobre programación lógica. Pearson.
• 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; referencia del programa de la unidad de aprendizaje.)
• Kowalski, R. (1979). Algorithm = logic + control. Communications of the ACM, 22(7), 424–436.