intro_ing

Vista previa del material en texto

Introducción a la Programación Lógica
Ingeniería Informática
Departamento de Lenguajes y
Ciencias de la Computación
Universidad de Málaga
Programming in Prolog opens the mid to a new way of looking at 
computing. There is a change of perspective which every Prolog
programmer experiences when first getting to know the
language. Declarative programming clears the mind.
David H.D. Warren
Introducción a la Programación Lógica 3
Temario (Programación Lógica)
1. Principios de la programación lógica
2. Técnicas básicas de programación Prolog
3. Predicados extralógicos
4. Programación lógica con estructuras
5. Control en Prolog
6. Metaprogramación en Prolog
7. Técnicas avanzadas de programación Prolog
Introducción a la Programación Lógica 4
Software (Programación Lógica)
SWI-Prolog
entorno de programación Prolog (Windows/Linux/OSX)
http://www.swi-prolog.org/
SLD-Draw
visualización de árboles SLD (Windows/Linux)
http://www.lcc.uma.es/~lopez/progdec
Introducción a la Programación Lógica 5
Bibliografía I (Programación Lógica)
Referencias básicas:
“The Art of Prolog” (2ed)
Leon Sterling y Ehud Shapiro
MIT Press, 1994
“Programación en Prolog” (2ed)
William F. Clocksin y Chris S. Mellish
Gustavo Gili, 1993
“Prolog Programming for Artificial Intelligence” (3ed)
Ivan Bratko
Addison-Wesley, 2000
Introducción a la Programación Lógica 6
Bibliografía II (Programación Lógica)
Libros y referencias disponibles en internet:
“Clause and Effect”
William F. Clocksin
“Prolog Programming: A First Course”
Paul Brna
“Logic, Programming and Prolog” (2ed)
Ulf Nilsson y Jan Maluszynski
Consultar sitio web de la asignatura:
http://www.lcc.uma.es/~lopez/progdec
Introducción a la Programación Lógica 7
¿Qué es la Programación Lógica?
la idea fundamental de la programación lógica consiste en 
emplear la lógica como lenguaje de programación
Datos = términos de primer orden
Procedimiento = fórmulas bien formadas
Ejecución = Deducción controlada y constructiva
la lógica no es imperativa:
no sirve para indicar cómo resolver un problema (órdenes)
la lógica es declarativa:
sirve para especificar qué problema resolver (condiciones)
sin embargo, la programación lógica permite ambos enfoques
Introducción a la Programación Lógica 8
El enfoque imperativo
programación imperativa (C++, Java, etc.)
• diseñar un algoritmo para resolver el problema
• computar la solución ejecutando el algoritmo
• el énfasis está en cómo resolver el problema
la programación lógica también es capaz de describir 
algoritmos a un nivel de abstracción alto
Introducción a la Programación Lógica 9
El enfoque lógico
programación lógica
• especificar las condiciones que satisfacen las soluciones
• deducir las soluciones a partir de las condiciones
• el énfasis está en qué problema resolver
el problema se describe especificando qué caracteriza a sus 
posibles soluciones
Introducción a la Programación Lógica 10
Ejemplo 1: ordenar tres números
Problema: ordenar tres números distintos
Entrada: conjunto XXXX = {XXXX, XXXX, XXXX}
Solución: ∃∃∃∃ A,B,C tales que:
A,B y C ∈∈∈∈ XXXX ∧∧∧∧
A ≠≠≠≠ B ≠≠≠≠ C ∧∧∧∧
A < B ∧∧∧∧
B < C
no es una solución imperativa: no es un algoritmo de 
ordenación
es una solución declarativa: especifica las condiciones que 
caracterizan a la solución
Introducción a la Programación Lógica 11
Ejemplo 1 resuelto en Prolog
programa
ordenar(X,[A,B,C]) :-
member(A,X),member(B,X),member(C,X),
A =\= B, A =\= C, B =\= C,
A < B,
B < C.
ejecución
?- ordenar([9,2,5],S).
S = [2,5,9];
No
Prolog deduce la solución a partir de las condiciones
Ejercicio: una de las condiciones es redundante. ¿Cuál?
Introducción a la Programación Lógica 12
Ejemplo 2: descomponer un número
Problema: Descomponer un número en la suma de dos pares
Entrada: un natural N
Solución: ∃∃∃∃ A y B tales que:
A, B ∈ NNNN ∧∧∧∧
A mod 2 = 0 ∧∧∧∧
B mod 2 = 0 ∧∧∧∧
N = A + B
Introducción a la Programación Lógica 13
Ejemplo 2 resuelto en Prolog
programa:
descomponer(N,A,B) :-
between(0,N,A), A mod 2 =:= 0,
between(0,N,B), B mod 2 =:= 0,
N =:= A + B.
ejecución:
?- descomponer(6,A,B).
A=0, B=6;
A=2, B=4;
A=4, B=2;
A=6, B=0;
No
Prolog encuentra todas las soluciones: un procedimiento puede 
devolver varias respuestas
Introducción a la Programación Lógica 14
Otra solución a la descomposición en pares
podemos hacer el programa más determinista: una vez 
seleccionado un valor para A, podemos calcular el valor exacto 
de B.
programa:
descomponer_det(N,A,B) :-
between(0,N,A), A mod 2 =:= 0,
B is N-A, B mod 2 =:= 0. % B determinado
Introducción a la Programación Lógica 15
Ejemplo 3: partir una lista
Problema: partir una lista L en dos listas A y B de manera que el 
último elemento de A aparezca en B
Ejemplo: L = 1,2,3,4,3,5 A = 1,2,3 B = 4,3,5
Entrada: lista L
Solución: ∃∃∃∃ A y B tales que:
L = A concatenada con B ∧∧∧∧
A = a1,a2,...,an ∧∧∧∧
B = b1,...bm ∧∧∧∧
∃∃∃∃ j. (bj ∈∈∈∈ B ∧∧∧∧ bj=an)
Introducción a la Programación Lógica 16
Ejemplo 3 resuelto en Prolog
programa:
partir(L,A,B) :-
append(A,B,L),
last(A,Ult),
memberchk(Ult,B).
ejecución:
?- partir([1,2,3,4,2,3],A,B).
A = [1, 2], B = [3, 4, 2, 3] ;
A = [1, 2, 3], B = [4, 2, 3] ;
No
Introducción a la Programación Lógica 17
Ejemplo 4: el cruce de rebaños
Problema: Dos cabreros se encuentran en un cruce y se produce 
el siguiente diálogo:
- Dame una cabra, para que tengamos las mismas
- Mejor dame tú una a mí, para que tenga yo el doble que tú
¿Cuántas cabras tiene cada cabrero?...
Solución: ∃∃∃∃ A y B ∈∈∈∈ NNNN+ tales que:
B-1 = A+1 ∧∧∧∧
2*(A-1) = B+1
Introducción a la Programación Lógica 18
Ejemplo 4 resuelto en Prolog
programa:
rebaño(A,B) :-
between(1,10,A), % conjetura 1
between(1,10,B), % conjetura 2
B-1 =:= A+1, 
2*(A-1) =:= B+1.
ejecución:
?- rebaño(A,B).
A= 5, B= 7;
No
Introducción a la Programación Lógica 19
Otra solución al cruce de los rebaños
De la misma forma que hay varios algoritmos para un mismo 
problema, es posible que haya varias especificaciones de la 
solución
Solución: ∃∃∃∃ A y B ∈∈∈∈ NNNN+ tales que: 
B = A+2,
2*(A-1) = B+1
programa:
rebaño2(A,B) :-
between(1,10,A), % conjetura 1
B is A+2, % B determinado
2*(A-1) =:= B+1.
Introducción a la Programación Lógica 20
Un poco de historia (I)
Resolución y unificación (J. Alan Robinson, 1965)
Resolución de problemas mediante demostración automática 
de teoremas (Cornell Green, 1969)
El lenguaje Prolog (Alain Colmerauer, 1972)
Interpretación procedimental de las cláusulas de Horn
(Robert Kowalski, 1973)
Compilador de Prolog para DEC-10 (David H.D. Warren, 1977)
Máquina abstracta de Warren (David H.D. Warren, 1983)
Introducción a la Programación Lógica 21
Un poco de historia (y II)
80’s – Primeros 90’s:
Proyecto de la Quinta Generación (Japón)
Paralelismo masivo
Programación lógica concurrente (Kernel Language)
Estándar ISO Prolog (1995)
Actualmente:
Programación con restricciones
Programación en Internet
Transferencia de tecnología a otros paradigmas
(implementación, análisis de programas,…)
Introducción a la Programación Lógica 22
Ejercicios (I)
Para resolver estos ejercicios puedes usar las comparaciones:
X > Y, X < Y, X =< Y, X >= Y
1. Una terna pitagórica está formada por tres enteros 
positivos X, Y, Z tales que X2 + Y2 = Z2. Define un predicado 
pitagoras(N,X,Y,Z) que sea cierto cuando X, Y, Z son 
menores o iguales que N y forman una terna pitagórica.
2. Define un predicado raiz(N,R) que sea cierto cuando R sea 
la parte entera de la raíz cuadrada de N.
3. En qué año del siglo XX nació Carlos, si su edad en el año 
2000 es igual a la suma de las cifras de su año de nacimiento.
4. Mi hijo es ahora tres veces más joven que yo, pero hace 5 
años era cuatro veces más joven. ¿Qué edad tienen padre e 
hijo?
Introducción a la Programación Lógica 23
Ejercicios (y II)
5. Entre un preso y un carcelero se produce el siguiente 
diálogo:
- ¿Cuándo saldréde aquí?
- ¿Qué edad tienes?
- Veinticinco
- Yo tengo cincuenta y cuatro. Saldrás cuando te
duplique la edad.
¿Cuántos años le quedan por cumplir al preso?
6. Define un predicado partir(L,A,B,C) que parta una lista 
L en tres sublistas A, B y C de forma que tengan al menos un 
elemento en común. Ten en cuenta que append sólo recibe 
tres argumentos.