Joe Duffy 谈论安全并行机制的唯一性和不可变性引用

我们近期采访了《Concurrent Programming on Windows》一书的作者 Joe Duffy，谈到了他在使用类型系统以确保安全并发方面的研究成果。这部分成果已经发表在一篇名为《Uniqueness and Reference Immutability for Safe Parallelism》（安全并行机制的唯一性和不可变性引用）的论文里。此次访问的缘由，是由于对这项研究项目的内容看起来还普遍存在着一些误解。

InfoQ：人们对你的研究工作存在着怎样的误解？

Joe：首先我想说，我对于来自社区的反馈和计论表示由衷的感谢，这也是我们选择在社区内首先发表论文的重要原因。总体来说效果非常好，我也期望我的团队能在今后几年陆续发表更多的内容，多年的辛勤工作能得到公众的认可，这实在太棒了。

是的，我确实认为对这篇论文存在着一些普遍的误解。但这也是可以预期的，因为这部分的研究内容比较新颖，而且许多与之相关的研究论文都没有事先将问题的上下文说明清楚。

· “隐式并行是不可能的，你们的尝试只会徒劳无功。”

这句话是在假设我们的主要目标是要实现隐式并行。但正如我在博客中所解释的一样，这并不是我们的主要动力。这种假设确实很诱人，而我也很高兴我们已经在某些受限条件下实现了这一点，但是类型系统的应用范围远远不只这一点。

无论好坏，我已经充分地了解了几个世纪以来在自动并行以及相关的自动向量化方面的努力成果，在我职业生涯的大部分时间都致力于对它们以及相关问题的研究。不幸的是，我自己也和许多其它研究者一样遇到了同样的障碍。基于经典的 C 语言形式编写的典型的控制流程驱动的程序是无法完美地实现并行自动化的，相比于经过手动调整的并行程序而言更是如此。当然，确实存在着某些可能性和有效的技术，但他们的应用面广泛度还不足以完全改变这个游戏的局面。

而我的工作目标之一，就是让程序员们可以用他们的方式创建大型的复杂系统，例如操作系统、web 服务器以及设备驱动。他们可以出于效率的考虑使用类 c 的老式语言结构，比如简单的 for 循环，可变数组及位域，并在需要时能够受益于安全并行、隔离以及不可变性。对可变数据结构的 for 循环会被重新组织，以实现数据并行。这里的关键并不在于结构重新组织的完全自动化，而是类型系统可以保证它的安全性。这种重构在结构上是不会产生竞态条件或死锁的。

顺便说一下，另一种不同的反应是“隐式并行是我们的救世主！摩尔定律又回来了！”。这种观点虽然比较积极正面，但也是错的。并行确实在这个系统中变得简单了，但它还是有代价的。

· “这些工作之前就有人完成了：看看 Haskell，Rust 这些吧”

当今的语言设计和 30 年前已经有所不同了，要创建一个成功的语言，你很可能会从过去的语言中吸取众多优点，然后再提供一个良好且易用的语法，并提供优秀的框架和工具，以此形成你的独特价值。我毫不怀疑在我们的论文中体现了很多聪明的想法，例如在隔离状态和不可变状态之间进行转换的简单性，而且非常自然地实现了许多 C# 程序员编写的代码（例如：使用“建造者”（builder）模式以实现不可变状态），但我依然很感谢先辈们的工作对我们的影响。

Haskell 对我们的工作确实有着极大的启示作用，对此我第一个举手表示赞同。这一项工作的最初想法，实际上是由于我在考虑，对于一个 Haskell 的纯函数式方式及其 state monad 的等价物来说，如果我们将其开放，它会变成什么样子。换句话说，让我们试着把一个纯函数式程序语言嵌入到另一个可变的命令式语言中。由于当时我工作于 CLR 与.NET Framework 平台，因此 C# 就是一个自然的着手点。我对这一点从不掩饰。实际上，这些年来我一直和一些 Haskell 的原设计者们保持交流。

我也很喜欢 Rust，能公开地看到他们的工作进展实在是很棒。

也就是说，就像 Haskell 和 Rust 包括了许多其它语言没有的优秀想法一样，我们的成果也有着它们不具备的某些东西。实际上，每个人都是站在巨人的肩膀上，这是计算机科学，乃至整个科学界的普遍现象。没什么值得羞愧的 – 这是一件美妙的事。

· “没有人需要可变的命令式代码了，使用函数式编程就够了。”

我同意某些团队和问题领域是适合使用纯函数式编程的，尤其是对于科学问题来说更是如此。不过，如果我们说的是 Haskell 之外的其它函数式语言，那这一说法就完全违背论文中的一个重要观点了。

LISP、Scheme、ML、O’Caml 和 F# 这些语言，是“不鼓励”你使用可变状态的。但如果你真的愿意，你还是可以这么做。而且这种可变性虽然可以从数据结构的注解中看到，但对程序的整体分析过程而言是不可见的。这包括了过程间的契约，例如某个方法是否会改变状态，以及改变为何种状态。简单地说，我无法单凭某个映射方法的参数，就断定这个方法在并行运行时是否能够避免竞态条件。当然，在 Haskell 中可以做到这一点，这多亏了它的 monad 的概念（先不考虑 unsafePerformIO）。

当然，对类 C 编程语言来说，如 C、C++、Java 和 C#，情况要糟得多。它不鼓励你编写不可变的、无副作用的代码，而且即使在你决定这么做后，你也显然得不到任何类型系统的支持。我猜 C++ 程序员可能会把“const”当作一线希望，但对它的使用并没有一致的认同，何况它也可以被轻易地转型。

在我们的系统中有一个关键性的不同之处，我们采用了函数式语言的方式，鼓励使用不可变性和无副作用编程，但允许你出于便利性或效率的考虑进行选择。而一旦你选择了这种方式，类型系统就会明确地知道，想要欺骗类型系统是绝对做不到的。我们也有与 unsafePerformIO 类似的实现，但不允许第三方直接调用它，而是创建了一个安全的抽象，它有着记忆功能，能够将不安全性封装起来并缓存。

最终，你将得到一种真正安全的并行编程体验，而且不仅仅限于并行。由于消息传递的交叉存储，使得 Erlang 总是受困于竞态问题。而类型系统中同样的技术则可以实现安全的消息传递。

许多读者其实都没有抓住这一点：在类型系统里你可以充分利用命令式编程，也可以充分利用函数式编程，而且他们之间能够无缝地接合在一起。

InfoQ：你刚才说到你提供了一个受限版本的 unsafePerformIO，你能详细地说明一下你怎样使用它吗？

Joe：最重要的一点是，我们不会将它开放给第三方，就像我们不会把 C# 中的“unsafe”开放给第三方一样。

反之，我们在构建系统的时候则使用到了这一功能。在某些不为人知的地方，我们需要“欺骗”系统，但在这样做的时候，我们依然充分尊重系统中的那些金科玉律。我记得 Tony Hoare 把它叫做“善意的副作用”，他的意思是确实有副作用产生，但在它们所发生的这一层面是不会被外界所观察到的。说它是善意的，是因为它的实现有着良好的作用，而且并未违反系统的整体原则。

举例来说，有一些并行框架会在并行的工作者之间将各自的状态以别名的方式暴露出来，这就在技术上破坏了语言的隔离性规则，并因此产生了副作用。而我们所创建的 API 则充分遵循了这些规则，例如在同时并行处理时，不会有任何可见的可变状态；隔离状态始终保持隔离，诸如此类。记忆体（memoization）是另一类抽象方式，这是指我们为延迟解析、缓存及记忆状态等操作提供了标准的抽象类库。最后一点，我们发现使用这些技术也能简化“只写”的一些抽象实现，例如事件或性能计数器等等。

我们的理论是，我们需要支持的模式数量是有限的，而且随着时间推移，我们发觉对这些模式的使用在收缩，而并非不断增长。验证这些模式的实现安全性毫无疑问是十分重要的，因为在这些地方的任何一个错误就意味着在整个类型安全系统中打开了一个缺口，就如 C# 中的“unsafe”一样。我们认真地检查了每一项内容，考虑到在这种情况下基本上没有类型检查功能，我们甚至为“安全”一词进行了重新定义。我很乐于在今后对验证功能展开进一步的研究工作，相比于基于子类型的强壮的类型系统而言，对于这些插入式技术的验证还远远谈不上方便、简洁和稳定。

InfoQ：这一研究的许多方面看起来与代码契约（Code Contract）项目能够良好地整合，尤其是与 Pure属性等方面。你是否有看过这方面的内容？

Joe：这一点提的非常好。

我们的语言按照 Eiffel 和 Spec# 的内容，对契约提供了第 1 等的支持。这门语言也应用了它固有的对副作用的了解，确保了这些契约是无副作用的。

回到我刚开始创建这个类型系统的时候，我曾经粗略地设计了一些东西，它与.NET 中的 [Pure] 属性很相似。但是当开始在代码中做一些真正有趣的事时，你很快就会遇到一些局限。我最喜欢的一个例子就是迭代，如果我有一个不可变的列表，那我所获得的迭代器必须是可变的，因为我需要对它执行 MoveNext 操作，并且它需要知道如何映射成不可变的元素。如果没有一个完整的类型系统，你会发觉你的工作处处受限，举步维艰。

InfoQ：你认为这个项目中是否有哪方面是比较罕见的，或是独一无二的？

Joe：我比较诧异的是，在结合函数式与命令式编程方面，我们本应该看到更多的应用。确实，像 F# 这样的语言，或者说近 30 年来其它主要的函数式语言，它们提供给你改变状态的功能，甚至有些语言还能够提供类 C 语言的流程控制语法。但这种状态改变在类型系统中的追踪方式很难进行符号性分析，也难以实现由类型决定的不同的行为。

Haskell 当然实现了这一点，这多亏了 monad，但出于一些其它原因，许多主流开发者选择了避免使用 Haskell，其中很大原因是一些表面层的东西，例如语法。

我认为，在我们的语言中可以真正地实现无副作用的方法，这一事实改变了整个游戏。我可以对 LINQ 操作符进行重载，由于可以保证无副作用产生，这使得它可以实现自动并行运行。由于延迟解析的存在以及缺乏解析顺序的保证，使得查询结果通常很难推导出结果，由于这一原因，实际上无副作用的查询更加常见，这也符合 SQL 的惯例。因此这个系统不仅只为了并行存在，它也指导程序员使用安全的模式。另外，对那些需要在 LINQ 查询中进行状态转换操作的开发者，我们也提供了相应的重载。

这些模式在整个框架设计中随处可见，只要想一下排序的比较就明白了。

我认为整个项目中最有趣的一部分，是我们用这门语言编写了一个完整的操作系统，在语言本身与应用方面同时进行创新。有一种常见的现象是，语言的创造经常是凭空产生的，需要经过一段长时间的使用才知道哪些方面是好用的，再去调整那些不好用的方面。这个过程需要一段很长的时间，你需要把新东西发布给用户，等待他们做出一些东西，再从他们那边获取反馈。我们采取的方式则能够立刻看到各种问题。使用这种方法工作了几年之后，我很难再想象回到过去的方式了。这一方式不仅仅针对语言，对整个开发平台都是通用的。

InfoQ：你编写了一个完整的操作系统？如果只是为了证实一个类型系统的有效性，这未免有点搞得太大了，是什么促使你和你的同事接下了这个项目？

Joe：实际上是先有这个操作系统的，我们只是随着时间的推移感觉到，要真正达到我们的目标，需要对语言作出创新。编写一个完整的系统是感觉很棒的。

InfoQ：除了将可变状态与其它代码分离这一想法之外，还有哪些方面是你们想从 Haskell中吸收的呢？

Joe：Haskell 可以说是促进了这个类型系统产生的原始动力。

很难指出有其它哪部分内容能像最初的状态 monad 这一想法一样为我带来巨大的触动和鼓舞。不过，在我们开发这门语言的时候，我确实阅读了几百篇有关 Haskell 的论文，几乎每一篇论文都对我有某种程序的影响。

我个人为 Haskell 这种高阶参数化多态所深深吸引，包括类型本质。并且经常思考着将这些想法融入到 C# 的泛型类型系统中的各种方法。

这些年来还有一些有趣的论文，讨论了如何以一种类似于 monad，并且功能友好的方式实现类似静态可变类型的东西。这对我们的创新过程也有所帮助，因为我们也在致力更多地使用具有不可变性及基于功能的对象，以取代对可变静态类型的使用。

各种错误模型也是非常有趣的，尤其体现在组合与编程模型方面，虽然有很大一部分是针对 monadic 错误及简单的语法错误的。

最后，我这几年来一直密切留意 Data Parallel Haskell 的相关工作，尤其是近期关于 GPGPU 的相关工作，并且发现 Concurrent Haskell 中的许多核心的优秀思想也对我们设计消息传递产生了影响。我还记得 2007 年时，我在一个会议上展示我们团队在并行 LINQ 上的工作成果时，有几位 Haskell 的专家也在场。我突然意识到我们所做的工作其实是相同的，只是在两个非常不同的系统上罢了。当晚我们还出去一起喝了两杯，我想这就是这个项目的想法产生的摇篮。即使到如今，我也在尽力结合这两者的优点。

InfoQ：你刚才提到“由于消息传递的交叉存储，使得 Erlang总是受困于竞态问题。而类型系统中同样的技术则可以实现安全的消息传递。”。我不太明白你的意思，你是说这项研究能够解决交叉存储的问题吗？倘若如此，能否就这一点展开一下讨论？

Joe：这很有趣，多数人对“竞态条件”的定义非常狭隘，仅仅指代典型的多线程程序中典型的基于线程的指令级交叉存储。实际上，竞态条件可以发生在更粗粒度的级别。比方如，假设有两个进程在同时读写同一个文件，这种情况的结果很显然取决于时间，往往由操作系统的调度器所决定，它能够导致微妙的相互作用。

结果表示，多数类似的共享资源都有一个并发模型，文件可以被加锁为独占式访问，数据库则使用事务，等等。

但是如果这些进程如果互相之间开发发送消息呢？当然，进程可以被隔离（什么也不共享），但它们之间的相互作用很大程度取决于时间及调度。换句话说，这就是竞态！近年来有一些有趣的论文，在 Erlang 的环境下讨论了这一话题。

虽然我无法在这里描述所有的细节，但可以给一些提示。用同样的方式去思考粗粒度的状态管理，就如我们所思考细粒度的状态管理一样，以此实现无竞态的任务及数据并行，这对消息传递的处理也很有启发性。

关于受访者

Joe Duffy是微软的一个操作系统孵化项目的首席架构师，他负责开发平台、编程语言及并行编程模型的设计。在这之前，他作为架构师创建了.NET 的并行扩展。Joe 也是一名作者和讲师，最新的著作是 Concurrent Programming on Windows (Addison-Wesley)。他最近在撰写一本新书 Notation and Thought，对编程语言的世界做了一次有趣的历史性回顾。在工作与写书之外，他会与他的妻子 Kim 出门旅行、写音乐、饮酒，或者是阅读数学的历史。你可以在他的博客中了解到他更多的想法。

查看英文原文：Joe Duffy on Uniqueness and Reference Immutability for Safe Parallelism