4

Haskell 是一门非常棒的语言。我喜欢它。但是作为一个 C++ 程序员,对计算机架构有一些基本的了解,我真的很想知道 Haskell 的实现细节。

我的意思是,例如,map功能。我知道语法,结果。但是,我想知道这个功能是如何在 RAM 中真正起作用的。因为 C 家族语言对语法和计算机行为之间的映射关系非常清楚。

那么有人对函数式编程语法背后的计算机行为有想法吗?或者任何关于这方面的书,比如“C++ 对象模型内部”?

4

3 回答 3

5

首先,警告:Haskell 的基本属性之一是编译器可能在编译期间对您的代码执行非常激进的转换。因此,实际执行的代码可能与您编写的代码完全不同。

抛开这个警告,第一个近似值,您可以期望每个变量和每个数据字段都是指向堆对象的指针。这些堆对象中的一些代表数据(整数、布尔值、字符、列表节点等),其中一些代表由于惰性而尚未执行的 Haskell 代码。如果您编写一个长而复杂的表达式,则每个子表达式都将成为一个堆对象,顶级表达式指向较低的表达式。所以你程序的整个表达式图变成了堆上的对象图。

(图 /= 树。树中没有“循环”。Haskell 允许递归,因此 Haskell 表达式不一定是表达式。)

Big Haskell 表达式变成了一堆堆对象。复杂的嵌套模式匹配以最佳顺序被脱糖成一系列单层匹配。该语言的所有其他语法糖都被剥离了,直到只剩下 6 个原语:

  1. 创建变量
  2. 使用变量
  3. 创建函数
  4. 调用函数
  5. 创建数据记录
  6. 检查数据记录

如果您想知道实际的位和字节是如何工作的,那取决于编译器。如果您指的是 GHC,它的工作原理大致如下:

  • 每个堆对象要么是代码,要么是数据。

  • 如果它是数据,它包含一个值构造函数 ID 号和每个构造函数字段的指针。

  • 如果它是代码(即,一些尚未执行的子表达式),它包含一个指向函数机器代码块的指针,以及一个指向每个函数参数的指针(没有柯里化)。

  • 当您尝试执行条件分支、I/O 操作或seq在堆对象上时,运行时会跳转到堆对象指向的某些代码。

  • 如果对象表示数据,它将指向一些立即返回的代码。

  • 如果对象代表代码,它将指向实际实现该功能的代码。此代码计算函数的答案,并用表示答案的数据对象覆盖原始堆对象。

  • 无论哪种方式,当控制权返回给调用者时,堆对象肯定是一个数据对象,它现在可以检查构造函数 ID 或它想做的任何其他事情。

于 2014-01-24T16:49:11.040 回答
4

实现惰性函数式语言的基本思想称为 Graph Reduction。

“函数式编程语言的实现”是一本关于该主题的详细的,如果较旧的书:http ://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/

更像教程的介绍:http ://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/

有关如何实现 GHC 的更多信息,您可以查看“Spineless Tagless G-Machine”(STGM)论文,例如:http://www.dcc.fc.up.pt/~pbv/aulas/linguagens/peytonjones92implementing。 pdf

于 2014-01-24T12:23:22.933 回答
4

有一本非常好的书详细介绍了使用惰性图缩减实现函数式语言:

实现函数式语言:教程。西蒙·佩顿·琼斯和大卫·莱斯特,1992。

本书提供了一种实用的方法来理解使用惰性图缩减的非严格函数式语言的实现。本书旨在成为实用实验材料的来源,通过帮助读者开发、修改和试验一些重要的编译器,帮助使函数式语言实现“活跃起来”。

这本书的不同寻常之处在于它既要执行又要阅读。我们不仅提供每种实现技术的抽象描述,还提供每种主要方法的完整工作原型的代码,然后对其进行一系列改进。所有代码都以机器可读的形式提供。

请注意,这本书不同于函数式编程语言的实现,Simon Peyton Jones,1987(这也很有趣)。

于 2014-01-24T19:35:03.373 回答