JavaScript杂谈——懒执行和尾递归

一说到函数式编程，无论是在理论上还是实践上，Haskell 肯定首先映入眼帘，F# 和 Scala 紧跟其后。如果你真想函数式编程，踏踏实实去学习上述三门语言吧。但是，函数式编程的思想，有一些是我们在 JavaScript 编程中可以借鉴的。

Lazy evaluation

暂且把它翻译为懒执行或者懒运行吧。懒执行的意思就是程序在它需要运行的时候才运行。在 JavaScript 中恰巧有这个概念，那就是 generator。

Generator 是个函数，当我们调用 next 方法时它才会运行。举个例子：

const thisIsAGenerator = function *() {
  let a = 0;
  for(;;) {
    yield a;
    a++;
  }
}

const g = thisIsAGenerator();
for (let i = 0; i < 5; i++) {
  console.log(g.next().value); // 0, 1, 2, 3, 4
}
g.return();
console.log(g.next()); // { value: undefined, done: true }

定义一个 generator 函数的标志就是 function 旁边有个 *。运行这个 generator 函数并不会立即运行函数体里的内容，而是返回给调用者一个 iterator 对象。当调用者调用这个 iterator 的 next 函数时，generator 函数体才会开始运行，并在第一个 yield 关键字处停止运行，并返回 yield 语句中的变量值给调用者。当调用者调用 iterator 对象的 return 函数时，generator 函数就结束了。

next 函数的返回值是一个对象，它有两个属性，value 和 done。其中 done 标识了这个 generator 函数是否已经结束。

我们都知道可以用 console.time 和 timeEnd 来计算一段程序的运行时间，假如某些情况下我们不能使用 console，或者想把测试结果保存起来，这时我们就可以利用 generator 来实现一个这个功能。

const timing = function *(time) {
  yield Date.now() - time;
}
const time = timing(Date.now());

// 开始
let sum = 0;
for (let i = 0; i < 1000000; i++) {
  sum = sum + i;
}
// 结束 

console.log(time.next().value) // 这里输出被开始和结束包裹起来的程序的运行时间

我们知道 Stream api 在 Node.js 中存在很长时间了。但是在浏览器中却迟迟没有被推行开来。利用 generator，我们可以实现类似 Stream api 的东西。

const nums = function *(f=null) {
  let i = 0;
  for(;;) {
    yield i;
    if (f) {
      i += f(i);
    } else {
      i += 1;
    }
  }
}

const data = [];
const nums_gen = nums(x=> x + 1);
for (let i of nums_gen) {
  console.log(i); // 0, 1, 3, 7, 15, 31, 63, 127, ...
  if(i > 10000) {
    break;
  }
  data.push(i);
}

nums 是个产生数字的 generator，它接收一个参数，这个参数是个函数，默认值是 null。它的内部逻辑很简单，从 0 开始，如果没有传递函数参数，每次返回值加 1，如果传递了函数，每次返回值加上函数作用后的结果，是不是有点儿像 map 函数的作用？然后我们利用这个数字产生器生成了一些数据 data，很简单，大家可以实际运行下代码看下结果。

有了数据我们就可以实现一个 Stream 了。

const testStream = function *(data) {
  const chunkSize = 5;
  const dataLen = data.length;
  let i = 0;
  while (i < dataLen) {
    const resultData = [];
    for (let j = 0; j < chunkSize; j++) {
      if (data[i]) {
        resultData.push(data[i]);
      }
      i += 1;
    }
    yield resultData;
  }
}

for (let i of testStream(data)) {
  console.log(i); // [ 1, 3, 7, 15 ] [ 31, 63, 127, 255, 511 ] [ 1023, 2047, 4095, 8191 ]
}

注意，此代码传入的 data 是上一段代码生成的。testStream(data) 类似于 fs.createReadStream(data)，后面的 for of 操作类似于 readerStream.on('data', function(chunk){})。

尾递归优化

这是另一个函数式语言中的概念，但是 JavaScript 引擎没有提供此功能（Webkit除外）。尾递归优化就是让递归的运行方式像运行普通循环一样。在纯函数式编程语言中，比如 Haskell，是没有循环语句的，所以只能通过递归来实现循环。下面我们来验证下 JavaScript 引擎确实没有尾递归优化，也就是正确书写尾递归也一样爆栈。

// 生成数据
const d = new Array(100000);
for(let i = 0; i < d.length; i++) {
  d[i] = i;
}

// 尾递归函数
const sumFn = function(data, sum=0) {
  if(!data.length) {
    return sum;
  }
  
  return sumFn(data.slice(1), sum + data[0]);
}

console.log(sumFn(d)); // JavaScript heap out of memory

sumFn 就是我们的尾递归函数，用来计算一个 10 万个数据的加和。一些编译器看到该函数的最后一句是调用自己，那么就会对该程序作出优化，不会出现堆栈溢出的情况。然而大多数 JavaScript 引擎并没有对此作出优化。但并不是没有办法，那就是 trampolining 函数。实现如下：

const trampoline = (fn) => {
  return (...args) => {
    let result = fn(...args);
    while(typeof result === 'function') {
      result = result();
    }
    return result;
  }
}

// 生成数据
const d = new Array(100000);
for(let i = 0; i < d.length; i++) {
  d[i] = i;
}

// 尾递归函数改造
const sumFn = function(data, sum=0) {
  if(!data.length) {
    return sum;
  }
  
  // 这里把尾递归调用变成了返回一个函数
  return () => sumFn(data.slice(1), sum + data[0]);
}

// 使用 trampolining
const finalSumFn = trampoline(sumFn)
console.log(finalSumFn(d)); // 4999950000

trampoline 函数接收一个函数作为参数，这个函数就是尾递归函数；然后它返回一个函数，这个函数相当于把尾递归函数又包装了一层，可以和 react 的高阶组件类比一下。在这个包装后的函数里，我们调用了尾递归函数，并对尾递归函数的返回值进行判断，如果返回结果还是函数，就继续运行它，直到返回结果不是函数为止。我们对尾递归函数的返回值做了修改，从之前的返回一个值变成了返回一个函数，这样就和 trampoline 函数的 while 循环对上了。说白了，trampoline 把经过改造的尾递归调用变成了 while 循环。

让我们不用循环重写下 filter 函数：

const _myFilter = function (data, fn, result=[]) {
  if(!data.length) {
    return result
  }
  
  return () => _myFilter(data.slice(1), fn, fn(data[0]) ? (result.length ? new Array(...result, data[0]) : [data[0]]) : result);
}

const myFilter = trampoline(_myFilter);
console.log(myFilter(d, x => x % 2 === 0));

其实和之前的加和函数差不多，唯一绕一点儿的就是那个嵌套三元表达式，其实也不没什么难的。外层的三元表达式的真值结果又是一个三元表达式而已，如果你把它写成 if 语句可能会更好理解写，但就不那么函数式了。

虽然解决了问题了，但付出的代价也不小，如果你测试一下的话，会发现 trampoline 函数会比普通 for 循环慢得多，array 内建的 filter 函数也比 trampoline 版的快得多。

如果有问题，请添加公众号“读一读我”。