作者：[英]Simon Marlow 著
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
Haskell并行与并发编程试读：
前言
作为一名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》（剑桥大学出版[1]社）、《Learn You a Haskell for Greate Good》（No Starch Press）或者《Haskell：The Craft of Functional Programming》（Addison-Wesley），应该是一个很好的开始。如何阅读本书
本书的主要目标是让读者能够进行并行与并发Haskell编程。但是，正如你大概已经知道的，学习编程并非是单独看书就可以的。这正是本书的编写刻意切合实际，包含大量的可以运行、修改和扩展的例子的原因所在。书中有几章包含了练习，建议读者尝试，通过这些练习可以熟悉该章介绍的主题，本人强烈推荐做一些练习，或按自己的想法写些代码。
在探讨本书的主题时，我不会回避陷阱和系统中不完善的部分。Haskell已经发展了20多年，但其在今天的发展比以往任何时刻都更为迅速。因此自然会遇到一些不一致情况和系统中不那么好的部分。本书涉及的一些主题是新近发展起来的：第4、5、6和14章涉及了一些最近几年开发的框架。
本书包含两个基本独立的部分，第一部分和第二部分。读者可以随意从一部分开始阅读，或者在两部分间切换着阅读（也就是并发地阅读两部分）。两部分中仅有一处存在依赖关系：如果先阅读了第一部分，那么将更容易理解第13章，尤其是在13.2.5节前，应该先读第4章。
尽管两部分是基本独立的，但同一部分内的各章还是应按顺序阅读。本书并非是参考书，书中包含的一些可运行的例子和主题是贯穿数章开发和发展出来的。本书的排版约定
本书使用如下排版约定。● 楷体：用于强调、新术语。● 等宽字体：表示变量、函数、类型、参数、对象以及其他的程序
构成部分。此图标表示一个小技巧、建议或者一般性注释。此图标表示需要警惕的陷阱，一般是一些不那么明显的情况。
代码示例如下：timetable1.hssearch :: ( 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趣学指南》已由人民邮电出版社出版。——编者注第1章 绪论
长久以来，编程社区已熟知线程和锁难以使用。即使很简单的问题也常常需要过高的专业技能，而且会导致难以诊断的故障。然而，线程和锁依然十分通用，从并行图像处理到并发Web服务器，足以表达出所需要编写的任何内容，并且有一个专一的通用API也有不可否认的好处。但是，若想让并行和并发编程变得更容易，就要接受“不同的问题要用不同的工具解决”的思想，一种工具无法解决所有的问题。图像处理可以自然地表达成并行矩阵运算，而线程则很好地适用于并发Web服务器的情况。
因此在Haskell中，我们的目标是尽可能为多种工作提供正确的工具。若发现一项工作在Haskell中没有正确的对应工具，则会尝试找出一种方法将其制造出来。工具的多样化不可避免会带来负面影响，即需要大量的学习，而这正是本书所要进行讲解的。在本书中，将会讨论如何用Haskell编写并行和并发程序，从简单地利用并行来加速计算密集型程序，到使用轻量级线程编写高速并发的网络服务程序。在这个过程中，还将会看到如何使用Haskell编写程序，让其运行在现代图形显卡中强大的处理器（GPU）上，也会看到如何编写程序，使之能够在网络中的多台机器上运行（分布式编程）。
这并非说本人打算对每一种最新出现的试验性编程模型都进行介绍。若仔细查看Hackage上的软件包，可以发现各式各样用于并行和并发编程的库，其中许多是为了特定目的而开发的，更不用说所有的未到实用阶段的研究性项目。在本书中，我将重点关注现在已能用来完成工作，足够稳定，并在生产中可信赖的API。此外，本人的目标是让读者牢固地掌握最底层的工作原理，以便在需要的时候能够在此之上搭建出自己的抽象结构。1.1 术语：并行性和并发性
在许多领域并行和并发是同义词，但在编程中则不然，它们被用来描述在根本上完全不同的两个概念。
并行程序是指使用多个硬件参与计算（如多个处理器核心）使之更快的程序。目标是通过将计算的不同部分分配给不同的处理器，使之能够同时执行，从而更早得到问题的答案。
与之相对的，并发则是一种包含多个控制线程的程序构成技术。从概念上说，这些控制线程是“同时”被执行的，也就是说，用户所观察到的最终影响，是由这些线程交替作用产生的。到底是否真的是同时执行则属于实现上的细节。并发程序可以通过交替的方式在单个处理器上执行，或在多个物理处理器上执行。
并行编程仅关注效率，而并发编程则关注程序的构成，使之能够和多个独立的外部媒介交互（如用户、数据库或一些外部客户）。并发性使得这类程序能够模块化，和用户交互的线程可以明确地区分于和数据库通信的线程。在没有并发的情况下，这类程序必须通过事件循环和回调的方式编写，与线程所提供的相比，通常更加低效且模块化不足。
在纯函数式的程序中，“控制线程”这个概念是没有意义的，因为没有需要观测的效果，而且程序的结果也和求值的顺序无关。因此，并发性是用于构成产生效果的代码的技术；在Haskell中，即IO monad中的代码。
一个与之相关的内容是确定性和非确定性编程模型的区分。确定性编程模型中每个程序只会给出一个结果，而非确定性编程模型则容许——取决于执行时某些情况——程序可以有不同的结果。由于必须和外部媒介交互，而这些交互会导致事件在不可预测的时刻发生，所以并发编程模型必然是非确定性的。而非确定性有一些显著的缺点：程序将会变得非常难以测试和推断。
对于并行编程来说，应尽可能地使用确定性编程模型。既然目标仅仅是更快地获得答案，那么还是不要让程序在这个过程中变得更难调试。确定性并行编程是这两方面的最佳结合：测试、调试和推断可以以顺序的方式执行，但加入更多处理器后程序则能运行得更快。事实上，大多数计算机处理器自身通过流水线和多个执行单元的形式实现了确定性并行。
虽然可以使用并发的方式实现并行编程，但这通常不是一个明智的选择，因为并发的使用牺牲了确定性。在Haskell中，大多数的并行编程模型都是确定性的。然而，注意到确定性编程模型并不足以表达所有的并行算法是非常重要的，有些算法是依赖于内部不确定性的，特别是要对解空间进行搜索的问题。此外，有时希望并行化确实有副作用的程序，那就别无选择，只能使用非确定性并行编程或并发编程了。
最后，希望在同一个程序中混合使用并行和并发编程是完全合理的。大多数的交互式程序需要使用并发来维持一个快速响应的用户界面，与此同时在后台执行计算密集型的任务。1.2 工具和资源
为了运行本书中的范例程序和完成练习，需要安装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）。
阅读本书时，建议读者手上备有以下文档。● GHC用户指南（http://www.haskell.org/ghc/docs/latest/html/
users_guide/）。● Haskell Platform的库文档，可以在Haskell Platform的主网站（http://www.haskell.org/platform/）上找到。任何本书中没有特别
说明的类型或函数的文档都可以在那里找到。● Haskell Platform外的软件包文档，可在Hackage（http://
hackage.haskell.org/）上找到。若要搜索特定函数或类型的文档，
可以使用Hoogle（http://www.haskell.org/hoogle/）。
需要注意的是，本书用到的大多数API都不属于Haskell 2010标准。这些API由附加软件包提供，其中有一些包含在Haskell Platform中，而其余的可以在Hackage上找到。1.3 示例代码[1]
示例代码被收集整理为parconc-examples软件包放在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
如今，处理器制造商基本放弃了对单处理器性能提升的努力，转而将注意力集中到提供更多数量的处理器上。而并行技术能利用额外的核心，因此能使程序性能得到最大的提升。而并行Haskell的目标就在于提供一种自然而稳健的方式对多个处理器进行访问。
读者也许想知道编译器能否自动将程序并行化。毕竟，纯函数式[1]语言中的计算之间仅有数据依赖关系，很大程度上清晰明了，因此可以轻易地进行分析，所以纯函数语言的自动并行化应该相对容易些。但是，即使是纯函数式语言，自动并行化仍被一个由来已久的问题所阻扰：为了让程序运行得更快，通过并行提升的性能应至少抵消由此引入的额外开销，而在这方面，编译时（compile-time）分析并不能做出很好的判断。一种替代的方法是通过运行时的性能剖析找到优秀的并行化候选方法，然后将这些信息反馈回编译器。即使这样，在实际中该方法也并没有很成功。
全自动并行化依旧不切实际。然而，Haskell提供的并行编程模型成功地消除了一些传统上与并行编程相关的乏味和易于出错的部分。● Haskell中的并行编程是确定性的：无论在多少个处理器上运
行，并行程序总是产生相同的结果。因此，在调试并行程序时，
不必真的并行运行。此外，程序员有信心在并行化一个程序后，
不会引入难以通过测试消除的潜在竞争情况或死锁。● 并行Haskell程序是高级的和陈述性的，无需显式地处理诸如同
步或通信的概念。程序员只需指出需要并行执行的位置，实际上
并行运行程序的细节则交给运行时系统。这既有好的一面，也有
不足。● 通过更少的操作细节表达，使并行Haskell程序更为抽象，因此可能在广泛的并行硬件上运行。● 并行Haskell程序可以利用现有的运行时系统中，诸如并行垃圾回收这样，经过高度优化的技术。此外，未来运行时改善时，程序不需要额外的修改即可受益。● 隐藏大量的执行细节，性能方面的问题可能会难以理解。而且，并行Haskell中程序员对程序的可控性比低级的编程语言差，因此性能问题的解决可能非常棘手。事实上，并不限于并行Hasekll，对于任何尝试优化Haskell程序的人来说，这个问题都非常熟悉。在本书中，本人希望能示范如何识别和变通地解决在实际中出现的最为常见的问题。
并行Haskell程序员主要需要思考的问题是划分（partitioning）：将问题分成几个可以独立计算的部分。理想的情况是，希望有足够的任务让所有处理器保持忙碌。然而，这样的努力会受到以下两方面的阻扰。
粒度（granularity）
若任务太小，则管理任务带来的开销会超过任何并行运行这些任
务所带来的益处。因此，任务的粒度应足够大，使得额外开销显
得很小。但又不能太大，因为这可能会造成任务不足，而存在无
法让所有的处理器都保持忙碌状态的风险，尤其是在执行接近结
束，剩下的任务不多的时候。
数据依赖（data dependencies）
当一个任务依赖于另一个时，两者必须串行执行。本书中的前两
个编程模型采取了不同的途径处理数据依赖：在第3章，数据依
赖完全是隐式的，而在第4章，数据依赖则是显式的。使用显式
数据依赖进行编程不够简洁，但采用不隐藏的数据依赖关系的方
式则更易于程序的理解和问题的修复。
下面各章将会对Haskell提供的多种并行编程模型进行描述。● 第2章和第3章介绍Eval monad和求值策略，适用于表达非数值
密集并且不基于数组的Haskell程序的并行性。这些编程模型都
切实可行，有许多成功并行化的优秀例子。● 第4章介绍Par monad这一更新的编程模型。该编程模型的目标
同样在于并行化普通的Haskell代码，但采用了不同的折中：通
过牺牲部分求值策略的简洁性和模块性来换取程序员对程序的更
大可控性。[2]● 第5章着眼于Repa库，该库提供了丰富的组合子用于搭建并行
数组计算。通过组合数个简单的运算，可以表达出复杂的数组算
法，并且该库会通过一种名为融合（fusion）的技术将计算组合
优化为单遍（single-pass）的算法。此外，该库的实现会针对可
用的处理器自动并行化运算。● 第6章讨论使用Acellerate库进行图形处理器（GPU）编程，该库
提供的编程模型和Repa类似，但直接在GPU上进行运算。
并行化Haskell代码可以是令人愉快的经历：在程序中添加一小段注解（annotation），使之能在多核机器上的运行速度提升几倍。也可能令人沮丧，正如下面几章将会看到的，遇到许多陷阱。其中一些是Haskell特有的，一些则是任何语言都会碰到的。但愿在最后对于并行编程，读者能够建立起足够的直觉，通过使用书中的这些的技术，可以让自己的程序获得足够的并行加速比。
在阅读本书的部分内容时务必牢记，由于当今计算设备非常复杂，性能依赖于大量互相影响的组件，获得可靠的并行性能数据在本质上是困难的。出于这个原因，在本人电脑上运行范例得到的结果可能和在读者的硬件上运行的结果有所不同。希望差别不大，否则可能表明GHC中存在问题，对此应该向GHC项目汇报。重要的是察觉到性能的不确定性，尤其是在牵涉到并行性的时候。
[1] 即每个计算之间，依赖关系仅由参与运算的数据决定的，不像非纯函数式语言中，程序中的后一条语句可能依赖于前一条语句。——译者注
[2] combinator，指不包含自由变量的函数。——译者注[1]第2章 并行基础：Eval Monad
本章将讲授在Haskell代码中使用并行编程技术的基础。首先将介绍一些关于惰性求值的必要背景，然后在2.2节讲解如何进行并行编程。[2]2.1 惰性求值和弱首范式
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 xx = _
特殊符号_表示“未求值的”，对于这种情况，读者也许听过另一个词“thunk”，即内存中表示1 + 2这个未求值计算的对象。此例中的thunk如图2-1所示。图2-1 表示1 + 2的thunk
在图中，x是一个指向内存对象的指针，该内存对象表示函数+应用于整数1和2。
该thunk表示x将在其值需要时被求值。在GHCi中，触发求值最容易的方法是将其打印出来，也就是说，在提示符后输入x即可：Prelude> x3
现在若通过:sprint查看x的值，可以发现其已被求值：Prelude> :sprint xx = 3
从内存中的对象方面考虑，即表示1 + 2的thunk实际上被（装箱[4]的）整数3覆盖了。因此，以后任何对x值的查询都会立即返回结果，这就是惰性求值的工作原理。
前面的例子比较简单，再试一个稍为复杂的的示例：Prelude> let x = 1 + 2 :: IntPrelude> let y = x + 1Prelude> :sprint xx = _Prelude> :sprint yy = _
这里再次将变量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 xx = 3Prelude> :sprint yy = 4
正如所预期的，两者均已被求值。因此，到目前为止一般性的原则如下。● 定义一个表达值会建立一个thunk来表示该表达式。● 在需要其值前，thunk保持未求值状态。一旦被求值，则会被求
出的值所替代。
再看一下增加一个数据结构会发生什么情况：Prelude> let x = 1 + 2 :: IntPrelude> let z = (x,x)
变量z绑定到了序对（x，x），命令:sprint显示出一些有意思的内容：Prelude> :sprint zz = (_,_)
这里隐含的结构如图2-3所示。图2-3 两项引用同一thunk的序对
变量z本身引用了序对（x，x），但序对的两项均指向了未求值的，代表x的thunk。这说明数据结构可以使用未求值的表达式来构建。
下面再次将z变为thunk：Prelude> import Data.TuplePrelude Data.Tuple> let z = swap (x,x+1)
函数swap的定义为：swap（a，b）=（b，a）。这次z和前面的一样，是未求值的：Prelude Data.Tuple> :sprint zz = _
这样的话，当使用seq来对z求值时，就能看清楚具体发生的情况：Prelude Data.Tuple> seq z ()()Prelude Data.Tuple> :sprint zz = (_,_)
函数seq执行后，导致作为参数的z被求值，成为一个序对，但序对的两项仍然处于未求值状态。函数seq仅对其第一个参数的第一层构造求值，不再对剩下的结构继续求值。对此有一个专门的称呼：称函数seq对第一个参数求值，使之成为弱首范式（weak head normal form）。该术语的使用是出于历史原因，因此对其不必深究。该术语[5][6]常被缩写为WHNF。名词范式在这里是“完全求值”的意思，在2.4节会看到如何将表达式求值使之成为范式。
弱首范式的概念在下面两章会多次出现，因此值得去花些时间去理解这个概念，并对Haskell中求值是如何发生的有所体会。对此在GHCi中试验不同的表达式和:sprint命令不失为一种很好的方法。
为了完成本例，下面对x进行求值：Prelude Data.Tuple> seq x ()()
此时z会是何值？Prelude Data.Tuple> :sprint zz = (_,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 xsxs = _
接着对该列表求值，使之成为弱首范式：Prelude> seq xs ()()Prelude> :sprint xsxs = _ : _
目前为止，只知道xs是一个至少包含一个元素的列表。接着，对该列表应用length函数：Prelude> length xs10
函数length的定义如下：length :: [a] -> Intlength [] = 0length (_:xs) = 1 + length xs
注意到length会忽略列表的头，而只对列表的尾xs进行递归，因而对列表应用length时，列表的结构会被展开，但元素不会被求值。这点通过:sprint可以清楚地看到：Prelude> :sprint xsxs = [_,_,_,_,_,_,_,_,_,_]
GHCi注意到列表已被展开，所以改用方括号显示列表，而不再使用:。
即使通过求值的方式展开了整个列表，该列表仍不是范式（而仍然是弱首范式）。通过对列表应用一个函数，该函数需要使用列表的所有元素，就可以使之完全求值。例如sum函数：Prelude> sum xs65Prelude> :sprint xsxs = [2,3,4,5,6,7,8,9,10,11]
前面这些讨论，对于惰性求值这个精妙而复杂的主题仅触及了表面。幸运的是，多数情况下，编写Haskell代码无需了解或担心求值是何时进行的。的确，Haskell语言定义十分仔细，不对如何求值作明确指定；语言的实现可以自由地选择策略，只需保证结果正确。这也是程序员大多数时候所关注的。但是，当编写并行代码时，了解表达式何时被求值变得重要起来，因为只有这样才能对并行化计算进行安排。
第4章使用Par monad，对数据流进行明确的描述，是另一种使用惰性求值进行并行编程的方法。该方法牺牲了部分简洁性从而避免了一些惰性求值相关的微妙的问题。由于会出现一种方法比另一种解决问题更自然或更高效的情况，因此两种方法都值得学习。2.2 Eval monad、rpar和rseq
下面介绍模块Control.Parallel.Strategies提供的用于并行编程的一些基本内容，定义如下：data Eval ainstance Monad EvalrunEval :: Eval a -> arpar :: a -> Eval arseq :: 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/rparrunEval $ 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/rseqrunEval $ 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/rseqrunEval $ 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都完成求值后才返回。
对使用的模式，应如何选择？● 由于程序员很少会提前知道哪个计算最耗时，因此在两个计算中
任意等待一个是毫无道理的，所以rpar/rseq的模式不太有用。● 对于rpar/rpar和rpar/rseq/rseq两种模式的选择，则视具体情况而
定。如果期望尽早开始更多的并行计算，而且返回值不依赖任何
运算的结果，那么使用rpar/rpar是合理的。反而言之，如果所有
可能的并行计算都已经开始了，或下面的代码需要用到其中一个
运算的结果，那么显然应该使用rpar/rseq/rseq。
下面是最后一种写法。例2-4 rpar/rpar/rseq/rseqrunEval $ 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 -N2time: 0.00s(24157817,14930352)time: 0.83s[7]
当rpar/rseq代码片断返回，打印第一行时间戳，第二行时间戳则在最后的计算结束后打印。正如所看到的，代码片断是立即返回的。在rpar/rseq中，第二个计算（短的那个）完成后才返回：$ ./rpar 2 +RTS -N2time: 0.50s(24157817,14930352)time: 0.82s
在rpar/rseq/rseq中，返回是在最后的：$ ./rpar 3 +RTS -N2time: 0.82s(24157817,14930352)time: 0.82s2.3 示例：并行化数独解算器
本节将分析一个实例，考察如何并行化一个程序，使之对多组输入数据执行相同的计算。该计算实现了数独求解的功能。解算器（solver）速度相当快，能在2分钟内求解所有给定了17个已知数的共49 000个谜题。
仅作为需要的对多组输入数据执行大量相同计算的例子，对于解算器如何工作的细节，这里并不感兴趣。这里进行讨论的目的是并行化解算器，使之能够同时解多个谜题。出于该目的，解算器将被当作黑盒处理。
解算器在模块Sudoku中实现，模块提供了一个函数solve，类型如下：solve :: String -> Maybe Grid[8]
每一个数独问题都通过一个String表示，该String的每个字符依次表示九宫格中一格的内容，或是空的，通过字符.表示，或是数字1～9。
函数solve返回值的类型是Maybe Grid，具体包括两种情况，无解用Nothing表示，有解则是Just g，这里g的类型是Grid。出于本例的目的，这里只对是否有解感兴趣，而对解本身（Grid）不感兴趣。
下面先从普通的串行代码开始说明。代码从文件中读取一系列数独问题，然后求解。
sudoku1.hsimport Sudokuimport Control.Exceptionimport System.Environmentimport Data.Maybemain :: IO () main = do [f] <- getArgs -- ❶ file <- readFile f -- ❷ let puzzles = lines file -- ❸ solutions = map solve puzzles -- ❹ print (length (filter isJust solutions)) -- ❺
上面这段简短的程序工作方式如下。
❶ 获取命令行参数，并要求只带一个参数，即包含输入数据的文件的文件名。
❷ 读取给定文件的内容。
❸ 将文件内容分割成行，每行一个谜题。[9]
❹ 通过函数solve映射列表的每一行，求解所有谜题。
❺ 先从列表中去除值为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.txt1000
这1 000个问题均有解，所以答案是1 000。但由于目的是让程序运行得更快，所以真正感兴趣的是程序运行的时间。因此，增加一些命令行参数再运行一遍：$ ./sudoku1 sudoku17.1000.txt +RTS -s1000 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.0003sINIT 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 secondProductivity 95.9% of total user, 95.7% of total elapsed
参数+RTS -s让GHC运行时系统输出上面的统计结果。对分析性能的第一步来说，这些数据特别有帮助。这些输出的细节在GHC用户指南中均有解释，但这里只对Total time（总时间）这一项特别有兴趣。总时间这项包含两个数据：程序使用的总的CPU时间和elapsed时间或wall-clock时间。由于程序是在单核处理器上运行的，所以两者基本相等（由于系统的其他的活动，有时elapsed时间会稍长一些）。
下面的代码使用并行编程，利用两个处理器核心进行计算。首先将问题列表分成两份，然后并行地对这两个部分的问题进行求解。
sudoku2.hsmain :: 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
试读结束[说明：试读内容隐藏了图片]