Adrianistán

Supertutorial de Prolog: aprende Prolog en español

29/08/2020

Si estás aquí es porque has decidido aprender Prolog o por lo menos, te ha entrado la curiosidad sobre este lenguaje del paradigma lógico. ¡Sabia elección! En este artículo y los siguientes (enlazados al final) podrás aprender todo lo básico de Prolog.

Antes de nada, avisar que ya tenía un tutorial de Prolog aquí, sin embargo, creo que comete varias malas prácticas. En vez de editarlo, prefiero empezar de cero y además explicar más cosas.

Hola Mundo

Antes de entrar en la teoría, abre tu editor y copia/pega lo siguiente a un fichero llamado socrates.pl:


human(socrates).
mortal(X) :- human(X).

La explicación es sencilla. En la primera línea afirmamos que socrates es humano, en la segunda afirmamos que para que X sea mortal, antes tiene que ser humano. Todo esto lo detallaré más adelante.

Ahora necesitarás un intérprete de Prolog. El más popular y el que actualmente recomiendo es SWI-Prolog disponible para Windows, Mac, Linux y más.

Con SWI-Prolog instalado ejecuta desde un terminal:


swipl socrates.pl

Ahora podemos realizar consultas. Prolog es un lenguaje inicialmente diseñado en base a consultas lógicas. Vamos a pedir a Prolog que nos diga si socrates es humano.


?- human(socrates).
true.

A lo que responde true, es decir, es cierto, socrates es humano.

¿socrates es mortal?


?- mortal(socrates).
true.

¿Y adrian?


?- mortal(adrian).
false.

¿Cuántos humanos hay?


?- human(X).
   X = socrates.

Solo socrates. ¿Y cuantos mortales?


?- mortal(X).
   X = socrates.

Y si queremos un hola mundo más clásico, podemos usar write y nl.


?- write('Hola Mundo'), nl.
Hola Mundo
   true.

Historia de Prolog

Prolog (PROgrammation en LOGique) nació en 1972 en la Universidad de Provenza en la ciudad francesa de Marsella (mismo año que C). Diseñado por Alan Colmerauer y Philip Roussel para trabajar en inteligencia artificial, siempre ha estado ligado a este campo. En 1995 fue estandarizado, bajo ISO (como C++, Ada o Fortran). Durante este tiempo se han creado muchas implementaciones. Algunas las puedes ver en Universo Prolog

Sintaxis de Prolog

La sintaxis de Prolog es muy simple. Solo existen tres elementos:

Los dos últimos son elementos excepcionales. Un comentario empieza por el símbolo % seguido del comentario. Los comentarios son textos que se eliminan al procesar la entrada y son útiles para anotar cosas. Los quasiquotes son elementos que permiten introducir sintaxis diferente a la de Prolog en Prolog (HTML, JSON, LISP, JavaScript, ...) pero es algo bastante avanzado.

Los términos, son entonces, el 95% del código Prolog. Estos llevan un punto al final si no forman parte de ningún otro término de forma recursiva. Los términos se dividen a su vez en:

Los constantes son términos que pueden ser átomos, números (y en algunas implementaciones también hay strings). Los átomos son cadenas de texto que empiezan por letra minúscula o llevan comillas simples. Los átomos son elementos inmutables que representan algo. La cualidad del átomo es que solo pueden ser iguales a ellos mismos. Los números son bastante explicativos, cadenas de texto compuestas de dígitos. Prolog no distingue entre ints, floats, etc y muchas implementaciones disponen de precisión arbitraria en los números. Los strings empiezan por comillas dobles y representan cadenas de texto "manipulables". Saber donde se usa string y donde atom en sistemas que usan ambos elementos es algo que se aprende con la práctica.

Las variables son cadenas de texto que empiezan por una letra mayúscula. El funcionamiento de las variables es ligeramente diferente al de los lenguajes de programación tradicionales. Una variable puede entenderse como la solución de un problema (que será un término). Al principio del programa, cuando todavía no se han recorrido condiciones del problema, la variable no estará ligada, eso querrá decir, que puede ser cualquier cosa todavía. Según vaya avanzando el programa, Prolog unificará (más adelante esto) la variable con algún otro término y puede que la variable acabe ligada, es decir, a partir de ese momento, se comporta como si fuese el otro término. Esto sería, en esencia, añadir una restricción sobre la solución.

En el apartado de unificación veremos esto más en detalle.

Los compuestos son términos recursivos, se componen de un átomo, que llamaremos functor, y entre paréntesis y separados por comas, más términos. Esto puede parecer una llamada a una función, pero no. En Prolog no hay funciones. Simplemente es un término compuesto varios términos dentro de él.


% Un comentario
socrates. % Un átomo
15. % Un número
libro(don_quijote, cervantes). % Un compuesto. libro es functor, don_quijote y cervantes son los otros términos.
Variable. % Una variable
serie('Los Simpson', autor(Nombre, Apellido)). % Un compuesto más complejo

Al conjunto de compuestos con el mismo functor se le llama predicado y tiene una aridad, que es el número de términos que tiene entre paréntesis.

Además de esto, los términos pueden llevar asociado un cuerpo. El cuerpo es un conjunto de predicados que tienen que ser verdaderos para poder afirmar que el término es verdadero. A esto se le llama regla. Si el término no lleva cuerpo, se dice que es un hecho y es verdadero siempre.


human(socrates). % Afirmamos que socrates es humano (hecho)
mortal(X) :- human(X). % Afirmamos que para que X sea mortal, antes tiene que ser humano (regla)
% Otra forma de verlo, todos los humanos son mortales

Semántica de Prolog

Al revisar la sintaxis ha surgido un poco algo de la semántica, es decir, ¿qué significa lo que hacemos? Los programas Prolog son una base de conocimiento (como una base de datos pero más potente). Esta base de conocimiento es dinámica y el código fuente es simplemente el estado inicial de la base de "datos".

Inicialmente Prolog se diseña como un lenguaje orientado a consultas, como SQL, donde tenemos un terminal donde ir escribiendo pequeñas sentencias.

En el terminal escribimos predicados para ver si son ciertos o no, dado el conocimiento del programa. Cuando introducimos variables, busca valores para las variables que cumplan el predicado.

Prolog implementa un algoritmo de búsqueda (backtracking) por nosotros.

Backtracking

El algoritmo de backtracking es bastante simple y consiste en lo siguiente:

  1. Busca algún compuesto con el mismo functor, en la base de conocimiento (de arriba a abajo).
  2. Si es un hecho, unifica con él. (explicación más adelante)
  3. Si es una regla, pasa a tratar de demostrar el cuerpo de la regla.
  4. Si llega a un punto en el que no puede continuar, falla. Vuelve hacia atrás, deshace todas las unificaciones realizadas y si hay algún punto de elección, toma otra ruta.

Podemos pensar que el algoritmo va haciendo un árbol intentando encontrar algo en la base de conocimiento que satisfaga el predicado de entrada.

O viendo cada predicado, podemos ver como puede pasar Prolog en un sentido hacia delante o hacia atrás.

Hola mundo, otra vez

Ahora que sabemos todo esto de como funciona Prolog por debajo podemos volver a ejecutar el Hola Mundo del principio y tratar de ver como funciona. Para ello te recomiendo activar el modo trace, que nos deja ver que va haciendo Prolog paso a paso. Escribe trace antes de ejecutar la consulta. Por ejemplo: 


?- trace, mortal(X).
   Call: (11) mortal(_6364) ? creep
   Call: (12) human(_6364) ? creep
   Exit: (12) human(socrates) ? creep
   Exit: (11) mortal(socrates) ? creep
X = socrates.

Unificación

… o ¿pueden juntarse dos expresiones en una sin contradecirse?

En Prolog, la operación más básica es la unificación, que podemos realizar mediante el operador = pero que igualmente se realiza cuando busca en la base de conocimiento. La idea es muy simple, ¿podemos asumir que dos términos pueden juntarse en uno solo? Para ello se realiza lo siguiente.

Veamos algunos ejemplos:


?- a = b.
   false.
?- a = a.
   true.
?- a = X.
   X = a.
?- X = Y.
   X = Y.
?- 4+5=3+6.
   false.
?- book(Name, Author) = book('Don Quijote', 'Cervantes').
   Name = 'Don Quijote', Author = 'Cervantes'.

Es interesante prestar atención a que que una cosa esté en un lado u otro es indiferente. Además, es interesante como 4+5=3+6 no es true. Esto es debido a que Prolog, con unificación simplemente, compara términos pero no ejecuta operaciones aritméticas. Así pues 4+5 no es el mismo término que 3+6, ya que se escriben de forma diferente.

Operadores

Ya hemos visto como funciona el operador unificación (=). Veamos el resto de los operadores de Prolog:

Ejemplo: rutas aéreas

Vamos a ver un ejemplo más avanzado de programa Prolog. Se trata de un programa que tiene un listado de vuelos configuradas, con un precio entre dos aeropuertos. Vamos a hacer un programa que nos calcule cuanto nos costaría hacer el viaje de ida y vuelta (si es que es posible).


vuelo(mad,bcn,200).
vuelo(bcn,mad,100).

idavuelta(X, Y, Precio) :-
    vuelo(X, Y, P1),
    vuelo(Y, X, P2),
    Precio is P1+P2.

En el terminal de Prolog:


?- idavuelta(mad,bcn,X).
   X = 300.
?- idavuelta(bcn,mad,X).
   X = 300.
?- idavuelta(Origen,Destino,Precio).
   Origen = mad, Destino = bcn, Precio = 300
;  Origen = bcn, Destino = mad, Precio = 300.
?- idavuelta(mad,nyc,X).
   false.

Vamos a añadir un poco más de complejidad al programa. En la vida real, no existen vuelos directos que conecten todas las ciudades con todas, muchas veces hay que hacer escala. Por ello vamos a añadir que vuelo tenga una regla para vuelos que realizan escalas.


vuelo(mad,bcn,200).
vuelo(bcn,mad,100).
vuelo(bcn,vll,30).
vuelo(vll,bcn,30).
vuelo(mad,vlc,50).
vuelo(vlc,mad,50).

vuelo(X, Y, Precio) :-
    vuelo(X, Z, P1),
    vuelo(Z, Y, P2),
    Precio is P1+P2.

idavuelta(X, Y, Precio) :-
    vuelo(X, Y, P1),
    vuelo(Y, X, P2),
    Precio is P1+P2.

Hemos añadido vuelos de ida y vuelta entre BCN y VLL y entre MAD y VLC. Ahora podemos preguntar por el precio del vuelo entre VLL y VLC, que lógicamente será, VLL->BCN->MAD->VLC (30+100+50). También el precio de ida y vuelta que será 180 más la vuelta, que son 280.


?- vuelo(vll, vlc, X).
   X = 180
?- idavuelta(vll, vlc, X).
   X = 460

Aunque, claro, estas soluciones no son únicas. Podemos dar vueltas entre MAD y BCN el tiempo que queramos. Por eso Prolog, nos ofrece más soluciones, que podemos obtener presionando la letra N


?- vuelo(vll, vlc, X).
   X = 180
;  X = 480
;  X = 780
;  X = 1080
;  X = 1380
;  X = 1680
;  X = 1980
;  X = 2280
;  X = 2580
;  X = 2880
;  X = 3180
;  X = 3480
;  X = 3780
;  X = 4080
;  ...

Listas en Prolog

La lista en Prolog es una estructura de datos básica. Es una lista enlazada, implementada mediante términos compuestos, pero a la que se le aplica azúcar sintáctico para que sea más legible. Las listas se definen con corchetes y se puede usar la barra vertical | para separar el primer elemento del resto. Además existen diversos predicados estándar para trabajar con listas como length/2 (longitud de una lista), member/2 (pertenencia a una lista), append/3 (combinar listas), nth0 (elemento N contando desde cero en una lista), nth1 (elemento N contando desde 1 en una lista).

Como son predicados, pueden trabajar en varios sentidos. Por ejemplo con length/2:

Veamos algunos ejemplos más:


?- length([a,b,c], N).
   N = 3.
?- length(X, 5).
   X = [_A,_B,_C,_D,_E].
?- member(X, [socrates,platon,aristoteles]).
   X = socrates
;  X = platon
;  X = aristoteles
?- member(platon, [socrates, platon, aristoteles]).
   true
?- append([a,b],[c,d], X).
   X = "abcd".
?- append([a,b],X,[a,b,c,d]).
   X = "cd".
?- append(X,Y,[a,b,c,d]).
   X = [], Y = "abcd"
?- append(X,Y,[a,b,c,d]).
   X = [], Y = "abcd"
;  X = "a", Y = "bcd"
;  X = "ab", Y = "cd"
;  X = "abc", Y = "d"
;  X = "abcd", Y = []

Un ejemplo de uso del operador | es el siguiente, para implementa la suma de toda una lista de números.


suma([], 0).
suma([H|T], S) :-
    suma(T, S1),
    S is H+S1.

H es una variable que unifica con el primer elemento de la lista, mientras que T unifica con el resto de la lista. Esto lo podemos usar como:


?- suma([1,2,3,4], X).
X = 10.

Metapredicados

Por último, conviene repasar algunos metapredicados de Prolog. Los metapredicados son predicados que trabajan con otros predicados y son extremadamente útiles.

Hagamos un ejemplo con assertz y retractall:


?- human(X).
false.
?- assertz(human(socrates)).
   true.
?- assertz(human(platon)).
   true.
?- human(X).
   X = socrates
;  X = platon.
?- retractall(human(X)).
?- human(X).
   false.

Ahora veamos un ejemplo del resto de predicados. Teniendo este fichero:


parent(juancarlos, felipe).
parent(juancarlos, cristina).
parent(juancarlos, elena).

married(felipe).
married(cristina).
divorced(elena).

Podemos ejecutar los siguientes comandos:


?- forall(parent(juancarlos, X), married(X)).
   false.
?- forall(parent(juancarlos, X), (married(X);divorced(X))).
   true.
?- findall(X, married(X), Married).
   Married = [felipe,cristina].
?- maplist(write, [felipe, cristina]).
felipecristina   true

Continúa...

Con esto ya tienes suficiente como para realizar programas simples y medianos en Prolog, ya que, en esencia, Prolog es un lenguaje compacto. Sin embargo el lenguaje tiene muchas más cosas interesantes y que merece la pena ver, he aquí algunos enlaces de interés dentro de este blog:

Tags: prolog programacion tutorial