< 返回版块

2019-08-02 09:03    责任编辑:jay

标签:rust

本文转载自:https://overreacted.io/algebraic-effects-for-the-rest-of-us/

写给那些搞不懂代数效应的我们(翻译)

Cowsay

Cowsay

原文:Algebraic Effects for the Rest of Us,作者Dan Abramov
翻译题记:
昨天的Rust日报上刊登了一个实现了代数效应的Rust库,以及这篇文章的原版链接。
这是一篇通俗易懂的有趣文章,本文只是对其的粗略意译,并且省略了其中的链接(和表情包)。请有能力的朋友尽量前往原文围观。

你听说过代数效应吗?

我的第一次尝试理解大失败。我找了一些PDF,但是学术论文就是具有某种令我犯困的魔力。

不过后来我的大佬同事塞巴斯蒂安(他搞出了React Hooks)老是发表「啊其实我们在React里干的事就是代数效应」这样的言论,以至于有段时间代数效应已经变成了我们讨论React时的一个梗了。

事实上,代数效应是一个很coooooool的概念,也没有那些PDF上写得那么吓人。如果你只是一个普通的React用户,那什么都不用知道,用就行了;如果你是个像我一个的好奇宝宝,那就请读下去吧。

(免责须知:我并不是语言砖家,有的地方可能讲得不严谨。要是哪里说错了欢迎提出修改建议。)

尚未生产化

代数效应是一个学术概念。所以说,不像if,函数,甚至是async,你现在还没办法在生产环境中用到它。目前只有一些专门为了探索代数效应的玩具语言实现了它,OCaml还在努力把它生产化。不过有人说LISP已经提供了类似的功能,所以如果你用LISP那么你有机会在生产环境下试试看。

那我管它干什么

想象一下你正在用goto写程序,这时候突然有个人来给你介绍iffor。或者你正在写回调地狱的时候有人给你看了一眼async/await。超牛逼对不对?

如果你是一个喜欢思想领先于编程业界潮流的人,现在开始理解代数效应再合适不过。当然这并不是必须的;这就有点像是在1999年尝试理解async

好吧,那么什么是代数效应?

这个名字逼格可能挺高但是道理很简单。如果你很熟悉try/catch块,那么理解代数效应很容易。

我们先从try/catch为基础将起。你有一个函数要抛出异常,经过千山万水以后它另外一个函数接住了这个异常:

function getName(user) {
  let name = user.name;
  if (name === null) {
    throw new Error('A girl has no name');
  }
  return name;
}

function makeFriends(user1, user2) {
  user1.friendNames.add(getName(user2));
  user2.friendNames.add(getName(user1));
}

const arya = { name: null };
const gendry = { name: 'Gendry' };
try {
  makeFriends(arya, gendry);
} catch (err) {
  console.log("Oops, that didn't work out: ", err);
}

我们在getName里抛出了异常,穿过了makeFriends,最后异常在它遇到的最近的catch块中被处理。这是异常机制的一个重要特性,中间的代码不需要关心有关异常处理的事

不像C里的错误码机制, 用了try/catch,你就不用手动将异常一层一层地传递了。它们会自动向上层传递,不用担心会弄丢。

这和代数效应有什么关系呢?

在上面的例子中,一旦我们遇到了一个错误,我们就不能继续执行下去了。我们会从catch块中继续执行,没有任何机会回去执行出错以后的代码。

凉凉。我们也许可以在catch中修正错误并重试一次,但是我们不能「回到」之前的那次执行中去了。但是如果有代数效应,我们就可以这样做。

这是一个用虚构的JavaScript方言编写的例子(就叫它ES2025吧):

function getName(user) {
  let name = user.name;
  if (name === null) {
    name = perform 'ask_name';
  }
  return name;
}

function makeFriends(user1, user2) {
  user1.friendNames.add(getName(user2));
  user2.friendNames.add(getName(user1));
}

const arya = { name: null };
const gendry = { name: 'Gendry' };
try {
  makeFriends(arya, gendry);
} handle (effect) {
  if (effect === 'ask_name') {
    resume with 'Arya Stark';
  }
}

(如果有2025年网上冲浪的朋友搜索「ES2025」然后被引导到这篇文章来了,请接收我的歉意……当然如果到那时候代数效应真的成为了JavaScript的一部分那我很开心。)

我们这回没有用try,而是使用了perform关键字。同样,我们用虚构的try/handle替换了try/catch语法不重要,重要的是背后的道理。

所以说发生什么了?我们仔细研究一下。

这回我们没有抛出一个异常,而是执行(perform)了一个效应(effect)。就像我们可以把任何值使用throw抛出,我们也可以用perform把它执行。在这个例子中,我传了一个字符串,但是它也可以是对象或者别的数据结构:

function getName(user) {
  let name = user.name;
  if (name === null) {
    name = perform 'ask_name';
  }
  return name;
}

当我们抛出一个异常时,运行引擎会寻找调用栈中最近的try/catch块处理异常。同样,当我们执行一个效应时,引擎也会寻找最近的try/handle来处理效应

try {
  makeFriends(arya, gendry);
} handle (effect) {
  if (effect === 'ask_name') {
    resume with 'Arya Stark';
  }
}

例子中的效应允许我们决定怎么处理缺失的name。相比异常机制,这里出现了一个有趣的新概念:虚构的resume with关键字。

这就是异常机制做不到的部分了。它允许我们跳回执行效应的代码继续执行,并且还可以夹带一点私货。

function getName(user) {
  let name = user.name;
  if (name === null) {
  	// 1. 我们在这执行了一个效应
  	name = perform 'ask_name';
  	// 4. ……然后我们回到了这里(这时name的值为'Arya Stark')
  }
  return name;
}

// ...

try {
  makeFriends(arya, gendry);
} handle (effect) {
  // 2. 我们被跳转到这里(就像try/catch)
  if (effect === 'ask_name') {
  	// 3. 然而,我们可以带着一个值继续执行(不像try/catch!)
  	resume with 'Arya Stark';
  }
}

想适应这个概念可能要花点功夫,但是本质上这就是一个「可以继续执行的try/catch」。

然而,**代数效应远比try/catch要来的灵活,可恢复异常只是其中一个使用场景。**我从这里开始讲只是因为这个例子讲起来最容易。

没有颜色的函数

代数效应对异步代码带来了有趣的潜移默化。

如果一个语言有async/await关键字,那么它的函数通常是有「颜色」的。比如说,如果在JavaScript中getName是一个异步函数,那么它的调用者makeFriends就没办法是同步的。结果就是调用者以及调用者的调用者全都被async了。如果一个函数又需要是同步的又需要是异步的,情况就变得很痛苦。

// 如果我们希望它是异步的……
async getName(user) {
  // ...
}

// 那么它也必须是异步的……
async function makeFriends(user1, user2) {
  user1.friendNames.add(await getName(user2));
  user2.friendNames.add(await getName(user1));
}

// 下同……

JavaScript生成器也是差不多。如果你最后会调用一个生成器,那么整个调用链条就一定会受到这个生成器的影响。

所以这和我们又能扯上什么关系呢?

暂且忘掉async/await,让我们回到之前的例子中来:

function getName(user) {
  let name = user.name;
  if (name === null) {
    name = perform 'ask_name';
  }
  return name;
}

function makeFriends(user1, user2) {
  user1.friendNames.add(getName(user2));
  user2.friendNames.add(getName(user1));
}

const arya = { name: null };
const gendry = { name: 'Gendry' };
try {
  makeFriends(arya, gendry);
} handle (effect) {
  if (effect === 'ask_name') {
    resume with 'Arya Stark';
  }
}

如果我们的效应处理块不能同步地获取「默认名字」怎么办?比如说,需要现从数据库里抓。

事实上,我们什么都不用改,resume with完成可以和异步代码一起用:

function getName(user) {
  let name = user.name;
  if (name === null) {
    name = perform 'ask_name';
  }
  return name;
}

function makeFriends(user1, user2) {
  user1.friendNames.add(getName(user2));
  user2.friendNames.add(getName(user1));
}

const arya = { name: null };
const gendry = { name: 'Gendry' };
try {
  makeFriends(arya, gendry);
} handle (effect) {
  if (effect === 'ask_name') {
    setTimeout(() => {
      resume with 'Arya Stark';
    }, 1000);
  }
}

在这个例子里,我们等了一秒才执行resume with。你可以把它想象成一个只能执行一次的回调函数(跟朋友装逼的时候可以管它叫「one-shot delimited continuation」)。

现在代数效应的模型清楚多了。当我们抛出一个异常的时候,执行引擎会摧毁所有上层调用栈以及其中的局部变量(「回卷(unwind)」);但是当我们执行一个效应时,虚构的引擎会创建一个回调函数,这个回调函数的函数体是正在执行的函数体的剩余部分,并且在我们执行resume with时执行这个回调函数。

再说一遍,所有的语法都是编出来的。语法不重要,重要的是原理。

关于副作用

值得指出的一点,代数效应是从函数式编程中脱胎的。它所解决的一部分问题只在纯函数式编程中才存在。比方说,如果一个语言不允许任何种类的副作用(比如Haskell),你就需要用Monad把副作用封起来。如果你读过Monad教程你就会发现那玩意理解起来很麻烦。代数效应可以解决类似的问题,但是少了很多繁文缛节。

所以说,很多关于代数效应的讨论我都不太理解(我对于Haskell系语言并不熟)。但是,哪怕在一门如JavaScript这样的有副作用的语言里,我还是觉得代数效应相当有用。它可以把「做什么」和「怎么做」完全分离。

它可以让你写代码的时候先把注意力都放在「做什么」上:

function enumerateFiles(dir) {
  const contents = perform OpenDirectory(dir);
  perform Log('Enumerating files in ', dir);
  for (let file of contents.files) {
    perform HandleFile(file);
  }
  perform Log('Enumerating subdirectories in ', dir);
  for (let directory of contents.dir) {
    // 我们可以递归或者调用别的有效应的函数
    enumerateFiles(directory);
  }
  perform Log('Done');
}

然后再把上面的代码用「怎么做」包裹起来:

let files = [];
try {
  enumerateFiles('C:\\');
} handle (effect) {
  if (effect instanceof Log) {
    myLoggingLibrary.log(effect.message);
    resume;
  } else if (effect instanceof OpenDirectory) {
    myFileSystemImpl.openDir(effect.dirName, (contents) => {
      resume with contents;
    });
  } else if (effect instanceof HandleFile) {
    files.push(effect.fileName);
    resume;
  }
}
// `files`数组里现在有所有的文件了

这甚至意味着上面的函数可以被封装成代码库了:

import { withMyLoggingLibrary } from 'my-log';
import { withMyFileSystem } from 'my-fs';

function ourProgram() {
  enumerateFiles('C:\\');
}

withMyLoggingLibrary(() => {
  withMyFileSystem(() => {
    ourProgram();
  });
});

async/await不同的是,代数效应不会把中间的代码搞复杂。enumerateFile可能位于outProgram底下相当深的调用链条中,但是只要它的上方某处存在着效应处理块,我们的代码就能运行。

代数效应同样允许我们不用写太多脚手架代码就能把业务逻辑和实现它的效应的具体代码分离开。比如说,我们可以在测试中用一个伪造的文件系统和日志系统来代替上面的生产环境:

import { withFakeFileSystem } from 'fake-fs';

function withLogSnapshot(fn) {
  let logs = [];
  try {
    fn();
  } handle (effect) {
    if (effect instanceof Log) {
      logs.push(effect.message);
      resume;
    }
  }
  // Snapshot emitted logs.
  expect(logs).toMatchSnapshot();
}

test('my program', () => {
  const fakeFiles = [/* ... */];
  withFakeFileSystem(fakeFiles, () => {
    withLogSnapshot(() => {
      ourProgram();
     });
  });
});

因为这里没有「颜色」问题(夹在中间的代码不需要管代数效应),并且代数效应是可组合的(你可以把它嵌套起来),你可以用它创建表达能力超强的抽象。

关于类型

代数效应的概念是从静态类型语言中来的,所以关于它的讨论很多都集中在效应可以被类型系统表达出来这一点上。其重要性毋庸置疑,但是引入它可能会阻碍对概念的理解,所以这篇文章完全没有提类型的事。但是,我还是应该提醒读者,如果一个函数可以执行某种效应,它的函数签名应该体现出这一点。这样你就可以避免陷入「满地都是效应但不知道它们是从哪里来的」的困境。

你可能会说,把效应嵌入函数签名相当于给函数染上了颜色。没错。但是,给一个中间层的函数引入新的效应,这件事本身并不是一个语义层面的改动——不像给一个同步函数添加async使它变成异步函数那样。另外,自动推导也可以起到一定的帮助。代数效应和其他颜色还有一个重要的区别,你是可以把它「封装」在一定的边界范围内的,比如说对于一个具有异步效应的函数,只要在它的外面包裹一个异步效应的处理块就可以了。所以在必要的时候,用户有机会把效应对外界隐藏,或者转换为另一种效应进行暴露。

我们应该把代数效应引入JavaScript吗?

老实说我并不是很清楚。代数效应是非常有用的。但是对于JavaScript这样的语言,你也可以说它有用得过头了。

我觉得对于一个不太依赖于可变状态,并且标准库对效应也比较友好的语言来说,引入代数效应会比较合适。如果你平时写的是perform Timeout(1000)perform Fetch('http://google.com'),和perform ReadFile('file.txt'),并且你的语言有模式匹配和效应类型系统,那么这是一个非常惬意的编程环境。

说不定这种语言可以编译成JavaScript呢(

所以这跟React又有什么关系呢?

没啥关系。你甚至可以说这就是个噱头。

如果你看了我关于时间切片和Suspense的讨论,其中的第二部分涉及到一个从缓存中读取的组件:

function MovieDetails({ id }) {
  // 如果数据还没抓取到怎么办?
  const movie = movieCache.read(id);
}

(讨论中的API稍有不同,这不重要。)

这个组件使用了React的一个叫做Suspense的特性,这是一种用于数据抓取的正在开发的功能。其中最有趣的部分显然是,数据也许还没有进入movieCache,在这种情况下我们必须得做点什么,因为代码执行不下去了。技术上来讲,read方法在这时会抛出一个Promise(对没错,就是抛出),这会「暂停」执行流程。React会接住这个Promise,并且记住在数据到达时重新渲染组件树。

这当然不是代数效应,虽然是也受到了代数效应的启发。但是它们的目的是相同的:调用栈顶端的代码需要跳转到调用栈底层(在这里是React),并且不想让中间的代码受到牵连或者被async之类的。当然,在这个例子中我们不能真正地继续执行,但是按照React的模型,重新渲染组件树跟继续执行差不了多少。只要你的编程模型说它们是等价的,它们就是!(

Hooks也是一个让人联想到代数效应的例子。很多人看到Hooks的第一个问题是:useState要怎么知道是哪个组件引用它的?

function LikeButton() {
  // useState 怎么知道它在哪个组件里?
  const [isLiked, setIsLiked] = useState(false);
}

我在另一篇文章的末尾曾经解答过:有一个类似于「当前分发器」的可变状态指向你正在使用的分发器实现。类似的,也有一个「当前组件」状态指向LikeButton的内部数据结构。所以useState才知道该干什么。

在适应这个架构之前,人们常常觉得这种做法有点脏。因为依赖于全局可变状态总让人觉得怪不舒服的(所以说你觉得他们是怎么实现try/catch的?)。

但是,你也可以把useState看做是一个perform State(),而这个效应被React处理了。这样就可以「解释」React是怎么为它提供组件引用的了,因为它在调用栈的底部,所以可以注册效应处理块。事实上,实现这样的状态是我见过的最多的代数效应教程。

当然了,React实际上不是这么实现useState的,因为我们在JavaScript中还没有代数效应可以用。 事实上在userState的实现中有一个隐藏的字段指向我们正在使用的组件,以及一个隐藏字段指向我们正在使用的分发器。为了提升性能,在挂载和更新函数中甚至提供了分别的useState实现。但是如果你使劲「误解」一下这段代码,你就会发现它其实就是代数效应。

总结一下,在JavaScript中,抛异常可以粗略地代替IO效应,只要代码可以被重新执行没有副作用并且也不是很重;在try/finally中放置一个「分发器」字段也可以粗略地代替同步效应处理块。

你也可以用生成器实现一个更加如假包换的代数效应,但是这样的话你需要放弃一个JavaScript天生的「透明」优势,并且需要把一切都换成生成器……

教练,我还要学

就我个人而言,我没有想到代数效应居然是这么好理解的一个东西。我在理解Monad的时候总是很痛苦,但是代数效应似乎「就那样」就弄明白了。希望这篇文章也可以使你也「就那样」就把它搞懂。

我不知道代数效应还要多久才能汇入主线。如果到了2025年还没有主流语言采用代数效应我会相当失望。记得五年以后提醒我一下。

我知道你可以用代数效应做很多事,但是如果你不真得用代数效应写一些代码的话是很难理解它的威力的。如果这篇文章引起了你的兴趣,你可以看看这些资源:

ocamllabs/ocaml-effects-tutorial​github.com图标https://www.janestreet.com/tech-talks/effective-programming/​www.janestreet.com

https://www.youtube.com/watch?v=hrBq8R_kxI0​www.youtube.com

也有很多人说,如果你忽略了类型系统(就像我这篇文章),你可以找到很久以前有关Common LISP的conditional system的文章。你也可以读读詹姆斯·龙关于continuation的文章,其中讲了为什么call/cc可以作为搭建用户层可继续异常的基础。

如果你发现了帮助JavaScript用户理解代数效应的文章,请在推特上和我说一声!


全文如上。

我平日里的主要爱好项目是一个用Rust编写的脚本语言Shattuck。感兴趣的读者可以查看我往期的文章。在我制定的Shattuck两大目标中,「不使用GIL实现多线程」已经初步通过Hulunbuir实现了,我会在近期写一篇文章用Hulunbuir实现一个链表。另一个目标「少用哈希表」,以及它背后更深层次的「避免引入类的概念」,本来的打算是通过学习Rust的trait系统。看过这篇文章后,我意识到代数效应可以在某种程度上发挥和trait类似的作用,也许Shattuck可以有更加有趣的实现方式了。

希望各位读者阅读愉快。