详情
本书深入浅出地介绍如何使用Haskell语言及相关的库和框架编写并行和并发程序。本书用两个部分分别讲解并行Haskell编程和并发Haskell编程。书中包含大量可运行的代码示例，并附有详细的注释，读者通过亲身运行、修改和调试代码，可极大地加深对书中内容的理解。
书名：Haskell并行与并发编程
ISBN：978-7-115-36718-1
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
• 著 [英] Simon Marlow
译 喻昌远
责任编辑 杨海玲
• 人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
• 读者服务热线：(010)81055410
反盗版热线：(010)81055315
Copyright ©2013 by O’Reilly Media, Inc.
Simplified Chinese Edition, jointly published by O’Reilly Media, Inc. and Posts & Telecom Press, 2014. Authorized translation of the English edition, 2014 O’Reilly Media, Inc., the owner of all rights to publish and sell the same.
All rights reserved including the rights of reproduction in whole or in part in any form.
本书中文简体版由O’Reilly Media, Inc.授权人民邮电出版社出版。未经出版者书面许可，对本书的任何部分不得以任何方式复制或抄袭。
版权所有，侵权必究。
本书深入浅出地介绍如何使用Haskell语言及相关的库和框架编写并行和并发程序。本书用两个部分分别讲解并行Haskell编程和并发Haskell编程。根据编程模型的不同，并行部分介绍了3种并行编程方式：基于惰性求值的并行（Eval Monad及求值策略）、基于数据流的并行（Par Monad）以及面向大规模数组算法的并行（Repa数据并行编程和Acellerate GPU编程）。并发部分则按抽象层次由低到高分别涉及线程和MVar、重叠I/O、线程的取消和超时、软件事务内存、高级并发抽象、并发网络服务程序、使用线程并行编程和分布式编程等，最后还介绍调试、性能调优以及外部函数接口。书中包含大量可运行的代码示例，并附有详细的注释，读者通过亲身运行、修改和调试代码，可极大地加深对书中内容的理解。
本书适合有一定Haskell语言基础的程序员或者对并行或并发编程感兴趣的相关人员阅读。
十年前，出于好奇，我第一次在真正意义上接触到了GNU/Linux操作系统，那时我还刚上大学不久。也正是那一年的暑假，我留在学校，修了Linux系统的选修课。整个夏天，随着课程的学习，一个崭新的世界展现在了我的面前。就在这一年，我知道了Richard Stallman的自由软件运动和GNU项目，被其捍卫软件自由的黑客精神深深震撼，又为GNU项目以及其他自由软件所取得的丰硕成果欢欣鼓舞。可以毫不夸张地说，以十年前为起点发生的这一切，对我的大学生活，乃至人生观和价值观，都产生了重大而深刻的影响。
作为影响之一，GNU Emacs成为了我日常编程开发使用的编辑器。该编辑器最先由Richard Stallman开发，历史悠久，功能强大，至今仍然有大量的活跃用户。其与众不同之处在于可以通过名为Emacs Lisp的编程语言灵活地实现各种功能。而Emacs Lisp是函数式编程语言Lisp的一种方言。因此在深入学习Emacs的过程中，我了解了Lisp这一简洁而优雅的语言，进而对函数式编程产生了浓厚的兴趣。
我第一次听说Haskell还是因为Perl 6，由于在校的时候选修了Perl语言的课程，所以那时对Perl 6比较感兴趣，而当时最完整的Perl 6实现是用Haskell编写的。真正开始Haskell的学习已经是毕业之后的事情了，那时我希望找到一种表达能力强，性能也不错的语言，作为以后日常学习和生活使用的编程语言。Haskell作为函数式语言，有着优异的表达能力，作为静态、编译型语言，可以达到相当不错的性能，尤为重要的是，Haskell最主要的实现GHC（Glasgow Haskell Compiler）是自由软件。因此，我开始了Haskell语言的学习和使用。值得提一下的是，我本人是数字集成电路设计工程师，而数字电路设计和函数式编程是非常相似的，实际上，在Hackage上有不少用来设计数字电路的Haskell库或工具。
长久以来，我一直受惠于自由软件，而因此一直希望能为其发展贡献出自己的一份力量。恰逢去年上海Linux用户组（SHLUG）的宋方睿同学向人民邮电出版社推荐我参与本书的翻译工作，经过慎重的考虑，我向编辑表达希望翻译本书的意愿。虽然缺乏翻译的经验，但觉得自己经过努力应该能够胜任翻译工作，而且作为一位长期的Haskell用户，我也很希望能够为Haskell语言的推广作出自己的贡献，回报社区。非常幸运的是，我的努力和能力得到了本书的责任编辑的认可，我得以进行本书的翻译工作。
在翻译的过程中，我首先要感谢的是我的亲人和朋友，感谢他们的理解和支持。
其次，我要感谢宋方睿同学，他本人也是《Haskell趣学指南》一书的译者之一。除了感谢他的推荐外，在本书的前期翻译过程中，他也给予了我很大的帮助。
我还要感谢人民邮电出版社的编辑，特别是本书的责任编辑杨海玲，非常感谢她对我信任，还有在贯穿全书的翻译过程中对我的支持和帮助。
最后，限于本人水平有限，译文中错误在所难免，望读者谅解。
喻昌远
2014年7月
作为一名Glasgow Haskell编译器（GHC）的开发者近15年，我目睹了Haskell从一门合适的研究性语言成长为一个繁荣丰富的生态系统。在GHC的并行和并发的支持上，我花费了大量的时间。在1997年，我重写了其运行时系统（Runtime System），这是该年我对GHC做的头几件事情之一。而且当时我们还做了一个关键性的决定，即直接在系统的核心支持并发，而非在额外的可选库或附加库中支持。对于这个决定，我希望是基于敏锐的先见之明，但事实上却很大程度和我们找到一种方法有关，这种方法使得支持并发性的额外开销能减少到接近零（我们一直困扰于性能问题，之前的额外开销在2%左右）。尽管如此，成为实现的必要部分，意味着并发性在GHC中的地位是一等的，而我很确信，正是这个决定给GHC带来了稳定且高性能的并发支持。
Haskell有着与并行性（parallelism）相关联的悠久传统。仅举几个项目为例，有专为并行计算设计的衍生自Id语言的并行Haskell变体，有在多台机器上运行并行Haskell程序的GUM系统，以及GRiP系统——一个为运行并行函数式程序设计的完整计算机架构。所有的这些都发生在现在的多核革命之前，而问题是当时摩尔定律让我们仍能制造出更快的电脑。并行性的实现非常困难，而当普通的电脑可以以指数级的速度变快时，为此而努力似乎得不偿失。
在2004年前后，为了使GHC运行时系统能在共享内存的多处理器上运行，我们决定为其开发一个并行实现（parallel implementation），这在之前还未曾做过。这恰好是在多核革命的前夕，当时多处理器的机器还很常见，但多核的仍未出现。这里我再次希望，决定此时解决并行性问题是出于远见卓识，但这个决定却和下面的事实关系更大，即开发内存共享的并行实现是一个有趣的研究性问题，而且听起来很有意思。Haskell的纯粹是根本性的——这意味着可以避免在运行时系统和垃圾回收器中加锁而造成的部分额外开销，也就是说，可以将使用并行造成的额外开销减小到很少的几个百分点。然而，直到经过了更多的探索研究，调度器的重写，以及一个全新的并行垃圾回收器的使用，这个新实现才真正达到可用的程度，能够加速大量的程序。我在2009年国际函数式程序设计大会（International Conference on Functional Programming，ICFP）上提交的论文是这一并行实现从一个有趣的原型变为实用工具的转折点。
所有这些研究和实现的工作都非常有趣，但教导程序员如何使用Haskell中的并行与并发特性的高质量资源依然匮乏。在过去的几年，我有机会两次在暑期班讲授Haskell并行与并发编程，一次是在Budapest举办的2011中欧函数式程序设计（CEFP）暑期班，另一次是在法国南部Cadarache举办的2012 CEA/EDF/INRIA暑期班。在为这些课程准备材料时，我首次有理由编写一些深入的指南，并且开始收集一些优秀的实例。在2012年的暑期班之后，我已经有了100页的指南，在一些人（见致谢部分）的鼓励下，我决定将这些内容编写成书。当时我觉得已经完成了一半左右，但实际上可能才接近四分之一。实在有太多内容要写了！希望你能享受我最终的成果。
阅读本书需要一些基本的Haskell使用知识，而本书中并未涉及这些内容。为此，阅读一本入门书籍，例如《Real World Haskell》（O'Reilly）、《HaskellProgramming in Haskell》（剑桥大学出版社）、《Learn You a Haskell for Greate Good》[1]（No Starch Press）或者《Haskell：The Craft of Functional Programming》（Addison-Wesley），应该是一个很好的开始。
本书的主要目标是让读者能够进行并行与并发Haskell编程。但是，正如你大概已经知道的，学习编程并非是单独看书就可以的。这正是本书的编写刻意切合实际，包含大量的可以运行、修改和扩展的例子的原因所在。书中有几章包含了练习，建议读者尝试，通过这些练习可以熟悉该章介绍的主题，本人强烈推荐做一些练习，或按自己的想法写些代码。
在探讨本书的主题时，我不会回避陷阱和系统中不完善的部分。Haskell已经发展了20多年，但其在今天的发展比以往任何时刻都更为迅速。因此自然会遇到一些不一致情况和系统中不那么好的部分。本书涉及的一些主题是新近发展起来的：第4、5、6和14章涉及了一些最近几年开发的框架。
本书包含两个基本独立的部分，第一部分和第二部分。读者可以随意从一部分开始阅读，或者在两部分间切换着阅读（也就是并发地阅读两部分）。两部分中仅有一处存在依赖关系：如果先阅读了第一部分，那么将更容易理解第13章，尤其是在13.2.5节前，应该先读第4章。
尽管两部分是基本独立的，但同一部分内的各章还是应按顺序阅读。本书并非是参考书，书中包含的一些可运行的例子和主题是贯穿数章开发和发展出来的。
本书使用如下排版约定。
此图标表示一个小技巧、建议或者一般性注释。
此图标表示需要警惕的陷阱，一般是一些不那么明显的情况。
代码示例如下：
timetable1.hs
search :: ( partial -> Maybe solution ) -- ❶
-> ( partial -> [ partial ] )
-> partial
-> [solution]
标题是代码片段所在的源代码文件的文件名，该文件可以在示例代码中找到；关于如何获取示例代码，见1.3节。当引用同一个文件中的多个片段时，仅第一次会有文件名标题。
❶ 代码片段中常会出现这样的关于某行的注释。
输入shell中的命令示例如下：
$ ./logger
hello
bye
logger: stop其中$字符是提示符，紧接着是命令，剩下的几行是命令产生的输出。
GHCi会话示例如下：
> extent arr
(Z :. 3) :. 5
> rank (extent arr)
2
> size (extent arr)
15由于GHCi的默认提示符会在导入几个模块后显得过长，本人常将GHCi的提示符设定为>后面接着一个空格。通过在GHCi中使用下列命令，可以完成该设置：
Prelude> :set prompt "> "
>随书附带的示例代码可在线获取，具体如何获取和构建请参见1.3节。关于示例代码的使用、修改和再发布的权利的相关信息，请参见示例代码发布包中的LICENSE文件。
如果你想就本书发表评论或有任何疑问，敬请联系出版社。
美国：
O’Reilly Media Inc.
1005 Gravenstein Highway North
Sebastopol, CA 95472
中国：
北京市西城区西直门南大街2号成铭大厦C座807室（100035）
奥莱利技术咨询（北京）有限公司
我们为本书提供了专门的网页，上面有勘误表、示例，以及其他额外的信息，可以通过http://oreil.ly/parallel-concurrent-prog-haskell访问该网页。
若要留言或询问关于本书的技术问题，请发送电子邮件到bookquestions@oreilly.com。
想了解更多关于我们的书籍、课程、会议，以及新闻等信息，请登录我们的网站：http://www.oreilly.com。
我们的其他联系方式如下。
Facebook: http://facebook.com/oreilly
Twitter: http://twitter.com/oreillymedia
YouTube:http://www.youtube.com/oreillymedia
有好几个月的时间我满脑子都是并行和并发Haskell而无法容下其他东西，所以我最先也是最重要的是要感谢我的妻子，感谢她对我的鼓励、她的耐心，以及在写书时提供的蛋糕。
其次，本书的编写很大程度上要归功于Simon Peyton Jones，他自GHC诞生之初就开始领导该项目，他坚持不懈的热情和对技术的深刻了解是GHC发展的持续推动力。他一直是我最丰富的灵感之源。
我还要感谢Mary Sheeran和Andres Löh，他们说服我将授课笔记编写成书。感谢CEPH和CEA/EDF/INRIA暑期班的组织者邀请我授课，让我有了开始的动力。感谢作为我的“试验品”，上我课的学生们。
非常感谢本书的编辑Andy Oram及O'Reilly的其他人，在他们的帮助下，本书才得以出版。
下面这些人都以某种方式对本书的编写提供了帮助，他们或者是审查了早期的书稿、给我提出了建议、给在线章节留言，或者是我借用了他们写的代码（希望已经进行了署名），或者用了他们撰写的论文或博客中的想法，或者是其他的帮助（若遗漏了一些人的话，实在抱歉）：Joey Adams、Lennart Augustsson、Tuncer Ayaz、Jost Berthold、Manuel Chakravarty、Duncan Coutts、Andrew Cowie、Iavor Diatchki、Chris Dornan、Sigbjorn Finne、Kevin Hammonad、Tim Harris、John Hughes、Mikolaj Konarski、Erik Kow、Chris Kuklewicz、John Launchbury、Roman Leshchinskiy、Ben Lippmeier、Andres Löh、Hans-Wolfgang Loidl、Ian Lynagh、Trevor L. McDonell、Takayuki Muranushi、Ryan Newton、Mary Sheeran、Wrenng Thornton、Bryan O’Sullivan、Ross Paterson、Thomas Schilling、Michael Snoyman、Simon Thomson、Johan Tibell、Phil Trinder、Bas Van Dijk、Phil Wadler、Daniel Winograd-Cort、Nicolas Wu和Edward Yang.
最后，我要感谢Haskell社区，这是我遇到的最友好、包容、有帮助以及鼓舞人心的在线开源社区之一。朋友们，我们有很多值得骄傲的地方，坚持下去。
[1] 中文版书名《Haskell趣学指南》已由人民邮电出版社出版。——编者注
长久以来，编程社区已熟知线程和锁难以使用。即使很简单的问题也常常需要过高的专业技能，而且会导致难以诊断的故障。然而，线程和锁依然十分通用，从并行图像处理到并发Web服务器，足以表达出所需要编写的任何内容，并且有一个专一的通用API也有不可否认的好处。但是，若想让并行和并发编程变得更容易，就要接受“不同的问题要用不同的工具解决”的思想，一种工具无法解决所有的问题。图像处理可以自然地表达成并行矩阵运算，而线程则很好地适用于并发Web服务器的情况。
因此在Haskell中，我们的目标是尽可能为多种工作提供正确的工具。若发现一项工作在Haskell中没有正确的对应工具，则会尝试找出一种方法将其制造出来。工具的多样化不可避免会带来负面影响，即需要大量的学习，而这正是本书所要进行讲解的。在本书中，将会讨论如何用Haskell编写并行和并发程序，从简单地利用并行来加速计算密集型程序，到使用轻量级线程编写高速并发的网络服务程序。在这个过程中，还将会看到如何使用Haskell编写程序，让其运行在现代图形显卡中强大的处理器（GPU）上，也会看到如何编写程序，使之能够在网络中的多台机器上运行（分布式编程）。
这并非说本人打算对每一种最新出现的试验性编程模型都进行介绍。若仔细查看Hackage上的软件包，可以发现各式各样用于并行和并发编程的库，其中许多是为了特定目的而开发的，更不用说所有的未到实用阶段的研究性项目。在本书中，我将重点关注现在已能用来完成工作，足够稳定，并在生产中可信赖的API。此外，本人的目标是让读者牢固地掌握最底层的工作原理，以便在需要的时候能够在此之上搭建出自己的抽象结构。
在许多领域并行和并发是同义词，但在编程中则不然，它们被用来描述在根本上完全不同的两个概念。
并行程序是指使用多个硬件参与计算（如多个处理器核心）使之更快的程序。目标是通过将计算的不同部分分配给不同的处理器，使之能够同时执行，从而更早得到问题的答案。
与之相对的，并发则是一种包含多个控制线程的程序构成技术。从概念上说，这些控制线程是“同时”被执行的，也就是说，用户所观察到的最终影响，是由这些线程交替作用产生的。到底是否真的是同时执行则属于实现上的细节。并发程序可以通过交替的方式在单个处理器上执行，或在多个物理处理器上执行。
并行编程仅关注效率，而并发编程则关注程序的构成，使之能够和多个独立的外部媒介交互（如用户、数据库或一些外部客户）。并发性使得这类程序能够模块化，和用户交互的线程可以明确地区分于和数据库通信的线程。在没有并发的情况下，这类程序必须通过事件循环和回调的方式编写，与线程所提供的相比，通常更加低效且模块化不足。
在纯函数式的程序中，“控制线程”这个概念是没有意义的，因为没有需要观测的效果，而且程序的结果也和求值的顺序无关。因此，并发性是用于构成产生效果的代码的技术；在Haskell中，即IO monad中的代码。
一个与之相关的内容是确定性和非确定性编程模型的区分。确定性编程模型中每个程序只会给出一个结果，而非确定性编程模型则容许——取决于执行时某些情况——程序可以有不同的结果。由于必须和外部媒介交互，而这些交互会导致事件在不可预测的时刻发生，所以并发编程模型必然是非确定性的。而非确定性有一些显著的缺点：程序将会变得非常难以测试和推断。
对于并行编程来说，应尽可能地使用确定性编程模型。既然目标仅仅是更快地获得答案，那么还是不要让程序在这个过程中变得更难调试。确定性并行编程是这两方面的最佳结合：测试、调试和推断可以以顺序的方式执行，但加入更多处理器后程序则能运行得更快。事实上，大多数计算机处理器自身通过流水线和多个执行单元的形式实现了确定性并行。
虽然可以使用并发的方式实现并行编程，但这通常不是一个明智的选择，因为并发的使用牺牲了确定性。在Haskell中，大多数的并行编程模型都是确定性的。然而，注意到确定性编程模型并不足以表达所有的并行算法是非常重要的，有些算法是依赖于内部不确定性的，特别是要对解空间进行搜索的问题。此外，有时希望并行化确实有副作用的程序，那就别无选择，只能使用非确定性并行编程或并发编程了。
最后，希望在同一个程序中混合使用并行和并发编程是完全合理的。大多数的交互式程序需要使用并发来维持一个快速响应的用户界面，与此同时在后台执行计算密集型的任务。
为了运行本书中的范例程序和完成练习，需要安装Haskell Platform（http://hackage.haskell.org/platform/）。Haskell Platform中包含了GHC编译器和所有重要的库，包括这里需要使用的并行和并发库。本书中的代码在2012.4.0.0版Haskell Platform上测试，但是示例代码会随着新的版本发布而进行更新。
有几章需要安装额外的软件包。安装这些额外的依赖的指令可以在1.3节中找到。
此外，本人推荐安装ThreadScope。ThreadScope是一个可视化Haskell程序执行的工具，尤其是对查看并行和并发Haskell代码的行为非常有用。在Linux系统上，ThreadScope很可能可以直接通过发行版的包管理器安装，这也是目前为止最容易的安装方式。例如，在Ubuntu上，可以通过以下的简单命令安装：
$ sudo apt-get install threadscope对于如何在其他系统上安装ThreadScope，请参见Haskell网站（http://www.haskell.org/haskellwiki/ThreadScope）。
阅读本书时，建议读者手上备有以下文档。
需要注意的是，本书用到的大多数API都不属于Haskell 2010标准。这些API由附加软件包提供，其中有一些包含在Haskell Platform中，而其余的可以在Hackage上找到。
示例代码被收集整理为parconc-examples软件包[1]放在Hackage上。运行下列命令可下载并解开该包：
$ cabal unpack parconc-examples然后，安装所依赖的包：
$ cd parconc-examples
$ cabal install --only-dependencies接着，配置并构建[2]所有的范例程序：
$ cabal configure
$ cabal build随着未来Haskell Platform或其他API的变化，parconc-examples包也会随之进行必要的更新。
[1] 后面“软件包”将简称为“包”。——译者注
[2] 即编译和链接。——译者注
如今，处理器制造商基本放弃了对单处理器性能提升的努力，转而将注意力集中到提供更多数量的处理器上。而并行技术能利用额外的核心，因此能使程序性能得到最大的提升。而并行Haskell的目标就在于提供一种自然而稳健的方式对多个处理器进行访问。
读者也许想知道编译器能否自动将程序并行化。毕竟，纯函数式语言中的计算之间仅有数据依赖关系[1]，很大程度上清晰明了，因此可以轻易地进行分析，所以纯函数语言的自动并行化应该相对容易些。但是，即使是纯函数式语言，自动并行化仍被一个由来已久的问题所阻扰：为了让程序运行得更快，通过并行提升的性能应至少抵消由此引入的额外开销，而在这方面，编译时（compile-time）分析并不能做出很好的判断。一种替代的方法是通过运行时的性能剖析找到优秀的并行化候选方法，然后将这些信息反馈回编译器。即使这样，在实际中该方法也并没有很成功。
全自动并行化依旧不切实际。然而，Haskell提供的并行编程模型成功地消除了一些传统上与并行编程相关的乏味和易于出错的部分。
并行Haskell程序员主要需要思考的问题是划分（partitioning）：将问题分成几个可以独立计算的部分。理想的情况是，希望有足够的任务让所有处理器保持忙碌。然而，这样的努力会受到以下两方面的阻扰。
粒度（granularity）
数据依赖（data dependencies）
下面各章将会对Haskell提供的多种并行编程模型进行描述。
Eval monad和求值策略，适用于表达非数值密集并且不基于数组的Haskell程序的并行性。这些编程模型都切实可行，有许多成功并行化的优秀例子。Par monad这一更新的编程模型。该编程模型的目标同样在于并行化普通的Haskell代码，但采用了不同的折中：通过牺牲部分求值策略的简洁性和模块性来换取程序员对程序的更大可控性。并行化Haskell代码可以是令人愉快的经历：在程序中添加一小段注解（annotation），使之能在多核机器上的运行速度提升几倍。也可能令人沮丧，正如下面几章将会看到的，遇到许多陷阱。其中一些是Haskell特有的，一些则是任何语言都会碰到的。但愿在最后对于并行编程，读者能够建立起足够的直觉，通过使用书中的这些的技术，可以让自己的程序获得足够的并行加速比。
在阅读本书的部分内容时务必牢记，由于当今计算设备非常复杂，性能依赖于大量互相影响的组件，获得可靠的并行性能数据在本质上是困难的。出于这个原因，在本人电脑上运行范例得到的结果可能和在读者的硬件上运行的结果有所不同。希望差别不大，否则可能表明GHC中存在问题，对此应该向GHC项目汇报。重要的是察觉到性能的不确定性，尤其是在牵涉到并行性的时候。
[1] 即每个计算之间，依赖关系仅由参与运算的数据决定的，不像非纯函数式语言中，程序中的后一条语句可能依赖于前一条语句。——译者注
[2] combinator，指不包含自由变量的函数。——译者注
Eval Monad[1]本章将讲授在Haskell代码中使用并行编程技术的基础。首先将介绍一些关于惰性求值的必要背景，然后在2.2节讲解如何进行并行编程。
Haskell是一门惰性语言，即表达式是在其值需要使用时才被求值[3]。一般来说，不必担心该过程如何发生，只要表达式在需要时求值，不需要时不被求值即可。但是，当在代码中使用了并行编程后，就需要告诉编译器一些程序运行的信息，即某些代码应该并行执行。由于对惰性求值的工作方式有一个直觉的认识将有助于有效地进行并行编程，因此本节将以GHCi作为试验工具，探讨惰性求值的一些基本概念。
下面从非常简单内容的开始：
Prelude> let x = 1 + 2 :: Int这会将变量x绑定（bind）到表达式1 + 2（为了避免任何由重载带来的复杂性，特指定为Int类型）。此时，仅考虑Haskell语言本身，1 + 2是和3相等的，因此这里也可以写成let x = 3 :: Int，而且通过普通的Haskell代码无法将两种写法区分开。但出于并行编程的目的，这里确实在意1 + 2和3的区别，因为1 + 2是一个还未开始的计算，其值也许可以通过其他方法并行地计算出来。当然，在实际中不会对像1 + 2这样简单情况使用并行计算，然而，其作为未求值计算的本质是仍然是重要的。
此刻，称x为未求值的（unevaluated）。一般来说，在Haskell中是无法得知x是未求值的，但幸运的是，GHCi的调试器提供了一些命令，这些命令可以查看Haskell表达式的结构，但又不影响表达式本身。因此，可以通过使用这些命令来说明发生的情况。:sprint这条命令可以打印出表达式的值，但又不会引发表达式求值。
Prelude> :sprint x
x = _特殊符号_表示“未求值的”，对于这种情况，读者也许听过另一个词“thunk”，即内存中表示1 + 2这个未求值计算的对象。此例中的thunk如图2-1所示。
图2-1 表示1 + 2的thunk
在图中，x是一个指向内存对象的指针，该内存对象表示函数+应用于整数1和2。
该thunk表示x将在其值需要时被求值。在GHCi中，触发求值最容易的方法是将其打印出来，也就是说，在提示符后输入x即可：
Prelude> x
3现在若通过:sprint查看x的值，可以发现其已被求值：
Prelude> :sprint x
x = 3从内存中的对象方面考虑，即表示1 + 2的thunk实际上被（装箱的）整数3覆盖了[4]。因此，以后任何对x值的查询都会立即返回结果，这就是惰性求值的工作原理。
前面的例子比较简单，再试一个稍为复杂的的示例：
Prelude> let x = 1 + 2 :: Int
Prelude> let y = x + 1
Prelude> :sprint x
x = _
Prelude> :sprint y
y = _这里再次将变量x绑定到1 + 2，此外，还将变量y绑定到x + 1，然后，正如所预期的，:sprint命令显示两者均未被求值。在内存中，会有图2-2所示的结构。
图2-2 一个引用了另外的thunk的thunk
不幸的是，该结构无法被直接查看，读者只有相信这里所画的图是正确的。
现在，为了计算y的值，需要x的值，即y依赖于x。因此，对y的求值同时会导致对x的求值。这次使用不同方法来强制求值，即通过Haskell内建的seq函数。
Prelude> seq y ()
()函数seq先对其第一个参数求值，这里是y，然后返回第二个参数，此例中，即()。再查看此时x和y的值：
Prelude> :sprint x
x = 3
Prelude> :sprint y
y = 4正如所预期的，两者均已被求值。因此，到目前为止一般性的原则如下。
再看一下增加一个数据结构会发生什么情况：
Prelude> let x = 1 + 2 :: Int
Prelude> let z = (x,x)变量z绑定到了序对（x，x），命令:sprint显示出一些有意思的内容：
Prelude> :sprint z
z = (_,_)这里隐含的结构如图2-3所示。
图2-3 两项引用同一thunk的序对
变量z本身引用了序对（x，x），但序对的两项均指向了未求值的，代表x的thunk。这说明数据结构可以使用未求值的表达式来构建。
下面再次将z变为thunk：
Prelude> import Data.Tuple
Prelude Data.Tuple> let z = swap (x,x+1)函数swap的定义为：swap（a，b）=（b，a）。这次z和前面的一样，是未求值的：
Prelude Data.Tuple> :sprint z
z = _这样的话，当使用seq来对z求值时，就能看清楚具体发生的情况：
Prelude Data.Tuple> seq z ()
()
Prelude Data.Tuple> :sprint z
z = (_,_)函数seq执行后，导致作为参数的z被求值，成为一个序对，但序对的两项仍然处于未求值状态。函数seq仅对其第一个参数的第一层构造求值，不再对剩下的结构继续求值。对此有一个专门的称呼：称函数seq对第一个参数求值，使之成为弱首范式（weak head normal form）。该术语的使用是出于历史原因，因此对其不必深究。该术语常被缩写为WHNF[5]。名词范式在这里是“完全求值”[6]的意思，在2.4节会看到如何将表达式求值使之成为范式。
弱首范式的概念在下面两章会多次出现，因此值得去花些时间去理解这个概念，并对Haskell中求值是如何发生的有所体会。对此在GHCi中试验不同的表达式和:sprint命令不失为一种很好的方法。
为了完成本例，下面对x进行求值：
Prelude Data.Tuple> seq x ()
()此时z会是何值？
Prelude Data.Tuple> :sprint z
z = (_,3)记得变量z被定义为swap（x，x+1），即（x+1，x），前面刚对x求值了，所以z的第二个成员是已被求值的，值为3。
最后，来看一个关于列表和几个常见列表函数的例子。对于函数map的定义，读者或许已经知道，不过还是列在下面作为参考：
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs函数map建立了一个惰性的数据结构。若重写map的定义而让thunk明确，可能会更清楚一些：
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = let
x' = f x
xs' = map f xs
in
x' : xs'这和前面的map的定义是一样的，但可以看到map返回的列表的头和尾各自都是thunk：f x和map f xs。也就是说，map建立了图2-4所示的结构。
图2-4 通过map建立的thunk
下面使用map定义一个简单的列表结构：
Prelude> let xs = map (+1) [1..10] :: [Int]此时xs未被求值：
Prelude> :sprint xs
xs = _接着对该列表求值，使之成为弱首范式：
Prelude> seq xs ()
()
Prelude> :sprint xs
xs = _ : _目前为止，只知道xs是一个至少包含一个元素的列表。接着，对该列表应用length函数：
Prelude> length xs
10函数length的定义如下：
length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs注意到length会忽略列表的头，而只对列表的尾xs进行递归，因而对列表应用length时，列表的结构会被展开，但元素不会被求值。这点通过:sprint可以清楚地看到：
Prelude> :sprint xs
xs = [_,_,_,_,_,_,_,_,_,_]GHCi注意到列表已被展开，所以改用方括号显示列表，而不再使用:。
即使通过求值的方式展开了整个列表，该列表仍不是范式（而仍然是弱首范式）。通过对列表应用一个函数，该函数需要使用列表的所有元素，就可以使之完全求值。例如sum函数：
Prelude> sum xs
65
Prelude> :sprint xs
xs = [2,3,4,5,6,7,8,9,10,11]前面这些讨论，对于惰性求值这个精妙而复杂的主题仅触及了表面。幸运的是，多数情况下，编写Haskell代码无需了解或担心求值是何时进行的。的确，Haskell语言定义十分仔细，不对如何求值作明确指定；语言的实现可以自由地选择策略，只需保证结果正确。这也是程序员大多数时候所关注的。但是，当编写并行代码时，了解表达式何时被求值变得重要起来，因为只有这样才能对并行化计算进行安排。
第4章使用Par monad，对数据流进行明确的描述，是另一种使用惰性求值进行并行编程的方法。该方法牺牲了部分简洁性从而避免了一些惰性求值相关的微妙的问题。由于会出现一种方法比另一种解决问题更自然或更高效的情况，因此两种方法都值得学习。
Eval monad、rpar和rseq下面介绍模块Control.Parallel.Strategies提供的用于并行编程的一些基本内容，定义如下：
data Eval a
instance Monad Eval
runEval :: Eval a -> a
rpar :: a -> Eval a
rseq :: a -> Eval a并行性是通过Eval monad表达的，具体包括rpar和rseq两个运算。组合子rpar用于描述并行，即其参数可以并行求值；而rseq则用于强制串行求值，即对其参数求值并等待结果。两者的求值的结果都是弱首范式。rpar的参数不必是未求值的计算，即thunk，若参数是已经被求值的，则不会发生任何事情，因为没有东西需要并行计算。
Eval monad提供了runEval运算用于执行Eval计算，然后返回结果。值得注意的是，runEval是纯函数，没有副作用，无需在IO monad中使用。
为了观察rpar和rseq的效果，假设有一个函数f，以及两个被f应用的参数x和y，而且f x算得比f y慢，希望能够并行的计算f x和f y的结果。下面会使用几种不同的方法编写代码，然后研究它们间的区别。首先，对f x和f y使用rpar，然后返回一对结果，如例2-1所示。
例2-1 rpar/rpar
runEval $ do
a <- rpar (f x)
b <- rpar (f y)
return (a,b)该代码片断执行的情况如图2-5所示。
图2-5 rpar/rpar的时间线
从图2-5中可以看到f x和f y同时开始求值，而return这句也是立刻被执行的：并不等待f x或f y完成求值。在f x和f y开始并行求值的同时，剩下的程序接着执行。
下面尝试另一种写法，将第二个rpar换成rseq。
例2-2 rpar/rseq
runEval $ do
a <- rpar (f x)
b <- rseq (f y)
return (a,b)执行后，结果如图2-6所示。
图2-6 rpar/rseq的时间线
图2-6中f x和f y仍然并行求值，但最后的return是f y完成后才执行的。这是因为使用了rseq，该函数会在返回前等待其参数完成求值。
若添加一个额外的rseq等待f x，则会等待f x和f y都完成。
例2-3 rpar/rseq/rseq
runEval $ do
a <- rpar (f x)
b <- rseq (f y)
rseq a
return (a, b)需要注意的是，新的rseq是应用于a，第一个rpar的结果。结果如图2-7所示。
图2-7 rpar/rseq/rseq的时间线
上述代码直到f x和f y都完成求值后才返回。
对使用的模式，应如何选择？
下面是最后一种写法。
例2-4 rpar/rpar/rseq/rseq
runEval $ do
a <- rpar(f x)
b <- rpar(f y)
rseq a
rseq b
return (a, b)这段代码和rpar/rseq/rseq的行为是一样的，等待两个求值完成后再返回。虽然该写法是最长的，但和其他写法相比，显得更为对称，基于该原因，这个写法可能更加可取。
通过范例程序rpar.hs可以试验这些不同的写法，程序使用Fibonacci函数模拟并行运行的大量的计算。GHC需要-threaded参数才能支持并行，程序请按下面的方式编译：
$ ghc -O2 rpar.hs -threaded按如下方式，可以试验rpar/rpar写法，其中+RTS -N2标志告诉GHC使用双核来运行程序（请确保机器至少是双核的）：
$ ./rpar 1 +RTS -N2
time: 0.00s
(24157817,14930352)
time: 0.83s当rpar/rseq代码片断返回[7]，打印第一行时间戳，第二行时间戳则在最后的计算结束后打印。正如所看到的，代码片断是立即返回的。在rpar/rseq中，第二个计算（短的那个）完成后才返回：
$ ./rpar 2 +RTS -N2
time: 0.50s
(24157817,14930352)
time: 0.82s在rpar/rseq/rseq中，返回是在最后的：
$ ./rpar 3 +RTS -N2
time: 0.82s
(24157817,14930352)
time: 0.82s本节将分析一个实例，考察如何并行化一个程序，使之对多组输入数据执行相同的计算。该计算实现了数独求解的功能。解算器（solver）速度相当快，能在2分钟内求解所有给定了17个已知数的共49 000个谜题。
仅作为需要的对多组输入数据执行大量相同计算的例子，对于解算器如何工作的细节，这里并不感兴趣。这里进行讨论的目的是并行化解算器，使之能够同时解多个谜题。出于该目的，解算器将被当作黑盒处理。
解算器在模块Sudoku中实现，模块提供了一个函数solve，类型如下：
solve :: String -> Maybe Grid每一个数独问题都通过一个String[8]表示，该String的每个字符依次表示九宫格中一格的内容，或是空的，通过字符.表示，或是数字1～9。
函数solve返回值的类型是Maybe Grid，具体包括两种情况，无解用Nothing表示，有解则是Just g，这里g的类型是Grid。出于本例的目的，这里只对是否有解感兴趣，而对解本身（Grid）不感兴趣。
下面先从普通的串行代码开始说明。代码从文件中读取一系列数独问题，然后求解。
sudoku1.hs
import Sudoku
import Control.Exception
import System.Environment
import Data.Maybe
main :: IO ()
main = do
[f] <- getArgs -- ❶
file <- readFile f -- ❷
let puzzles = lines file -- ❸
solutions = map solve puzzles -- ❹
print (length (filter isJust solutions)) -- ❺上面这段简短的程序工作方式如下。
❶ 获取命令行参数，并要求只带一个参数，即包含输入数据的文件的文件名。
❷ 读取给定文件的内容。
❸ 将文件内容分割成行，每行一个谜题。
❹ 通过函数solve映射列表的每一行[9]，求解所有谜题。
❺ 先从列表中去除值为Nothing的元素，然后计算列表的长度，从而得出有解的谜题数量，最后将该值打印出来。即使对解本身不感兴趣，但对代码中的filter isJust还是有必要了解的：若缺少该部分代码，程序就不会对列表的元素求值，因此也就不会进行实际的求解计算（请回忆一下2.1节中length的例子）。
通过对一组样例问题的求解，可以检查程序是否正常工作。首先，编译程序：
$ ghc -O2 sudoku1.hs -rtsopts
[1 of 2] Compiling Sudoku ( Sudoku.hs, Sudoku.o )
[2 of 2] Compiling Main ( sudoku1.hs, sudoku1.o )
Linking sudoku1 ...需要记住，当目标是程序性能时，使用完整的优化（-O2）进行编译非常重要。毕竟目标是让程序运行得更快。
现在，运行程序解1000个样例问题：
$ ./sudoku1 sudoku17.1000.txt
1000这1 000个问题均有解，所以答案是1 000。但由于目的是让程序运行得更快，所以真正感兴趣的是程序运行的时间。因此，增加一些命令行参数再运行一遍：
$ ./sudoku1 sudoku17.1000.txt +RTS -s
1000
2,352,273,672 bytes allocated in the heap
38,930,720 bytes copied during GC
237,872 bytes maximum residency (14 sample(s))
84,336 bytes maximum slop
2 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 4551 colls, 0 par 0.05s 0.05s 0.0000s 0.0003s
Gen 1 14 colls, 0 par 0.00s 0.00s 0.0001s 0.0003s
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.25s ( 1.25s elapsed)
GC time 0.05s ( 0.05s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.30s ( 1.31s elapsed)
%GC time 4.1% (4.1% elapsed)
Alloc rate 1,883,309,531 bytes per MUT second
Productivity 95.9% of total user, 95.7% of total elapsed参数+RTS -s让GHC运行时系统输出上面的统计结果。对分析性能的第一步来说，这些数据特别有帮助。这些输出的细节在GHC用户指南中均有解释，但这里只对Total time（总时间）这一项特别有兴趣。总时间这项包含两个数据：程序使用的总的CPU时间和elapsed时间或wall-clock时间。由于程序是在单核处理器上运行的，所以两者基本相等（由于系统的其他的活动，有时elapsed时间会稍长一些）。
下面的代码使用并行编程，利用两个处理器核心进行计算。首先将问题列表分成两份，然后并行地对这两个部分的问题进行求解。
sudoku2.hs
main :: IO ()
main = do
[f] <- getArgs
file <- readFile f
let puzzles = lines file
(as,bs) = splitAt (length puzzles `div` 2) puzzles -- ❶
solutions = runEval $ do
as' <- rpar (force (map solve as)) -- ❷
bs' <- rpar (force (map solve bs)) -- ❸
rseq as' -- ❹
rseq bs' -- ❺
return (as' ++ bs') -- ❻
print (length (filter isJust solutions))❶ 将问题列表分为两等份（若列表长度为奇数，则两部分长度相差一）。
❷❸ 使用前一节介绍的rpar/rpar/rseq/rseq模式对两个问题列表并行求解。但是，求解过程并非是完全直接的，因为rpar仅求值生成弱首范式。若仅使用rpar（map solve as），求值过程会在列表的第一个（:）这里停住，不再继续下去，因此rpar不会产生任何实际的并行计算。整个列表及其元素均需要进行求值，而不是部分求值，因此使用了force：
force :: NFData a => a -> a函数force对其参数的整个结构进行求值，约化为范式，然后再返回。该函数在模块Control.DeepSeq中。对于NFData类，2.4节会继续讲解，现只要将其认为是一类可以求值为范式的类型即可。
使用rpar时，求值不够深入是一种常见的错误，因此，对于每一个rpar，养成思考其对应结构需要进行多少程度并行求值的习惯，会是一个不错的办法（实际上，在后面要介绍的Par monad中，设计人员在这方面做得有些过度以至于默认使用force，同样是一个常见的问题）。
❹❺ 通过使用rseq，等待两个列表求值结束。
❻ 将两个列表合并起来，形成完整的解列表。
下面运行程序，并测量并行化带来的性能提升：
$ ghc -O2 sudoku2.hs -rtsopts -threaded
[2 of 2] Compiling Main ( sudoku2.hs, sudoku2.o )
Linking sudoku2 ...程序可以使用两个核运行：
$ ./sudoku2 sudoku17.1000.txt +RTS -N2 -s
1000
2,360,292,584 bytes allocated in the heap
48,635,888 bytes copied during GC
2,604,024 bytes maximum residency (7 sample(s))
320,760 bytes maximum slop
9 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 2979 colls, 2978 par 0.11s 0.06s 0.0000s 0.0003s
Gen 1 7 colls, 7 par 0.01s 0.01s 0.0009s 0.0014s
Parallel GC work balance: 1.49 (6062998 / 4065140, ideal 2)
MUT time (elapsed) GC time (elapsed)
Task 0 (worker) : 0.81s ( 0.81s) 0.06s ( 0.06s)
Task 1 (worker) : 0.00s ( 0.88s) 0.00s ( 0.00s)
Task 2 (bound) : 0.52s ( 0.83s) 0.04s ( 0.04s)
Task 3 (worker) : 0.00s ( 0.86s) 0.02s ( 0.02s)
SPARKS: 2 (1 converted, 0 overflowed, 0 dud, 0 GC'd, 1 fizzled)
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.34s ( 0.81s elapsed)
GC time 0.12s ( 0.06s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.46s ( 0.88s elapsed)
Alloc rate 1,763,903,211 bytes per MUT second
Productivity 91.6% of total user, 152.6% of total elapsed可以注意到的是，现在总时间（Total time）显示出了CPU时间（1.46 s）和elapsed时间（0.88 s）的不同。之前，elapsed时间是1.31 s，可以计算出使用双核的加速比是 1.31/0.88 = 1.48。查看CPU时间有助于了解核心的忙碌程度，但从上面可以看到，使用多核运行程序的CPU时间经常比单核运行的wall-clock时间要长。因此使用CPU时间和wall-clock时间之比来计算加速比常令人误解（在这里是1.66 s）。所以加速比总是使用wall-clock时间之比计算。
一般来说，有多种原因导致了加速比只有1.48而没到2，并非所有的原因都受Haskell程序员控制。但在该问题中，有部分是由代码的写法造成的，可以通过ThreadScope工具诊断出来。为了使用ThreadScope剖析程序性能，需要用-eventlog标志重新编译程序，然后运行时再加+RTS -l参数。这样，程序运行时会输出一个名为sudoku2.eventlog的日志文件，供threadscope使用。
$ rm sudoku2; ghc -O2 sudoku2.hs -threaded -rtsopts -eventlog
[2 of 2] Compiling Main ( sudoku2.hs, sudoku2.o )
Linking sudoku2 ...
$ ./sudoku2 sudoku17.1000.txt +RTS -N2 -l
1000
$ threadscope sudoku2.eventlogThreadScope的性能剖析如图2-8所示，该图通过ThreadScope的“Export image”选项生成，因此只包含时间线图，而没有其他GUI部分。
图2-8 sudoku2 ThreadScope性能剖析
图2-8中x轴为时间，水平方向的3条带状图形显示程序随时间的执行情况。最上面一条是“活跃”（activity）情况，显示当时有多少核心在执行Haskell代码（而非处于空闲或垃圾回收状态）。下面的每条代表一个核心，显示该核心在此时执行什么内容。每条分成两个部分：上面的，高一些呈绿色的表示核心在执行Haskell代码；下面的，低一些的，橙色或绿色的表示核心在进行垃圾回收。
从图中可以看到，程序运行接近结束的一段时间里，只有一个核在执行程序，另一个处于空闲状态（除了GHC的并行垃圾回收器所必须的常规性垃圾回收操作）。这说明两个并行任务是不平均的：一个执行的时间比另一个要长。未充分的利用两个核心，是导致不理想的加速比的原因。
尽管问题列表被平分成两份，而且问题是偶数个，但每个问题求解花费的时间并不相同，具体的时间全都依赖数据解算器的搜索策略[10]，所以两个核心的工作负荷并不平均。
以上说明了并行化代码的一个重要原则：避免将工作划分成少量的固定数目工作块。具体有以下两个原因。
即使通过将工作划分成与核心数相同的工作块来解决第二个问题，第一个问题依然存在，即每个工作块需要处理的工作量可能不同。
对于rpar的调用次数，GHC并没有强制的要求，调用次数完全由使用者决定，系统会自动将并行工作分配到可用的核心上去。若工作划分的更细，则系统就能让全部核心维持更长时间的忙碌。
将工作进行固定的分割常被称为静态划分（static partitioning），而在运行时将较小单位的工作分配到各处理器则被称为动态划分（dynamic partitioning）。GHC已经提供了动态划分的机制，只需通过足够频繁的调用rpar来产生足够的任务，GHC就能完成动态划分并平衡工作量。
函数rpar的参数被称为spark。运行时（runtime）将spark收集到spark池，当有处理器空闲时，通过一种称为工作密取（work stealing）的技术，从spark池中取出并执行。spark可能在未来某个时刻被求值，也可能不会——均取决于是否有空闲的核心。创建spark的开销非常低：rpar函数本质上是将一个指向表达式的指针写入一个数组。
下面对数独的求解尝试动态划分。首先，将并行地应用函数于一个列表的操作抽象成一个函数parMap：
parMap :: (a -> b) -> [a] -> Eval [b]
parMap f [] = return []
parMap f (a:as) = do
b <- rpar (f a)
bs <- parMap f as
return (b:bs)函数parMap的定义类似于monad风格的map函数，不同之处在于通过rpar将函数f应用于列表元素a的计算嵌入Eval monad中。因此，函数parMap会遍历整个列表，对每个元素a，为计算f a创建一个spark，最终返回一个新的列表。当函数parMap返回时，列表中的每个元素都有一个对应的spark。现在可以并行对所有的解进行求值。
sudoku3.hs
main :: IO ()
main = do
[f] <- getArgs
file <- readFile f
let puzzles = lines file
solutions = runEval (parMap solve puzzles)
print (length (filter isJust solutions))注意到该版本和第一版的sudoku1.hs基本上完全一样，仅有的区别在于将map solve puzzles替换为了runEval（parMap solve puzzles）。
运行新版的程序，加速比进一步提升：
Total time 1.42s ( 0.72s elapsed)对应的加速比为1.31/0.72 = 1.82，接近理想的加速比2。此外，GHC运行时系统还提供了spark创建的数量：
SPARKS: 1000 (1000 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)程序运行中创建的spark正好是1000个，而且全部是converted（被转换，即在运行时确实被并行执行）的。下面是spark可能发生的其他情况。
overflowed（溢出）
dud
rpar应用于一个已被求值的表达式时，被认为是dud，该rpar将被忽略。GC’d（被垃圾回收）
fizzled
这版程序的ThreadScope性能剖析看上去比前面的好得多（见图2-9）。此外，工作分配是由运行时管理的，程序可自动适应更多处理器的情况。例如，同一个程序在8核的机器[11]上测量出了5.83的加速比。
图2-9 sudoku3 ThreadScope性能剖析
若仔细观察双核的性能剖析，可以发现在开始的一小段时间里似乎没有处理多少工作。实际上，在ThreadScope（见图2-10）里将这段时间放大，可以看到两个核心都在工作，但主要是垃圾回收，而且主要是由一个核心完成的。事实上，此时程序正在读取输入文件（惰性地），然后按行分割，再调用函数parMap，遍历这些行。将文件内容分割成行会产生大量的数据，从图中看似乎是在第二个核心上执行的。然而，可以注意到，即使分割文件是串行的，程序并未等待分割结束后才开始并行操作。当函数parMap获取到列表的第一个元素，即第一行的内容时，就创建了第一个spark。因此，在文件全部分割成行前，两个核心均已开始工作。在某种意义上，惰性求值让程序的并行程度变得更高。
图2-10 sudoku3：放大后的ThreadScope性能剖析
通过添加下面这行代码（见sudoku4.hs），可以试验强制完成行分割，然后再进行数独求解的效果：
evalute (length puzzles)函数evalate就像IO monad中的seq：该函数将其参数求值为弱首范式，然后再将其返回。
evalute ::a → IO a早期强制对行进行求值会略微降低程序的并行程度，由于行分割的过程和数独求解的过程不再有重叠，这时双核的运行时间是0.76 s。不过，这样就可以在ThreadScope里面清楚地看到串行和并行部分的边界（见图2-11）。
图2-11 sudoku4 ThreadScope性能剖析
观察上图，可以看到程序串行运行了16.7 ms，然后开始并行运行。若一个程序中包含了串行部分，就如此例，那么将不可能达到理想加速比。事实上，可以通过阿姆达尔定律来计算给定核心数时的最大加速比：
1/((1 - P) + P/N)
式中P为可并行运行的时间比例，N是可用的处理器数量。此例中，P为（0.76 − 0.0167）/ 0.76 = 0.978，最大可能的加速比是1.96。对两个处理器来说，串行部分比例太小，无法对理论最大加速比造成有效的影响。但如果有更多的处理器，假设64个，那么串行部分显得重要起来：1 /（（1−0.978）+ 0.978/64）= 26.8。不管怎样，程序中这微小的串行部分都会将64核运行的加速比限制在26.8。事实上，即使是1024核，也仅能达到44左右的加速比，而且无论用多少核，加速比也无法达到46。从阿姆达尔定律可以看出，不但随着核心数的增加，并行加速变得更加困难，而且存在一个理论的最大并行度。
前面已经用过了force函数，其具体类型如下：
force :: NFData a => a -> a函数force会对其参数完全求值，然后返回。不过该函数并非内建，而是针对每种数据类型，通过NFData类对该函数的行为进行定义。NFData的意思是范式数据（normal-form data），其中范式是指不包含未被求值子表达式的值，“数据”则表示范式中不包含函数，因为无法看到函数里面的内容并对里面的内容求值[12]。
类NFData仅包含一个方法：
class NFData a where
rnf :: a -> ()
rnf a = a `seq` ()函数rnf名字的意思是“约化为范式”（reduce to normal-form）。该函数对其参数完全求值，然后返回()。默认通过seq来实现，对于没有子结构的类型来说很方便，只需使用默认定义即可。例如：Bool的实例可以简单地定义：
instance NFData Bool模块Control.Deepseq对库中所有其他的常见类型均提供了实例。
对于自定义的类型，可能需要实现相应的NFData的实例。例如，对于二叉树类型：
data Tree a = Empty | Branch (Tree a) a (Tree a)那么，其NFData的实例如下：
instance NFData a => NFData (Tree a) where
rnf Empty = ()
rnf (Branch l a r) = rnf l `seq` rnf a `seq` rnf r实现的思路为递归地对数据类型的组成部分应用rnf，然后将这些rnf的调用通过seq组合起来。
Control.DeepSeq模块中还有一些其他运算，例如：
deepseq :: NFData a => a -> b -> b
deepseq a b = rnf a `seq` b函数deepseq因其和seq的相似性而得名：和seq类似，都是强制求值。如果把弱首范式看成是浅（shallow）求值，那么范式就是深（deep）求值，因此得名deepseq。
函数force是通过deepseq定义的：
force :: NFData a => a -> a
force x = x `deepseq` x函数force的功能应该被认为是将WHNF转换为NF（normal form），也就是，当程序将force x求值成WHNF时，x会被求值成NF。
将表达式求值为范式需要对整个数据结构进行遍历，因此需要铭记，对于大小为n的数据结构，其复杂度是O(n)，而对
seq来说，只有O(1)。因此，应该避免对同一数据反复使用force或deepseq函数。
WHNF和NF就像天平的两端，但是，根据数据类型的不同，还有许多处于中间的“不同程度的求值”。例如：前面的length函数对列表的脊（spine）求值，即展开了列表，但未对列表的元素求值。parallel包中的模块Control.Seq提供了一系列组合子，通过组合，可以对数据结构达到不同程度的求值。本书虽然不会在例子中使用这些运算，但对读者也许会有所帮助。
[1] Monad中文译为单子。——译者注
[2] weak head normal form，函数式编程中的一种范式。——译者注
[3] 技术上说，这并不正确。Haskell实际上是一门非严格（non-strict）的语言，惰性求值只是几种正确的实现策略之一。不过GHC使用的是惰性求值，因此这里忽略这个技术细节。
[4] 严格地说，是被一个到该值的间接引用所覆盖，不过这些细节在这里并不重要。感兴趣的读者可以到GHC wiki上阅读关于该实现的文档，以及许多关于该设计的论文。
[5] 即弱首范式英文weak head normal form的首字母缩写。——译者注
[6] 即表达式里面所有的部分、各层次均被求值，不存在未求值的部分。——译者注
[7] 这里指的是包含rpar和rseq的代码片断，而非rpar/rseq模式。——译者注
[8] 即字符串。——译者注
[9] 映射的原文为map，即对列表的每个元素应用函数solve。——译者注
[10] 实际上，输入的样例问题是经过排序的，使得能够清楚地示范这个问题。
[11] 机器是Amazon EC2 High-CPU extra-large实例。
[12] 不过，纯粹为了方便，定义了一个函数的NFData实例，会将函数求值为WHNF（弱首范式），因为经常会有数据结构里面包含函数，而尽管如此，还是想尽可能地对这样的数据结构进行求值。
