Exceptions for control flow

I also asked this question on clojurians, but I’ll ask it here as I suspect it may lead to a more indepth and opinionated discussion.

I wrote the following function, inspired by a similar function I previously implemented in Scala. However, certain parts of the Scala function are not implemented yet in my clojure version.

(defn call-with-return
  "A functional interface to CL block/return.
  The caller of call-with-return provides a unary function.
  The body of that function may call the function passed as argument.
  to cause call-with-return to return. E.g.,
  (call-with-return
    (fn [ret1]
      ;; now ret1 is a unary function, callint ret1 with argument x
      ;; causes call-with-return to immediately return x
      (if something
          (ret1 42) ;; return 42 from call-with-return
         ...)))"  
  [unary]
  (letfn [(ret [v] ;; TODO, need to somehow set NoStackTrace on the exception
            (throw (ex-info "" {:data v
                                :ident ret})))]
    (try (unary ret)
         (catch clojure.lang.ExceptionInfo e
           (if (= ret (:ident (ex-data e)))
             (:data (ex-data e))
             (throw e))))))

The function, call-with-return creates a block which can be escaped from. Such escape can be anywhere within the calling stack. The function is also reentrant, in the sense that I can nest calls to call-with-return, and the escaping protocol won’t get confused.

Moreover, since the escape function is just a lexical variable, it can be passed along to other functions allowing them to escape as well.

Usage example:

(call-with-return
 (fn [ret1]
   (call-with-return 
    (fn [ret2] 
      (ret1 42))) ;; return from outer call-with-return
   43))

 ---> 42

(call-with-return
 (fn [ret1]
   (call-with-return 
    (fn [ret2] 
      (ret2 42))) ;; return from inner call-with-return
   43))

43

So what’s the problem? Well the call to ex-info is expensive, and the underlying java implementation does a lot of work to generate stacktrace information. My Scala implementation of this function obviates this problem by creating a local subclass of Exception, overriding the java method which generates such expensive stacktrace information. I don’t know how to do this in Clojure, but I’m pretty sure it’s possible as the Scala code doesn’t do much other than propagate the information on to the java exception generator.

  def block[A](body:(A=>Nothing)=>A):A = {
    // CL like block/return, the name of the return() function is provided
    //  by the caller.
    //  Usage:  block{ ret =>  ... ret(someValue) ...}

    // extending Exception with NoStackTrace prevents throwing the
    // exception from computing the stacktrace and storing the information.
    // We don't need a stacktrace because the purpose of this exception
    // is simply to perform a non-local exit.
    import scala.util.control.NoStackTrace

    class NonLocalExit(val data:A) extends Exception with NoStackTrace {}
    def ret(data:A):Nothing = {
      throw new NonLocalExit(data)
    }
    try{
      body(ret)
    }
    catch{
      case nonLocalExit: NonLocalExit => nonLocalExit.data
    }
  }

While the scala version distinguishes different escapes by the identity of the exception class, which is different for every invocation of block, the clojure version distinguishes such cases by the identity of (:ident e), the exception data includes the actual return function ret which is different for each invocation of call-with-return. Thus calls to call-with-return may be imbedded within each other, either lexically, or within subsequent function calls.

You can do something similar to what you did in Scala and generate a class which extends Exception and overrides the fillInStackTrace method:

(ns clojure-playground.NoStackException)
(gen-class :name clojure_playground.NoStackException
           :extends java.lang.Exception)
(defn -fillInStackTrace
  ([])
  ([_n]))

Then in REPL:

(compile 'clojure-playground.NoStackException)
(import 'clojure_playground.NoStackException)
(new NoStackException "foo")

Not sure how to make it work in the context of a project, but it seems doable.
You can also use one of the myriad implementations of the Either monad.

@bsless, thanks for the suggestion. It appears from looking at the sala code that fillInStackTrace needs to return self in the case that it does not call super.fillInStackTrace. How would I do that in the -fillInStackTrace function, or is that the wrong place to do it?

I might have made a mistake in the signature:

(defn -fillInStackTrace
  ([this])
  ([this _n]))

Now you can easily return this if you want, but I’m not sure if in Clojure you need to return this from the function.
From testing before/after I don’t see a difference.

1 Like

Even if I am able to use ns/gen-class to create such a class, I still don’t see how to solve one of the problems the scala code solves. In the scala version we have a class whose identity is held in a lexical variable. i.e., within the block function there is a lexical variable NonLocalExit whose value is a class. I.e., recursive calls to block (if the body of block again calls block) then in the recursive call the new lexical variable is bound to a different class than in the outer call.

block{ ret1 =>
   block{ ret2 ==> 
     if someTest() ret1(value1) else ret2(value2)
}}

At runtime calling ret1 throws the outer exception and calling ret2 throws the inner exception. But either exceptions is thrown from inside the inner most try/catch. The inner catch does not accidentally catch the exception thrown by calling ret1.

I avoid this problem in the Clojure version by using ex-info. The inner most try/catch will capture both exceptions but the program logic determines via the call to (if (= ret (:ident (ex-data e))) ... (throw e)) and if it is an exception generated by an outer call to, re-throws the same exception via (throw e).

Again in the Scala version the inner most catch DOES NOT catch an exception generated by an outer call to block.

I admit that this may seem obscure, but in order for the code to work, it should work.

We have a similar problem in Clojure with reduce/reduced. A call to reduced will exit the inner most call to reduce, even if the call is sitting within the lexical scope of the outer reduce, thus making the idiom brittle. In the following code, the reduced sitting lexically outside the inner reduce, will nevertheless only abort from the inner reduce, not from the outer one.

(reduce (fn [acc1 item1]
          (letfn [(outer-escape [v]
                    (reduced v))]
            (reduce (fn [acc2 item2]
                      (if (some-condition)
                        (outer-escape 42)
                        (reduced 43))) () item1))) () some-sequence)

I think I’m starting to understand the source of the problem. Perhaps you could do object equality instead (the last part of this example wouldn’t work since ex-data won’t work now)

(defn call-with-return
  [f]
  (let [cause (NoStackException. (str (gensym "cause__")))
        ret (fn ret [v]
              (throw (NoStackException. "message" cause)))]
    (try (f ret)
         (catch NoStackException e
           (if (= (.getCause ^NoStackException e) cause)
             (:data (ex-data e))
             (throw e))))))

If you modify my original implementation to override ExceptionInfo you could also send the data back on it.
Any variation on this works, too, you could create a whole new instance of the thrown exception every call instead of cause, i.e.

[e (NoStackException. (str (gensym "cause__")))
 ret (fn ret [v] (throw e))]

Really not sure what the best solution could be here.

Ideally I’d like to only generate the actual exception if it is going to be thrown.
If I understand you correctly, you are suggestion to generate a new exception object at runtime on every call to call-with-return? It seems like that might work, but it would be great to avoid constructing the object in the case it is not used used.

Notice in the Scala code that the exception is only allocated if it is then immediately thrown.

Admittedly, I don’t know the overhead of creating an exception and not throwing it, and I don’t understand the overhead of try in the case that no exception is thrown. Also in the Scala case, I don’t know the overhead of creating a new class which is never instantiated.

I can theorize on some parts, and attempt to answer others.
Allocating an exception without generating a stack trace shouldn’t be costly. It’s not a huge object from what I can see. You’re also allocating a function in each call (functions in Clojure are class instances of AFn), so asymptotically your number of allocations is in the same order of magnitude.
try is very cheap on the JVM (practically free?) but prevents the JVM from performing some optimizations.
throw/catch is supposed to be very expensive as far as I know.
General recommendations I found online are to not use Exceptions for control flow.
The overhead of creating a class but not instantiating it - I have no idea, but if the definition is not done in areas of memory which are solely reserved to the executing thread there will be some locks and contentions due to writing to shared memory.
I’ll consider returning an Either monad instead.

A while ago I tried to figure out how to return as cheaply as possible, this is what I came up with:


There are tests at the bottom which works as examples.

My return isn’t as generic as yours, but instead it uses a volatile variable for control flow which (as I understand it) is as cheap as it gets. :slight_smile:

1 Like

If I’m understanding you right, you’re wanting to create a new, unique exception class with every call to call-with-return, so that (1) there is guaranteed to be only one catch that will catch this return, and (2) instances of exception objects are only generated when needed (i.e. lazily, not eagerly).

If I got that right, I’d try creating a class using gen-class, similar to what @bsless mentioned in his first reply. This is a little unpleasant because (I think) you have to switch to a different namespace to create the class. (See some examples on clojuredocs.org.) But you could switch back after you’re done, or perhaps do that work in a future so that it doesn’t affect your current namespace. You’d also need to compile the new class and import it into the current namespace before using it.

Alternatively, have you seen the idea of “conditions”, a.k.a. “conditional restarts”? They solve a similar problem. You might be able to solve your problem that way; furthermore, you might like the rich approach to control flow that they provide. There’s a solid introduction to them in Chapter 19 of Practical Common Lisp by Peter Seibel. There’s also a capable Clojure library, special, which weighs in at just a few dozen lines of code. If you don’t like that one, its README mentions others that might appeal.