Story Transcript
Índice
Introducción a Prolog
Introducción
Constantes y predicados
Computación simbólica, no numérica. Resolver problemas expresados en forma de objetos y relaciones entre ellos.
Morfología Unificación Funcionamiento procedimental
Listas, operadores, aritmética Control del backtracking
Hechos
Una parte importante de los programas en prolog son los hechos, formados por combinación de predicados y constantes:
Constantes: se utilizan para referirse a objetos. Predicados: expresan relaciones entre los objetos.
Juan
Luis
Juan es el progenitor de Luis
Carlos Laura
Tras compilar un programa en el intérprete, se pueden realizar consultas: ?- progenitor(juan, luis). yes ?- progenitor(juan, laura). no
progenitor(juan,luis). progenitor(juan,maria).
Ejemplo: progenitor(juan,luis).
Consultas (I) – Preguntas de sí y no
Sintaxis y semántica del lenguaje
Enrique Alfonseca (basado en el libro de Iván Bratko) Escuela Politécnica Superior, UAM
Hechos y consultas Reglas. Recursión Funcionamiento de prolog
Maria
progenitor(luis,carlos) progenitor(luis,laura).
Consultas (II) – Variables
Si alguno de los atributos es una variable, el intérprete retornará los valores que puede tomar para ser satisfecha. Su nombre ha de comenzar con mayúscula, o con guión bajo: _ ?- progenitor(juan,X). X = luis ; X = maria ?- progenitor(laura,X). no
1
Consultas (III) – Varias variables
En consultas con varias variables, se retornarán todas las combinaciones de valores posibles: ?- progenitor(X,Y). X = juan Y = luis ; X = juan Y = maria ; X = luis Y = carlos ; X = luis Y = maria ;
Consultas (IV) – Varios predicados
Es posible combinar varios predicados en la misma consulta. En este caso, para satisfacer la consulta deberán satisfacerse todos ellos: ?- progenitor(juan,Y), progenitor(Y,carlos). Y = luis ; ?- progenitor(X,luis), progenitor(X,maria). X = juan
Ejercicios
Reglas (I)
Formula en prolog las siguientes consultas: ¿Quién es el progenitor de Luis?
hijo(luis,juan). hijo(maria,juan).
¿Quién es el abuelo de Laura?
¿Quién es hermano de Carlos?
Reglas (II)
Las reglas en prolog tienen dos componentes: cabeza (el consecuente) y cuerpo (el antecedente). hijo(Y,X) :- progenitor(X,Y).
Una vez introducida la regla en el intérprete, podrá utilizarla para responder consultas: ?- hijo(luis,X). X = juan
Podríamos introducir todos los hechos inversos acerca de quién es hijo de quién:
Una manera más sencilla sería introducir una regla: Para todo X e Y, Si X es progenitor de Y, Y es hijo de X
Reglas (III) – Varios antecedentes
Cuando el cuerpo de una regla contiene varios antecedentes, han de ser todos satisfechos para que se aplique: hija(Y,X) :- progenitor(X,Y),hembra(Y). hijo(Y,X) :- progenitor(X,Y),macho(Y). hembra(maria). macho(luis). ?- hija(X,juan). X = maria
2
Reglas (IV) – Ejemplo hermano(X,Y) :progenitor(Z,X), progenitor(Z,Y). ?- hermano(luis,H). H = luis ; H = maria ;
Reglas recursivas (I)
Consideremos la relación “antepasado”:
juan es antepasado de luis, maría, carlos y laura. luis es antepasado de carlos y laura.
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,Z), progenitor(Z,Y). antepasado(X,Y) :- progenitor(X,Z), progenitor(Z,K), progenitor(K,Y). etc.
Ejercicio
¿Es correcta la siguiente definición de antepasado?
antepasado(X,Y) :- progenitor(X,Y). antepasado(X,Y) :- progenitor(Z,Y), antepasado(X,Z).
Ejercicios Escribe en prolog: Todo aquel que tiene un hijo es feliz.
Define las relaciones “abuelo” y “nieto”
Describe (informalmente) cómo modificarías el predicado hermano para que no saliera uno hermano de sí mismo:
Reglas recursivas (II) X es antepasado de Y si: O bien X es el padre de Y O bien X es el padre de un antepasado de Y antepasado(X,Y) :- progenitor(X,Y). antepasado(X,Y) :- progenitor(X,Z), antepasado(Z,Y).
Funcionamiento de prolog
Para responder una consulta, prolog:
Busca por orden un hecho o regla que unifique con la consulta (asignando valores a las variables, si es preciso).
Si es un hecho, termina. Si es una regla, intenta comprobar (de manera 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) – Ejemplo
Funcionamiento de prolog (III)
Los contenidos de la base de datos son:
?- progenitor(juan,X) Prolog busca el primer hecho o regla con nombre “progenitor”, y cuyo primer argumento sea el átomo “juan”.
progenitor(juan,luis). progenitor(juan,maria). progenitor(luis,carlos) progenitor(luis,laura). antepasado(X,Y) :- progenitor(X,Y). antepasado(X,Y) :- progenitor(X,Z), antepasado(Z,Y).
El primer resultado (en la BD) es progenitor(juan,luis). por lo que el intérprete devuelve X = luis
Funcionamiento de prolog (IV)
Funcionamiento interno de prolog (V) Ante la consulta
El segundo resultado (en la BD) es progenitor(juan,maria).
antepasado(juan,X)
por lo que el intérprete devuelve X = maria
antepasado(X,Y) :- progenitor(X,Y).
la primera regla que unifica con la consulta es: por tanto, se intenta responder a la consulta progenitor(juan,X)
No habría más resultados en la base de datos.
Ejercicio
Simula cómo razonaría prolog para devolver todos los descendientes de “juan”, utilizando el predicado “progenitor”.
cuyo primer resultado sería progenitor(juan,luis). por lo que el intérprete devuelve X = luis
Ejercicio Dada la siguiente base de datos (suponiendo que está definido el predicado “diferentes”): progenitor(juan,carlos). 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
Introducción
Morfología Unificación Funcionamiento procedimental
Listas, operadores, aritmética Control del backtracking
Números
Hechos y consultas Reglas. Recursión Funcionamiento de prolog
Los átomos (o constantes simbólicas) pueden tomar los siguientes nombres:
Cadenas de letras, dígitos y guión bajo, comenzando por una letra minúscula: juan, x, el_pais
Cadenas de caracteres especiales: + - * / < > = : . & _ ~: , --->, .:., ::=, ...
Cadenas de caracteres entre comillas simples: 'El_Salvador', 'Nueva_Guinea', 'Juan'
Sintaxis y semántica del lenguaje
Átomos
Enteros: 1, 34, -5, 0 Reales: 3.14, -0.0035, 100.2
No son muy utilizados, pues Prolog es un lenguaje de programación simbólica.
Variables
Cadenas de letras, dígitos y guión bajo, que comienzan con letra mayúscula, o con el guión bajo: X Result _ Lista_de_tareas _x23
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
Son objetos que tienen varios componentes.
La estructura ha de tener un nombre (functor) El functor tiene atributos: los elementos de la estructura.
Por ejemplo:
date(1, mayo, 2001): puede usarse para representar el 1 de mayo de 2001 date(Dia, mayo, 2001): para representar cualquier día de mayo de 2001.
Ejercicios
¿Cuáles de los siguientes son objetos morfológicamente correctos?
Diana diana _diana 'Diana' 'Diana se va al sur' va(diana, sur) 45 5(x,y) +(north, west) three(Black(Cats))
5
Unificación (I)
Dados dos términos, decimos que unifican si:
Unificación (II)
Son idénticos, o Las variables de los dos términos se pueden instanciar a objetos de manera que los dos términos lleguen a ser idénticos.
Ejemplo: date(D,M,2001)
date(D,M,2001)
D = D1 M = mayo A1 = 2001 A1 =
date(D1, mayo, A1)
D = D1 M = mayo A1 = 2001
Unificación (III)
Las reglas generales de la unificación son:
Si S y T son constantes, han de ser el mismo objeto. 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 cuando:
El nombre del functor sea el mismo Todos sus atributos unifican
Semántica declarativa Los programas en Prolog se pueden entender como teorías lógicas:
P :- Q, R Si Q y R son ciertos, P es cierto
Un objetivo G se cumple si:
Existe una cláusula C en el programa tal que:
Existe una instancia I de C tal que 1. 2.
La cabeza de I es idéntica a G Todos los objetivos en el cuerpo de I son ciertos
Siempre se escoge la unificación más general: date(D1, mayo, A1)
D = 1 D = siete D1 = 1 D1 = siete M = mayo M = mayo 2001 A1 = 2001
Ejemplo date(D, mes(M), 2001) date(D1, mes(mayo), A1) date(15, mes(M), Y) _________________ date(15,mes(mayo),2001) D = D1 = 15 M = may A1 = Y = 2001
Semántica declarativa: ejemplo
Objetivo G: abuelo(juan, Nieto). Cláusula C: abuelo(X,Y) :- padre(X,Z), padre(Z,Y)
Instancia I: abuelo(juan,marta) :- padre(juan,luis), padre(luis,marta)
La cabeza de I es idéntica a G. Los objetivos en el cuerpo de I todos se cumplen.
6
Semántica procedimental
Se refiere a la manera en que Prolog resuelve los objetivos.
Las cláusulas de la BD están en un cierto orden. Se selecciona siempre la primera disponible. Si 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
Definiendo predicados recursivos, hay que tener cuidado en poner la condición de finalización en primer lugar.
pred2(X,Z) :- parent(X,Y), pred2(Y,Z). pred2(X,Z) :- parent(X,Z).
Peligro de bucle infinito
Si tenemos una cláusula del tipo: padre(X,Y) :- padre(X,Y)
Aunque lógicamente correcta, puede meter al intérprete en bucle cerrado.
Índice
Introducción
Sintaxis y semántica del lenguaje
pred3(X,Z) :- parent(X,Z). pred3(X,Z) :- pred3(X,Y), parent(Y,Z). pred4(X,Z) :- pred4(X,Y), parent(Y,Z). pred4(X,Z) :- parent(X,Z).
Hechos y consultas Reglas. Recursión Funcionamiento de prolog Morfología Unificación Funcionamiento procedimental
Listas, operadores, aritmética Control del backtracking
pred2(juan,marta)
Listas (I)
Una lista es una secuencia de elementos (átomos, estructuras, o listas). Se representan entre corchetes:
Listas (II)
.(juana, .(tenis, .(carlos, .(futbol,[]))))
[juana, tenis, carlos, futbol]
Una lista vacía se representa como: []
La representación interna es con una estructura llamada ".", con dos elementos: cabeza y cola:
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], List2 = .(a, .(b, .(c, []))), List3 = [a,List1,List2]. List1 = [a,b,c] List2 = [a,b,c] List3 = [a,[a,b,c],[a,b,c]]
Operaciones con listas (I)
Operaciones con listas (II)
Miembro de una lista:
miembro(X,[X|Tail]). miembro(X, [Head|Tail]) :miembro(X, Tail).
Se puede especificar explícitamente la separación entre la cabeza y la cola, mediante una barra vertical:
?- L = [a,b,c], R = [cabeza|L] L = [a,b,c] R = [cabeza,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]
Concatenación:
conc([], L, L). conc([X|L1], L2, [X|L3]) :conc(L1,L2,L3).
?- miembro(a, [a,b,c]). yes ?- miembro([b,c], [a,[b,c]]). yes ?- miembro(b, [a,[b,c]]). no
?- conc([a,b,c],[1,2,3],L). L = [a,b,c,1,2,3] ?- conc([a,b],L2,[a,b,[],c]). L2 = [[],c]
Operaciones con listas (II)
Operaciones con listas (II)
?- conc(L1,L2,[a,b]). L1=[] L2=[a,b] ;
?- conc(Before,[3,X|After],[1,2,3,4,5]). Before=[1,2] X=4 After=[5]
L1=[a] L2=[b] ; L1=[a,b] L2=[] ; no
8
Ejercicios
Define el predicado "last" que devuelva el último elemento de una lista, de dos maneras:
Basándose en el predicado "conc" Sin utilizarlo.
Escribe un predicado para añadir un elemento a una lista. Escribe un predicado para eliminar un elemento de una lista.
Operadores (I)
Aunque las listas son estructuras .(Head,Tail), se pueden escribir entre corchetes por claridad. Otros predicados, también por claridad, se pueden escribir como operadores (p.ej., con notación infija). Ejemplo:
+(3, 5) 3 + 5
Operadores (II) - Aritméticos
Operadores (III) - Evaluación
Existen operadores predefinidos para operaciones aritméticas + Suma - Resta * Multiplicación / División // División entera ** Elevación a potencia mod Módulo (resto de división)
Operadores (IV) – Operador "is"
Operadores (V) - Ejemplo
El argumento izquierdo ha de ser una variable. El argumento derecho será una expresión. Todas las variables en esa expresión han de estar asociadas a valores. Los operadores en prolog tienen todos asociado un número de precedencia. Los de menor número se ejecutan antes (ej: ** antes que *, antes que +, antes que is)
Los operadores son como cualquier otro predicado de prolog. Por omisión, no se evalúan.
?- X = 1 + 2. X = 1 + 2
Se puede forzar la evaluación utilizando el operador "is".
?- X is 1 + 2. X = 3
Máximo común divisor de dos números:
gcd(X,X,X). gcd(X,Y,D) :X < Y, Y1 is Y – X, gcd(X, Y1, D). gcd(X,Y,D) :Y < X, gcd(Y,X,D).
9
Operadores – Ejercicios
Define un predicado que calcule la longitud de una lista. Define un predicado que calcule el menor número dentro de una lista de números. Define un predicado con un único argumento, que devuelva "true" si los elementos en esa lista están ordenados.
Índice
Cuando prolog tiene que satisfacer una consulta, prueba todas las posibilidades (realizando backtracking) hasta encontrar las asignaciones de valores que la satisfagan. En el intérprete, si se piden más soluciones, se continúan buscando mediante backtracking.
Hechos y consultas Reglas. Recursión Funcionamiento de prolog
Sintaxis y semántica del lenguaje
Previniendo el backtracking (I)
Introducción
Morfología Unificación Funcionamiento procedimental
Listas, operadores, aritmética Control del backtracking
Ejemplo (I) 0 si x < 3 f(x) =
2 si x >= 3 y x < 6 4 si x >= 6
f(X,0) :- X < 3. f(X,2) :- 3 =< X, X < 6. f(X,4) :- 6 =< X. Ejemplo: ?- f(1,Y)
Ejemplo(II)
Ejemplo(III)
f(X,0) :- X < 3, !. f(X,2) :- 3 =< X, X < 6, !. f(X,4) :- 6 =< X.
f(X,0) :- X < 3, !. f(X,2) :- X < 6, !. f(X,4).
:- f(1,Y), 2 < Y. no :- f(7,Y). Y = 4
:- f(1,Y). Y = 0 ; Y = 2 ; Y = 4
10
Corte
Sea G el objetivo a satisfacer. Si entre los antecedentes de G se encuentra un corte !,
El corte inmediatamente se da por satisfecho Todas las alternativas a reglas para G dejan de considerarse Todas las alternativas a los antecedentes previos al corte dejan de considerarse
Corte (II) c(X) :- p(X),q(X),r(X),!,s(X),t(X),u(X). c(X) :- v(X). a(X) :- b(X),c(X),d(X). a(maria). ?- a(X). Suponemos que b(X) se cumple. Suponemos que p,q,r se cumplen, y la X se instancia a un cierto valor. ! también se cumple (automáticamente) Suponemos que s(X) falla. Entonces:
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. max(X, Y, Y) :- X < Y.
max(X, Y, X) :- X >= Y, !. max(X, Y, Y). Requisito: el tercer argumento no debe estar instanciado. En caso contrario, se pueden obtener resultados no deseados:
Añadir elementos a una lista
add(X,L,L) :- member(X,L), !. add(X,L,[X|L]). Igual que antes, el tercer argumento no debe estar instanciado al invocar este predicado en el intérprete.
?- max(3,1,1). yes
Ejercicios (I)
Sea el siguiente programa Prolog:
p(1). p(2) :- !. p(3). Escribir las respuestas a las siguientes consultas: ?- p(X). ?- p(X), p(Y). ?- p(X), !, p(Y).
Ejercicios (II)
La siguiente relación clisifica números en positivos o negativos:
class(Number, positive) :- Number > 0. class(0, zero). class(Number, negative) :- Number < 0.
Defínelo de manera más eficiente usando cortes.
11
Ejercicios (III)
Negación como fallo
Escribe, con y sin cortes, el procedimiento “split”, que divide una lista en dos sublistas, la primera con los números positivos, y la segunda con los negativos.
?- split([3,-1,0,5,-2],[3,0,5],[-1,-2]). yes
Para evitar la aplicación de una regla, se puede forzar el fallo con una combinación del corte, y la constante “fail”.
“fail” es un objetivo que nunca se satisface.
Por ejemplo, “Todos los pájaros, excepto el 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. different(X,Y).
not(P) :P, !, fail ; true
o bien: different(X,Y) :X = Y , !, fail ; true. donde “true” es un objetivo que siempre se cumple.
Muchos intérpretes de prolog traen el predicado not predefinido, con un operador asociado \+ vuela(X) :- pajaro(X), \+ pinguino(X), \+ avestruz(X).
Problemas con corte y negación
Problema con negación – Ejemplo
Corte: Los programas ya no corresponden a la definición declarativa: el orden de las cláusulas importa, y puede ser necesario forzar a que algún argumento sea una variable no instanciada. Negación: No corresponde a una negación lógica, sino al hecho de que no hay evidencia para demostrar lo contrario.
Ejemplo de restaurantes:
buena_comida(el_meson). caro(el_meson). buena_comida(casa_paco). razonable(Restaurante) :- \+ caro(restaurante). ?- buena_comida(X), razonable(X). X = casa_paco ?- razonable(X), buena_comida(X). no
12
Problema con negación – Causa
En Prolog, una consulta con una variable no instanciada se satisface si hay al menos una asignación de valores a la variable que la cumpla:
Al usar la negación, esa consulta pasa a ser cierta si el argumento de la negación fue falso, es decir, si ninguna asignación posible de valores cumplió la fórmula:
buena_comida(X) -> X = casa_paco
not(razonable(X)) = no(existe X tal que X razonable) = para todo X, X no es razonable
Negación - Ejercicios hombre(juan). ?- soltero(juan). hombre(carlos). ?- soltero(carlos). mujer(maria). ?- soltero(X). mujer(laura). ?- sinHijos(juan). padre(juan,maria). ?- sinHijos(carlos). padre(juan,carlos). ?- sinHijos(X). madre(laura,maria). ?- soltero(X), sinHijos(X). madre(laura,carlos). ?- hombre(X), soltero(X), esposo(juan,laura). sinHijos(X). esposo(laura,juan). soltero(X) :- \+ esposo(X,Y). sinHijos(X) :- \+ padre(X,Y), \+ madre(X,Z).
13