I’ll be back

Recursion is one of the really nice techniques in computer science which allows proof to follow implementation. Tail recursion, and self tail recursion in particular, are often patterns that compilers go to a lot of effort to implement efficiently. Without such optimisations, it is all too easy to write something that works for test cases and then fails with a stack overflow in a production system.

In Clojure, if we compile the function
(defn checkEven [x]
  (letfn [(step [y status]
            (if (= x y)
               status
             (step (+ y 1) (not status))))]
    (step 0 true)))

We see that it works nicely for small values:
user=> (test.foo/checkEven 1)
false
user=> (test.foo/checkEven 2)
true
user=> (test.foo/checkEven 3)
false

But then fails with a stack overflow for large values.
user=> (test.foo/checkEven 30000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

If we compile the code and look at the resulting classes, we find that the nested step function is compiled into an instance of a class foo$checkEven__149$step__151 (when compiled in a namespace foo), and the invoke method on this class has the following java definition.

public java.lang.Object invoke(java.lang.Object, java.lang.Object)   throws java.lang.Exception;
  Code:
   0:    aload_0
   1:    getfield    #50; //Field x:Ljava/lang/Object;
   4:    aload_1
   5:    invokestatic    #60; //Method clojure/lang/Util.equiv:(Ljava/lang/Object;Ljava/lang/Object;)Z
   8:    ifeq    16
   11:    aload_2
   12:    goto    51
   15:    pop
   16:    aload_0
   17:    checkcast    #62; //class clojure/lang/IFn
   20:    aload_1
   21:    getstatic    #39; //Field const__2:Ljava/lang/Object;
   24:    invokestatic    #68; //Method clojure/lang/Numbers.add:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Number;
   27:    getstatic    #43; //Field const__3:Lclojure/lang/Var;
   30:    invokevirtual    #72; //Method clojure/lang/Var.get:()Ljava/lang/Object;
   33:    checkcast    #62; //class clojure/lang/IFn
   36:    aload_2
   37:    invokeinterface    #75,  2; //InterfaceMethod clojure/lang/IFn.invoke:(Ljava/lang/Object;)Ljava/lang/Object;
   42:    aconst_null
   43:    astore_1
   44:    aconst_null
   45:    astore_2
   46:    invokeinterface    #77,  3; //InterfaceMethod clojure/lang/IFn.invoke:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
   51:    areturn

The self tail call in the source happens on line 46, where we see that it isn’t implemented as a tail call in the byte code.

Clojure has a way of telling the compiler to use a self tail call. This is done by using the recur special form. In our example above, we can rewrite it to.
(defn checkEven [x]
  (letfn [(step [y status]
            (if (= x y)
               status
             (recur (+ y 1) (not status))))]
    (step 0 true)))

At which point the invoke method is changed to
public java.lang.Object invoke(java.lang.Object, java.lang.Object)   throws java.lang.Exception;
  Code:
   0:    aload_0
   1:    getfield    #50; //Field x:Ljava/lang/Object;
   4:    aload_1
   5:    invokestatic    #60; //Method clojure/lang/Util.equiv:(Ljava/lang/Object;Ljava/lang/Object;)Z
   8:    ifeq    16
   11:    aload_2
   12:    goto    43
   15:    pop
   16:    aload_1
   17:    getstatic    #39; //Field const__2:Ljava/lang/Object;
   20:    invokestatic    #66; //Method clojure/lang/Numbers.add:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Number;
   23:    getstatic    #43; //Field const__3:Lclojure/lang/Var;
   26:    invokevirtual    #70; //Method clojure/lang/Var.get:()Ljava/lang/Object;
   29:    checkcast    #72; //class clojure/lang/IFn
   32:    aload_2
   33:    invokeinterface    #75,  2; //InterfaceMethod clojure/lang/IFn.invoke:(Ljava/lang/Object;)Ljava/lang/Object;
   38:    astore_2
   39:    astore_1
   40:    goto    0
   43:    areturn

The tail call has been turned into a goto allowing the method to execute in constant stack space.
user=> (test.foo/checkEven 1)
false
user=> (test.foo/checkEven 2)
true
user=> (test.foo/checkEven 3)
false
user=> (test.foo/checkEven 30000)
true

The recur form can be used to tail call into the nearest lexical function, and is also used by the loop special form to allow looping with regard to a set of local bindings. Hence the following is much like a call to the above function with an argument of 31.
(let [x 31]
  (loop [y 0 status true]
     (if (= x y)
        status
      (recur (+ y 1) (not status)))))

Which compiles to the code
public java.lang.Object invoke()   throws java.lang.Exception;
  Code:
   0:    getstatic    #39; //Field const__1:Ljava/lang/Object;
   3:    astore_1
   4:    getstatic    #45; //Field const__3:Ljava/lang/Object;
   7:    astore_2
   8:    getstatic    #72; //Field java/lang/Boolean.TRUE:Ljava/lang/Boolean;
   11:    astore_3
   12:    aload_1
   13:    aload_2
   14:    invokestatic    #78; //Method clojure/lang/Util.equiv:(Ljava/lang/Object;Ljava/lang/Object;)Z
   17:    ifeq    25
   20:    aload_3
   21:    goto    52
   24:    pop
   25:    aload_2
   26:    getstatic    #55; //Field const__6:Ljava/lang/Object;
   29:    invokestatic    #84; //Method clojure/lang/Numbers.add:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Number;
   32:    getstatic    #59; //Field const__7:Lclojure/lang/Var;
   35:    invokevirtual    #87; //Method clojure/lang/Var.get:()Ljava/lang/Object;
   38:    checkcast    #89; //class clojure/lang/IFn
   41:    aload_3
   42:    invokeinterface    #92,  2; //InterfaceMethod clojure/lang/IFn.invoke:(Ljava/lang/Object;)Ljava/lang/Object;
   47:    astore_3
   48:    astore_2
   49:    goto    12
   52:    areturn

So we’ve seen a couple of methods for dealing with functions that are self recursive, and that we can use a looping construct instead of defining a function. However, we haven’t seen how to get a couple of mutually recursive functions to execute in constant stack space. Clojure offers the trampoline function for doing this.
(defn trampoline
  "trampoline can be used to convert algorithms requiring mutual
  recursion without stack consumption. Calls f with supplied args, if
  any. If f returns a fn, calls that fn with no arguments, and
  continues to repeat, until the return value is not a fn, then
  returns that non-fn value. Note that if you want to return a fn as a
  final value, you must wrap it in some data structure and unpack it
  after trampoline returns."
  ([f]
     (let [ret (f)]
       (if (fn? ret)
         (recur ret)
         ret)))
  ([f & args]
     (trampoline #(apply f args))))

The idea behind trampoline is that we have a single function sitting on the stack. This calls another function which either returns a value, in which case this value is returned, or a function is returned, in which case the function is called. This is a typical implementation technique in languages that compile via CPS transformations.

We could take an example of mutually recursive functions,
(defn checkEven [x]
  (letfn [(step-even [x]
            (if (= x 0)
               true
             (step-odd (- x 1))))
          (step-odd [x]
            (if (= x 0)
               false
             (step-even (- x 1))))]
    (step-even x)))

user=> (checkEven 10)
true
user=> (checkEven 11)
false
user=> (checkEven 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

and transform it into the following which doesn’t cause stack overflow.
(defn checkEven [x]
  (letfn [(step-even [x]
            (if (= x 0)
               true
             #(step-odd (- x 1))))
          (step-odd [x]
            (if (= x 0)
               false
             #(step-even (- x 1))))]
    (trampoline step-even x)))

user=> (checkEven 10)
true
user=> (checkEven 11)
false
user=> (checkEven 10000)
true

One could imagine the compiler automatically doing the transformation to use recur, though it would make the compiler more complicated and would change the semantics of the program – the self call couldn’t be intercepted using a binding of the var corresponding to the function. trampoline is a very nice mechanism with many uses, and the tidy way of defining anonymous functions in Clojure using the # reader macro makes it easy to use it for optimising mutually recursive functions.

Advertisements
This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s