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) }
        }
      };
    }
  };
}