作者
Björn Gustavsson <bjorn(at)erlang(dot)org>
状态
已接受/R13A 已在 OTP R13A 版本中实现
类型
标准跟踪
创建于
2009年1月28日
Erlang 版本
OTP_R12B-5

EEP 26:使 andalso 和 orelse 尾递归 #

摘要 #

Erlang 5.1 添加了在 guards 中使用 ‘andalso’、‘orelse’、‘and’ 和 ‘or’ 的能力。然而,‘andalso’ 和 ‘orelse’ 的语义与其他相关语言不同,导致混淆和效率低下。

我建议使 ‘andalso’ 和 ‘orelse’ 成为尾递归。

此 EEP 部分基于 Richard O’Keefe 的 EEP 17,但范围更窄。

规范 #

目前,(E1 andalso E2) 作为表达式的行为类似于

case E1 of
    false -> false;
    true  -> case E2 of
                 false -> false;
                 true  -> true
             end
end

除了前者引发 {badarg,NonBool} 异常,后者引发 {case_clause,NonBool} 异常。

应该将其更改为

case E1 of
    false -> false;
    true  -> E2
end.

目前,(E1 orelse E2) 作为表达式的行为类似于

case E1 of
    true -> true
    false -> case E2 of
        true  -> true
        false -> false
    end
end

除了前者引发 {badarg,NonBool} 异常,后者引发 {case_clause,NonBool} 异常。

应该将其更改为

case E1 of
    true  -> true;
    false -> E2
end

动机 #

为了解锁 Erlang 中 ‘andalso’/‘orelse’ 的全部潜力。

鉴于当前的实现,您要么必须使用 ‘case’ 重写自然使用 AND 和 OR 运算符编写的代码,要么仅在您知道列表相对较短时才使用 ‘andalso’/‘orelse’。

例如,如果列表的所有元素都满足谓词,则返回 ‘true’,否则返回 ‘false’ 的函数 all/2 可以这样编写

all(Pred, [Hd|Tail]) ->
    Pred(Hd) and all(Pred, Tail);
all(_, []) ->
    true.

在每次递归中,我们测试当前元素 Hd 是否满足谓词,并且列表的其余部分也匹配该谓词。这段代码读起来几乎就像英语一样。

当然,‘and’ 会评估其两个操作数,因此即使列表的第一个元素未能满足谓词,也会遍历整个列表。此外,‘and’ 不是尾递归的,因此该函数将使用与列表长度成正比的堆栈空间。

为了避免在某个元素未能满足谓词时遍历列表的其余部分,我们可以使用 ‘andalso’

all(Pred, [Hd|Tail]) ->
    Pred(Hd) andalso all(Pred, Tail);
all(_, []) ->
    true.

一旦 Pred(Hd) 返回 false,递归将停止,并且无需遍历列表的其余部分。但是,由于 ‘andalso’ 不是尾递归的,因此该函数将需要与遍历的列表元素数量成正比的堆栈空间。

为了更清楚地了解 ‘andalso’ 不是尾递归的,这里是带有 ‘andalso’ 展开为嵌套 ‘case’ 表达式的 all/1(在 R12B-5 中会是这样)

all(Pred, [Hd|Tail]) ->
    case Pred(Hd) of
        false -> false;
        true  -> case all(Pred, Tail) of
        false -> false;
        true  -> true
        end
    end;
all(_, []) ->
    true.

为了使 all/1 在 R12B-5 中成为尾递归,您必须自己编写 ‘case’ 表达式

all(Pred, [Hd|Tail]) ->
    case Pred(Hd) of
        false -> false;
        true  -> all(Pred, Tail)
    end;
all(_, []) ->
    true.

如果此 EEP 被接受,在 R13B 中我们可以这样编写

all(Pred, [Hd|Tail]) ->
    Pred(Hd) andalso all(Pred, Tail);
all(_, []) ->
    true.

并且 all/1 函数将是尾递归的。

在我看来,后者更容易阅读和编写。 ‘case’ 表达式主要是样板代码,其中 ‘true’ 和 ‘false’ 必须正确拼写几次。(像 ‘ture’ 和 ‘flase’ 这样的拼写错误很常见,但在大多数情况下,会在第一次测试程序时发现。)

可以认为,由于 Erlang 具有明确定义的真值(不像其他一些语言,其中 0 为假,其他任何值都为真),因此所有对布尔值进行操作的运算符都应确保其参数为布尔值。

测试 ‘and’ 和 ‘or’ 的两个参数是有道理的,因为为这些运算符执行的代码始终会获取两个操作数的值。但是,‘andalso’ 和 ‘orelse’ 仅在某些时候测试它们的第二个操作数。

X = 1, X >= 0 andalso X    % checked error
X = 1, X < 0 andalso X     % unchecked error

似乎没有必要在某些时候进行检查,尤其是在它执行诸如阻止尾递归之类的戏剧性操作时。

Richard O’Keefe 在 EEP 17 中的动机是与其它语言的“文化一致性”。请参阅 EEP 17

理由 #

(令我)惊讶的是,此 EEP 的主题被证明是有争议的。

我将通过列出一些反对该提案的更严肃的论点以及我的反驳论点来开始此理由,并以支持该提案的论点结束。

反对的理由之一是,新的结构会使使用者感到困惑。 ‘andalso’/’orelse’ 不能再被描述为“布尔运算符”,而是“控制结构”。

是的,‘andalso’/‘orelse’ 不再是布尔运算符,因为它不再保证返回布尔值。但是,将 ‘andalso’/‘orelse’ 用作 ‘case’ 表达式

case E1 orelse E2 of
    true -> ....;
    false -> ...
end

以与以前相同的方式工作。大多数用户肯定不会注意到任何差异。如果一个运算符不允许不评估其两个参数,那么它之前也肯定不是运算符。

另一个反对的论点是,可以使用 ‘andalso’/‘orelse’ 在一行中编写“丑陋的代码”,例如

Debug andalso io:format("...", [...])

而不是

if
    Debug -> io:format("...", [...]);
    true -> ok
end

这段代码可能“丑陋”(根据某人的品味或对“丑陋”的某种定义),但是一行的代码不难理解,而且我不认为它会变成代码维护问题。

使 ‘andalso’/‘orelse’ 尾递归的主要论据是:当前的实现是危险的。您很容易编写非尾递归代码,例如

all(Pred, [Hd|Tail]) ->
    Pred(Hd) andalso all(Pred, Tail);
all(_, []) ->
    true.

而没有意识到它并引入严重的性能问题。(这种情况在 实践中 已经发生)。

如果您不能以这种方式使用 ‘andalso’/‘orelse’,则这些运算符将变得非常无用。(有些人会说 “完全无用”。)您必须将优美的代码(在我看来)重写为更丑陋的代码(相比之下,在我看来)和更容易出错的代码(样板代码中 ‘true’/‘false’ 的拼写错误)

all(Pred, [Hd|Tail]) ->
    case Pred(Hd) of
        false -> false;
        true  -> all(Pred, Tail)
    end;
all(_, []) ->
   true.

向后兼容性 #

任何在没有引发异常的情况下运行的代码都将继续产生相同的结果,除了运行速度更快。

确实引发异常的代码可能会在以后在其他地方引发不同的异常,或者可能会以意想不到的方式静默完成。我认为任何人都故意依赖 (E1 andalso 0) 引发异常的可能性不大。

以前由于这些运算符具有如此令人惊讶的行为而无法正常工作的代码现在将在更多情况下工作。

参考实现 #

拟议的更改已在我们的日常构建中实现和运行,而没有发现任何需要在 Erlang/OTP 中更新的代码。编译器测试套件中需要更新一个测试 ‘andalso’/‘orelse’ 的测试用例。

版权 #

本文档已置于公共领域。