¿Cómo funciona un compilador de Haskell?

Question

¿Dónde puedo conseguir un poco de papel / doc / lo que sea que describe cómo un compilador de Haskell realmente funciona? He leído un buen número de los documentos de GHC, pero se detuvo después de conseguir un dolor de cabeza. Por lo tanto, algo que no requiere un doctorado para entenderlo y no está escrito en la supuesta Está usted-a-ser--ya familiar-con-estilo que sería preferible. No es un problema si es muy largo y toma algún tiempo para entender que aunque.

PS:. Lo más interesante sería algo acerca de GHC, pero nada está bien

Answer 1

Puede obtener una respuesta de la boca del caballo! Simon Peyton Jones (asistente GHC) escribió un libro que explica cómo implementar lenguajes de programación funcionales. Está disponible de forma gratuita en línea, ya que es ahora fuera de impresión: http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/

Por supuesto, GHC ha pasado desde que el libro fue escrito, pero sigue siendo muy relevante.

Answer 2

¿Usted está buscando detalles en especial sobre la compilación perezoso-evaluación? No es el libro de Simon Peyton-Jones mencionado por Max Bolingbroke, también el libro que detalla la implementación de Clean está en línea:

http://wiki.clean.cs.ru.nl/Functional_Programming_and_Parallel_Graph_Rewriting

Si usted tiene una afiliación universitaria y quiere algo más pequeño que podría tratar de conseguir estos libros (Henderson & Diller son sin duda fuera de impresión):

Antoni Diller "Compilación de función" Idiomas ISBN 0 471 92027 4

Peter Henderson "Aplicación programación funcional e Implementación" ISBN 0-13-331579-7

AJT Davie "Una introducción a la programación funcional Sistemas utilizando Haskell" ISBN 0 521 27724 8

Diller tiene un compilador completo para un lenguaje vago (implementado en Pascal) a través de la reducción combinador. Esta fue la técnica de aplicación inventado por David Turner por SASL. Henderson tiene muchas partes de un compilador para LISPkit una miniatura, la variante de Lisp perezoso. Davie detalla un poco de la maquinaria para la elaboración de un lenguaje vago, por ejemplo, hay una descripción de la eso de STG mucho más cortos que el libro de Simon Peyton-Jones (STG es la SPJ máquina abstracta se utiliza para Haskell).

Los desarrolladores limpios tienen un poco de información sobre la aplicación de SAPL (un simple Aplicativo Language) si se mira a través de su lista de publicaciones:

https://clean.cs.ru.nl/Publications

Por último hay un buen número de artículos que documentan aspectos de la Utrecht Haskell Compiler UHC (y EHC). Creo que la mayoría de la información es cómo se organiza el compilador (con gramáticas de atributos y "shuffle") y cómo los sistemas de tipo (hay varios niveles de sistema de tipo de EHC) se implementan, en lugar de cómo el back-end 'compilación' trabajos.

Answer 3

Por desgracia, sospecho que lo que estás buscando no existe. La teoría compilador y la teoría del lenguaje formal son temas bastante complejos en Ciencias de la Computación, y Haskell es de ninguna manera un punto de partida.

En primer lugar, probablemente debería tener una buena base en:

• Análisis léxico: http://en.wikipedia.org/wiki/Lexical_analysis
• de análisis: http://en.wikipedia.org/wiki/Parsing#Programming_languages
  • Contexto gratuito (y otros) los sistemas de gramática (CFG, BNF)
• Generación de código: http://en.wikipedia.org/wiki/Code_generation_(compiler)

Yo sospecharía nada explicar nada sobre el funcionamiento interno de Haskell requeriría una sustancialmente mejor comprensión de los temas anteriores que, por ejemplo, sería C.

Me he dado un solo curso sobre el tema hasta el momento, así que no tengo la literatura formal para recomendar, pero estoy seguro de que existen muchas fuentes buenas.

Answer 4

Los compiladores son un tema muy amplio y sería imposible explicarlas en totalidad aquí. Pero aquí es una visión general de un compilador general. Esperemos que esto le dará un poco de comprensión que pueden hacer que la lectura cosas específicamente sobre GHC un poco más fácil de entender.

compiladores generalmente trabajo por una serie de transformaciones en 2 partes, la parte delantera de extremo y de fondo.

La primera transformación se está convirtiendo texto plano en algo un poco más fácil de recorrer. Esto en sí está generalmente dividido en 2 partes:

Análisis léxico o Tokenization - El acto de transformación de texto sin formato en trozos pequeños (típicamente los operadores, identificadores, literales etc).

análisis sintáctico o analizar - Pasando estos pequeños trozos en una estructura de árbol. (Típicamente un AST, un de sintaxis abstracta Tree)

La siguiente etapa es el análisis semántico. En esta etapa, un compilador suele añadir información a la AST (como información de tipo) y construir una tabla de símbolos. Con esto concluye el front-end.

La siguiente transformación transforma la AST en una IR, un intermedio Representación . Esto es generalmente, hoy en día una forma SSA, una asignación individual estático .

Esto se optimiza entonces, a través de constante de propagación, análisis de código Dead, Vectorización etc.

La última transformación es la generación de código. La transformación de la IR en código máquina. Esto puede ser muy complicado. También se refiere a veces como la reducción.

Para obtener más información recomiendo esta página de Wikipedia .

Answer 5

Wikipedia tiene una buena - legible - explicación del funcionamiento interno de la GHC (similar a la explicación de @ dan_waterworth, pero adaptadas a Haskell y el GHC):

http://en.wikipedia.org/wiki/Glasgow_Haskell_Compiler#Architecture

Answer 6

Uno de los mejores trabajos sobre el tema que he leído es:

• El Glasgow Haskell Compiler por Simon Marlow y Simon Peyton-Jones. La arquitectura de aplicaciones de código abierto.