PDF de programación - Introducción a la Programación Lógica

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

Temario (Programación Lógica)

Principios de la programación lógica

1.
2. Técnicas básicas de programación Prolog
3.
4.
5.
6. Metaprogramación en Prolog
7. Técnicas avanzadas de programación Prolog

Predicados extralógicos
Programación lógica con estructuras
Control en Prolog

Introducción a la Programación Lógica

3

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

4

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

5

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

6

¿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

7

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

8

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

9

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

10

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

11

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

12

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

13

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

14

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

15

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

16

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

17

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

18

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

19

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

20

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

21

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

22

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.

Introducción a la Programación Lógica

23