作者
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 是一个原子,模块前缀 m 只能是原子或变量。

“最终目标”是

  • 变量是该变量本身,
  • 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) 之间没有自动连接。导入或导出其中一个不会自动导入或导出另一个。

重命名 #

在展开和重命名之后,伪赋值的数量与之前完全相同,但现在每个伪赋值都以一个简单的变量作为其整个目标。

这通过重命名来处理。不要将变量视为由名称标识,而是将其视为由 «name,version» 对标识。所以赋值

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 的最后出现不都具有相同的版本,则令 «X,m» 为 E 中 X 的最高版本。在 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...)

既容易出错又很乏味,因为如果他们必须重新排列转换顺序、添加转换或删除转换,他们就必须重命名变量。

使用重命名在纯声明式语言中对整个变量进行“赋值”建模的事实早已为人所知。我在编写“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

在我们拥有框架的美好未来中。

从我的角度来看,好处是这种简短的语法可以在不引入可变数据结构的情况下实现。这是赋值。而且这是一种经过验证的技术,已经使用了 25 年以上。

对于顽固的赋值爱好者来说,坏处是,以这种方式更新深层路径需要沿途分配记录的修改副本,但如果不改变 Erlang 的基本属性,我们就无法改变这一点。

基本原理 #

问题是:应该提供哪种“赋值”,应该使用什么语法进行赋值,以及应该允许哪些目标。

在不添加允许 Haskell 式单子或 Clean/Mercury 式唯一性跟踪的类型系统的情况下,有两种方法可以将赋值添加到 Erlang:Lisp 的方法和 S 的方法。Lisp 的方法是提供具有所有破坏性能力的真实事物。这将使 Erlang 对于 C/Java/JavaScript 程序员来说更舒适,并且我们可以期待 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)

这不仅仅是一种说话方式,确实有一个名为 “[<-“ 的函数,它真的会被调用。凭借其类似于 C 的语法、不可变的数据结构和延迟计算的函数参数,S 语言绝对很奇怪。但它非常实用。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)` 语法来源于 frames 提案。如果记录字段是伪赋值的,那么框架槽也应该是伪赋值的。

如果我们想要伪赋值给哈希表或类数组结构的元素,我们必须允许函数调用。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 代码。

参考实现 #

本草案中没有,但给出了实现提示。

版权 #

本文档已置于公共领域。