EEP 19：列表推导式多生成器 #

摘要 #

向列表推导式添加受 Clean 启发的多个序列生成器，使代码更清晰地表达意图，并减少对 zip 的需求。

这与 EEP 12 有关，但与其无关。

规范 #

目前，Erlang 有

Pattern <- Expr

枚举单个列表的元素，以及

Pattern <= Expr

枚举二进制数据。EEP 12 添加了

Pattern [<-] List
Pattern {<-} Tuple
Pattern <<<->> Binary

本提案将其更改为

generator: term_generator | binary_generator;
binary_generator: pattern '<=' expression;
term_generator: term_generator '&&' term_generator
              | pattern '<-' expression;

如果我们坚持目前的 Erlang，或者

generator: term_generator | binary_generator;
binary_generator: pattern '<=' expression
                | pattern '<<' '<-' '>>' expression;
term_generator: term_generator '&&' term_generator
              | pattern '<-' expression
              | pattern '[' '<-' ']' expression
              | pattern '{' '<-' '}' expression;

如果我们采用 EEP 12。

粗略地说，忽略错误和副作用，P1 <- E1 && ... Pn <- En 的效果与 {P1,...,Pn} <- zip(E1, ..., En) 的效果相同，其中

zip([X1|Xs1], ..., [Xn|Xsn]) ->
    [{X1,...,Xn} | zip(Xs1, ..., Xsn)];
zip([], ..., []) ->
    [].

但是，预计实现中不会创建任何额外的列表或元组；这指定了效果，而不是如何实现。

使用 EEP 12 新表示法的项生成器的效果是，先替换

P {<-} E   with   P <- tuple_to_list(E)
P [<-] E   with   P <- E

然后应用上面的转换而得到的效果。

在出现错误的情况下，&& 的行为与使用 zip 的行为不完全相同。我们需要更精确地指定实际行为。为了简洁起见，我忽略了二进制枚举。元组枚举和元组推导式目前都通过重写为普通列表推导式来定义，所以这是我们现在需要担心的全部。

列表推导式的形式为 [E || C1, ..., Cn]，其中每个 Ci 是

• 一个生成器 Pattern <- List_Expression
• 一个绑定 Pattern = Any_Expression
• 一个“保护” Other_Expression，应该给出 true 或 false。

它的行为类似于

R = [],
<| E || [C1, ..., Cn] |>(R),
reverse(R)

其中

<| E || [] |>(R)
=>  R = [E | R]             % reassign R

<| E || [Pi <- Ei|Cs] |>(R)
=>  Ti = Ei
    Label: case Ti
             of [Pi|X] -> Ti = X % reassign Ti
                          <| E || Cs |>(R)
                          goto Label
              ; [_ |X] -> Ti = X % reassign Ti
                          goto Label
              ; []     -> ok
           end

<| E || [Pi = Ei|Cs] |>(R)
=>  case Ei
      of Pi -> <| E || Cs |>(R)
       ; _  -> ok
    end

<| E || [Ei|Cs] |>(R)
=>  case Ei
      of true  -> <| E || Cs |>(R)
       ; false -> ok
    end

在这些转换中，使用了模式匹配语法，其目的是，根据 Erlang 的正常规则未绑定的变量，因此通过 Pi <- 或 Pi = 匹配绑定，被视为好像在要生成的代码中未绑定，忽略它们之前可能拥有的任何值。当 R 或 Ti 出现在模式匹配的左侧时，情况也是如此；忽略变量确实已绑定的事实，并完成一个简单的赋值。

这确实涉及（重新）分配给要生成的代码中的局部变量，但它不涉及用户可见的分配，也不涉及可变数据结构。对于语言或运行时系统来说，它与重用一个死的寄存器相比没有更多的问题。

处理多列表枚举是对枚举规则的简单，但示意性的更改。

<| E || [Pi1 <- Ei1 && Pi2 <- Ei2 && ... && Pik <- Eik|Cs] |>(R)
=>  Ti1 = Ei1
    ...
    Tik = Eik
    Label: case {Ti1,...,Tik}
             of {[Pi1|X1], ..., [Pik,Xk]} ->
                Ti1 = X1    % reassign
                ...
                Tik = Xk    % reassign
                <| E || Cs |>(R)
                goto label
              ; {[_|X1], ..., [_|Xk]} ->
                Ti1 = X1    % reassign
                ...
                Tik = Xk    % reassign
              ; {[], ..., []} ->
                ok
           end

请注意，case 表达式和 case 子句中使用元组语法并不意味着在生成的代码中字面创建元组，而只意味着在每个 case 子句中将 k 个值与 k 个模式匹配。

动机 #

“我如何一次迭代多个列表？”是来自 Erlang 和 Haskell 初学者的一个比较常见的问题。标准的答案是“使用 zip”，对于 Haskell 来说，这几乎是可以接受的，因为 zip 系列最多可以处理 7 个列表，并且编译器会努力使用森林消除来消除中间数据结构。对于 Erlang 来说，即使缺少 zip4，并且创建不需要的列表和元组的明显成本也太真实了，使用 zips 会使代码更难阅读，这意味着没有任何好处可以抵消坏处。

使用新的表示法，

zip4(As, Bs, Cs, Ds) ->
    [{A,B,C,D} || A <- As && B <- Bs && C <- Cs && D <- Ds].

zipwith4(F, As, Bs, Cs, Ds) ->
    [F(A,B,C,D) || A <- As && B <- Bs && C <- Cs && D <- Ds].

dot(Xs, Ys) ->
    sum([X*Y || X <- Xs && Y <- Ys]).

ifelse(Tests, Xs, Ys) -> % Simulate R's ifelse(,,)
    [  case T of true -> X ; false -> Y end
    || T <- Tests && X <- Xs && Y <- Ys
    ].

来自模块 dialyzer_dep 的这段代码

merge_outs([#output{type=list, content=L1}|Left],
           #output{type=list, content=L2}) ->
  NewList = [merge_outs([X, Y]) || {X, Y} <- lists:zip(L1, L2)],
  merge_outs(Left, output(NewList));

将变成

merge_outs([#output{type=list, content=L1}|Left],
            #output{type=list, content=L2]) ->
    merge_outs(Left, output(
        [merge_outs([X,Y]) || X <- L1 && Y <- L2]));

来自模块 dialyzer_dataflow 中的 forward_args/3 的这段代码

NewArgTypes = [t_sup(X, Y) ||
               {X, Y} <- lists:zip(ArgTypes, OldArgTypes)],

将变成

NewArgTypes = [t_sup(X, Y) || X <- ArgTypes && Y <- OldArgTypes],

理由 #

这是一个真正不需要发明的情况。Clean 有

Qualifier = Generators {|Guard}
Generators = {Generator}-list
           | Generator {& Generator}
Generator = Selector <- ListExpr // lazy list
          | Selector <|- ListExpr // overloaded list
          | Selector <-: ArrayExpr //  array

我所要做的就是稍微调整一下，使其适合 Erlang 的语法。由于我们使用“||”表示列表推导式，“&&”是同步生成器的明显拼写。

我还不详细了解 Erlang 编译器的工作原理，但它似乎涉及生成辅助函数。让我们以

[f(X) || X <- Xs, X > 0]

为例。这似乎被编译为

foo(Xs)

其中

foo([X|Xs]) when X > 0 -> [f(X) | foo(Xs)];
foo([_|Xs]) -> foo(Xs);
foo([]) -> [].

使用多序列生成器，转换是类似的。

[g(X, Y) || X <- Xs && Y <- Ys, X > Y]

可以编译为

bar(Xs, Ys)

其中

bar([X|Xs], [Y|Ys]) when X > Y ->
    [g(X, Y) | bar(Xs, Ys)];
bar([_|Xs], [_|Ys]) -> bar(Xs, Ys);
bar([], []) -> [].

上面的规范给出了我希望看到的转换类型；我确实有一个基于 Pop-2 的实现，不需要反转，但不知道它如何适应 BEAM。

一个明显的问题是，我们是否真的需要这个。为什么不让人们直接调用 lists:zip 并让编译器优化它们呢？一个答案是，这种表示法更清晰；程序员的意图是同时沿着两个或多个列表前进，而不是创建一对列表。当你想创建一个对列表时，lists:zip/2 是完美的方法。更重要的答案是，提议的表示法不是简单地优化使用 lists:zip/2 的等效代码。

[E || {P,Q} <- lists:zip(A, B)]    % "zip version"

如果 A 和 B 不是长度相同的正确列表，则会立即失败。

[E || P <- A && Q <- B]            % "Clean version"

如果 A 和 B 不是长度相同的正确列表，则最终会失败，但在那之前可能已经多次评估了 E（这可能具有副作用）。因此，Erlang 编译器不允许将“zip 版本”替换为“Clean 版本”，除非它可以证明 A 和 B 都是列表（这可能在 Dialyzer 的能力范围内），并且它们的长度完全相同（据我所知不是）。

但是，多序列生成器和使用 lists:zip/2 调用的单序列生成器显然是相似的，因此它们最终应该以相同的方式响应不同长度的列表。在 Haskell 中，将两个不同长度的列表压缩在一起的行为就像将较长的列表截断为较短的列表的长度一样。由于 Haskell 具有惰性求值，列表可能是无限的，因此您不能等到最后才开始列表推导式。由于 Erlang 是严格的，并且错误很常见，因此 Erlang 中的 lists:zip/2 是有意义的。

向后兼容性 #

“运算符”‘&&’目前在 Erlang 中的任何地方都不是合法的语法，因此不会影响任何现有代码。

参考实现 #

目前还没有，但我想在弄清楚如何做的时候去做。

版权 #

本文档已置于公共领域。[EmacsVar]：<> “局部变量：” [EmacsVar]：<> “模式：缩进文本” [EmacsVar]：<> “缩进制表符模式：nil” [EmacsVar]：<> “句子结尾双空格：t” [EmacsVar]：<> “填充列：70” [EmacsVar]：<> “编码：utf-8” [EmacsVar]：<> “结束：”