添加命名循环和 recur-to 功能以支持嵌套循环

Question

从提议的电子邮件中复制到 Clojure/dev Google 社群组

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

大家好：

目前 loop/recur 只限于“单层”循环：循环形式可以发生在其他循环形式内，但没有“递归到外部循环”的功能。

几年前，我提出了一项提案，旨在向 Clojure 添加对嵌套循环的支持，并提供一个 ClojureScript 的试验性补丁，我认为其语法和语义足以使嵌套循环感觉自然，并且仍然是 core loop/recur 模型的一个自然扩展，具有相同的显式尾递归优势。


(loop foo [...]    ; 命名循环
  ...
  (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
  我现在已经实现了一个完整的修补程序，使得 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

  The remainder of this email sets out the proposal in more detail, states its key properties in a somewhat rigorous form, briefly summarizes the implementation approach and discusses certain design choices made in the patch.

概述

例如，可以这样编写：
========

(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
                                            
                                           


并且，在保证每个 recur-to 形式相对于所有其包含的循环形式（包括目标在内）都处于尾位置，并且传递给每个 recur-to 形式的参数数量与目标循环的本地变量的数量（加上一个带头循环名称参数）相匹配的情况下，这应该能够编译，并且行为类似于 Java 中的嵌套循环。

提议的语法模仿了 Scheme 的命名 lets，尽管在语义上
它们有很大的不同 - 这个提议严格限制将循环/递归模型以自然的方式扩展到嵌套循环。当然，命名 fn 形式也应该可以作为 recur-to 的目标。

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

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

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

2. 指定一个目标不在 recur-to 形式所在的循环或 fn 形式的名称中的一个 recur-to 目标是错误的。

无法在 try 键盘中递归。

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

10. 允许循环名称的阴影；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* 特殊形式的宏。）

3. 如果将来希望保留将循环命名作为局部变量的选项，那么现在最好使它们形成阴影，并由局部变量影响，因为否则在将来将其提升为局部变量的级别将是一个破坏性的变化。为了举例说明这种未来的变化可能是有用的，如果将来在 JDK 规范中实现了尾调用消除支持，那么可能会考虑是否采用类似 Scheme 的方法，将循环命名视为绑定到有一个单参数列表的函数，该参数列表对应于命名循环的循环局部变量；如果局部变量从未被引用，则这种闭包分配也许可以被优化掉。

需要注意的是，如果 TCE（尾调用消除）支持最终实现，它将使一系列替代设计方案成为可能。例如，可以引入 Scheme 风格的命名 let 作为 let 宏的一项特性。因此，在我看来，合理地限制 loop/recur/recur-to 仅限于 label+goto 样式的循环可能是有道理的，即使在假设的带有 VM TCE 支持的未来，也没有理由给予循环命名类似局部变量的处理；因此补丁当前的“无阴影交互”方法。

谨祝，
Michał

Answer 1

_Comment made by: alexmiller_

感谢 Michal，你在这里做了大量良好的工作。我认为你错过了查看 1.9 的新功能的机会，但愿意在下一个版本上回顾这个问题。

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

你是否考虑过用关键字来指定名称等其它选项？关键字没有像局部变量那样的词法阴影期望，也许可以避免这些问题？也许它们在其他方面不可取。

Answer 2

_Comment made by: 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/commit/212ea06d21d3b336ac35480c99170e81defaf956

我还准备了一个压缩版本，它将当前 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-introduced 命名的 recur 目标区分开来，这些目标当然既是局部变量。

所以我想我们可以说使用关键词作为循环名称，使用符号作为 fn 名称，如果我们对没有元数据的循环名称感到满意。我们甚至可以允许 fn 形式使用关键词名称，如果意图是创建一个有名称的 recur 目标，而不提供 fn 实例的局部引用。（这基本上是 fn + loop 的糖衣。）

我还需要再考虑一下我更喜欢哪种方法。我仍然喜欢在 recur 目标（fn / loop / recur-to）的所有地方使用符号的一致性，但让本地/非本地差异伴随着句法上的区别很有吸引力。

作为一些公开的头脑风暴，我发现使用关键词循环名称现在保留了对未来符号支持的开放可能性——可能是一次针对基于 VM-TCE 的类似 Scheme 的循环名称，这些名称将为闭包提供局部引用。或者我们可以将“符号标签”作为“let-like”形式（由 LetExpr 支持的形式，即 let & loop）的通用特性（一旦 TCE 到来）。然后我们得考虑 recur-to 是否应该能够以这样的命名 let 作为目标……还有普通的 let 呢？可能更容易坚持 label+goto 循环在 loop/recur/recur-to 中，以及通过单独的设施（可能是简单的 let）支持的 Scheme 类型的 lets，其中 fn某种意义上是两个模型的交叉点（它已经是，因为它在无名称的 recur 目标中也引入了 recur 目标）。

作为最后的笔记，我认为提到可以用于类似目的的关键词的例子只有一个是在简短字段访问语法中——我记得 (. x :foo) / (.:foo x) 被提出作为最终成为 (. x -foo) / (.-foo x) 的可能语法。尽管这是一条未走的路，但我认为它说明了如何合理地适应关键词/symbols 有效地访问两个命名空间。（好吧，在长句版本中；.: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的循环名称不会覆盖名为foo的fn引入的recur目标。如果我们最终要引入以符号为名的非fn引入的recur目标（如前一个评论中讨论的 recur-to-targetable Scheme-style let/loop形式），那么这绝对是一个可行的办法。如果不是这样，也许这比在当前上下文中声明:foo会覆盖foo少一些任意性？

Answer 4

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

Answer 5

我在尝试此补丁时发现一个不幸的不兼容性问题。以下代码编译失败，错误信息为"No matching recur/recur-to target"（没有匹配的recur/recur-to目标）

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

查看Compiler.java，我认为问题是，在这种情况下，case表达式的分支使用了C.EXPRESSION，而不是传播传递给CaseExpr.emit的上下文（在这种情况下应该是C.RETURN）。这个上下文导致recur-to忽略外部循环

对于一个未打补丁的Compiler.java中的常规recur，它看起来tail position检查是在RecurExpr.parse期间完成的。看起来CaseExpr.parse传播了上下文，因此尾调用位置检查通过。所以下面的代码可以编译而不出现错误

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