Introducción a Prolog, tutorial en español
12/04/2018
Prolog es un lenguaje de programación lógico, quizá uno de los más populares de este paradigma ya que fue el primero en implementarlo, en el año 1972 en Francia.
Durante un tiempo, se creyó que PROLOG supondría la revolución de los lenguajes de programación, siendo uno de los estandartes de los lenguajes de programación de quinta generación. Tanto se creía que Borland, la famosa empresa de compiladores para MS-DOS, tenía Turbo Prolog, junto a Turbo C++, Turbo Pascal, Turbo Assembler y Turbo Basic.
Desafortunadamente, Prolog no triunfó como se esperaba y solo fue usado dentro del mundo de la Inteligencia Artificial. Existe un estándar ISO sobre Prolog (al igual que Ada, C++ y otros lenguajes estandarizados) pero no es demasiado influyente. Tampoco ha habido ningún éxito en alguna de las versiones propuestas para dotarle de orientación a objetos al lenguaje.
Prolog sin embargo ha influenciado a algunos lenguajes como Erlang, que toman algunos aspectos de él.
No obstante, Prolog sigue siendo un lenguaje muy interesante, diferente al resto de lenguajes (tanto imperativos, como funcionales), así que pongámonos a ello.
Actualmente existen varios compiladores de Prolog: SWI Prolog, GNU Prolog, Visual Prolog (al mucha gente no lo considera Prolog de verdad), ...
La mejor versión bajo mi punto de vista es SWI Prolog, que tiene una librería de predicados bastante extensa. Es rápido y permite generar ejecutables nativos (realmente no lo son, pero la máquina virtual de Prolog ocupa muy poco y apenas se nota en el tamaño del ejecutable).
Lo podéis descargar gratuitamente desde su página oficial que como curiosiad, está hecha en SWI Prolog. También está en la paquetería de las distribuciones GNU/Linux habituales.
Para empezar con Prolog voy a tomar un camino distinto de muchos tutoriales y voy a empezar haciendo un programa con Entrada/Salida y que se ejecute como un binario independiente. La potencia de Prolog no está ahí especialmente, pero es un buen punto de partida
Para ello definimos un predicado main de la siguiente forma y lo guardamos en un fichero main.pl.
¿Qué hace el programa? Imprime en pantalla Hola Mundo (write), una nueva línea (nl), lee un string de teclado con el separador \n y lo unifica con la variable Nombre. Esto ya veremos que significa, pero de momento puedes pensar que Nombre es una variable de salida y que a partir de ahí Nombre tiene un valor establecido.
Compilamos con el siguiente comando:
Con esto le decimos a SWI Prolog que el objetivo a demostrar es main y que nos genere un fichero stand_alone (independiente).
Y ejecutamos el fichero ejecutable como uno más.
Ahora que ya sabemos como se generan programas compilados, vamos a introducirnos más en lo que hace especial a Prolog.
Prolog fue diseñado con una terminal interactiva en mente. La idea era que el usuario fuese introduciendo preguntas y el programa en Prolog fuese contestando. Este enfoque, similar a usar un programa desde el REPL de tu lenguaje, no ha acabado cuajando, pero es necesario pasar por él. Más adelante veremos como con SWI Prolog no hace falta usar la terminal. La terminal se abre escribiendo swipl en la línea de comandos:
Vemos un símbolo de interrogación. Eso nos permite saber que estamos en una terminal de Prolog. Podemos escribir write("Hola"). y tener nuestro hola mundo tradicional, aunque no es muy interesante, pero sí es muy interesante que después escribe true. Más adelante veremos por qué.
En Prolog los programas son algo diferentes a lo que estamos acostumbrados. Realmente en Prolog no hay programas sino una base de datos. Un programa se compone de predicados, muy parecidos a los del Cálculo de Predicados. Los predicados aportan información sobre las relaciones entre elementos. Todos los predicados tienen que acabar en punto.
Siguiendo las mismas normas que el cálculo de predicados:
Prolog durante la ejecución, va a intentar demostrar que el predicado es cierto, usando el algoritmo de backtracking. Y ahí está la verdadera potencia de Prolog. Veamos unos ejemplos:
Guarda ese archivo con extensión .pl y ejecuta swipl comida.pl.
Ahora en la terminal podemos hacer preguntas. ¿Es la manzana una fruta? Prolog responde verdadero. ¿Es la pera una fruta? Prolog responde que falso, porque según el archivo comida.pl, no lo es. Prolog no es inteligente, no sabe que significan las palabras, simplemente actúa siguiendo un conjunto de normas formales.
Hemos dicho que Prolog tiene variables. Una variable en Prolog es un marcador de hueco, es algo que no existe, porque no es ninguna constante en específico. Veamos la potencia de las variables con este otro predicado.
En este caso pedimos demostrar fruta(X).. Prolog buscará la primera solución que demuestra el predicado, que es que X valga manzana. Aquí podemos pulsar ENTER y Prolog se para o pulsar N y Prolog busca otra solución. ¿Potente, verdad? Prolog realiza un proceso interno que se llama unificación, es importante saber como funciona para ver que hace Prolog en realidad.
La unificación es un proceso que combina dos predicados en uno que encaja. Para ello buscamos las sustituciones de valores con los que dos predicados son compatibles (realmente solo se pueden modificar las variables). No obstante, Prolog busca siempre el unificador más general, que es aquel que unifica dejando los predicados de forma más genérica posible, es decir, que pueden usarse con más valores.
Espero que esta imagen aclare el concepto de unificación. Básicamente Prolog para intentar demostrar un predicado intentará unificar con otros predicados del programa. Así cuando ponemos por ejemplo comida(manzana) , unifica con comida(X) así que Prolog toma ese predicado para continuar.
Cuando Prolog intenta demostrar un predicado aplica el algoritmo de backtracking. Este algoritmo recorre todas las soluciones posibles pero de forma más inteligente que la fuerza bruta. Backtracking intenta conseguir una solución hasta que un predicado falla, en ese momento, Prolog va hacia atrás y continúa por otra vía que pueda seguir.
Cada predicado es un nodo. Si un predicado falla se vuelve atrás. Esto es muy interesate ya que Prolog técnicamente puede ejecutar código hacia atrás.
Un predicado Prolog sigue esta estructura:
Pero los predicados de Prolog no tienen por qué ser así de simples. Normalmente se usa el operador :- para indicar algo que para que se cumpla la parte de la izquierda, tiene que cumplirse la parte de la derecha antes (en cálculo de predicados es ←).
Por ejemplo, todas las frutas son comidas, así que podemos añadir esto a nuestro archivo.
Y los predicados en Prolog se pueden repetir y repetir y repetir. Prolog siempre intenta demostrar de arriba a abajo, si falla un predicado, prueba con el siguiente más para abajo y termina cuando no hay más predicados que probar. ¡Así que podemos definir comida en base a más predicados!
En Prolog existen varios operadores importantes:
Quiero prestar especial atención en símbolo de igual que no es asignación sino unificación, pero puede parecerse. Estas dos líneas son equivalentes:
Ya que en ambos casos se unifica X con 5.
Veamos un ejemplo de todo esto, ya mucho más realista.
Lo cargamos con swipl restaurante.pl y podemos contestar a las siguientes preguntas de forma sencilla:
¿Qué valor calórico tiene la comida de paella, trucha y flan?
Dime una comidas equilibrada que lleve naranja de postre
¿Cuántas comidas con naranja hay?
Si te fijas en el predicado comidas_con_naranja, es diferente al resto. Esta programado de otra forma. La salida por pantalla se hace con write como ya habíamos visto al principio, write es un predicado que siempre es cierto y en caso de backtracking simplemente pasa. aggregate_all es también otro predicado incluido en SWI Prolog, para en este caso, contar cuantas soluciones tiene el predicado comida(_,_,naranja). X unifica en aggregate_all con el valor que toca (que es una constante, los números son constantes) y en las siguientes sentencias (write), X ha sido sustituido por el valor con el que unificó en aggregate_all.
Por otro lado, ¿qué significa la barra baja? Es una variable anónima. Cuando no usamos una variable en más lugares y no nos interesan sus valores podemos simplemente poner barra baja.
Prolog tiene un tipo de dato más avanzado, las listas. Su tamaño es dinámico y es conveniente distinguir la cabeza de la cola. La cabeza es el primer elemento de una lista, la cola el resto de la lista.
Las listas se crean con corchetes:
sumlist es un predicado de SWI que hace la suma de todos los elementos de una lista.
Con la barra podemos separar cabeza y cola de una lista:
Vamos a ver como se puede implementar sumlist con Prolog de forma sencilla.
El predicado es sencillo, para un caso base de lista vacía, la suma es 0. Para otros casos más complejos separamos la lista en cabeza H y cola T y la suma es N. Esta suma se define como el resultado de sumar T (queda en X) y la cabeza H.
Assert y retract
¿Podemos crear predicados en tiempo real? Claro. Prolog provee de los predicados especiales assert para añadir y retract para eliminar un predicado.
Prolog tiene un operador muy controvertido, el operador de corte, !. Se trata de un operador que permite no volver hacia atrás. Hay que intentar no usarlo, pero muchas veces mejora el rendimiento.
Prolog tiene un gran soporte para la metaprogramación. Assert y Retract son ya formas de metaprogramación, no obstante Prolog tiene muchas más.
call permite ejecutar código Prolog desde Prolog.
setarg permite modificar un término de un predicado y arg unifica una variable con el término de un predicado que queramos. nb_setarg es la versión de setarg que en caso de backtracking no deshace la operación. Un ejemplo de esto lo podemos encontrar en la definición de aggregate_all en la librería de SWI Prolog:
Prolog posee un predicado muy útil para hacer debugging. Es trace y con el predicado que vaya a continuación podremos inspeccionar todas las operaciones del motor de backtracking.
Durante un tiempo, se creyó que PROLOG supondría la revolución de los lenguajes de programación, siendo uno de los estandartes de los lenguajes de programación de quinta generación. Tanto se creía que Borland, la famosa empresa de compiladores para MS-DOS, tenía Turbo Prolog, junto a Turbo C++, Turbo Pascal, Turbo Assembler y Turbo Basic.
Desafortunadamente, Prolog no triunfó como se esperaba y solo fue usado dentro del mundo de la Inteligencia Artificial. Existe un estándar ISO sobre Prolog (al igual que Ada, C++ y otros lenguajes estandarizados) pero no es demasiado influyente. Tampoco ha habido ningún éxito en alguna de las versiones propuestas para dotarle de orientación a objetos al lenguaje.
Prolog sin embargo ha influenciado a algunos lenguajes como Erlang, que toman algunos aspectos de él.
No obstante, Prolog sigue siendo un lenguaje muy interesante, diferente al resto de lenguajes (tanto imperativos, como funcionales), así que pongámonos a ello.
Actualmente existen varios compiladores de Prolog: SWI Prolog, GNU Prolog, Visual Prolog (al mucha gente no lo considera Prolog de verdad), ...
La mejor versión bajo mi punto de vista es SWI Prolog, que tiene una librería de predicados bastante extensa. Es rápido y permite generar ejecutables nativos (realmente no lo son, pero la máquina virtual de Prolog ocupa muy poco y apenas se nota en el tamaño del ejecutable).
Lo podéis descargar gratuitamente desde su página oficial que como curiosiad, está hecha en SWI Prolog. También está en la paquetería de las distribuciones GNU/Linux habituales.
Nuestro primer programa
Para empezar con Prolog voy a tomar un camino distinto de muchos tutoriales y voy a empezar haciendo un programa con Entrada/Salida y que se ejecute como un binario independiente. La potencia de Prolog no está ahí especialmente, pero es un buen punto de partida
Para ello definimos un predicado main de la siguiente forma y lo guardamos en un fichero main.pl.
main :-
write("Hola Mundo"),
nl,
write("¿Cuál es tu nombre? "),
read_string(user_input,['\n'],[],_,Nombre),
write("Hola "),write(Nombre),nl,
halt.
¿Qué hace el programa? Imprime en pantalla Hola Mundo (write), una nueva línea (nl), lee un string de teclado con el separador \n y lo unifica con la variable Nombre. Esto ya veremos que significa, pero de momento puedes pensar que Nombre es una variable de salida y que a partir de ahí Nombre tiene un valor establecido.
Compilamos con el siguiente comando:
swipl --goal=main --stand_alone=true -o main -c main.pl
Con esto le decimos a SWI Prolog que el objetivo a demostrar es main y que nos genere un fichero stand_alone (independiente).Y ejecutamos el fichero ejecutable como uno más.
Ahora que ya sabemos como se generan programas compilados, vamos a introducirnos más en lo que hace especial a Prolog.La terminal de Prolog
Prolog fue diseñado con una terminal interactiva en mente. La idea era que el usuario fuese introduciendo preguntas y el programa en Prolog fuese contestando. Este enfoque, similar a usar un programa desde el REPL de tu lenguaje, no ha acabado cuajando, pero es necesario pasar por él. Más adelante veremos como con SWI Prolog no hace falta usar la terminal. La terminal se abre escribiendo swipl en la línea de comandos:
Vemos un símbolo de interrogación. Eso nos permite saber que estamos en una terminal de Prolog. Podemos escribir write("Hola"). y tener nuestro hola mundo tradicional, aunque no es muy interesante, pero sí es muy interesante que después escribe true. Más adelante veremos por qué.Los programas Prolog
En Prolog los programas son algo diferentes a lo que estamos acostumbrados. Realmente en Prolog no hay programas sino una base de datos. Un programa se compone de predicados, muy parecidos a los del Cálculo de Predicados. Los predicados aportan información sobre las relaciones entre elementos. Todos los predicados tienen que acabar en punto.
Siguiendo las mismas normas que el cálculo de predicados:
- Las constantes empiezan por minúscula
- Las variables empiezan por mayúscula
- Las funciones son constantes seguidas de N teŕminos. Son funciones estrictamente matemáticas.
- Los predicados pueden ser atómicos o compuestos, con operadores lógicos (and, or, implica, etc)
Prolog durante la ejecución, va a intentar demostrar que el predicado es cierto, usando el algoritmo de backtracking. Y ahí está la verdadera potencia de Prolog. Veamos unos ejemplos:
fruta(manzana).
fruta(naranja).
fruta(platano).
Guarda ese archivo con extensión .pl y ejecuta swipl comida.pl.
Ahora en la terminal podemos hacer preguntas. ¿Es la manzana una fruta? Prolog responde verdadero. ¿Es la pera una fruta? Prolog responde que falso, porque según el archivo comida.pl, no lo es. Prolog no es inteligente, no sabe que significan las palabras, simplemente actúa siguiendo un conjunto de normas formales.Hemos dicho que Prolog tiene variables. Una variable en Prolog es un marcador de hueco, es algo que no existe, porque no es ninguna constante en específico. Veamos la potencia de las variables con este otro predicado.
En este caso pedimos demostrar fruta(X).. Prolog buscará la primera solución que demuestra el predicado, que es que X valga manzana. Aquí podemos pulsar ENTER y Prolog se para o pulsar N y Prolog busca otra solución. ¿Potente, verdad? Prolog realiza un proceso interno que se llama unificación, es importante saber como funciona para ver que hace Prolog en realidad.Unificación
La unificación es un proceso que combina dos predicados en uno que encaja. Para ello buscamos las sustituciones de valores con los que dos predicados son compatibles (realmente solo se pueden modificar las variables). No obstante, Prolog busca siempre el unificador más general, que es aquel que unifica dejando los predicados de forma más genérica posible, es decir, que pueden usarse con más valores.
Espero que esta imagen aclare el concepto de unificación. Básicamente Prolog para intentar demostrar un predicado intentará unificar con otros predicados del programa. Así cuando ponemos por ejemplo comida(manzana) , unifica con comida(X) así que Prolog toma ese predicado para continuar.
Backtracking
Cuando Prolog intenta demostrar un predicado aplica el algoritmo de backtracking. Este algoritmo recorre todas las soluciones posibles pero de forma más inteligente que la fuerza bruta. Backtracking intenta conseguir una solución hasta que un predicado falla, en ese momento, Prolog va hacia atrás y continúa por otra vía que pueda seguir.
Cada predicado es un nodo. Si un predicado falla se vuelve atrás. Esto es muy interesate ya que Prolog técnicamente puede ejecutar código hacia atrás.Un predicado Prolog sigue esta estructura:
Predicados avanzados
Pero los predicados de Prolog no tienen por qué ser así de simples. Normalmente se usa el operador :- para indicar algo que para que se cumpla la parte de la izquierda, tiene que cumplirse la parte de la derecha antes (en cálculo de predicados es ←).
Por ejemplo, todas las frutas son comidas, así que podemos añadir esto a nuestro archivo.
fruta(manzana).
fruta(naranja).
fruta(platano).
comida(X) :- fruta(X).
Y los predicados en Prolog se pueden repetir y repetir y repetir. Prolog siempre intenta demostrar de arriba a abajo, si falla un predicado, prueba con el siguiente más para abajo y termina cuando no hay más predicados que probar. ¡Así que podemos definir comida en base a más predicados!
fruta(manzana).
fruta(naranja).
fruta(platano).
carne(pollo).
carne(vaca).
carne(cerdo).
carne(caballo).
comida(paella).
comida(pulpo).
comida(X) :- fruta(X).
comida(X) :- carne(X).
Operaciones
En Prolog existen varios operadores importantes:
- , (coma) AND
- ; (punto y coma) OR
- A = B, se intenta unificar A y B. Devuelve true si funciona
- A \= B es falso si A y B unifican
- A is B, se evalúa B (es decir, se calcula lo que representa) y se unifica con A
- A =:= B , evalúa A, evalúa B y los compara. Verdadero si son iguales
- A =\= B, evalúa A, evalúa B y los compara. Falso si son iguales
- Y muchos otros como =<, >=, >, < que tienen el comportamiento esperado.
- Las operaciones matemáticas solo se pueden introducir en expresiones que vayan a ser evaluadas.
Quiero prestar especial atención en símbolo de igual que no es asignación sino unificación, pero puede parecerse. Estas dos líneas son equivalentes:
X = 5
% y
5 = X
Ya que en ambos casos se unifica X con 5.
Veamos un ejemplo de todo esto, ya mucho más realista.
%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Programa restaurante %
%%%%%%%%%%%%%%%%%%%%%%%%%%%
% menu
entrada(paella).
entrada(gazpacho).
entrada(pasta).
carne(filete_de_cerdo).
carne(pollo_asado).
pescado(trucha).
pescado(bacalao).
postre(flan).
postre(nueces_con_miel).
postre(naranja).
% Valor calorico de una racion
calorias(paella, 200).
calorias(gazpacho, 150).
calorias(pasta, 300).
calorias(filete_de_cerdo, 400).
calorias(pollo_asado, 280).
calorias(trucha, 160).
calorias(bacalao, 300).
calorias(flan, 200).
calorias(nueces_con_miel, 500).
calorias(naranja, 50).
% plato_principal(P) P es un plato principal si es carne o pescado
plato_principal(P):- carne(P).
plato_principal(P):- pescado(P).
% comida(Entrada, Principal, Postre)
comida(Entrada, Principal, Postre):-
entrada(Entrada),
plato_principal(Principal),
postre(Postre).
% Valor calorico de una comida
valor(Entrada, Principal, Postre, Valor):-
calorias(Entrada, X),
calorias(Principal, Y),
calorias(Postre, Z),
sumar(X, Y, Z, Valor).
% comida_equilibrada(Entrada, Principal, Postre)
comida_equilibrada(Entrada, Principal, Postre):-
comida(Entrada, Principal, Postre),
valor(Entrada, Principal, Postre, Valor),
menor(Valor, 600).
% Conceptos auxiliares
sumar(X, Y, Z, Res):-
Res is X + Y + Z. % El predicado "is" se satisface si Res se puede unificar
% con el resultado de evaluar la expresion X + Y + Z
menor(X, Y):-
X < Y. % "menor" numerico
dif(X, Y):-
X =\= Y. % desigualdad numerica
% cuantas comidas llevan naranja de postre
%
comidas_con_naranja :-
write("Comidas con naranja: "),
aggregate_all(count,comida(_,_,naranja),X),
write(X),
nl.
Lo cargamos con swipl restaurante.pl y podemos contestar a las siguientes preguntas de forma sencilla:
¿Qué valor calórico tiene la comida de paella, trucha y flan?
valor(paella,trucha,flan,N).
Dime una comidas equilibrada que lleve naranja de postre
comida_equilibrada(X,Y,Z),Z=naranja.
¿Cuántas comidas con naranja hay?comidas_con_naranja.
Variables anónimas y predicados predefinidos
Si te fijas en el predicado comidas_con_naranja, es diferente al resto. Esta programado de otra forma. La salida por pantalla se hace con write como ya habíamos visto al principio, write es un predicado que siempre es cierto y en caso de backtracking simplemente pasa. aggregate_all es también otro predicado incluido en SWI Prolog, para en este caso, contar cuantas soluciones tiene el predicado comida(_,_,naranja). X unifica en aggregate_all con el valor que toca (que es una constante, los números son constantes) y en las siguientes sentencias (write), X ha sido sustituido por el valor con el que unificó en aggregate_all.
Por otro lado, ¿qué significa la barra baja? Es una variable anónima. Cuando no usamos una variable en más lugares y no nos interesan sus valores podemos simplemente poner barra baja.
Listas en Prolog
Prolog tiene un tipo de dato más avanzado, las listas. Su tamaño es dinámico y es conveniente distinguir la cabeza de la cola. La cabeza es el primer elemento de una lista, la cola el resto de la lista.
Las listas se crean con corchetes:
X = [1,2,3,4,5],
sumlist(X,N).
sumlist es un predicado de SWI que hace la suma de todos los elementos de una lista.
Con la barra podemos separar cabeza y cola de una lista:
[1,2,3,4] = X,
[H|T] = X.
Implementando sumlist
Vamos a ver como se puede implementar sumlist con Prolog de forma sencilla.
sumar([],0).
sumar([H|T],N) :-
sumar(T,X),
N is X+H.
El predicado es sencillo, para un caso base de lista vacía, la suma es 0. Para otros casos más complejos separamos la lista en cabeza H y cola T y la suma es N. Esta suma se define como el resultado de sumar T (queda en X) y la cabeza H.
Assert y retract
¿Podemos crear predicados en tiempo real? Claro. Prolog provee de los predicados especiales assert para añadir y retract para eliminar un predicado.
Operador de corte
Prolog tiene un operador muy controvertido, el operador de corte, !. Se trata de un operador que permite no volver hacia atrás. Hay que intentar no usarlo, pero muchas veces mejora el rendimiento.
Metaprogramación
Prolog tiene un gran soporte para la metaprogramación. Assert y Retract son ya formas de metaprogramación, no obstante Prolog tiene muchas más.
call permite ejecutar código Prolog desde Prolog.
setarg permite modificar un término de un predicado y arg unifica una variable con el término de un predicado que queramos. nb_setarg es la versión de setarg que en caso de backtracking no deshace la operación. Un ejemplo de esto lo podemos encontrar en la definición de aggregate_all en la librería de SWI Prolog:
aggregate_all(count, Goal, Count) :-
!,
aggregate_all(sum(1), Goal, Count).
aggregate_all(sum(X), Goal, Sum) :-
!,
State = state(0),
( call(Goal),
arg(1, State, S0),
S is S0 + X,
nb_setarg(1, State, S),
fail
; arg(1, State, Sum)
).
Debug con trace
Prolog posee un predicado muy útil para hacer debugging. Es trace y con el predicado que vaya a continuación podremos inspeccionar todas las operaciones del motor de backtracking.