<div class="notebook">
<div class="nb-cell markdown" name="md1">
# PROLOG
</div>
<div class="nb-cell markdown" name="md37">
Ejemplos de libretas de Prolog [aquí](https://swish.swi-prolog.org/example/examples.swinb)
</div>
<div class="nb-cell markdown" name="md19">
### Ejemplo: suma y multiplicación de naturales
</div>
<div class="nb-cell program" name="p16">
suma(X, 0, X).
suma(X, s(Y), s(Z)) :- suma(X, Y, Z).
mult(0, U, 0).
mult(s(X), Y, Z) :- mult(X, Y, V), suma(V, Y, Z).
</div>
<div class="nb-cell markdown" name="md20">
Probemos con los ejemplos vistos en clase.
Comencemos con la suma.
</div>
<div class="nb-cell query" name="q22">
suma(s(0), s(0), X).
</div>
<div class="nb-cell query" name="q24">
suma(s(s(s(0))), s(s(0)), X).
</div>
<div class="nb-cell markdown" name="md21">
Ahora la multiplicación.
</div>
<div class="nb-cell query" name="q23">
mult(s(0), s(s(0)), X).
</div>
<div class="nb-cell query" name="q25">
mult(s(s(0)), s(s(0)), X).
</div>
<div class="nb-cell markdown" name="md22">
Veamos si puede descomponer en número en sus factores
</div>
<div class="nb-cell query" name="q26">
mult(X,Y,s(s(s(s(s(s(0))))))).
</div>
<div class="nb-cell markdown" name="md23">
---
Cambiemos el orden de las variables para ver si mejora la ejecución
</div>
<div class="nb-cell program" name="p17">
suma(X, 0, X).
suma(X, s(Y), s(Z)) :- suma(Y, X, Z).
mult(0, U, 0).
mult(s(X), Y, Z) :- mult(Y, X, V), suma(Y, V, Z).
</div>
<div class="nb-cell markdown" name="md24">
¿Seguirá funcionando la suma y la multiplicación?
</div>
<div class="nb-cell query" name="q28">
suma(s(s(s(0))), s(s(0)), X).
</div>
<div class="nb-cell query" name="q29">
mult(s(s(0)), s(s(0)), X).
</div>
<div class="nb-cell markdown" name="md25">
¿Qué tal se comporta descomponiendo números en sus factores?
</div>
<div class="nb-cell query" name="q30">
mult(X,Y,s(s(s(s(s(s(0))))))).
</div>
<div class="nb-cell query" name="q31">
mult(X,Y,s(s(s(s(s(s(s(s(s(s(s(s(0))))))))))))).
</div>
<div class="nb-cell markdown" name="md4">
### Otro ejemplo
Retomemos el ejemplo de principio de la [Nota 12](https://turing.iimas.unam.mx/~nohernan/teaching/notas-lc/nota12/lcNota12.pdf)
</div>
<div class="nb-cell program" name="p5">
ancestro(X,Y) :- progenitor(X,Y).
ancestro(X,Y) :- progenitor(X,Z),ancestro(Z,Y).
progenitor(bob, allen).
progenitor(catherine, allen).
progenitor(dave, bob).
progenitor(ellen, bob).
progenitor(fred, harry).
progenitor(harry, george).
progenitor(ida, george).
progenitor(joe, bob).
</div>
<div class="nb-cell markdown" name="md6">
La meta que hemos ocupado en los ejemplos en clase.
</div>
<div class="nb-cell query" name="q3">
ancestro(Y,bob),ancestro(bob,Z).
</div>
<div class="nb-cell markdown" name="md7">
Para imprimir todos los valores de ``Y`` y ``Z`` que hacen correcto al argumento usamos el operador ``fail``, el cual forza la falla y obliga a PROLOG a regresar al **punto de retorno** inmediato anterior
</div>
<div class="nb-cell query" name="q4">
ancestro(Y,bob),ancestro(bob,Z),format("Y: ~w, Z: ~w\n", [Y,Z]),fail.
</div>
<div class="nb-cell markdown" name="md5">
### Búsqueda a profundidad
PROLOG realiza una búsqueda a produndidad sobre el árbol SLD que define la meta, las cláusulas de programa y la regla de cómputo. Esto puede originar la **no** terminación de una ejecución. El programador **debe** ordenar cuidadosamente las cláusulas y las literas que las componen para evitar que la ejecución no termine.
</div>
<div class="nb-cell program" name="p1">
test :- p(X).
p(a).
p(X) :- p(f(X)).
</div>
<div class="nb-cell query" name="q1">
test.
</div>
<div class="nb-cell markdown" name="md2">
El programa termina en dos pasos de resolución.
</div>
<div class="nb-cell program" name="p4">
test :- p(X).
p(X) :- p(f(X)).
p(a).
</div>
<div class="nb-cell query" name="q8">
trace,test.
</div>
<div class="nb-cell markdown" name="md18">
### Verificación de presencias
Un ejemplo en el que PROLOG *no* realiza la **verificación de presencias** en la unificación:
</div>
<div class="nb-cell program" name="p15">
test(X) :- p(X,X).
p(Y,f(Y)) :- q(a).
q(a).
</div>
<div class="nb-cell query" name="q19">
test(X).
</div>
<div class="nb-cell query" name="q20">
Z=g(Z).
</div>
<div class="nb-cell query" name="q21">
unify_with_occurs_check(A,f(A)).
</div>
<div class="nb-cell markdown" name="md3">
### Aritmética
Aunque es posible formalizar la artimética en lógica de primer orden, hay dos problemas. Primero, sería incómodo ejecutar una meta sobre el número de empleados en una tienda departamental y recibir como respuesta ``s(s(s(s(s(a)))))`` en lugar de 5, como al principio de esta nota. El segundo problema es la ineficiencia de la resolución como método de computación numérica. PROLOG tiene la siguiente sintaxis para la aritmética estándar: ``Result is Expression``.
Supongamos que tenemos un programa para cobrar en una papelería. La siguiente cláusula obtiene el precio de lista y el descuento de una base de datos, y calcula el precio después de aplicarle el descuento.
</div>
<div class="nb-cell program" name="p3">
precio_de_venta(Articulo, Precio):-
precio_de_lista(Articulo, Lista),
porcentaje_descuento(Articulo, Descuento),
Precio is Lista - Lista * Descuento / 100.
precio_de_lista(cuaderno, 25).
precio_de_lista(lapiz, 5).
precio_de_lista(engrapadora, 110).
precio_de_lista(pluma, 10).
precio_de_lista(mouse, 300).
porcentaje_descuento(cuaderno, 8).
porcentaje_descuento(lapiz, 10).
porcentaje_descuento(engrapadora, 20).
porcentaje_descuento(pluma, 10).
porcentaje_descuento(mouse, 15).
</div>
<div class="nb-cell query" name="q5">
precio_de_venta(pluma,X).
</div>
<div class="nb-cell query" name="q2">
precio_de_venta(engrapadora,X).
</div>
<div class="nb-cell markdown" name="md8">
Los predicados aritméticos difieren de los predicados ordinarios porque son de ida únicamente. Si ``10 is X+Y``, ``X`` y ``Y`` podrían ser unificados con 0 y 10, y al tomar
puntos de retorno, podrían ser unificados con 1 y 9, y así sucesivamente. Sin embargo, esto es **ilegal**. En ``Result is Expression``, ``Expression`` debe ser evaluada a un valor numérico, entonces dicho valor es unificado con ``Result``. Los predicados aritméticos no son enunciados de asignación. El siguiente programa *no* es correcto:
</div>
<div class="nb-cell program" name="p20">
10 is X + Y.
</div>
<div class="nb-cell query" name="q32">
10 is 9+1.
</div>
<div class="nb-cell program" name="p19">
</div>
<div class="nb-cell program" name="p2">
precio_de_venta_iva(Articulo, Precio):-
precio_de_lista(Articulo, Lista),
porcentaje_descuento(Articulo, Descuento),
Precio is Lista - Lista * Descuento / 100,
porcentaje_iva(Articulo, Impuesto),
format('El valor de \'Precio\' se unificó con ~2f,\n ya no puede volverse a unificar.\n', [Precio]),
Precio is Precio * (1 + Impuesto / 100).
precio_de_lista(cuaderno, 25).
precio_de_lista(lapiz, 5).
precio_de_lista(engrapadora, 110).
precio_de_lista(pluma, 10).
precio_de_lista(mouse, 300).
porcentaje_descuento(cuaderno, 8).
porcentaje_descuento(lapiz, 10).
porcentaje_descuento(engrapadora, 20).
porcentaje_descuento(pluma, 10).
porcentaje_descuento(mouse, 15).
porcentaje_iva(cuaderno, 15).
porcentaje_iva(lapiz, 15).
porcentaje_iva(engrapadora, 15).
porcentaje_iva(pluma,15).
porcentaje_iva(mouse,15).
</div>
<div class="nb-cell query" name="q7">
precio_de_venta_iva(pluma,X).
</div>
<div class="nb-cell markdown" name="md14">
Una vez que se unifica ``Precio`` con 9 por la operación ``Precio is Lista - Lista * Descuento / 100`` ya no puede cambiar su valor. Tenemos que usar una variable distinta, digamos ``Precio1``.
</div>
<div class="nb-cell program" name="p11">
precio_de_venta_iva(Articulo, Precio):-
precio_de_lista(Articulo, Lista),
porcentaje_descuento(Articulo, Descuento),
Precio1 is Lista - Lista * Descuento / 100,
porcentaje_iva(Articulo, Impuesto),
format('El valor de \'Precio1\' se unificó con ~2f,\nlo usamos para calcular el valor de \'Precio\'.\n', [Precio1]),
Precio is Precio1 * (1 + Impuesto / 100).
precio_de_lista(cuaderno, 25).
precio_de_lista(lapiz, 5).
precio_de_lista(engrapadora, 110).
precio_de_lista(pluma, 10).
precio_de_lista(mouse, 300).
porcentaje_descuento(cuaderno, 8).
porcentaje_descuento(lapiz, 10).
porcentaje_descuento(engrapadora, 20).
porcentaje_descuento(pluma, 10).
porcentaje_descuento(mouse, 15).
porcentaje_iva(_,15).
</div>
<div class="nb-cell query" name="q14">
precio_de_venta_iva(pluma,X).
</div>
<div class="nb-cell query" name="q6">
precio_de_venta_iva(engrapadora,X).
</div>
<div class="nb-cell markdown" name="md9">
### El operador de corte (cut)
Considere el siguiente programa para el factorial de un número ``N``, a su vez es parte de otro predicado que verifica (``check``) si el factorial es par. Verifiquemos la ejecución del factorial con ``check(0)``.
</div>
<div class="nb-cell program" name="p6">
factorial(0, 1).
factorial(N, F):-
N1 is N-1,
factorial(N1, F1),
F is N*F1.
check(N) :- factorial(N, F), is_even(F).
is_even(X):-
M is mod(X,2),
M == 0.
</div>
<div class="nb-cell query" name="q9">
trace, check(0).
</div>
<div class="nb-cell markdown" name="md10">
Se realizará un número infinito de llamadas a la segunda cláusula de ``factorial``, es *stack* se acabará.
Una llamada a ``factorial`` con argumento 0 tiene una única solución. Si volvemos a puntos de retorno, la cláusula meta fallará. Esto lo evitamos con el operador de *corte*, denotado por ``!``, al final de la primer cláusula. El corte impide volver a puntos de retorno, es decir, se poda el árbol SLD.
</div>
<div class="nb-cell program" name="p7">
factorial(0, 1):-!.
factorial(N, F):-
N1 is N-1,
factorial(N1, F1),
F is N*F1.
check(N) :- factorial(N, F), is_even(F).
is_even(X):-
M is mod(X,2),
M == 0.
</div>
<div class="nb-cell query" name="q10">
check(0).
</div>
<div class="nb-cell markdown" name="md11">
En el caso del ``factorial`` hay una mejor opción, a saber, agregar al predicado una condición que prevenga el comportamiento no deseado (``N > 0``).
</div>
<div class="nb-cell program" name="p10">
factorial(0, 1).
factorial(N, F):-
N > 0,
N1 is N-1,
factorial(N1, F1),
F is N*F1.
check(N) :- factorial(N, F), is_even(F).
is_even(X):-
M is mod(X,2),
M == 0.
</div>
<div class="nb-cell query" name="q13">
check(0).
</div>
<div class="nb-cell markdown" name="md12">
### Definiciones recursivas
PROLOG tiene integrado el reconocimiento del patrón ``[H|T]`` para listas. Con el cual podemos definir un predicado que determine si un elemento es miembro de una lista.
</div>
<div class="nb-cell program" name="p8">
is_member(X,[X|_]). % Comentario en PROLOG. Este es el caso base donde el elemento
% a buscar es la cabeza de la lista
is_member(X,[_|T]):-
is_member(X,T),
write(T),nl. %¿Qué pasa si ponemos esta instrucción antes del 'is_member(X,T)'?
</div>
<div class="nb-cell query" name="q11">
is_member(a,[1,a,5,a]).
</div>
<div class="nb-cell markdown" name="md28">
Se imprime lo anterior porque el [árbol SLD](https://turing.iimas.unam.mx/~nohernan/teaching/notas-lc/nota12/tree1.svg) que genera la meta es:
</div>
<div class="nb-cell html" name="htm1">
<img src="https://turing.iimas.unam.mx/~nohernan/teaching/notas-lc/nota12/tree1.svg" alt="Alt text" width="450" height="550">
</div>
<div class="nb-cell markdown" name="md27">
¿Qué pasa si ponemos ``write(T),nl`` antes del ``is_member(X,T)``?
</div>
<div class="nb-cell program" name="p18">
is_member(X,[X|_]). % Comentario en PROLOG. Este es el caso base donde el elemento
% a buscar es la cabeza de la lista
is_member(X,[_|T]):-
write(T),nl,
is_member(X,T).
</div>
<div class="nb-cell query" name="q27">
is_member(a,[1,a,5,a]).
</div>
<div class="nb-cell markdown" name="md29">
Lo anterior se explica observando el [nuevo árbol SLD](https://turing.iimas.unam.mx/~nohernan/teaching/notas-lc/nota12/tree2.svg) que genera la meta:
</div>
<div class="nb-cell html" name="htm2">
<img src="https://turing.iimas.unam.mx/~nohernan/teaching/notas-lc/nota12/tree2.svg" alt="Alt text" width="400" height="700">
</div>
<div class="nb-cell markdown" name="md13">
Vemos en el árbol SLD que PROLOG, además de tener una rama de éxito con ``is_member(a,[a,5,a])``, analiza también la rama que se desprende de la llamada recursvia: ``is_member(a,[a,5,a]):- write([a,5,a]), nl, is_member(a,[5,a]).`` Podemos indicarle que ese caso no es necesario, pues ya encontró una instancia del elemento buscado.
</div>
<div class="nb-cell program" name="p9">
is_member(X,[X|_]):-!. % Comentario en PROLOG. Este es el caso base donde el elemento
% a buscar es la cabeza de la lista
is_member(X,[_|T]):-
write(T),nl,
is_member(X,T).
</div>
<div class="nb-cell query" name="q12">
is_member(a,[1,a,5,a]).
</div>
<div class="nb-cell markdown" name="md15">
---
Definimos un filtro para quedarnos con los elementos pares de una lista del siguiente modo.
</div>
<div class="nb-cell program" name="p12">
take_even([],[]).
take_even([H|T],[H|T1]):-
0 =:= mod(H,2),
take_even(T,T1),!. % Operador de corte
take_even([_|T],T1):-
take_even(T,T1).
</div>
<div class="nb-cell query" name="q15">
take_even([0,1098],X).
</div>
<div class="nb-cell markdown" name="md16">
---
También definimos una función que quite repeticiones. La idea es aplicar primero la llamada recursiva para que apartir del caso base se añadan los elementos de la lista original, cuidando que el elemento a añadir no esté ya en la lista a regresar.
</div>
<div class="nb-cell program" name="p13">
set([],[]).
set([H|T1],[H|T]):-
set(T1,T),
not_member(H,T),!.
set([_|T1],T):-
set(T1,T).
not_member(_,[]).
not_member(X,[Y|T]):-
X \== Y,
not_member(X,T).
</div>
<div class="nb-cell query" name="q16">
set([a,c,c],X).
</div>
<div class="nb-cell query" name="q17">
set([10,5,7,10,6,4],X).
</div>
<div class="nb-cell markdown" name="md30">
En lugar de usar le predicado ``not_member``, podemos usar el predicado predefinido ``member``
</div>
<div class="nb-cell program" name="p23">
set([],[]).
set([H|T1],T):-
set(T1,T),
member(H,T),!.
set([H|T1],[H|T]):-
set(T1,T).
</div>
<div class="nb-cell query" name="q36">
set([a,c,c],X).
</div>
<div class="nb-cell query" name="q37">
set([10,5,7,10,6,4],X).
</div>
<div class="nb-cell markdown" name="md32">
---
### El poder de la programación declarativa
**Ejemplo:** El siguiente programa permuta una lista
</div>
<div class="nb-cell program" name="p22">
permute([],[]).
permute([X|Y],Z) :- permute(Y,W),insert(X,W,Z).
insert(A,B,[A|B]). %Inserta al inicio
insert(A,[B|C],[B|D]) :- insert(A,C,D). %Inserta en otra posición
</div>
<div class="nb-cell query" name="q38">
insert(a,[w,x,y,z],I).
</div>
<div class="nb-cell query" name="q39">
permute([llueve,en,la,cdmx],P).
</div>
<div class="nb-cell markdown" name="md33">
**Ejemplo:** El siguiente programa ordena una lista - pero de forma muy ineficiente
</div>
<div class="nb-cell program" name="p24">
permute([],[]).
permute([X|Y],Z) :- permute(Y,W),insert(X,W,Z).
insert(A,B,[A|B]). %Inserta al inicio
insert(A,[B|C],[B|D]) :- insert(A,C,D). %Inserta en otra posición
sort_noe(L1,L2) :- permute(L1,L2),ord(L2).
ord([]).
ord([_]).
ord([X|[Y|Z]]) :- X=<Y, ord([Y|Z]).
</div>
<div class="nb-cell query" name="q40">
sort_noe([4,-10,8,-16,29,-78,18],L2).
</div>
<div class="nb-cell markdown" name="md34">
Escribe ``Quicksort`` en Prolog
</div>
<div class="nb-cell markdown" name="md26">
### Acertijos en Prolog
Vamos a resolver un acertijo de los que encontramos [aquí](https://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/).
Repetir los elementos de una lista un número dado de veces
Ejemplo:
```
?- repetir([a,b,c],3,X).
X = [a,a,a,b,b,b,c,c,c]
```
¿Cuáles son los resultados de la meta?
``?- repetir(X,3,Y).``
</div>
<div class="nb-cell program" name="p21">
repetir(L,N,R):-
repetir_aux(L,N,N,R).
repetir_aux([],_,_,[]).
repetir_aux([_|T],0,N,T1):-
repetir_aux(T,N,N,T1).
repetir_aux([H|T],C,N,[H|T1]):-
C > 0,
CNVO is C - 1,
repetir_aux([H|T],CNVO,N,T1).
</div>
<div class="nb-cell query" name="q33">
repetir([a,b,c],3,X).
</div>
<div class="nb-cell query" name="q34">
repetir(X,3,Y).
</div>
<div class="nb-cell markdown" name="md17">
### ¿A qué corresponden los predicados sin argumentos?
A variables proposicionales.
</div>
<div class="nb-cell program" name="p14">
p :- q.
r :- s.
q :- s.
s.
</div>
<div class="nb-cell query" name="q18">
p.
</div>
<div class="nb-cell markdown" name="md31">
¿Es posible tener dos literales idénticas en Prolog?
</div>
<div class="nb-cell query" name="q35">
trace,q,s.
</div>
<div class="nb-cell markdown" name="md35">
---
**Ejercicio:** Considera el siguiente programa en Prolog
</div>
<div class="nb-cell program" name="p25">
happy :- birthday,graduation.
happy :- birthday.
happy.
birthday :- !,fail.
birthday :- birthday.
graduation :- fail.
</div>
<div class="nb-cell markdown" name="md36">
- Construya el árbol SLD para la meta ``?- happy.``
- Reacomode el orden de las cláusulas tal que la búsqueda DFS encuentre una solución para la meta ``?- happy.``
- Inserte un operador de corte en el programa de arriba de modo que el nuevo árbol de búsqueda se vuelve finito, pero tan grande como sea posible.
- Describa los efectos de insertar el operador de corte en cualquiera de las tres posibles posiciones en la primera cláusula.
</div>
<div class="nb-cell query" name="q41">
trace,happy.
</div>
<div class="nb-cell program" name="p26">
happy :- birthday,graduation.
happy :- birthday.
happy.
birthday :- fail,!.
birthday :- birthday.
graduation :- fail.
</div>
<div class="nb-cell query" name="q42">
trace,happy.
</div>
<div class="nb-cell markdown" name="md38">
#### Para más ejemplos de Prolog consultar esta [libreta](https://swish.swi-prolog.org/example/examples.swinb)
</div>
</div>