Prolog

Prolog, proveniente del francés Programation en Logique,​ es un lenguaje de programación lógico e interpretado, bastante conocido en el medio de investigación en Inteligencia Artificial.

Historia

Se trata de un lenguaje de programación ideado a principios de los años 70 en la universidad de Aix-Marseille por los profesores Alain Colmerauer y Phillipe Roussel. Inicialmente se trataba de un lenguaje totalmente interpretado hasta que, a mediados de los 70, David H.D. Warren desarrolló un compilador capaz de traducir Prolog en un conjunto de instrucciones de una máquina abstracta denominada Warren Abstract Machine, o abreviadamente, WAM. Desde entonces Prolog es un lenguaje semi-interpretado.

Prolog se enmarca en el paradigma de los lenguajes lógicos, lo que lo diferencia enormemente de otros lenguajes más populares tales como Fortran, Pascal, C, Java.

Vuelta atrás (backtracking)

En los lenguajes de programación antes mencionados, las instrucciones se ejecutan normalmente en orden secuencial, es decir, una a continuación de otra, en el mismo orden en que están escritas, que sólo varía cuando se alcanza una instrucción de control (un bucle, una instrucción condicional o una transferencia).

Los programas en Prolog se componen de cláusulas de Horn que constituyen reglas del tipo "modus ponendo ponens", es decir, "Si es verdad el antecedente, entonces es verdad el consecuente". No obstante, la forma de escribir las cláusulas de Horn es al contrario de lo habitual. Primero se escribe el consecuente y luego el antecedente. El antecedente puede ser una conjunción de condiciones que se denomina secuencia de objetivos. Cada objetivo se separa con una coma y puede considerarse similar a una instrucción o llamada a procedimiento de los lenguajes imperativos. En Prolog no existen instrucciones de control. Su ejecución se basa en dos conceptos: la unificación y el backtracking.

Gracias a la unificación, cada objetivo determina un subconjunto de cláusulas susceptibles de ser ejecutadas. Cada una de ellas se denomina punto de elección. Prolog selecciona el primer punto de elección y sigue ejecutando el programa hasta determinar si el objetivo es verdadero o falso.

En caso de ser falso entra en juego el backtracking, que consiste en deshacer todo lo ejecutado situando el programa en el mismo estado en el que estaba justo antes de llegar al punto de elección. Entonces se toma el siguiente punto de elección que estaba pendiente y se repite de nuevo el proceso. Todos los objetivos terminan su ejecución bien en éxito ("verdadero"), bien en fracaso ("falso").

Programación en Prolog

Existen dos tipos de cláusulas: Hechos y Reglas. Una regla es del tipo:

Cabeza :- Cuerpo.

y se lee como "La cabeza es verdad si el cuerpo es verdad". El cuerpo de una regla consiste en llamadas a predicados, que son llamados los objetivos de las reglas. El Predicado ,/2 (es decir, un operador pareado con nombre , ) denota conjunción de objetivos, y ;/2 denota disyunción. Conjunciones y disyunciones pueden sólo aparecer en el cuerpo, no en la cabeza de la regla.

Cláusulas con hechos vacíos son llamados hechos. Un ejemplo de un hecho es:

gato(tom).

que es equivalente a la regla:

gato(tom) :- true.

El predicado integrado true/0 siempre es verdad.

Dado el hecho superior, se puede preguntar:

¿ es tom un gato ?

?- gato(tom).  
Yes

¿ que cosas son gatos ?

?- gato(X).  
X = tom

Debido a la naturaleza relacional de muchos predicados integrados, ellos pueden ser típicamente usados en muchas direcciones. Por ejemplo, length/2 puede ser usado para determinar el tamaño (largo) de una lista) (length(List, L), dada la lista List) así como para generar un esqueleto de lista para un largo dado (length(X, 5)), y también para generar ambos esqueletos de lista y sus tamaños juntos (length(X, L)). Similarmente, append/3 puede ser usado también para unir o anexar dos listas (append(ListA, ListB, X) dadas las listas ListA y ListB) así como para dividir una lista en dos partes (append(X, Y, List), dada una lista List). Por esta razón, un comparativamente pequeño grupo de librería de predicados basta para muchos programas en Prolog. Todos los predicados pueden también ser usados para realizar pruebas unitarias: las consultas pueden ser incrustados en programas y permitir pruebas automáticas de regresión en tiempo de compilación.

Como un lenguaje de propósito general, Prolog también provee variados predicados incorporados para realizar actividades de rutina como entrada/salida, usando gráficas y otras comunicaciones con el sistema operativo. Estos predicados no entregan un significado relacional y son sólo útiles por los efectos colaterales que exhiben en el sistema. Por ejemplo, el predicado write/1 muestra un término en la pantalla.

Expresiones

Prolog cuenta con operadores para la unificación y comparación, sea con evaluación o sea simbólica, como los siguientes:

• X is Y %unificación con evaluación.
• X = Y %unificación simbólica
• X=:=Y %comparación con evaluación
• X == Y %comparación simbólica.

?- X is 3+5.
   X = 8

?- X = 3+5.
   X = 3+5

?- 3+5 =:= 2+6.
   yes

?- 3+5 == 2+6.
   no

?- 3+5 == 3+5.
   yes

Listas

La representación de hechos simples no es lo común en la clasificación de elementos, sino que se agrupan los elementos de un mismo tipo en una lista.

Las listas son colecciones de elementos en Prolog. Una lista se divide en dos partes: Cabeza. Es el primer elemento de la lista. Cola. Es una lista con el resto de los elementos de la lista. La cabeza y la cola de una lista se separan con el símbolo "|".

Ejemplos de Código Prolog

Ejemplo simple

%%
%% declaraciones
%%
padrede('juan', 'maria'). % juan es padre de maria
padrede('pablo', 'juan'). % pablo es padre de juan
padrede('pablo', 'marcela').
padrede('carlos', 'debora').

% A es hijo de B si B es padre de A
hijode(A,B) :- padrede(B,A).
% A es abuelo de B si A es padre de C y C es padre B
abuelode(A,B) :- 
   padrede(A,C), 
   padrede(C,B).
% A y B son hermanos si el padre de A es también el padre de B y si A y B no son lo mismo
hermanode(A,B) :- 
   padrede(C,A) , 
   padrede(C,B), 
   A \== B.        

% A y B son familiares si A es padre de B o A es hijo de B o A es hermano de B
familiarde(A,B) :- 
   padrede(A,B).
familiarde(A,B) :-
   hijode(A,B). 
familiarde(A,B) :- 
   hermanode(A,B).
%%
%% consultas
%%
% juan es hermano de marcela?
?- hermanode('juan', 'marcela').
yes

% carlos es hermano de juan?
?- hermanode('carlos', 'juan').
no

% pablo es abuelo de maria?
?- abuelode('pablo', 'maria').
yes

% maria es abuela de pablo?
?- abuelode('maria', 'pablo').
no

Factorial de un número

% La sintaxis es factorial(N, F) -> Factorial de N es F (el resultado se guarda en F)
factorial(0, 1) :- !.
factorial(N, F) :- N1 is N - 1, factorial(N1, F1), F is N*F1.

%el factorial se llama recursivamente dejando el resultado en F 

Usos de Listas en Prolog

Creación y consulta de listas

plantas([manzana, naranja, limon, espinaca, gardenia, alfalfa,pino]). 

lista([1,2,3]).

?-lista([H|T]).
   H=1 
   T=[2,3]

?-lista([H,J|T]).
   H=1
   J=2
   T=[3]

Longitud de una lista

% Si queremos hallar la longitud de una lista.
% La longitud de una lista vacia es 0.
% La longitud de cualquier lista es la longitud de la cola + 1.

longitud([],0).
longitud([H|T],N):-longitud(T,N0), N is N0 + 1.

?- longitud([a,b,c],L).
   3
?- longitud([a,b,c],4).
   No

Búsqueda de un elemento

% Si queremos determinar si un elemento pertenece a una lista.
% El elemento pertenece a la lista si coincide con la cabeza de la lista.
% El elemento pertenece a la lista si se encuentra en la cola de la lista.

pertenece(X,[X|_]) :- !.
pertenece(X,[_|R]):- pertenece(X,R). 

?- pertenece(b,[a,b,c]).
   Yes
?- pertenece(b,[a,[b,c]]).
   No
?- pertenece([b,c],[a,[b,c]]).
   Yes

Eliminar elemento de una lista

% Si queremos eliminar un elemento de la lista.
% Si X es la cabeza de la lista, la cola T es la lista sin X
% Si X no es la cabeza de la lista, conservamos la cabeza de la lista 
%     como parte de la respuesta y continuamos eliminando X de la cola T.
elimina(X,[X|T],T).
elimina(X,[H|T],[H|T1]):- elimina(X,T,T1).

?- elimina(1,[1,2,3,4],R).
   R = [2,3,4]
?- elimina(1,R,[2,3]).
   R = [1, 2, 3]  
   R = [2, 1, 3]  
   R = [2, 3, 1]  

Concatenar listas

% Si queremos concatenar dos listas lista. 
% Concatenar una lista vacia con L es L.
% Concatenar X|L1 con L2 es poner el primer 
% elemento de la primera lista (X) más la 
% concatenación del resto de la lista (L1) con L2

concatenar([],L,L).
concatenar([X|L1],L2,[X|L3]):-concatenar(L1,L2,L3).

?- concatenar([1,2],[3,4],R).
R = [1, 2, 3, 4].

Comprobar si una lista es la inversa de otra

% Si queremos calcular la inversa de una lista. 
% La inversa de una lista vacia es una lista vacia.
% La inversa de H|T es la inversa de T concatenada con H.

inversa([],[]).
inversa([H|T],L):-  inversa(T,R),  concatenar(R,[H],L).

?- inversa([a,b,c,d],[d,c,b,a]).
   Yes

% Utilizando un parametro acumulador.

inver(L1,L2):-inver(L1,L2,[]).

inver([],L,L).
inver([H|T],L,S):-inver(T,L,[H|S]).

?- inver([a,b,c,d],[d,c,b,a]).
   Yes

Véase también

• Programación Lógica
• Probador de Teoremas Lógicos

Enlaces relacionados

• Ciao-prolog compilador/Intérprete eficience distribuido bajo GPL.
• SWI-PROLOG, compilador/Intérprete de Prolog bajo licencia LGPL
• Strawberry Prolog, compilador libre de Prolog
• Laboratorio de programación lógica de la Universidad Politécnica de Madrid.
• Tutorial gratuito de programación en Prolog
• Curso intermedio (gratuito) de programación en Prolog
• Learn Prolog Now! (tutorial gratuito)