关于GHC实现的好的介绍性文本？ [英] Good introductory text about GHC implementation?

问题描述

在Haskell中编程时（尤其是在解决Project Euler问题时，次优解决方案往往会影响CPU或内存需求），我常常对该程序的行为感到困惑。我看看个人资料，尝试介绍一些严格性，选择另一个数据结构，但主要是在黑暗中摸索，因为我缺乏一个良好的直觉。

，而我知道Lisp，Prolog和命令式语言是如何实现的，我不知道如何实现一种惰性语言。我也有点好奇。

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

我不知道的事情：

• ？




• 当有多个评估候选项时，执行顺序是什么（当我知道它是从所需的输出驱动时，首先评估A，然后评估B，或先评估B，以检测您根本不需要A）






• 什么是CAF？ （分析表明有时热点在那里，但我没有线索）

解决方案

GHC系统的架构和方法的大部分技术信息在他们的wiki中。

应用什么典型优化？

关键的文件是：。
具体来说，请参见如何表示thunk如何。

堆栈和堆如何使用？

由无纺标签G机器的设计，具体来说，自从该纸张发布以来有许多修改。广义上，执行模型：

• （盒装）对象在全局堆上分配;


• 每个线程对象都有一个堆栈，包括框架与堆对象具有相同的布局;


• 在进行函数调用时，将值推送到堆栈并跳转到函数;


• if代码需要分配eg

要深入了解堆栈使用模型，请参阅推送/输入与评估/应用。

什么是CAF？

恒定适用表格。例如。在您的程序中为程序执行的生命期分配的顶级常数。由于它们是静态分配的，因此必须特别由垃圾回收器处理。

---

和进一步阅读：

：

• GHC评论


• Spinless Tagless G-machine


• 通过转换编译


• 推送/输入与评估/应用


• Unboxed Values as First-Class Citizens


• 内联的秘密


• 多核Haskell的运行时支持

When programming in Haskell (and especially when solving Project Euler problems, where suboptimal solutions tend to stress the CPU or memory needs) I'm often puzzled why the program behaves the way it is. I look at profiles, try to introduce some strictness, chose another data structure, ... but mostly it's groping in the dark, because I lack a good intuition.

Also, while I know how Lisp, Prolog and imperative languages are typically implemented, I have no idea about implementing a lazy language. I'm a bit curious too.

Hence I would like to know more about the whole chain from program source to execution model.

Things I wonder about:

• what typical optimizations are applied?

• what is the execution order when there are multiple candidates for evaluation (while I know it's driven from the needed outputs, there may still be big performance differences between first evaluating A and then B, or evaluating B first to detect that you don't need A at all)

• how are thunks represented?

• how are the stack and the heap used?

• what is a CAF? (profiling indicates sometimes that the hotspot is there, but I have no clue)

解决方案

The majority of the technical information about the architecture and approach of the GHC system is in their wiki. I'll link to the key pieces, and some related papers that people may not know about.

What typical optimizations are applied?

The key paper on this is: A transformation-based optimiser for Haskell, SL Peyton Jones and A Santos, 1998, which describes the model GHC uses of applying type-preserving transformations (refactorings) of a core Haskell-like language to improve time and memory use. This process is called "simplification".

Typical things that are done in a Haskell compiler include:

• Inlining;
• Beta reduction;
• Dead code elimination;
• Transformation of conditions: case-of-case, case elimiation.
• Unboxing;
• Constructed product return;
• Full laziness transformation;
• Specialization;
• Eta expansion;
• Lambda lifting;
• Strictness analysis.

And sometimes:

• The static argument transformation;
• Build/foldr or stream fusion;
• Common sub-expression elimination;
• Constructor specialization.

The above-mentioned paper is the key place to start to understand most of these optimizations. Some of the simpler ones are given in the earlier book, Implementing Functional Languages, Simon Peyton Jones and David Lester.

What is the execution order when there are multiple candidates for evaluation

Assuming you're on a uni-processor, then the answer is "some order that the compiler picks statically based on heuristics, and the demand pattern of the program". If you're using speculative evaluation via sparks, then "some non-deterministic, out-of-order execution pattern".

In general, to see what the execution order is, look at the core, with, e.g. the ghc-core tool. An introduction to Core is in the RWH chapter on optimizations.

How are thunks represented?

Thunks are represented as heap-allocated data with a code pointer.

See the layout of heap objects. Specifically, see how thunks are represented.

How are the stack and the heap used?

As determined by the design of the Spineless Tagless G-machine, specifically, with many modifications since that paper was released. Broadly, the execution model:

• (boxed) objects are allocated on the global heap;
• every thread object has a stack, consisting of frames with the same layout as heap objects;
• when you make a function call, you push values onto the stack and jump to the function;
• if the code needs to allocate e.g. a constructor, that data is placed on the heap.

To deeply understand the stack use model, see "Push/Enter versus Eval/Apply".

What is a CAF?

A "Constant Applicative Form". E.g. a top level constant in your program allocated for the lifetime of your program's execution. Since they're allocated statically, they have to be treated specially by the garbage collector.

---

References and further reading:

• The GHC Commentary
• The Spinless Tagless G-machine
• Compilation via Transformation
• Push/Enter vs Eval/Apply
• Unboxed Values as First-Class Citizens
• Secrets of the Inliner
• Runtime Support for Multicore Haskell

这篇关于关于GHC实现的好的介绍性文本？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！