添加命名循环和 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 ...)))) ; 回到命名循环
                          （注意：这必须位于尾部位置
                          与这三个循环相关


  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 能够实现所提议的功能（第一个链接是基于当前主分支的分支，即 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
            ；(工作)
            (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 形式名称的 recur-to 目标是错误的。

不可能在 try 跨越 recur。

4. 传递给 recur 的参数数量超出初始目标/标签参数的数量必须与目标循环或 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-to 作为将递归到新的 recur* 特殊形式的宏的同时保留 recur。)

3. 如果希望在将来保留将循环名作为局部变量的选项，那么现在将它们作为本地变量的影子可能是更好的选择，因为否则在以后将它们提升到本地变量的地位将是一个破坏性的变化。为了说明为什么未来的这种变化可能会很有用，假设在未来的JDK规范中出现了尾调用消除支持，人们可能会考虑是否采用类似于Scheme的方法，将循环名作为一个局部变量绑定到只有一个arglist的函数，这个arglist对应于命名循环的局部变量；如果本地变量从未被引用，这种闭包分配可能可以优化掉。

值得注意的是，如果TCE支持确实存在，它将使得一系列替代设计成为可能。例如，可以作为let宏的一个特性引入Scheme风格的命名lets。因此，在我看来，将循环/recur/recur-to限制为只使用标签+goto风格的循环似乎是合理的，即使是在假设的未来有VM TCE支持的情况下，也没有理由将循环名称享有类似局部的待遇；因此，补丁当前采用的没有影子交互的方法。

问候,
Michał

Answer 1

_评论者：alexmiller_

感谢Michał，你在这里做了很多出色的工作。我认为你刚刚错过了查看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

我还准备了一个压扁的版本，它直接将当前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目标的一致性，但让局部/非局部差异伴随着语法上的区别也很吸引人。

在这种情况下，公开思考，我觉得使用关键词循环名称现在可以保持开启未来悬挂支持符号的可能性——可能是为那些基于VM-TCE的类似Scheme的循环名称提供对闭包的局部引用。或者我们可以将“符号标签”变成“let-like”形式（也就是由LetExpr支持的，即let & loop）的一种通用特性一旦TCE着陆。然后我们会考虑recur-to是否可以针对这样的命名let……再说说普通的let？可能更容易坚持使用loop/recur/recur-to中的label+goto循环和通过一个单独的设施（可能只是一个简单的let）支持的类似Scheme的lets，而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的recur目标。如果我们最终想引入非fn引入的recur目标，使用符号作为名称（如前面评论中讨论的，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)))))