Immutable.js或Lazy.js执行短路融合吗？

Question

9 浏览2023年4月19日

匿名的 2023年4月19日

0 Comments

首先，让我为那些不了解“短路融合（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调用已经通过组合square和increment函数合并为一个单独的map调用。因此，不会创建中间数组。

现在，我理解像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还提供了一个惰性的Seq，允许高效地链接像map和filter这样的集合方法，而不创建中间表示。使用Range和Repeat创建一些Seq。

因此，Immutable.js的开发者声称他们的Seq数据结构允许高效地链接像map和filter这样的集合方法，而不创建中间表示（即执行了短路融合）。

然而，我在他们的代码中没有看到他们在任何地方这样做。也许我找不到它是因为它们使用了ES6，而我的眼睛对ES6语法并不太熟悉。

此外，在他们关于Lazy Seq的文档中，他们提到：

Seq描述了一种惰性操作，允许它们高效地链接所有可迭代方法（例如map和filter）。

Seq是不可变的 - 一旦创建了一个Seq，它就无法改变、追加、重新排列或以其他方式修改。相反，对Seq调用的任何变异方法都将返回一个新的Seq。

Seq是惰性的 - Seq做尽量少的工作来响应任何方法调用。

因此，可以确定Seq确实是惰性的。然而，并没有示例显示确实没有创建中间表示（他们声称正在执行此操作）。

接下来是Lazy.js，情况也是一样。幸运的是，Daniel Tao在他的博客文章中介绍了Lazy.js的工作原理，在其中提到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);
}

在这里，map、filter和take函数产生中间的MappedSequence、FilteredSequence和TakeSequence对象。这些Sequence对象本质上是迭代器，消除了中间数组的需要。

然而，据我了解，仍然没有进行短路融合。中间数组结构只是被中间的Sequence结构替换，而这些结构并没有融合。

我可能是错的，但我相信像Lazy(array).map(f).map(g)这样的表达式会产生两个单独的MappedSequence对象，其中第一个MappedSequence对象将其值懒惰地传递给第二个对象，而不是第二个对象通过函数组合来替换第一个对象并完成两者的工作（通过函数组合）。

简而言之：Immutable.js和Lazy.js是否确实执行短路融合？据我所知，它们通过模拟惰性求值使用序列对象（即迭代器）来消除中间数组。然而，我认为这些迭代器是链接的：一个迭代器惰性地将其值传递给下一个迭代器，而不是将其合并为一个迭代器。因此，它们并没有“消除中间表示”。它们只是将数组转换为常数空间的序列对象。

0

Immutable.js或Lazy.js执行短路融合吗？

0 答案