PDF de programación - Programación Lógica

[white paper]
Programación lógica

Un recorrido por la programación lógica y uno de sus lenguajes más
representativos: Prolog, clásico de la inteligencia artificial, que se aplica
de múltiples formas en el desarrollo de software comercial.

L

a programación lógica, junto con la funcional, forma parte de lo que se co-
noce como programación declarativa. En los lenguajes tradicionales, la
programación consiste en indicar cómo resolver un problema mediante sen-
tencias; en la programación lógica, se trabaja de una forma descriptiva, establecien-
do relaciones entre entidades, indicando no cómo, sino qué hacer. La ecuación de Ro-
bert Kowalski (Universidad de Edimburgo) establece la idea esencial de la programa-
ción lógica: algoritmos = lógica + control. Es decir, un algoritmo se construye especi-
ficando conocimiento en un lenguaje formal (lógica de primer orden), y el problema
se resuelve mediante un mecanismo de inferencia (control) que actúa sobre aquél.
Prolog
El lenguaje Prolog, principal representante del paradigma, se basa en un subconjun-
to de la lógica de primer orden (restricción de la forma clausal de la lógica denomi-
nada cláusulas de Horn). Philippe Roussel y Alain Colmerauer (Universidad de Aix-
Marseille) lo crearon en 1972, y su base teórica se debe en gran parte a Kowalski.

Estructuras básicas
Prolog cuenta con dos tipos de estructuras: términos y sentencias. Los términos

pueden ser constantes, variables o functores:

> Las constantes, representadas por una cadena de caracteres, pueden ser núme-

ros o cualquier cadena que comience en minúscula.

> Las variables son cadenas que comienzan con una letra mayúscula.

Poste 1

Poste 2

Poste 3

[Figura 1] Problema y resolución de las torres de Hanoi.

58

> Los functores son identificadores que em-
piezan con minúscula, seguidos de una
lista de parámetros (términos) entre pa-
réntesis, separados por comas.

Las sentencias son reglas o cláusulas. Hay
hechos, reglas con cabeza y cola, y consultas.

> Un hecho establece una relación entre
objetos, y es la forma más sencilla de
sentencia. Por ejemplo:

humano (socrates).
ama (juan,maría)

Se establece que Sócrates es humano y

que Juan ama a María.

> Una regla permite definir nuevas relacio-
nes a partir de otras ya existentes. Si que-
remos establecer que todo humano es
mortal, en lógica estándar escribiríamos
V(x)(humano(x)=>mortal(x)), mientras que
en Prolog escribimos:

mortal(X):-humano(X).

> Esto se lee: X (variable) es mortal si X es
humano. El símbolo :- significa “si” o, si
lo leemos de derecha a izquierda, enton-
ces o implica. En esta regla, mortal(X) es
la cabeza, y humano(X) es el cuerpo.

> Para entender el concepto de consulta,

veamos un ejemplo. En lógica estándar:

> V(x)(humano(x)=>mortal(x))
> humano(socrates)
> entonces mortal (socrates)

> Partiendo de que los humanos son mor-
tales y de que Sócrates es humano,
deducimos que Sócrates es mortal. Para
realizar esa deducción en Prolog, hay
que preguntar si es mortal Sócrates, o
quién es mortal. Si del programa lógi-
co (conjunto de hechos y reglas) se
deduce que Sócrates es mortal, enton-
ces ésa será la respuesta que obtendre-
mos. Veamos el programa:

users.code

mortal(X):-humano(X).
humano(Sócrates).

Para preguntar interactivamente, los ambientes de Prolog tienen un
listener, un intérprete de línea de comando cuyo prompt es un signo
de pregunta. Se introduce una sentencia (eventualmente con varia-
bles), y Prolog intentará demostrarla (usando un algoritmo de inferen-
cia llamado SLD-Resolution, basado en la regla de resolución de
Robinson), buscando además constantes que puedan reemplazar las
variables de la pregunta. Las preguntas de nuestro ejemplo serían:

?- mortal(Sócrates).
Yes.

?- mortal(X)
X = socrates

Las segundas líneas son las respuestas de Prolog: primero, afirman-
do que sí, Sócrates es mortal; después, contestando Sócrates al pregun-
tar quién es mortal. Si agregamos más conocimiento a nuestro progra-
ma lógico (por ejemplo, que Platón es mortal), podemos pedir más res-
puestas. Si luego de obtener Sócrates escribimos un punto y coma (así
“pedimos más”), nos responderá Platón. Cuando Prolog no tenga más
respuestas, nos dirá que No; esa negativa no significa que lo que pre-
guntemos sea falso, sino que no lo conoce o no puede demostrarlo. Es
decir que si preguntamos, por ejemplo, si Arquímedes es mortal, la res-
puesta será que no, pero porque nuestro programa no cuenta con el co-
nocimiento suficiente. Esto se denomina negación por falla.

?- mortal(X)
X = socrates;
X = platon;
No

Este modo interactivo es muy útil para prueba y prototipación, pero
dependiendo de la implementación Prolog en particular, es posible
realizar invocaciones desde otros ambientes, o ejecutar un programa
Prolog que tenga un predicado main (que será el que se intentará pro-
bar). Para facilitar el desarrollo de aplicaciones, Prolog cuenta con un
conjunto de características que “ensucian” de alguna manera su pure-
za en lo que hace al paradigma, pero que lo vuelven utilizable. Habla-
mos, por ejemplo, de escritura por pantalla, pedido de datos al usua-
rio y otros elementos específicos de control del mecanismo de inferen-
cia (el predicado de corte es el más conocido).

Operadores

GERARDO ROSSEL
Investigador del CAETI.
[email protected]

Listas
Prolog manipula listas con una facilidad sintáctica que
simplifica la programación: una lista es un par ordenado,
donde un elemento es un término (la cabeza), y el otro pue-
de ser un término, una lista o la lista vacía (la cola). Las lis-
tas van entre corchetes, y la cabeza se separa de la cola con
el símbolo pipe; la lista vacía se indica con dos corchetes se-
parados por un espacio. Haciendo un abuso de notación,
también es posible enumerar todos los elementos de la lista
separándolos con comas. Por ejemplo, la lista 1, 2, socrates,
a, platon se escribe en Prolog de estas dos maneras:

[1|[2|[socrates|[a|[platon|[]]]]]]
[1, 2, socrates, a, platon]

Para comprender un poco mejor el poder de la programa-
ción declarativa, comparemos un algoritmo que determina si
un elemento se encuentra en una lista en un lenguaje decla-
rativo (por ejemplo, Pascal) y en Prolog. En Pascal:

function member(item:Integer; L:Array

of Integer):Boolean;

var

i:Integer;

begin

i:=0;
while((i <= length(L)) and (L[i] <> item)) do

begin

i := i+1;

end;

Result := item = L[i];

end;

Para saber si un elemento es parte de una lista, en Prolog

sólo declaramos que es su cabeza o es parte de su cola.

member(X,[X|Xs]).
member(X,[Y|Ys]) :- member(X,Ys).

El predicado member (parte del estándar de Prolog) dice que
un elemento (representado por la variable X) es miembro de
una lista si es la cabeza de ella (la cabeza de la lista [X|Xs]
es X), y también que un elemento es miembro de una lista si
es miembro de la cola (la cola de la lista [Y|Ys] es Ys, que es,

MATEMATICOS
Suma
+
Resta
-
*
Multiplicación
División (retorna siempre en punto flotante)
/
División entera (trunca)
//
Resto de división
mod
**
Potenciación

RELACIONALES
Mayor que
>
Menor que
<
>= Mayor o igual que
=< Menor o igual que
=:= Aritméticamente igual
=\= Aritméticamente diferente

59

[white paper - Programación lógica]

a su vez, una lista, un término o la lista vacía, según definimos anteriormente). En un
caso indicamos cómo determinar que un elemento es parte de la lista, mientras que en
el otro declaramos qué significa que un elemento sea parte de la lista. En esta última
situación, el motor de inferencia se encargará de responder cuando preguntemos.

Operadores aritméticos y relacionales
El predicado igual (=) compara dos términos, y es verdadero solamente cuando
ambos son idénticos o cuando alguna sustitución de variables los hace idénticos (es
más correcto decir “cuando unifican”). Las siguientes consultas nos dan un ejemplo:

?- 1 = 1.
yes
?- 1 = 2.
no
?- 2 = 1+1.
no
?- a=A.
A = a ;
No

Puede parecer extraño que la consulta 2 = 1+1 nos arroje un no como respuesta; en
realidad, la constante 2 no unifica con el predicado + con dos argumentos 1 y 1. Para
estas comparaciones, y para conseguir asignaciones, se usa el predicado is:

?- 2 is 1+1.
yes
?- X is 1+2.
X = 3 ;
no
?- 1 is X+2.
Error

En el primer caso, 1 + 1 es 2, el is responde yes. En el segundo, responde que X=3 es
la sustitución adecuada a X = 1+2; al pedir otra respuesta (con el punto y coma), no la
encuentra. El último ejemplo es un error: al usar is, la parte derecha debe estar instan-
ciada. El estándar establece que en otro caso es un error, aunque algunas distribucio-
nes de Prolog responden no. En la tabla [Operadores] vemos otras posibilidades.

Editor de reglas

si.. entonces

Componente lógico

Programa lógico específico

Traductor

Respuestas

Motor
Prolog

Base lógica

precio(x):=hora(y,3)...

Tablas en base de datos

[Figura 2] Reglas de negocios y Prolog.

60

Las torres de Hanoi
Este problema puede mostrar la potencia
del paradigma lógico. Se comienza ordenan-
do los discos de mayor a menor (de abajo
hacia arriba) sobre un eje, y se trata de llevar-
los a otro (del primero al último) para que
queden de la misma forma. Es posible despla-
zar los discos de a uno (siempre tomando el
de arriba), y nunca puede ubicarse un disco
sobre otro de menor diámetro. La [Figura 1]
muestra los estados inicial y final, luego de
realizar los movimientos. Existen tres postes,
y uno de ellos se usa como auxiliar (con sólo
dos sería imposible). Se trata, entonces, de
hacer un programa que pueda mover N dis-
cos desde el poste 1 hasta el poste 3, usando
el poste 2 como auxiliar. Para lograrlo, esta-
blecemos una regla cuya cabeza sea el predi-
cado Hanoi con un parámetro indicando la
cantidad de discos por mover; en el cuerpo de
la regla pondremos el predicado mover con
los parámetros: cantidad de discos (N), des