Programación en un lenguaje lógico

Importante: los fragmentos de Python y de Haskell de este tema se ejecutan en el navegador con los intérpretes didácticos del curso. El código de Prolog también. Los fragmentos de SQL y de Datalog "puro" que aparecen como texto no se ejecutan (Datalog sí tiene su propio evaluador en el laboratorio de la sección 9).

Objetivo de aprendizaje

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

1. Definir relaciones sobre listas con recursión estructural (caso base y caso recursivo) y leer programas en Prolog sin ejecutarlos.
2. Usar acumuladores y distinguir una versión de crecimiento cuadrático de otra lineal, midiéndolas con las inferencias.
3. Combinar aritmética y recursión, y reconocer cuándo una relación pierde la reversibilidad.
4. Representar árboles con términos y definir relaciones sobre ellos.
5. Reunir todas las respuestas con findall y explicar en qué se diferencian Prolog y Datalog.
6. Comparar la misma solución en Python, Haskell y Prolog, y argumentar cuándo conviene el enfoque lógico.

Ruta de trabajo del tema

1. Planteamiento inicial

Se desea definir la relación miembro(X, Lista): «X es un elemento de Lista». En Python se escribiría x in lista, que ya viene incluido. En Prolog, member/2 también viene en la biblioteca, pero el objetivo es entender cómo se define.

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

2. Recursión sobre listas

Las listas de Prolog tienen exactamente dos formas, igual que en Haskell: la lista vacía [] o una cabeza seguida de una cola, [H|T]. Una definición recursiva tiene entonces una cláusula por cada forma.

Plantilla de tres preguntas (la misma de la Unidad IV, ahora con relaciones):

1. ¿Qué ocurre con la lista vacía? (caso base)
2. Si la lista tiene cabeza y cola, ¿cómo se relaciona la solución de la cola con la solución de la lista completa? (caso recursivo)
3. ¿Qué argumento adicional hace falta para expresar el resultado? (argumento de salida)

Longitud

% longitud(Lista, N): N es la cantidad de elementos de Lista.
longitud([], 0).
longitud([_|Resto], N) :- longitud(Resto, M), N is M + 1.

La misma idea en los tres paradigmas. Ejecute cada columna y observe las diferencias en la tabla.

Pertenencia y concatenación

% concatenar(Xs, Ys, Zs): Zs es Xs seguida de Ys.
concatenar([], Ys, Ys).
concatenar([X|Xs], Ys, [X|Zs]) :- concatenar(Xs, Ys, Zs).

% miembro(X, Lista): X es un elemento de Lista.
miembro(X, [X|_]).
miembro(X, [_|Resto]) :- miembro(X, Resto).

La pregunta inicial del tema se responde con dos casos: X es miembro si es la cabeza, o si es miembro de la cola. Y como las relaciones no distinguen entradas de salidas, la misma definición genera los elementos cuando X queda sin ligar.

Nota: las relaciones de la biblioteca (member/2, append/3, length/2…) se definen de esta manera. El intérprete del curso incluye una pequeña biblioteca escrita en Prolog; si usted define un predicado con el mismo nombre, el suyo reemplaza al de la biblioteca.

3. Acumuladores

Una solución se puede escribir de dos maneras: dejando que el resultado se construya al regresar de la recursión (como longitud), o acumulándolo en un argumento extra mientras se desciende. La segunda técnica es la misma que, en la Unidad IV, convirtió un ciclo en una recursión con acumulador.

Invertir una lista ilustra la diferencia. La versión ingenua concatena en cada paso; la del acumulador coloca cada elemento al frente de una lista que se va construyendo.

% reversa(Lista, Inversa) usando un acumulador.
reversa(L, R) :- reversa(L, [], R).
reversa([], Acc, Acc).
reversa([X|Xs], Acc, R) :- reversa(Xs, [X|Acc], R).

Medir el trabajo: las inferencias

El motor cuenta cada llamada a un predicado como una inferencia. Es una medida independiente de la velocidad del equipo, equivalente a contar pasos de reducción en Haskell.

El trabajo de la versión ingenua crece con el cuadrado de la longitud (cada paso vuelve a recorrer lo ya invertido); el de la versión con acumulador crece linealmente. Duplicar la lista cuadruplica el trabajo de la primera y solo duplica el de la segunda.

Error común — optimizar sin medir: antes de reescribir un predicado, mida las inferencias de las dos versiones con las mismas consultas. A veces la versión "más elegante" es también la más lenta.

4. Aritmética y recursión

El factorial mezcla recursión y aritmética. Dado que is exige valores ya conocidos, el orden de las metas importa.

% factorial(N, F): F es N!.
factorial(0, 1).
factorial(N, F) :- N > 0, M is N - 1, factorial(M, G), F is N * G.

Importante: factorial(5, F) da F = 120; factorial(N, 120) produce un error de «instanciación» porque N > 0 y M is N - 1 necesitan que N tenga ya un valor. Las relaciones aritméticas de Prolog estándar no son reversibles. Hay extensiones (restricciones, CLP) que lo resuelven, pero están fuera del alcance del curso.

5. Ordenar con quicksort

El algoritmo es el mismo que se programó en Haskell en el tema 4.3: elegir un pivote, repartir el resto en menores y mayores, ordenar cada parte y unir. En Prolog cada reparto es una relación.

% quicksort(Lista, Ordenada)
quicksort([], []).
quicksort([P|Resto], S) :-
    particion(Resto, P, Menores, Mayores),
    quicksort(Menores, SM),
    quicksort(Mayores, SMa),
    append(SM, [P|SMa], S).

% particion(Lista, Pivote, Menores, Mayores)
particion([], _, [], []).
particion([X|Xs], P, [X|Ms], Ns) :- X =< P, particion(Xs, P, Ms, Ns).
particion([X|Xs], P, Ms, [X|Ns]) :- X > P, particion(Xs, P, Ms, Ns).

Nota: el parámetro X =< P se escribe con =<, no <=. Con X < P y X >= P el resultado sería el mismo, salvo para elementos iguales al pivote (que caerían en el otro lado).

6. Árboles

Prolog no necesita declarar tipos de datos: cualquier estructura se puede usar como nodo. Un árbol binario de búsqueda se representa con dos formas de término: nil (el árbol vacío) y arbol(Izquierdo, Valor, Derecho).

% Un árbol es nil o arbol(Izquierdo, Valor, Derecho).
% pertenece(X, Arbol): X está en el árbol.
pertenece(X, arbol(_, X, _)).
pertenece(X, arbol(I, V, _)) :- X < V, pertenece(X, I).
pertenece(X, arbol(_, V, D)) :- X > V, pertenece(X, D).

% inorden(Arbol, Lista): Lista contiene los valores en orden.
inorden(nil, []).
inorden(arbol(I, V, D), L) :-
    inorden(I, LI), inorden(D, LD), append(LI, [V|LD], L).

7. Generar y probar

En la Unidad IV se vio que el paradigma funcional resuelve muchos problemas transformando datos. El paradigma lógico resuelve muchos otros buscando: se describe qué es una solución y el motor explora las posibilidades. La técnica más simple es generar y probar: producir candidatos y descartar los que no cumplen.

% perm(Lista, Permutacion)
perm([], []).
perm(L, [H|T]) :- select(H, L, R), perm(R, T).

El problema de las reinas

Colocar N reinas en un tablero de N × N sin que dos se ataquen. Se representa una solución como una lista de N números: el i-ésimo es la fila de la reina de la columna i. La versión A genera todas las permutaciones y después comprueba cuáles son seguras; la B coloca una reina a la vez y comprueba al colocarla, descartando ramas inútiles tan pronto como es posible.

La diferencia (unas 18 000 inferencias contra unas 3 700 con seis reinas) crece muy rápido con N. El principio es el mismo que en el mapa del tema 5.2: comprobar lo antes posible.

Definición — Generar y probar: estrategia que produce candidatos y luego comprueba una condición. Es simple y correcta, pero costosa. Su mejora consiste en comprobar condiciones parciales durante la generación, como hace la versión B.

8. Reunir todas las respuestas

Con el retroceso, las respuestas aparecen una por una y se pierden. A veces se necesita una lista con todas, por ejemplo para contarlas o para operar con ellas. findall/3 hace exactamente eso:

Definición — findall(Plantilla, Meta, Lista): explora todas las soluciones de Meta y reúne en Lista una copia de Plantilla por cada una. Si no hay soluciones, Lista es [].

Nota: findall y forall están fuera de la lógica pura: examinan el árbol de búsqueda completo de una meta. Son útiles y de uso corriente, pero rompen la lectura declarativa simple del programa.

9. Datalog

Prolog es un lenguaje de propósito general. Datalog es un subconjunto pensado para consultar bases de datos: conserva los hechos y las reglas, pero elimina todo lo que hace impredecible la ejecución.

Definición — Punto fijo: estado en el que aplicar todas las reglas a todos los hechos conocidos ya no produce ningún hecho nuevo. Datalog calcula las consecuencias de un programa repitiendo las reglas hasta alcanzarlo.

Cada regla de Datalog debe ser segura: toda variable de la cabeza aparece en alguna meta del cuerpo. Eso garantiza que el conjunto de hechos deducibles sea finito.

Prolog contra Datalog en un grafo con ciclo

El grafo del laboratorio tiene el ciclo a → b → c → a. Observe la evaluación ascendente: en cada ronda se deducen los hechos nuevos, y en la última ya no aparece ninguno. Después compare con lo que hace la búsqueda de Prolog sobre el mismo programa.

Prolog, que busca de arriba hacia abajo, entra en el ciclo y repite las respuestas indefinidamente; Datalog, que calcula conjuntos, termina siempre y devuelve cada respuesta una sola vez.

Datalog y SQL

La consulta recursiva del grafo se escribe en SQL con una expresión de tabla recursiva. El fragmento es ilustrativo y no se ejecuta en esta página; verifique su sintaxis con el gestor de bases de datos que utilice.

WITH RECURSIVE camino(origen, destino) AS (
    SELECT origen, destino FROM arco
  UNION
    SELECT a.origen, c.destino
    FROM arco a JOIN camino c ON a.destino = c.origen
)
SELECT destino FROM camino WHERE origen = 'a';

Nota: la UNION (en lugar de UNION ALL) elimina los duplicados y es lo que permite que la consulta termine en un grafo con ciclos, igual que el punto fijo de Datalog.

10. La misma solución en tres paradigmas

El curso cierra comparando. Ya se vio longitud, concatenar, quicksort y factorial en los tres lenguajes. Falta uno que sintetiza las diferencias: encontrar el mayor elemento de una lista.

Definición — Estudio comparativo: análisis de una misma solución en varios paradigmas para contrastar sus ventajas y desventajas. Es la evidencia final que pide el programa de la unidad de aprendizaje: el proyecto de esta unidad (Unidad V - Proyecto - Un mismo problema en tres paradigmas) la construye con un problema propio.

11. Errores frecuentes y verificación

Error común — olvidar el caso base: una definición recursiva sin caso base produce una búsqueda infinita. Escriba primero la cláusula de la lista vacía.

Error común — escribir X = Y + 1 esperando un cálculo: = unifica estructuras; para calcular se usa is.

Error común — olvidar que is exige valores ya conocidos: si la variable del lado derecho aún no tiene valor, hay un error de instanciación. Revise el orden de las metas.

Error común — usar findall cuando basta la propia relación: reunir respuestas en una lista pierde la capacidad de preguntar "al revés". Úselo solo cuando de verdad necesite la lista.

Error común — olvidar condiciones excluyentes: si dos cláusulas se aplican al mismo caso (como X =< P y X >= P con X igual a P), aparecen respuestas duplicadas o incorrectas. Escriba condiciones que se excluyan.

12. Libreta de trabajo

13. Preguntas de reflexión

1. Defina en Prolog la relación ultimo(Lista, X) («X es el último elemento»). Pruebe que funciona al revés: ¿qué responde ultimo(L, 3)? ¿Por qué la consulta no termina después de la primera respuesta?
2. Escriba sumatoria(Lista, S) de dos maneras: sin acumulador y con acumulador. Mida las inferencias de ambas con una lista de 20 elementos. ¿Cuál esperaba que fuera más eficiente y qué encontró?
3. Para el problema de las reinas, explique con sus palabras por qué la versión B hace menos trabajo aun cuando describe el mismo problema. ¿Qué otra restricción podría comprobarse antes?
4. Elija un problema que conozca de otra materia (horarios, rutas, reglas de una empresa) y explique si conviene resolverlo con Prolog, con Datalog o con otro paradigma. Justifique con las características de cada uno.
5. Compare la reversibilidad de concatenar con el hecho de que factorial(N, 120) produzca un error. ¿Qué tienen en común y en qué difieren las dos situaciones?

14. Lecturas recomendadas

• Sterling, L., & Shapiro, E. (1994). The art of Prolog (2nd ed.). MIT Press. (Capítulos sobre listas, árboles y programación con acumuladores; disponible en la bóveda: 08-Referencias.)
• Clocksin, W. F., & Mellish, C. S. (2003). Programming in Prolog (5th ed.). Springer. (Capítulos sobre listas, aritmética y estructuras de datos; disponible en la bóveda.)
• Bratko, I. (1986). Prolog programming for artificial intelligence. Addison-Wesley. (Capítulos sobre listas y árboles, y problemas de búsqueda; disponible en la bóveda.)
• Gabbrielli, M., & Martini, S. (2010). Programming languages: principles and paradigms. Springer. (Capítulo sobre el paradigma lógico, incluida la sección sobre Datalog.)
• Ceri, S., Gottlob, G., & Tanca, L. (1989). What you always wanted to know about Datalog (and never dared to ask). IEEE Transactions on Knowledge and Data Engineering, 1(1), 146–166.