Prolog Sintaxis y significado de los programas. cap..2

INTRODUCCIÓN:

En el capitulo anterior, conocimos un gran terreno de Prolog, pero aun nos hace falta profundizar, mas en el tema de Prolog el siguiente espacio de palabras y ejercicios, conoceremos que mas puede hacer Prolog, y hasta donde podemos llegar con la Programación, y sobre todo como identifica una linea de código, es decir un objeto en  Prolog.

2. Sintaxis y significado de los programas.

2.1.- Lo siguientes es conocer que tipos básicos de datos, dice que Prolog reconoce a un objeto por su sintaxis, ya que en Prolog no es necesario declarar el tipo de dato que se usara, como por ejemplo cuando declaramos variable en java primero debemos declarar que tipo es (int, float, long etcc....) Prolog no, entre las conocidas de Prolog son como las que se muestran en la figura  2.1:

figura 2.1

Los Átomos:

Estas se construyen de 3 formas:

1). Cadenas de letras, dígitos y el símbolo de subrayado (_), pero comenzando siempre con una letra minúscula.

Ejemplos :

ana nil x25 x_25 x_25 AB x_ x_y a_b_c

2). Cadenas de caracteres especiales.

Ejemplos: <---> ===> ... .:. ::=

3). Cadenas de caracteres encerrados en comillas simples (').

Ejemplos: 'Tomas' 'Juan_Hernandez' 'Jose Lopez Lopez'

Números.

Pueden ser enteros ó reales :

Ejemplos: 1 -97 3.141592 -1.2 0

Variables.

Son Cadenas de letras, dígitos y el símbolo de subrayado ( _ ) que comienzan siempre con una letra mayúscula ó un símbolo de subrayado.

Ejemplos: X Nombre_1 _x23 _55

Estructuras.

Son objetos que tienen varios componentes.

Ejemplo: fecha( 20, agosto, 1992)

fecha recibe el nombre de functor; En este caso todos sus componentes son constantes pero pueden ser variables ó incluso estructuras. Aunque las estructuras tienen varios componentes, en los programas Prolog se tratan como objetos únicos. Es decir, en Prolog, todos los objetos son términos.

Ejemplo: agosto y fecha( 20, agosto, 1992) son ambos términos.

Todos los objetos estructurados se pueden interpretar como árboles donde el functor es la raíz del árbol y sus componentes son las hojas del árbol. Si un componente es a su vez una estructura, entonces será un subárbol del árbol inicial.

[Inf. Tomada por el Autor:  Edgar Altamirano Carmona  Universidad  Autónoma  de  Guerrero.]

Una ves conocido esto vamos a empezar con algunos ejercicios, con su respectivas resoluciones y vamos a explicar como funciona y ahora que realizara Prolog por nosotros......

Ejercicio. Sugiera una representación para rectángulos, cuadrados y círculos como objetos Prolog estructurados. Escriba algunos ejemplos que representen objetos físicos concretos utilizando la representación que sugirió.

Rectángulos

rectangulo(p1(X,Y),p2(Z,Y),p3(Z,W),p4(X,W).

Cuadrados

cuadrado (p1(X,Y),p2(Z,Y),p3(Z,W),p4(X,W)).

El cuadrado es de  la misma manera que el rectángulo, ya que es un caso especial de él.

 círculos

circunferencia (puntoori(X,Y), radio(R)).

La geometría nos dice que para construir cualquier figura geométrica al menos necesitamos un punto de inicio, y para nuestro caso el circulo, su punto de inicio y su radio.

2.2. Matching (empatamiento).

La operación más importante sobre los términos es la de matching (empatamiento). Dados dos términos cualesquiera decimos que "empatan" si se cumple lo siguiente :

(1). Son idénticos; ó,

(2). Las variables en ambos términos pueden instanciarse a objetos de tal modo que después de la sustitución de las variables por estos objetos los términos puedan ser idénticos.

Ejemplo. Los términos fecha( D, M, 1992) y fecha( D1, mayo, Y1) empatan. Una instanciación que hace que ambos términos sean idénticos es:

D se instancia a D1.

M se instancia a mayo.

Y1 se instancia a 1992.

Ejemplo. Los términos fecha( D, M, 1992) y fecha( D1, M1, 1990) no empatan.

Ejemplo. Los términos fecha( X, Y, Z) y punto( X, Y, Z) tampoco empatan.

El matching es un proceso que toma como entrada dos términos y checa si empatan. Si los términos no empatan decimos que el proceso falla. Si los términos empatan el proceso tiene éxito y las variables se instancian en ambos términos a los valores que las hacen ser idénticas.

Ejemplo. Consideremos nuevamente el matching de dos fechas. La respuesta a esta operación se le puede pedir a Prolog usando el operador "=" de la siguiente forma :

?- date( D, M, 1992) = date( D1, mayo, Y1).

Las reglas generales para decidir si dos términos S y T empatan son las siguientes :

(1). Si S y T son constantes entonces S y T empatan únicamente si se

trata de los mismos objetos.

(2). Si S es una variable y T es cualquier cosa, entonces empatan y S se instancia a T. Y a la inversa, si T es la variable, entonces T se instancia a S.

(3). Si S y T son estructuras empatan únicamente si :

(a). S y T contienen el mismo functor principal, y

(b). Todos sus componentes correspondientes empatan.

La instanciación resultante se determina por la operación de matching sobre los componentes.

[Inf. Tomada por el Autor:  Edgar Altamirano Carmona  Universidad  Autónoma  de  Guerrero.]

Ejercicios.

1. ¿ Las siguiente operaciones de matching tienen éxito ó fallan ?

Si tienen éxito, ¿cuáles son las instanciaciones resultantes en las variables?

(a). punto( A, B) = punto( 1, 2).

(b). punto( A, B) = punto( X, Y, Z).

(c). +( 2, 2) = 4.

(d). +( 2, D) = +( E, 2).

(e). triangulo(punto(-1,0),P2,P3) = triangulo(P1,punto(1,0),punto(0,Y)).

(a). punto( A, B) = punto( 1, 2).

 Si tiene éxito

(b). punto( A, B) = punto( X, Y, Z).

No hay éxito

(c). +( 2, 2) = 4.

No hay éxito, no hay nada que indique que la operación +(2,2) deba realizar la suma, en consecuencia se toman como términos diferentes, por ello el matching falla.

(d). +( 2, D) = +( E, 2).

Si hay éxito

(e). triangulo(punto(-1,0),P2,P3) = triangulo(P1,punto(1,0),punto(0,Y)).

Si hay éxito

2. Usando la representación que se definió anteriormente para segmentos de línea, escriba un término que represente cualquier segmento de línea vertical en x = 5.

linea(p1(5,Y1),(5,Y2))

3. Asuma que un rectángulo se representa con el término rectángulo( P1, P2, P3, P4) donde P1,P2,P3,P4 son los vértices del rectángulo ordenado positivamente. Defina la relación regular( R) que es verdad (true) si R es un rectángulo cuyos lados son vertical y horizontal.

2.3. Significado declarativo.

Los programas Prolog pueden entenderse de dos maneras: declarativa y proceduralmente.

El significado declarativo de los programas determina si una meta dada es cierta, y si es el caso, para qué valores de las variables es cierta.

Para definir de manera más precisa el significado declarativo, necesitamos introducir antes el concepto de "instancia" de una cláusula.

Una instancia de una cláusula C es la cláusula C con cada una de sus variables sustituidas por algún término. Una "variante" de una cláusula C es una instancia de la cláusula C tal que cada variable se sustituye por otra variable.

Ejemplo. Considere la cláusula:

tienehijo(X) :- pariente( X, Y).

dos variantes de esta cláusula son :

tienehijo(A) :- pariente(A, B).

tienehijo(X1) :- pariente(X1, X2).

Instancias de esta cláusula son :

tienehijo(pedro) :- pariente( pedro, Z).

tienehijo(beto) :- pariente( beto, muchacha(carolina)).

Dado un programa y una meta G, el significado declarativo nos dice :

Una meta G es cierta (esto es, satisfactible, o se sigue lógicamente del programa) si y solamente si :

(1). Existe una cláusula C en el programa tal que,

(2). Existe una instancia I de la cláusula C tal que,

(a). La cabeza de I es idéntica a G, y

(b). todas las metas en el cuerpo de I son ciertas.

Esta definición se extiende a las preguntas de Prolog. En general una pregunta al sistema Prolog es una "lista" de metas separadas por comas.

Una lista de metas es cierta si todas las metas en la lista son ciertas para la misma instanciación de las variables. Los valores de las variables resultan de la instanciación mas general.

Una coma entre metas denota una conjunción de metas: todas tienen que ser ciertas. Prolog acepta además la disyunción de metas : cualquiera de las metas en una disyunción tiene que ser verdadera. La disyunción se indica con el símbolo de punto y coma (;).

Para que nos quede mas aun claro que el agua vamos consideremos este otro ejemplo:

Ejemplo.

P :- Q ; R.

se lee: "P es cierta si Q es cierta ó si R es cierta"

El significado de ésta cláusula es el mismo que las dos siguientes:

P :- Q.

P :- R.

La coma tiene prioridad de ejecución. La siguiente cláusula:

P :- Q, R ; S, T, U.

se interpreta como

P :- ( Q, R) ; (S, T, U).

y significa lo mismo que las cláusulas:

P :- Q, R.

P :- S, T, U.

Ejercicios.

1. Considere el siguiente programa:

f( 1, uno).

f( s(1), dos).

f( s(s(1)), tres).

f( s(s(s(X))), N) :- f( X, N).

¿cómo contestará Prolog las siguientes preguntas? Cuando sean posibles varias respuestas, dé al menos dos de ellas.

(a). ?- f( s(1), A).  

SU INTERPRETACIÓN ES .-A ES DOS SI s(1), es DOS PROLOG LO INTERPRETA ........FIGURA 2.3 

FIGURA 2.3

DE LA MISMA FORMA PARA LAS DEMÁS..................................

(b). ?- f( s(s(1)), dos).

(c). ?- f( s(s(s(s(s(s(1)))))), C).

(d). ?- f( D, tres).

2. El siguiente programa dice que dos personas son parientes si,

(a). uno es predecesor del otro, ó

(b). ambos tienen un predecesor común, ó

(c). ambos tienen un sucesor común :

parientes( X, Y) :- predecesor( X, Y).

parientes( X, Y) :- predecesor( Y, X).

parientes( X, Y) :- predecesor( Z, X), predecesor( Z, Y).

parientes( X, Y) :- predecesor( X, Z), predecesor( Y, Z).

¿puede usted acortar el programa usando la notación de ';' ?

parientes(X,Y) :- predecesor(X,Y) ; predecesor(Y,X) ;predecesor(Z,X),

 predecesor(Z,Y) ; predecesor(X,Z) , predecesor(Y,Z).

3. Reescriba el siguiente programa sin utilizar la notación de ';' :

traducir( Numero, Palabra) :-

Numero = 1, Palabra = uno;

Numero = 2, Palabra = dos;

Numero = 3, Palabra = tres.

traducir(Numero,Palabra) :- Numero=1,Palabra=uno.

traducir(Numero,Palabra) :- Numero=2,Palabra=dos.

traducir(Numero,Palabra) :- Numero=3,Palabra =tres.

2.4. Significado procedural.

El significado procedural especifica el cómo contesta Prolog a las preguntas. Responder a una pregunta significa tratar de satisfacer una lista de metas. Estas pueden satisfacerse si las variables que existen en las metas pueden instanciarse de tal modo que las metas se sigan lógicamente del programa. Así el significado procedural de Prolog es un procedimiento para ejecutar una lista de metas con respecto a un programa dado. Ejecutar las metas significa tratar de satisfacerlas.

Llamemos a este procedimiento 'ejecuta'.

 las entradas y salidas a este procedimiento son :

entrada : un programa y una lista de metas.

salida : un indicador de éxito / falla y una instanciación particular

de las variables.

el significado de las dos salidas es como sigue :

(1). El indicador de éxito/falla es 'yes' si las metas son satisfactibles y 'no' si ocurre lo contrario. Decimos que 'yes' señala una terminación exitosa y 'no' una falla.

(2). Una instanciación de las variables se produce solamente en el caso de una terminación exitosa; en el caso de una falla no hay instanciación.

Ejemplo. En el siguiente ejemplo se hace una traza de la ejecución para ilustrar el significado procedural de Prolog :

(a). Programa.

enorme( oso). % cláusula 1

enorme( elefante). % cláusula 2

chico( gato). % cláusula 3

cafe( oso). % cláusula 4

negro( gato). % cláusula 5

gris( elefante). % cláusula 6

oscuro( Z) :- % cláusula 7 : cualquier negro es oscuro.

negro( Z).

oscuro( Z) :- % cláusula 8 : cualquier café es oscuro.

cafe( Z).

en nuestro programa en Prolog se vera asi....

?- oscuro( X), enorme( X). % Quién es oscuro y enorme ?

(c). Traza de la ejecución.

(1). Lista inicial de metas : oscuro(X), enorme(X).

(2). Examina el programa de arriba hacia abajo buscando una cláusula cuya cabeza empate con la primera meta : oscuro(X). Se encuentra la cláusula 7 :

oscuro( Z) :- negro( Z).

se reemplaza la primera meta con el cuerpo instanciado de la cláusula 7, dando una nueva lista de metas :

negro(X), enorme(X).

(3). Examina el programa para encontrar un empatamiento de negro(X). Se encuentra la cláusula 5: negro( gato). Esta cláusula no tiene cuerpo, así que la lista de metas, luego de instanciarse se convierte en :

enorme(gato)

(4). Examina el programa para buscar la meta enorme(gato), no se encuentra ninguna cláusula. Por lo tanto se realiza un proceso de backtracking al paso 3) y se elimina la instanciación X = gato. Ahora la lista de metas es de nuevo:

negro(X), enorme(X).

Se continúa examinando el programa a partir de la cláusula 5. No se encuentra ninguna cláusula. Por lo tanto se realiza un proceso de backtracking nuevamente al paso (2) y se continúa examinando a partir de la cláusula 7. Se encuentra la cláusula 8:

oscuro(Z) :- cafe(Z).

Se reemplaza la primera meta en la lista de metas por cafe(X), dando:

cafe(X), enorme(X)

(5). Examina el programa buscando empatar cafe(X), encuentra cafe(oso). Esta cláusula no tiene cuerpo, así que la lista de metas es ahora:

enorme(oso)

(6). Examina el programa y encuentra la cláusula enorme(oso). Esta cláusula no tiene cuerpo, así que la lista de metas se queda vacía. Esto indica una terminación exitosa y la instanciación correspondiente a la variable queda como :

X = oso.

Ejercicio.

1. Considere el programa anterior y realize la traza de ejecución a la pregunta :

?- enorme(X), oscuro(X).

compare su traza de ejecución con la anterior, ya que esencialmente es la misma pregunta pero con otro orden. ¿En cuál de ambos casos Prolog realiza más trabajo antes de encontrar la respuesta final?

2.5. El problema del mono y la banana.

El problema del mono y la banana se utiliza como un ejemplo sencillo de solución de problemas. El siguiente programa en Prolog mostrará como se pueden utilizar los mecanismos de 'matching' y 'backtracking'. Utilizaremos la siguiente versión del problema: Existe un mono en la puerta de un cuarto; enmedio del cuarto cuelga una banana del techo; el mono está hambriento y desea capturar la banana, pero no puede alcanzarla desde el piso. En la ventana del cuarto hay una caja que el mono puede usar.

El mono puede realizar solamente las siguientes acciones: caminar sobre el piso, subir a

la caja, empujar la caja (si el mono está junto a la caja), y, agarrar la banana (si el mono

está sobre la caja y bajo la banana).

¿Cómo puede el mono llegar a capturar la banana?

Análisis del problema.

Una tarea importante en programación es encontrar una representación del problema en

términos del lenguaje de programación utilizado.

En este caso podemos pensar del 'mundo del mono' en términos de 'estados' que

cambian con el tiempo. El estado actual se determina por la posición actual de los

objetos.

Por ejemplo, el estado inicial del mundo está determinado por:

1). El mono está en la puerta.

2). El mono está sobre el piso.

3). La caja está en la ventana.

4). El mono no tiene la banana.

Es conveniente combinar todas estas piezas de información en un solo

objeto estructurado. Escogeremos la palabra 'estado' como el functor que

retendrá los cuatro componentes anteriores :

El estado final es una situación en que el mono tiene la banana, es decir, cualquier

estado en cuyo componente último sea :

estado( _, _, _, silatiene)

Las transiciones permitidas que cambian el mundo de un estado a otro son

las siguientes :

(1). agarrar la banana.

(2). subir a la caja.

(3). empujar la caja.

(4). caminar en el cuarto.

No todas las transiciones son posibles en cada estado posible del mundo del mono. Por ejemplo, la transición 'agarrar la banana' es solamente posible si el mono está sobre la caja y bajo la banana y si no tiene todavía la banana. Estas transiciones ó reglas se pueden formalizar en Prolog como una relación de tres componentes que llamaremos 'mover':

mover( Estado1, M, Estado2)

Los tres argumentos de la relación especifican un movimiento tal que:

Estado1 ----- M -----> Estado2

'Estado1' es el estado antes del movimiento 'M'; 'M' es el movimiento realizado, y 'Estado2' es el estado del mundo del mono después de haberse realizado el movimiento 'M'.

El movimiento 'agarrar' es una precondición necesaria antes de la meta final y lo podemos definir con la cláusula:

mover( estado( enmedio, sobrelacaja, enmedio, nolatiene),

agarrarlabanana,

estado( enmedio, sobrelacaja, enmedio, silatiene)).

Esta cláusula nos dice que después de ejecutarse, el mono tendrá la banana y permanece sobre la caja y enmedio del cuarto.

De una forma similar a la anterior podemos expresar el hecho de que el mono estando sobre el piso puede caminar de la posición P1 a cualquier posición P2. El mono puede realizar esta acción sin importar la posición de la caja y si tiene ó no la banana:

% caminar de P1 a P2

mover( estado( P1, sobreelpiso, B, H),

caminar( P1, P2 ),

estado( P2, sobreelpiso, B, H)).

Esta cláusula nos dice entre otras cosas:

-El movimiento realizado fue: 'caminar de una posición P1 a otra P2'.

-El mono está sobre el piso antes y después del movimiento.

-La caja está en algún lugar B y permanece en el mismo lugar.

-El estado de tiene ó no tiene la banana permanece igual después del movimiento.

La cláusula especifica un conjunto de movimientos posibles porque es aplicable a cualquier situación que se apareje ('matching') al estado antes del movimiento.

Hasta aquí hemos definido los movimientos 'agarrar la banana' (1) y 'caminar de P1 a P2' (4). Los otros dos tipos de movimientos 'empujar la caja' (3) y 'subir a la caja' (2) se pueden definir de manera similar.

Finalmente, la pregunta que nuestro programa debe contestar es: ¿ Puede el mono, desde algún estado inicial 'S', capturar la banana ?

Esta pregunta se puede formular con el predicado:

puedetener(S)

donde el argumento 'S' es un estado del mundo del mono. El programa para satisfacer el predicado 'puedetener' lo podemos basar en dos observaciones:

(1). Para cualquier estado 'S' en el cual el mono ya tiene la banana, el predicado 'puedetener' debe ser cierto:

puedetener( estado( _, _, _, silatiene)) :- !.

(2). De otro modo, el mono puede tener la banana desde un estado S1 si existe algún movimiento M del estado S1 a otro estado S2, tal que el mono pueda tener la banana en el estado S2 :

puedetener( S1) :-

mover( S1, M, S2),

puedetener(S2).

[Inf. Tomada por el Autor:  Edgar Altamirano Carmona  Universidad  Autónoma  de  Guerrero.]

Programa del mono y la banana.

El programa completo es el siguiente:

% Movimientos válidos.

% (1). Agarrar la banana.

mover( estado( enmedio, sobrelacaja, enmedio, nolatiene),

agarrarlabanana,

estado( enmedio, sobrelacaja, enmedio, silatiene)).

% (2). Subir a la caja.

mover( estado( P, sobreelpiso, P, H),

subiralacaja,

estado( P, sobrelacaja, P, H)).

% (3). Empujar la caja de P1 a P2.

mover( estado( P1, sobreelpiso, P1, H),

empujar( P1, P2),

estado( P2, sobreelpiso, P2, H)).

% (4). Caminar de P1 a P2.

mover( estado( P1, sobreelpiso, B, H),

caminar( P1, P2),

estado( P2, sobreelpiso, B, H)).

% Resolver si el mono puede tener la banana.

% Caso 1 : El mono ya tiene la banana.

puedetener( estado( _, _, _, silatiene)) :- !.

% Caso 2 : El mono debe realizar alguna actividad para tener la banana.

puedetener( S1) :-

mover( S1, M, S2),

puedetener(S2).

Nuestro Programa estando en Prolog:......

Análisis del comportamiento procedural.

Consideremos la siguiente pregunta al programa anterior:

?- puedetener( estado( enlapuerta,sobreelpiso,enlaventana,nolatiene)).

Prolog contestará: 'yes'. O en su caso con un (true)------ figura 2.5

El proceso llevado a cabo por Prolog para alcanzar ésta respuesta involucra una serie de búsquedas de movimientos válidos entre una serie de movimientos alternativos posibles. En algún punto de la búsqueda existirá un movimiento equivocado y válido que conducirá a una hoja del árbol de búsquedas, en tal situación, un proceso de 'backtracking' (vuelta atrás) se llevará a cabo para continuar con el proceso :

Árbol de búsqueda para el problema del mono y la banana. El proceso de backtracking se realiza una sola vez. Las búsquedas se realizan de arriba a abajo y de izquierda a derecha.

Conclusión:

Su pudo identificar que prolog no es  lenguaje común, es parecido, pero no es igual ya que como lo mencionamos antes otros programa necesitan reconocer primero el tipo de dato u objeto, Prolog solo necesita saber cual es la sintaxis del objeto para saber que tipo de dato se trata, como también ahora sabemos que se parece mucho a las técnicas de búsqueda que aplicábamos en capítulos anteriores en especial las de búsqueda ciega en el ultimo capitulo se puede ver como se soluciono el problema del mono y la banana.


HUMOR:

Referencias

Upuntes de Prolog.
Autor: Edgar Altamirano Carmona
Universidad Autónoma de Guerrero.