Índice

Introducción
Introducción a Prolog „
‰ Hechos y consultas
‰ Reglas. Recursión
‰ Funcionamiento de prolog
„ Sintaxis y semántica del lenguaje
‰ Morfología
Enrique Alfonseca
‰ Unificación
(basado en el libro de Iván Bratko)
‰ Funcionamiento procedimental
Escuela Politécnica Superior, UAM
„ Listas, operadores, aritmética
„ Control del backtracking

Constantes y predicados Hechos

„ Computación simbólica, no numérica. „ Una parte importante de los programas en

„ Resolver problemas expresados en forma de prolog son los hechos, formados por
objetos y relaciones entre ellos. combinación de predicados y constantes:
‰ Constantes: se utilizan para referirse a objetos. progenitor(juan,luis).
Juan
‰ Predicados: expresan relaciones entre los progenitor(juan,maria).
objetos. progenitor(luis,carlos)
Luis Maria
„ Ejemplo: progenitor(luis,laura).
progenitor(juan,luis).
Juan es el progenitor de Luis Carlos Laura

Consultas (I) – Preguntas de sí y no Consultas (II) – Variables

„ Tras compilar un programa en el intérprete, „ Si alguno de los atributos es una variable, el

se pueden realizar consultas: intérprete retornará los valores que puede
?- progenitor(juan, luis). tomar para ser satisfecha.
yes ‰ Su nombre ha de comenzar con mayúscula, o con
guión bajo: _
?- progenitor(juan, laura). ?- progenitor(juan,X).
no X = luis ;
X = maria
?- progenitor(laura,X).
no

1
Consultas (III) – Varias variables Consultas (IV) – Varios
predicados
„ En consultas con varias variables, se retornarán „ Es posible combinar varios predicados en la
todas las combinaciones de valores posibles:
misma consulta. En este caso, para
?- progenitor(X,Y).
satisfacer la consulta deberán satisfacerse
X = juan
Y = luis ;
todos ellos:
X = juan ?- progenitor(juan,Y),
Y = maria ; progenitor(Y,carlos).
X = luis Y = luis ;
Y = carlos ; ?- progenitor(X,luis),
X = luis progenitor(X,maria).
Y = maria ; X = juan

Ejercicios Reglas (I)

Formula en prolog las siguientes consultas: „ Podríamos introducir todos los hechos
„ ¿Quién es el progenitor de Luis? inversos acerca de quién es hijo de quién:
hijo(luis,juan).
hijo(maria,juan).
„ ¿Quién es el abuelo de Laura?
„ Una manera más sencilla sería introducir una
regla:
„ ¿Quién es hermano de Carlos? Para todo X e Y,
Si X es progenitor de Y,
Y es hijo de X

Reglas (II) Reglas (III) – Varios

antecedentes
„ Las reglas en prolog tienen dos „ Cuando el cuerpo de una regla contiene
componentes: cabeza (el consecuente) y varios antecedentes, han de ser todos
cuerpo (el antecedente). satisfechos para que se aplique:
hijo(Y,X) :- progenitor(X,Y). hija(Y,X) :- progenitor(X,Y),hembra(Y).
hijo(Y,X) :- progenitor(X,Y),macho(Y).
„ Una vez introducida la regla en el intérprete, hembra(maria).
podrá utilizarla para responder consultas: macho(luis).
?- hijo(luis,X).
X = juan ?- hija(X,juan).
X = maria

2
Reglas (IV) – Ejemplo Ejercicios
hermano(X,Y) :- Escribe en prolog:
progenitor(Z,X), „ Todo aquel que tiene un hijo es feliz.
progenitor(Z,Y).

?- hermano(luis,H).
„ Define las relaciones “abuelo” y “nieto”
H = luis ;
„ Describe (informalmente) cómo modificarías el predicado
H = maria ;
hermano para que no saliera uno hermano de sí mismo:

Reglas recursivas (I) Reglas recursivas (II)

„ Consideremos la relación “antepasado”: X es antepasado de Y si:

‰ juan es antepasado de luis, maría, carlos y laura. „ O bien X es el padre de Y
‰ luis es antepasado de carlos y laura. „ O bien X es el padre de un antepasado de Y
„ X es antepasado de Y si existe una sucesión
de relaciones de paternidad entre Y y X: antepasado(X,Y) :- progenitor(X,Y).
antepasado(X,Y) :- progenitor(X,Y).
antepasado(X,Y) :- progenitor(X,Z),
antepasado(X,Y) :- progenitor(X,Z), progenitor(Z,Y).
antepasado(X,Y) :- progenitor(X,Z), progenitor(Z,K), antepasado(Z,Y).
progenitor(K,Y).
etc.

Ejercicio Funcionamiento de prolog

„ ¿Es correcta la siguiente definición de „ Para responder una consulta, prolog:

antepasado? ‰ Busca por orden un hecho o regla que unifique
con la consulta (asignando valores a las
antepasado(X,Y) :- progenitor(X,Y). variables, si es preciso).
„ Si es un hecho, termina.
antepasado(X,Y) :- progenitor(Z,Y),
„ Si es una regla, intenta comprobar (de manera
antepasado(X,Z). recursiva) si se cumple el cuerpo de la misma.
„ En el caso de que no se cumpla, hace backtracking, y
continua buscando la siguiente regla que unifique con la
consulta.

3
Funcionamiento de prolog (II) – Funcionamiento de prolog (III)
Ejemplo
Los contenidos de la base de datos son: ?- progenitor(juan,X)
progenitor(juan,luis). Prolog busca el primer hecho o regla con
progenitor(juan,maria). nombre “progenitor”, y cuyo primer
progenitor(luis,carlos) argumento sea el átomo “juan”.
progenitor(luis,laura).
El primer resultado (en la BD) es
antepasado(X,Y) :- progenitor(X,Y).
progenitor(juan,luis).
antepasado(X,Y) :- progenitor(X,Z), por lo que el intérprete devuelve
antepasado(Z,Y). X = luis

Funcionamiento de prolog (IV) Funcionamiento interno de prolog

(V)
Ante la consulta
El segundo resultado (en la BD) es antepasado(juan,X)
progenitor(juan,maria). la primera regla que unifica con la consulta es:
por lo que el intérprete devuelve antepasado(X,Y) :- progenitor(X,Y).
X = maria por tanto, se intenta responder a la consulta
progenitor(juan,X)
cuyo primer resultado sería
No habría más resultados en la base de datos.
progenitor(juan,luis).
por lo que el intérprete devuelve
X = luis

Ejercicio Ejercicio
„ Simula cómo razonaría prolog para devolver Dada la siguiente base de datos (suponiendo que
está definido el predicado “diferentes”):
todos los descendientes de “juan”, utilizando progenitor(juan,carlos).
el predicado “progenitor”. progenitor(juan,maria).
progenitor(carlos,luis).
progenitor(maria,marta).
hermano(X,Y) :- progenitor(Z,X), progenitor(Z,Y),
diferentes(X,Y).
„ Simula la consulta “primo(luis,X).” dadas las
siguientes dos definiciones alternativas:
primo(X,Y) :-
progenitor(A,X),progenitor(B,Y),hermano(A,B).
primo(X,Y) :-
hermano(A,B),progenitor(A,X),progenitor(B,Y).

4
Índice Átomos
„ Introducción „ Los átomos (o constantes simbólicas)
‰ Hechos y consultas pueden tomar los siguientes nombres:
‰ Reglas. Recursión
‰ Cadenas de letras, dígitos y guión bajo,
‰ Funcionamiento de prolog
comenzando por una letra minúscula: juan, x,
„ Sintaxis y semántica del lenguaje el_pais
‰ Morfología
‰ Cadenas de caracteres especiales: + - * / < > = : .
‰ Unificación & _ ~: <===>, --->, .:., ::=, ...
‰ Funcionamiento procedimental
‰ Cadenas de caracteres entre comillas simples:
„ Listas, operadores, aritmética 'El_Salvador', 'Nueva_Guinea', 'Juan'
„ Control del backtracking

Números Variables

„ Enteros: 1, 34, -5, 0 „ Cadenas de letras, dígitos y guión bajo, que

comienzan con letra mayúscula, o con el guión bajo:
„ Reales: 3.14, -0.0035, 100.2
X Result _ Lista_de_tareas _x23
‰ No son muy utilizados, pues Prolog es un
lenguaje de programación simbólica. „ El nombre _ está reservado para variables
"anónimas".
„ El alcance de una variable es en la cláusula
(excepto _):
abuelo(X,Y) :- padre(X,Z), padre(Z,Y).
padre(X,Y) :- hijo(Y,X).
padreEHijo(X) :- padre(X,_), padre(_,X).

Estructuras Ejercicios

„ Son objetos que tienen varios componentes. „ ¿Cuáles de los siguientes son objetos
morfológicamente correctos?
‰ La estructura ha de tener un nombre (functor) ‰ Diana
‰ El functor tiene atributos: los elementos de la ‰ diana
estructura. ‰ _diana
‰ 'Diana'
„ Por ejemplo:
‰ 'Diana se va al sur'
‰ date(1, mayo, 2001): puede usarse para ‰ va(diana, sur)
representar el 1 de mayo de 2001 ‰ 45
‰ date(Dia, mayo, 2001): para representar ‰ 5(x,y)
cualquier día de mayo de 2001. ‰ +(north, west)
‰ three(Black(Cats))

5
Unificación (I) Unificación (II)

„ Dados dos términos, decimos que unifican si: „ Siempre se escoge la unificación más
‰ Son idénticos, o general:
‰ Las variables de los dos términos se pueden date(D,M,2001) date(D1, mayo, A1)
instanciar a objetos de manera que los dos D = D1 D = 1 D = siete
términos lleguen a ser idénticos. M = mayo D1 = 1 D1 = siete
„ Ejemplo: date(D,M,2001) date(D1, mayo, A1) A1 = 2001 M = mayo M = mayo
D = D1 A1 = 2001 A1 = 2001
M = mayo
A1 = 2001

Unificación (III) Ejemplo

„ Las reglas generales de la unificación son: date(D, mes(M), 2001)

‰ Si S y T son constantes, han de ser el mismo date(D1, mes(mayo), A1)
objeto.
date(15, mes(M), Y)
‰ Si S es una variable y T es cualquier cosa,
unifican (S se instancia a T); y viceversa. _________________
‰ Si S y T son estructuras, unifican siempre y date(15,mes(mayo),2001)
cuando: D = D1 = 15
„ El nombre del functor sea el mismo
„ Todos sus atributos unifican
M = may
A1 = Y = 2001

Semántica declarativa Semántica declarativa: ejemplo

„ Los programas en Prolog se pueden „ Objetivo G: abuelo(juan, Nieto).

entender como teorías lógicas: „ Cláusula C:
P :- Q, R abuelo(X,Y) :- padre(X,Z), padre(Z,Y)
Si Q y R son ciertos, P es cierto „ Instancia I:
„ Un objetivo G se cumple si: abuelo(juan,marta) :- padre(juan,luis),
‰ Existe una cláusula C en el programa tal que: padre(luis,marta)
„ Existe una instancia I de C tal que ‰ La cabeza de I es idéntica a G.
1. La cabeza de I es idéntica a G ‰ Los objetivos en el cuerpo de I todos se cumplen.
2. Todos los objetivos en el cuerpo de I son ciertos

6
Semántica procedimental Peligro de bucle infinito

„ Se refiere a la manera en que Prolog „ Si tenemos una cláusula del tipo:

resuelve los objetivos. padre(X,Y) :- padre(X,Y)
‰ Las cláusulas de la BD están en un cierto orden. „ Aunque lógicamente correcta, puede meter al
‰ Se selecciona siempre la primera disponible. Si intérprete en bucle cerrado.
no se llega a la solución, se da marcha atrás
(backtracking) y se busca otra.
‰ El orden de las cláusulas puede afectar a la
ejecución, especialmente a la eficiencia.

Peligro de bucle infinito Índice

„ Definiendo predicados recursivos, hay que „ Introducción

tener cuidado en poner la condición de ‰ Hechos y consultas
‰ Reglas. Recursión
finalización en primer lugar.
pred2(X,Z) :- parent(X,Y), pred2(Y,Z). ‰ Funcionamiento de prolog
pred2(X,Z) :- parent(X,Z). „ Sintaxis y semántica del lenguaje
‰ Morfología
pred3(X,Z) :- parent(X,Z). ‰ Unificación
pred3(X,Z) :- pred3(X,Y), parent(Y,Z). ‰ Funcionamiento procedimental

pred4(X,Z) :- pred4(X,Y), parent(Y,Z).

„ Listas, operadores, aritmética
pred4(X,Z) :- parent(X,Z). „ Control del backtracking
pred2(juan,marta)

Listas (I) Listas (II)

„ Una lista es una secuencia de elementos „ La representación interna es con una

(átomos, estructuras, o listas). estructura llamada ".", con dos elementos:
„ Se representan entre corchetes: cabeza y cola:
.(juana, .(tenis, .(carlos, .(futbol,[]))))
[juana, tenis, carlos, futbol]
„ Una lista vacía se representa como: „ La cola de toda lista puede ser:
‰ Otra lista, usando el functor “.”
[]
‰ La lista vacía [].

7
Listas (III) - Ejemplo Separación de la cabeza y la cola
?- List1 = [a,b,c], „ Se puede especificar explícitamente la
List2 = .(a, .(b, .(c, []))), separación entre la cabeza y la cola,
List3 = [a,List1,List2]. mediante una barra vertical:
List1 = [a,b,c] ?- L = [a,b,c], R = [cabeza|L]
L = [a,b,c]
List2 = [a,b,c]
R = [cabeza,a,b,c]
List3 = [a,[a,b,c],[a,b,c]]
?- L=[a,b,c], R=[el1,el2|L], U=[a|[]]
L = [a,b,c]
R = [el1,el2,a,b,c]
U = [a]

Operaciones con listas (I) Operaciones con listas (II)

„ Miembro de una lista: „ Concatenación:
miembro(X,[X|Tail]). conc([], L, L).
miembro(X, [Head|Tail]) :-
conc([X|L1], L2, [X|L3]) :-
miembro(X, Tail).
conc(L1,L2,L3).
?- miembro(a, [a,b,c]).
yes ?- conc([a,b,c],[1,2,3],L).
?- miembro([b,c], [a,[b,c]]). L = [a,b,c,1,2,3]
yes
?- conc([a,b],L2,[a,b,[],c]).
?- miembro(b, [a,[b,c]]).
L2 = [[],c]
no

Operaciones con listas (II) Operaciones con listas (II)

?- conc(L1,L2,[a,b]). ?- conc(Before,[3,X|After],[1,2,3,4,5]).
L1=[] Before=[1,2]
L2=[a,b] ; X=4
After=[5]
L1=[a]
L2=[b] ;

L1=[a,b]
L2=[] ;
no

8
Ejercicios Operadores (I)

„ Define el predicado "last" que devuelva el „ Aunque las listas son estructuras .(Head,Tail),
último elemento de una lista, de dos se pueden escribir entre corchetes por
maneras: claridad.
‰ Basándose en el predicado "conc" „ Otros predicados, también por claridad, se
‰ Sin utilizarlo. pueden escribir como operadores ([Link]., con
„ Escribe un predicado para añadir un notación infija).
elemento a una lista. „ Ejemplo:
„ Escribe un predicado para eliminar un ‰ +(3, 5)
‰ 3 + 5
elemento de una lista.

Operadores (II) - Aritméticos Operadores (III) - Evaluación

„ Existen operadores predefinidos para „ Los operadores son como cualquier otro
operaciones aritméticas predicado de prolog. Por omisión, no se
+ Suma evalúan.
- Resta ?- X = 1 + 2.
X = 1 + 2
* Multiplicación
/ División „ Se puede forzar la evaluación utilizando el
// División entera operador "is".
?- X is 1 + 2.
** Elevación a potencia X = 3
mod Módulo (resto de división)

Operadores (IV) – Operador "is" Operadores (V) - Ejemplo

„ El argumento izquierdo ha de ser una „ Máximo común divisor de dos números:

variable. gcd(X,X,X).
„ El argumento derecho será una expresión. gcd(X,Y,D) :-
Todas las variables en esa expresión han de X < Y,
estar asociadas a valores. Y1 is Y – X,
„ Los operadores en prolog tienen todos gcd(X, Y1, D).
asociado un número de precedencia. Los de gcd(X,Y,D) :-
menor número se ejecutan antes (ej: ** antes Y < X,
que *, antes que +, antes que is) gcd(Y,X,D).

9
Operadores – Ejercicios Índice

„ Define un predicado que calcule la longitud „ Introducción

de una lista. ‰ Hechos y consultas
‰ Reglas. Recursión
„ Define un predicado que calcule el menor ‰ Funcionamiento de prolog
número dentro de una lista de números. „ Sintaxis y semántica del lenguaje
„ Define un predicado con un único argumento, ‰ Morfología
que devuelva "true" si los elementos en esa ‰ Unificación
lista están ordenados. ‰ Funcionamiento procedimental
„ Listas, operadores, aritmética
„ Control del backtracking

Previniendo el backtracking (I) Ejemplo (I)

„ Cuando prolog tiene que satisfacer una 0 si x < 3

consulta, prueba todas las posibilidades f(x) = 2 si x >= 3 y x < 6
(realizando backtracking) hasta encontrar las
4 si x >= 6
asignaciones de valores que la satisfagan.
„ En el intérprete, si se piden más soluciones, f(X,0) :- X < 3.
se continúan buscando mediante f(X,2) :- 3 =< X, X < 6.
backtracking. f(X,4) :- 6 =< X.

Ejemplo:
?- f(1,Y)

Ejemplo(II) Ejemplo(III)
f(X,0) :- X < 3, !. f(X,0) :- X < 3, !.
f(X,2) :- 3 =< X, X < 6, !. f(X,2) :- X < 6, !.
f(X,4) :- 6 =< X. f(X,4).

:- f(1,Y), 2 < Y. :- f(1,Y).

no Y = 0 ;
:- f(7,Y). Y = 2 ;
Y = 4 Y = 4

10
Corte Corte (II)
c(X) :- p(X),q(X),r(X),!,s(X),t(X),u(X).
„ Sea G el objetivo a satisfacer. c(X) :- v(X).
„ Si entre los antecedentes de G se encuentra a(X) :- b(X),c(X),d(X).
a(maria).
un corte !,
‰ El corte inmediatamente se da por satisfecho ?- a(X).
„ Suponemos que b(X) se cumple.
‰ Todas las alternativas a reglas para G dejan de
„ Suponemos que p,q,r se cumplen, y la X se instancia a un cierto
considerarse valor.
‰ Todas las alternativas a los antecedentes previos „ ! también se cumple (automáticamente)

„ Suponemos que s(X) falla. Entonces:

al corte dejan de considerarse
‰ No se permite intentar otras posibilidades para p(X), q(X) o r(X)
‰ No se permite intentar con la regla c(X) :- v(X).
‰ Sí se permite probar otra posibilidad de a: X se instancia a “maria”

Ejemplos usando el corte (I) Ejemplos usando el corte (II)

max(X, Y, X) :- X >= Y. „ Añadir elementos a una lista
max(X, Y, Y) :- X < Y.
add(X,L,L) :- member(X,L), !.
max(X, Y, X) :- X >= Y, !.
add(X,L,[X|L]).
max(X, Y, Y).
Igual que antes, el tercer argumento no debe estar
Requisito: el tercer argumento no debe estar instanciado. En instanciado al invocar este predicado en el
caso contrario, se pueden obtener resultados no deseados: intérprete.

?- max(3,1,1).
yes

Ejercicios (I) Ejercicios (II)

„ Sea el siguiente programa Prolog: „ La siguiente relación clisifica números en

p(1). positivos o negativos:
p(2) :- !. class(Number, positive) :- Number > 0.
p(3). class(0, zero).
Escribir las respuestas a las siguientes consultas: class(Number, negative) :- Number < 0.
?- p(X). „ Defínelo de manera más eficiente usando
?- p(X), p(Y). cortes.
?- p(X), !, p(Y).

11
Ejercicios (III) Negación como fallo

„ Escribe, con y sin cortes, el procedimiento „ Para evitar la aplicación de una regla, se
“split”, que divide una lista en dos sublistas, puede forzar el fallo con una combinación del
la primera con los números positivos, y la corte, y la constante “fail”.
segunda con los negativos. ‰ “fail” es un objetivo que nunca se satisface.
?- split([3,-1,0,5,-2],[3,0,5],[-1,-2]). „ Por ejemplo, “Todos los pájaros, excepto el
yes avestruz y el pingüino, vuelan”:
vuela(X) :- pinguino(X), !, fail.
vuela(X) :- avestruz(X), !, fail.
vuela(X) :- pajaro(X).

Comprobación de diferencia: Predicado de negación

different(X,X) :- !, fail. not(P) :-
different(X,Y). P, !, fail
;
o bien: true

different(X,Y) :-
Muchos intérpretes de prolog traen el predicado not
X = Y , !, fail
predefinido, con un operador asociado \+
;
vuela(X) :- pajaro(X), \+ pinguino(X),
true. \+ avestruz(X).
donde “true” es un objetivo que siempre se cumple.

Problemas con corte y negación Problema con negación –

Ejemplo
Corte: „ Ejemplo de restaurantes:
„ Los programas ya no corresponden a la buena_comida(el_meson).
definición declarativa: el orden de las caro(el_meson).
cláusulas importa, y puede ser necesario buena_comida(casa_paco).
forzar a que algún argumento sea una razonable(Restaurante) :- \+ caro(restaurante).
variable no instanciada.
?- buena_comida(X), razonable(X).
Negación:
X = casa_paco
„ No corresponde a una negación lógica, sino ?- razonable(X), buena_comida(X).
al hecho de que no hay evidencia para no
demostrar lo contrario.

12
Problema con negación – Causa Negación - Ejercicios
„ En Prolog, una consulta con una variable no hombre(juan).
hombre(carlos). ?- soltero(juan).
instanciada se satisface si hay al menos una ?- soltero(carlos).
mujer(maria).
asignación de valores a la variable que la cumpla: ?- soltero(X).
mujer(laura).
buena_comida(X) -> X = casa_paco ?- sinHijos(juan).
padre(juan,maria).
?- sinHijos(carlos).
„ Al usar la negación, esa consulta pasa a ser cierta padre(juan,carlos). ?- sinHijos(X).
si el argumento de la negación fue falso, es decir, si madre(laura,maria). ?- soltero(X), sinHijos(X).
ninguna asignación posible de valores cumplió la madre(laura,carlos). ?- hombre(X), soltero(X),
fórmula: esposo(juan,laura). sinHijos(X).
not(razonable(X)) = no(existe X tal que X razonable) = esposo(laura,juan).
para todo X, X no es razonable soltero(X) :- \+ esposo(X,Y).
sinHijos(X) :- \+ padre(X,Y), \+ madre(X,Z).

13