Haskell编译器如何工作?
-
10-10-2019 - |
题
在哪里可以获得一些纸/文档/任何描述Haskell编译器实际工作原理的内容?我读了很多GHC文档,但头痛后停了下来。因此,不需要博士学位的东西就可以理解它并且不需要以您支持的与熟悉的风格写作。如果真的很长,并且需要一些时间才能理解它,那不是问题。
PS:最有趣的是GHC,但一切都可以。
解决方案
您可以从马的嘴里得到答案!西蒙·佩顿·琼斯(Simon Peyton Jones)(GHC向导)写了一本书,说明了如何实施功能编程语言。它可以在线免费提供,因为现在已经绝版了: http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/
当然,自从这本书撰写以来,GHC已经继续前进,但仍然非常相关。
其他提示
您是否正在寻找有关编译懒惰评估的详细信息? Max Bolingbroke提到的西蒙·佩顿·琼斯(Simon Peyton-Jones)的书,详细介绍Clean的实现的书也在线:
http://wiki.clean.cs.ru.nl/functional_programming_and_paroulle_graph_rewriting
如果您有大学的隶属关系并且想要一些较小的东西,您可以尝试获得这些书(Henderson&Diller肯定是绝版的):
Antoni Diller“编译功能语言” ISBN 0 471 92027 4
彼得·亨德森(Peter Henderson)“功能编程应用程序和实施” ISBN 0-13-331579-7
AJT Davie“使用Haskell的功能编程系统简介” ISBN 0 521 27724 8
迪勒(Diller)有一个完整的编译器,用于通过减少组合者的懒惰语言(用Pascal实施)。这是David Turner为SASL发明的实施技术。亨德森(Henderson)有许多部分用于Lispkit的编译器,该编译器是LISP的微型,懒惰的变体。戴维(Davie)详细介绍了编译懒惰语言的大量机械,例如,STG的描述比Simon Peyton-Jones的书短得多(STG是用于Haskell的抽象机器SPJ)。
如果您浏览其出版物列表,那么干净的开发人员就会有很多有关实施SAPL(一种简单的应用语言)的信息:
https://clean.cs.ru.nl/publications
最后,有很多论文记录了Utrecht Haskell编译器UHC(和EHC)的方面。我认为大多数信息是如何组织编译器(具有属性语法和“洗牌”),以及如何实现类型系统(EHC中的类型系统的各种级别),而不是如何实现后端'编译'作品。
不幸的是,我怀疑您想要的不存在。编译器理论和形式语言理论是计算机科学中相当复杂的主题,而Haskell绝不是起点。
首先,您可能应该获得良好的基础:
- 词汇分析: http://en.wikipedia.org/wiki/lexical_analysis
- 解析: http://en.wikipedia.org/wiki/parsing#programming_languages
- 上下文免费(和其他)语法系统(CFG,BNF)
- 代码生成: http://en.wikipedia.org/wiki/code_generation_(compiler)
我会怀疑任何关于Haskell内部人物的任何解释都需要比C所说的要更好地理解上述主题。
到目前为止,我已经参加了有关该主题的一门课程,因此我没有正式的文献推荐,但是我敢肯定有很多很好的资源。
编译器是一个巨大的主题,不可能在这里全面解释它们。但这是通用编译器的概述。希望这将使您有所了解,这些理解可能会使有关GHC的专门阅读内容更容易理解。
编译器通常通过两部分(前端和后端)进行一系列转换来工作。
第一个转换是将纯文本变成更容易穿越的东西。该本身通常分为2个部分:
词汇分析或令牌化 - 将纯文本转换为小块的行为(通常是操作员,标识符,文字等)。
句法分析或解析 - 将这些小块变成树结构。 (通常是 AST,抽象语法树)
下一个阶段是语义分析。在此阶段,编译器通常会在AST中添加信息(例如类型信息)并构建符号表。这是前端的结论。
下一个转换将AST转换为 IR,中间表示. 。这通常是如今 SSA表格,单个静态分配.
然后,通过不断传播,死亡代码分析,矢量化等进行优化。
最后一个转换是代码生成。将IR转换为机器代码。这可能非常复杂。有时也称为降低。
有关更多信息,我建议 此Wikipedia页面.
Wikipedia有一个很好的 - 可读性 - 对GHC的内部概述(类似于 @dan_waterworth的解释,但特定于Haskell和GHC):
http://en.wikipedia.org/wiki/glasgow_haskell_compiler#architecture
我读过的有关该主题的最好的论文之一是:
- 格拉斯哥哈斯克尔编译器 西蒙·马洛(Simon Marlow)和西蒙·佩顿·琼斯(Simon Peyton-Jones)。开源应用程序的架构。