¿Cuál es el propósito de una pila? ¿Por qué lo necesitamos?

ACTUALIZACIÓN: Me gustó tanto esta pregunta que la hice el tema de mi blog el 18 de noviembre de 2011. Gracias por la gran pregunta!

Siempre me he preguntado: ¿cuál es el propósito de la pila?

Asumo que te refieres a la pila de evaluación del lenguaje MSIL, y no a la pila real por hilo en tiempo de ejecución.

¿Por qué hay una transferencia de memoria a pila o "carga"?"Por otro lado, ¿por qué hay una transferencia de pila a ¿memoria o "almacenamiento"? ¿Por qué no guardarlas todas en la memoria?

MSIL es un lenguaje de "máquina virtual". Compiladores como el compilador C# generan CIL, y luego en tiempo de ejecución otro compilador llamado JIT (Just In Time) convierte el IL en código máquina real que puede ejecutarse.

Así que primero vamos a responder a la pregunta "¿por qué tener MSIL en absoluto?"¿Por qué no hacer que el compilador de C# escriba el código de máquina?

Porque es más barato hacerlo por aquí. Supongamos que no lo hicimos de esa manera; supongamos que cada lenguaje tiene que tener su propio generador de código máquina. Tiene veinte diferentes lenguajes: C#, JScript .NET, Visual Basic, IronPython, F#... Y supongamos que tiene diez procesadores diferentes. ¿Cuántos generadores de código tienes que escribir? 20 x 10 = 200 generadores de código. Eso es mucho trabajo. Ahora supongamos que desea agregar un nuevo procesador. Tienes que escribir el generador de código para ello veinte veces, una para cada idioma.

Además, es un trabajo difícil y peligroso. ¡Escribir generadores de código eficientes para chips en los que no eres un experto es un trabajo duro! Los diseñadores de compiladores son expertos en el análisis semántico de su lenguaje, no en la asignación eficiente de registros de nuevos conjuntos de chips.

Ahora supongamos que lo hacemos de la manera CIL. ¿Cuántos generadores CIL tienes que escribir? Uno por idioma. ¿Cuántos compiladores JIT tienes que escribir? Uno por procesador. Total: 20 + 10 = 30 generadores de código. Además, el generador de lenguaje a CIL es fácil de escribir porque CIL es un lenguaje simple, y el generador de código de CIL a máquina también es fácil de escribir porque CIL es un lenguaje simple. Nos deshacemos de todas las complejidades de C# y VB y otras cosas y "menor" todo a un lenguaje simple que es fácil escribir un jitter para.

Tener un lenguaje intermedio reduce el costo de producir un nuevo compilador de lenguaje dramáticamente. También reduce el costo de soportar un nuevo chip dramáticamente. Si quieres dar soporte a un nuevo chip, encuentras a algunos expertos en ese chip y les haces escribir un CIL jitter y ya está; entonces das soporte a todos esos idiomas en tu chip.

Bien, así que hemos establecido por qué tenemos MSIL; porque tener un lenguaje intermedio reduce los costos. ¿Por qué entonces el lenguaje es una "máquina de pila"?

Porque las máquinas de pila son conceptualmente muy simples para que los escritores de compiladores de lenguaje las traten. Las pilas son un mecanismo simple y fácil de entender para describiendo cálculos. Las máquinas de pila también son conceptualmente muy fáciles de manejar para los escritores de compiladores JIT. Usar una pila es una abstracción simplificadora, y por lo tanto nuevamente, reduce nuestros costos.

Usted pregunta "¿por qué tener una pila en absoluto?"¿Por qué no hacer todo directamente de memoria? Bueno, pensemos en eso. Supongamos que desea generar código CIL para:

int x = A() + B() + C() + 10;

Supongamos que tenemos la convención de que" add"," call"," store " y así sucesivamente siempre quitan sus argumentos la pila y poner su resultado (si hay uno) en la pila. Para generar código CIL para este C# simplemente decimos algo como:

load the address of x // The stack now contains address of x
call A()              // The stack contains address of x and result of A()
call B()              // Address of x, result of A(), result of B()
add                   // Address of x, result of A() + B()
call C()              // Address of x, result of A() + B(), result of C()
add                   // Address of x, result of A() + B() + C()
load 10               // Address of x, result of A() + B() + C(), 10
add                   // Address of x, result of A() + B() + C() + 10
store in address      // The result is now stored in x, and the stack is empty.

Ahora supongamos que lo hicimos sin una pila. Lo haremos a tu manera, donde cada opcode toma las direcciones de sus operandos y la dirección a la que almacena su resultado :

Allocate temporary store T1 for result of A()
Call A() with the address of T1
Allocate temporary store T2 for result of B()
Call B() with the address of T2
Allocate temporary store T3 for the result of the first addition
Add contents of T1 to T2, then store the result into the address of T3
Allocate temporary store T4 for the result of C()
Call C() with the address of T4
Allocate temporary store T5 for result of the second addition
...

¿Ves cómo va esto? Nuestro código se está volviendo enorme porque tenemos que asignar explícitamente todo el almacenamiento temporal que normalmente convención simplemente ir en la pila . Peor aún, nuestros propios opcodes se están volviendo enormes porque ahora todos tienen que tomar como argumento la dirección en la que van a escribir su resultado y la dirección de cada operando. Una instrucción " add " que sabe que va a tomar dos cosas de la pila y poner una cosa puede ser un solo byte. Una instrucción add que toma dos direcciones de operando y una dirección de resultado va a ser enorme.

Usamos opcodes basados en pila porque las pilas resuelven el problema común. A saber: Quiero asignar algo de almacenamiento temporal, usarlo muy pronto y luego deshacerse de él rápidamente cuando haya terminado. Al asumir que tenemos una pila a nuestra disposición podemos hacer que los opcodes sean muy pequeños y el código muy conciso.

ACTUALIZACIÓN: Algunos pensamientos adicionales

Por cierto, esta idea de reducir drásticamente los costos al (1) especificar una máquina virtual, (2) escribir compiladores que se dirijan al lenguaje de VM, y (3) escribir implementaciones de la VM en una variedad de hardware, no es una idea nueva en absoluto. No se originó con MSIL, LLVM, Java bytecode, o cualquier otra infraestructura moderna. La implementación más temprana de esta estrategia que conozco es la máquina pcode de 1966.

La primera vez que escuché personalmente de este concepto fue cuando aprendí cómo los implementadores de Infocom lograron que Zork se ejecutara en tantas máquinas diferentes tan bien. Especificaron un virtual machine llamó a Z-machine y luego hizo emuladores de Z-machine para todo el hardware en el que querían ejecutar sus juegos. Esto tenía el enorme beneficio añadido de que podían implementar virtual memory management en sistemas primitivos de 8 bits; un juego podía ser más grande de lo que cabía en la memoria porque podían simplemente enviar el código desde el disco cuando lo necesitaban y descartarlo cuando necesitaban cargar nuevo código.