haskell - mac - Comprender STG
language haskell (4)
Desea leer el libro de SPJ sobre la implementación funcional de PL:
El diseño de GHC se basa en algo llamado STG, que significa "máquina de G sin espinas, sin etiquetas".
Ahora G-machine es aparentemente la abreviatura de "máquina de reducción de gráficos", que tiene cómo se implementa la pereza. Los thunks no evaluados se almacenan como un árbol de expresiones, y ejecutar el programa implica reducirlos a la forma normal. (Un árbol es un gráfico acíclico, pero la recursión generalizada de Haskell significa que las expresiones de Haskell forman gráficos generales, por lo tanto, reducción de gráficos y no reducción de árboles).
Lo que está menos claro son los términos "sin espinas" y "sin etiquetas".
Creo que "sin espinas" se refiere al hecho de que las aplicaciones de funciones no tienen un "lomo" de nodos de aplicación de funciones. En cambio, tiene un objeto que nombra la función llamada y apunta a todos sus argumentos. ¿Es eso correcto?
Pensé que "sin etiquetas" hacía referencia a que los nodos de constructor no estaban "etiquetados" con un ID de constructor, y en su lugar las expresiones de casos se resolvían con una instrucción de salto. Pero ahora no estoy seguro de que sea correcto. En cambio, parece referirse al hecho de que los nodos no están etiquetados con su estado de evaluación. ¿Alguien puede aclarar cuál (si alguna) de estas interpretaciones es correcta?
La wiki de GHC contiene un artículo introductorio sobre STG escrito por Max Bolingbroke:
Sé kung fu: aprender STG por ejemplo
La máquina STG es una parte esencial de GHC, el compilador Haskell líder en el mundo. Define cómo se debe implementar eficientemente el modelo de evaluación Haskell en hardware estándar. A pesar de este papel clave, en general no se entiende bien entre los usuarios de GHC. Este documento tiene como objetivo proporcionar una visión general de la máquina STG en su versión moderna, eval / apply, puntero etiquetado por una serie de ejemplos simples que muestran cómo se compila el código fuente de Haskell.
Tienes razón sobre el "sin espinas", eso es, si estoy en lo cierto. Se describe básicamente en el artículo de 1988 de Burn, Peyton-Jones y Robson, "The Spineless G-Machine". Lo he leído, pero no está tan fresco en mi mente. Básicamente, en la máquina G, todas las entradas de la pila apuntan a un nodo de la aplicación, excepto el que se encuentra en la parte superior, que apunta al encabezado de la expresión. Esos nodos de aplicación hacen que el acceso a los argumentos sea indirecto, y en algunas descripciones de G-Machine, antes de aplicar una función, la pila se reorganiza, de modo que los últimos n nodos en la pila apuntan al argumento en lugar del nodo de la aplicación. Si no me equivoco, la parte "sin espinas" se trata de evitar tener estos nodos de aplicación (que se llaman el lomo del gráfico) en la pila por completo, evitando así la reorganización antes de cada reducción.
En cuanto a la parte "sin etiqueta", ahora estás más correcto que antes, pero ... Usar etiquetas en los nodos es algo muy, muy viejo. ¿Puedes pensar en cómo se implementó un lenguaje de tipado dinámico como LISP? Cada celda debe tener su valor y una etiqueta que diga el tipo. Si quieres algo, debes examinar la etiqueta y actuar en consecuencia. En el caso de Haskell, el estado de evaluación es más importante que el tipo, Haskell está tipado estáticamente.
En la máquina STG, las etiquetas no se usan. Las etiquetas fueron reemplazadas, tal vez por inspiración de OO lanaguages, por un conjunto de indicadores de función. Cuando desee el valor de un nodo que no ha sido computado, la función lo calculará. Cuando ya está calculado, la función lo devuelve. Esto permite mucha creatividad en lo que esta función puede hacer sin hacer que el código del cliente sea más complejo.
Esta parte "Sin etiquetas" sí, se describe en el artículo "Implementación de lenguajes funcionales en hardware estándar" por SPJ.
También hay objeción a esta cosa "sin etiquetas". Básicamente, esto implica indicadores de función, que es un salto indirecto en términos de arquitectura informática. Y los saltos indirectos son un obstáculo para la predicción de bifurcación y, por lo tanto, para la canalización en general. Porque la arquitectura considera que hay una dependencia de datos en el argumento de salto, detener la interconexión, o la arquitectura supone que no conoce el destino y detiene la interconexión.
La respuesta de migle es exactamente lo que significa la ausencia de agujas y la ausencia de etiquetas del STGM. Hoy no vale la pena tratar de entender los nombres de las dos características porque los nombres provienen de la historia de las tecnologías de reducción de gráficos: de G-machine, Spineless G-machine y Spineless and Tagless G-machine.
La máquina G usa espinas y etiquetas. Un lomo es una lista de bordes desde el nodo raíz de una aplicación de función hasta el nodo de la función. Por ejemplo, una aplicación de función de "f e1 e2 ... en" se representa como
root = AP left_n en
left_n = AP left_n-1 en-1 ...
left_2 = AP left_1 e1
left_1 = FUN f
en G-machine, y por eso un spine es una lista de bordes que consta de left_n -> left_n-1 -> ... -> left_2 -> left_1. ¡Literalmente es un lomo de la aplicación de función!
En la misma aplicación de función, hay etiquetas AP y FUN.
En la próxima máquina G avanzada llamada máquina Spineless G, no existe tal espina dorsal al representar una aplicación de función de este tipo en un bloque contiguo cuya primera ranura apunta a f, la segunda ranura apunta a e1, ..., y la n +1-ésimo punto de ranura para en. En esta representación, no necesitamos una columna vertebral. Pero el bloque comienza una etiqueta especial que designa el número de ranuras y así sucesivamente.
En la máquina G más avanzada, llamada máquina rotativa sin etiqueta Spineless Tagless, dicha etiqueta se reemplaza con un puntero a la función. Evaluar una aplicación de función es saltar al código mediante el puntero de función.
Es lamentable encontrar que el documento STGM de Simone Peyton Jones no proporciona reglas de compilación / evaluación en un nivel abstracto, por lo que es muy natural que las personas no sean fáciles de entender la esencia del STGM.