关于GHC实施的好的介绍性文本？

Question

在Haskell中进行编程时(特别是在解决Project Euler问题时,其中次优解决方案往往会对CPU或内存需求造成压力)我经常感到困惑,为什么程序的行为方式如此.我看一下配置文件,尝试引入一些严格,选择另一种数据结构,...但主要是它在黑暗中摸索,因为我缺乏良好的直觉.

此外,虽然我知道如何实现Lisp,Prolog和命令式语言,但我不知道实现一种懒惰的语言.我也有点好奇.

因此,我想了解更多关于从程序源到执行模型的整个链.

我想知道的事情:

应用了哪些典型的优化？
当有多个评估候选者时,执行顺序是什么(虽然我知道它是从所需的输出驱动的,但是在首先评估A然后B之后可能仍然存在很大的性能差异,或者首先评估B以检测到您不需要一点都不)
thunk如何代表？
如何使用堆栈和堆？
什么是CAF？(分析表明有时热点在那里,但我没有线索)

Answer 1

关于GHC系统的体系结构和方法的大多数技术信息都在他们的wiki中.我将链接到关键部分,以及一些人们可能不知道的相关论文.

应用了哪些典型的优化？

关于这一点的关键论文是:基于转换的Haskell优化器,SL Peyton Jones和A Santos,1998,描述了GHC使用类型保留转换(重构)类似Haskell核心语言以改善时间和记忆用法.该过程称为"简化".

在Haskell编译器中完成的典型事情包括:

而有时:

上述论文是开始理解大多数优化的关键所在.一些较简单的一些在早期的书" 实施功能语言",Simon Peyton Jones和David Lester中给出.

当有多个候选人进行评估时,执行顺序是什么

假设您使用的是单处理器,那么答案就是"编译器根据启发式选择静态选择的一些顺序,以及程序的需求模式".如果你通过sparks使用推测评估,那么"一些非确定性的,无序的执行模式".

通常,要查看执行顺序是什么,请查看核心,例如ghc-core工具.关于Core的介绍在RWH章节中进行了优化.

thunk如何代表？

Thunks表示为带有代码指针的堆分配数据.

堆对象

如何使用堆栈和堆？

由Spineless Tagless G-machine的设计决定,具体而言,自该论文发布以来进行了许多修改.从广义上讲,执行模型:

要深入了解堆栈使用模型,请参阅"推/输对比Eval /应用".

什么是CAF？

"不变的申请表".例如,为程序执行的生命周期分配的程序中的顶级常量.由于它们是静态分配的,因此必须由垃圾收集器专门处理.

参考文献和进一步阅读:

Answer 2

这可能不是您在介绍性文本方面的想法,但Edward Yang有一系列博客文章讨论Haskell堆,如何实施thunk等等.

这既有插图也有娱乐性,而且不需要为Haskell的新手深入细节.该系列涵盖了您的许多问题:

在更技术层面上,有许多论文涵盖(与其他事物一致),你想知道的部分内容:

SPJ,Simon Marlow等人在Haskell的GC上发表的一篇论文 - 我还没有读过它,但由于GC经常代表Haskell工作的一个很好的门户,它应该给予洞察力.
Haskell 2010报告 - 我相信你已经听说过这个,但是不要链接到它太好了.可以在某些地方进行干读,但是了解Haskell的最佳方法之一,至少是我读过的部分.
Haskell的历史 - 比技术名称更具技术性,并提供了一些非常有趣的Haskell设计视图以及设计背后的决策.阅读之后,你不禁能更好地理解Haskell的实现.