Introducción al lenguaje PROLOG

1

ÍNDICE

Bibliografía recomendada.

2

1.- Introducción formal al lenguaje Prolog

3

2.- Cláusulas

5

3.- Términos

5

4.- Hechos

6

5.- Consultas

7

6.- Equiparación

7

7.- Reglas

8

7.1.- Recursividad

8

7.2.- Recursividad encubierta

9

7.3.- Eficiencia

9

7.4.- Directivas para mejorar la eficiencia

10

8.- Desigualdad

11

9.- Operadores lógicos y aritméticos

11

10.- Igualdad y asignación

12

11.- Modos de funcionamiento

13

12.- Eficiencia y corte

14

12.1.- Corte Verde

15

12.2.- Corte Rojo

15

13.- Fallo

17

14.- Negación

17

15.- Progamación Determinista/No Determinista

18

16.- Mecanismo de Resolución

19

17.- Listas

20

18- Ejercicios Básicos

23

Apéndice.- SWI_Prolog

31

Introducción al lenguaje PROLOG

BIBLIOGRAFÍA RECOMENDADA

•

Bibliografía Básica

Prolog. Programming for artificial Intelligence Ivan Bratko Ed. Addison-Wesley, 1994 The Art of Prolog L.Sterling, E.Shapiro The MIT Press, Cambridge, Massachusetts,1994

•

Bibliografía Complementaria

Programming in Prolog W.F.Clocksin, C.S.Mellish Springer-Verlag,1987 Prolog. Introducción a la Programación de sistemas expertos J.M.Orenga y Ortega, J.P.Sánchez y Beltrán Ed. RAMA, 1987

2

Introducción al lenguaje PROLOG

3

1.- INTRODUCCIÓN FORMAL AL LENGUAJE PROLOG PROLOG es un lenguaje declarativo e interpretado, en este tipo de lenguajes se representan los conocimientos sobre un determinado dominio y sus relaciones. A partir de ese conocimiento, se deducen las respuestas a las cuestiones planteadas, es decir se obtiene una inferencia. El dominio lo constituye un conjunto de objetos. El conocimiento se formaliza mediante un conjunto de relaciones que describen de forma simultánea las propiedades y sus interacciones. Se declara el conocimiento disponible acerca de: •

OBJETOS: ♦ propiedades ♦ relaciones

•

• •

REGLAS, que determinan interacciones lógicas del tipo: si ocurre q, r, s y t entonces P

Ventaja: No hay que preocuparse de detalles de cómo resolver algo Desventaja: La resolución no siempre es eficiente.

Desde un punto de vista lógico, un programa Prolog está constituido por un conjunto de cláusulas de Horn. Una cláusula de Horn tiene la forma general: p(t1,t2,….,tn) :- p1(….),p2(….),…,pm(….)

con m >= 0

Donde tanto p como las pi son símbolos predicados con sus argumentos entre paréntesis. A los argumentos de un predicado se les denomina Términos. Las cláusulas de Horn son expresiones condicionales, siendo el símbolo “:-” el condicional o símbolo de la implicación (normalmente en lógica se utiliza el símbolo “← ←”). Así la cláusula anterior podría leerse de la siguiente forma: “SI p1(….) Y p2(….) Y … Y pm(….) ENTONCES p(t1,t2,…,tn)” o bien podría leerse también: “ Es cierto p(t1,t2,…,tn) SI es cierto p1(….) Y es cierto p2(….) Y … Y es cierto pm(….) “ Cuando m=0, la cláusula no tiene parte derecha, en este caso diremos que se trata de un hecho o afirmación. p(t1,t2,…,tn). Cuando la cláusula no tiene parte izquierda (o cabeza), se tiene una cláusula negativa o pregunta, este tipo de cláusulas se utilizan para realizar la entrada/salida del programa: ?p1(….),p2(….),…,pm(….) Un término ti puede ser: •

un átomo (número, constante)

Introducción al lenguaje PROLOG

• •

4

una variable una estructura (functor): f(t1,t1,…tm) donde los argumentos ti son a su vez términos

En la sintaxis estándar de Prolog (la que utilizaremos aquí se conoce como sintaxis de Edimburgo), los símbolos de átomos (constantes), functores y predicados comienzan con una letra minúscula, los símbolos de variables comienzan con una letra mayúscula o con un subrayado. Un ejemplo de un programa Prolog sería el siguiente: 1. 2. 3. 4. 5.

p(a,f(T,b)) :- q(Y,c,a),r(T,b). p(a,b). q(c,c,a). q(a,b,c) :- r(g(a,b),d). r(f(b,a),b).

Una computación en Prolog es un proceso de RESOLUCION LINEAL CON UNIFICACIÓN aplicado a una cláusula negativa (la pregunta) y al conjunto de cláusulas que constituyen el programa. Así la cláusula negativa: ?p(a,X). Tendría la siguiente interpretación: ¿Para qué valores de la variable X resulta cierto el predicado p(a,X). ? ¿Para que valores de X se deduce p(a,X) del conjunto premisa que componen las cláusulas del programa? Para resolver el objetivo ?p(a,X) aplicando resolución lineal, se intenta su unificación con la parte izquierda de alguna cláusula que contenga el mismo predicado/aridad. Si la unificación es posible, se sustituye el objetivo original por la lista de objetivos de la parte derecha de la cláusula utilizada en la unificación (con las sustituciones de variables que la unificación implica). El proceso continúa con el primer objetivo de la lista resultante hasta que desaparezcan todos los objetivos. Si en un momento dado resulta imposible resolver un objetivo, se retrocede (backtracking) al objetivo más reciente con otras alternativas para su resolución, y se resuelve con la siguiente alternativa. Si no existen alternativas disponibles, el objetivo de partida falla. Si se vacía la lista de objetivos, el objetivo queda resuelto. El proceso desencadenado para el objetivo anterior sería el siguiente: ?p(a,X) ?q(Y,c,a),r(T,b) ?r(T,b) ?[ ]

resolviendo con 1, sustitución X=f(T,b) resolviendo con 3, sustitución Y=c resolviendo con 5, sustitución T=f(a,b) cláusula vacía

Luego el objetivo original se ha resuelto (es cierto) con X=f(f(a,b),b), que es el resultado (o salida) del cálculo realizado por el programa Prolog. La estrategia de resolución descrita para aplicar el principio de resolución y que suele utilizarse en el Prolog estándar, se denomina primero_en_profundidad (depth first), pues el árbol de búsqueda de la solución se recorre en profundidad (se intenta resolver en primer lugar el objetivo más reciente de la lista de objetivos). El orden de utilización de las cláusulas para resolver un objetivo en Prolog standard es el determinado por su aparición en el programa. Nota: ¿Existe alguna otra solución a la resolución de ese objetivo?

Introducción al lenguaje PROLOG

5

2.- CLÁUSULAS Un programa en Prolog está constituido por una secuencia de cláusulas. Estas cláusulas deben representar todo el conocimiento necesario para resolver el problema. Se pueden diferenciar tres tipos de Cláusulas: • Hechos (afirmaciones), pueden representar: ♦ Objetos ♦ Propiedades de objetos. ♦ Relaciones entre objetos. • Reglas. • Consultas (cláusulas negativas). Como se ha mencionado, un programa Prolog es una secuencia de cláusulas, donde cada cláusula puede estar formada por uno o varios predicados. Las cláusulas deben terminar obligatoriamente en punto.

3.- TÉRMINOS En Prolog hay tres tipos de términos: CONSTANTES, VARIABLES Y ESTRUCTURAS Tipo

Comentarios

Ejemplos

Casos Especiales

En Minúsculas.

luis

Nombre de:

pedro

Átomos especiales :?-

Constante Átomo

• Objetos

edad

• Propiedades

color

• Relaciones

padre ‘rey león’

Número Entero

Sólo dígitos, +, -

63

Real

Y punto decimal

365.2425

Variable

Comienzan con Mayúscula o con _

Suma _Y

Estructura

Término compuesto por otros Términos

edad(luis, 63)

X

padre_de(luis, eva)

Variable anónima: _

Introducción al lenguaje PROLOG

6

4.- HECHOS Es el mecanismo básico para representar: • objetos/personas/conceptos. • propiedades de los objetos. • relaciones entre los objetos. Ejemplos: padre(luis). padre_de(luis, pedro). azul(cielo). Una relación viene definida por todas las instancias que aparecen con un predicado. tipo de concepto

Ejemplo

aridad

objetos/personas/proposiciones

luis

predicado/0

pedro cielo Propiedades

padre

predicado/1

azul Relaciones

padre_de

predicado/2, .../n

Los hechos pueden introducirse en la base de hechos del intérprete de Prolog mediante una aserción: ?- assert(padre_de(luis, pepe)). yes.

Base de HECHOS. EJEMPLOS amigos(pedro, antonio). amigos(pedro, flora). amigos(pedro, juan). amigos(pedro, vicente). amigos(luis, felipe). amigos(luis, maria). amigos(luis, vicente). amigos(carlos, paloma). amigos(carlos, lucia). amigos(carlos, juan). amigos(carlos, vicente). amigos(fernando, eva).

amigos(fernando, pedro). millonario(pedro). millonario(antonio). millonario(flora). soltero(pedro). soltero(flora). soltero(eva). soltero(luis). padre_de(carlos, fernando). padre_de(antonio, maria). padre_de(antonio, carlos).

Introducción al lenguaje PROLOG

7

5.- CONSULTAS Es el mecanismo para extraer conocimiento del programa: ?- amigos(pedro, antonio). yes ?- amigos(pedro, eva). no ?- amigos(pedro, pepe). no

X = juan ; X = vicente ; no

?- amigos(pedro, X). X= antonio ; X = flora ;

?- novios(pedro, flora). WARNING Undefined predicate novios/2

?- amigos(antonio, pedro). no

Ejemplo: Mi amigo, Vicente, busca amigos/as de mis amigos que sean millonarios/as y estén solteros/as: ?- amigos(X, vicente), amigos(X, Y), millonario(Y), soltero(Y). X = pedro Y = flora ; No •

Una consulta estará constituida por una o varias metas que Prolog deberá resolver. El intérprete de Prolog nos devuelve más soluciones si utilizamos el punto y coma “;” cuando no existen más soluciones que unifiquen con el objetivo, el intérprete contesta No.

6.- EQUIPARACIÓN Este mecanismo permite comprobar si dos expresiones son equivalentes, produce como resultado una sustitución de términos cuando esta es posible. Por ejemplo, si una variable está libre y es equiparada con un valor numérico, se obtiene una instanciación (asignación) de la variable con dicho valor. Ejemplos: amigos(pedro, vicente) y amigos(pedro, vicente) son equiparables. amigos(pedro, vicente) y amigos(X, vicente) son equiparables. X = pedro. amigos(pedro, Y) y amigos(X, vicente) son equiparables. X = pedro, Y = vicente. amigos(X, X) y amigos(pedro, vicente) no son equiparables porque X = pedro, X = vicente no es posible. En general, dos términos T1 y T2 son equiparables: • T1, T2 son constantes => idénticas. • T1 o T2 es una variable => se equiparan instanciando el otro término a la variable. • T1, T2 son estructuras => los términos que los componen son equiparables manteniendo una instanciación de las variables coherente.

Introducción al lenguaje PROLOG

8

7 .- REGLAS Permiten establecer relaciones más elaboradas entre objetos, por ejemplo, relaciones generalizadas o particularizadas, o relaciones causa-efecto. A continación, se muestran un conjunto de ejemplos en Prolog que permiten generalizar conceptos como el de padre, familiar, etc.. padre(X) :- padre_de(X, Y). padre(X) :- padre_de(X, _). hijo_de(X,Y) :- padre_de(Y, X). hermanos(X,Y) :- padre_de(Z,X), padre_de(Z,Y).

% ¡X = Y!

familiares(X, Y) :- padre_de(X, Y). familiares(X, Y) :- padre_de(Y, X). familiares(X, Y) :- hermanos(Y, X). practica_suspendida(X) :- practica_copiada(X). practica_suspendida(X) :- practica_insuficiente(X). practica_insuficiente(X) :- programa_no_funciona(X). practica_insuficiente(X) :- memoria_insuficiente(X). peligro_de_inundacion(X) :- grifo_abierto(X), lleno_de_agua(X). amigos_interesantes(X, Z) :- amigos(Y, X), amigos(Y, Z), millonario(Z), soltero(Z). % ¡Z = X!

7.1.-Reglas. RECURSIVIDAD Para definir reglas más generales y flexibles, es necesario un mecanismo adicional. Para ello se utilizará el concepto de recursividad. Para definir el concepto antecesor_de puede definirse de una forma iterativa: antecesor_de(X,Y) :- padre_de(X, Y). antecesor_de(X,Y) :- padre_de(X, Z), padre_de(Z, Y). antecesor_de(X,Y) :- padre_de(X, Z1), padre_de(Z1, Z2), padre_de(Z2, Y). antecesor_de(X,Y) :- padre_de(X, Z1), padre_de(Z1, Z2), padre_de(Z2, Z3), padre_de(Z3, Y). ...

% padre % abuelo % bisabuelo % tatarabuelo

Este mecanismo no es eficiente, dado que no nos permite generalizar fácilmente el concepto de antecesor. Prolog permite utilizar definiciones recursivas, que resuelven el problema de forma elegante. antecesor_de(X, Y) :- padre_de(X, Y). antecesor_de(X, Y) :- padre_de(X, Z), antecesor(Z, Y).

Introducción al lenguaje PROLOG

9

7.2.- Reglas. RECURSIVIDAD ENCUBIERTA Uno de los peligros que conlleva la recursividad, es la de realizar definiciones circulares o que el intérprete de Prolog no sea capaz de resolver. El ejemplo más simple de un caso problemático sería: antecesor_de(X, Y) :- antecesor_de(X, Y). % que se puede reducir a la cláusula: P => P Esta cláusula es declarativamente correcta, pero el intérprete de Prolog no podrá resolverla nunca y se quedará atrapado en un bucle infinito. De aquí se pueden observar otros casos problemáticos, por ejemplo si se define la siguiente base de hechos sobre las amistades de una persona: amigos(pedro, antonio). amigos(pedro, flora). ... amigos(fernando, pedro). Si consideramos que el concepto amistad tiene una relación conmutativa, entonces posiblemente nos interesaría definir la relación de amistad inversa o complementaria: amigos(X, Y) :- amigos(Y, X). % ¡Peligro, recurrencia! Esta definición aparentemente lógica provoca un error. La forma correcta de definirlo sería a través de un nuevo predicado: son_amigos(X, Y) :- amigos(X, Y). son_amigos(X, Y) :- amigos(Y, X).

7.3.- Reglas. EFICIENCIA En lógica matemática no se impone un orden especial de las cláusulas y de los términos que componen los programas. Sin embargo, en Prolog es necesario cuidar el orden de las cláusulas dentro de un programa, debido a que el intérprete unifica la reglas en el orden secuencial en el que le han sido proprocionadas. Volviendo a la definición del predicado antecesor_de podemos ver que consta de dos cláusulas, una de las cuales posee dos metas (u objetivos). Esto permite generar cuatro definiciones distintas de antecesor_de, permutando el orden de los términos y de las cláusulas. antecesor1(X, Y) :- padre_de(X, Y). antecesor1(X, Y) :- padre_de(X, Z), antecesor1(Z, Y). antecesor2(X, Y) :- padre_de(X, Z), antecesor2(Z, Y). antecesor2(X, Y) :- padre_de(X, Y). antecesor3(X, Y) :- padre_de(X, Y). antecesor3(X, Y) :- antecesor3(Z, Y), padre_de(X, Z) . antecesor4(X, Y) :- antecesor4(Z, Y), padre_de(X, Z) . antecesor4(X, Y) :- padre_de(X, Y).

Introducción al lenguaje PROLOG

10

En los ejemplos anteriores se obtienen resultados distintos. • • • •

antecesor1 es la más eficiente y funciona siempre. antecesor2 es menos eficiente. antecesor3 sólo funciona para algunos casos. antecesor4 no funciona nunca, siempre se queda atrapado en un bucle infinito.

Ejemplos: ?- antecesor3(antonio, carlos). % Verifica que la relación es cierta. ?- antecesor3(carlos, maria). % La relación es falsa, pero el programa no puede comprobarlo, quedará atrapado en un bucle % infinito. ?- antecesor3(X, Y). % Es capaz de imprimir algunos resultados, pero cuando la primera regla que define antecesor3 % falle, quedará atrapado en un bucle infinito.

7.4.- Reglas. Directivas para mejorar la eficiencia. El siguiente conjunto de directivas pueden utilizarse para lograr que la ejecución de nuestro programa Prolog sea lo más eficiente posible. •

Primero los objetivos más sencillos

- Ordenación de cláusulas: 1º las más específicas. 2º las más generales (con recursividad). Ejemplo: antecesor(X, Y) :- padre_de(X,Y). antecesor(X, Y) :- padre_de(X,Y), antecesor(Z,Y).

- Ordenación de términos dentro de una cláusula: 1º los términos más específicos. 2º los términos más generales (recursivos). Ejemplo: antecesor(X, Y) :- padre_de(X,Y), antecesor(Z,Y).

•

Acotar el espacio de búsqueda

amigos_interesantes(X, Z) :- % ¡Z = X! amigos(Y, X), amigos(Y, Z), millonario(Z), soltero(Z). Sabiendo que los amigos son más frecuentes que los millonarios y solteros, resultará más eficiente a la hora de realizar la búsqueda cambiar el orden de las metas: amigos_interesantes(X, Z) :- % ¡Z = X! millonario(Z), soltero(Z), amigos(Y, X), amigos(Y, Z).

Introducción al lenguaje PROLOG

11

8.- DESIGUALDAD Para comprobar si dos términos son distintos, disponemos de diferentes operadores. • Desigualdad \== Comprueba si dos términos son distintos. Por ejemplo, si dos variables tienen distintos valores instanciados. • Desigualdad aritmética =\= Verifica la desigualdad numérica de dos expresiones. Ejemplos: hermanos(X,Y) :- padre_de(Z,X),padre_de(Z,Y),X \== Y . amigos_interesantes(X, Z) :- millonario(Z), soltero(Z), amigos(Y, X), amigos(Y, Z), X \== Z . no_nulo(X) :- X =\= 0.

9.- OPERADORES LOGICOS Y ARITMETICOS Otros operadores de comparación aritmética son: < ; > ; =< ; >= Operadores y funciones aritméticas válidas en Prolog son: + / // mod abs **

* división real. división entera. resto de división entera. valor absoluto. potencia.

^ potencia. max valor máximo de dos. min valor mínimo de dos. round redondea al entero más próximo. integer trunca a la parte entera. float convierte en un valor real.

Introducción al lenguaje PROLOG

12

10.- IGUALDAD Y ASIGNACION Disponemos de cuatro tipos de operadores de ‘igualdad’: • Igualdad aritmética

[=:=]. Comprueba la igualdad numérica de las expresiones argumento.

igual1(X, Y) :- X =:= Y. • Identidad

[==]. Comprueba si los términos argumento son idénticos.

igual2(X, Y) :- X == Y. • Unificación [ = ]. Comprueba si los términos argumento son unificables (equiparables). Es equivalente a la asignación directa entre variables en un lenguaje procedimental. Da fallo si la unificación no es posible. igual3(X, Y) :- X = Y. Una definición equivalente sería: igual4(X,X). • Asignación

[is]. Evalúa la segunda expresión e intenta asignar el valor obtenido a la

variable. ¡No es conmutativo! incremento(X,Y) :- Y is X+1. Una definición similar a la de igualdad sería: igual5(X, Y) :- X is Y. Los operadores antes mencionados, aunque parten de conceptos muy distintos, poseen comportamientos similares, lo cuál puede inducir a errores. A continuación se muestra una tabla comparativa de todas las posibilidades existentes. Operador Ejemplo Igual?(3,3). Igual?(1,3). Igual?(1+2,3). Igual?(3,1+2). Igual?(X,1+2). Igual?(1+2,X). Igual?(3,X). Igual?(X,3). Igual?(‘hola’,’hola’). Igual?(1.0,1). Igual?(1,1.0). Igual?(1.0,1.0). Igual?(1.1,1.1). * **

=:= igual1 yes no yes yes * * * * ** yes yes yes yes

== igual2 yes no no no no no no no yes no no yes yes

Excepción: Variable X libre. Error: ‘hola’ no es función (o expresión) válida.

= igual3 yes no no no X=1+2 X=1+2 X=3 X=3 yes no no yes yes

= igual4 yes no no no X=1+2 X=1+2 X=3 X=3 yes no no yes yes

is igual5 yes no no yes X=3 * * X=3 yes no*** yes*** no*** yes***

Introducción al lenguaje PROLOG

***

13

Prolog tiene tendencia a convertir valores reales a enteros. En el segundo argumento del operador is detecta que se puede convertir en entero.

Introducción al lenguaje PROLOG

14

11.- MODOS DE FUNCIONAMIENTO Un predicado puede ser utilizado con diversos tipos de argumentos, pero no siempre está garantizado que funcione. Los tipos de argumentos más comunes son: •

Términos (constantes o variables instanciadas). Representados con +

• •

Variables libres. Representado con Cualquiera de los dos. representado con ?

Posibilidades: igual1(X, Y) :- X =:= Y. igual1(constante, constante) igual1(vlibre, constante) igual1(constante, vlibre) igual1(vlibre, vlibre)

funciona no funciona no funciona no funciona

==> igual1(+, +)

Resumen : igual1(+,+). ———— igual4(X,X). igual4(constante, constante) igual4(vlibre, constante) igual4(constante, vlibre) igual4(vlibre, vlibre)

funciona funciona funciona funciona

==> igual4(+, +) ==> igual4(-, +) ==> igual4(+, -) ==> igual4(-, -)

Resumen : igual4(?, ?) ———— igual5(X, Y) :- X is Y. igual5(constante, constante) igual5(vlibre, constante) igual5(constante, vlibre) igual5(vlibre, vlibre)

funciona funciona no funciona no funciona

==> igual5(+, +) ==> igual5(-, +)

Resumen : igual5(?,+). ———— Se puede incluir más información sobre el tipo concreto de argumento, por ejemplo: número, expresión, carácter,... igual1(X, Y) :- X =:= Y. Resumen : igual1(+,+). Los argumentos deben ser expresiones numéricas: ==>

igual1(+expresión,+expresión).

———— igual4(X,X). Resumen : igual4(?, ?) Los argumentos pueden ser cualquier tipo de término: ==>

igual4(?término,?término).

———— igual5(X, Y) :- X is Y. Resumen : igual5(?,+). El primer argumento pueden ser una variable libre o constante numérica, el segundo debe ser una expresión numérica: ==> igual5(?número,+expresión). Es conveniente incluir información de este tipo en los programas cada vez que se define un predicado.

Introducción al lenguaje PROLOG

15

12.- EFICIENCIA Y CORTE Supongamos que se desea programar en Prolog la siguiente función matemática:

Función escalón

4 2 0

-6

-3

0

3

6

0,  f ( x) = 2, 4, 

9

x=6.

f(X,0) :- X < 3, !. X=2, Y=0, X3 y la tercera cuando X>6. Podemos reescribir el programa de la siguiente forma: f(X,0) :- X < 3, !. f(X,2) :- X < 6, !. f(X,4). Curiosamente deja de funcionar en modo f(+,+), por ejemplo el caso f(0,4) daría cierto. ¿Qué se ha hecho mal?. El problema es que el nuevo programa se basa en un programa semánticamente incorrecto, si eliminásemos el corte, observaríamos que al eliminar el operador de corte obtenemos un programa incorrecto: f(X,0) :- X < 3. f(X,2) :- X < 6.

% ¡MAL!

Introducción al lenguaje PROLOG

17

f(X,4). ¡Este tipo de corte (Corte Rojo) debe emplearse con sumo cuidado! Partiendo del ejemplo anterior: f(X,0) :- X < 3, !. f(X,2) :- X < 6, !. f(X,4).

% f(+,-)

El motivo de perder el modo f(+,+) es debido a una interacción poco obvia entre la equiparación, las condiciones y el corte. El programa realmente debería ser: f(X,Y) :- X < 3, !, Y is 0. f(X,Y) :- X < 6, !, Y is 2. f(X,Y) :- Y is 4.

% f(+,?)

No obstante este programa sigue basándose en un programa semánticamente incorrecto; al eliminar nuevamente el operador de corte se sigue obteniendo un programa incorrecto: f(X,Y) :- X < 3, Y is 0. f(X,Y) :- X < 6, Y is 2. f(X,Y) :- Y is 4.

% ¡MAL!

?- f(2, X). X=0; X=2; X=4 Supongamos que se desea programar otra función matemática en Prolog:: Función rampa 6 5 4 3 2 1 0 -3

-2

-1

-1

0

1

2

3

4

5

6

7

8

9

10

-2

a Una primera solución, sin utilizar el corte podría ser: g(X,Y) :- X < 3, Y is 3 - X. g(X,Y) :- 3 =< X, X < 6, Y is X - 3. g(X,Y) :- X >= 6, Y is 9 - X. Incluyendo el corte se obtendría: g(X,Y) :- X < 3, !, Y is 3 - X. g(X,Y) :- 3 =< X, X < 6, !, Y is X - 3. g(X,Y) :- X >= 6, Y is 9 - X.

3 − x ,  g ( x ) =  x − 3,  9 − x ,

x= Y, Z is Y.

% min(+,+,?)

Ejemplo: dados tres hechos que describen los lados de un triángulo, escribir un programa que devuelva las longitudes ordenadas de forma ascendente: ordena(-,-,-). lado(a, 5). lado(b, 3). lado(c, 4). ordena2(X,Y, X1,Y1) :- X=Y, X1 is Y, Y1 is X. ordena3 (X, Y, Z) :- lado(a, X1), lado(b, Y1), lado(c, Z1), ordena2(X1,Y1, X2,Y2), ordena2(X2,Z1, X,Z2), ordena2(Y2,Z2, Y,Z). Para obtener un programa no determinista, lo que se puede plantear es; generar de forma combinatoria soluciones posibles y comprobar si son correctas. El método de búsqueda de Prolog se encarga de retroceder cuando una solución no es válida. ordena3 (X, Y, Z) :- lado(Xn, X), lado(Yn, Y), lado(Zn, Z), Xn \= Yn, Xn \= Zn, Yn \= Zn, X =< Y, Y =< Z.

Introducción al lenguaje PROLOG

20

16.- MECANISMO DE RESOLUCION Como se explicó en la introducción, Prolog utiliza un mecanismo conocido como Resolución lineal con unificación para resolver las preguntas que se le plantean (cláusulas negativas), el mecanismo consiste en realizar una búsqueda en profundidad y retroceso (backtracking) tratando de unificar la cláusula objetivo con las contenidas en la base de hechos, hasta lograr alcanzar la cláusula vacía. A continuación, se muestra de forma simplificada el algoritmo utilizado: 1. 2. 3. 4.

Se extraen las metas de la consulta y se introducen en orden en la lista de metas. Se realiza una llamada recursiva al procedimiento de búsqueda con la lista de metas pendientes. Si se encuentra solución, imprimirla Si no hay solución, imprimir false.

PROCEDIMIENTO DE BÚSQUEDA: 1º Se extrae la primera meta eliminándola de la lista. 2º Mientras sea posible: 3º Buscar un hecho o una regla que satisfaga la meta. 4º Si se encuentra: 5º Si ListaMetas no está vacía llamar al procedimiento de búsqueda de forma recursiva con ListaMetas y las variables equiparadas. 6º Si ListaMetas está vacía provocar un retorno con las metas satisfechas y las variables equiparadas. 7º Si hay solución de las metas al volver de la llamada en 5º, provocar un retorno con las soluciones. 8º En caso contrario, seguir en bucle, paso 3º. 9º Si no se ha encontrado solución alguna, provocar un retroceso, e.d. un retorno sin solución. Ejemplo. Base de hechos: primoroso(zorro). primoroso(oso). amoroso(oso). astuto(zorro).

Consulta: ?-primoroso(X), amoroso(X).

Mecanismo de resolución: ListaMetas = { primoroso(X), amoroso(X) } Resultado = Proc_Busqueda (ListaMetas, X) Pmeta = primera (ListaMetas) = primoroso(X) ListaMetas = resto (ListaMetas) = { amoroso(X) } Mientras sea posible: Primer hecho: ¿primoroso(zorro) satisface PMeta?, si; ==> Resultado = Proc_Busqueda (ListaMetas)

Introducción al lenguaje PROLOG

21

PMeta = primera (ListaMetas) = amoroso(X), X = zorro. ListaMetas = resto (ListaMetas) = { } Mientras sea posible: Primer hecho: ¿amoroso(oso) satisface PMeta?, no; Retroceso sin solución para amoroso(X). Resultado = Proc_Busqueda (ListaMetas) = False. Siguiente hecho: ¿primoroso(oso) satisface PMeta?, si; ==> Resultado = Proc_Busqueda (ListaMetas, X = oso) PMeta = primera (ListaMetas) = amoroso(X), X = oso. ListaMetas = resto (ListaMetas) = { } Mientras sea posible: Primer hecho: ¿amoroso(oso) satisface PMeta?, si; ListaMetas vacia => Provocar retorno con Solución { X = oso } Provocar retorno con Solución { X = oso } Imprimir Solución X = oso.

17.- LISTAS Una lista es una secuencia ordenada de elementos que pueden tener cualquier longitud. Los elementos de una lista puede ser cualquier tipo de términos (constantes, variables o estructuras), o incluso otra lista. Las listas en Prolog pueden representarse como un caso particular de árbol, una lista está formada por dos elementos: la cabeza (primer elemento de la lista) y la cola (resto de elementos de la lista). Ambos elementos se consideran componentes de la estructura cuyo functor es el punto “.” Ejemplos: 1. Lista con un único elemento “a” Notación en Prolog ⇒ .(a,[ ]) Representación gráfica ⇒

. a

[ ] %lista vacía

2. Lista con tres átomos “a,b,c” Notación en Prolog ⇒ .(a,.(b,.(c,[]))) Representación gráfica ⇒ a

. . b

. c

•

[ ] %lista vacía

Debido al frecuente uso de este tipo de estructura, Prolog permite una notación abreviada para representar listas. Los elementos de la lista aparecen separados por comas, y la lista completa aparece entre corchetes.

[a, b, c] []

Lista con los tres elementos a, b y c Lista vacía.

En la definición de predicados se pueden usar además variables y un separador: [a | L]

Lista con el elemento a en la cabecera y el resto en la variable L (cola).

Introducción al lenguaje PROLOG

22

[a, b | L]

Lista con los elementos a y b en la cabecera y el resto en la variable L (cola).

[X | L]

Lista con el primer elemento instanciado en la variable X y el resto en la variable L (cola).

[X, Y | L]

Lista con el primer elemento instanciado en la variable X, el segundo en Y y el resto en la variable L (cola).

•

Ejemplos de predicados útiles en el manejo de listas.

1º.- Número de elementos de una lista: longitud(Xs, N) longitud([ ], 0). longitud([X | Xs], N) :- longitud(Xs, N1), N is N1+1.

2º.- Pertenencia a una lista: pertenece(X, L) % 1ª forma pertenece(X, [ ]) :- fail. pertenece(X, [X|L]). pertenece(X, [Y|L]) :- X\=Y, pertenece(X, L). % 2ª forma pertenece(X, [X|L]). pertenece(X, [Y|L]) :- pertenece(X, L).

3º.- Creación de una lista a partir de dos listas (concatenar dos listas: Append). concatenar(L1,L2,L3) concatenar([ ], L, L). concatenar([X|C1],L2, [X|C3]) :- concatenar(C1,L2,C3).

4º.- Eliminación de un elemento X de una lista L1, como consecuencia se obtiene la lista L2 (se elimina la primera aparición del elemento). elimina(X,L1,L2) % 1ª forma elimina(X,[]) :- fail. elimina(X,[X|Cola],Cola). elimina(X,[Y|C1],[Y|C2]) :- elimina(X,C1,C2). % 2ª forma elimina(X,[X|Cola],Cola). elimina(X,[Y|C1],[Y|C2]) :- elimina(X,C1,C2).

Introducción al lenguaje PROLOG

23

5º.- Eliminación de todas las apariciones de un elemento X en una lista L1, como consecuencia se obtiene la lista L2. borrar(X,L1,L2) borrar(_,[ ],[ ]). borrar(X,[X|C],M) :- ! , borrar(X,C,M). borrar(X,[Y|L1],[Y|L2]) :- borrar(X,L1,L2).

6º.- Invertir todos los elementos de una lista. invertir(L1,L2) invertir([],[]). invertir([X|C],Z) :- invertir(C,C1),concatenar(C1,[X],Z).

•

Ejemplos de unificación de listas.

Lista 1 [X,Y,Z] [mustang] [X,Y|Z]

Lista 2 [esto,es,prolog] [X|Y] [cuando,harry,encontro,a,sally]

[X,busca,Z] [X,[actor,Z]] [[el,Y]|Z]

[harry,Y,sally] [cine,[Y,meg]] [[X,libro],esta,aquí]

Instanciaciones X=esto, Y=es, Z=prolog X=mustang, Y=[] X=cuando, Y=harry, Z=[encontro,a,sally] X=harry, Y=busca, Z=sally X=cine, Y=actor, Z=meg X=el, Y=libro, Z=[esta,aquí]

Si se tienen dudas de la posible unificación de dos listas o de términos en general, se puede asegurar el resultado de la unificación utilizando el predicado interno “=” del intérprete de Prolog. Ejemplos: ?-[X,libro]=[lapiz,Y]. X=lapiz Y=libro Yes ?-[X,libro]=[Y,lapiz]. No

Introducción al lenguaje PROLOG

24

18.- EJERCICIOS BÁSICOS

•

Ejercicio 1

Enunciado: Programar en Prolog una cláusula que calcule el factorial de n.

Soluciones…Ejercicio 1

•

Solución 1ª

factorial(0, 1). factorial(N, X) :-N1 is N - 1, factorial(N1, X1),X is X1 * N.

La solución anterior no funciona bien si le pasamos un número negativo, para evitar este problema podemos utilizar el fallo y el corte:

•

Solución 2ª

factorial2(N, _) :- N < 0, fail. factorial2(0, 1). factorial2(N, X) :- N > 1, N1 is N - 1, factorial(N1, X1), X is X1 * N.

•

Solución 3ª

factorial3(N, _) :- N < 0, !, fail. factorial3(0, 1) :- !. factorial3(N, X) :- N > 1, N1 is N - 1, factorial(N1, X1), X is X1 * N.

•

Solución 4ª

factorial4(N, _) :- N < 0, !, fail. factorial4(0, 1) :- !. factorial4(N, X) :- N1 is N - 1, factorial(N1, X1), X is X1 * N.

Introducción al lenguaje PROLOG

25

Ejercicio 2

•

Enunciado: Programar la siguiente función matemática en Prolog. Función Sierra 8 7 6 5 4 3 2 1 0 -1 -2 -3

0

3

6

9

12

nodefinida x < 0  x, 0≤ x Y) THEN Swap2 (X, Y) ; IF (X > Z) THEN Swap2 (X, Z) ; IF (Y > Z) THEN Swap2 (Y, Z) ; END;

(* Ordena2 *)

BEGIN Ordena3 (X, Y, Z); IF (X > 0) AND (X + Y > Z) THEN BEGIN IF (X = Z) THEN

(* Es_triangulo *)

Introducción al lenguaje PROLOG

28 WRITELN (‘Equilatero’); ELSE IF (X = Y) OR (Y = Z) WRITELN (‘Isósceles’); ELSE WRITELN (‘Escaleno’); RETURN (TRUE);

END ELSE RETURN (FALSE); END;

•

Planteamiento 1º

En primer lugar, se plantean las condiciones necesarias para poder construir un triángulo T(a,b,c) a partir de las magnitudes a, b y c. Condiciones previas para que T(a,b,c) sea triángulo: [a>0, b>0, c>0] Restricción necesaria para que T(a,b,c) sea triángulo: a+b>c si c>a,b a+c>b si b>a,c b+c>a si a>b,c

T(a,b,c) es equilátero si a=b=c T(a,b,c) es isósceles si se cumple a=c, b!=a a=b, c!=a c=b, a!=c T(a,b,c) es escaleno si se cumplen a!=b b!=c a!=c •

Solución 1ª lados_positivos(A,B,C) :- A>0, B>0, C>0. lados_adecuados(A,B,C) :- A=0. lados_adecuados(A,B,C) :- A=