PDF de programación - Técnicas básicas de programación Prolog

Técnicas básicas de programación Prolog

Programación Declarativa

Pablo López

25 de octubre de 2007

1. Programación recursiva

La recursión es una técnica fundamental en Prolog, tanto para repre-
sentar los datos como para procesarlos. Esto se debe a que Prolog, como
todos los lenguajes declarativos puros, carece de iteración.

Aunque la programación recursiva es una técnica que nos resulta fami-
liar, la recursión en Prolog exhibe ciertas particularidades que se apartan
lo habitual. Por ejemplo, el caso base y el caso recursivo no tienen por qué
ser excluyentes, lo que permite generar respuestas múltiples.

Esta sección ilustra el empleo de la recursión en Prolog a través un
ejemplo simple pero eficaz: la axiomatización de la aritmética de Peano.
Los objetos a representar serán los números naturales {0, 1, 2, 3...} y las
relaciones serán las operaciones aritméticas básicas: suma, resta, producto...
Además de la recursión (de datos y código), introduciremos los con-
ceptos de modo de un argumento, y uso, comportamiento y significado de un
predicado.

Ejemplo: Axiomatización de la aritmética de Peano

El dominio de los naturales. El conjunto de los naturales N se define
inductivamente como sigue:

1. 0 ∈ N
2. si x ∈ N, entonces σ(x) ∈ N

[Caso Base]
[Caso Recursivo]
donde σ es la función sucesor σ : N → N; es decir, σ(x) representa al
sucesor de x. Las anteriores definiciones permiten construir el conjunto
N partiendo del caso base (1), obteniendo nuevos elementos aplicando el
caso recursivo (2):

{z

recursivo

}

}.

N = { 0|{z}

base

|

, σ(0), σ(σ(0)), σ(σ(σ(0))), ...

Notas de clase

Octubre 2007

T2.2

Técnicas básicas de programación Prolog

Los naturales así definidos son recursivos: un natural mayor que 0 será
de la forma σ(x); es decir, «contiene» otro natural x más pequeño que él.
Por lo tanto, debemos encontrar una estructura de datos recursiva para
representar los naturales.

En la mayoría de los lenguajes imperativos la recursión de datos debe
ser simulada mediante punteros o mecanismos similares. Por el contrario,
la recursión de datos puede emplearse en Prolog de forma directa. En
concreto, para representar los naturales en Prolog basta emplear térmi-
nos Prolog recursivos que capturen la definición inductiva de N. El caso
base de N nos asegura la existencia de un objeto concreto y único: el 0. Pa-
ra representar este objeto en Prolog utilizaremos una constante c. El caso
recursivo introduce una función σ : N → N. La expresión σ(x) es un ob-
jeto compuesto que debe ser representado por una estructura de aridad 1.
Tomaremos una estructura de functor s/1. Los naturales se representarán
entonces por términos Prolog que se ajusten a la gramática GN:

N ::= c

| s(N)

[Caso Base]
[Caso Recursivo]

donde el functor s/1 es siempre aplicado a un término que representa un
natural bien formado. Los siguientes son ejemplos de términos Prolog
que representan naturales bien formados; es decir, que se ajustan a la gra-
mática GN:
c
s(c)
s(s((c)))
s(s(s(c)))

Un natural n ∈ N se representa aplicando n veces el functor s/1 a la
constante c, lo que denotaremos de forma abreviada por sn(c).

El programador no puede comunicar de ninguna forma a Prolog que
tiene la intención de representar los naturales por términos que se ajus-
ten a la gramática GN. Esto se debe a que Prolog carece de definiciones
de tipos. Los siguientes son términos Prolog que no son naturales bien
formados, pues el functor s/1 no siempre se aplica a un natural bien for-
mado:

s(s(f(c)))
s(s(a))

Aunque no es posible restringir el functor s/1 de forma que siempre se
aplique correctamente, sí podemos definir una relación es_natural/1 que
se satisfaga cuando su único argumento sea un natural bien formado.

El predicado es_natural/1 podría definirse extensionalmente (por enu-

meración de todos los casos):

Notas de clase

Octubre 2007

Técnicas básicas de programación Prolog

T2.3

es_natural(c).
es_natural(s(c)).
es_natural(s(s(c))).
...

El problema de esta definición es que deberíamos introducir un núme-
ro infinito numerable de hechos para completarla. Parece más apropiado
definir es_natural/1 intensionalmente, determinando las condiciones que
debe cumplir un término Prolog para ser un natural bien formado. Basta
razonar siguiendo la definición inductiva de N:

1. 0 ∈ N

[Caso Base]
El 0 es un elemento de N. Esto es cierto incondicionalmente, por lo
que se traduce a Prolog el por hecho:

es_natural(c).

donde reemplazamos 0 por su representación Prolog, c.

2. si x ∈ N entonces σ(x) ∈ N

[Caso Recursivo]
Este enunciado incluye una condición y una conclusión, por lo que
se traduce a Prolog por la regla:

es_natural(s(X)):- es_natural(X).

donde reemplazamos σ(x) por s(X).

de donde obtenemos la definición:

es_natural(s).
es_natural(s(X)) :- es_natural(X).

El predicado es_natural/1 así definido es una definición de dominio
o tipo, pues define el conjunto de términos que representan un dominio
(tipo) dado. Para comprobar el funcionamiento de es_natural/1, basta
resolver el objetivo:

:- es_natural(s(s(s(c)))).

al que Prolog responderá afirmativamente. Por el contrario, Prolog res-
ponderá negativamente a los siguientes objetivos:

:- es_natural(s(s(s(0)))).
:- es_natural(s(f(s(0)))).

También es posible plantear un objetivo donde aparezca una variable:

:- es_natural(X).

Notas de clase

Octubre 2007

T2.4

Técnicas básicas de programación Prolog

Figura 1: Árbol de búsqueda del objetivo es_natural(X).

Intuitivamente, estamos preguntando a Prolog si existe algún X tal que
X es un natural bien formado. Obviamente, existen un número infinito
numerable de términos X que son naturales bien formados, y vemos que
Prolog los genera en orden creciente:

:- es_natural(X).
X= c;
X= s(c);
X= s(s(c));
...

La figura 1 muestra el árbol de búsqueda del objetivo es_natural(X). Pue-
de apreciarse que la rama más a la derecha es infinita, por lo que el ob-
jetivo nunca termina. Además, cada respuesta computada se obtiene de
forma progresiva, introduciendo variables (Xi) y sustituciones (Xi/s(Xi+1))
intermedias. Para derivar —o construir— el natural n, basta descender n
veces a la derecha (aplicando la regla recursiva) y descender finalmente a
la izquierda (aplicando el caso base). Este comportamiento se debe a que
al resolver los subobjetivos es_natural(Xi), el caso base y el caso recursivo
no son excluyentes. Obtenemos un comportamiento similar si planteamos
un objetivo con un argumento parcialmente instanciado:

:- es_natural(s(s(X))).
X= c;
X= s(c);
X= s(s(c));
...

Modo de un argumento. Los objetivos anteriores realizan funciones muy
distintas a pesar de invocar al mismo procedimiento. La razón es que el

Notas de clase

Octubre 2007

1 es_natural(c).2 es_natural(s(X)):- es_natural(X).1) es_natural(X)2. éxito{X/c}1 - {X/c}3) es_natural(X1)2 - {X/s(X1)}4. éxito{X/s(c)}1 - {X1/c}5) es_natural(X2)2 - {X1/s(X2)}6. éxito{X/s(s(c))}1 - {X2/c}7) es_natural(X3)...2 - {X2/s(X3)} Técnicas básicas de programación Prolog

T2.5

papel jugado por los argumentos pasados al procedimiento es diferente.
Un argumento o parámetro actual de un procedimiento puede estar en
dos modos:1

Modo + el argumento no tiene variables libres o las variables que contiene

no van a resultar instanciadas como resultado de la ejecución

Modo - el argumento tiene variables libres que resultan instanciadas al

ejecutar el procedimiento

El argumento del objetivo es_natural(s(s(s(c)))) no contiene variables,
por lo que está en modo +. Por el contrario, los argumentos de los objetivo
es_natural(X) y es_natural(s(s(Y))) contienen variables que resultan
instanciadas en el proceso de resolución, por lo que están en modo -.

Simplificando, podemos identificar el modo + con los parámetros de
entrada y el modo - con los parámetros de salida y entrada/salida. En los
lenguajes imperativos tradicionales, el que un parámetro sea de entrada
o salida depende exclusivamente de cómo se defina el parámetro formal
en la cabecera del procedimiento. Por el contrario, en Prolog, el que un
parámetro sea de entrada o salida depende del propio parámetro actual y
de cómo se defina el parámetro formal correspondiente en la cabecera del
predicado. Esto es consecuencia de emplear la unificación como mecanis-
mo para el paso de parámetros.

Uso, comportamiento y significado de un predicado. Como hemos visto
en el ejemplo anterior, un predicado puede comportarse de forma diferen-
te —e incluso no funcionar— según el modo en que se encuentren sus
parámetros actuales. Se llama uso de un predicado a la combinación de los
modos de los parámetros actuales. Por ejemplo, el predicado es_natural
tiene dos usos diferentes: es_natural(+) y es_natural(-), según su úni-
co argumento esté en modo + o -. Puesto que un parámetro puede estar en
dos modos diferentes, un predicado con n argumentos puede tener hasta
2n usos diferentes.

La forma en que actúa un predicado para un uso concreto se denomi-
na comportamiento. El comportamiento clasifica a los predicados según el
número de respuestas que generan en test o generador.

Un predicado se comporta como un test si la respuesta computada está
vacía; es decir, no se instancia ninguna variable. Esto quiere decir que la
única respuesta que se obtiene de un test es éxito o fracaso. Por ejemplo,
el objetivo es_natural(s(s(c))) se comporta como un test, pues su úni-
co argumento está en modo +. El test corresponde siempre al uso en que

1Estas definiciones de modo no se ajustan a las que aparecen en el estándar ISO de
Prolog y no son completamente precisas. Para simplificar, nos ceñiremos a ellas a lo largo
del curso.

Notas de clase

Octubre 2007

T2.6

Técnicas básicas de programación Prolog

todos los argumentos del predicado están en modo +, pues de lo contra-
rio algún argumento resultaría instanciado y la respuesta computada no
estaría vacía.

Un predicado se comporta como un generador si las respuestas compu-
tadas no están vacías. Para ello, al menos un argumento debe estar en
modo -. Según el número