javascript - Immutable.js或Lazy.js是否执行捷径融合？

Question

首先，让我为不认识的人定义short-cut fusion。考虑以下JavaScript中的数组转换:

var a = [1,2,3,4,5].map(square).map(increment);

console.log(a);

function square(x) {
    return x * x;
}

function increment(x) {
    return x + 1;
}

在这里，我们有一个数组 [1,2,3,4,5]，其元素首先平方 [1,4,9,16,25]，然后递增 [2,5,10,17,26]。因此，尽管我们不需要中间数组 [1,4,9,16,25]，我们仍然可以创建它。
捷径融合是一种优化技术，可以通过将一些函数调用合并为一个来摆脱中间数据结构。例如，可以将捷径融合应用于上述代码以产生:

var a = [1,2,3,4,5].map(compose(square, increment));

console.log(a);

function square(x) {
    return x * x;
}

function increment(x) {
    return x + 1;
}

function compose(g, f) {
    return function (x) {
        return f(g(x));
    };
}

如您所见，通过组合 map和 map函数，将两个单独的 square调用合并为一个 increment调用。因此，不会创建中间数组。

现在，我了解到 Immutable.js和 Lazy.js之类的库在JavaScript中模拟了惰性评估。惰性评估意味着仅在需要时才计算结果。
例如，考虑上面的代码。尽管我们 square和 increment数组的每个元素，但是我们可能不需要所有结果。
假设我们只想要前3个结果。使用Immutable.js或Lazy.js，我们可以获取前3个结果 [2,5,10]，而无需计算后2个结果 [17,26]，因为不需要它们。
但是，延迟评估只会延迟结果的计算，直到需要为止。它不会通过融合功能删除中间数据结构。
为了清楚说明这一点，请考虑以下模拟延迟评估的代码:

var List = defclass({
    constructor: function (head, tail) {
        if (typeof head !== "function" || head.length > 0)
            Object.defineProperty(this, "head", { value: head });
        else Object.defineProperty(this, "head", { get: head });

        if (typeof tail !== "function" || tail.length > 0)
            Object.defineProperty(this, "tail", { value: tail });
        else Object.defineProperty(this, "tail", { get: tail });
    },
    map: function (f) {
        var l = this;

        if (l === nil) return nil;

        return cons(function () {
            return f(l.head);
        }, function () {
            return l.tail.map(f);
        });
    },
    take: function (n) {
        var l = this;

        if (l === nil || n === 0) return nil;

        return cons(function () {
            return l.head;
        }, function () {
            return l.tail.take(n - 1);
        });
    },
    mapSeq: function (f) {
        var l = this;
        if (l === nil) return nil;
        return cons(f(l.head), l.tail.mapSeq(f));
    }
});

var nil = Object.create(List.prototype);

list([1,2,3,4,5])
    .map(trace(square))
    .map(trace(increment))
    .take(3)
    .mapSeq(log);

function cons(head, tail) {
    return new List(head, tail);
}

function list(a) {
    return toList(a, a.length, 0);
}

function toList(a, length, i) {
    if (i >= length) return nil;

    return cons(a[i], function () {
        return toList(a, length, i + 1);
    });
}

function square(x) {
    return x * x;
}

function increment(x) {
    return x + 1;
}

function log(a) {
    console.log(a);
}

function trace(f) {
    return function () {
        var result = f.apply(this, arguments);
        console.log(f.name, JSON.stringify([...arguments]), result);
        return result;
    };
}

function defclass(prototype) {
    var constructor = prototype.constructor;
    constructor.prototype = prototype;
    return constructor;
}

如您所见，函数调用是交错的，并且仅处理数组的前三个元素，证明结果的确是延迟计算的:

square [1] 1
increment [1] 2
2
square [2] 4
increment [4] 5
5
square [3] 9
increment [9] 10
10

如果不使用惰性评估，则结果将是:

square [1] 1
square [2] 4
square [3] 9
square [4] 16
square [5] 25
increment [1] 2
increment [4] 5
increment [9] 10
increment [16] 17
increment [25] 26
2
5
10

但是，如果您看到源代码，则每个函数 list， map， take和 mapSeq返回一个中间的 List数据结构。不执行捷径融合。

这使我想到了一个主要问题:Immutable.js和Lazy.js之类的库是否执行捷径融合？
我问的原因是因为根据文档，它们“显然”是这样做的。但是，我对此表示怀疑。我怀疑他们是否真正执行了捷径融合。
例如，这取自Immutable.js的 README.md文件:

Immutable also provides a lazy Seq, allowing efficient chaining of collection methods like map and filter without creating intermediate representations. Create some Seq with Range and Repeat.

因此，Immutable.js的开发人员声称，他们的 Seq数据结构可高效链接诸如 map和 filter 之类的收集方法，而无需创建中间表示(即，他们执行捷径融合)。
但是，我在任何地方的 code中都看不到他们这样做。也许我找不到它，因为他们正在使用ES6，而且我对ES6语法不太熟悉。
此外，在他们的 Lazy Seq文档中，他们提到:

Seq describes a lazy operation, allowing them to efficiently chain use of all the Iterable methods (such as map and filter).

Seq is immutable — Once a Seq is created, it cannot be changed, appended to, rearranged or otherwise modified. Instead, any mutative method called on a Seq will return a new Seq.

Seq is lazy — Seq does as little work as necessary to respond to any method call.

因此可以确定 Seq确实是懒惰的。但是，没有任何示例显示确实没有创建中间表示(他们声称这样做)。

转到Lazy.js，我们遇到的情况相同。值得庆幸的是，丹尼尔·陶(Daniel Tao)就Lazy.js的工作方式写了一个 blog post，其中他提到Lazy.js的核心只是功能组合。他给出了以下示例:

Lazy.range(1, 1000)
    .map(square)
    .filter(multipleOf3)
    .take(10)
    .each(log);

function square(x) {
    return x * x;
}

function multipleOf3(x) {
    return x % 3 === 0;
}

function log(a) {
    console.log(a);
}

<script src="https://rawgit.com/dtao/lazy.js/master/lazy.min.js"></script>

在这里， map， filter和 take函数产生中间 MappedSequence， FilteredSequence和 TakeSequence对象。这些 Sequence对象本质上是迭代器，无需中间数组。
但是，据我了解，仍然没有捷径融合发生。中间数组结构简单地替换为未融合的中间 Sequence结构。
我可能是错的，但我相信像 Lazy(array).map(f).map(g)这样的表达式会产生两个单独的 MappedSequence对象，其中第一个 MappedSequence对象将其值提供给第二个对象，而不是第二个通过完成两者的工作来替换第一个(通过函数组合) )。
TLDR: Immutable.js和Lazy.js是否确实执行快捷融合？据我所知，它们通过序列对象(即迭代器)模拟惰性求值来摆脱中间数组。但是，我相信这些迭代器是链接在一起的:一个迭代器懒惰地将其值提供给下一个。它们不会合并到单个迭代器中。因此，它们不会“消除中间表示”。它们仅将数组转换为恒定的空间序列对象。

Answer 1

我是Immutable.js的作者(也是Lazy.js的粉丝)。

Lazy.js和Immutable.js的Seq是否使用捷径融合？不，不完全是。但是它们确实删除了操作结果的中间表示。

捷径融合是一种代码编译/翻译技术。您的例子很好:

var a = [1,2,3,4,5].map(square).map(increment);

转译:

var a = [1,2,3,4,5].map(compose(square, increment));

Lazy.js和Immutable.js并非编译器，也不会重新编写代码。它们是运行时库。因此，它们使用可迭代的组合(运行时技术)来代替捷径融合(一种编译器技术)。

您在TLDR中回答此问题:

As far as I know they get rid of intermediate arrays by emulating lazy evaluation via sequence objects (i.e. iterators). However, I believe that these iterators are chained: one iterator feeding its values lazily to the next. They are not merged into a single iterator. Hence they do not "eliminate intermediate representations". They only transform arrays into constant space sequence objects.

完全正确。

让我们打开包装:

数组在链接时存储中间结果:

var a = [1,2,3,4,5];
var b = a.map(square); // b: [1,4,6,8,10] created in O(n)
var c = b.map(increment); // c: [2,5,7,9,11] created in O(n)

快捷融合转译创建中间功能:

var a = [1,2,3,4,5];
var f = compose(square, increment); // f: Function created in O(1)
var c = a.map(f); // c: [2,5,7,9,11] created in O(n)

可迭代组合创建中间可迭代:

var a = [1,2,3,4,5];
var i = lazyMap(a, square); // i: Iterable created in O(1)
var j = lazyMap(i, increment); // j: Iterable created in O(1)
var c = Array.from(j); // c: [2,5,7,9,11] created in O(n)

请注意，使用可迭代组合，我们尚未创建中间结果存储。当这些库说不创建中间表示时，它们的含义恰恰是本示例中描述的内容。不会创建包含值 [1,4,6,8,10]的数据结构。

但是，当然 是一些的中间表示形式。每个“惰性”操作都必须返回某些内容。他们返回一个迭代。创建这些文件非常便宜，并且与所操作的数据大小无关。注意，在快捷融合转译中，也进行了中间表示。 compose的结果是一个新函数。功能组合(手写或捷径融合编译器的结果)与Iterable组合非常相关。

删除中间表示形式的目的是提高性能，尤其是在内存方面。可迭代的组合是实现此目标的强大方法，并且不需要解析和重写优化编译器的代码(这些代码在运行时库中是不合适的)的开销。

Appx:

这是 lazyMap的简单实现可能是这样的:

function lazyMap(iterable, mapper) {
  return {
    "@@iterator": function() {
      var iterator = iterable["@@iterator"]();
      return {
        next: function() {
          var step = iterator.next();
          return step.done ? step : { done: false, value: mapper(step.value) }
        }
      };
    }
  };
}