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

Question

从Clojure/dev Google组的提案邮件复制

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

你好，

目前loop/recur仅限于"单层"循环：loop形式可以放在其他loop形式内部，但没有提供"递归到外部循环"的设施。

几年前，我提出了一项提案，建议为Clojure添加对嵌套循环的支持，并附带了ClojureScript的proof-of-concept补丁，使用了我认为足以使嵌套循环感觉自然，同时仍然自然扩展核心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))))                回滚到ilop
      （完成))))


并且，如果每个 recur-to 形式相对于其所有封装循环结构（直至目标及其包含的目标，包含目标本身）都处于尾递归位置，并且传递给每个 recur-to 形式的参数数与目标循环的局部变量数相匹配（以及加上一个前导循环名称参数），则应该能够编译并且其行为与 Java 中的嵌套循环相似。

所提出的语法是在 Scheme 的命名 let 上构建的，尽管在语义上
它们相当不同——此提案严格限于以自然方式扩展循环/递归模型为嵌套循环。当然，带有名称的 fn 形式也应该被视为有效的 recur-to 目标。

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

在上文所述补丁到位后，以下规则在编译时强制执行

1. 每个 recur-to 形式必须相对于其所有封装循环结构（无论是否有名称，直至包括其目标目标）处于尾递归位置。

2. 指定一个并不出现在 recur-to 形式的封装循环或 fn 形式的名称中的 recur-to 目标是一种错误。

3. 无法跨越 try 进行 recur-to。

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

5. 允许遮蔽循环名称；recur-to 只能针对以其尾递归位置相对于它是内部最深的具有给定名称的循环。被遮蔽的命名循环引入的循环局部在遮蔽循环内部仍然可见（除非它们被具有相同名称的其他局部遮蔽）。

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

内部最深的循环或 fn 形式始终可以使用 plain recur 进行定位，无论它是否有名称。此外，(recur-to nil ...) 等价于 (recur ...)（即使内部最深的循环或 fn 形式实际上是带有名称的），而 (loop nil [...] ...) 等价于 (loop [...])。

实现方法摘要
======================================

此补丁修改了编译器中的循环标签处理，并实现了循环宏的一些必要的调整。

它还向 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* 特殊形式。）

3. 如果未来有必要保留将循环名称视为局部变量的选项，那么现在可能最好将它们设为可影响其他变量的和被影响，否则在以后某个时间点将它们提升到局部变量的地位将会引发破坏性变更。为了举例说明这样的未来变更可能是有用的，如果尾调用消除支持在未来JDK规范中出现，有人可能会考虑是否采用类似于Scheme的方法，将循环名称视为绑定到只有一个参数列表的函数的局部变量；如果这个局部变量从没有被引用，那么这种闭包分配可能可以通过优化来移除。

值得注意的是，如果尾调用消除（TCE）支持确实出现了，它将启用一系列替代的开发设计。例如，可以引入类似Scheme的风格命名let作为let宏的一项功能。因此，在我看来，限制循环/recur/recur-to仅用于标签+goto风格的循环似乎是合理的，即使是在假设的具有虚拟机TCE支持的将来也是如此，没有理由赋予循环名称类似局部的待遇；因此，补丁当前采用没有影子交互的方法。

致敬，
Michał

Answer 1

_由：alexmiller_发表的评论

谢谢Michał，看起来你在这里做了大量的好工作。我认为你刚刚错过了观察1.9中新功能窗口的机会，但希望能够在这个下一个版本中重新审视此问题。

将recur从特设形式变为宏似乎并不理想，所以可能最好要么扩展现有形式，要么添加recur-to特设形式。

您考虑过其他指定名称的选项吗，比如关键字？关键字不带有像局部变量一样的词法阴影期望，因此可能可以绕过这些问题。也许它们由于其他原因而不被推荐。

Answer 2

_由：michalmarczyk_发表的评论

致敬，很高兴知道这些。

*recur-to 作为独立的特设形式*

关于变更recur是合理的。这里是一个使recur-to成为新独立特设形式的补丁版本。请注意，它在编译器中仍然与循环和let分享RecurExpr类。此补丁旨在叠加在先前的补丁之上，以明确说明差异

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

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

我还准备了一个压缩版本，该版本在当前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 目标时相同的 recur 目标名称的形式，这看起来是合理的）；部分是“默认情况”，因为静态符号引用通常使用符号。（clojure.core/extend 使用关键字，但那些不是真正的静态引用。）不一定确定将元数据附加到循环名称的功能是否可能很有用，但这也是一个因素。

关于现有用法的第二部分可能或可能不是主要考虑因素，尤其是在循环名称相对独特，它们只能通过单个特殊形式——recur-to——被引用，并且在其他情况下在源代码中是看不见的。这也使它们与 fn 引入的命名 recur 目标不同，后者当然也可以充当局部变量。

因此，如果我们愿意容忍没有元数据的循环名称，我们可能可以使用关键字作为循环名称，符号作为 fn 名称。我们甚至可以允许 fn 表达式使用关键字名称，如果目的是建立一个命名 recur 目标而不提供 fn 实例的局部引用。（这基本上是 fn + loop 的糖衣包装。）

我还需要更多考虑哪种方法更受欢迎。我仍然喜欢在 recur 目标处使用符号的连贯性（fn / loop / recur-to），但有一点点魅力是伴随着局部/非局部差异的语法区别。

作为公开头脑风暴的一部分，我发现使用关键字作为循环名称可以保持未来支持符号的可能性——或许是为了那些提供对闭包的局部引用的 VM-TCE-like Scheme 循环名称。或者，我们可以在 TCE 实现“let-like”形式（由 LetExpr 支持的 let & loop）时，将“symbol labels”作为“let-like”形式的通用功能。那时，我们需要考虑 recur-to 是否可以针对这样的命名 let... 还有关于普通的 let？可能会更简单地将 label+goto 循环保留在 loop/recur/recur-to 中，并通过一个独立设施（可能简单地是 let）支持 Scheme-like 的 let，其中 fn 是两种模式的某种交叉点（它已经如此，因为它引入了 recur 目标甚至在没有命名的情况下。）

作为最后的笔记，我认为提出使用关键词进行类似操作的可能性的一幕发生时——我记得 (. x :foo) / (.:foo x) 被提出来作为最终成为 (. x -foo) / (.-foo x) 的可能语法。（虽然是一个没有选择的选项，但我认为它说明了如何让人合理地习惯于关键词/符号实际上在访问两个命名空间。（好吧，在长版本中；.:foo 在技术上是一个符号。使用关键字作为循环名称不会对“keyword-derived”符号的任何类别给予特殊待遇。）

无论如何，我会看看能否准备出一种使用循环名称的关键字的补丁版本。

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的循环名称不会覆盖名为foo的fn引入的recur目标。如果我们最终想引入不使用fn引入的recur目标作为符号名称（如先前评论中讨论的recursive Scheme-style let/loop形式），那肯定是一个好方法。如果不是，或许这比在这个上下文中声明:foo会覆盖foo更少任意性？

Answer 4

参考资料： 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，我相信问题在于，至少在这个例子中，case表达式正在使用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)))))