你怎么在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语言不支持一流的延续.这一点,以及JVM没有提供捕获当前延续的方法的事实,意味着无法实现letcc对所有情况都满意的方法.

但是,在某些情况下可以实现延续.具体来说,如果您拥有所有代码(即必须捕获continuation的代码),那么您可以使用continuation-passing-style(CPS).基本上,您为每个函数添加一个额外的参数.此参数是表示该调用的延续的函数.您通过调用continuation函数"返回"一个值.当然,这种风格本身就很难写 - 但幸运的是,这是一种我们可以通过宏轻松应用于特定代码的转换.

就其本身而言,CPS不适用于不进行尾调用优化(TCO)的平台.因为CPS中任何函数的最后一步是调用另一个函数,没有TCO,堆栈会快速溢出,除了最简单的计算.这个问题可以通过采用thunking和trampolining来解决.

解决方案

如上所述,您可以使用宏编写自己的CPS转换.但是,我会邀请你结账我的pulley.cps库,它已经为你做了这个.有替代方案,但据我所知,pulley.cps是唯一提供以下所有功能的Clojure库:

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

替代方案包括:

• delimc提供了一个用于分隔连续的库.这似乎不是很完整(例如,binding失败,因为它不理解try/ finally块)并且在4年内没有被触及.
• algo.monads是Clojure的monad库.monad和continuation之间存在强大而有趣的关系,而algo.monads提供了一个延续monad.虽然monadic风格并不那么方便,但它确实具有使效果更明确的优点,这有助于封装使用不具有控制效果的代码.另外,do符号(例如,domonad宏)极大地模糊了直接和一元风格之间的界限.