Capitulo 5

5. Control del Retroceso (Backtracking).
Hemos visto hasta ahora que el programador puede controlar la ejecución de un programa
ordenando las cláusulas y metas. En este capítulo estudiaremos otra manera de control
conocida como corte (cut).

5.1. Prevención del retroceso.
Prolog realizará automáticamente el retroceso si es necesario para satisfacer una meta. El
retroceso automático es un concepto de programación muy útil porque libera al
programador de la tarea de programar explícitamente los retrocesos. Aunque por otra
parte el retroceso sin control puede ocasionar ineficiencia en un programa. Por lo tanto es
necesario saber prevenir y controlar el retroceso.

la relación entre X y Y puede especificarse con las tres reglas siguientes :
 Regla 1 : if X < 3 then Y = 0
 Regla 2 : if 3 <= X and X < 6 then Y = 2
 Regla 3 : if 6 <= X then Y = 4
lo cual puede escribirse en Prolog como :
 f(X,0) :- X < 3. % Regla 1
 f(X,2) :- 3 =< X, X < 6. % Regla 2
 f(X,4) :- 6 =< X. % Regla 3

?- f(7, Y).
 Y = 4.
Analicemos que ha sucedido. Las tres reglas fueron exploradas antes de que la respuesta
final fuera obtenida. Esto produjo la siguiente secuencia de metas:
regla 1 : 7 < 3 falla, retrocede y trata la regla 2.
regla 2 : 3 ó 7 tiene éxito, enseguida 7 < 6 falla, retrocede y trata la regla 3.
regla 3 : 6 ó 7 tiene éxito.
esta traza nos revela otra fuente de ineficiencia. Primero establece que X < 3 no es cierto
(7<3 3="<" 7="" es="" falla="" la="" meta="" nbsp="" nosotros="" p="" pero="" que="" sabemos="" siguiente="" tiene="" x="" xito="">una vez que la primera prueba ha fallado, la segunda prueba va a realizarse como si fuese
la negación de la primera. Por lo tanto la segunda prueba es redundante y la meta
correspondiente puede omitirse. Lo mismo es verdad acerca de la meta 6 =< X en la regla
3. Esto nos lleva a la siguiente formulación de las tres reglas anteriores:
 if X < 3 then Y = 0,
 de-otro-modo if X < 6 then Y = 2,
 de-otro-modo Y = 4.
lo cual nos lleva a la tercera versión en Prolog :
 f(X,0) :- X < 3, !.
 f(X,2) :- X < 5, !.
 f(X,4).
éste último programa produce los mismos resultados que la versión original pero es la
versión mas eficiente.
Nótese sin embargo que si removemos los símbolos de corte:
 f(X,0) :- X < 3.
 f(X,2) :- X < 5.
 f(X,4).
la ejecución producirá soluciones múltiples y equivocadas. Por ejemplo:
 ?- f(1,Y).
 Y = 0;
 Y = 2;
 Y = 4;
 no.

5.2. Usando el corte.
Cálculo del máximo.
El procedimiento para encontrar el valor máximo de dos números puede programarse
como una relación :
 max(X,Y,Max).
donde Max = X si X es mayor ó igual a Y, y Max es Y si X es menor a Y :
 max(X,Y,X) :- X >= Y.
 max(X,Y,Y) :- X < Y.
estas dos reglas son mutuamente exclusivas; una formulación mejor es :
 if X ó Y then Max = X,
 de-otro-modo Max = Y.
ésto se escribe en Prolog usando el corte como :
 max(X,Y,X) :- X >= Y, !.
 max(X,Y,Y). 

Capitulo 4 (Ejercicios 4.3)

Ejercicio
El problema de las ocho reinas.
Se trata de colocar 8 reinas en un tablero de ajedrez vacío de tal manera que ninguna
reina pueda atacar directamente a otra reina. La solución será programada como un
predicado unario solucion(Pos) que será verdadero si y solamente si Pos representa una
posición de las ocho reinas sin que se ataque una a ninguna otra.
Primero tenemos que elegir una representación para las posiciones del tablero. Una
manera lógica sería representar las posiciones de las ocho reinas como una lista de ocho
ítems, cada ítem correspondiendo a la posición de cada reina. La posición de una reina
será especificada por un par de coordenadas (X,Y) sobre el tablero, donde cada
coordenada es un entero entre 1 y 8. En notación de Prolog lo podriamos manejar así:
X/Y donde el símbolo “/” en este caso no indica realizar una división, sino solamente es
un separador de ambos símbolos X y Y.

Colocar n-reinas en un tablero rectangular de dimensiones NxN, de forma que no se encuentren más de una en la misma línea horizontal, vertical o diagonal.

Solución:

La implementación del problema de las n-reinas en WSI-Prolog consiste en tres pasos:

1. Generar el tablero de dimensión n.
2. Generar la permutación sobre ese tablero.
3. Comprobar si el tablero cumple la condición donde todas las reinas colocadas no se amenacen entre sí.

Código fuente:

1.- La siguiente línea añade reglas de nivel superior, es muy importante para poner en ejecución sin el cual SWI-Prolog nos dará error.
[user].
2.- nreinas (+N,?Sol). Es el predicado principal que nos permite conocer el resultado de la operación.
nreinas(N,Sol) :- generarTablero(N,Tablero), permutar(Tablero,Sol), buenTablero(Sol).
3.- generarTablero(+X,?Y). Este predicado genera un tablero de dimensión variable (N).
generarTablero(0,[]).
generarTablero(X,[X|R]) :- XMenos1 is X - 1, XMenos1 >= 0, generarTablero(XMenos1,R).
4.- permutar(?LX,?LY). Verifica si LY es una permutación de los elementos de LX, la única permutación de la lista vacía es la lista vacía.
permutar([],[]).
permutar(X,[C|Z]) :- seleccionar(X,C,R), permutar(R,Z).
5.- seleccionar(L,X,R). Verifica si X es un elemento de L y R, es la lista L sin el elemento X.
seleccionar([X|R],X,R).
seleccionar([C|R],X,[C|Y]) :- seleccionar(R,X,Y).
6.- buenTablero(+X). Verifica si en el tablero X, ninguna reina amenaza a otra; considerando que amenazar también se entiende ser amenazado.
buenTablero([]).
buenTablero([C|R]) :- not(amenaza(C,R)), buenTablero(R).
7.- amenaza(X,Y). Verifica si una reina colocada en la columna X de la fila n de un tablero amenaza a cualquiera de las demás reinas colocadas en las filas 0.n-1 del resto del tablero, y cuyas columnas vienen especificadas en la lista Y.
amenaza(X,Prof,[C|_]) :- X is C+Prof;
X is C-Prof;
X = C.
amenaza(X,Prof,[_|R]) :- ProfMas1 is Prof + 1, amenaza(X,ProfMas1,R).
amenaza(_,[]) :- fail.
amenaza(X,Y) :- amenaza(X,1,Y).

Ejecución en SWI-Prolog:

La imagen está delimitada en tres secciones cuya descripción es:

a) Código.- Sección de código ingresado.
b) Ctrl+D.- Combinación de teclas para poder compilar el algoritmo..
c) Pruebas.- Resultado de la ejecución del algoritmo compilado nreinas (n,S), donde n es igual a la dimensión.

Gráficos de los resultados obtenidos

Representación gráfica del tablero de 4 dimensiones nreinas (4,S), donde S=(3,1,4,2) en el que se aprecia la ausencia de amenaza y amenazado.

Representación gráfica del tablero de 8 dimensiones nreinas (8,S), donde S=(8,4,1,3,6,2,7,5) en el que se aprecia la ausencia de amenaza y amenazado.

Capitulo 4 (Ejercicio 4.2)

Este ejemplo muestra como una construcción matemática abstracta se puede trasladar
fácilmente al lenguaje Prolog. Un autómata finito no determinístico es una máquina
abstracta que recibe como entrada una cadena de símbolos y decide si acepta ó rechaza
dicha entrada. El autómata contiene un cierto número de estados y siempre se encuentra
en alguno de ellos; puede además cambiarse de un estado a otro. Su estructura interna
se puede representar con un grafo de transición

Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.

Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.

La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.

Capitulo 4 (Ejercicios 4.1)

Ejercicios.
Escribir preguntas para encontrar lo siguiente: 
a). Nombres de las familias que no tienen hijos. 
b). Nombres de todos los hijos que no trabajan. 
c). Nombres de las familias con esposas que trabajan y esposos que no trabajan. 
d). Todos los hijos cuyos padres difieren en edad con al menos 10 años. 
e). Definir la relación: gemelos(Hijo1, Hijo2) que sirva para encontrar geme-los en la 
base de datos.
Una base de datos se puede representar en Prolog como un conjunto de hechos. Por 
ejemplo, una base de datos acerca de familias: cada familia se representa con una sola 
cláusula y tiene tres componentes: Esposo, Esposa e Hijos. El número de hijos es variable 
y se debe representar con una lista. A su vez cada persona (esposo, esposa ó hijo) tiene 
cuatro componentes: nombre, apellido, fecha de nacimiento y trabajo : 
familia( 
 persona(juan,perez,fecha(7,mayo,1950),trabaja(uag,2000)), 
 persona(ana,flores,fecha(9,mayo,1951),no_trabaja), 
 [persona(jose,perez,fecha(5,mayo,1973),no_trabaja), 
 persona(susana,perez,fecha(5,junio,1975),no_trabaja) 
 ]). 
familia( 
 persona(jorge,flores,fecha(21,abril,1953),trabaja(uag,2500)), 
 persona(edith,juarez,fecha(5,enero,1960),no_trabaja), 
 [persona(pedro,flores,fecha(1,julio,1980),no_trabaja) 
 ]). 
...
Una vez definida la base de datos, es posible ir adicionando procedimientos que hagan 
más práctica la interacción con ella : 
% X es esposo. 
esposo(X) :- familia(X,_,_). 
% X es esposa. 
esposa(X) :- familia(_,X,_). 
% X es hijo. 
hijo(X) :- familia(_,_,Hijos), miembro(X,Hijos). 
miembro(X, [X|L]). 
miembro(X, [Y|L]) :- miembro(X, L).

familia(
persona(jorge,jaimes,fecha(09,mayo,1991),no_trabaja), % esposo
[ %, esposa
[ %, hijos.

familia(
persona(gustavo,jaimes,fecha(23,abril,1964),trabaja(comerciante,3000)),
persona(isabel,moyao,fecha(08,julio,1972),trabaja(empleada,3000)),
[ persona(orquidea,jaimes,fecha(21,agosto,1989),trabaja(comerciante,2000)) ]
).
 % Asi definiremos quien es esposo: Y es esposo.
esposo(Y) :- familia(Y,_,_).
 % Asi definiremos quien es esposa: X es esposa.
esposa(X) :- familia(_,X,_).
 % Asi definiremos quien es hijo: 
hijo(Z) :- familia(_,_,Hijos), miembro(Z,Hijos).
miembro(X, [X|_]). % Asi utilizaremos esta operacion para enlistar a todos los Hijos.
miembro(X, [_|L]) :- miembro(X, L).
% Asi podremos saber si hay una persona en la base de datos.
existe(Persona) :- esposo(Persona); esposa(Persona); hijo(Persona).
% Con este por fecha de nacimiento.
fecha_nacimiento(persona(_,_,Fecha,_), Fecha).
% Con esta el salario de una persona.
salario(persona(_,_,_,trabaja(_,S)),S).
salario(persona(_,_,_,no_trabaja),0).
% Con este ultimo el ingreso total de la familia.
total([],0). 
total([Persona|Lista],Suma) :- salario(Persona,S), 
 total(Lista,Resto), Suma is S + Resto. 

Capitulo 3

Ejercicios.
1. Escriba una meta, usando concat, para eliminar los tres últimos elementos de una lista 
L produciendo otra lista L1. Recomendación: L es la concatenación de L1 y una lista de 
tres elementos. 
2. Escriba una secuencia de metas para eliminar los tres primeros elementos y los tres 
últimos elementos de una lista L produciendo la lista L2. 
3. Defina la relación: 
 ultimo( Elemento, Lista) 
de tal modo que Elemento sea el último elemento de la lista Lista. Escriba dos versiones: 
(a) usando la relación concat, y (b) sin usarla. 

Átomos

Se construyen de tres formas:
- Cadena de letras, dígitos y el símbolo de subrayado, pero siempre se comienza con una letra MINÚSCULA.
- Cadenas de caracteres especiales.
- Cadenas de caracteres encerrados en comillas simples ( ' ).

Números

Estos pueden ser:
- Reales.
- Enteros.

Variables

Cadenas de letras, dígitos y el símbolo de subrayado.
Comienzan siempre en MAYÚSCULAS o el símbolo de subrayado ( _ ).

Estructuras

Las estructuras son un tipo de dato muy interesante, las definimos como objetos que tienen varios componentes.
propiedades:
-funtor principal.
-componentes.

ejemplo:
departamento(sala,comedor,cocina,cochera,dormitorio)

funtor principal:
-departamento.

componentes:
-sala,comedor,cocina,cochera,dormitorio
Los componentes deben de ir separados por comas, los componentes son constantes, como ya lo vimos anteriormente, pueden también ser variables o estructuras.

Ejercicio 2.4

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? 

a) programa:

enorme(oso).
enorme(elefante).
chico(gato).
cafe(oso).
negro(gato).
gris(elefante).
oscuro(Z) :- negro(Z).
oscuro(Z) :- cafe(Z).


b)pregunta:?- enorme(X),oscuro(X).


c)Traza de ejecucion:1) Lista inicial de metas:  enorme(X),oscuro(X).2) Examina el programa de arriba hacia abajo buscando una clausula cuya cabeza empate con la primera meta: enorme(X) se encuentra en la clausula (1), se instancia X = oso.3) Se trata o busca satisfacer la segunda meta inicial: oscuro(oso), se encuentra la regla en la clausula 7.
Se busca satisfacer: oscuro(oso) :- negro(oso). (no se encuentra negro(oso)) BACKTRACKING.
4) Tras el backtracking se devuelve a la clausula 7 y se prueba con la clausula 8.
Se busca satisfacer: oscuro(oso) :- cafe(oso). (si se encuentra en el programa la clausula cafe(oso)).
Esta clausula no tiene cuerpo, asi que la lista de metas queda vacia. Esto indica una terminacion exitosa y la instanciacion corresponde a la variable queda como:
X = oso.

Ejercicios 2.3

Ejercicios

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).

Como contestara prolog las siguientes preguntas?

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

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

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

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

respuestas exactas

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)  ; parientes( X, Y) :- predecesor( Y, X) ; 
parientes( X, Y) :- predecesor( Z, X), predecesor( Z, Y)  ; parientes( X, 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 = 1, Palabra = dos.
traducir( Numero, Palabra) :- Numero = 1, Palabra = tres.

Ejercicio 2.1 y 2.2

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ó.


podemos ver que para construir una circunferencia almenos necesitamos el punto de origen y su radio.

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).
(c). triangulo(punto(-1,0),P2,P3) = triangulo(P1,punto(1,0),punto(0,Y)).
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.
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.

a) Podemos ver que hay empatamiento ya que:

A=1 B=2

b) En este caso no hay empatamiento, ya que los argumentos no concuerdan.

c) En este caso si hay empatamiento, ya que la opracion nos lleva al resultado:

4=4

d) por lo que vemos si empatan ya que tienen los mismos funtores y por ultimo:

D=2 E=2

Sintaxis y Significado de los Programas

Prolog reconoce el tipo de un objeto por su sintaxis.

Al igual que en Lógica de Primer Orden, los términos en Prolog se clasifican en tres categorías  constantes, variables y términos compuestos.

Constantes

Prolog distingue dos tipos de constantes:

Números. Este tipo de constantes se utilizan para representar tanto números  enteros como

números  reales y poder realizar con ellos operaciones aritméticas.

- La representación mas corriente de los números  enteros es la notación decimal habitual

(por ejemplo 0, 1, -320, 539, etc) aunque también se pueden representar en otras

bases no decimales.

- Los números  reales se pueden representar tanto en notación decimal (por ejemplo

1.0, -3.14) como en notación exponencial (por ejemplo 4.5E6, -0.12e+3, 12.0e-2). En ambos casos deberá haber siempre por lo menos un dígito a cada lado del punto.

Átomos. Los átomos (no confundir con las formulas atómicas de la LPO) se utilizan para

dar nombre a objetos especificos, es decir, representan individuos concretos. Existen tres

clases principales de atomos:

- cadenas formadas por letras, digitos y el simbolo de subrayado, que deben empezar necesariamente por una letra minuscula.

Cadenas validas: f, pepe1, libro33a, libro_blanco.

Cadenas no validas: 1libro, libro-blanco, _hola, Libro.

- cualquier cadena de caracteres encerrada entre comillas simples.
Ejemplos: 'Juan' 'Pepe_Hernandez' 'Carlos Hernández Lopez'.

Estos átomos son útiles cuando se necesita trabajar con constantes que empiecen por una letra mayúscula  o por un dígito.

- existe además otro tipo de átomos, compuestos por combinaciones especiales de signos, de uso menos común.

1.7

Resumen.
La programación en Prolog consiste en definir relaciones y preguntar acerca de las
relaciones.
Un programa consiste de cláusulas. Estas son de tres tipos: hechos, reglas y preguntas.
Una relación puede especificarse con hechos, estableciendo la lista de objetos que
satisfacen la relación o estableciendo las reglas acerca de la relación.
Un procedimiento es un conjunto de cláusulas acerca de una misma relación.
En Prolog, para establecer si un objeto satisface una pregunta puede ser un proceso
complicado que involucra inferencias lógicas, exploración entre alternativas posibles y
posibles procesos de backtracking (vuelta atrás). Todo esto lo realiza automáticamente
Prolog y es en principio oculto para los usuarios