CIUDAD DE MÉXICO (proceso.com.mx).-Si uno revisa el índice temático del Manual del Lenguaje Pascal, de la empresa Borland, lo que es un ciclo recursivo dice así: “Ciclo recursivo: Véase ciclo recursivo”. Pero más allá de la puntada, el tema de la auto referencia y recursión tiene mucho que ver con los elementos propios de la vida, entre muchos otros dominios.

Un elemento que parece condición imprescindible para la existencia de vida es la auto replicación de los organismos, lo que viene a ser en términos formales lo que llamamos auto referencia. Los organismos vivos, por ejemplo, poseen en su genética la información completa para crear otro ser vivo como él. Tienen pues un mapa completo de ellos mismos y en alguna medida es auto referente. Curiosamente, en lo que se refiere a las computadoras, que es el entorno en donde se pueden analizar los problemas de la vida, denominada “vida artificial” (que se hace vía simulaciones de las características de la vida: metabolismo, alimentación, reproducción, etcétera). Y hallamos que éstas se programan a partir de lenguajes específicamente diseñados para generar las secuencias de instrucciones que hagan que la máquina haga la labor que queremos.

Hay una variedad enorme de lenguajes de programación. 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, 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 (hartman@symcom.math.uiuc.edu), escrito para la Commodore 6428

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.

En Pascal, un programa que da como resultado el propio código fuente puede ser este:

program self(input, output);

type

s = string[255];

n=integer;

var

a : array [1..100] of s;

i,j : integer;

function t(a:integer):integer;

begin

if a<7 then t:=a else t:=a+11

end;

function q(a:s):s;

var j:n;

begin

for j:=strlen(a)downto 1 do

   if a[j]=#39 then strinsert(#39,a,j);

 q:=a;

end;

begin (*main*)

a[1] := 'program self(input, output);';

a[2] := 'type s = string[255]; n=integer;';

a[3] := 'var a : array [1..100] of s; i,j :

integer;';

a[4] := 'function t(a:integer):integer; begin if a<7

then t:=a else t:=a+11 end; function q(a:s):s;';

a[5] := ' var j:n;begin for j:=strlen(a)downto 1 do if

a[j]=#39 then strinsert(#39,a,j);q:=a;end;';

a[6] := 'begin';

a[18] := ' for i := 1 to 11 do begin

setstrlen(a[i+6], 0);';

a[19] := ' strwrite(a[i+6],1,j,''

a['',t(i):1,''] := '''''', q(a[t(i)]), '''''';'');';

a[20] := ' end;';

a[21] := ' for i := 1 to 22 do writeln(a[i]);';

a[22] := 'end.';

for i := 1 to 11 do begin setstrlen(a[i+6], 0);

   strwrite(a[i+6],1,j,' a[',t(i):1,'] := ''',

q(a[t(i)]), ''';');

end;

for i := 1 to 22 do writeln(a[i]);

end.

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 estos dos ejemplos es que los lenguajes utilizados, BASIC y Pascal son imperativos, en donde el compilador (o intérprete) requiere de separar los datos de las instrucciones. Dicho de otra manera, caemos en la idea que von Neumann analizara en los años cincuenta del siglo pasado y que además, diese con un modelo que ha sido probablemente muy parecido al que se genera en la auto replicación de las cadenas de ADN.

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 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. 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.

Lo interesante es que si suponemos que el ADN es el código que contiene las instrucciones para crear un nuevo ser, considerando que los errores que ocurren (estadísticamente) son mínimos, entonces el ADN debe contener una copia completa de cómo crear un individuo completo, algo así como el código Quine de la vida. Y esto tiene algunos elementos para considerar que es así. Los programas Quine no pueden existir si dentro del código no está el código mismo que trata de auto referenciarse. Esto podría mostrarnos que la vida se produce por un fenómeno recusivo y entonces tendríamos que explicar la razón de que es así.

Es curioso notar que los fenómenos en vida artificial contengan un grado enorme de recursión. Pareciera que éste es el mejor mecanismo para poder replicar información. Pero ya hemos visto que esto requiere de más recursos que la rutina equivalente de manera iterativa. ¿Por qué la recursión en el fenómeno de la vida (real y artificial) tiene tanta relevancia?