#Function Memoization S1

中文标题：函数记忆化

#面向 JavaScript 的 Function.prototype.memo

ECMAScript 第一阶段提案。

提案负责人：Hemanth HM；J. S. Choi。

#理由

函数记忆化是一种常见的技术，它缓存函数调用的结果，并在再次出现相同输入时返回缓存的结果。这些技术可用于：

• 以空间换时间的方式优化昂贵的函数调用（例如阶乘、斐波那契数）。
• 缓存状态→UI 计算（例如 React 的 useMemo）。
• 确保回调始终返回相同的单例对象。
• 相互递归的递归下降解析。
• 实现来自元胞自动机的 hashlife。
• 物化数据库查询视图。
• 逻辑编程中的制表。

记忆化很有用、很常见，但写起来很烦人。我们提议探索在 JavaScript 语言中新增一个记忆化 API。

如果该提案被批准进入第一阶段，那么我们将探索 API 设计的各种方向。我们还将尽可能收集真实世界的用例，并围绕满足这些用例来塑造我们的设计。

此外，如果 proposal-policy-map-set 与本提案都被批准进入第一阶段，那么我们将探索记忆化函数如何使用这些数据结构来控制其缓存的内存使用。

#描述

Function.prototype.memo 方法将创建一个新函数，该函数针对每组给定的参数元组最多调用一次原函数。之后任何以相同参数对该新函数的调用，都将返回首次以这些参数调用时的结果。

function f (x) { console.log(x); return x * 2; }

const fMemo = f.memo();
fMemo(3); // Prints 3 and returns 6.
fMemo(3); // Does not print anything. Returns 6.
fMemo(2); // Prints 2 and returns 4.
fMemo(2); // Does not print anything. Returns 4.
fMemo(3); // Does not print anything. Returns 6.

此外，我们可能还会添加一个函数装饰器版本：@Function.memo。这将使记忆化更容易应用于函数声明：

@Function.memo
function f (x) { console.log(x); return x * 2; }

两种版本都可以用于递归函数：

// Version with prototype method:
const getFibonacci = (function (n) {
  if (n < 2) {
    return n;
  } else {
    return getFibonacci(n - 1) +
      getFibonacci(n - 2);
  }
}).memo();
console.log(getFibonacci(100));

// Version with function decorator:
@Function.memo
function getFibonacci (n) {
  if (n < 2) {
    return n;
  } else {
    return getFibonacci(n - 1) +
      getFibonacci(n - 2);
  }
}
console.log(getFibonacci(100));

#结果缓存

开发者将能够传入一个可选的 cache 参数。该参数必须是具有 .has、.get 和 .set 方法的类 Map 对象。特别是，有一个关于具有 LRUMap 等缓存替换策略的类 Map 对象的提案，它能让开发者轻松指定记忆化函数使用受内存约束的缓存。

我们至少可以通过两种可能的方式来设计 cache 参数；参见问题 3和问题 4。

#元组键？

A：我们可以使用元组作为缓存的键。每个元组代表对记忆化函数的一次调用，且元组的形式为 #[thisVal, newTargetVal, ...args]。

对象值将被能唯一标识该对象的符号（symbol）所取代。（元组不能直接包含对象。记忆化函数的闭包将持有一个内部 WeakMap，用于将对象映射到它们的符号。）

const cache = new LRUMap(256);
const f = (function f (arg0) { return this.x + arg0; }).memo(cache);
const o0 = { x: 'a' }, o1 = { x: 'b' };
f.call(o0, 0); // Returns 'a0'.
f.call(o1, 1); // Returns 'b1'.

此时 cache 将是 LRUMap(2) { #[s0, undefined, 0] ⇒ 'a0', #[s1, undefined, 1] ⇒ 'b1' }，其中 s0 和 s1 是唯一符号。f 的闭包将在内部持有一个 WeakMap { o0 ⇒ s0, o1 ⇒ s1 }。

memo 的默认行为（即未提供 cache 参数时）尚不确定（参见问题 3）。它可能只是一个无界的普通 Map。（WeakMap 不能将元组作为键。）

#复合键？

B：缓存的键的另一种选择是复合键。每个复合键代表对记忆化函数的一次调用，且复合键的形式为 compositeKey(thisVal, newTargetVal, ...args)。

const cache = new LRUMap(256);
const f = (function f (arg0) { return this.x + arg0; }).memo(cache);
const o0 = { x: 'a' }, o1 = { x: 'b' };
f.call(o0, 0); // Returns 'a0'.
f.call(o1, 1); // Returns 'b1'.

此时 cache 将是 LRUMap(2) { compositeKey(o0, undefined, 0) ⇒ 'a0', compositeKey(o1, undefined, 1) ⇒ 'b1' }。

memo 的默认行为（即未提供 cache 参数时）尚不确定（参见问题 3）。它可能只是一个 WeakMap，而 WeakMap 可以将复合键作为其键。

#未解决的问题

#问题 2：

memo 应该是一个原型方法、一个静态函数、一个函数装饰器，还是多种形式？

#问题 3：

缓存垃圾回收应如何工作？（使用 WeakMap 作为缓存是理想的……只是 WeakMap 不支持将原始值作为键。）

我们是否应该直接使用 Map，让开发者自己管理缓存内存？（另见 LRUMap 和 LFUMap。）

此外还有 compositeKeys 提案。

#问题 4：

如果我们采用 Map 缓存，应如何组织缓存结构？例如，我们可以使用 Map 树，或者在一个 Map 中使用参数元组作为键。

#问题 5：

函数调用应如何被视为“等价”？值如何比较（例如，使用像 === 那样的 SameValue，还是像 Map.get 那样的 SameValueZero）？this 绑定的接收者和 new.target 值是否也参与比较？

#先例

• lodash.memoize
• Undescore.js memoize
• Python functools.lru_cache
• 维基百科“函数记忆化”文章