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

 (devblogs.microsoft.com)
2 puntos por GN⁺ 2024-04-04 | 1 comentarios | Compartir por WhatsApp
  • Las primeras computadoras tenían que implementar llamadas a funciones sin stack ni heap, y el compilador administraba el estado de la llamada con variables globales ocultas que correspondían a parámetros, direcciones de retorno y variables locales
  • Quien llamaba guardaba los argumentos, colocaba la posición de regreso en una variable de dirección de retorno y luego saltaba al punto de entrada de la función; la función, tras hacer el cálculo, volvía a saltar a la dirección guardada
  • Incluso las variables locales lógicas usaban en realidad almacenamiento global, así que, aunque por fuera parecían funciones, por dentro se comportaban más como memoria fija y goto
  • Algunos ABI y procesadores optimizaban el paso de argumentos y el manejo de la dirección de retorno con registros o branch with link, pero la limitación básica seguía ahí
  • Como la dirección de retorno de una misma función era sobrescrita por una nueva llamada, la recursión era imposible, y los lenguajes de la época respondían prohibiéndola o permitiéndola solo de forma explícita

Cómo construir llamadas a funciones sin stack

  • En los primeros entornos de cómputo no existían ni el stack ni el heap que hoy damos por sentados
  • La asignación dinámica de memoria sin heap podía sustituirse por búferes de tamaño fijo
    • Incluso al procesar datos de tamaño variable, se reservaba por adelantado un búfer fijo lo bastante grande
    • Si los datos solicitados excedían la capacidad del búfer, el programa terminaba con un error fatal
    • Una implementación más amable permitía configurar la capacidad máxima en tiempo de compilación
    • Una implementación más sofisticada podía poner un asignador personalizado sobre el búfer fijo y usarlo como allocate y free

Convención de llamada basada en variables globales ocultas

  • Para implementar llamadas a funciones sin stack, el compilador definía varias variables globales ocultas para cada función
    • una variable global por cada parámetro de entrada
    • una variable global para guardar la dirección de retorno de la función
    • variables globales correspondientes a las variables locales
  • El código de llamada se ejecutaba en el siguiente orden
    • guardar los valores de los parámetros en sus variables globales ocultas correspondientes
    • registrar la posición de regreso en la variable de dirección de retorno de la función
    • hacer un salto goto al punto de inicio de la función
  • La función leía y escribía tanto los parámetros como las variables locales desde esas variables globales ocultas
  • Al terminar, colocaba el valor de retorno en el registro de valor de retorno y saltaba a la dirección almacenada en la variable de dirección de retorno de la función

Ejemplo de cómo un código parecido a C se transforma en código basado en goto

  • La función de ejemplo add_two_values(int a, int b) podía transformarse sin stack en espacios de almacenamiento como los siguientes
    • a2v_a y a2v_b son variables globales para guardar los argumentos
    • a2v_c es la variable global correspondiente a la variable local c
    • a2v_retaddr es la variable global para guardar la dirección de retorno
  • Quien llama, sample(), guarda 31415 y 2718 respectivamente en las variables globales de argumentos
  • Luego coloca la posición resume en a2v_retaddr y salta a add_two_values
  • add_two_values guarda el resultado del cálculo en return_value_register y luego regresa mediante a2v_retaddr
  • De vuelta en la posición resume, quien llama guarda el valor del registro de retorno en sample_x

Optimización con registros y branch with link

  • La misma estructura podía hacerse más rápida a nivel ABI mediante paso por registros
  • Muchos procesadores ofrecían un link register especial y la instrucción branch with link
    • branch with link guarda automáticamente en el link register la dirección de la instrucción siguiente a la instrucción de bifurcación
    • Quien llama puede poner los dos primeros argumentos en argument_register_1 y argument_register_2
    • La función llamada puede mover los valores de esos registros a sus propias variables globales ocultas para usarlos
  • La dirección de retorno también podía guardarse desde link_register en la variable de dirección de retorno de la función
  • Esta optimización mantenía la estructura básica de que las llamadas y los retornos podían hacerse sin stack

Por qué la recursión quedaba bloqueada

  • La restricción central de este esquema de llamadas es la imposibilidad de recursión
  • Si ocurría una llamada recursiva, la variable de dirección de retorno de esa misma función era sobrescrita con la dirección de retorno de la nueva llamada
  • Cuando terminaba la llamada externa, la posición original a la que debía volver ya había desaparecido, y se terminaba saltando a un lugar incorrecto
  • Los lenguajes de programación de la época evitaban este problema al no admitir recursión
  • FORTRAN al principio ni siquiera admitía subrutinas, y estas se agregaron en 1958
  • El soporte de recursión no se volvió estándar en FORTRAN hasta 1991, e incluso entonces había que declarar la subrutina como RECURSIVE

Código automodificable y las instrucciones de subrutina en los primeros procesadores

  • Algunos compiladores usaban de forma aún más ingeniosa código automodificable
    • el campo de dirección dentro de la instrucción de salto al final de la función actuaba en la práctica como variable de dirección de retorno
  • Este método no era solo un truco simple, sino que podía ser una necesidad práctica
    • algunos procesadores podían no admitir saltos indirectos
  • Una vez reconocida la utilidad práctica de las subrutinas, varios procesadores añadieron instrucciones dedicadas de llamada
    • guardaban la dirección de retorno en la primera palabra de la subrutina
    • la ejecución real comenzaba en la segunda palabra
    • al regresar, ejecutaban un salto indirecto mediante la etiqueta de inicio de la subrutina
  • En el ejemplo de ensamblador, bsr add_two_values guarda la dirección de retorno en la primera palabra de add_two_values y empieza a ejecutar desde la instrucción real después del nop de sacrificio

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-04-04
Opiniones de Hacker News

  • En este tema, The Art of Computer Programming fue realmente muy bueno
    A primera vista parece anticuado, pero contiene una enorme cantidad de algoritmos para manejar arreglos o estructuras de datos que cambian dinámicamente, de la época anterior al heap o al stack
    El libro avanza paso a paso hasta la recolección de basura y la implementación de listas de Lisp, e incluye exactamente ese conocimiento enciclopédico que uno espera de Knuth
    Un ejemplo que me gusta especialmente es la forma en que dos arreglos comparten dinámicamente un mismo espacio. Si un arreglo crece hacia adelante desde location#0 y el segundo crece hacia atrás desde location#End, se puede dividir eficientemente un espacio asignado de forma estática
    También se puede extender a un número arbitrario de arreglos, pero llegado a ese punto conviene más usar Malloc y Realloc, y la técnica en sí ya se parece bastante a una rutina tipo malloc

    • Algunos procesadores de texto de computadoras de 8 bits funcionaban así. El documento ocupaba toda la RAM disponible: el texto antes del cursor estaba al inicio de la RAM, y el texto después del cursor estaba al final
      Insertar y pegar no requería desplazar datos, pero moverse por el texto sí. Aun así, funcionaba bien
    • En la mayoría de las arquitecturas de conjuntos de instrucciones y ABI, el stack crece hacia abajo desde direcciones altas, así que en sistemas de memoria pequeños de un solo hilo esta técnica permitía repartir de forma flexible la memoria entre el heap y el stack
    • La asignación de recursos por aplicación en el MacOS antiguo se explica exactamente de esta manera. Cada app tenía asociado un requisito mínimo de RAM y una cantidad preferida de RAM, y al ejecutarse ocupaba un slot del tamaño preferido
      Si no había tanto disponible, se le asignaba menos que lo preferido; si ni siquiera podía obtener el mínimo, fallaba al ejecutarse
      Recuerdo que el sistema colocaba el heap y las bibliotecas en la parte inferior de ese fragmento de RAM física, y el stack en la parte superior
      Alrededor de System 8 se agregó una capa de virtualización, con lo que este enfoque se volvió menos necesario, y para la época de MacOS X, al usar memoria paginada como otros sistemas, estos trucos ya no hacían falta
      Aun así, es divertido pensar en una época en la que este “truco raro” de Art of Computer Programming era la forma de asignar RAM a varias apps ejecutándose al mismo tiempo
    • Como dato curioso, Itanium tenía dos stacks en total: uno para push/pop manual y otro que hacía rotar el archivo de registros
      Uno crecía hacia arriba y el otro hacia abajo. Era una estructura fascinante, pero al final no logró entregar el rendimiento prometido
    • El formato en disco de SQLite también usa una técnica de arreglos similar al almacenar el contenido de las páginas de nodos hoja de B-tree de una tabla
      Dentro de una página de tamaño fijo, el arreglo de offsets crece hacia adelante y el arreglo de valores de filas de longitud variable crece hacia atrás desde el final. Según entiendo, al eliminar filas pueden quedar huecos en el arreglo de atrás
      Como la documentación cita a TAOCP para la propia estructura B-tree, no me sorprendería que hubiera sido una inspiración directa

  • Incorporar funciones recursivas en ALGOL fue bastante polémico y sigue siendo una historia interesante: https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...

  • Escribí un intérprete de Forth para una máquina SUBLEQ (https://github.com/howerj/subleq) y un intérprete para una máquina bit-serial (https://github.com/howerj/bit-serial); ninguno de los dos tenía la pila de llamadas a funciones que Forth necesita.
    SUBLEQ tampoco permite cargas/almacenamientos indirectos, así que para hacer cualquier cosa mínimamente compleja se necesita código automodificable.
    El enfoque fue crear en ambas máquinas una máquina virtual que pudiera realizar esas funciones, e incorporar también multithreading cooperativo.
    Si hace falta un heap, se escribe en Forth, y el conjunto de palabras de punto flotante también se escribe en Forth. Muchos MCU todavía no tienen instrucciones de punto flotante, y eso puede manejarse con llamadas a funciones de software que lo implementen.
    Aunque no se mencionen, supongo que otros compiladores usaron enfoques similares. Algunos intérpretes de BASIC también implementaban una VM y luego la usaban como destino, y P-Code es parecido.

    • La TI-99/4A tenía solo 256 bytes, es decir 128 palabras, de RAM principal directamente accesible por la CPU.
      La mayor parte de la memoria básica del sistema era RAM de video, y había que acceder a ella mediante un procedimiento bastante engorroso de poke/peek a los registros del chip de video.
      El chip de video mantenía un puntero de memoria actual con autoincremento, de modo que en lecturas o escrituras consecutivas el puntero aumentaba de a 1, pero el solo hecho de que la mayor parte de la memoria del sistema solo fuera accesible de esta forma hacía difícil escribir programas grandes.
      Por eso TI creó una máquina abstracta llamada GPL, que hacía más natural este acceso a la RAM de video. Sin embargo, al ejecutarse interpretada sobre el TMS9900, era más lenta que el código nativo, y además la CPU solo podía acceder a la RAM del chip de video en momentos en que el chip no estuviera haciendo el barrido de la pantalla, como durante el retorno horizontal/vertical, así que era todavía más lenta.
      Como el código BASIC y las variables también estaban por completo en esta memoria de video, es bastante obvio en qué estaba escrito el intérprete de BASIC de la TI-99/4A. No era nada rápido.
      Lo interesante es que el TMS9900 no tenía registros de propósito general reales. Los registros de espacio de trabajo WR0~WR15 estaban en algún lugar de la memoria, y el registro puntero de espacio de trabajo WP apuntaba a ellos.
      Los únicos registros físicos de la CPU eran PC, WP y el registro de estado. En consecuencia, se podía hacer una forma muy primitiva de ventaneo de registros, y al bifurcar con la instrucción BLWP se activaba un nuevo conjunto de “registros” en otra ubicación de memoria, mientras la dirección de retorno se guardaba en el nuevo espacio de trabajo.
      Últimamente hablo seguido de la TI-99/4A porque, como proyecto personal, estoy haciendo un ensamblador para esta máquina.
    • Vi esos trabajos mientras aprendía y profundizaba en Forth y Subleq. Me gustó leer el enfoque, y quise comprar el libro, pero Amazon dice que no se puede. Me pregunto si habrá una reimpresión.
    • Iba a hablar de subleq, pero ahí hasta escribir un “Hello world” es realmente difícil.

  • Es cierto que algunos procesadores guardaban la dirección de retorno en la palabra inmediatamente anterior a la primera instrucción de la subrutina, y el PDP-8 hacía eso.
    La evolución del PDP-8 también puede verse como un viaje hacia el soporte de hardware para la recursión.
    Al principio, la instrucción JMS incrustaba la dirección de retorno en la primera palabra de la función. A menudo el llamador ponía los argumentos después de la instrucción JMS, y el llamado leía los argumentos con offsets respecto de la instrucción de retorno, incrementándola cada vez para que la dirección de retorno volviera a apuntar a una ubicación de código.
    Más adelante se volvió bastante común crear una pila simple usando una de las ubicaciones de autoincremento. El PDP-8 tenía ocho ubicaciones de memoria que se incrementaban cada vez que se usaban como punteros, y el prólogo/epílogo de la función gestionaba directamente esta pila, lo que hacía posible la recursión completa.
    Más tarde aún, implementaciones en microprocesador como el Harris 6120 agregaron una pila de hardware, lo que mejoró el rendimiento.

    • La Librascope LGP-30 de 1956 tenía la instrucción R, es decir, una instrucción para guardar la dirección de retorno.
      Esta instrucción guardaba el PC+1 ya incrementado en la parte de dirección de instrucción de la ubicación destino, y por convención ese destino era una instrucción de salto incondicional justo antes del inicio de la subrutina.
      Después de la instrucción R se ponía una instrucción U de salto incondicional hacia la subrutina correspondiente.
      La subrutina retornaba saltando a la dirección que estaba justo antes de ella, donde había un salto incondicional de vuelta a lo que seguía inmediatamente al punto de llamada.
      La recursión era imposible salvo que se usara una convención de llamada más avanzada. Y todos los códigos de instrucción del lenguaje ensamblador eran de una sola letra.
    • IBM 1800, IBM 1130 y muchas máquinas de esa época también hacían eso. Las máquinas con suficientes registros, como la serie Xerox Sigma, podían evitar esta práctica.

  • En programas escritos para AVR-8, usar la convención de llamada de C a veces se siente como una locura.
    Si usas ensamblador, puedes mantener las variables del bucle interno dentro del gran archivo de registros, o puedes usar los métodos descritos en el artículo.
    También me gusta la forma de “colorear” funciones en este tipo de apps. Si sabes que una función roja y una función verde no estarán activas al mismo tiempo, puedes reutilizar sus variables locales o parámetros.

    • Al trabajar en entornos restringidos, especialmente si uno está acostumbrado a las comodidades de los sistemas operativos de escritorio, el uso de pila de C puede no resultar intuitivo.
      En un proyecto de una base de código para microcontrolador al que me sumé hace tiempo, varios desarrolladores llevaban semanas rastreando bugs difíciles de atrapar en varios subsistemas.
      Si movían el código, el bug también se movía con él. Tras investigar un poco y poner trampas, se pudieron encontrar puntos del código donde la pila de llamadas crecía demasiado y sobrescribía otras estructuras de datos.

  • Cuando aprendí a programar por primera vez, me obligaron a programar exactamente de esta manera. No fue en los años 70, sino en 2001
    Porque mi primera experiencia de programación fue con el “lenguaje” de scripting semigráfico que ofrecía la herramienta de desarrollo de juegos RPG Maker 2000
    Si nunca viste el scripting de RM2K, imagina una mezcla entre Scratch y el modo Paredit de Emacs. Ej.: https://forums.rpgmakerweb.com/data/attachments/21/21958-f89...
    Parece texto, pero no se puede editar como texto; solo se edita como bloques con cuadros de diálogo de propiedades
    Por supuesto, el lenguaje de scripting de RPG Maker no tenía cosas elegantes como una pila. Si necesitabas una subrutina reutilizable, tenías que asignar variables globales secretas para los parámetros, y no había reentrancia
    Viéndolo en retrospectiva, creo que, con suficiente terquedad, se podrían haber implementado tanto registros como una pila de ejecución dentro de RPG Maker 2000
    Al principio parece fácil. Puedes crear “registros” falsos como la zero page del 6502, y también una pila usando acceso indirecto a variables (https://rpgmaker.net/tutorials/523/)
    El problema es que RM2K tiene concurrencia en forma de scripts de “parallel process”. Si los procesos paralelos usan estas abstracciones, distintos “hilos” se pisan el estado unos a otros
    Por lo tanto, necesitas varias zero pages y pilas por cada “núcleo virtual”, y tienes que asignar/vincular/planificar núcleos virtuales para cada script paralelo. Es decir, de algún modo cada script debe tener un puntero de pila que solo él conozca
    Para que sea estable incluso con condiciones de carrera, normalmente necesitarías algo como un mutex
    Conociendo la obsesión de los desarrolladores de juegos en RPG Maker, sospecho que alguien habrá encontrado una forma de engañar a alguna función del runtime para que se comporte como un mutex, pero sinceramente me da miedo saber qué hicieron en realidad

    • Yo también empecé con rpgmaker, y leer esto me da muchísima nostalgia
      Recuerdo haber descargado de rpgmaker.net un juego con un custom battle system implementado. Era una implementación que reemplazaba por completo el sistema de combate integrado usando técnicas como las que describiste
      Cuando lo abrí en el editor para ver cómo funcionaba, quedé totalmente abrumado. Había cientos de “variables”, y si no recuerdo mal solo permitían i64, además de cientos de “interruptores”. Los interruptores eran booleanos
      En ese momento no tenía ningún concepto de pila, heap ni llamadas a funciones
      No puedo ni imaginar la cantidad de energía que habrá requerido construirlo y mantenerlo/depurarlo

  • Si no recuerdo mal, cuando escribía programas BASIC en la ZX81, lo hacía de una forma cercana a “sin pila”
    1 GOTO 30
    10 LET C = A + B
    20 RETURN
    30 LET A = 1
    40 LET B = 2
    50 GOSUB 10
    60 LET A = C
    70 LET B = 3
    80 GOSUB 10
    90 PRINT C
    RUN
    6
    En cierto modo, estaba haciendo yo mismo lo que el compilador hace en el artículo. Los números de línea eran direcciones de memoria, y las variables ocultas no estaban ocultas para mí. Porque yo era el compilador
    Lo único que hacía el intérprete era guardar la dirección de retorno de GOSUB
    Eso sí, el código podría estar sintácticamente mal, o mi memoria podría estar distorsionada. Cuarenta años es mucho tiempo, pero la idea general es correcta
    Además, el procesador Z80 dentro de la máquina sí tenía funciones de gestión de pila. El intérprete BASIC era realmente simple, pero tenía excusa: solo había 1 KB de RAM y 8 KB de ROM para el SO, el intérprete y todo lo demás

    • Aun así, eso usa al menos una pila de llamadas. GOSUB guarda el número de línea u otra referencia que RETURN consultará, y si anidas llamadas a GOSUB, tiene que recordar varios puntos de retorno, así que necesita algún tipo de pila
      Solo que algunos BASIC, en lugar de una pila de propósito general, tenían un arreglo fijo de punteros de retorno y un índice de posición actual, de modo que, por ejemplo, la profundidad de llamada quedaba fija en 7. Para el programador, se comportaba como una pila de llamadas
      Por supuesto, no era una pila “de verdad” con variables locales/parámetros, como uno esperaría al oír la palabra pila
      En el entorno básico de BBC BASIC se podía hacer una demo divertida que mostraba qué pasaba durante llamadas anidadas, incluida la recursión. Si ubicabas la pila en la parte superior de la memoria de pantalla y evitabas dibujar ahí, podías ver cómo la pila crecía a medida que avanzaba el trabajo
      Como la resolución de pantalla era baja, los 2 bytes de una dirección de retorno se veían como 8 píxeles gruesos en los modos de pantalla 1 o 5. En el modo 2 eran 4, pero con colores parpadeantes y quedaba peor; en los modos 0, 3, 4 y 6 eran 16, pero verlos a nivel de bits era más difícil de distinguir que una repetición de 8 colores

  • Antes de que existiera un heap ampliable arbitrariamente, los programadores aplicaban al menos algo de criterio de ingeniería
    Porque tenían que considerar la distribución probabilística de las entradas y dimensionar adecuadamente todo el almacenamiento intermedio
    Así nacieron las secciones de “BUGS AND LIMITATIONS”

    • Esa forma antigua de hacer las cosas sigue vigente hoy, dependiendo de lo que hagas. En hard real-time casi no se usa memoria dinámica, principalmente porque el tiempo de asignación/liberación de memoria no es determinista
      Por eso todo se asigna estáticamente en tiempo de compilación, y tienes que saber cuánta memoria van a consumir las entradas
      Pero conocer el límite superior del consumo de memoria también solía ser algo normal para los programadores de aplicaciones. Porque nunca quieres quedarte sin memoria
      Hoy en día parece que simplemente dejamos el uso de memoria en modo YOLO
    • Históricamente, uno de los grandes objetivos de GNU también fue eso. Querían eliminar las limitaciones artificiales de las utilidades centrales
      Por ejemplo, fue una gran mejora frente a restricciones como que la longitud máxima de los comandos de sed fuera finita y corta
    • En realidad, el error fue dejar que los humanos proporcionaran entradas a los programas de computadora

  • Llevo tanto tiempo haciendo programación funcional que, sinceramente, me cuesta imaginar cómo escribir código sin recursión
    Técnicamente sé cómo convertir algoritmos recursivos en algoritmos iterativos, y también lo he hecho en entornos con muchas restricciones de recursos, pero no me gusta
    Por lo general, la versión recursiva es más elegante y, en el 99% de los casos, me parece suficientemente rápida. Si el compilador soporta recursión de cola, se acerca al 100%, aunque en la mayoría de los trabajos más interesantes de todos modos hay que mantener la pila manualmente
    A veces hago ese tipo de cosas a propósito para aprender cómo se hacía antes de que yo naciera. De vez en cuando trasteo con juegos de Commodore 64, y eso me hace sentir con fuerza el lujo que es estar acostumbrado hoy a hardware rápido, barato y fácil de usar

    • Los conjuntos de instrucciones de hoy definitivamente son mucho más útiles
      Para hacer recursión en esas máquinas antiguas había que construir uno mismo el mecanismo de pila, y aun así seguían quedando problemas por resolver porque, básicamente, no había otra forma disponible más que el almacenamiento global
      Viví esa época, pero no se la recomendaría a nadie

  • En la función @let de Enhanced GNU Awk, para los bloques @let fuera de una función, por ejemplo dentro de bloques BEGIN o END, hice que el compilador asignara variables globales secretas
    Estas variables se reutilizan entre bloques tanto como sea posible
    $ ./gawk --dump-variables 'BEGIN { @let (a, b, c = 1) { } }'
    $ cat awkvars.out
    $let0001: untyped variable
    $let0002: untyped variable
    $let0003: 1
    ARGC: 1
    ARGIND: 0
    ARGV: array, 1 elements
    BINMODE: 0
    [ .. snip many ]
    https://www.kylheku.com/cgit/egawk/about/

    • Ese sitio web no funciona desde mi ISP. Ni ping funciona, ni nc -z 104.37.63.7 443
      Actualización: parece que la infraestructura de seguridad está rota. No sé ni qué es eso y tampoco uso Twitter. Al revisar el AS, es Google Fiber
      Y preferiría que no me doxearan