clojure - 在 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)))))

我的问题是:如何在 Clojure 中执行letcc？

Answer 1

背景

核心 Clojure 语言不支持一流的延续。事实上，JVM 没有提供捕获当前延续的方法，这意味着无法实现满足所有情况的 letcc。

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

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

解决方案

正如我上面提到的，您可以使用宏编写自己的 CPS 转换。不过，我邀请您查看我的 pulley.cps图书馆，它已经为你做到了这一点。还有其他选择，但据我所知，pulley.cps 是唯一提供以下所有功能的 Clojure 库:

• call-cc/let-cc
• “ native ”(未转换)和转换代码之间的无缝调用
• 异常(try/catch/finally)支持
• 绑定(bind) 表单(它们也是正确的尾递归!)
• 允许您提供现有原生函数的 CPS 版本(如果您想捕获该函数内的延续，这是必需的)

替代方案包括:

• delimc提供用于分隔延续的库。这似乎不是很完整(例如，绑定(bind)失败，因为它不理解try/finally block )并且还没有' 4年来没有被碰过。
• algo.monads是 Clojure 的 monad 库。 monad 和 Continuation 之间存在着紧密而有趣的关系，algo.monads 提供了 Continuation monad。尽管一元样式不太方便，但它确实具有使效果更加明确的优点，这有助于将使用控制效果的代码与不使用控制效果的代码封装在一起。另外，do 表示法(例如，domonad 宏)极大地模糊了直接风格和单子(monad)风格之间的界限。