De la eficiencia en cómputo

A mí me gusta Prolog, el lenguaje de programación, que a decir de la propaganda que Borland hacía de su compiladort (turbo Prolog), era "el lenguaje natural de la inteligencia artificial". Bonita frase publicitaria, nada más.

Y lo que me gusta de Prolog es su paradigma, que es totalmente diferente al que tienen los lenguajes de programación de cuarta generación como Pascal y C. En prolog actuamos en otra forma: definimos el problema y el lenguaje se encarga de darnos la solución. Suena a magia, pero no lo es.

Prolog es un lenguaje de programación declarativo y por ende, lo que tenemos que hacer es precisamente declarar las condiciones iniciales y de frontera. Por ejemplo, puedo decir:

ama(juan, ana).

Lo cual quiere decir, por ejemplo, que "juan ama a ana". Ojo, aquí es importante el orden de los términos. En prolog no es esto equivalente a lo que sigue:

ama(ana, juan).

Lo cual querría decir que "ana ama a juan", lo cual evidentemente no es equivalente.

Pero lo interesante aquí es el que declaramos, casi en el idioma que hablamos normalmente, un hecho que dentro de Prolog tiene sentido. No hablamos pues de hacer cálculos sofisticados por ejemplo, sino de declarar estas relaciones, que en los lenguajes de cuarta generación se dificulta hacerlo.

Pero pensando en esto y en los problemas que Prolog puede resolver, vía el mecanismo de la recursividad, hallé que en realidad habría que preguntarse si Prolog es un lenguaje víable para aplicaciones reales y no para meramente problemas académicos como los que ya he tratado aquí (crear crucigramas, pasear por un laberinto, resovlver sudokus, etc.). Y la realidad es que pienso que Prolog bien puede ser una herramienta víable, pero solamente para unos pocos casos en donde las simbologías son muy importantes.

Por ejemplo, pienso en un diccionario que tengo que consultar. Si mi diccionario cuenta con digamos medio  millón de palabras, y necesito saber si una palabra determinada existe en mi archivo (y considerando que las palabras están debidamente ordenadas), requiero de hacer unas 19 búsquedas, pues 2^N = 500,000 es aproximadamente 19.

Escribir un programa en Prolog que haga una búsqueda binaria no es difícil. La idea es colocarse en la palabra 250,000 inicialmente y e si la palabra que busco es la que está en esa posición. Si no es, entonces debo ver si "me pasé", es decir, la palabra está antes de la que hallé o "me quedé corto", es decir, la palabra está después de la que leí. Así, divido esa región del archivo 0 a 249,000; o 250,001 a 500,000 entre dos y vuelvo a hacer la búsqueda. En Prolog, naturalmente esto se hace de forma recursiva, lo cual implica guardar el estado del sistema, vía el stack, que es una estructura de datos LIFO (Last In, First Out), cada vez que se hace la llamada recursiva. Obviamente necesito una condición terminal o de salida para no ciclar al programa y que éste termine por quedarse sin memoria.

Si intento hacer, en cambio, una búsqueda binaria en un lenguaje de cuarta generación, hallaré que no necesito usar ninguna función recursiva y con un ciclo WHILE puedo resolver mis dificultades. Aquí no hay que llevar cuenta del stack y resulta muy eficiente en términos de memoria.

Aún así, 19, 20 búsquedas usando un stack en un algoritmo recursivo no sólo no es terriblemente ineficiente, sino que es además muy elegante. Niklaus Wirth decía: "Iteratum humanum est, recursivitum divinum est" (la iteración es humana, la recursion es divina)

Pero pensando en esto, me pregunté si quisiese hacer una búsqueda linea, es decir, buscar de la primera a la última palabra en mi diccionario. Si hago esto, en el mejor de los casos haré una búsqueda: la palabra que busco está en la primera posición. En el peor de los casos la palabra que busco estará en la última línea de mi archivo, por lo cual haré medio millón de consultas.

Si quiero hacer esto en Prolog, y además lo quiero hacer recursivo, debo prepararme para guardar en el stack medio millón de estados. Por lo menos eso en un principio. Mi esquema en Prolog sería algo así:


Si la variable I es mayor que medio millón termina.

Define la variable I como 1
busca en la iésima palabra si es la que busco
si no lo es, crea una nueva variable I1 que sea igual a I+1
ve al principio del procedimiento y vuelve a buscar con estos valores
Si es el valor, imprime el resultado y asigna a la variable el valor de medio millón + 1 y ve al procedimiento recursivo


Obviamente estoy asumiendo que quienes me leen ya han tenido contacto con Prolog, pero aquí el asunto que quiero ilustrar es la dificultad que voy a enfrentar, que es la de guardar el estado del sistema en el stack a cada llamada recursiva. Dudo que el programa soporte medio millón de llamadas guardadas en el stack. ¿Qué hacer entonces? La solución es usar la instrucción corte (cut), la cual se identifica con un signo de admiración "!" y entonces le decimos al sistema en prolog que no guarde todos estos estados temporales de la recursión, porque en el fondo no me interesa saber qué pasa cuando regreso de la recursión en sí.

Si se me ocurre hacer esto en algún lenguaje de cuarta generación como Pascal, lo que haría es:

repite
  asigna a I el valor de 1
  asigna termina = falso
  lee el registro cuyo valor es I
  Si es la palabra que busco, entonces
      asigna a la varianble termina = verdadero
      escribe resultado
  Si la palabra no es la que busco, incremento la variable I
hasta que termina = verdadero



Aquí no llevo control del stack y no tengo que preocuparme por nada de eso. Por ende, parece ser más fácil usar para este asunto en particular, un lenguaje de cuarta generación.

Pero un momento, hasta los lenguajes declarativos, que usan simbologías, no se salvan de tener que hacer procedimientos repetitivos como en los lenguajes tradicionales. Aquí la cuestión es que el programador necesita definir las cosas de manera que el sistema sea eficiente y no se quede sin memoria.

En suma, pienso que Prolog es un lenguaje comercialmente víable, pero en este caso, el programador requiere de ser más cuidadoso, mucho más, de los recursos de memoria con los que cuenta. No tener esto presente puede hacer de prolog un lenguaje por demás ineficiente y poco usable.

Criptogramas aritméticos y Prolog

Hay una historia, evidentemente falsa, en la cual se dice que un joven estaba en un país extranjero estudiando, pero después de algunas semanas, se halló sin dinero. Contó su remanente y halló que podía mandar un telegrama a su padre, para que éste le enviará más dinero. Sin embargo, su capital sólo alcanzaba para poner tres palabras.

¿Cómo decirle qué cantidad necesitaba? En un acto de ingenio, decidió escribir SEND + MORE = MONEY, asumiendo que su padre entendería que en clave le estaba diciendo qué cantidad necesitaba.

Pues bien, este tipo de criptogramas no son muy complicados de resolver en Prolog, porque en este tipo de lenguajes, en donde se hace hincapié en dos temas, la recursión y el backtrack. Así, la técnica para resolver el criptograma aritmético implica simplemente pasar todos los posibles valores por las variables que se necesitan y ver si se cumplen las condiciones exigidas. A esto se le llama un árbol solución y si dibujáramos todas las posibles alternativas, tendríamos un nodo principal con una serie de ramas, que muchas veces se ramifican generando muchas pequeñas ramas o bien, muchas ramas cortas.

La recursión es otra técnica presente. En este caso, se trata de hacer una llamada de una función a la misma función, en donde nuevos parámetros son involucrados. Pero antes de procesar la llamada, podemos observar si se cumple una condición terminal. Si es así, salimos de la recursión y en caso contrario, entramos en un ciclo más de ella.


La recursión tiene su importancia porque a pesar de que mcuhos lenguajes de cuarta generación, como Pascal y C, lo tienen disponible, es claro que se requiere de más recursos de cómputo, memoria en particular. Para ilustrarlo, pensemos en una oficina en donde existen unos diez teléfonos. Suena el primero y una secretaria lo contesta. Se pone a atender a quien habla cuando suena el segundo teléfono. Entonces la secretaria le dice al interlocutor del teléfono 1: "espere un momento por favor". Entonces la mujer contesta el segundo teléfono. Mientras habla con el interlocutor 2, suena un tercer teléfono. de nuevo, la secretaria le dice al interlocutor 2 que espere. Atiende al tercer teléfono y cuando termina la comunicación con éste tercer interlocutor, regresa al segundo y continúa la conversación en donde se quedó. Cuelga con este segundo interlocutor y retoma la conversación con el primer interlocutor en el punto donde la dejó. ¿Cómo se acuerda en qué punto se quedó en cada llamada? Bien pues la eficiente secretaria lleva un stack interno, lo cual es una estructura en donde se van apilando las conversaciones. Cuando empieza la primera llamada, la secretaria habla, pero entonces, al sonar el segundo teléfono, la secretaria pone en la pila la conversación en el punto que está al contestar el segundo teléfono. Al sonar el tercer teléfono, la secretaria pone encima de la pila, el estado de la segunda llamada. Cuando cuelga el tercer teléfono, va al anterior y ve en qué momento de la conversación se quedó y saca ese dato de la pila. Hace lo mismo al colgar.

El stack/pila, es una estructura FILO - First In, Last Out, (el primero que entra es el último que se va). Solamente para comparar con otras estructuras, ¿qué tipo de estructura es FIFO (First In, First Out)? ¿Qué ejemplo de la vida cotidiana contiene una estructura FIFO? (*)

Pero regresando al punto del criptograma aritmético, he aquí el programa que resuelve el acertijo en Prolog. ¿Podrá escribirse una versión más corta que ésta en cualquier otro lenguaje? Tengo mis dudas.


smm :-
        X = [S,E,N,D,M,O,R,Y],
        Digits = [0,1,2,3,4,5,6,7,8,9],
        assign_digits(X, Digits),
        M > 0,
        S > 0,
                  1000*S + 100*E + 10*N + D +
                  1000*M + 100*O + 10*R + E =:=
        10000*M + 1000*O + 100*N + 10*E + Y,
        write(X).

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

assign_digits([], _List).
assign_digits([D|Ds], List):-
        select(D, List, NewList),
        assign_digits(Ds, NewList).


No es de sorprenderse que el programa no sea una virtud de eficiencia. De hecho, requiere revisar 10!/2 posibilidades para ver en cuáles se cumplen las condiciones del problema. No obstante esto, hay que aclarar que en Prolog jamás se habla de eficiencia, o de uso de recursos en forma mínima.

A todo esto, una posible solución al criptograma es:


    [9,5,6,7]       SEND
    [1,0,8,5]     + MORE
                 ---------
  [1,0,6,5,2]      MONEY


________
(*) La cola de un banco es FIFO. La gente llega, se forma, un cajero atiende a un cliente. Hasta que no termina sus operaciones ese cliente, los demás deben esperar en la cola.