作者
Richard A. O'Keefe <ok(at)cs(dot)otago(dot)ac(dot)nz>
状态
最终/R15B 在 OTP R15B 版本中实现
类型
标准跟踪
内容类型
text/plain
创建时间
2011-05-27
Erlang 版本
OTP_R14B04

EEP 37:带名称的 Fun #

摘要 #

扩展了 fun 的语法,允许在每个参数列表之前始终存在一个变量名。这使得 fun 可以递归。这个“结”是在将 fun 应用于其参数的操作码中系上的,因此不需要更改垃圾收集器的设计。

规范 #

目前,fun 有三种形式

fun Name/Arity
fun Module:Name/Arity

fun Fun_Clause {; Fun_Clause}... end

我们添加另一种形式

fun Variable Fun_Clause {; Variable Fun_Clause}... end

如果任何 Fun_Clause 都有一个 Variable,则所有都必须有,并且它们必须是同一个变量。与参数列表中的变量一样,此变量是 fun 的局部变量,不与其上下文共享。在 fun 内部,该变量绑定到 fun 表达式的值。

有几种可能的实现方式。其中一种非常简洁,因为它保留了垃圾收集器必须处理的数据结构的无环性。

实现现有 fun 的一种方法是这样

  • a 创建一个具有生成名称的辅助函数

      <foo>(...,X1,...,Xk) ...;
      ...
      <foo>(...,X1,...,Xk) ....
    

    该函数具有与 fun 相同的参数列表、guards 和子句主体,只是与上下文共享的每个变量都作为额外的参数出现。

  • b 将 fun 表达式转换为

      '%mk-fun'({fun <foo>/n+k, X1, ..., Xk})
    

    这为元组提供了一个特殊的标签,表明它表示一个 fun 值。

  • cFoo(E1,...,Em) 转换为

    转换为 A1 := E1, ..., Am := Em; funcall_m(Foo),其中 funcall_m 指令检查其参数是否是一个期望 m 个参数的闭包,将元组的 X1,...,Xk 字段移动到参数寄存器 A<m+1>..A<m+k>,然后跳转到第一个字段中的地址。

实现递归 fun 所需的全部内容是

  • a’ 创建一个辅助函数

      <foo>(...,X1,...,Xk,Variable) ...;
      ...
      <foo>(...,X1,...,Xk,Variable) ....
    
  • b’ 将 fun 表达式转换为

      '%mk-rec-fun'({fun <foo>/<n+k+1>, X1, ..., Xk})
    

    这只是应用了第二个特殊标签。

  • c’ funcall_m 操作码对于旧的和

    递归 fun 的作用相同,只是在跳转之前,它将 fun 值 Foo 本身添加为参数 A<m+k+1>。 这就“系上了结”。

因此,创建一个递归 fun 不需要比现有 fun 花费更多的时间或空间,并且不涉及创建任何指针环。它的代码可以插入到 funcall_m 指令的失败路径中,无论其形式如何。

动机 #

Fun 名称可以服务于三个目的。

首先,它们可以只是文档。例如,

cfun_files(CFun) ->
    fun(F1, F2) ->
        [[?OBJ(T1,_) | _] | _] = F1,
        [[?OBJ(T2,_) | _] | _] = F2,
        CFun(T1, T2)
    end.

可以写成

cfun_files(CFun) ->
    fun Compare([[?OBJ(T1,_)|_]|_], [[?OBJ(T2,_)|_]|_]) ->
    CFun(T1, T2)
    end.

一个未使用的命名 fun 可以像没有名称一样实现。

其次,fun 的名称可以构建到其生成的名称中。在撰写本文时,我们可能有

'-F/N-fun-K-'

其中 F/N 是包含 fun 的函数的名称,而 KF/N 中较早的 fun 的数量。我们可以使用以下方法在名称中构建名称

'-F/N-fun-Name-[K-]'

其中仅当外部函数包含多个具有相同名称的 fun 时才存在 K。 这样做的目的是,这种名称在热加载后更有可能有用。例如,如果我们从

f(...Xs, Ys, ...) ->
    ...
    sort(Xs, fun X_Key({_,N,_}) -> N end),
    sort(Ys, fun Y_Key({N,_,_}) -> N end),
    ...

开始,然后我们修改它,交换对 sort/2 的两个调用。使用命名 fun,这两个 fun 保留其生成的名称,并且模块是安全的。使用匿名函数,这两个 fun 很可能会交换名称;糟糕!

第三,Erlang 邮件列表中经常被问到的一个问题是“为什么我不能有递归 fun?”对此,我们现在可以依赖地回答,“你可以;它们看起来像这样。”

这仍然不允许相互递归的 fun,但人们似乎并没有要求那么多。

最后,下次有人争论 Erlang 语法不一致,因为函数子句具有重复的名称而 fun 子句没有时,我们将能够回答“但是 fun 子句可以具有重复的名称,并且可能应该有。”

基本原理 #

似乎只有两个主要问题。

fun 名称变量的作用域应该是什么? fun 中的某些变量在 fun 及其上下文之间共享。这样做可以让我们编写

f(...) ->
    fun G(...) -> ... end,
    fun H(...) -> ... end,
    ... use G and H ...

有点像在 Scheme 中使用嵌套的“define”,只是虽然 H 可以使用 G,但 G 不能使用 H

由于你不能以这种方式获得相互递归,因此不应被误导地认为你可能会得到。最好你必须写

f(...) ->
    GG = fun G(...) -> ... end,
    HH = fun H(...) -> ... end,
    ... use GG and HH ...

以便你清楚地了解你正在获得什么。

虽然 fun 子句主体中的变量可以与上下文共享,但参数中的变量不是,我发现这令人困惑。至少这样,fun 名称遵循与紧挨着的参数列表中的变量相同的范围规则。

另一个主要问题是,递归 fun 值是否应与现有 fun 值完全相同,只是其中有一个环(在构造时系上结),还是引入一个新标签(在调用时系上结)。Erlang 堆中缺少环一直是多个垃圾收集器设计中的主要因素。我预计更改这一点要比此提案所需的更改难度大一个数量级。看到可以在调用时系上结(而不会减慢对现有 fun 的调用)使我敢于希望此提案有一天可能会被接受。

现在的主要问题是,这不允许我们定义一组相互递归的局部函数。现在采用此提案可能会阻碍一个更好地处理相互递归的提案。

我不认为这样的提案会很快出现。

这有一个特例,其中 fun 名称仅在尾调用位置使用,这可以通过编译器生成跳回到开头来完全处理。 这根本不需要对运行时系统产生任何影响。

向后兼容性 #

不使用新功能的代码不会改变其含义。可能存在依赖于生成函数名称形式的代码;这需要更改。

所有语法工具都需要修改以处理新形式。现有解析转换很可能会在新形式的代码上失败,但在不包含新形式的代码上会保持不变。

至少需要一条新指令来创建适当区分的闭包。在修改之前,分析 BEAM 文件的现有程序将不理解这一点。

如“动机”部分所述,即使你不在任何子句主体中使用该名称,命名函数也是有用的。这意味着我们可以分阶段交付该功能。

  1. 使解析器识别 fun 名称并检查其标识。如果 fun 名称在主体中使用,则报告错误。在任何下游工具看到它之前,将其从 AST 中删除 fun 名称。

    在此阶段,fun 名称可以用作文档。

  2. 升级下游工具以识别具有两个额外字段的扩展 'fun' AST 节点:fun 名称(作为原子)和一个标志,指示它是否未使用,仅在尾部位置使用,或者更广泛地使用。

    升级解析器以报告 fun 名称,但保留检查它们是否未使用的功能。测试下游工具。

  3. 修改编译器以使用新的、更安全的生成名称形式。确保仅通过接口访问生成的名称,因此所有内容都是一致的。

    在此阶段,fun 名称有助于减少代码修改带来的风险,这些修改会添加、删除或重新排序 fun;不改变函数中具有特定名称的 fun 数量的更改不应更改其名称。

  4. (可选。)修改代码生成器以接受尾部调用位置的 fun 名称并生成跳转。修改解析器以允许这样做。

    此时,可以像列表遍历或二分搜索一样传递循环作为参数。尚未对 Erlang 术语或 BEAM 引擎的表示形式进行任何更改。

  5. 添加一个新标签。如果现有检查失败,则修改 funcall 指令以检查它,并推送闭包本身。添加一条新指令以创建一个新闭包。修改 Erlang 术语表示以编码递归 fun。修改类型测试指令以识别新值。教 HiPE 如何操作。

    这是最后阶段。

参考实现 #

本草案中没有。阶段 1 可以很容易地完成。阶段 2 对我来说很难,因为我甚至不确定所有相关的模块是什么。

参考文献 #

无。

版权 #

本文档已置于公共领域。