作者
Richard A. O'Keefe <ok(at)cs(dot)otago(dot)ac(dot)nz>
狀態
草稿
類型
標準追蹤
建立日期
2013年2月4日
Erlang 版本
OTP_R16A

EEP 41:Erlang 的偽賦值 #

摘要 #

在 Erlang 中加入中綴符號「:=」,其語義與 R 中的「<-」相同,皆為純函數式更新。

範例 #

假設有以下宣告

-record(rect, {top,left,bottom,right}).
-record(whatever, {region, ...}).

centre(#rect{top=T,left=L,bottom=B,right=R}) ->
    {(L+R)/2, (T+B)/2}.

'centre:='(#rect{top=T,left=L,bottom=B,right=R}, {X,Y}) ->
    DX = X - (L+R)/2,
    DY = Y - (T+B)/2,
    #rect{top=T+DY,left=L+DX,bottom=B+DY,right=R+DX}.

偽賦值

centre(W#whatever.region) := P

會展開為

W' = W#whatever{
       region = 'centre:='(W#whatever.region, P)}

其中 W' 會自動取代後續所有提到 W 的地方。

規格 #

引入一個新的符號「:=」。它只能以以下形式使用

Lhs := Rhs

其中 Rhs 是任何 Erlang 表達式,稱為來源;而 Lhs 稱為目標,且為

  • 一個變數(而非萬用字元),
  • Lhs' #record.field,或
  • ~f(Lhs'),或
  • f(Lhs', E2, …, En),或
  • m:f(Lhs', E2, …, En)

其中 E2 … En 是任何 Erlang 表達式,Lhs' 是相同形式的另一個實例,f 是一個 atom,而模組前綴 m 只能是 atom 或變數。

「最終目標」

  • 變數的最終目標是該變數本身,
  • L#r.f 的最終目標是 L 的最終目標,
  • ~f(L) 的最終目標是 L 的最終目標,
  • f(L,…) 的最終目標是 L 的最終目標,
  • m:f(L,…) 的最終目標是 L 的最終目標。

任何偽賦值基本上都是對其最終目標進行(重新)綁定,其值為賦予該變數的值,而非來源右側的值。

偽賦值等同於一系列由逗號連接的簡單變數 = 表達式綁定,並且可以出現在任何允許此類綁定序列的表達式中,除非它出現在列表推導式內,在這種情況下,最終目標不得在該推導式之外被提及。

偽賦值的語義使用三個概念階段定義:保護、展開和重新命名。

保護 #

基本概念是

f(T, E2, ..., En) := S

是以下語法的糖衣

T := 'f:='(T, E2, ..., En, S)

這種形式的偽賦值來自 S (S R),儘管 Pop-2 (P) 早得多就採用了類似的方法,而 SETL (M) 中也發現了有些類似的「邪惡函數調用」(看起來是命令式的,但其值在語義上是不可變的)。

稍微複雜的地方在於,我們希望 T1、E2、…、En、S 的子表達式只被評估一次並且按照順序評估。這就像 Common Lisp (L) 的巨集處理廣義變數的方式一樣,「[評估]巨集調用的子形式 [...] 嚴格按照從左到右的順序評估一次」。讓我們從一個範例開始

f(g(T, E1), E2) := E3

=> V1 = E1,
   g(T, V1) := 'f:='(g(T, V1), E2, E3)

=> V1 = E1,
   T := 'g:='(T, V1, 'f:='(g(T, V1), E2, E3))

這樣 E1 就不會被評估兩次。

此步驟使用 Erlang 偽程式碼定義,其中 <[…]> 方括號是「準引用」,用於包圍抽象語法樹的原始語法表示。簡而言之,在 AST 上進行預序遍歷,為每個函數(但最上層的函數除外)的每個非第一個參數 Arg 添加 V=Arg 綁定,對於任何需要保護的 Arg 執行此操作。哪些參數不需要這種保護?那些評估不會產生任何可觀察效果的參數,我們可以大致認為變數和常數不需要保護,而其他所有參數都需要保護。

% protect(ast()) -> ast()

protect(<[ Lhs := Rhs ]>) ->
    {Lhs', Bindings} = protect(Lhs, 0, []),
    prepend_bindings(Bindings, <[ Lhs' := Rhs ]>).

% prepend_bindings([ast()], ast()) -> ast().

prepend_bindings([Binding|Bindings], E) ->
    E' = prepend_bindings(Bindings, E),
    <[ Binding, E' ]>;
prepend_bindings([], E) ->
    E.

% protect(Expr::ast(), Depth::int(), [ast()]) ->
%     {ast(), [ast()].

protect(<[ Var ]>, _, B) ->
    {<[ Var ]>, B};
protect(<[ ~F(T) ]>, D, B) ->
    {T', B'} = protect(T, D+1, B),
    {<[ ~F(T') ]>, B'};
protect(<[ T#R.F ]>, D, B) ->
    {T', B'} = protect(T, D+1, B),
    {<[ T'@R.F ]>, B'};
protect(<[ F(T,E2,...,En) ]>, D = 0, B) ->
    {T', B'} = protect(T, D+1, B),
    {<[ F(T',E2,...,En) ]>, B');
protect(<[ F(T,E2,...,En) ]>, D, B) when D > 0 ->
    {[E2',...,En'], B'} = protect_args([E2,...,En], B),
    {T', B''} = protect(T, D+1, B),
    {F(T',E2',...,En'), B''};
protect(<[ M:F(T,E2,...,En) ]>, D = 0, B) ->
    {T', B'} = protect(T, D+1, B),
    {<[ M:F(T',E2,...,En) ]>, B'');
protect(<[ M:F(T,E2,...,En) ]>, D, B) when D > 0 ->
    {[E2',...,En'], B'} = protect_args([E2,...,En], B),
    {T', B''} = protect(T, D+1, B),
    {M:F(T',E2',...,En'), B''};

% protect_args([ast()], [ast()]) -> {[ast()], [ast()]}.

protect_args([], B) ->
    {[], B};
protect_args([<[ Var ]>|Args], B) ->
    {Args', B'} = protect_args(Args, B),
    {[< Var ]>|Args'], B'};
protect_args([<[ Const ]>|Args], B) ->
    {Args', B'} = protect_args(Args, B),
    {[< Const ]>|Args'], B'};
protect_args([<[ E ]>|Args], B) ->
    V = a new variable,
    {Args', B'} = protect_args(Args, [<[ V = E ]>|B]),
    {[<[ V ]>|Args'], B'}.

展開 #

展開會遞迴地重寫偽賦值,直到目標變成簡單變數為止。

L#r.f := E
=>  L := L#r{f = E}

~f(L) := E
=>  L := <{f ~ E | L}>

f(L, E2, ..., En) := E
=> L := 'f:='(L, E2, ..., En, E)

m:f(L, E2, ..., En) := E
=> L := m:'f:='(L, L2, ..., En, E)

賦值函數並非一種特殊的函數,而是一種具有特殊名稱形式的普通函數。可以使用現有的 Erlang 手段匯出、導入、遠端調用、傳遞到 fun 中或作為 fun 傳遞。

特別是,f/n 和 ‘f:=/(n+1) 之間沒有自動關聯。匯入或匯出其中一個並不會自動匯入或匯出另一個。

重新命名 #

在展開和重新命名後,偽賦值的數量與之前完全相同,但現在每個偽賦值的目標都是一個簡單的變數。

這由重新命名處理。不要將變數視為由名稱識別,而是將其視為由「名稱,版本」對識別。所以賦值

V := E

應被認為是(並且實際上被轉換為)

«V,n+1» = E

其中 n 是在執行路徑上出現的 V 的最高版本,直到此重新綁定。如果沒有此類版本,則 n = 0。因此

X := f(...),
X := g(..X..),
X := h(..X..),

變成

«X,1» = f(...),
«X,2» = g(..«X,1»..),
«X,3» = h(..«X,2»..),

序列很容易。困難之處在於會分裂和重新結合的控制路徑,例如 ‘if’ 或 ‘case’。

如果 E 是一個分裂-結合的控制路徑,而 X 是一個出現在 E 中並且在 E 之後仍然存在的變數,並且 X 在 E 的每個分支中的最後出現版本並不完全相同,那麼令 «X,m» 為 X 在 E 中的最高版本。在 E 的每個建立 X 版本的分支中,將 X 的最高版本替換為 «X,m»。如果分支沒有建立 X 的版本,且 X 在進入 E 時並非活躍的,則這已經是 Erlang 中的錯誤,我們不會對其進行更改。如果 «X,p» 是進入 E 時 X 的活躍版本,則新增

«X,m» = «X,p»

在每個未更新 X 的分支的 -> 箭頭之後。這是一個範例。

W = 137,
if X < Y  -> Z = X-1, Z := Z*(Y+1)
 ; X >= Y -> Z = 42, W := 3145
end,
f(Z, W)

變成

«W,1» = 137,
if «X,1» < «Y,1» ->
      «W,2» = «W,1»,   % patch
      «Z,1» = «X,1» - 1,
      «Z,2» = «Z,1»*(«Y,1»+1)
 ; «X,1» >= «Y,1» ->
      «Z,2» = 42,     % patch
      «W,2» = 3145
end,
f(«Z,2», «W,2»)

新增第一個修補行是因為該分支沒有更新 W,並且將其新增在該位置,以便不干擾該分支其餘部分的結果。第二個修補行本應綁定 «Z,1»,只是該版本被提升至與另一個分支匹配。

實際上,我們正在使用靜態單賦值形式,而修補程式正在將 phi 函數推回分支中。

編譯器的語義分析器和程式碼產生器永遠不會知道偽賦值。沒有理由為變數的不同版本分配相同的虛擬暫存器或記憶體單元;是否分配取決於暫存器分配器,如果這樣做有用,則分配,如果這樣做更有用,則不分配。

動機 #

有幾個人在 Erlang 郵件列表中抱怨說,必須寫

X  = f(...),
X1 = g(..X..),
X2 = h(..X1...)

既容易出錯又很乏味,因為如果他們必須重新排序轉換順序、新增轉換或刪除轉換,他們就必須重新命名變數。

使用重新命名在純宣告式語言中對整個變數進行「賦值」建模的事實早已為人所知。我在撰寫「The Craft of Prolog」時就已經知道,而且當時已經是眾所周知的。問題不是我們是否可以支援

X := f(...),
X := g(..X..),
X := h(..X..),

而是我們應該支援嗎?

Loïc Hoguin 強烈主張「[他]只是想要s能夠輕鬆更新深層資料結構的原語」(2013 年 1 月 26 日),並表示 Erlang 對記錄的處理方式不足,因為它使這變得困難。他寫道(2013 年 1 月 25 日)

假設有一個變數 Character。此變數包含關於角色的所有資訊。您如何最好地存取和修改 Character?答案不得涉及程序字典、程序或訊息傳遞。今天,我必須編寫每個存取和修改函數。或者我可以生成它,但無論哪種方式,我最終都會在許多模組中擁有數百個函數。或者我可以使用記錄,並且為我編寫的每個修改函數的每個子記錄使用一行。這既不容易也不實際。容易且實際的做法是

Character.weapon.ability.cost

用於存取,以及

Character.weapon.ability.cost = 123

用於修改。

我並不是要給他那個,但是

C = cost(ability(Character#cinfo.weapon)),
cost(ability(Character#cinfo.weapon)) := C + 123

他可以擁有,其中所有函數都可能被內聯,或

C = ~cost ~ability ~weapon Character,
~cost ~ability ~weapon Character := C + 123

在我們擁有 frame 的美好未來中。

從我的角度來看,好處在於,無需引入可變資料結構即可擁有這種簡潔的語法。這是賦值。而且這是一種經過驗證且使用了 25 年以上的技術。

對於頑固的賦值愛好者來說,不利的一面在於,以這種方式更新深層路徑需要在過程中分配修改後的記錄副本,但是如果我們不改變 Erlang 的基本屬性,我們就無法更改這一點。

原理 #

問題是:應該提供哪種「賦值」,應該使用什麼語法進行賦值,以及應該允許哪些目標。

如果不新增允許 Haskell 式單子或 Clean/Mercury 式唯一性追蹤的類型系統,則有兩種方法可以將賦值新增到 Erlang 中:Lisp 方式和 S 方式。Lisp 方式是在其所有破壞性力量中提供真實的東西。這將具有巨大的好處,使 C/Java/JavaScript 程式設計師在使用 Erlang 時會感到更舒適,並且我們可以期待 Erlang 語法最終被改革為具有執行緒的 JavaScript 的那一天。這也將付出巨大的代價,需要對 Erlang 編譯器和執行階段系統進行重大更改,並使 Erlang 程式設計師所珍視的主要保證之一(「您的資料在我們這裡很安全」)失效。這會使 Erlang 程式更難以正確編寫。坦白說,如果我們想要具有執行緒的 JavaScript,我們最好將執行緒新增到 JavaScript 中。

另一種方法是 S 方式。S 是 John Chambers 在 AT&T 發明的一種程式語言,用於程式設計統計演算法。修訂後的語言定義於 1988 年發佈。S 的語法看起來像稍微錯亂的 C,但是語義卻令人驚訝地具有函數性。特別是,至少在 S3 之前,S 值並未檢測到共享可變的部分。類似於以下的 S 賦值

a[i,j] <- 0

等同於

"["(a, i, j) <- 0

這又等同於

a <- "[<-"(a, i, j, value = 0)

這不單單是一種說話的習慣,實際上確實有一個名為「[<-]」的函數,這個函數就是如此調用的。S 語言憑藉其類似 C 的語法、不可變的資料結構以及惰性求值的函數參數,絕對是相當奇特的。但它卻非常實用。R 儲存庫中擁有大量執行驚人且有用操作的套件;它被世界各地的統計學課程所採用;並且有大量的優秀書籍在教導和使用 S/R。因此,儘管「賦值」的概念,是指計算一個新的完整值並將其重新繫結到一個值上的語法糖,這可能看起來不太熟悉,但它已被證明既是可行實用的。

由於存在一種經過實戰考驗的「賦值」形式,它不需要可變的資料結構,這顯然是 Erlang 應該採用的方式。

至於語法,我很熟悉以下這些:

  • Lhs = Rhs (Fortran, COBOL, BASIC, C)
  • Lhs := Rhs (Algol, Pascal, Modula, Ada, ANSI Smalltalk)
  • Lhs 左箭頭 Rhs (APL, 古典 Smalltalk)
  • Lhs <- Rhs (S)
  • Rhs -> Lhs (S, Pop-2)
  • (set! Lhs Rhs) (Scheme)
  • (setf Lhs Rhs) (Lisp)

在這些語法中,Erlang 已經將 =, <- 和 -> 用於其他目的,而 Unicode 左箭頭仍然難以輸入。Erlang 語法不是 Lisp 語法,雖然 LFE 擁有 Lisp 風格的巨集,但普通的 Erlang 並沒有。這使得 := 成為唯一可靠的候選者。

至於虛擬賦值的目標,我們可以簡單地允許 Erlang 變數。在 Erlang 郵件列表中,經常有人要求使用重新命名風格的賦值。重要的是要理解,這種重新命名方式的變數「賦值」不需要重寫記憶體單元:變數的不同「版本」可能佔用不同的單元,而且是否佔用不同單元取決於暫存器分配器。

我們也看到 Erlang 因無法清楚表達鏈式紀錄更新而受到批評。人們寧願寫成:

X1 = X#r{f = X#r.f#s{g = X#r.f#s.g#t{h = 42}}}

而不是

X#r.f#s.g#t.h := 42

誰能責怪他們呢?(好吧,可以。我認為無論語法如何,他們都不應該這樣寫程式碼,而且我在自己的 C 程式碼中發現,清除指標鏈揭露了許多現在和潛在的錯誤。問題的根本性質是過度耦合。)因此,我們希望允許欄位參考作為目標。

~f(L) 語法來自框架提案。如果紀錄欄位可以進行虛擬賦值,那麼框架槽也應該可以。

如果我們想要對雜湊表或類似陣列結構的元素進行虛擬賦值,我們必須允許函數呼叫。S 的範例表明,我們可以在賦值左側包含函數呼叫,這表示我們可以執行:

at(Dict, Key) ->
    case dict:find(Dict, Key)
      of {ok,V} -> V
       ; error  -> 0
    end.

'at:='(Dict, Key, Value) ->
    dict:store(Key, Value, Dict).

...

    at(D, K) := at(D, K) + 1
...
'element:='(N, Tuple, V) ->
    setelement(N, Tuple, V).
...
   A := {0,0,0},
   element(1, A) := 3,
   element(2, A) := 1,
   element(3, A) := 4

某些語言允許您對子字串進行賦值。如果我們可以使用虛擬賦值來呼叫函數,那麼我們就不需要額外的機制來處理它

'substr:='(String, Start, New) ->
    string:substr(String, 1, Start - 1) ++ New.

'substr:='(String, Start, Length, New) ->
    string:substr(String, 1, Start - 1) ++ New ++
    string:substr(String, Start + Length - 1).

下一步的通用化將是遵循 Algol 68 並允許

if G1 -> B1, L1
 ; ...
 ; Gn -> Bn, Ln
end := E

表示

if G1 -> B1, L1 := E
 ; ...
 ; Gn -> Bn, Ln := E
end

並對 'case' 等等進行類似的定義。我看不出有任何直接的方法可以在不複製 E 或不按順序進行計算的情況下實現它,所以在這個點之前停止似乎是個好主意。

上面的「擴充」步驟表示匯入或匯出 f/n 並不會自動匯入或匯出 'f:='/(n+1)。這可能是造成不重要但惱人錯誤的來源。我預期使用賦值函數會比定義它們更為常見,而且您可以呼叫遠端函數而無需明確匯入它,因此寫入

string:substr(Line, Comment_Start) := ""

不需要任何特殊的宣告。那麼,可能發生的錯誤是在模組中定義 f/n 和 'f:='/(n+1),然後匯出第一個而不匯出第二個。如果這真的成為一個問題,那麼很容易新增一條規則,即如果匯出了 f/n 並且定義了 'f:='/(n+1),則賦值形式也會被匯出。讓我們看看是否真的需要它。

是否應該允許在變數的初始繫結中使用虛擬賦值語法?似乎沒有任何令人信服的理由禁止它。

有一個令人信服的理由禁止在列表推導式內部進行虛擬賦值,然後在外部使用這些變數。列表推導式可以像目前這樣編譯為內聯程式碼,而不是產生獨立的遞迴函數。而透過實際的、名副其實的、直接修改記憶體單元的變數賦值,可以用來實現此類賦值。形式語義仍然可以使用重新命名。但是程式碼產生器必須知道這一點。重新命名語義可以使用獨立方法來實現,但是此類變數的目前值必須傳入和傳回,這會產生讓我,更不用說其他程式設計師,感到驚訝的負擔。禁止它要簡單得多。這與匿名函數中變數的作用域規則有些相似,處理起來相當複雜。

向後相容性 #

目前,Erlang 原始碼中的任何地方都不允許使用符號「:=」和符號序列「:」「=」,因此不會直接影響任何現有程式碼。

虛擬賦值被定義為原始碼到原始碼的轉換。此轉換僅限於受影響的函數子句,並且可以完全在剖析器中完成。

這表示 Erlang 工具鏈中剖析器下游的任何東西都不會受到此變更的影響。尤其是,分析、監控和除錯工具只會看到普通的舊 Erlang。

參考實作 #

本草案中沒有,但提供了實作提示。

著作權 #

本文件已置於公共領域。