PDF de programación - Tema 1: Introducción a Prolog

Programación Declarativa

Curso 2000–2001

Tema 1: Introducción a Prolog

José A. Alonso Jiménez
Miguel A. Gutiérrez Naranjo

Dpto. de Ciencias de la Computación e Inteligencia Artificial

Universidad de Sevilla

PD 2000–01

CcIa

Introducción a Prolog

1.1

gramación

Objetivos del curso
x Lógica como especificación y lenguaje de pro-
x Prolog = Programming in Logic
x Relaciones con otros campos:
u Bases de datos
u Sistemas basados en el conocimiento
u Procesamiento del lenguaje natural
u Inteligencia artificial
x Pensar declarativamente

PD 2000–01

CcIa

Introducción a Prolog

1.2

Declarativo vs. imperativo
x Paradigmas
u Imperativo: Se describe cómo resolver el problema
u Declarativo: Se describe qué es el problema
x Programas
u Imperativo: Una sucesión de instrucciones
u Declarativo: Un conjunto de sentencias
x Lenguajes
u Imperativo: Pascal, C, Fortran
u Declarativo: Prolog, Lisp puro, ML, Haskell
x Ventajas
u Imperativo: Programas rápidos y especializados
u Declarativo: Programas generales, cortos y legibles

PD 2000–01

CcIa

Introducción a Prolog

1.3

Historia
x -350: Grecia clásica (Aristóteles,...)
x 1930: Edad de oro de la lógica (G¨odel)
x 1960: Demostración automática de teoremas
x 1965: Resolución y unificación (Robinson)
x 1969: QA3, obtención de respuesta (Green)
x 1972: Implementación de Prolog (Colmerauer)
x 1974: Programación lógica (Kowalski)
x 1977: Prolog de Edimburgo (Warren)
x 1981: Proyecto japonés de Quinta Generación
x 1986: Programación lógica con restricciones
x 1995: Estándar ISO de Prolog

PD 2000–01

CcIa

Introducción a Prolog

1.4

Un ejemplo simple: divisibilidad
x Problema: Escribir un programa para declarar

que 2 divide a 6 y utilizarlo para responder a
las siguientes cuestiones:

u ¿2 divide a 6?.
u ¿3 divide a 12?.
u ¿Cuáles son los múltiplos de 2?.
u ¿Cuáles son los divisores de 6?.
u ¿Cuáles son los elementos X e Y tales que X divide a
x Programa: divisibilidad-1.pl

Y?.

divide(2,6).

x Sesión

?- divide(2,6).
Yes
?- divide(3,12).
No
?- divide(2,X).
X = 6
Yes
?- divide(X,Y).
X=2
Y=6
Yes

PD 2000–01

CcIa

Introducción a Prolog

1.5

Un ejemplo simple: divisibilidad
x Conceptos
u Relación: divide/2
u Nombre de una relación: divide
u Argumentos de una relación
u Hecho
u Programa
u Constante: 2, 6
u Variable: X, Y
u Objetivo
u Objetivo satisfacible
u Respuesta

PD 2000–01

CcIa

Introducción a Prolog

1.6

Unificación
x Ejemplos de unificación

divide(2,6) divide(2,X)

{X/6}

divide(2,6)

divide(X,6) divide(2,Y}

{X/2, Y/6}

divide(2,6)

divide(X,6) divide(2,X)

divide(2,6) divide(X,X)

No unif.

No unif.

divide(X,6) divide(Y,Z)

{X/4, Y/4, Z/6} divide(4,6)

divide(X,6) divide(Y,Z)

{X/Y, Z/6}

x Unificador de máxima generalidad (u.m.g.)

divide(4,6)

PD 2000–01

CcIa

Introducción a Prolog

1.7

Ampliación del programa
x Problema: Ampliar el programa anterior,

añadiéndole que 2 divide a 12 y que 3 divide
a 6 y a 12 y utilizarlo para responder a las si-
guientes cuestiones:

u ¿Cuáles son los elementos X e Y tales que X divide a
u ¿Cuáles son los múltiplos de 2 y de 3?
x Programa: divisibilidad-2.pl

Y?

divide(2,6).
divide(2,12).
divide(3,6).
divide(3,12).

x Sesión

?- divide(X,Y).
Y = 6 ;
X = 2
X = 2
Y = 12 ;
Y = 6 ;
X = 3
X = 3
Y = 12 ;
No
?- divide(2,X), divide(3,X).
X = 6 ;
X = 12 ;
No

PD 2000–01

CcIa

Introducción a Prolog

1.8

Ampliación del programa
x Conceptos:
u Pregunta cerrada
u Pregunta abierta
u Pregunta compuesta
u Respuesta
u Respuestas múltiples
u Literal seleccionado

PD 2000–01

CcIa

Introducción a Prolog

1.9

Reglas
x Problema: Ampliar el programa anterior

añadiéndole que los números divisibles por 2
y por 3 son divisibles por 6 y utilizarlo para
responder a las siguientes cuestiones:

u ¿Cuáles son los múltiplos de 6?
u ¿Cuáles son los elementos X e Y tales que X divide a
x Programa: divisibilidad-3.pl

Y?

divide(2,6).
divide(2,12).
divide(3,6).
divide(3,12).
divide(6,X) :-

divide(2,X),
divide(3,X).

divide(6,X) :- divide(2,X), divide(3,X).

x Interpretación de cláusulas
u Cláusula:
u Fórmula:
(∀X)[divide(2, X) ∧ divide(3, X) → divide(6, X)]
u Interpretación declarativa
u Interpretación procedimental

PD 2000–01

CcIa

Introducción a Prolog

1.10

Reglas
x Sesión

?- divide(6,X).
X = 6 ;
X = 12 ;
No
?- divide(X,Y).
X = 2
X = 2
X = 3
X = 3
X = 6
X = 6
No

Y = 6 ;
Y = 12 ;
Y = 6 ;
Y = 12 ;
Y = 6 ;
Y = 12 ;

x Conceptos:
u Cláusulas: hechos, reglas y preguntas
u Reglas: cabeza y cuerpo

PD 2000–01

CcIa

Introducción a Prolog

1.11

Resolución
x Modus ponens
A → B
A
B

x Resolución (I)
A ∨ B
¬A ∨ C
B ∨ C
x Resolución (II)
A ← B1, . . . , Bn
← A, C1, . . . , Cm
← B1, . . . , Bn, C1, . . . , Cm
x Resolución (III): Si A1θ = A2θ con θ u.m.g.
A1 ← B1, . . . , Bn
← A2, C1, . . . , Cm
← (B1, . . . , Bn, C1, . . . , Cm)θ

PD 2000–01

CcIa

Introducción a Prolog

1.12

Resolución en lógica proposicional
x Programa: leche.pl

es_leche :-

parece_leche,
lo_da_la_vaca.

parece_leche :-

es_blanco,
hay_una_vaca_en_la_etiqueta.

lo_da_la_vaca.
es_blanco.
hay_una_vaca_en_la_etiqueta.

x Sesión

?- es_leche.
yes

x Traza

(1) 0 CALL es_leche?
(2) 1 CALL parece_leche?
(3) 2 CALL es_blanco?
(3) 2 EXIT es_blanco
(4) 2 CALL hay_una_vaca_en_la_etiqueta?
(4) 2 EXIT hay_una_vaca_en_la_etiqueta
(2) 1 EXIT parece_leche
(5) 1 CALL lo_da_la_vaca?
(5) 1 EXIT lo_da_la_vaca
(1) 0 EXIT es_leche

PD 2000–01

CcIa

Introducción a Prolog

1.13

Demostración SLD

:- es leche.

es leche :- parece leche, lo da la vaca.

:- parece leche, lo da la vaca.

parece leche :-

es blanco,
hay una vaca en la etiqueta.

?

)
9

?

?

9
9
)?

?

:- es blanco,
hay una vaca en la etiqueta.
lo da la vaca.

es blanco.

:- hay una vaca en la etiqueta,
lo da la vaca.

:- hay una vaca en la etiqueta.

:- lo da la vaca.

lo da la vaca.



x SLD:
u S: regla de Selección
u L: resolución Lineal
u D: cláusulas Definidas

PD 2000–01

CcIa

Introducción a Prolog

1.14

Traza
x Problema: Utilizar el programa anterior para

calcular los divisores de 6 con el dispositivo
trace y construir el árbol de deducción.

[1] divide(2,6).
[2] divide(2,12).
[3] divide(3,6).
[4] divide(3,12).

x Arbol de resolución SLD

[5] divide(6,X) :-
divide(2,X),
divide(3,X).

PD 2000–01

CcIa

Introducción a Prolog

1.15

?-divide_a(6,X).?- divide_a(2,X), divide_a(3,X).?-divide_a(3,6).?-divide_a(3,12).[5][1][2][3][4]{X/6}{X/12}Traza
x Programa

[1] divide(2,6).
[2] divide(2,12).
[3] divide(3,6).
[4] divide(3,12).

x Traza:

?- trace(divide).

[5] divide(6,X) :-
divide(2,X),
divide(3,X).

divide/2: call redo exit fail

Yes
?- divide(6,X).
T Call: ( 7) divide(6, _G260)
T Call: ( 8) divide(2, _G260)
T Exit: ( 8) divide(2, 6)
T Call: ( 8) divide(3, 6)
T Exit: ( 8) divide(3, 6)
T Exit: ( 7) divide(6, 6)
X = 6 ;
T Redo: ( 8) divide(3, 6)
T Fail: ( 8) divide(3, 6)
T Redo: ( 8) divide(2, _G260)
T Exit: ( 8) divide(2, 12)
T Call: ( 8) divide(3, 12)
T Exit: ( 8) divide(3, 12)
T Exit: ( 7) divide(6, 12)
X = 12 ;
No

PD 2000–01

CcIa

Introducción a Prolog

1.16

Reglas recursivas: naturales.pl
x Problema: Los números naturales se forman a

partir del cero y la función sucesor. De forma
más precisa:
* El 0 es un número natural
* Si n es un número natural, s(n) también lo es
Escribir un programa para decidir si una ex-
presión es un número natural y utilizarlo para
responder a las siguientes cuestiones:

u ¿Es s(s(0)) un número natural?
u ¿Es 2 un número natural?
u ¿Cuáles son los números naturales?
x Programa: naturales.pl

nat(0).
nat(s(X)) :-

nat(X).

PD 2000–01

CcIa

Introducción a Prolog

1.17

Reglas recursivas: naturales.pl
x Sesión

?- nat(s(s(0))).
Yes
?- nat(dos).
No
?- nat(X).
X = 0 ;
X = s(0) ;
X = s(s(0)) ;
X = s(s(s(0))) ;
X = s(s(s(s(0))))
Yes

x Conceptos:
u Regla recursiva
u Símbolos de función
u Términos
u Infinitas respuestas

PD 2000–01

CcIa

Introducción a Prolog

1.18

Reglas recursivas: naturales.pl
x Arbol de resolución SLD

(I) nat(0).
(II) nat(s(X)):-nat(X).

:-nat(N ).



Z





Z

Z





Z

Z

(II)

θ2 = {N → s(X1)}

Z

Z

Z

ZZ~

:-nat(X1).

(I)

θ1 = {N → 0}







=


RC1 = {N → 0}

(I)

θ21 = {X1 → 0}







=


RC2 = {N → s(0)}



Z



Z

Z

Z

Z







(II)

θ22 = {X1 → s(X2)}

Z

Z

Z

ZZ~

:-nat(X2).



Z



Z







Z

Z

Z

(I)

θ221 = {X2 → 0}







=


RC3 = {N → s(s(0))}

θ222 = {X2 → s(X3)}

(II)

Z

Z

Z

ZZ~
. . .

PD 2000–01

CcIa

Introducción a Prolog

1.19

Reglas recursivas: suma.pl
x Problema: Definir el predicado suma(X,Y,Z)

de forma que si X e Y son dos números
naturales con la representación del programa
naturales.pl, entonces Z es el resultado de
sumar X e Y. Por ejemplo,

suma(s(0),s(s(0)),X) => X=s(s(s(0)))

Utilizarlo para responder a las siguientes cues-
tiones:

u ¿Cuál es la suma de s(0) y s(s(0))?
u ¿Cuál es la resta de s(s(s(0))) y s(0)
u ¿Cuáles son las soluciones de la ecuación X + Y =
x Programa: suma.pl

s(s(0))?

suma(0,X,X).
suma(s(X),Y,s(Z)) :- suma(X,Y,Z).

PD 2000–01

CcIa

Introducción a Prolog

1.20

Reglas recursivas: suma.pl
x Sesión

?- suma(s(0),s(s(0)),X).
X = s(s(s(0)))
Yes
?- suma(X,s(0),s(s(s(0)))).
X = s(s(0))
Yes
?- suma(X,Y,s(s(0))).
X = 0
Y = s(s(0)) ;
X = s(0)
Y = s(0) ;
X = s(s(0))
Y = 0 ;
No

PD 2000–01

CcIa

Introducción a Prolog

1.21

Intelligence (2nd ed.) (Addison–Wesley, 1990)

Bibliografía
x Bratko, I. Prolog Programming for Artificial
u Cap. 1: “An overview of Prolog”
u Cap. 2: “Syntax and meaning of Prolog programs”
x Clocksin, W.F. y Mellish, C.S. Programming

ligence (John Wiley, 1990)

in Prolog (Fourth Edition) (Springer Verlag,
1994)

u Cap. 1: “Tutorial introduction”
u Cap. 2: “A closer look”
x Shapiro, S.C. Encyclopedia of Artificial Intel-
u “Logic programming” (por R.A. Kowalski y C.J. Hog-
x Van Le, T. Technique