为嵌套循环添加命名循环和recur-to功能

Question

从提议电子邮件复制到Clojure/dev Google群体

  https://groups.google.com/d/msg/clojure-dev/zlMGmv60MVA/beyIRTrhAgAJ

你好，

目前loop/recur仅限于“单层”循环：循环形式可以出现在其他循环形式内，但没有任何“回溯到外部循环”的设施。

几年前，我发表了一项关于将嵌套循环添加到Clojure的提案，并提供了一个ClojureScript的概念验证补丁，其语法和语义足以使嵌套循环感觉自然，同时仍然是核心loop/recur模型的自然扩展，具有相同的显式尾递归优势。


(loop foo [...]    ; 命名循环
  ...
  (loop [...]                            陌生人循环
    ...
    (loop [...]                            最内层循环
      ...
      (recur-to foo ...)))) ; 回溯到命名循环;
                                        NB. 这必须在尾部位置
                               与三个循环相关


  https://groups.google.com/d/msg/clojure-dev/imtbY1uqpIc/8DWLw8Ymf4IJ
  https://dev.clojure.org/display/design/Named+loops+with+recur-to
  https://github.com/michalmarczyk/clojurescript/tree/recur-to
  https://github.com/michalmarczyk/clojurescript/commit/feba0a078138da08d584a67e671415fc403fa093

我现在已在Clojure中实现了一个完整的补丁，使得提议的功能得以实现（第一个链接是基于当前master的分支，即1.9.0-alpha17之后的“为下一次开发迭代做准备”提交；第二个是此分支的当前尖端，供将来参考）

  https://github.com/michalmarczyk/clojure/tree/recur-to

  https://github.com/michalmarczyk/clojure/commit/212ea06d21d3b336ac35480c99170e81defaf956

我还在JIRA中创建了一个票据，以便将上述内容以补丁文件的形式发布

  https://dev.clojure.org/jira/browse/CLJ-2235

此电子邮件的其余部分更详细地介绍了提议，以一种相对严格的形式陈述了其关键属性，简要总结了实现方法，并讨论了补丁中做出的某些设计选择。

概述
========

例如，人们可以编写：


(let [m (two-dimensional-matrix)]
  (loop iloop [i 0]                                           命名循环
    (if (< i i-lim)
      (loop [j 0]                            嵌套匿名循环
        (if (< j j-lim)
          (do
            (work)
            (recur (inc j)))  ; 递归到最内层循环
          (recur-to iloop (inc i)))) ; 递归到 iloop
      (done))))


并且，在递归形态相对于所有其包含的循环形态直到包含目标（可能是命名循环或fn形态）都是尾形态，并且传递给每个递归形态的目标参数的数量与目标循环的循环局部变量数量匹配（加上一个作为先导循环名称参数），则这应该能够编译并且具有与Java中嵌套循环类似的性能。

提出的语法是模仿了Scheme的命名let，虽然在语义上
这二者有所不同——这一提议严格限于以自然的方式扩展循环/递归模型到嵌套循环。当然，命名fn形态也应该作为有效的recur-to目标。

命名循环和recur-to的关键特性
==========================================

在上述补丁放置到位后，以下规则在编译时生效

1. 每个recur-to形态必须相对于所有其包含的循环形态（无论是否有名）处于尾形态，直到包括其目标（可能是一个命名循环或fn形态）。

2. 如果recur-to的目标不出现在其位于尾形态的包含循环或fn形态的名字中，则这是一个错误。

3. 不能通过try来递归。

4. 传递给recur-to的参数数量（超出初始目标/标签参数外）必须与目标循环或fn形态的形式参数数量相匹配。

5. 允许循环名称的遮蔽；recur-to只能针对与其尾形态存在的给定名称的最内层循环。被遮蔽的命名的循环引入的循环局部变量在遮蔽循环内仍然可见（除非它们被相同名称的局部变量遮蔽）。

注意。循环名称不是局部变量。特别是，它们既不被局部变量遮蔽，也不是被同名局部变量遮蔽。这一点值得详细讨论；请参阅本电子邮件末尾的设计选择部分。

最内层循环或fn形态始终可以使用 recur 进行定位，无论其是否有名。此外（recur-to nil ...) 与 (recur ...) 等价（即使在最内层循环或fn形态实际上是命名的情况下），并且 (loop nil [...] ...) 与 (loop [...]) 等价。

实现方法的概述
======================================

该补丁修改了编译器中循环标签的处理，并实现了对循环宏的少数必要的调整。

它还引入了循环*特殊形式的可选名称参数。（这主要是为了避免破坏直接发射loop*的非核心宏。）

最后，将 recur 特殊形式重命名为 recur*；recur 和 recur-to 成为定义在 clojure.core 中的宏。请参阅下文设计选择部分以了解其他方法。

设计选择
==============

1. 在开发过程中，纯粹是为了方便，那时我有一个单独的 loop-as 宏，它接受一个名称参数。我认为将命名功能直接添加到 loop 中是合理的，特别是考虑到 fn 已经接受一个可选的名称。不过，loop-as仍然是一个有效的设计选择。

2. 如果避免重命名现有的 recur 特殊形式为 recur* 并重新实现 recur 作为宏是一个愿望，可以添加一个新的 recur-to 特殊形式。（或者，可以在保留 recur 的同时添加 recur-to 作为将 recur* 特殊形式委托给新 recur* 特殊形式的宏。）

3. 如果未来希望保留将循环名称视为局部变量的选项，那么现在将其视为隐藏并在局部变量上被隐藏可能是更可取的，因为否则在后来将它们提升为局部变量的状态将会造成破坏性变更。为了举例说明这种未来的更改可能有用，如果尾调用消除支持在未来 JDK 规范中到来，人们可能会考虑是否采用类似于 Scheme 的方法，其中循环名称被视为绑定到只有一个 arglist（对应于命名循环的循环局部变量）的函数的局部变量；如果局部变量从未被引用，这种闭包分配可能会被优化掉。

需要注意的是，如果尾调用消除支持真的实现了，它将使一系列替代设计成为可能。例如，可以引入 Scheme 风格的命名 let 作为 let 宏的功能之一。因此，在我看来，将 loop/recur/recur-to 限制为仅用于 label+goto 风格的循环是有道理的，即使在假设的未来的 VM 尾调用消除支持中，也没有理由给予循环名称类似局部的待遇；因此，补丁当前采用不进行隐藏交云的方法。

祝好，
Michał

Answer 1

评论者：alexmiller

感谢 Michal，你在这里做了很多好工作。我认为你可能已经错过了查看 1.9 新特性的时间窗口，但在下一个版本上我会回顾这个问题。

将 recur 从特殊形式改为宏似乎不太可取，因此可能最好是扩展现有的形式或者添加 recur-to 特殊形式。

你是否考虑了用关键字指定名称的其他选项？关键字不带有与局部变量相同的词法隐藏预期，也许可以绕过这些问题？也许它们由于其他原因而不可取。

Answer 2

评论者：michalmarczyk

祝好，很高兴听到这一点。

_*recur-to 作为独立特殊形式*_

关于改变 recur 这一点是公平的。这里是一个将 recur-to 作为新的、独立特殊形式的补丁版本。请注意，它仍然与编译器中的 RecurExpr 类共享，正如 loop 和 let 所做的那样。此补丁旨在叠加在先前的基础上，以便清楚地显示差异。

    0002-CLJ-2235-implement-recur-recur-to-as-separate-specia.patch

    https://github.com/michalmarczyk/clojure/tree/recur-to

我还准备了一个压缩版本，它将 current master 直接带到相同的状况。

    0001-CLJ-2235-implement-named-loop-recur-to-separate-special-form.patch

    https://github.com/michalmarczyk/clojure/tree/recur-to-separate-special-form

顺便说一下，在实施这个补丁时，我不得不撤销原始补丁对clojure.pprint的改动。我认为这表明，采用一个全新的、独立的 recur-to 是更好的主意——我在准备原始帖子时忽略了这个，否则可能就会影响我的判断。（改动通过 #_ 注释标记，我在原始补丁中忘记删除了。新合并的补丁通过不修改该文件来自动清理它。）

**作为循环名称的符号与关键词**

我部分使用符号，因为 fn 期待可选名称参数为符号（如果提供的话），因此 recur-to 无论如何都需要支持符号名称（假设这里我们想要 recur-to 使用与引入它时相同的 recur 目标名称的形式，这似乎是合理的）；部分是“默认情况下”，因为静态符号引用通常使用符号。（clojure.core/extend 使用关键词，但这些并不是真正的静态引用。）不确定将元数据附加到循环名称上是否可能是有用的，但这也是其中一个原因。

关于现有使用的第二部分可能是一个主要考虑因素，尤其是在循环名称在某种意义上是独特的，它们只能通过单个特殊形式（recur-to）来引用，并且在源代码中否则是无形的。这也将它们与 fn 引入的命名 recur 目标区分开来，这些目标当然也充当局部变量。

所以，如果我们愿意使用没有元数据的循环名称，那么我们可以使用关键词作为循环名称，而用符号作为 fn 名称。我们甚至可以允许 fn 形式使用关键词名称，如果意图是建立没有提供 fn 实例局部引用的命名 recur 目标。（这基本上是 fn + loop 的语法糖。）

我必须再思考一下哪种方法更受我青睐。我仍然喜欢将符号用于 recur 目标（fn / loop / recur-to）的一致性，但使局部/非局部差异伴随语法上的区分也很有吸引力。

在公开脑力激荡的过程中，我发现使用关键词作为循环名称现在会保留未来添加对符号支持的开放可能性——也许是为提供对封闭对象局部引用的 VM-TCE 基于方案的循环名称。或者我们可以一旦 TCE 到来，将“符号标签”作为“let-like”形式（由 LetExpr 支持，即 let & loop）的通用功能。然后我们将考虑 recur-to 是否可以针对这样的命名 let…还有关于普通的 let 怎么办？可能最好坚持 loop/recur/recur-to 中的标签+goto 循环和通过单独设施（可能简单为 let）支持的类似方案，而 fn 则是这两个模型的交集（它本来就是，因为它即使在未命名的情况下也会引入 recur 目标）。

最后一点，我认为提出使用关键词替代某个类似情况的一个例子是简写字段访问语法——据我所知，(.) x :foo) / (.:foo x) 被提出作为一个可能的语法，这在最终成为 (. x -foo) / (.-foo x) 的语法。尽管这是一条未走过的路，我认为它说明了如何合理解释关键词/符号实际访问两个命名空间。（嗯，在长版本中；.:foo 技术上是符号。通过关键词使用循环名称将不会对任何类别的“关键词衍生”符号提供特殊待遇。）

无论如何，我会考虑准备一个使用关键词作为循环名称的补丁版本。

Answer 3

评论者：michalmarczyk

这是一个关于“循环名称关键词”的补丁的初稿

0002-CLJ-2235-use-keywords-as-loop-names.patch

此补丁应用于已压缩的“分离特殊形式”补丁之上

0001-CLJ-2235-implement-named-loop-recur-to-separate-special-form.patch

同时附上压缩补丁以便使用

0001-CLJ-2235-recur-to-keyword-loop-names.patch

这是新方案的示例

`
(let [m [[[1 2 3] [4 5 6] [7 8 9]]

             [[10 11 12] [13 14 15] [16 17 18]]
             [[19 20 21] [22 23 24] [25 26 27]]]]
      ((fn iloop [i ires]
         (if (== i (count m))
           ires
           (loop :jloop [j 0 jres 0]
             (if (== j (count (get m i)))
               (recur-to iloop (inc i) (+ ires jres))
               (loop [k 0 kres 0]
                 (if (== k (count (get-in m [i j])))
                   (recur-to :jloop (inc j) (+ jres kres))
                   (recur (inc k) (+ kres (get-in m [i j k])))))))))
        0
        0))

`

请注意，当目标是 fn 形式时，recur-to 仍然使用符号。

此外，这个补丁采取的方法有副作用：名为 :foo 的循环不会屏蔽由 fn 引入的名为 foo 的 recur 目标。如果我们最终想要使用符号作为名称引入非 fn 引入的 recur 目标（如前一个评论中讨论的类似 Scheme 风格的 let/loop 形式），那绝对是一条可行的道路。如果不是这样的话，也许它在这个上下文中比直接声明 :foo 会屏蔽 foo 要好一些吧？

Answer 4

参考：[https://clojure.atlassian.net/browse/CLJ-2235](https://clojure.atlassian.net/browse/CLJ-2235)（由 michalmarczyk 报告）

Answer 5

我一直在试验这个补丁，并发现了一个不幸的不兼容性问题。以下代码编译失败，并显示消息“没有匹配的 recur/recur-to 目标”

(defn example
  [x]
  (loop top []
    (case (int x)
      0 (loop [] (recur-to top)))))

查看 Compiler.java，我相信问题在于这个例子中表达式选择器正在发出使用 C.EXPRESSION（堆栈跟踪包括 CaseExpr.emitExpr）的分支，而不是在 CaseExpr.emit 传递的上下文中传播上下文（在这种情况下应该是 C.RETURN）。这个上下文导致 recur-to 忽略外部循环。

对于未打补丁的 Compiler.java 中的常规 recur，看起来尾调用检查是在 RecurExpr.parse 时进行的。看起来 CaseExpr.parse 正在传播上下文，所以尾调用检查通过。因此，以下代码可以编译而不出错

(defn example2
  [x]
  (loop top []
    (case (int x)
      0 (loop [] (recur)))))