你如何在 Clojure 中使用 letcc？

Question

书中The Seasoned Schemer-作者写了如下代码：

(define intersectall
  (lambda (lset)
    (letcc hop
      (letrec
          ((A (lambda (lset)
                (cond
                  ((null? (car lset))  (hop (quote ())))
                  ((null? (cdr lset))  (car lset))
                  (else
                    (intersect (car lset)
                               (A (cdr lset))))))))
        (cond
          ((null? lset)  (quote ()))
          (else  (A lset)))))))

以下是它在 Clojure 中的潜在外观：

(defmacro letcc
  [name & body]
  `(letfn [(~name [arg#]
             (throw (ex-info (str '~name) {:name '~name :value arg#})))]
     (try ~@body
          (catch clojure.lang.ExceptionInfo e#
            (if (= '~name (:name (ex-data e#)))
              (:value (ex-data e#))
              (throw e#))))))

(defn intersectall
  [lset]
  (letcc hop
   (letfn [(A [lset]
             (cond (empty? (first lset))
                   (hop ())
                   (empty? (rest lset))
                   (first lset)
                   :else
                   (intersect (first lset) (A (rest lset)))))]
     (cond (empty? lset)
           ()
           :else
           (A lset)))))

我的问题是：你 letcc 在 Clojure 中的表现如何？

Answer 1

背景

核心 Clojure 语言不支持 first-class 延续。那个，以及 JVM 没有提供捕获当前延续的方法的事实，意味着没有办法实现对所有情况都令人满意的 letcc。

但是，在某些情况下可以实现延续。具体来说，如果您拥有所有代码（即必须在其中捕获延续的代码），那么您可以采用延续传递样式 (CPS)。基本上，您向每个函数添加一个额外的参数。此参数是一个函数，表示该调用的继续。您 "return" 通过调用延续函数获得一个值。当然，这种风格本身写起来很痛苦——但幸运的是，这是一种我们可以通过宏轻松应用于特定代码的转换。

CPS 本身不适合不进行尾调用优化 (TCO) 的平台。因为 CPS 中任何函数的最后一步都是调用另一个函数，所以如果没有 TCO，除了最琐碎的计算之外，堆栈会很快溢出。这个问题可以通过使用 thunking 和 trampolining 来解决。

解决方案

正如我上面提到的，您可以使用宏编写您自己的 CPS 转换。但是，我会邀请您查看我的 pulley.cps 图书馆，它已经为您完成了这项工作。有替代方案，但据我所知，pulley.cps 是唯一提供以下所有功能的 Clojure 库：

call-cc/let-cc
"native"（未转换）和转换代码之间的无缝调用
异常（try/catch/finally）支持
binding 形式（它们也是正确的尾递归！）
允许您提供现有本机函数的 CPS 版本（如果您想在该函数中捕获延续，这是必需的）

备选方案包括：

delimc 提供了一个用于定界延续的库。这似乎不是很完整（例如，binding 失败，因为它不理解 try/finally 块）并且已经 4 年没有被触及了。
algo.monads 是 Clojure 的 monad 库。 monads 和 continuations 之间有着紧密而有趣的关系，algo.monads 提供了一个 continuation monad。尽管 monadic 样式不是很方便，但它确实具有使效果更加明确的优势，这有助于将使用控制效果的代码与不使用控制效果的代码封装起来。另外，do 表示法（例如 domonad 宏）极大地模糊了直接样式和单子样式之间的界限。

Answer 2

您的示例中 (letcc hop ...) 捕获的延续被用作 "upwards continuation"。可以使用名称 return 代替：(letcc return ... (return () ...)。当调用名为 return 的延续时，整个 letcc 表达式的计算结果为 return 的值——然后 returned 作为 intersectall 的结果。

这意味着1.延续上升（我们return）和2.延续仅使用一次。当满足这些条件时，可以像您所做的那样根据 try 和 catch 实施 letcc。

据我所知，通过编写 letcc 宏，您已经回答了自己的问题。

正如 Nathan Davis 提到的，还有其他延续用例，但 Clojure 不直接支持它们。

注：这里有个相关问题：The Seasoned Schemer, letcc and guile

你如何在 Clojure 中使用 letcc？

How do you do letcc in Clojure?

scheme

continuations

clojure

背景

解决方案