Subrutina recursiva en Fortran 77

Introducción

Cuando empecé los artículos previos sobre Recursividad Terminal, pensé en demostrarlos en Fortran 77 por ser el lenguaje por excelencia que no soporta recursividad. Sin embargo, encontré algunos problemas y opté por otros lenguajes. En este artículo he retomado ese reto. ¿Conseguí finalmente ejecutar una subrutina recursiva en Fortran 77?

Objetivo: implementar la función Factorial recursivamente en Fortran 77

Un ejemplo típico de función recursiva cuyo valor depende de invocarse a sí misma es la función matemática Factorial:

Factorial(N)	si N es 0 entonces 1	//Caso base.
	en otro caso, N * Factorial(N-1)	//Llamada recursiva.

Utilicé dicha función como ejemplo por ser muy sencilla de implementar, muy ilustrativa y también porque yo no soy ningún experto en Fortran 77.

Problema 1: Fortran 77 no soporta recursividad

Al intentar crear un pequeño programa en Fortran 77 con una función (usaré el termino subrutina en general) recursiva me topé con el primer problema: no está permitida la recursividad ni directa (invocarse a sí mismo) ni indirecta (una subrutina no puede invocar a otra que ya esté en la pila de ejecución, es decir, que una misma subrutina sólo puede estar una única vez en memoria).

El compilador (supongo que el lenguaje en sí) que utilicé resuelve la imposibilidad de que una subrutina se invoque a sí misma o a otra que indirectamente pueda invocarla a ella permitiendo invocar únicamente subrutinas ya definidas (no se permiten declaraciones por adelantado como en otros lenguajes).

Así, al estar definiendo una subrutina, su cuerpo no puede tener invocaciones a sí misma porque aún no está completamente definida y obtendremos un error de subrutina (símbolo) desconocida. De igual modo, cada subrutina sólo puede invocar subrutinas que hayan sido previamente definidas, por lo que ninguna de ellas podrá contener invocaciones a ella.

Solución al problema 1

Siguiendo las indicaciones dadas por Andrew J. Miller en su página Example 1: Recursive Routines in FORTRAN 77 (and Fortran 90), utilicé las directivas EXTERNAL y CALL para conseguir que una subrutina se invoque a sí misma. Sólo sirve para subroutine, no sirve para function.

De este modo, la subrutina recursiva recibirá como argumento el nombre de una subrutina a la que invocar, que en este caso, será ella misma.

Problema 2: en Fortran 77 se pasan los argumentos por referencia

En Fortran 77 los argumentos siempre se pasan por referencia, por lo que hay que tener cuidado de no alterar el valor de aquellos argumentos que semánticamente sean de entrada, sobre todo si hicieran falta después de la invocación recursiva.

Solución al problema 2

En el caso de la función Factorial(N) es necesario realizar llamadas recursivas con el valor (N-1). Hay que tener en cuenta que si se altera el argumento con una asignación N= N-1 se está alterando el valor de la variable original, porque se pasa por referencia. Por lo tanto, hay que tener cuidado con el sitio donde se almacena el resultado de ese cálculo, ya que su ubicación será traspasada a la invocación recurisva.

Problema 3: subrutinas sin almacenar variables en la pila

En Fortran 77 el valor una una variable local se considera indefinido una vez que se sale de su ámbito. Sin embargo, es opcional, mediante la directiva SAVE, que se salvaguarde el valor de las variables locales de una subrutina entre una invocación y otra. En otras palabras, se solicita al compilador que almacene la variable local de la subrutina de forma estática.

Suena bastante chocante, pero después de todo, no es una idea tan disparatada dado que el lenguaje no permite que una misma subrutina esté dos veces en memoria, y por tanto, es irrelevante que sus variables locales estuviesen almacenadas estáticamente, ahorrando el coste computacional que conlleva mantener la pila de ejecución. Más discutible es que se programase usando esa característica como truco para reaprovechar el valor entre invocaciones.

Al parecer, ese comportamiento se hizo tan común que algunos compiladores antiguos (especialmente conocido el de DEC) se saltaban el estándar y siempre almacenaban las variables locales de forma estática sin que se pusiese explícitamente SAVE, y muchos programadores se acostumbraron a programar así.

El compilador que utilicé, el g77, tiene una opción para compilar en ese modo: -fno-automatic.

Al utilizar la directiva SAVE, la variable local V de la subrutina S ocupa siempre la misma posición de memoria M. En caso de que S se invocase recursivamente, se estaría sobreescribiendo constantemente la misma posición de memoria M, por lo que es muy probable que al acceder a V después de una invocación recursiva su valor difiera del valor que tenía antes de la invocación.

Solución al problema 3

Yo he forzado que aparezca este problema utilizando la directiva SAVE, demostrando que se puede eludir mediante una implementación basada en Recursividad Terminal, puesto que tras la invocación ya se tiene el resultado y no hay que realizar ninguna operación más (siendo por tanto irrelevante el valor de las variables locales en ese punto).

Demostración

Es muy importante tener en cuenta utilizar un compilador estricto para Fortran 77, ya que a partir de Fortran 90 ya no existen tantas restricciones (soporta recursión). Para las pruebas he utilizado:

• g77 - GNU project Fortran 77 compiler

Hoy día me costó encontrar compiladores de Fortran 77, así que realicé las pruebas sólo con ese compilador.

A continuación se puede ver el programa en Fortran 77 que escribí para este artículo, con una implementación recursiva de la función matemática Factorial. Se compone de la función factorial(num) que es un simple envoltorio (wrapper) para la subrutina recursiva factorial_inner(self, input, output), donde:

• self es el nombre de la subrutina a invocar con CALL (ella misma en este caso).
• input es el número cuyo Factorial se desea calcular (argumento de entrada).
• output es la variable acumulador del resultado (argumento de entrada/salida).

Hay que prestar especial atención a las líneas 3, 10, 11 y 12.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

subroutine factorial_inner(self, input, output) integer :: input, output, tmp save tmp external self if (input .GT. 0) then c Con cualquier otro orden de estas 3 sentencias el programa c fallará si se usa la directiva SAVE sobre la variable tmp. output= input * output tmp= input - 1 call self(self, tmp, output) endif return end integer function factorial(num) integer :: num, output external factorial_inner output= 1 call factorial_inner(factorial_inner, num, output) factorial= output return end program demo_factorial integer :: input, output integer :: factorial write (*,*) 'Input number:' read (*,*) input output= factorial(input) write (*,*) 'Factorial= ', output stop end

He puesto la variable tmp para evitar que el compilador cree variables temporales debidas a cálculos intermedios (expresiones) y para demostrar el funcionamiento de la directiva SAVE.

Si se elimina la directiva SAVE de la línea 3, el programa funcionará perfectamente aunque se reordenen las sentencias 10, 11 y 12 (con sentido claro), porque la variable tmp estará almacenada en la pila. Sin embargo, con dicha directiva activada, sólo fucionará correctamente en ese orden.

Obsérvese que, con la directiva SAVE activada, desde factorial_inner sólo se accede a la verdadera variable input (el argumento input de factorial_inner apunta al argumento num de factorial que a su vez apunta a la variable input del programa principal) en la primera invocación, de ahí en adelante se está trabajando con una referencia a la variable tmp (a la que se le ha asignado una posición fija en memoria), y por tanto, en el resto de invocaciones el argumento input y la variable local tmp apuntan a la misma posición de memoria. Si se intercambian las instrucciones 10 y 11, output estará mal calculado puesto que en la primera iteración input ya habrá sido decrementado. De hecho, ese intercambio de instrucciones provoca que el resultado siempre sea 0 porque al llegar a la invocación correspondiente al Factorial de 1 se realizaría la multiplicación output*input = output*0 = 0.

Conclusión

En respuesta a la pregunta que planteé al comienzo del artículo, sí ha sido posible implementar una subrutina recursiva en Fortran 77, con ciertas restricciones impuestas por el propio lenguaje, aunque lo más interesante ha sido aprender sobre lo útil que es la pila de ejecución y cómo la Recursividad Terminal puede ser de ayuda en ciertas condiciones.

Enlaces

Enlaces de interés relacionados con este artículo:

• The Fortran 77 standard
  http://www.fortran.com/F77_std/rjcnf.html
• Andy's Fortran Examples (excelentes consejos para Fortran por Andrew J. Miller)
  http://www.esm.psu.edu/~ajm138/fortranexamples.html
• Fortran Arrays and Memory Allocation
  http://soliton.ae.gatech.edu/classes/ae6382/fortran/arrays_memory_allocation.html
• Online Compiler .net Fortran
  http://www.onlinecompiler.net/fortran
• g77 - GNU project Fortran 77 compiler
• http://www.kilmnj.com/g77/
• Using and Porting GNU Fortran
  https://gcc.gnu.org/onlinedocs/gcc-3.4.4/g77/
• fort77 - invoke f2c Fortran translator transparently, like a compiler
  http://manpages.ubuntu.com/manpages/natty/man1/fort77.1.html
  
• Fortran90 1.0 documentation
  http://www.fortran90.org/
• Are local variables in Fortran 77 static or stack dynamic?
  http://stackoverflow.com/questions/2582409/are-local-variables-in-fortran-77-static-or-stack-dynamic/2583248#2583248
• fortran SAVE statement
  http://stackoverflow.com/questions/2893097/fortran-save-statement/2893604#2893604

(Actualizado 03/03/2016)

Más sobre Recursividad Terminal (Tail Recursion)

Introducción

En el artículo anterior sobre Recursividad Terminal incluí la siguiente conclusión:

Algo muy interesante de la Recursividad Terminal es que no es necesario almacenar las llamadas recursivas en la pila de ejecución, lo que evita su desbordamiento. Además, en teoría, podría permitir realizar una implementación recursiva en un lenguaje que no tenga soporte para ello.

¿Te has preguntado si es posible utilizar Recursividad Terminal si la función requiere varias invocaciones recursivas?

A continuación intentaré demostrar empíricamente la citada conclusión a la vez que demostraré que sí es posible usar Recursividad Terminal aunque se necesiten varias invocaciones recursivas.

La sucesión de Fibonacci

La sucesión de Fibonacci es una sucesión matemática infinita de números naturales en la que cada valor se calcula como la suma de los dos valores anteriores. Unas fuentes la definen a partir de 0 y 1 mientras que otras lo hacen a partir de 1 y 2. Me voy a quedar con la que empieza en 0.

N	00	01	02	03	04	05	06	07	08	09	10
Valor	0	1	1	2	3	5	8	13	21	34	55

Se define recursivamente con dos invocaciones a sí misma:

fibonacci(N)	si N es 0 entonces 0	//Caso base 1.
	si N es 1 entonces 1	//Caso base 2.
	en otro caso, fibonacci(N-1) + fibonacci(N-2)	//Doble llamada recursiva.

Es un caso muy conocido que servirá para ilustrar el uso de Recursividad Terminal con varias invocaciones recursivas.

Implementación recursiva natural

Empecemos por la implementación recursiva natural. En este caso he utilizado C++, más adelante explicaré por qué.

double fibonacci_rec(int n) {
    double f;
    
    if (n <= 0) {
        f= 0;
    }
    else if (n == 1) {
        f= 1;
    }
    else {
//        f= fibonacci_rec(n - 1) + fibonacci_rec(n - 2);
        double one= fibonacci_rec(n - 1);
        double two= fibonacci_rec(n - 2);
        f= one + two;
    }
    
    return f;
}

He utilizado un estilo de programación en el que he tratado de desglosar todas las operaciones de alto nivel, para que sea más fácil comparar las diferentes implementaciones.

He llamado one al resultado de la invocación con N-1 y two al resultado de la invocación con N-2.

He utilizado double simplemente porque la función crece muy rápido y usando un int el resultado se desborda fácilmente.

Implementación recursiva terminal

Recuérdese que la Recursividad Terminal se basa en la idea de calcular todo lo necesario antes de realizar las llamadas recursivas, pasando ese cálculo intermedio a la invocación mediante argumentos.

En este caso, en teoría se necesitarían 2 llamadas recursivas, por lo que hay que realizar 2 cálculos intermedios y pasar 2 argumentos extra.

double fibonacci_tail_inner(int n, double one, double two) {
    double f;

    if (n <= 0) {
        f= 0;
    }
    else if (n == 1) {
        f= one;
    }
    else {
//        f= fibonacci_tail_inner(n - 1, one + two, one);
        double tmp= one + two;
        two= one;
        one= tmp;
        n= n - 1;

        f= fibonacci_tail_inner(n, one, two);
    }

    return f;
}

double fibonacci_tail(int n) {
    return fibonacci_tail_inner(n, 1, 0);
}

En este caso, he llamado one al acumulador de la invocación N-1 y two al acumulador de la invocación N-2. Los cálculos que hay que realizar en cada llamada son:

• el one que se pasa a la llamada recursiva es la suma del one y el two actuales.
• el two que se pasa a la llamada recursiva es el one actual.

Sólo ha quedado una única llamada recursiva. Hay que tener en cuenta que esto no es un detalle nimio, ya que esta implementación es muchísimo más rápida por tener un coste lineal (N), mientras que la implementación recursiva natural tiene un coste exponencial (2^N-1).

Implementación sin pila de ejecución: goto

Sí sí, has leído bien, he utilizado la operacion goto para demostrar que es posible hacer una implementación recursiva terminal sin ir apilando las invocaciones. Dicha característica, la posibilidad de usar variables globales y la disponibilidad de GCC son la razones de que haya utilizado C++ .

Discusiones "goto sí goto no" aparte, la operación goto no deja de ser una herramienta que en este caso me ha venido genial para realizar una implementación recursiva sin llamadas a subrutinas.

static int g_n;
static double g_one;
static double g_two;
static double g_f;
#define pseudocall_fibonacci_goto_inner() goto l_start

double fibonacci_goto_inner() {
l_start:
    if (g_n <= 0) {
        g_f= 0;
    }
    else if (g_n == 1) {
        g_f= g_one;
    }
    else {
        double tmp= g_one + g_two;
        g_two= g_one;
        g_one= tmp;
        g_n= g_n - 1;

        pseudocall_fibonacci_goto_inner(); //goto l_start;
    }

    return g_f;
}

double fibonacci_goto(int n) {
    g_one= 1;
    g_two= 0;
    g_n= n;
    g_f= -1;

    return fibonacci_goto_inner();
}

Para evitar suspicacias, he utilizado variables globales (g_n, g_one, g_two y g_f), dejando solamente la variable local tmp necesaria para poder calcular los valores de g_one y g_two para la "siguiente llamada recursiva". Al ser variables globales, sólo existen una única vez en memoria: no se instancian en la pila de ejecución cuando se necesitan, sino que están en el bloque de memoria estática del programa.

Al comienzo de la función fibonacci_goto_inner está la etiqueta l_start, que es el punto al que se salta cada vez que se desea simular una llamada recursiva, es decir, la "llamada recursiva" consiste saltar al comienzo de la función. Por estética, se puede "ocultar" la sentencia goto con una macro.

No hay ninguna llamada a subrutina, por lo que no se apila nada en la pila de ejecución: las únicas posiciones de memoria ocupadas son las de las variables globales y la variable local tmp.

Se puede comprobar visualmente que esta solución es prácticamente idéntica a la versión anterior, salvo por el uso de variables globales y la simulación de la llamada recursiva.

Optimización

Gracias a Avelino Herrera Morales sé que el GCC soporta Tail Call Optimization utilizando la opción -foptimize-sibling-calls, incluida en las opciones -O2 y -O3 (aparentemente sola no funciona, necesita acompañarse de -O1). Aparte de este comentario, utilizando el comando objdump me enseñó que el código generado con dicho flag no genera ninguna instrucción de llamada a subrutina (call o similar).

Probablemente, la solución que aplique el compilador sea muy similar a la que yo he expuesto aquí (pero con variables locales claro), es decir, simplemente sustituir la llamada recursiva por un simple salto al comienzo de la función sin apilar ni desapilar nada en la pila de ejecución.

Pruebas

En este enlace puedes ver un pequeño programa que incluye todas las implementaciones de la función Fibonacci de este artículo y una versión interativa.

C++ Fibonacci Recursion Test

Variando la variable MAX de la función main se puede comprobar fácilmente que la implementación recursiva natural es lentísima, volviéndose desesperante a partir de 50.

Con valores grandes de MAX (en mi caso, un valor cercano a 33333) se puede provocar que se desborde la pila en la implementación recursiva terminal sin optimizar sin que se desborde la pila en la implementación recursiva terminal con goto. Si se activa la optimización, se puede comprobar que no se desborda en ninguno de esos dos casos. En teoría, la versión recursiva natural también se desbordaría, pero en la práctica es tan lenta que no se puede comprobar (hay que desactivar esa parte del código para hacer pruebas de fuerza bruta).

Conclusión

Tal y como dije en la introducción ha quedado demostrado:

• que en un escenario donde no se dispone de la gestión de la pila de ejecución (al escribir en ensamblador a mano por ejemplo), es posible simular una implementación recursiva empleando un esquema de Recursividad Terminal.
• que la Recursividad Terminal se puede utilizar con funciones que requieran varias llamadas recursivas.

Destaco que la implementación Recursiva Terminal, si está optimizada, evita los problemas de desbordamiento de pila (Stack Overflow) de la solución Recursiva Natural. De hecho, la solución implementada con goto demuestra que no se necesita ni la pila.

Enlaces

Enlaces de interés relacionados con este artículo:

• ¿Qué es la sucesión de Fibonacci?
  http://curiosidades.batanga.com/4461/que-es-la-sucesion-de-fibonacci
• Sucesión de Fibonacci - Wikipedia
  http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci
• Recursividad Terminal (Tail Recursion) en este mismo blog
  http://programacion-curiosidad.blogspot.com.es/2015/04/recursividad-terminal-tail-recursion.html
• http://stackoverflow.com/questions/18582333/is-this-tail-recursion
• http://runnable.com/U44bs7vG_3wKYXUm/tail-recursive-fibonacci-c%2B%2B-for-recursion
• https://gist.github.com/enigmaticape/4013070
• http://stackoverflow.com/questions/22111252/tail-recursion-fibonacc
• https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

(Actualizado 28/05/2015)

Recursividad Terminal (Tail Recursion)

Introducción

Seguro que sabes lo que es la Recursividad: la definición de una función (o procedimiento) requiere de invocarse a sí misma con otros argumentos hasta alcanzar un caso base (situación en la que no es necesario invocarse a sí misma para obtener el resultado). El ejemplo típico es la función matemática factorial:

factorial(N)	si N es 0 entonces 1	//Caso base.
	en otro caso, N * factorial(N-1)	//Llamada recursiva.

En una función recursiva, para poder calcular el valor de la función hay que esperar hasta haber calculado el valor de todas las llamadas recursivas (puede haber varias, como en la Sucesión de Fibonacci por ejemplo).

La programación recursiva tiene ventajas y desventajas respecto a la programación iterativa: suele simplificar mucho el algoritmo pero suele ser más lenta y sobre todo, es muy propensa al desbordamiento de la pila de ejecución (stack overflow).

Recursividad Terminal

En la Recursividad Terminal (Tail Recursion en inglés), aunque una función se invoque a sí misma, no necesita esperar al resultado de la invocación recursiva, sino que antes de invocarse a sí misma, realiza todos los cálculos necesarios, de modo que en la última llamada (la correspondiente a un caso base) ya se te tenga el resultado final.

La idea es pasar el resultado parcial a la llamada recursiva en vez de esperar a que sea ésta la que lo devuelva. En otras palabras, realizar los cálculos a medida que se desciende recursivamente en vez de hacerlo a medida que se asciende al deshacer la pila de llamadas.

Si el compilador/intérprete es suficientemente inteligente, detectará que no es necesario almacenar el frame (ventana, marco o tradúcelo como quieras) de cada invocación en la pila de ejecución, y que, al llegar al final, no es necesario deshacer la pila de llamadas. Esta optimización se conoce como Tail Call Optimization (TCO).

De ese modo, se ahorra memoria (evitando los problemas de desbordamiento de la pila de ejecución) y se aumenta muchísimo el rendimiento (se evitan todas las operaciones de manejo de la pila de ejecución), aunque el rendimiento podrá ser mejor o peor dependiendo del algoritmo en sí.

Ejemplo

El concepto es bastante extraño y complicado de explicar; es mucho mejor ver un ejemplo. Los ejemplos se han ejecutado con el intérprete GNU CLISP v2.49+ ejecutable online en el siguiente enlace:

Coding Ground - Execute LISP Program Online

A continuación se puede ver un programa en Common Lisp para invertir el orden de los elementos de una lista (reverse). El código fuente completo está disponible en este enlace:

Source code: Recursividad Terminal (Tail Recursion)

a) Recursión Normal

Esta versión está escrita con recursión normal: en cada invocación, el resultado consiste en encolar el primer elemento al resultado de la invocación recursiva con el resto de elementos. El caso base es cuando se recibe una lista vacía, devolviendo una lista vacía también.

;Normal recursion
(defun my_reverse (a_list)
    (cond
        ((null a_list) nil)
        (t (append
                (my_reverse (rest a_list))
                (list (first a_list))
           ) 
        )
    )
)

(trace my_reverse)
(write (my_reverse '(1 2 3 4 5)))

A continuación se muestra la traza de ejecución:

;; Tracing function MY_REVERSE.                                                                                                                                                      
1. Trace: (MY_REVERSE '(1 2 3 4 5))                                                                                                                                                  
2. Trace: (MY_REVERSE '(2 3 4 5))                                                                                                                                                    
3. Trace: (MY_REVERSE '(3 4 5))                                                                                                                                                      
4. Trace: (MY_REVERSE '(4 5))                                                                                                                                                        
5. Trace: (MY_REVERSE '(5))                                                                                                                                                          
6. Trace: (MY_REVERSE 'NIL)                                                                                                                                                          
6. Trace: MY_REVERSE ==> NIL                                                                                                                                                         
5. Trace: MY_REVERSE ==> (5)                                                                                                                                                         
4. Trace: MY_REVERSE ==> (5 4)                                                                                                                                                       
3. Trace: MY_REVERSE ==> (5 4 3)                                                                                                                                                     
2. Trace: MY_REVERSE ==> (5 4 3 2)                                                                                                                                                   
1. Trace: MY_REVERSE ==> (5 4 3 2 1)                                                                                                                                                 
(5 4 3 2 1)  

Se puede comprobar que la lista en orden inverso se construye desde abajo hacia arriba.

b) Recursión Terminal

Ahora se muestra como quedaría el algoritmo utilizando recursividad terminal. La idea es apilar el primer elemento de in_list a out_list y pasar el resultado de eso como out_list a la invocación recursiva con el resto de in_list. Y en el caso base (in_list está vacía), ahora simplemente se devuelve el argumento out_list sin más.

Ha sido necesario cambiar la interfaz de la función para que reciba 2 argumentos en vez de uno, y algo muy importante, la primera invocación deber realizarse con el valor correcto para el argumento out_list: una lista vacía. Por eso se utiliza una función envoltorio (wrapper).

;Tail recursion
(defun my_reverse_tail_inner (in_list out_list)
    (cond
        ((null in_list) out_list)
        (t (my_reverse_tail_inner
                (rest in_list)
;Alternativa al append.
;                (cons (first in_list) out_list)
                (append
                    (list (first in_list))
                    out_list
                )
            )
        )
    )
)

(defun my_reverse_tail (a_list)
    (my_reverse_tail_inner a_list nil)
) 

(trace my_reverse_tail_inner)
(trace my_reverse_tail)
(write (my_reverse_tail '(1 2 3 4 5)))

A continuación se muestra la traza de ejecución:

;; Tracing function MY_REVERSE_TAIL_INNER.                                                                                                                                           
;; Tracing function MY_REVERSE_TAIL.                                                                                                                                                 
1. Trace: (MY_REVERSE_TAIL '(1 2 3 4 5))                                                                                                                                             
2. Trace: (MY_REVERSE_TAIL_INNER '(1 2 3 4 5) 'NIL)                                                                                                                                  
3. Trace: (MY_REVERSE_TAIL_INNER '(2 3 4 5) '(1))                                                                                                                                    
4. Trace: (MY_REVERSE_TAIL_INNER '(3 4 5) '(2 1))                                                                                                                                    
5. Trace: (MY_REVERSE_TAIL_INNER '(4 5) '(3 2 1))                                                                                                                                    
6. Trace: (MY_REVERSE_TAIL_INNER '(5) '(4 3 2 1))                                                                                                                                    
7. Trace: (MY_REVERSE_TAIL_INNER 'NIL '(5 4 3 2 1))                                                                                                                                  
7. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
6. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
5. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
4. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
3. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
2. Trace: MY_REVERSE_TAIL_INNER ==> (5 4 3 2 1)                                                                                                                                      
1. Trace: MY_REVERSE_TAIL ==> (5 4 3 2 1)                                                                                                                                            
(5 4 3 2 1) 

Se puede ver que la lista en orden inverso se va construyendo desde arriba hacia abajo y que al llegar al caso base, ya está completamente construída, por lo que se deshace la pila devolviendo siempre lo mismo: el resultado final. En este caso, aparece una llamada más, la correspondiente a la función envoltorio (wrapper).

En este caso, también se podría simplificar el código utilizando la función cons para apilar un elemento al comienzo de una lista (en el caso de recursion normal hay que encolar usando la función append), simplificando mucho el código y reduciendo su coste.

Demostración de Tail Call Optimization

El intérprete indicado previamente permite aplicar Tail Call Optimization (TCO), pero para ello hay que precompilar la función utilizando compile.

Hasta donde mi conocimiento alcanza, es complicado desmostrar que se aplica TCO:

• una vez compilada una función (optimizada o no), no se puede tracear (sólo aparecerá una invocación).
• habría que acceder al código generado (¿es eso posible?) y además analizarlo para entenderlo...

Así que, he demostrado empíricamente que efectivamente se aplica TCO. La idea es averiguar cuán grande puede ser una lista sin que se desborde la pila al invertir el orden de sus elementos. Utilizando el intérprete indicado previamente, fui aumentando el tamaño de la lista (límite del loop) del siguiente programa:

(compile 'my_reverse)
(compile 'my_reverse_tail_inner)

;normal: se desborda la pila con menos de 35000 elementos.
(time (write (list-length (my_reverse (loop for n from 1 to 34000 by 1 collect n)))))
(write-line "")

;terminal con tantos elementos como la normal.
(time (write (list-length (my_reverse_tail (loop for n from 1 to 34000 by 1 collect n)))))
(write-line "")

;terminal: prueba de que se puede utilizar con una cantidad de elementos enorme.
(time (write (list-length (my_reverse_tail (loop for n from 1 to 3400012 by 1 collect n)))))
(write-line "")

La versión normal (my_reverse) se desborda con menos de 35000 elementos, mientras que con la versión terminal (my_reverse_tail) no conseguí desbordar la pila ni con varios millones de elementos.

Como datos orientativos, en una de las ejecuciones obtuve los siguientes resultados:

34000                                                                                                                                                                                
Real time: 38.68157 sec.                                                                                                                                                             
Run time: 38.663563 sec.                                                                                                                                                             
Space: 9248826160 Bytes                                                                                                                                                              
GC: 9157, GC time: 29.230534 sec.                                                                                                                                                    
34000                                                                                                                                                                                
Real time: 0.052549 sec.                                                                                                                                                             
Run time: 0.052638 sec.                                                                                                                                                              
Space: 1642160 Bytes                                                                                                                                                                 
GC: 1, GC time: 0.002901 sec.                                                                                                                                                        
3400012                                                                                                                                                                              
Real time: 6.269858 sec.                                                                                                                                                             
Run time: 6.099169 sec.                                                                                                                                                              
Space: 163210736 Bytes                                                                                                                                                               
GC: 21, GC time: 0.995367 sec.                                                                                                                                                       

Se puede observar una descomunal diferencia de velocidad, siendo la versión normal lentísima respecto a la terminal.

El consumo de memoria de la versión normal también es muy superior. Y se puede observar que el Garbage Collector apenas se dispara en la versión terminal.

Conclusión

Algo muy interesante de la Recursividad Terminal es que no es necesario almacenar las llamadas recursivas en la pila de ejecución, lo que evita su desbordamiento. Además, en teoría, podría permitir realizar una implementación recursiva en un lenguaje que no tenga soporte para ello.

Un punto negativo de la Recursividad Terminal está en que hay que cambiar la interfaz de la función para añadir el argumento "de salida o acumulador" y que además, hay que cerciorarse de invocarla con el valor inicial adecuado para dicho argumento; para esto último es recomendable crear una función envoltorio (wrapper) que se encargue de ello mostrando una interfaz equivalente a la versión no terminal.

Lo que a mí me parece más interesante, es que se trata una solución recursiva alternativa, que tal vez permita implementar algo recursivamente que de otro modo no se pueda. Por ejemplo, si en Common Lisp no se dispusiera de la función append (encolar), no se podría realizar la implementación normal, pero sí la terminal utilizando la función cons (apilar).

Enlaces

Enlaces de interés relacionados con este artículo:

• http://en.wikipedia.org/wiki/Tail_call
• http://blog.zarovich.org/index.php/2007/02/recursividad-terminal/
• http://emiliodevesa.com/recursividad-terminal-en-ocaml/
• http://stackoverflow.com/questions/33923/what-is-tail-recursion
• Common Lisp
  https://common-lisp.net/
• [LISPWORKS] Common Lisp HyperSpec (TM)
  http://www.lispworks.com/documentation/HyperSpec/Front/index_tx.htm
• This is GNU CLISP - an ANSI Common Lisp Implementation
  http://www.clisp.org/
• TCO in CLISP using the example from Chris Taylor.
  http://stackoverflow.com/a/15271806

(Actualizado 29/04/2015)

Conversión de Charset/Encoding en Java

Introducción

Un problema bastante común para los programadores, especialmente para los hispanohablantes, es la codificación de caracteres (Character encoding en inglés).

Un juego de caracteres (en inglés Character set o más comúnmente charset) es la definición de un conjunto de caracteres determinado identificándolos con un número.

Un charset puede tener uno o varios encodings. Un encoding determina la representación de cada carácter mediante secuencias de bytes (1 o más bytes). Es decir, el mismo carácter puede tener distintas representaciones en encodings diferentes, o visto desde el otro lado, una misma secuencia de bytes puede representar caracteres diferentes en un encoding u otro.

El manejo de encodings suele ser peor que un dolor de muelas, sobre todo cuando se necesita realizar comparaciones de Strings que provienen de diferentes fuentes: entrada de usuario, base de datos, código fuente, etc. Para obtener resultados correctos, hay que asegurarse de que cada String se construye a partir del encoding adecuado.

Problemas

Los problemas suelen aparecer con caracteres no ASCII como las vocales acentuadas. Por ejemplo, la cadena aáeéiíoóuú se representaría así:

Encoding / Bytes	00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17	18	19	20	21	22	23
ISO-8859-1	61	e1	65	e9	69	ed	6f	f3	75	fa	0a
UTF-8	61	c3	a1	65	c3	a9	69	c3	ad	6f	c3	b3	75	c3	ba	0a
UTF-16	ff	fe	61	00	e1	00	65	00	e9	00	69	00	ed	00	6f	00	f3	00	75	00	fa	00	0a	00

Se puede observar que una misma secuencia de caracteres da lugar a 3 secuencias de bytes diferentes.

Las secuencias de bytes probablemente no sean compatibles entre sí: es decir, no se puede leer una secuencia codificada en UTF-8 como si lo estuviese ISO-8859-1 o en UTF-16. En el ejemplo, al usar un editor ISO-8859-1 con la secuencia en UTF-8 se vería aáeéiíoóuú y al hacer lo inverso se vería a�e�i�o�u.

Puede ocurrir que secuencias válidas en un encoding sean inválidas en otro. Por ejemplo, la secuencia hexadecimal C1C1 representa la cadena ÁÁ en ISO-8859-1 pero es una secuencia inválida en UTF-8.

También puede pasar que haya caracteres de un charset que no se puedan representar en otro: por ejemplo, el charset ISO-8859-15 tiene el símbolo del Euro €, por lo que no se podrían convertir con exactitud textos con dicho símbolo al charset ISO-8859-1 que no lo tiene.

Strings en Java

En Java, los caracteres y secuencias de caracteres (String, StringBuilder, etc) se representan en una de las versiones del encoding UTF-16 de Unicode. Eso significa que da igual desde que fuente se haya creado el carácter, internamente se almacena en UTF-16.

Los constructores de las clases String, InputStreamReader y OutputStreamWriter entre otras permiten indicar el charset (Charset), de modo que se puede indicar como interpretar las secuencias de bytes para convertirlas en caracteres y viceversa. Por defecto se utiliza Charset.defaultCharset(), un charset obtenido de la configuración del sistema operativo para el usuario (entorno) que arrancó la máquina virtual Java.

En el fondo, para realizar la conversión entre caracteres y secuencias de bytes al leer o escribir, se utilizan las siguientes clases:

• CharsetEncoder: permite obtener la representación como secuencia de bytes de una secuencia de caracteres en determinado charset.
• CharsetDecoder: permite interpretar una secuencia de bytes como una secuencia de caracteres en un determinado charset.

Dichas clases proporcionan el mayor control sobre el proceso de conversión, permitiendo especificar por ejemplo el comportamiento ante secuencias de bytes inválidas o caracteres no representables.

Por el contrario, otras alternativas tienen restricciones que se deben tener en cuenta. Por ejemplo, en la documentación oficial de la clase String:

• public byte[] String#getBytes(Charset): (...) This method always replaces malformed-input and unmappable-character sequences with this charset's default replacement byte array. (...)
• public byte[] String#getBytes(): (...) The behavior of this method when this string cannot be encoded in the given charset is unspecified. (...)

Ejemplos

He realizado una implementación simple del comando iconv. El código se puede ver en el siguiente enlace:

CharsetTest

El modo de uso es el siguiente:

$ java -jar Project.jar input.file input-charset ouput-charset

Por ejemplo:

$ java -jar Project.jar utf8.txt utf8 iso-8859-1

Si no se invoca con 3 argumentos, se muestra la lista de charsets disponible y se indica el modo de uso correcto.

El código incluye la función:

public static String doConversion(
    String input,
    String inputCharsetName,
    String outputCharsetName
) throws IOException;

para transformar una String desde un charset a otro. He explicado que en memoria una String siempre está en UTF-16, por lo que la verdadera utilidad de esta función es ser un esqueleto para tratar los posibles problemas de conversión que se pueden presentar al pasar una String desde un charset origen (es decir, se está seguro de que todos los caracteres que la componen son representables en dicho charset) a otro charset destino según se configuren:

• CharsetEncoder#onMalformedInput(CodingErrorAction)
• CharsetEncoder#onUnmappableCharacter(CodingErrorAction)
• CharsetDecoder#onMalformedInput(CodingErrorAction)
• CharsetDecoder#onUnmappableCharacter(CodingErrorAction)

Para hacer pruebas, es recomendable utilizar 2 de los charsets cuya presencia debe estar garantizada en cualquier implementación de la plataforma Java (ver java.nio.charset.StandardCharsets): ISO-8859-1 y UTF-8. Y utilizar cadenas de caracteres cuya representación varíe de un charset a otro, como por ejemplo, las vocales acentuadas: áéíóú.

Enlaces

Enlaces de interés relacionados con este artículo:

• java.nio.charset.Charset
• java.nio.charset.StandardCharsets
• Supported Encodings
• Displays Available Charsets and aliases
• http://apuntesadeteran.blogspot.com.es/2013/06/abordando-problemas-de-encoding-en-java.html 
• http://kunststube.net/encoding/
• http://stackoverflow.com/questions/9699071/what-is-the-javas-internal-represention-for-string-modified-utf-8-utf-16
• http://docs.oracle.com/javase/8/docs/technotes/guides/intl/overview.html
• http://docs.oracle.com/javase/tutorial/i18n/text/unicode.html
• http://docs.oracle.com/javase/7/docs/api/java/lang/String.html
• http://docs.oracle.com/javase/7/docs/api/java/lang/Character.html#unicode
• http://es.wikipedia.org/wiki/Unicode#Repertorio_de_caracteres
• http://www.iso.org/iso/catalogue_detail?csnumber=28245
• http://www.unicode.org/faq/utf_bom.html#UTF8
• http://www.unicode.org/faq/utf_bom.html#UTF16

(Actualizado 31/01/2015)