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?

This question is a bit unclear. Are you looking for a better `letcc` than yours or are you wondering what's wrong with it? I don't think it's possible to do the "real" `letcc` in Clojure since it doesn't have first-class continuation. — molbdnilo, May 23 '16 at 14:26

score 5 · Accepted Answer · answered May 23 '16 at 15:41

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.

Its not really a deal breaker that the runtime has support for tail calls or call/cc for the language to have those features as it could fake it at compile time. No runtime has hardware support for tail calls and `call/cc` so at some level it's always faked. — Sylwester, May 23 '16 at 22:14
@Sylwester Not sure what you mean. Couldn't the same be said about function calls? I mean, the hardware might have a `call` instruction (e.g., x86 architecture), but the compiler / runtime still has to deal with argument passing, etc. Plus, regarding TCO ... tail call is to not-tail call as `call` is to `jmp`. So I would say both forms of function calls are equally supported by hardware. But anyway, the whole point of the answer is that you *don't* have to have continuations built-in to a language in order to implement them. — Nathan Davis, May 23 '16 at 23:04
Yes or both are equally emulated by resulting machine code since procedures doesn't have arguments. What I though was strange was *there is no way of implementing letcc that is satisfactory for all situations*. I'm thinking we have namespaces and can shadow every single of the special forms so there should be a way of just importing a continuations library and just have `call/cc` work without the need to introduce new special forms, but shadow existing ones of course. — Sylwester, May 23 '16 at 23:34
@Sylwester, that is in fact more-or-less the purpose of `override-fn` and `override-macro!` in pulley.cps, although it accomplishes the effect without the need for shadowing (in the case of `override-fn`, it implements the `ICallable` protocol on the function's class). This can help in some cases, but not in every case. For example, if you use Java interop to call a method on a Java class, there's no way to capture the continuation within that method. Sure, you could implement the same functionality in Clojure and CPS transform in -- but are you going to reimplement all of Java? — Nathan Davis, May 24 '16 at 00:21
@Sylwester Also remember that Clojure defines a lot of Java interfaces for various things, such as datastructures (`ISeq`, `IPersistentMap`, `IPersistentVector`). So to provide CPS transformations of these features is not very straight-forward. I suppose one could implement shadow interfaces for these (I've thought about that from time to time), but basically you end up re-implementing Clojure. At some point, maybe you'd be better off just restarting and build a language with continuations baked in? Anyway, thanks for the feedback! — Nathan Davis, May 24 '16 at 00:29

score 3 · Answer 2 · edited May 23 '17 at 11:52

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

How do you do letcc in Clojure?

2 Answers2

Background

Solutions