lunes, 29 de febrero de 2016

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

(Actualizado 03/03/2016)
Publicado por el No hay comentarios:
Etiquetas: , ,
Suscribirse a: Entradas (Atom)