How do you do letcc in Clojure?

Question

In the book The Seasoned Schemer - the author writes the following code:

(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)))))))

Here is potentially how it could look in 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)))))

My question is: How do you do letcc in Clojure?

Answer 1

The continuation caught by (letcc hop ...) in your example is used as an "upwards continuation". One could have used the name return instead: (letcc return ... (return () ...). When the continuation named return is called, the entire letcc-expression evaluates to the value given to return -- which is then returned as the result of intersectall.

This means that 1. the continuation goes up (we return) and 2. the continuation is used once only. When these conditions are met, one can implement letcc in terms of try and catch as you have done.

So as I see it, by writing your letcc macro, you have answered your own question.

Now as Nathan Davis mentions there are other use cases of continuations, but Clojure does not support them directly.

Note: There is a related question here: The Seasoned Schemer, letcc and guile

Answer 2

Background

The core Clojure language does not support first-class continuations. That, and the fact that the JVM does not provide a way to capture the current continuation, means there is no way of implementing letcc that is satisfactory for all situations.

However, it is possible to implement continuations in some situations. Specifically, if you own all the code (that is, the code in which you must capture continuations) then you can employ continuation-passing-style (CPS). Basically, you add an extra parameter to each function. This parameter is a function that represents the continuation of that call. You "return" a value by calling the continuation function. Of course, this style is a pain to write by itself -- but fortunately this is a transform we can easily apply to specific code via macros.

By itself, CPS is unsuitable for platforms that do not do tail-call optimization (TCO). Because the last step of any function in CPS is to invoke another function, without TCO the stack quickly overflows except for the most trivial of computations. This problem can be solved by employing thunking and trampolining.

Solutions

As I alluded above, you can write your own CPS transform using macros. However, I would invite you to checkout my pulley.cps library, which already does this for you. There are alternatives, but as far as I'm aware pulley.cps is the only Clojure library that provides all of the following:

• call-cc/let-cc
• Seamless calls between "native" (non-transformed) and transformed code
• Exception (try/catch/finally) support
• binding forms (they're properly tail-recursive too!)
• Allows you to provide a CPS version of an existing native function (this is necessary if you want to capture a continuation within that function)

Alternatives include:

• delimc provides a library for delimited continuations. This doesn't appear to be very complete (e.g., binding fails because it doesn't understand the try/finally block) and hasn't been touched in 4 years.
• algo.monads is a monad library for Clojure. There is a strong and interesting relationship between monads and continuations, and algo.monads provides a continuation monad. Although monadic style isn't quite as covenient, it does have the advantage of making the effect more explicit, which can aid in encapsulating the code that uses control effects from the code that doesn't. Plus, do notation (e.g., the domonad macro) greatly blurs the lines between direct and monadic style.