¿Regresó alguna vez? No, nunca regresó,
y su destino aún no se ha aprendido,
puede cabalgar para siempre por las calles de Boston,
es el hombre que nunca regresó.
"Charlie en la MTA", 1949
1. Cierres
Una de las características útiles de los lenguajes de programación modernos son las funciones anidadas:
def bubble(arr, comp):
def swap(i, j):
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
flag = True
while flag:
flag = False
for i in range(len(arr) - 1):
if comp(arr[i], arr[i+1]) > 0:
swap(i, i+1)
flag = True
Esta posibilidad en sí no es nueva: ya estaba en Algol (1958) y es familiar para muchos de Pascal (1970). Compilar funciones anidadas es fácil: por ejemplo, el marco de pila de la función interna puede almacenar un puntero al marco de pila de la función externa para que la función interna pueda acceder a los parámetros y variables locales de la externa. Alguien puede recordar que las instrucciones
enter
y
leave
, que aparecieron en 80186 (1982), implementan exactamente este tipo de soporte para funciones anidadas (aunque nunca he visto ningún compilador que lo hiciera).
Las dificultades comienzan si el idioma te permite transferir una función interna fuera de una externa:
def by_field(name):
def comp(x, y):
return x[name] – y[name]
return comp
bubble(my_records, by_field("year"))
¿Cómo puede la función interna acceder a los parámetros y variables locales de la externa después de que el retorno de la función externa haya destruido su marco de pila? De alguna manera, la función interna tiene que "tomar" las variables utilizadas junto con ella; una función junto con variables capturadas externamente se denomina "cierre". Pascal ya no admite esto; pero por ejemplo, en C # 7 (2017), para esto, se crea un objeto en el heap, que contiene todos aquellos parámetros y variables locales a los que se refiere la función interna; y las llamadas tanto desde él como desde la función externa no van a los valores en la pila, sino a los campos del objeto en el montón. ¿Es posible prescindir de esta complicación y continuar trabajando con la pila, para evitar el direccionamiento indirecto innecesario y preservar la localidad de las llamadas, y no ensuciar la caché de datos con saltos en el montón?
2. Continuación del pase
Al compilar lenguajes de programación funcional, donde la captura de variables locales mediante una función de retorno es una técnica muy común, el primer paso es traducir todo el programa a un "estilo de paso de continuación" (CPS). los retornos de las funciones se reemplazan con una devolución de llamada explícita que se pasa a cada función como un argumento adicional. Por ejemplo, en esta función simple que calcula el producto de todos los números primos de 1 a
n
inclusive:
def prodprimes(n):
if n == 1:
return 1
elif isprime(n):
return n * prodprimes(n-1)
else:
return prodprimes(n-1)
-
prodprimes
Se transfieren implícitamente diferentes direcciones de retorno a dos llamadas . Si estas direcciones se designan como
j
y
h
, y la dirección de retorno se pasa como un argumento explícito
c
, entonces toda la transferencia de control puede hacerse explícita:
def prodprimes(n, c):
if n == 1:
c(1)
else:
def k(b):
if b:
def j(p):
c(n * p)
prodprimes(n-1, j)
else:
def h(q):
c(q)
prodprimes(n-1, h)
isprime(n, k)
En CPS, no hay diferencia entre llamar a una función y devolver un valor de una función; ambos se abstraen como "pasar un valor a una dirección específica". Esta técnica se ha utilizado en la mayoría de los compiladores de Scheme desde el primero (1975); se le dedica un libro completo "Compilación con continuaciones" (1992), de donde se toma el ejemplo anterior. Más recientemente, un estilo similar de programación se ha vuelto popular bajo el nombre de "promesas".
La razón por la que los compiladores utilizaron CPS internamente como una representación intermedia antes de la SSA(inventado en 1988) se ha vuelto más popular - simplicidad: este no es otro lenguaje con sus propias reglas, sino un sublenguaje del PL original con la restricción de que una función o llamada de continuación se permite solo como la última función o el operador de continuación. Es fácil traducir el código PL a CPS con un conjunto de transformaciones formales, y es fácil aplicar transformaciones simplificadoras al código CPS; por ejemplo, descubra que la continuación es
h
trivial y reemplace el uso
h
con
c
. Una característica importante de CPS para nosotros es que los cierres se utilizan en el mismo ámbito en el que se declararon y, por lo tanto, pueden acceder a las variables capturadas desde el exterior de la misma manera que en 80186, a través de punteros a marcos de pila externos:
def by_field(name, c):
def comp(x, y, c):
c(x[name] – y[name])
c(comp)
def by_year(comp):
bubble(my_records, comp, halt)
by_field("year", by_year)
Después de la conversión a CPS
comp
, sabe que ella misma es una función de anidamiento 2, y el valor se
name
encuentra en el marco de anidamiento 1, por lo que la compilación de la llamada a
name
no causará dificultades.
Pero CPS tiene un inconveniente: dado que las continuaciones nunca se ejecutan
return
entonces sus marcos de pila nunca se destruyen y la pila se desbordará muy rápidamente. Por otro lado, una continuación puede necesitar un determinado marco de pila, ya sea si ella misma se refiere a él, o si recibe como parámetro una continuación que hace referencia a este marco. Además, la transición a la siguiente continuación debe ser la última acción dentro de la continuación, de modo que la dirección y los parámetros de la siguiente continuación puedan considerarse el resultado de la continuación. (El modelo de "promesas" devuelve este resultado explícitamente). Los compiladores de Scheme clásicos usaban un despachador como el siguiente bucle infinito:
- Ejecute la continuación actual y obtenga la dirección y los parámetros de la siguiente continuación como resultado;
- Compruebe a qué marcos de pila se puede acceder mediante los siguientes parámetros de continuación y continuación que se le pasen;
- , .
Con esta implementación, la pila de llamadas del sistema no se usa y las transiciones entre el despachador y las continuaciones se implementan normalmente
jmp
. Los fotogramas de continuación se desacoplan de la pila de llamadas y se destruyen en orden aleatorio en lugar de LIFO , de modo que su colección se puede considerar tanto como una pila como como un montón.
Como puede adivinar, con una verificación de pila en cada rama entre continuación, el rendimiento del programa deja mucho que desear. Una de las posibles optimizaciones es comprobar el tamaño de la pila actual antes de salir de la continuación y, si no supera el umbral especificado, pasar directamente a la siguiente continuación; de lo contrario, transfiera el control al despachador para que recoja toda la basura de la pila. Graduado de Boston Henry Baker del MIT comentó sobre este enfoque: "en lugar de saltar en un trampolín todo el tiempo, saltamos del Empire State Building, pero con mucha menos frecuencia".
3. En MTA
En 1948, Boston Metro (Metropolitan Transit Authority) aumentó las tarifas de 10 centavos a 15 centavos. En lugar de reemplazar todas las monedas de diez centavos, en la entrada del metro, los conductores recibieron instrucciones de cobrar un recargo de cinco centavos al salir del tren. Burlándose de este enfoque, un candidato a la alcaldía de Boston ordenó la grabación de una canción sobre un tal Charlie, que no tenía suficiente centavo para pagar una salida, y estaba condenado a viajar en metro sin cesar. El candidato se ganó la reputación de comunista, obtuvo sólo el 1,2% de los votos en las elecciones y dejó la política para siempre; Pero la canción sobre el pasajero que nunca regresa a la superficie de la tierra resultó ser mucho más popular: incluso la tarjeta del metro de Boston, presentada en 2006, se llama CharlieCard en honor a ese mismo pasajero.
La historia de Charlie inspiró a Henry Baker a escribir un compilador de Scheme en 1994 que convierte cada continuación en una función C para que la ejecución de esas funciones nunca llegue
return
: por ejemplo,
(define (revappend old new)
(if (null? old)
new
(revappend (cdr old) (cons (car old) new))))
- se convierte en
void revappend(clos_type *cont, cons_type *old, cons_type *new) {
if (old == NIL) {
/* Call continuation with new as result. */
return (cont->fn)(cont->env, new);
}
cons_type newer; /* Should check stack here. */
/* Code for (revappend (cdr old) (cons (car old) new)). */
newer.tag = cons_tag; newer.car = old->car; newer.cdr = new;
return revappend(cont, old->cdr, &newer);
}
El significado del operador
return
después de tal conversión es decirle al compilador de C que no es necesario guardar los registros antes de llamar a la continuación; de hecho, una función llamada como operando
return
nunca regresará. En el lugar marcado como
/* Should check stack here. */
, se inserta una verificación del tamaño de la pila y, si es necesario, se llama al despachador para la recolección de basura.
Este enfoque tiene varias ventajas sobre el clásico:
- Scheme : ; – , .. (varargs); – , .. (VLA). 21 . LLVM, .
- ABI – , Scheme. «» , CPS, . «» callback- «» , , , «» – , . Scheme,
map
fold
, , .
Por otro lado, C no admite funciones anidadas, lo que significa que todos los punteros a variables capturadas desde el exterior deben pasarse explícitamente junto con el cierre. Además, al colocar fotogramas de continuación en la pila del sistema en lugar de uno escrito por uno mismo, surge una dificultad: ¿cómo implementar la recolección de basura para la pila del sistema, que no está vinculada al dispositivo de un compilador C específico en una arquitectura específica?
4. El recolector de basura de Cheney
El primer y más simple recolector de basura se implementó en 1969 para LISP: cuando la mitad del montón estaba llena, el programa se detuvo y todos los datos "en vivo" se transfirieron de forma recursiva (primer recorrido en profundidad) a la segunda mitad del montón. En 1970, Chris Cheney, también en Cambridge, pero al otro lado del océano desde el MIT, notó que al atravesar los datos en vivo a lo ancho, el colector en sí no necesitaría memoria adicional durante la construcción; desde entonces, la recolección de basura con detener el programa y mover objetos activos a la segunda mitad del montón se ha llamado el "algoritmo de Cheney". Su principal inconveniente es que los datos en vivo pueden ocupar solo la mitad de la memoria disponible, y la segunda mitad está ocupada por un "búfer para copiar".
La eficiencia de la recolección de basura se puede mejorar si se observa que los datos de un programa típico se dividen en "de muy corta duración" y "de muy larga duración": si un objeto sobrevivió a una recolección de basura, es muy probable que sobreviva a la siguiente. colección también. Por lo tanto, el montón se divide en una "guardería" para los objetos recién creados y un "montón de adultos" de dos mitades. Cuando el vivero se llena, los datos en vivo se transfieren al montón de adultos; cuando la mitad del montón de adultos se desborda, los datos en vivo se transfieren a la otra mitad. Esto ahorra memoria (no se reserva espacio para datos de corta duración en la segunda mitad del montón) y tiempo de construcción (los datos de larga duración no se copian de un lado a otro con cada recolección de basura en el vivero).
Cuando se usa "Cheney en el MTA", la pila actúa como un criadero. El despachador llamado en el desbordamiento de pila recibe explícitamente como parámetros punteros a todos los datos en vivo: estos son todos los parámetros y variables locales de la continuación de la llamada, incluidas las variables capturadas pasadas a la continuación como un parámetro implícito. A diferencia de los recolectores de basura tradicionales, Cheney en el MTA no necesita buscar datos en vivo dentro de la pila: CPS asegura que todos los datos debajo del último marco de la pila estén muertos si no están disponibles en el último marco. Esto significa que al recolector de basura no le importa la estructura de los marcos de la pila, ni la posible presencia de marcos "extraños" en la pila, que quedan de funciones en otros idiomas.
El enfoque "Cheney en el MTA" se utiliza en los compiladores del esquema C "Chicken Scheme" (2000) y "Cyclone Scheme" (2016). En Cyclone, a la idea de Baker desde hace mucho tiempo, agregaron soporte para la recolección de basura paralela, cuando solo un hilo se detiene durante la recolección, cuya pila se está procesando, y el resto continúa funcionando.
