Llamadas a subrutinas en el mundo antiguo: antes de que las computadoras tuvieran pila o heap

Llamadas a subrutinas en la antigüedad, cuando las computadoras no tenían pila ni heap

• En la computación moderna damos por sentadas la pila y el heap, pero en los primeros tiempos de la computación las computadoras funcionaban sin pila ni heap.
• No es difícil imaginar la computación sin asignación dinámica de memoria. Había que usar búferes de memoria de tamaño fijo para todo.
• Si había que manejar datos de tamaño variable, se reservaba un búfer de tamaño fijo lo bastante grande como para contener los datos previsibles.
• Se podía ofrecer una configuración en tiempo de compilación para que el cliente ajustara la capacidad máxima, o escribir un asignador personalizado que pudiera "asignar" y "liberar" memoria dentro de un búfer de tamaño fijo.

Llamar funciones sin pila

• El compilador define variables globales secretas para los parámetros de entrada, la dirección de retorno y las variables locales de cada función.
• Para generar una llamada a función, el compilador asigna los valores de los parámetros a esas variables globales secretas, asigna la dirección de retorno a la variable secreta de "dirección de retorno" de la función y luego salta al inicio de la función.
• La función lee los parámetros desde las variables globales secretas y usa variables globales secretas predefinidas que corresponden lógicamente a las variables locales.
• Cuando la función termina, salta a la dirección almacenada en la variable secreta de "dirección de retorno" de la función.

Optimización del ABI

• Para optimizar el ABI, algunos valores se pasan en registros en lugar de variables globales.
• La mayoría de los procesadores tienen un registro de "enlace" y una instrucción de "salto con enlace", que configura automáticamente el registro de enlace con la dirección que sigue a la instrucción de "salto con enlace".
• Se optimiza la convención de llamada para pasar los primeros dos parámetros en registros.

La imposibilidad de las llamadas recursivas

• Las llamadas recursivas no funcionan. Sobrescriben la variable de dirección de retorno con la dirección de retorno de la llamada recursiva, así que cuando la llamada externa termina, salta al lugar equivocado.
• Los lenguajes de programación de la época resolvieron este problema declarando que no admitían recursión.

Conversación extra

• Algunos compiladores funcionaban de una manera aún más ingeniosa usando código automodificable: la variable especial de dirección de retorno era en realidad el campo de dirección de la instrucción de salto al final de la función.
• Si el procesador no admitía salto indirecto, este método se usaba por necesidad práctica.
• Una vez reconocido el valor práctico de las subrutinas, muchos procesadores añadieron una instrucción de llamada a subrutina que guardaba la dirección de retorno en la primera palabra de la subrutina y comenzaba la ejecución en la segunda palabra de la subrutina.
• Para regresar desde la subrutina, se ejecutaba un salto indirecto a través de la etiqueta de inicio de la subrutina.

La opinión de GN⁺

• Este artículo ayuda a entender la evolución de las técnicas de gestión de memoria usadas en el desarrollo de software moderno al explicar cómo se programaba en los primeros tiempos de la computación, cuando no existían la pila ni el heap.
• La forma de programar de aquella época, sin pila ni heap, puede parecer muy extraña e ineficiente para los desarrolladores actuales, pero aporta un contexto importante para comprender cómo ha evolucionado la tecnología a lo largo de la historia de la computación.
• Las limitaciones de programación de una época en la que las llamadas recursivas eran imposibles ofrecen un dato histórico interesante para los desarrolladores que hoy usan algoritmos recursivos.
• Desde una mirada crítica, estas primeras formas de programación muestran que eran muy limitadas para satisfacer los requisitos complejos y diversos de la actualidad.

[GN⁺]

Comentarios de Hacker News

• Reseña positiva del libro "The Art of Computer Programming"

  • Aunque el libro parece antiguo, trata varios algoritmos para modificar arreglos dinámicos y estructuras de datos de antes del heap y el stack.
  • El libro también explica la recolección de basura y la implementación de listas en Lisp, y ofrece ese tipo de conocimiento enciclopédico que Knuth hace que uno espere.

• Explicación de cómo dos arreglos pueden compartir dinámicamente un mismo espacio

  • Un arreglo crece normalmente desde la posición #0, y el otro crece en reversa desde la posición #End, permitiendo que ambos compartan de forma eficiente un espacio asignado estáticamente.
  • Este método puede extenderse a varios arreglos, pero a partir de cierto punto quizá sea mejor usar Malloc y Realloc.

• Se comparte un enlace a una historia interesante sobre lo polémico que fue introducir funciones recursivas en el lenguaje ALGOL

  • Mediante el enlace se comparte una historia interesante sobre cómo se introdujo la recursión en los lenguajes de programación.

• Se comparte la experiencia de escribir un intérprete de Forth para una máquina SUBLEQ y una máquina bit-serial

  • Ninguna de estas dos máquinas tiene stack de llamadas a funciones, que es un elemento esencial de Forth.
  • SUBLEQ no permite carga ni almacenamiento indirectos, y requiere código automodificable para realizar tareas poco comunes.
  • Se construye una máquina virtual para realizar estas funciones y dar soporte a multihilo cooperativo.
  • Cuando hace falta, el heap se escribe en Forth e incluso incluye operaciones de punto flotante implementadas como funciones de software.

• Explicación de la evolución técnica relacionada con las llamadas a subrutinas en el procesador PDP-8

  • Al principio, la instrucción JMS guardaba la dirección de retorno en la primera palabra de la función.
  • Después se usaron ubicaciones de autoincremento para crear un stack simple, y el prólogo/epílogo de la función administraba manualmente ese stack para hacer posible la recursión completa.
  • Más adelante se agregó un stack por hardware en implementaciones de microprocesador para mejorar el rendimiento.

• Un usuario con larga experiencia en programación funcional comparte su preferencia por la recursión

  • Sabe cómo convertir algoritmos recursivos en iterativos, pero prefiere la recursión.
  • En la mayoría de los casos la recursión es lo bastante rápida, y más aún si el compilador soporta tail recursion.
  • Mientras hackeaba juegos de Commodore 64, intentó aprender cómo se programaba antes.

• Se comparte una experiencia de diseño de un multiplexor serial RS232 alrededor de 1991

  • Diseño de hardware con un procesador Z80, EPROM y un dispositivo serial Z80-SIO.
  • Como no había stack, se usaba un método de precargar direcciones de retorno en pares de registros para las llamadas a funciones.

• Mención de la situación pasada en la que, antes de que el heap pudiera expandirse, los programadores tenían que considerar la posible distribución de las entradas y ajustar apropiadamente el tamaño del almacenamiento intermedio

  • Esto provocaba "bugs y límites".

• Explicación de que en la época en que no se podía usar recursión, la tail recursion sí era posible

  • Aparte del branch_with_link usado en la llamada inicial, había que usar saltos normales.

• Explicación de cómo en Enhanced GNU Awk el compilador asigna variables globales secretas para bloques @let fuera de las funciones

  • Estas variables se reutilizan tanto como sea posible.

• Mención de una publicación que describe el mundo del artículo "Goto considered harmful"

  • La mayoría de la gente solo conoce el título, y el artículo argumenta a favor de proporcionar un único punto de entrada para las subrutinas.
  • A veces se escribe código ensamblador para saltar hacia otra subrutina, pero no se querría que todo el código ensamblador fuera así.