INSTITUTO POLITÉCNICO NACIONAL
Centro de Investigación en Computación
Fundamentos de Inteligencia Artificial
06
Procesamiento de listas
y razonamiento declartivo...
Dr. Salvador Godoy Calderón
Comentarios
pendientes...
Comentarios...
En Prolog existen dos tipos de comentarios:
Comentarios de línea:
Comienzan con el símbolo % y terminan con el salto
de línea. Son el tipo más usado de comentarios en la
comunidad Prolog...
Comentarios de bloque:
Comienzan con /* y terminan con */ abarcando
cuantas líneas sea necesario. Muy comunes en otros
lenguajes...
Dr. Salvador Godoy Calderón 3
Estilo para comentar...
El estilo obligatorio para comentar programas durante
este curso es el siguiente:
1. Al inicio de cada archivo:
« Nombre completo (comenzando por el nombre
y no por algún apellido)...
« Descripción del programa (preferentemente, el
enunciado del problema)...
« Recomendación sobre la forma de ejecutar
algunos predicados importantes...
Dr. Salvador Godoy Calderón 4
Estilo para comentar...
El estilo obligatorio para comentar programas durante
este curso es el siguiente:
2. Al inicio de cada predicado o grupo de
predicados relacionados:
« Descripción de los parámetros, su
interpretación y restricciones si las hay...
« Interpretación de los parámetros respuesta...
Dr. Salvador Godoy Calderón 5
Ejemplo...
%===============================================================
% Salvador Godoy Calderón
%
% TAREA #1. Árbol genealógico
% Construir un programa Prolog para representar las relaciones de
% parentesco en la familia Simpson.
% Programar reglas para las relaciones de: medios hermanos, tíos,
% primos, cuñados y ancestros en general.
%================================================================
Dr. Salvador Godoy Calderón 6
Ejemplo...
%===============================================================
% cuñado/2.
% cuñado(+Personaje, - Cuñado)
% Recibe como parámetro el nombre de algún personaje conocido
% y devuelve el nombre de todos sus cuñados...
%
% El cuñado de alguien es el hermano de su esposa/esposo...
%================================================================
cuñado(Personaje, Cuñado) :- ...
Dr. Salvador Godoy Calderón 7
Comentarios...
https://www.swi-prolog.org/pldoc/man?section=preddesc
Dr. Salvador Godoy Calderón 8
Estilo de codificación...
Además de los comentarios pertinentes, es necesario
recordar la guía para codificación:
« Todos los nombres de predicados (functores),
constantes y variables, en español y con correcta
ortografía...
« Solamente las variables locales a un predicado
pueden estar abreviadas con una sola letra, los
parámetros de los predicados deben ser
descriptivos...
« Todos los comentarios también con correcta
ortografía...
Dr. Salvador Godoy Calderón 9
Sobre la tarea...
« Ancestro de un personaje...
ancestro(X, Ancestro) :- desciende(Ancestro, X).
ancestro(X, Ancestro) :- desciende(Z, X),
ancestro(Z, Ancestro).
Un predicado recursivo con dos cláusulas...
(recordar que esas cláusulas están
implícitamente conectadas con disyunción)
Dr. Salvador Godoy Calderón 10
Listas...
Dr. Salvador Godoy Calderón
Listas...
Las listas son posiblemente las estructuras más usadas en
programas de procesamiento no-numérico, en cualquier
lenguaje de programación...
Pero definitivamente son la estructura más usada en
inteligencia artificial simbólica (junto con los árboles)...
Eso se debe, por una parte, a su fácil asociación con
conjuntos, bolsas, pilas y colas. Pero, por otra parte, y
posiblemente más importante, a su naturaleza recursiva...
Dr. Salvador Godoy Calderón 12
Listas...
En Prolog las listas se denotan entre corchetes y
separando los elemantos internos con comas...
[ a, b, c, d, e, f ]
Gracias a la naturaleza sin tipos de datos en Prolog, una
lista puede contener, al mismo tiempo, cualquier tipo de
elementos (todos son términos)...
Dr. Salvador Godoy Calderón 13
Listas...
Para aprovechar la naturaleza recursiva de las listas,
existe en Prolog una forma abreviada de representarlas:
[ inicio | resto ]
Donde:
inicio (head) es uno o más términos, separados por
comas...
resto (tail) debe ser SIEMPRE una lista…
Esta expresión puede ser unificada con otras expresiones,
siguiendo las mismas reglas ya conocidas y el predicado
de unificación (=)...
Dr. Salvador Godoy Calderón 14
Algunas unificaciones...
Dr. Salvador Godoy Calderón 15
Algunas unificaciones...
Dr. Salvador Godoy Calderón 16
Representación...
Para la representación interna de las listas, Prolog usa
unas estructuras básicas llamadas celdas de construcción
(cons cells), estructras con sólo dos campos y cada uno de
ellos contiene un apuntador…
En particular, una celda puede apuntar a otra, con lo que
se pueden construir cadenas ligadas de celdas...
Dr. Salvador Godoy Calderón 17
Ejemplo...
La lista:
Se representa internamente como:
47.12
123 X
a b c
Siendo NIL un símbolo interno que indica el final de la lista...
Dr. Salvador Godoy Calderón 18
Listas propias y no-propias...
Las listas cuyo apuntador final es NIL se denominan listas
propias, pero también es posible definir listas no-propias, o
no terminadas en NIL...
b
d
a
a b c
Dr. Salvador Godoy Calderón 19
Formas No-canónicas
Formas No-canónicas...
Se dice que se usan variables en forma canónica, en un
predicado Prolog, cuando éstas toman el lugar de la
respuesta que entrega la función asociada…
función asociada: z = f (x, y)
forma canónica: f (x, y, Z)
(como predicado)
f (X, y, z) f (X, Y, z)
formas no-canónicas: f (X, Y, Z)
f (x, Y, z) f (x, Y, Z)
Estas formas, y la manera de encontrar las soluciones a
consultas, son lo que da su poder declarativo a Prolog…
Dr. Salvador Godoy Calderón 21
Algunas operaciones...
Es decir, el predicado member/2 se puede definir con
una regla recursiva de la siguiente forma:
member ( X, [ X |Resto] ).
member ( X, [Algo|Resto] ) :- member ( X, Resto) .
Dr. Salvador Godoy Calderón 22
Simplificación...
member ( X, [ X |Resto] ).
member ( X, [Algo|Resto] ) :- member ( X, Resto) .
En Prolog, el símbolo de guión bajo funciona como
variable anónima. Esta variable nunca se reporta en las
respuestas a consultas...
Usar guión bajo en una expresión indica que no es
relevante el valor asociado a esa variable...
member ( X, [ X | _ ] ).
member ( X, [ _ |Resto] ) :- member ( X, Resto ) .
Dr. Salvador Godoy Calderón 23
Pensamiento diferente...
El predicado member, en el contexto de un lenguaje
declarativo como Prolog, permite algunos usos no
convencionales en lenguajes imperativos…
Dr. Salvador Godoy Calderón 24
Pensamiento diferente...
Ahora, probemos una consulta compuesta...
Como no está especificada la longitud de la lista L, Prolog
trata de calcular todas las permutaciones de los elementos a,
b y c, en listas de tamaño infinito…
Dr. Salvador Godoy Calderón 25
Idea...
Si se especifica el tamaño de la lista L, entonces el
resultado será que Prolog busque todas las
permutaciones de los elementos indicados en la
consulta, pero sólo para listas de ese tamaño...
Dr. Salvador Godoy Calderón 26
Idea...
La misma condición se puede expresar usando unificación
con variable anónima...
Dr. Salvador Godoy Calderón 27
Concatenación...
El predicado preconstruído para concatenar listas es
append/3…
Es decir, que ese mismo comportamiento se puede
definir, también recursivamente, de la siguiente forma:
append ( [ ], L, L ).
append ( [ X | L1 ], L2, [ X | L3] ] ) :- append ( L1, L2, L3) .
Dr. Salvador Godoy Calderón 28
Concatenación...
Al igual que el caso anterior,
append se puede usar de
formas no-canónicas…
Dr. Salvador Godoy Calderón 29
Ideas...
Usando variables, podemos aprovechar la
definición recursiva de append para encontrar
el contexto de un elemento en una lista…
Dr. Salvador Godoy Calderón 30
Otra forma...
De hecho, podemos usar append para definir el predicado
member…
member (Elem, Lista) :- append (L1, [Elem | L2], Lista).
O alternativamente, usando variable anónima...
member (Elem, Lista) :- append ( _, [ Elem| _ ], Lista).
Dr. Salvador Godoy Calderón 31
Predicados...
En https://www.swi-prolog.org/pldoc/man?section=lists
se encuentra la lista de todos los predicados y operadores
predefinidos en Prolog para manejo de listas…
member (<elem>, <lista>).
append (<lista1>, <lista2>, <lista-result>).
length (<lista, <número>).
select (<elem>, <lista1>, <lista2>).
nth0 (<índice>, <lista>, <elemento>, <resto>).
…
Dr. Salvador Godoy Calderón 32
Muy útil...
Particularmente interesantes son los predicados nth0/3 y
nth1/3 para relacionar cada elemento en una lista con su
posición en la misma...
Dr. Salvador Godoy Calderón 33
Otra versión...
También existe la versión de aridad 4 de los predicados
nth0 y nth1 que nos dan información sobre el resto...
Dr. Salvador Godoy Calderón 34
Dos ejercicios
sencillos...
Algunos ejercicios...
Definir un predicado borra_inicial que elimine el primer
elemento de una lista...
Analizar los casos de cálculo y las condiciones para que el
predicado sea verdadero...
borra_inicial ( [ ], [ ] ).
borra_inicial( [X|Resto], Resto).
Dr. Salvador Godoy Calderón 36
Algunos ejercicios...
Definir un predicado longitud que calcule la longitud de
una lista como el número de elmentos que contiene...
lenght / 2
longitud ([ ], 0).
longitud ([ _ |Resto], N) :- longitud(Resto, M) , N is M+1.
Dr. Salvador Godoy Calderón 37
ESTUDIO...
https://www.tutorialspoint.com/prolog/prolog_lists.htm
https://www.geeksforgeeks.org/lists-in-prolog/
https://en.wikibooks.org/wiki/Prolog/Lists
Dr. Salvador Godoy Calderón 38
INSTITUTO POLITÉCNICO NACIONAL
Centro de Investigación en Computación
¡ Gracias !
Dr. Salvador Godoy Calderón
