Lambda Academy

【译】从高阶函数到库和框架

March 14, 2019

这篇文章中,我们会探索一些高阶函数,去思考如何用这些函数来让我们的程序更具表达性;同时,我们也要在程序可感知复杂度(perceived complexity) 和表达性之间达到折中和平衡。

什么是表达性

编程中最基础的概念之一就是函数可以调用其它函数。

当一个函数能调用其它函数,且当一个函数能被多个其它函数调用时,我们就可以干很多有意思的事情。而函数之间多对多的关系,比起一对多的关系,能让程序具有更强的表达能力。我们可以给每个函数单一的职责,然后命名这个职责;我们还能确保有且仅有一个函数承担某项职责。

多对多的函数关系使得函数与职责之间一对一的关系成为可能。

程序员经常说某个语言非常具有表达性,然而并没有一个普世单一的标准来定义什么是表达性。大多数程序员同意,决定某个语言具有“表达性”的一个重要特征是,该语言让程序员能很容易避免代码中没必要的啰嗦。如果函数拥有多个职责,这会让函数自身变得庞大笨拙。如果同一个职责要被多次实现,这就造成了程序的冗余。

如果程序中的函数都具有单一职责,且所有职责都仅被单一函数实现一次,这样的程序就避免了没必要的啰嗦。

综上,函数之间多对多的关系,让编写高表达性程序成为可能。而那些无此特征的程序,在“表达性”上则是非常糟糕的。

另一面:可感知复杂度

然而,能力越大,责任越大。多对多函数关系的负面就是,随着程序体积增长,该程序能干的事情就急剧增多。“表达性”经常与“可感知复杂度”存在冲突。

为了更容易理解上面的论断,我们画个关系图来类比来思考下。每个函数是一个节点,函数之间的调用关系是连线。假设程序中没有死代码,那么每个结构化程序都形成一个连接图。

graph

给定已知数量的节点,在这些节点中能画的连接图数量形成 A001187 整数序列。(译者注:这个太硬核数学了,不懂)…(数学,不懂,省略翻译)… 总之,仅仅 10 个函数就能形成多于 34 兆个程序组合方式……

程序灵活性的爆炸性增长让程序员不得不克制一下。函数和职责之间一对一关系带来的好处,被由此而造成的无限复杂度而抵消。试想理解这种复杂度的程序多么困难。

JavaScript 能提供工具帮忙缓解这个问题。它的块创建了命名空间,ES Modules 也具有这个功能。它很快就会具有私有对象属性。(译者注:公有和私有类属性已经进入 State 3 草案了)

命名空间将本可能大的关系图限制到小的图里面,每一个小图与其它小图(模块)连接的方式数量可控。用这种方式,你得到的依然是一张大图,但是你这张图的可组合可能性小了很多。这样,你就更容易弄清楚它能做什么,怎么做。

我们刚刚以靠近直觉的方式来描述一种设计优秀软件系统的方式:给予程序员因实体间多对多关系带来的灵活性,同时让程序员可以主动限定实体间可连接的方式。

但是请注意我们没有说有某种机制能同时干这两件事。不,我们只是说有一个工具能帮我们提升表达性,另一个工具帮我们限制程序中的可感知复杂度;而这两者之间存在冲突。

现在,我们直觉上能明白这个问题了,那就让我们来看一些高阶函数。从这些函数上,我们试着能不能看出表达性和可感知复杂度的同时存在。

高阶函数

如果一个函数接受其它若干函数作为参数,且/或将函数作为值返回,我们称这种函数为高阶函数,或 HOFs. 支持 HOFs 的语言同时也支持一等公民函数,而且几乎都会支持动态创建函数。

高阶函数给了程序员更多解构和组合程序的方式,由此,程序员有了更多编写职责 — 函数一对一关系的方式。让我们来看个例子。

传说好的公司总会要求毕业生应聘者进行 coding 面试。

比如,把两个已经排好序的列表合并到一起。这种问题不至于太难,同时也有现实应用场景。下面是一个天真的答案:

function merge({ list1, list2 }) {
  if (list1.length === 0 || list2.length === 0) {
    return list1.concat(list2);
  } else {
    let atom, remainder;

    if (list1[0] < list2[0]) {
      atom = list1[0];

      remainder = {
        list1: list1.slice(1),
        list2,
      };
    } else {
      (atom = list2[0]),
        (remainder = {
          list1,
          list2: list2.slice(1),
        });
    }
    const left = atom;
    const right = merge(remainder);
    return [left, ...right];
  }
}
merge({
  list1: [1, 2, 5, 8],
  list2: [3, 4, 6, 7],
});
//=> [1, 2, 3, 4, 5, 6, 7, 8]

下面是一个对数字组成列表求和的函数:

function sum(list) {
  if (list.length === 0) {
    return 0;
  } else {
    const [atom, ...remainder] = list;
    const left = atom;
    const right = sum(remainder);
    return left + right;
  }
}
sum([42, 3, -1]);
//=> 44

我们故意把这两个函数以同一种结构来写。这种结构叫线性递归。我们可以把这种共有结构抽离出来吗?

线性递归

线性递归形式很简单:

  1. 观察函数输入值,我们能把这个值的其中一个元素抽离开来吗?
  2. 如果不能,我们应该返回什么值?
  3. 如果能,那我们就把这个值分离成一个元素和剩下的元素。
  4. 把剩下的元素放进同一个线性递归函数执行,然后
  5. 把前面分离出来的元素,和后面对剩下元素进行线性递归的结果进行某种连接

我们刚刚展示的两个函数都有这个形式,那我们就写个高阶函数来实现线性递归。我们就以其中一个函数为例,来抽离出共有部分:

function sum(list) {
  const indivisible = (list) => list.length === 0;
  const value = () => 0;
  const divide = (list) => {
    const [atom, ...remainder] = list;
    return { atom, remainder };
  };
  const combine = ({ left, right }) => left + right;
  if (indivisible(list)) {
    return value(list);
  } else {
    const { atom, remainder } = divide(list);
    const left = atom;
    const right = sum(remainder);
    return combine({ left, right });
  }
}

还差一点就实现我们想要的高阶函数了,最关键的一部是重新命名几个变量:

function myself(input) {
  const indivisible = (list) => list.length === 0;
  const value = () => 0;
  const divide = (list) => {
    const [atom, ...remainder] = list;
    return { atom, remainder };
  };
  const combine = ({ left, right }) => left + right;
  if (indivisible(input)) {
    return value(input);
  } else {
    const { atom, remainder } = divide(input);
    const left = atom;
    const right = myself(remainder);
    return combine({ left, right });
  }
}

最后一步是将这些常量函数改成一个最终返回 myself 的函数的形参:

function linrec({ indivisible, value, divide, combine }) {
  return function myself(input) {
    if (indivisible(input)) {
      return value(input);
    } else {
      const { atom, remainder } = divide(input);
      const left = atom;
      const right = myself(remainder);
      return combine({ left, right });
    }
  };
}
const sum = linrec({
  indivisible: (list) => list.length === 0,
  value: () => 0,
  divide: (list) => {
    const [atom, ...remainder] = list;
    return { atom, remainder };
  },
  combine: ({ left, right }) => left + right,
});

现在我们就能利用 summerge 之间的相同属性了。让我们用 linrec 来实现 merge 吧:

const merge = linrec({
  indivisible: ({ list1, list2 }) => list1.length === 0 || list2.length === 0,
  value: ({ list1, list2 }) => list1.concat(list2),
  divide: ({ list1, list2 }) => {
    if (list1[0] < list2[0]) {
      return {
        atom: list1[0],
        remainder: {
          list1: list1.slice(1),
          list2,
        },
      };
    } else {
      return {
        atom: list2[0],
        remainder: {
          list1,
          list2: list2.slice(1),
        },
      };
    }
  },
  combine: ({ left, right }) => [left, ...right],
});

我们还可以更进一步!

二元递归

我们来实现一个叫 binrec 的函数,这个函数实现了二元递归。我们一开始举例子是合并两个已经排好序的列表,而 merge 函数经常被用在合并排序(merge sort)中。

binrec 实际上比 linrec 更简单。linrec 还要将输入值分为单个元素和剩余元素,binrec 将问题分成两部分,然后将同一个算法应用到这两个部分中:

function binrec({ indivisible, value, divide, combine }) {
  return function myself(input) {
    if (indivisible(input)) {
      return value(input);
    } else {
      let { left, right } = divide(input);
      left = myself(left);
      right = myself(right);
      return combine({ left, right });
    }
  };
}
const mergeSort = binrec({
  indivisible: (list) => list.length <= 1,
  value: (list) => list,
  divide: (list) => ({
    left: list.slice(0, list.length / 2),
    right: list.slice(list.length / 2),
  }),
  combine: ({ left: list1, right: list2 }) => merge({ list1, list2 }),
});
mergeSort([1, 42, 4, 5]);
//=> [1, 4, 5, 42]

脑洞再开大点,基于二元递归,我们还能扩展出多元递归,即将问题分成随意数量的对称部分:

function mapWith(fn) {
  return function*(iterable) {
    for (const element of iterable) {
      yield fn(element);
    }
  };
}
function multirec({ indivisible, value, divide, combine }) {
  return function myself(input) {
    if (indivisible(input)) {
      return value(input);
    } else {
      const parts = divide(input);
      const solutions = mapWith(myself)(parts);
      return combine(solutions);
    }
  };
}
const mergeSort = multirec({
  indivisible: (list) => list.length <= 1,
  value: (list) => list,
  divide: (list) => [
    list.slice(0, list.length / 2),
    list.slice(list.length / 2),
  ],
  combine: ([list1, list2]) => merge({ list1, list2 }),
});

我们还可以继续探索无数多个高阶函数,不过我刚刚展示的这几个已经够了。让我们回过头再来思考下表达性和可感知复杂度。

高阶函数,表达性,和复杂度之间的关系

…(太啰嗦,重复之前的内容,不翻译了)…… 如果两个函数实现了同一项职责,那我们的程序就不够 DRY (don’t repeat yourself),表达性也差。

高阶函数和这个有什么关系?如我们刚看到的,summerge 在解决域里面有不同的职责,一个是合并列表,一个是列表求总。但是两者共享同一个实现结构,那就是线性递归。所以,他们都负责实现线性递归算法。

通过把线性递归算法抽离出来,我们确保有且仅有一个实体 — linrec — 负责实现线性递归。由此,我们发现了,一等公民函数通过创建函数间的多对多关系,确实帮助了我们实现更强大的表达性。

然而,我们也知道,如果不利用某些语言特性或者架构设计来将函数进行分组管理,这种高阶函数的用法会增加程序的可感知复杂度。分组之后,组内函数依然存在丰富的相互关系,但是组之间的关系是限定的。

一对多和多对多

我们来比较下分别用 binrecmultirec 来实现 mergeSort

const mergeSort1 = binrec({
  indivisible: (list) => list.length <= 1,
  value: (list) => list,
  divide: (list) => ({
    left: list.slice(0, list.length / 2),
    right: list.slice(list.length / 2),
  }),
  combine: ({ left: list1, right: list2 }) => merge({ list1, list2 }),
});
const mergeSort2 = multirec({
  indivisible: (list) => list.length <= 1,
  value: (list) => list,
  divide: (list) => [
    list.slice(0, list.length / 2),
    list.slice(list.length / 2),
  ],
  combine: ([list1, list2]) => merge({ list1, list2 }),
});

我们传给 linrec 和 multirec 的函数挺有趣,来给他们命名下:

const hasAtMostOne = (list) => list.length <= 1;
const Identity = (list) => list;
const bisectLeftAndRight = (list) => ({
  left: list.slice(0, list.length / 2),
  right: list.slice(list.length / 2),
});
const bisect = (list) => [
  list.slice(0, list.length / 2),
  list.slice(list.length / 2),
];
const mergeLeftAndRight = ({ left: list1, right: list2 }) =>
  merge({ list1, list2 });
const mergeBisected = ([list1, list2]) => merge({ list1, list2 });

观察下函数名和函数的实际功能,你能发现某些函数,如 hasAtMostOne, Identitybisect 感觉像是通用目的函数,我们在写当前应用或其它应用时都会用到这种函数。事实上,这些函数确实能在一些通用目的函数工具库里找到。他们表达了在列表上的通用操作。(【译者注】:Ramda 里面的 identity 函数和这里一样。identity 函数,以及类似的 const always = x => y => x 一点都不无厘头,他们在特定上下文才有意义)

bisectLeftAndRightmergeLiftAndRight 则显得目的更特殊。他们不大可能被用在其它地方。mergeBisected 则混合一点,我们可能在其它地方能用到它,也可能用不到。

如本文一开始就一再强调的,这种多对多的函数关系,能帮助我们提升代码表达性,以及在程序实体和职责之间创建一对一的关系。例如,bisect 的职责就是把列表分成两部分。我们可以让代码其它所有部分都调用 bisect,而不是一直反复实现这个功能。

如果一个函数提供的接口或“行为协议”越通用,一个函数承担的职责越集中和简单,此函数创建多对多关系的能力就越强。因此,当我们写像 multirec 这样的高阶函数时,我们应当如此设计这些函数,使得它们接收通用目的函数为参数,而这些通用目的函数只承担简单职责。

我们同时也可以写像 bisectLeftAndRightmergeLeftAndRight 这种函数。当我们这样写的时候,程序中就会存在一对多关系,因为除了在 merge 函数中有用外,它们没什么通用功能。这限制了我们程序的表达性。

不幸的是,这种限制并不必然意味着程序的可感知复杂度的随之降低。通过仔细阅读代码,我们能看出 bisectLeftAndRight 这种函数在程序其它地方并没有什么用。如果我们没有另外使用模块作用域等机制去限制这些函数的范围,让其易于发现,我们并不能降低程序的可感知复杂度。

由此,我们可以观察到,某些编程技巧,比如那种为函数写高度专一的接口,或者让函数承担复杂的职责的编程技巧,会让程序的表达性降低,但并不能降低程序的可感知复杂度。

高阶函数和框架和库有什么关系

粗略来讲,框架和库不过是一些类,函数和其它代码的集合。区别是,框架被设计成来调用我们的代码,库被设计成被我们的代码调用。

框架通常期待我们写出带有非常具体而专一接口和行为协议的函数或者其它程序实体。例如,Ember 要求我们去扩展它的基类去创建组件,而不是使用普通的 ES6 Class。如我们上面已阐明的,当我们写出专一的接口时,我们就限制了程序的表达性,但并没有因此而降低程序复杂度。

这意味着我们是在为框架写代码,这样框架的作者就不用操心去在框架代码和用户代码之间创建多对多的关系。例如,我们在写 Ember 类时,是没法使用 JavaScript mixins, subclass factories, 和 method advice 这些代码组合方式的。我们不得不使用 Ember 提供的专一的元编程工具,或者使用专为 Ember 开发的插件。

面向框架的代码更具有一对多特性,而不是多对多,这就降低了其表达性。

相比之下,库是被设计成被我们的代码调用的。最重要的是,库是被很多很多个编程风格迥异的团队调用的,这让库的作者们有动力去编写具有通用接口和简单职责的函数。

面向库的代码更具有多对多的特性,而不是一对多,这就使得它更有表达性。

那是不是面向框架的代码都是坏的?其实并不一定,只是取舍而已。框架提供了做事的标准方式。框架承诺帮我们干更多事情,特别是帮我们干很复杂的事。

理想情况下,虽然我们的代码在框架之下会变得表达性很低,我们的目的是写更少的代码。而我们使用其它手段来降低程序的可感知复杂度。

从我们对 linrec, binrecmultirec 这些高阶函数的探索中,我们发现专一接口和通用接口的对比,框架和库的取舍。

【原文】From Higher-Order Functions to Libraries And Frameworks


译后记

此文举例的高阶函数,是用递归实现的。大多数情况下,mergesum 是用迭代实现的。那么,这些例子还有什么用吗?multirec 多元递归的使用场景是什么?敬请期待下一篇译文《递归数据结构与图像处理》


Lambda Academy

Lei Huang

这个博客我主要分享函数式编程和前端开发。我还有一个英文网站