添加命名循环和递归到嵌套循环的功能

Question

从提交给 Clojure/dev Google 群组的提案邮件中复制

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

你好，

目前 loop/recur 仅限于 "单层" 循环：循环形式可以出现在其他循环形式内，但没有 "递归到外部循环" 的功能。

几年前我提出了一项提案，为 Clojure 添加对嵌套循环的支持，并为 ClojureScript 提供了概念验证补丁，语义和语法我认为足够让嵌套循环感觉自然，同时 Still 是核心 loop/recur 模型的自然扩展，具有相同的尾递归好处


(loop foo [...]    ; 命名循环
 
 
 
 
 
 
 
 


  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 之后的 "为下一个开发迭代做好准备" 的提交；第二个链接是该分支的当前 tip，供将来参考）

  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)
            (work)
            (recur (inc j)))            )
          (recur-to iloop (inc i)))) ; 递归到 iloop
      
  


并且，如果每个 recur-to 形式相对于所有包含它的循环形式都位于尾部（包括其目标），且向每个 recur-to 形式传递的参数数量与目标循环的局部变量数相匹配（再加上领先循环名称参数），则应能编译并具有类似 Java 中嵌套循环的行为。

建议的语法以 Scheme 的命名 let 为模型，虽然在语义上
两者有很大区别 - 此提议严格限于以自然的方式将循环/递归模型扩展到嵌套循环。当然，命名 fn 形式也应该是有效的 recur-to 目标。

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

在上面的补丁实施后，以下规则在编译时强制执行

1. 每个 recur-to 形式都必须相对于其所有包含的循环形式（无论是命名还是未命名的）位于尾部，直至包括其目标（可能是命名循环或 fn 形式）。

2. 指定一个 recur-to 目标，该目标不在其包含的循环或 fn 形式的名称列表中，这是错误的，并且它需要相对于其位于尾部的循环或 fn 形式。

3. 无法在 try 语句中 recur。

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

5. 允许覆盖循环名称；recur-to 可以只针对名称最内的循环。此外，loop 内部通过引入的命名循环引入的循环局部变量在覆盖的循环中仍然可见（除非它们被同样命名的局部变量覆盖）。

注意。循环名称不是局部变量。特别是，它们既不被局部变量覆盖也不覆盖具有相同名称的局部变量。这一点值得更深入的讨论；请参见邮箱末尾的“设计选择”部分。

最内层的循环或 fn 形式始终可以使用纯 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-to 作为将 recur 代理到新 recur* 特殊形式的宏的同时，可以保留 recur 如其当前状态。）

3. 如果将来希望保留将循环命名作为本地变量的选项，现在最好是将它们视为被本地变量阴影和被阴影，因为否则在以后提升它们的本地变量状态将会是一个破坏性变化。为了举例说明这种未来的变化可能是有用的，如果尾调用消除支持在未来JDK规范中到来， someone might consider whether adopting a Scheme-like approach with the loop name treated as a local bound to a function with a single argument list corresponding to the loop locals of the named loop would be useful; 如果本地变量从未被引用，那么这种变化可能不会包含任何闭环分配，这或许可以被优化掉。

值得注意的是，如果尾调用消除支持确实出现，它将启用一系列替代设计。例如，可以作为let宏的特性的Scheme风格的命名let引入。因此，在我看来，限制循环/recur/to只能使用标签+goto风格的循环似乎是合理的，即使在假设的未来中具有虚拟机尾调用消除支持，也没有理由给予循环命名类似本地的待遇；因此，补丁目前采用无阴影交互的方法。

谨致问候，
Michał

Answer 1

由_alexmiller_发表评论：

感谢Michał，你在这里做了很多好的工作。我认为你错过了1.9版新特性审查的窗口，但希望在下一次发布中能回头考虑这个问题。

将recur从特称形式变为宏看起来不太合适，所以可能更好是在现有的形式上扩展或者添加recur-to特称形式。

你是否考虑过其他指定名称的方法，比如关键字？关键字没有携带你与本地变量相同的词法阴影期望，所以可能可以避开这些问题？也许由于其他原因也不理想。

Answer 2

由_michalmarczyk_发表的评论：

问候，这是好消息。

*recur-to作为一个不同的特称形式*

关于recur的改变，这是公平的。这是一个使recur-to成为一个新的、单独的特称形式的补丁版本。请注意，它仍然与编译器中loop和let共享RecurExpr类别。这个补丁旨在应用于之前的补丁之上，以确保delta清晰

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

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

我还准备了一个归并版本，它将当前主版本直接带到相同的状态

    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 实例的局部引用的情况下建立命名 recur 目标，甚至可以允许 fn 表达式使用关键字名称。（这基本上是 fn + loop 的语法糖。）

我还需要考虑我最喜欢哪种方法。我仍然喜欢在 recur 目标（fn / loop / recur-to）所有地方使用符号的一致性，但让局部/非本地差异伴随着一种句法区别是诱人的。

在进行一些公开头脑风暴的过程中，我发现现在使用关键字循环名称保持了对未来支持符号的可能性开放——可能用于那些 VM-TCE 基础上的类似于 Scheme 的循环名称，能够为闭包提供局部引用。或者我们可以在 TCE 到来时使“符号标签”成为“let-like”形式（即由 LetExpr 支持，即 let & loop）的通用功能。然后我们得考虑 recur-to 是否应该能够瞄准这种命名的 let…至于普通的 let？可能最好是坚持在 loop/recur/recur-to 中使用 label+goto 循环，并通过一个不同的设施（或许是简单的 let）支持类似 Scheme 的 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目标，使用符号作为名称（就像之前注释中讨论的具有 recur-to-targetable Scheme-style let/loop 形式的 recur），那么这肯定是一个好的选择。如果不是，那么这也许仍然比声明在这个上下文中：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发出分支（stacktrace包括 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)))))