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

Question

从提案电子邮件复制到Clojure/dev谷歌群组

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

你好，

目前loop/recur仅限于“单层”循环：循环形式可以嵌套在其他循环中，但尚无“回退到外部循环”的功能。

几年前，我提出了一项提案，为Clojure添加对嵌套循环的支持，并提供了一个ClojureScript的proof-of-concept补丁，其中包含我认为足够的语法和语义来使得嵌套循环感觉自然，同时仍为core loop/recur模型的自然扩展，具有相同的显式尾递归优势。


(loop foo [...]    ; 带名循环
  ...
  (loop [...]                     intervening loop
    ...
    (loop [...]           innermost loop
       ...(loop [...]              (recur-to 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
  https://github.com/michalmarczyk/clojure/tree/recur-to

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

  我在Clojure中实现了一个完整的补丁，以启用所提出的特性（第一个链接是基于当前主分支的分支，即1.9.0-alpha17后的“为下一次开发迭代做准备”的提交；第二个链接是分支当前尖端的链接，作为未来参考）。

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

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

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

此电子邮件的其余部分更详细地说明了提案，以某种严谨的形式表述其关键特性，简要总结了实现方法，并讨论了补丁中做出的某些设计选择。

概述
========

想法是，人们可以编写例如代码。


(let [m (two-dimensional-matrix)]
  (loop iloop [i 0]                     named loop
    (if (< i i-lim)
      (loop [j 0]                     nested anonymous loop
        (if (< j j-lim)
          (do
            (work)
            (recur (inc j)))     recur to the innermost loop
          (recur-to iloop (inc i)))) ; recur to iloop
      (done))))


并且，前提是每个 recur-to 形式与包含其的所有循环形式（包括其目标）都是尾位置的，并且提供给每个 recur-to 形式的参数数量与目标循环的局部变量数量相匹配（对于引导循环名称参数额外加一），则应该可以编译并且行为与 Java 中的嵌套循环非常相似。

所提出的语法在 Scheme 的命名 let 上进行了建模，虽然在语义上
它们有很大不同 - 本提议仅限于以自然的方式将循环/递归模型扩展为嵌套循环。当然，命名 fn 形式也应该是有效的 recur-to 目标。

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

假设将上述补丁应用于，编译时会强制执行以下规则

1. 每个 recur-to 形式都必须与包含其的所有循环形式（无论是命名还是非命名）的尾位置相匹配，直到包括其目标（这可能是命名循环或 fn 形式）。

2. 指定一个 recur-to 目标，而它并不是 recur-to 形式的包含循环或 fn 形式的名称之一，这是一个错误。

无法在 try 之间递归。

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

5. 允许覆盖循环名称；recur-to只能针对尾置位置的给定名称的内部最深层循环。由被覆盖的命名循环引入的循环局部变量在覆盖循环内部仍然可见（除非它们被相同名称的局部变量覆盖）。

注意。循环名称不是局部变量。特别是，它们既不受同名列局部变量的影响，也不会影响它们。这一点值得进一步讨论；请参阅本电子邮件末尾的设计选择部分。

内部最深层循环或 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 的同时添加 recur-to 作为将 recur 代理到新 recur* 特殊形式的宏。）

3. 如果未来希望保留将循环名视为局部变量的选项，那么现在可能更倾向于将它们设置为影子和被影子局部变量，否则在未来将其提升为局部变量的状态将导致不兼容的更改。为了举例说明这种未来更改可能是有用的，如果未来JDK规范中有了尾调用消除的支持，那么可以考虑是否采用类似于Scheme的方法，将循环名视为一个仅有一个参数列表（对应循环局部变量）的局部变量函数；如果这个局部变量 never 引用，那么这种 closure 分配可能会被优化掉。

需要指出的是，如果TCE（尾调用消除）支持最终实现，它将启用一系列的替代设计方案。例如，可以引入类似Scheme的命名let作为let宏的一个特性。因此在我看来说，限制loop/recur/recur-to仅用于label+goto风格的循环是合理的，即使在假设的未来有VM TCE支持的情况下，也没有理由将循环名视为局部变量；因此，该补丁当前采用不进行阴影交互的方法。

致谢，
Michał

Answer 1

_Comment made by: alexmiller_

感谢Michał，看来你在这里做了很多好的工作。我认为你刚刚错过了看1.9版本新功能的时间窗口，但希望在下一个版本上回过头来看这个。

将recur从特殊形式改为宏的方式似乎并不理想，所以可能会更好，要么扩展现有的形式，要么添加recur-to特殊形式。

你考虑过其他指定名称的选项，如关键字吗？关键字不会像局部变量那样带有所需的词法阴影，所以也许可以避开这些问题？也许它们在其他方面也不理想。

Answer 2

_Comment made by: michalmarczyk_

致敬，很高兴知道。

*recur-to作为一个独立的特殊形式*

关于改变recur，这是一个将recur-to作为一个新独立特殊形式的补丁版本。请注意，它仍然与编译器中的RecurExpr类共享，就像loop和let共享LetExpr一样。这个补丁旨在基于前一个补丁进行，以便清楚地显示变更。

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

    我在Clojure中实现了一个完整的补丁，以启用所提出的特性（第一个链接是基于当前主分支的分支，即1.9.0-alpha17后的“为下一次开发迭代做准备”的提交；第二个链接是分支当前尖端的链接，作为未来参考）。

我还准备了一个压缩版本，直接将当前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 实例局部引用的命名 recur 目标，我们甚至可以允许 fn 形式使用关键字名称（这将是在 fn 和 loop 上的糖）。

我必须再考虑一下哪种方法更令我满意。我仍然喜欢在整个 recur 目标处使用符号一致性的感觉（fn / loop / recur-to），但是随着本地/非本地差异伴随着句法上的区别，这很有吸引力。

在公开头脑风暴的过程中，我发现使用关键字现在作为循环名称很吸引人，因为它可以保留在将来添加对符号支持的余地——或许是为了那些基于 VM-TCE 的类似 Scheme 的循环名称，这将提供闭包的局部引用。或者我们可以在 TCE 到来时使"symbol labels"成为类似"let"的表单的通用特性（即由 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))

`

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

还请注意，此补丁采用的方案有一个副作用，即名为:foo的循环不会遮蔽由fn引入的递归目标foo。如果我们最终想使用符号作为名称引入非fn引入的递归目标（如表中前一个评论中讨论的recur-to-targetable 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)))))