Prolog

Tipos de Datos en Prolog

Primer Cuatrimestre de 2009
– Material Adicional –

• En Prolog no existe el concepto de tipo de
dato.
• Las variables denotan un cierto objeto, pero
ese objetopuede ser cualquiera de los
objetos considerados.
• La carencia de tipos de datos implica una
mayor responsabilidad para el programador.

Estructuras de Datos
en Prolog

Estructuras de DatosRecursivas

Estructuras de Datos
en Prolog
Lógica para Ciencias de la Computación

• No disponer de tipos de datos no implica
dejar de lado a las estructuras de datos.
• Por otro lado, larecursión es la principal
estructura de control en Prolog.
• Las estructuras de datos recursivas se
integran naturalmente a los programas
escritos en Prolog.

• Una estructura de datos se puede decirrecursiva si cada una de sus distintas
instancias satisfacen:
– Ser una instancia básica, la cual puede ser
definida de forma directa.
– Ser una instancia general, la cual se define
como unaelaboración de otra u otras
instancias más simples.

Codificación Recursiva para los
Números Naturales
• La codificación estándar parece no
satisfacer las condiciones anteriores:
– 0, 1, 2, 3, 4, …• La notación unaria sin duda es recursiva:
– 1, 11, 111, 1111, 11111, …

• La notación sn(0) también es recursiva:
– 0, s(0), s(s(0)), s(s(s(0))), s(s(s(s(0)))), …

Ejemplo
Dado un númeronatural obtener el siguiente:
next(X, s(X)).
?- next(0, 0).
no
?- next(0, Rsta).
Rsta = s(0)

1

Ejemplo
Verificar si el argumento suministrado es un número
natural en codificación sn(0):nn(0).
nn(s(X)) :- nn(X).
?- nn(s(s(0))).
yes
?- nn(Rsta).
…

Planteo Recursivo del Problema
• Consta de dos partes o casos:
– Caso Base: se define en forma directa la
solución a unainstancia base o trivial del
problema.
– Caso Recursivo: se define la solución a una
instancia gral. del problema en términos de la
solución a una instancia menor (ie, más
cercana a la instancia...