Immutable.js或Lazy.js执行捷径融合吗？ [英] Do Immutable.js or Lazy.js perform short-cut fusion?

问题描述

首先，让我为那些不喜欢你的人定义捷径融合。我知道。在JavaScript中考虑以下数组转换：

First, let me define what is short-cut fusion for those of you who don't know. Consider the following array transformation in 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] ，但我们仍然会创建它。

Here we have an array, [1,2,3,4,5], whose elements are first squared, [1,4,9,16,25], and then incremented [2,5,10,17,26]. Hence, although we don't need the intermediate array [1,4,9,16,25], we still create it.

快捷融合是一种优化技术，它可以通过将一些函数调用合并为一个来消除中间数据结构。例如，可以将快捷方式融合应用于上述代码以产生：

Short-cut fusion is an optimization technique which can get rid of intermediate data structures by merging some functions calls into one. For example, short-cut fusion can be applied to the above code to produce:

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 通过编写 square map 调用中>和增量函数。因此，不会创建中间数组。

As you can see, the two separate map calls have been fused into a single map call by composing the square and increment functions. Hence the intermediate array is not created.

现在，我理解像 Immutable.js 和 Lazy.js 在JavaScript中模拟延迟评估。延迟评估意味着只在需要时计算结果。

Now, I understand that libraries like Immutable.js and Lazy.js emulate lazy evaluation in JavaScript. Lazy evaluation means that results are only computed when required.

例如，考虑上面的代码。虽然我们 square 和增量数组的每个元素，但我们可能不需要所有结果。

For example, consider the above code. Although we square and increment each element of the array, yet we may not need all the results.

假设我们只想要前3个结果。使用Immutable.js或Lazy.js，我们可以得到前3个结果， [2,5,10] ，而不计算最后2个结果， [17,26] ，因为不需要它们。

Suppose we only want the first 3 results. Using Immutable.js or Lazy.js we can get the first 3 results, [2,5,10], without calculating the last 2 results, [17,26], because they are not needed.

然而，懒惰的评估只会延迟计算结果直到需要。它不会通过融合函数来删除中间数据结构。

However, lazy evaluation just delays the calculation of results until required. It does not remove intermediate data structures by fusing functions.

为了明确这一点，请考虑以下代码来模拟延迟评估：

To make this point clear, consider the following code which emulates lazy evaluation:

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

如您所见，函数调用是交错，只处理数组的前三个元素，证明结果确实懒惰地计算：

As you can see, the function calls are interleaved and only the first three elements of the array are processed, proving that the results are indeed computed lazily:

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

如果不使用延迟评估，那么结果将是是：

If lazy evaluation is not used then the result would be:

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 数据结构。没有进行快捷融合。

However, if you see the source code then each function list, map, take and mapSeq returns an intermediate List data structure. No short-cut fusion is performed.

这让我想到了我的主要问题：像Immutable.js和Lazy这样的库.js执行捷径融合？

This brings me to my main question: do libraries like Immutable.js and Lazy.js perform short-cut fusion?

我问的原因是因为根据文档，他们明显地”做。但是，我持怀疑态度。我怀疑他们是否真的进行了快捷融合。

The reason I ask is because according to the documentation, they “apparently” do. However, I am skeptical. I have my doubts whether they actually perform short-cut fusion.

例如，这取自 README.md 文件：

不可变还提供了一个懒惰的 Seq ，允许有效链接收集方法，如 map 和过滤器而不创建中间表示。使用 Range 和重复创建一些 Seq 。

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 和过滤器 ，无需创建中间表示（即他们执行快捷方式）融合）。

So the developers of Immutable.js claim that their Seq data structure allows efficient chaining of collection methods like map and filter without creating intermediate representations (i.e. they perform short-cut fusion).

但是，我不认为他们在代码。也许我找不到它，因为他们使用的是ES6，我的眼睛对ES6语法并不太熟悉。

However, I don't see them doing so in their code anywhere. Perhaps I can't find it because they are using ES6 and my eyes aren't all too familiar with ES6 syntax.

此外，在 Lazy Seq ：

Seq 描述了一个惰性操作，允许他们有效地链接使用所有Iterable方法（例如 map 和过滤器）。

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

Seq是不可变的 - 创建Seq后，无法更改，附加，重新排列或以其他方式修改。相反，在Seq上调用的任何变异方法都会返回一个新的Seq。

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是懒惰的 - Seq尽可能少地响应任何方法调用。

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

因此确定 Seq 确实是懒惰的。但是，没有示例表明确实没有创建中间表示（他们声称这样做）。

So it is established that Seq is indeed lazy. However, there are no examples to show that intermediate representations are indeed not created (which they claim to be doing).

继续使用Lazy.js我们也有同样的情况。值得庆幸的是，Daniel Tao写了一篇关于Lazy.js如何工作的博客文章，其中他提到Lazy.js的核心是功能组合。他给出了以下示例：

Moving on to Lazy.js we have the same situation. Thankfully, Daniel Tao wrote a blog post on how Lazy.js works, in which he mentions that at its heart Lazy.js simply does function composition. He gives the following example:

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>

这里地图，过滤器和 take 函数产生中间 MappedSequence ， FilteredSequence 和 TakeSequence 对象。这些 Sequence 对象本质上是迭代器，不需要中间数组。

Here the map, filter and take functions produce intermediate MappedSequence, FilteredSequence and TakeSequence objects. These Sequence objects are essentially iterators, which eliminate the need of intermediate arrays.

但是，据我所知，仍然没有发生捷径融合。中间数组结构简单地替换为未融合的中间 Sequence 结构。

However, from what I understand, there is still no short-cut fusion taking place. The intermediate array structures are simply replaced with intermediate Sequence structures which are not fused.

我可能错了，但是我相信像 Lazy（array）.map（f）.map（g）这样的表达式产生两个单独的 MappedSequence 对象其中第一个 MappedSequence 对象将其值提供给第二个，而不是第二个通过执行两者的工作替换第一个（通过函数组合）。

I could be wrong, but I believe that expressions like Lazy(array).map(f).map(g) produce two separate MappedSequence objects in which the first MappedSequence object feeds its values to the second one, instead of the second one replacing the first one by doing the job of both (via function composition).

TLDR： Immutable.js和Lazy.js确实执行快捷融合吗？据我所知，他们通过序列对象（即迭代器）模拟延迟评估来摆脱中间数组。但是，我相信这些迭代器是链接的：一个迭代器懒洋洋地将它的值提供给下一个迭代器。它们不会合并为单个迭代器。因此他们没有消除中间表征。它们只将数组转换为常量空间序列对象。

TLDR: Do Immutable.js and Lazy.js indeed perform short-cut fusion? 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.

推荐答案

我是Immutable.js的作者（和Lazy的粉丝） .js）。

I'm the author of Immutable.js (and a fan of Lazy.js).

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

Does Lazy.js and Immutable.js's Seq use short-cut fusion? No, not exactly. But they do remove intermediate representation of operation results.

快捷融合是一种代码编译/转换技术。你的例子很好：

Short-cut fusion is a code compilation/transpilation technique. Your example is a good one:

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不是转发器，也不会重写代码。它们是运行时库。因此，它们使用可迭代组合（运行时技术）而不是捷径融合（编译器技术）。

Lazy.js and Immutable.js are not transpilers and will not re-write code. They are runtime libraries. So instead of short-cut fusion (a compiler technique) they use iterable composition (a runtime technique).

您在TLDR中回答这个问题：

You answer this in your TLDR:

据我所知，他们通过序列对象（即迭代器）模拟lazy
评估来摆脱中间数组。但是，我相信这些迭代器被链接的
：一个迭代器将它的值
懒洋洋地提供给下一个。它们不会合并为单个迭代器。因此，
他们没有消除中间陈述。它们只有
将数组转换为常量空间序列对象。

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.

这是完全正确的。

让我们解包：

Arrays在链接时存储中间结果：

Arrays store intermediate results when chaining:

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)

快捷融合转换创建了中间函数：

Short-cut fusion transpilation creates intermediate functions:

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)

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

Iterable composition creates intermediate iterables:

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] 的数据结构。

Note that using iterable composition, we have not created a store of intermediate results. When these libraries say they do not create intermediate representations - what they mean is exactly what is described in this example. No data structure is created holding the values [1,4,6,8,10].

但是，当然一些中间表示。每个懒惰操作必须返回一些东西。他们返回一个可迭代的。创建这些非常便宜并且与正在操作的数据的大小无关。注意，在短切融合转录中，还进行了中间表示。 compose 的结果是一个新函数。功能组合（手写或快捷融合编译器的结果）与可迭代组合非常相关。

However, of course some intermediate representation is made. Each "lazy" operation must return something. They return an iterable. Creating these is extremely cheap and not related to the size of the data being operated on. Note that in short-cut fusion transpilation, an intermediate representation is also made. The result of compose is a new function. Functional composition (hand-written or the result of a short-cut fusion compiler) is very related to Iterable composition.

删除中间表示的目标是性能，尤其是关于记忆。可重构组合是一种实现此功能的强大方法，并且不需要解析和重写优化编译器代码的开销，这些代码在运行时库中是不合适的。

The goal of removing intermediate representations is performance, especially regarding memory. Iterable composition is a powerful way to implement this and does not require the overhead that parsing and rewriting code of an optimizing compiler which would be out of place in a runtime library.

Appx：

这是 lazyMap 的简单实现看起来像：

This is what a simple implementation of lazyMap might look like:

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

这篇关于Immutable.js或Lazy.js执行捷径融合吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！