作者
Richard A. O'Keefe <ok(at)cs(dot)otago(dot)ac(dot)nz>
狀態
草案
類型
標準追蹤
建立日期
2008年8月14日
Erlang 版本
OTP_R12B-4

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
  • 一個應傳回 true 或 false 的「守衛」 Other_Expression

其作用類似

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 來說幾乎可以接受,因為 zipping 系列最多支援 7 個列表,並且編譯器會努力透過使用 deforestation 來消除中間資料結構。對於 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 編譯器能夠證明 A 和 B 都是列表(這可能在 Dialyzer 的能力範圍內),並且它們的長度完全相同(據我所知,這並非如此),否則不允許將「zip 版本」替換為「Clean 版本」。

但是,多序列產生器和使用 lists:zip/2 呼叫的單序列產生器顯然相似,因此它們最終應以相同的方式對長度不同的列表做出反應。在 Haskell 中,將兩個長度不同的列表進行 zipping 的作用如同將較長的列表截斷為較短的列表的長度。由於 Haskell 具有惰性求值,因此列表可能是無限的,因此您無法等到最後才開始解析式。由於 Erlang 是嚴格的,並且由於錯誤很常見,因此 Erlang 中的 lists:zip/2 具有其存在意義。

回溯相容性 #

目前,「運算符」‘&&’ 在 Erlang 的任何地方都不是合法的語法,因此不會影響任何現有的程式碼。

參考實作 #

尚未有任何實作,但我想在弄清楚如何做的時候進行。

版權 #

本文檔已置於公共領域。[EmacsVar]: <> “Local Variables:” [EmacsVar]: <> “mode: indented-text” [EmacsVar]: <> “indent-tabs-mode: nil” [EmacsVar]: <> “sentence-end-double-space: t” [EmacsVar]: <> “fill-column: 70” [EmacsVar]: <> “coding: utf-8” [EmacsVar]: <> “End:”