有关GHC实施的好介绍性文字?

在Haskell中编程时(特别是在解决Project Euler问题时,次优解决scheme往往会强调CPU或内存的需求),我经常困惑为什么程序的行为是这样的。 我看着简介,尝试引入一些严格的,select另一个数据结构,但大多数是在黑暗中摸索,因为我缺乏一个良好的直觉。

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

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

我想知道的事情:

  • 典型的优化应用了什么?

  • 当有多个候选人进行评估时,执行顺序是什么(虽然我知道它是由所需的输出驱动的,但是先评估A然后再评估B或者先评估B以检测你不需要A)

  • thunk代表什么?

  • 如何堆栈和堆使用?

  • 什么是CAF? (分析表明有时热点在那里,但我不知道)

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

典型的优化应用了什么?

关键的论文是: Haskell ,SL Peyton Jones和A Santos,1998 的基于转换的优化器 ,它描述了GHC使用类似于Haskell核心语言的types保持转换(重构)的模型来改善时间和内存使用。 这个过程被称为“简化”。

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

  • 内联;
  • Beta减less;
  • 死码消除;
  • 病情转化:病例,病例报告。
  • 拆箱;
  • 构build产品退货;
  • 完全懒惰转化;
  • 专业化;
  • Eta扩张;
  • Lambda起重;
  • 严格分析。

有时:

  • 静态参数转换;
  • 构build/折叠或stream融合;
  • 常见的子expression式消除;
  • 构造器专业化。

上述论文是开始了解这些优化的关键所在。 在前面的书“ 实现函数式语言” (Simon Peyton Jones and David Lester)中给出了一些简单的例子。

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

假设你使用的是单处理器,那么答案就是“编译器根据启发式select静态select的一些命令,以及程序的需求模式”。 如果你通过火花使用投机评估,那么“一些非确定性,乱序执行模式”。

一般来说,看看执行顺序是什么,看看核心,例如ghc-core工具。 Core的介绍在RWH关于优化的章节中。

thunk代表了什么?

Thunk用代码指针表示为堆分配数据。

堆对象

查看堆对象的布局 。 具体来说,看看thunk是如何表示的 。

如何使用堆栈和堆?

正如无刺无标签G-机器的devise所确定的那样 ,具体而言,自该文件发布以来进行了许多修改。 一般来说,执行模式:

  • (盒装)对象被分配在全局堆上;
  • 每个线程对象都有一个堆栈 ,由与堆对象具有相同布局的框架组成;
  • 当你进行一个函数调用时,你将值推入堆栈并跳转到该函数;
  • 如果代码需要分配一个构造函数,那么这个数据就会被放在堆上。

要深入了解堆栈使用模式,请参阅“推/input与评估/应用” 。

什么是CAF?

一个“恒定的应用forms”。 例如,在程序执行期间为程序分配一个顶级常量。 由于它们是静态分配的,所以必须由垃圾收集器专门处理 。


参考和进一步阅读

  • GHC评论
  • 不旋转的无标记G机器
  • 通过转换编译
  • 推/input与评估/应用
  • 无箱价值作为一stream的公民
  • Inliner的秘密
  • 运行时支持多核Haskell

在介绍性文本中,这可能不是你想到的,但是杨德昌博士有一系列的博客文章,讨论Haskell堆,Thunk是如何实现的等等。

这是有趣的,无论是插图,也是凭借对事物的解释,而不需要为Haskell的新手研究太多的细节。 该系列涵盖了您的许多问题:

  • Haskell堆以及thunk如何存储 – 系列中的第一篇文章
  • 绑定和CAFs
  • IO monad如何被转换成原语

在技​​术层面上,还有一些论文涵盖了(与其他内容一致的),你想知道的部分内容。

  • SPJ的Simon Marlow等人在Haskell的GC上发表了一篇论文 – 我没有读过它,但是由于GC经常代表Haskell所做工作的一个很好的开端,所以它应该给予深入的了解。
  • Haskell 2010年的报告 – 我相信你会听说这个,但是不好链接。 可以在地方进行干读,但最好的方法之一是了解什么使得Haskell成为现实,至less是我读过的部分。
  • Haskell的历史 – 比名称更具技术含义,并提供了一些非常有趣的Haskelldevise和devise背后的决定。 读完之后,你不禁会更好地理解Haskell的实现。