Los lenguajes de programación vienen en muchos colores y sabores. Los hay de bajo nivel, como los ensambladores, que permiten escribir con códigos mnemotécnicos, las instrucciones para manejar los registros, leer la memoria, guardar información en la misma, hacer operaciones lógicas y aritméticas con ceros y unos, que es finalmente el lenguaje de más bajo nivel, el más primitivo, que podemos hallar en una computadora. Otros lenguajes de programación abstraen muchos de los detalles del código nativo y permiten programar sin tener que pasar por los detalles de la implementación física de la computadora. Así, podemos poner una instrucción como la siguiente:
A := B + C;
típica de Pascal, que suma los números B + C y el resultado lo pone en la variable A. Este mismo programa en ensamblador del procesador 6800 (de Motorola, de 8 bits), se escribe de esta manera:
LDAA #$05
ADDA #$08
STAA $50
SWI
Lo cual dice que la secuencia para sumar dos números sería:
• Cárguese el acumulador A (un registro que tiene el microprocesador 6800) con el valor 5 (en hexadecimal) [LDAA #$05]
• Añádase al acumulador A el valor 08 [ADDA #$08]
• Guárdese el resultado de lo que hay en el acumulador A en la localidad 50 (hexadecimal) [STAA $50]
• Termínese el programa con una interrupción por software [SWI] (software interrupt)
Como puede verse, hay que hacer más operaciones en lenguaje ensamblador que en un lenguaje como Pascal. Por supuesto, Pascal requiere de un programa especial, llamado “compilador”, que es un traductor de código de alto nivel a código de máquina, para que la computadora pueda ejecutar la suma.
Lo importante aquí es que los lenguajes de alto nivel permiten sustraerse de los detalles y así abstraer la información, colocándola en otro nivel y así hacer que la programación sea más fácil de escribir y de seguir por otros. Los compiladores, cabe aclarar, convierten el código fuente (en Pascal, por ejemplo), en código objeto (código nativo de la máquina que lo ejecutará).
La pregunta que naturalmente surge, en el contexto de la vida artificial es: ¿Podemos crear un programa que sea auto referente? Es decir, ¿podemos escribir un programa que entregue como resultado el propio programa fuente? Este tipo de programas se llaman genéricamente “código Quine”, por ser el apellido del filósofo (y lógico), Willard van Orman Quine, que trabajó en la auto referencia en los lenguajes humanos. Por ejemplo, al decir “esta frase es falsa”.
La tarea de hacer un programa que se auto replique, se auto reproduzca, tiene mucho que ver con el fenómeno de la vida misma y desde luego, con el formalismo de la vida artificial. Actualmente el crear un programa que se auto reproduzca así mismo es un reto que se ha resuelto prácticamente en todos los lenguajes de programación, desde los más sofisticados hasta los más simples. Veamos algunos ejemplos.
En BASIC:
10 READ A$:PRINT 10 A$:PRINT 20 “DATA” A$
20 DATA READ A$:PRINT 10 A$:PRINT 20 “DATA” A$
Autor: Christmas Hartman ([email protected]), escrito para la Commodore 64.
Una descripción somera de la idea de Hartman es la siguiente: En la línea 10 el programa lee una cadena de caracteres (la cual está en la sección DATA del código (línea 20). Nótese que la línea 20 es prácticamente la repetición del código de la línea 10, que se maneja no como código, sino como datos del programa, que son leídos por el código de la propia línea 10.
Si se analiza la estructura de este programa, puede verse de nuevo que dentro del código se encuentra como datos el código mismo. Y éste es el truco de los programas auto referentes. De hecho, parece imposible no hacer esto para resolver la tarea propuesta.
La dificultad con este ejemplo es que BASIC es un lenguaje imperatico, en donde el compilador (o intérprete) requiere de separar los datos de las instrucciones. Pero existen lenguajes que no hacen distinción entre datos y código. Uno de ellos es Prolog, otro es Postscript. Uno más es LISP. A estos se les llaman lenguajes funcionales y pueden manejar las simbologías de maneras más poderosas. La solución del problema del código auto referente puede resolverse en Prolog así:
quine :- listing(quine).
La auto referencia en lenguajes como Prolog puede verse en el siguiente código auto referenciable, basado en un problema propuesto por Bertrand Russell que dice así: “En un pueblo hay un barbero que rasura a todos aquellos que no se rasuran a sí mismos”. La pregunta a resolver es: “¿Quién rasura al barbero?”.
El código en Prolog tiene una sola línea:
rasura(barbero, Y) :- not (rasura (Y,Y)). //el barbero rasura a Y si éste no se rasura a sí mismo.
El problema con este código es que no tiene fin. No puede ser resuelto porque hay una contradicción lógica inevitable. Si el barbero no se rasura a sí mismo, entonces sería parte de las personas que no se rasuran a sí mismas, por lo que debería ser rasurado por el barbero, pero ¡ése es él mismo!. Puede verse que aquí el ciclo auto referente es incómodo y da al traste con la lógica del problema. De hecho, ejecutar este programa en una máquina que tenga un compilador de Prolog, nos llevará a un error de falta de memoria (out of memory), pues la recursión se convierte en infinita y las computadoras de la vida real no tienen memoria infinita y de ahí el error.
El fenómeno de la recursión se observa continuamente en los lenguajes de programación. Casi todos los lenguajes de alto nivel tienen alguna forma de hacer procedimientos o funciones recursivas, es decir, hacer que se definan ciertos algoritmos de manera auto referente. La dificultad de la recursión es que requiere de muchos más recursos de máquina para ejecutarse, particularmente se utiliza en muchísimas implementaciones de los lenguajes de programación, una estructura llamada “pila” (o stack). Una pila puede pensarse como una caja en donde ponemos –digamos– libros. El primer libro que meto en la caja queda en el fondo. Puedo ir metiendo más libros y precisamente hacer una pila con ellos. La cuestión es que el primer libro que entra a la pila es el último que puedo sacar. Eso en esencia es una estructura LIFO (Last In, First Out), es decir, el último que entra es el primero que sale.
En computadoras con pocos recursos, particularmente memoria, la recursión no ser usa normalmente. En ese caso se utilizan algoritmos iterativos, que hacen la misma tarea que un algoritmo recursivo, pero utilizando muchos menos recursos. De hecho, se puede demostrar que todo algoritmo recursivo tiene una versión iterativa.
Va un pequeño reto para los lectores binarios de unocero.com: escríbase, sin ver en Internet, sin revisar ninguna fuente externa, un programa, en su lenguaje favorito, que como salida entregue el propio código que hace esta tarea.