PDF被排除中项的诅咒
“大部分函数式”编程是行不通的。
Erik Meijer
软件行业存在一种趋势，将“大部分函数式”编程推销为解决开发者在并发、并行（多核）以及当然还有大数据方面所面临问题的灵丹妙药。当代命令式语言可以延续当前的趋势，拥抱闭包，并尝试限制突变和其他副作用。不幸的是，正如“大部分安全”行不通一样，“大部分函数式”也行不通。相反，开发者应该认真考虑一个完全原教旨主义的选项：拥抱纯粹的惰性函数式编程，并将所有效应都使用单子在类型系统中显式地表面化。
就像节食者迷恋神奇的10分钟奇迹锻炼小工具一样，开发者似乎也准备好接受简单的方法来解决他们领域中最新的危机。最近，许多人都在吹捧“接近函数式编程”和“有限的副作用”是应对新出现的房间里的大象（指并发和并行问题）的完美武器。很少有人愿意接受，这些好处必然是以牺牲诸如 I/O 等常见操作中潜在效应的便利性为代价的，正如节食者宁愿不承认锻炼的好处必然是以时间和汗水为代价的一样。
就像“大部分安全”一样，“大部分纯粹”也是一厢情愿的想法。最轻微的隐式命令式效应都会抹杀所有纯粹性的好处，就像一个细菌可以感染无菌伤口一样。另一方面，彻底根除所有效应——显式和隐式——会使编程语言变得毫无用处。这就是被排除中项的诅咒：你必须认真面对效应，要么 (a) 接受编程最终是关于突变状态和其他效应的，但出于务实的理由，尽可能地驯服效应；要么 (b) 废除所有隐式命令式效应，并在类型系统中使其完全显式化，但出于务实的理由，允许偶尔显式效应被抑制。
问题
命令式程序通过重复对共享全局状态执行隐式效应来描述计算。然而，在并行/并发/分布式世界中，单个全局状态是一个不可接受的瓶颈，因此支撑大多数当代编程语言的命令式编程的基本假设开始崩溃。与流行的看法相反，使状态变量不可变远不能消除不可接受的隐式命令式效应。异常、线程和 I/O 等普通操作都会造成与简单可变状态一样多的困难。考虑以下 C# 示例（感谢 Gavin Bierman），该示例过滤一个数组以保留所有介于 20 到 30 之间的值
static bool LessThanThirty(int x) {
Console.Write("{0}? Less than 30;", x); return x < 30;
}
static bool MoreThanTwenty(int x) {
Console.Write("{0}? More than 20;", x); return x > 20;
}
var q0 = new[]{ 1, 25, 40, 5, 23 }.Where(LessThanThirty);
var q1 = q0.Where(MoreThanTwenty);
foreach (var r in q1){ Console.WriteLine("[{0}];",r); }
因为Where是惰性的（或使用延迟执行），所以在q0和q1中使用的谓词中的效应是交错的；因此，评估q1打印所有介于 20 到 30 之间的值，就好像谓词被交叉一样
1? Less than 30; 1? More Than 20; 25? Less than 30; 25? More Than 20; [25];40? Less than 30; 5? Less than 30; 5? More Than 20; 23? Less than 30; 23? More Than 20; [23];
普通程序员肯定会期望q0先过滤掉所有高于 30 的值，然后再q1开始并删除所有小于 20 的值，因为这就是程序的编写方式，两个语句之间用分号分隔就证明了这一点。谓词之间的任何交叉依赖关系都会带来令人讨厌的意外。
这是另一个例子：将惰性与异常混合使用。如果在传递给Select（map）函数的闭包主体中抛出异常，由于延迟执行，异常不会在try-catch处理程序的范围内抛出。相反，异常在foreach循环强制评估时抛出，并且没有处理程序可见
var xs = new[]{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
IEnumerable<int> q;
try { q = xs.Select(x=>1/x); } catch { q = new int[]; }
foreach(var z in q){ Console.WriteLine(z): // 在这里抛出异常 }
效应以其他方式干扰语言特性，例如闭包和可释放模式之间的相互作用。下一个示例打开一个文件进行读取，并将文件变量捕获在一个闭包中，该闭包逃逸了 using 块的词法作用域。在 C# 中，using语句导致在块入口处初始化的变量在控制流到达块末尾时自动释放。因此，当闭包被调用时，文件已经被释放，从而导致一个令人惊讶的异常，它在时间和空间上都远离了静态源代码中抛出异常的代码所在的位置
Func<string> GetContents;
using(var file = FileSystem.OpenTextFileReader(@"my file")) {
GetContents = ()=>file.ReadToEnd();
}
Console.WriteLine(GetContents()); // 惊喜！一个异常
的词法作用域try-catch和using块与具有副作用的闭包的动态范围不能很好地混合。
深入兔子洞
如果惰性和闭包的例子看起来牵强，那么让我们看看一个以 printf 调试风格将其返回值跟踪到控制台的方法。尽管这看起来很无辜，但现在编译器执行像公共子表达式消除这样简单的优化是不安全的
string Ha() { var ha = "Ha"; Console.Write(ha); return ha; }
// 打印 HaHa
var haha = Ha()+Ha();
// 打印 Ha
var ha = Ha();
var haha = ha+ha;
但是等等——实际上情况更糟。仅仅创建一个新对象就是一个可观察的副作用。即使使用相同的参数调用，构造函数每次都会返回不同的结果，这可以通过GetHashCode或ReferenceEquals方法等来观察到
var a = new Object();
// 例如 58225482
Console.WriteLine(a.GetHashCode());
var b = new Object();
// 例如 54267293
Console.WriteLine(b.GetHashCode());
Debug.Assert(a != b);
为了使构造函数成为纯函数，你必须坚持所有对象的值语义，这意味着消除对象中所有共享的可变状态。现在，面向对象编程的本质——状态和行为封装在一个单元中——就丢失了。
这些例子说明了隐式命令式效应的另一个有害后果：它们排除了许多常见的优化转换。由于副作用隐式地改变了程序的全局环境，因此通常无法隔离和本地化效应。因此，命令式程序大多是非组合的，这使得程序员和编译器都难以对它们进行推理。
虽然这已经够糟糕了，但仅仅废除状态突变就足以使代码变得纯粹吗？不！不幸的是，仅仅使类中的所有字段readonly并禁止对局部变量赋值，还不足以驯服状态怪物。此处的 Cω 程序表明，即使在代码中看不到任何赋值或可变变量，线程也可以轻松模拟状态。私有通道Value(T current)承载单元格的状态，寄生在单元格内线程消息队列的隐藏可变状态上
class Cell<T> {
Cell<T>(T init){ Value(init); }
T Get() & async Value(T current){ return current; }
async Set(T @new) & async Value(T old){ Value(@new); }
}
你可以使用Point类，使用readonly类型Cell:
class Point {
readonly Cell<Int> x = new Cell<int>(0);
readonly Cell<int> y = new Cell<int>(0);
}
通过私有通道传递状态被接纳为 Erlang 中活动对象或 Actor 的基础。这是上面可变Cell程序的 Erlang 版本，使用尾递归函数cell(Value)来保持Cell:
new_cell(X) -> spawn(fun() -> cell(X) end).
cell(Value) ->
receive
{set, NewValue} -> cell(NewValue);
{get, Pid} -> Pid!{return, Value}, cell(Value);
{dispose} -> {}
end.
set_cell(Cell, NewValue) -> Cell!{set, NewValue}.
get_cell(Cell) ->
Cell!{get, self()},
receive
{return, Value} -> Value
end.
dispose_cell(Cell) -> Cell!{dispose}.
请注意，这个 Erlang Actor 基本编码了一个对象，它使用语言的模式匹配、消息发送和递归原语进行动态方法分派，你可以愉快地利用这些原语来实现可变引用，从而破坏 Erlang 语言本身不原生暴露可变状态的事实。
这些例子只是冰山一角。副作用的根本问题在于，有许多无法控制的方式来观察它们，更糟糕的是，通常可以用一种效应来模拟另一种效应。向纯组合电路添加递归使其可以构建提供可变状态的触发器。你可以证明状态和分隔延续足以模拟任何效应2，并且未检查的异常可以模拟延续4。在处理效应时，你怎么小心都不为过。
刚刚提出的例子表明，副作用可能非常棘手和微妙，它们会出现在最意想不到的地方。也许，你可能会问，“通过谨慎和自律，你能否通过避免导致问题的特性将命令式语言转换为纯粹的语言？” 要做到这一点，你必须删除所有内在效应。即使是求值也是一种效应，你必须放弃对编译器和运行时的控制。结果是，这种超纯程序无法与用户或环境交互，无法执行网络 I/O，无法响应用户界面事件，无法从文件中读取数据，无法获取当天的时间或生成随机数。这是一个可怕的困境：如果纯程序不能留下任何曾经执行过的痕迹，那么它们怎么可能有用呢？
虽然情况看起来黯淡，但幸运的是，有几种摆脱困境的方法。正如 John Hughes 在 1984 年的开创性论文“为什么函数式编程很重要”1中所观察到的，它们都涉及巧妙地添加特性而不是盲目地删除特性。
原教旨主义函数式编程
纯函数式编程是使用数学函数进行编程。这意味着表达值之间依赖关系的唯一方法是将函数应用于参数并收集返回的值。使用相同参数调用函数每次都会返回相同的结果。无法保守秘密，将值隐藏在一个小地方以便稍后拾取，无法直接说先做这个后做那个，无法启动线程，无法抛出未检查的异常，也无法只是在控制台上打印一些东西。这可能看起来很刻板和原教旨主义。确实如此。但它也强大且具有启发性。
要理解原教旨主义函数式编程如何帮助解决并发问题，重要的是要理解它不仅仅是没有副作用的命令式编程，正如我们所见，这是无用的。相反，它利用数学函数的原教旨主义语言，使用单子以组合方式表达和封装丰富的效应。为了构建单子的直观模型，让我们看一下可能最简单的通用方法
T Identity<T>(T me) { ... }
此方法的类型签名声明，对于所有类型T，给定类型为T的参数，该方法将返回类型为T的值。这并不是全部真相；命令式类型签名是漫不经心的、宽松的、过于松散的。它仅表达了方法实际数学类型的一个近似值。它没有考虑到可能隐藏在其执行中的任何副作用，例如它急切地评估其参数的事实；它可能会检查泛型类型参数（因此它并非对所有类型都统一工作T）；它可能会抛出异常、执行 I/O、启动线程、在堆中分配新对象并获取锁；它可以访问this等等。
纯粹的原教旨主义函数式语言的诀窍是拥有强迫症式的类型，并使用单子在类型签名中显式地公开所有效应，区分纯值的类型和可能包含效应的值的计算类型。
单子的非正式介绍
对于类型为a的值，让我们用函数应用程序的符号写出一个可以传递此类型值的效应计算(M a)，这是泛型类型的 Haskell 语法。设想这种效应计算的一种方法是使用一台机器，用于生成类型为a的输出值，同时显式地表示由输出值的计算引起的效应M。想象一下现实世界中的一家工厂，它需要电力并污染环境，作为生产商品的副作用。请注意，类型为M a的值只是一个承诺，它将生成类型为a的值，并且尚未执行任何效应。要实际使用单子值做一些事情，有两个标准组合器可以处理这种效应计算
* 中缀应用程序函数(ma>>=\a->f(a))，通常称为 bind，执行计算ma以暴露其效应，调用结果值a，并将该值传递给函数f。显然，此应用程序的结果(f a)应该再次是潜在的副作用计算；因此，bind 的类型签名如下所示
(>>=):: M a -> (a -> M b) -> M b.
* 注入函数(return a)将纯值注入到计算中。其类型签名为return :: a -> M a.
在实践中，每种效应通常都带有所谓的非适当态射。这些特定于域的操作对于该效应是唯一的（请参阅本文后面的示例）。
你现在可以将上述形式的所有效应计算抽象化和形式化为称为单子的代数结构，该结构支持用于创建和传播效应的两个通用操作，return和 bind(>>=):
class Monad m where {
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
}
Haskell 中所有单子的母体是 I/O 单子，它表示所有具有全局效应的计算。因此，它带有大量非适当态射，其中大多数对于命令式程序员来说都很熟悉，例如用于读取和写入控制台、启动线程和抛出异常的操作。一旦效应在 I/O 单子中显式化，例如，分配可变变量以及读取和写入它们的操作必须提升到 I/O 单子中。
data IO a -- 无需知道这是如何实现的
putChar :: Char -> IO ()
getChar :: IO Char
newIORef :: a -> IO (IORef a)
readIORef :: IORef a -> IO a
writeIORef :: IORef a -> a -> IO ()
forkIO :: IO a -> IO ThreadID
从forkIO的类型中，你可以立即看出，启动线程是一种副作用操作，这确保了使用线程的任何可变单元格编码也将位于 I/O 单子中。这可以防止程序员相信他们正在定义不可变类型，而实际上并非如此。请注意，I/O 单子并不阻止从多个线程同时更新全局状态，因为forkIO的类型显示了这一点。
单子的真正威力来自于计算本身只是值，可以在纯宿主语言中作为一等公民传递。这使程序员可以使用单子原语和非适当态射编写新的抽象（特定于域的和自定义控制结构）。
例如，你可以轻松定义一个函数，该函数接受副作用计算的列表并执行每个计算，并将结果收集在一个列表中
sequence :: Monad m => [m a] -> m [a]
sequence [] = return []
sequence (ma:mas) = ma >>= (\a -> sequence mas >>= (\as -> a:as))
纯粹的原教旨主义函数式语言是内部 DSL 的非常方便的宿主语言，因为它只是可执行的指称语义。因此，纯函数式语言在很大程度上实现了 P.J. Landin 在 1966 年发表的有影响力的论文“接下来 700 种编程语言”3的愿景。
在类型系统中显式化效应的另一个优点是，你可以区分各种效应并自由引入新的效应。例如，你可以定义事务内存的单子(STM a)6。它包含用于分配、读取和写入事务变量的非适当态射
newTVar :: a -> STM (TVar a)
readTVar :: TVar a -> STM a
writeTVar :: TVar a -> a -> STM ()
retry操作中止当前事务并等待任何事务变量被更改，或者当通过orElse运算符链接时，它尝试运行另一个事务块。
retry :: STM a
orElse :: STM a -> STM a -> STM a
最后，atomic函数将事务单子注入到通用 I/O 单子中。从那时起，就不能再对该值执行任何事务操作。
atomic :: STM a -> IO a
由于没有从I/O到STM的（隐式）泄漏，STM单子捕获了执行事务所需的所有机制，而无需担心回滚任意效应，因为普通的 Haskell 计算被认为是纯粹的。
副作用不仅难以驯服，而且还经常从后门偷偷溜进来。即使在据说是纯粹的 Haskell 中，也有一个看似不起眼的函数叫做unsafePerformIO :: IO a->a它告诉编译器“忘记”评估其参数所涉及的副作用。这个“几乎函数”应该有助于封装其他纯计算中的良性副作用；unsafePerformIO，然而，打开了潘多拉魔盒，因为它颠覆了 Haskell 类型系统，破坏了语言保证，并允许将任何类型转换为任何其他类型
unsafeCast :: a -> b
unsafeCast x = unsafePerformIO (do{
writeIORef castref x; readIORef castref
})
castref = unsafePerformIO (do{ newIORef undefined })
这些例子展示了使用单子将副作用计算视为值的强大功能，但普通开发者是否可以处理它们的问题仍然没有解答。我们认为答案是响亮的肯定，正如单子也是 LINQ 运作的基础这一事实所证实的那样。LINQ 标准查询运算符本质上是单子运算符。例如，SelectMany扩展方法直接对应于 Haskell bind(>>=)，它在前面介绍过
(>>=) :: m a -> (a -> m b) -> m b
M<T> SelectMany(this M<S> src, Func<S, M<T>> f)
Haskell 中的多态性和 CLR（公共语言运行时）、Java 或其他面向对象语言中的泛型之间的主要区别在于，单子的 Haskell 定义依赖于高阶类型多态性——也就是说，单子类（接口）由类型构造函数而不是类型参数化。通常，泛型只允许对类型进行参数化——例如，List<T>和Array<T>——但不允许对容器类型进行参数化M，例如M<T>，然后用M用List或Array实例化。因此，编码单子的 LINQ 标准序列运算符必须依赖于语法模式，本质上是重载，而不是适当的泛型。
你可以轻松地定义效应的可重用抽象，这就是人们经常称 Haskell 为世界上最好的命令式语言的原因。也许行业现在面临的真正危机比采用纯粹的原教旨主义函数式编程的感知痛苦要严重得多。LINQ 的热情接受表明人们已经准备好迎接改变。
替代方案
普遍的看法是，原教旨主义编程方法对于普通程序员来说范式转变太大，而前进的方向是使现有的命令式语言更加纯粹，从而驯服效应。提倡的方法是以双重方式驯服效应：假设所有方法都具有环境效应（都在 I/O 单子中），除非那些用特殊修饰符标记的方法，例如threadsafe, pure, immutable, readonly，区分val和var等，这些信号表示事件的缺失。虽然乍一看这似乎对开发者来说不太突兀，但可以说并非如此，因为一旦进入纯粹的上下文，你就无法调用不纯的函数，因此也必须传递性地将从纯粹方法调用的任何方法都标记为纯粹方法——就像在 Haskell 中在纯粹表达式的深处添加效应需要完全重构为单子风格一样。
纯粹性注释的一个问题是它们不可扩展——也就是说，用户无法定义新的“非效应”。正如我们在单子组合的示例中看到的那样，支持用户在必要时定义他们的效应和非适当态射至关重要。
其次，纯粹性注释通常与函数有关，而在 Haskell 中，效应不与函数绑定，而是与值绑定。在 Haskell 中，类型为f::A->IO B的函数是一个纯函数，给定类型为A的值，它返回一个副作用计算，由类型为IO B的值表示。然而，应用函数f不会导致任何立即发生的效应。这与将函数标记为纯函数有很大不同。如此处所示，将效应附加到值使程序员能够定义自己的控制结构，例如，将副作用计算列表转换为计算列表的副作用计算。
还有许多其他关于在命令式语言中推理效应的提案，例如线性或唯一类型、所有权类型，或者最近的分离逻辑5。然而，这些都需要用户和工具都具有高度的复杂性。与单子和纯函数式编程的简单等式推理相比，这是一种极其繁重的数学机制，因此并没有真正简化普通程序员的生活。一个人不需要计算机科学理论博士学位就能破解和推理代码。
对于开发者来说，驯服效应以使命令式语言变得纯粹，与坚持原教旨主义并使纯粹语言变得命令式一样痛苦。
结论
“大部分函数式编程”的想法是不可行的。仅仅部分删除隐式副作用是不可能使命令式编程语言更安全的。留下一种效应通常足以模拟你刚刚尝试删除的效应。另一方面，允许在纯粹语言中“忘记”效应也会以其自身的方式造成混乱。
不幸的是，没有黄金中间地带，我们面临着一个经典的二分法：被排除中项的诅咒，它提出了以下选择：（a）尝试使用纯粹性注释来驯服效应，但完全接受你的代码仍然从根本上是效应性的事实；或者 (b) 完全拥抱纯粹性，通过在类型系统中使所有效应显式化，并通过引入诸如unsafePerformIO之类的非函数来变得务实。此处展示的示例旨在说服语言设计者和开发者跳过镜子，开始更认真地看待原教旨主义函数式编程。
参考文献
1. Hughes, J. 1989. 为什么函数式编程很重要。计算机杂志 32(2): 98-107. 10.1093/comjnl/32.2.98
2. Filinski, A. 1994. 表示单子。在第 21 届年度 编程语言原理研讨会论文集 (POPL) 中。 出版社：446-457。
3. Landin, P. J. 1966. 接下来 700 种编程语言。 通讯 9(3): 157-166. 10.1145/365230.365257
4. Lillibridge, M. 1999. 未检查的异常可能比 call/cc 更强大。高阶和符号计算 12(1): 75-104. 10.1023/A:1010020917337
5. O'Hearn, P. W. 2012. 分离逻辑入门（以及自动程序验证和分析）。软件安全与保障；分析和验证工具。北约和平与安全科学系列 33: 286-318。
6. Oram, A., Wilson, G. 2007. 代码之美：顶级程序员解释他们的思考方式。O'Reilly Media。
喜欢它，讨厌它？请告诉我们
Erik Meijer (邮箱受保护) 是 Applied Duality, Inc. 的创始人，也是 TUDelft 云编程教授。他最出名的事迹可能是他对 Haskell、C#、Visual Basic 和 Hack 等编程语言的贡献，以及他在 LINQ 和 Rx Framework 方面的工作。
© 2014 1542-7730/14/0400 $10.00
最初发表于 Queue vol. 12, no. 4—
在 数字图书馆 中评论本文
更多相关文章
Matt Godbolt - C++ 编译器中的优化
在向编译器提供更多信息方面需要权衡：这可能会使编译速度变慢。诸如链接时优化之类的技术可以让你兼得两者。编译器中的优化在不断改进，而即将到来的间接调用和虚函数分派的改进可能很快就会带来更快的多态性。
Ulan Degenbaev, Michael Lippautz, Hannes Payer - 作为合资企业的垃圾回收
跨组件跟踪是一种解决跨组件边界的引用循环问题的方法。只要组件可以形成任意对象图，并且在 API 边界上具有重要的所有权，就会出现此问题。CCT 的增量版本已在 V8 和 Blink 中实现，从而能够以安全的方式有效且高效地回收内存。
David Chisnall - C 语言不是一种低级语言
在最近的 Meltdown 和 Spectre 漏洞之后，值得花一些时间来研究根本原因。这两个漏洞都涉及处理器推测性地执行超出某种访问检查的指令，并允许攻击者通过侧信道观察结果。导致这些漏洞以及其他几个漏洞的特性被添加进来，是为了让 C 程序员继续相信他们正在用低级语言编程，而这种情况在几十年前就已经不是这样了。
Tobias Lauinger, Abdelberi Chaabane, Christo Wilson - 你不应该依赖我
大多数网站都使用 JavaScript 库，其中许多库已知是易受攻击的。了解问题的范围，以及包含库的许多意外方式，仅仅是朝着改善情况迈出的第一步。此处的目的是，本文中包含的信息将有助于为社区提供更好的工具、开发实践和教育努力。
© 保留所有权利。