How Erjang compiles tail recursion

Notice: I posted a blog entry on this subject here at my blog

For self-recursive functions, erlc does the work, so such functions are easy to turn into a loop. Tail-recursion for other functions are handled differently.

For each function, a java class is generated like you can see below, in this case the function appmon_info:start_link/3. When calling the function in tail-position, it will be called using

return appmon_info.start_link.invoke_tail(proc, arg1, arg2, arg).

The method invoke_tail just saves the arguments inside the proc object, and returns the marker EProc.TAIL_MARKER, which will then always be returned to a context where there is a loop that knows what to do if that marker is returned.

This encoding of tail-recursion seems to be reasonably fast (I have done some performance measurements), and the trick is to not allocate a new object to stash those saved arguments into. The way erjang does it, the memory for those locations is likely to be in on-chip cache, and so it is surprisingly cheap to store into such memory locations (it’s also not congested, because only this thread accesses that process’ EProc object).

// class for the module (also contains other things not listed here)
class appmon_info extends EModule {
    static EFun3 start_link = new start_link();

   class start_link extends EFun3 {
        // normal method for invoking   appmon_info:start_link/3
        public EObject invoke(EProc eproc, EObject arg0, EObject arg1, EObject arg2)  {
            EObject tmp;
            tmp = start_link__3$body(eproc, arg0, arg1, arg2);
            while(tmp == EProc.TAIL_MARKER)
                tmp = eproc.tail.go(eproc);
            return tmp;
        }

       // used for invoking ditto in tail position
        public EObject invoke_tail(EProc eproc, EObject arg0, EObject arg1, EObject arg2) {
            eproc.arg0 = arg0;
            eproc.arg1 = arg1;
            eproc.arg2 = arg2;
            eproc.tail = this;
            return EProc.TAIL_MARKER;
        }

       // used to do one step in completing a tail-recursive call
        public EObject go(EProc eproc) {
            EObject arg0 = eproc.arg0;
            EObject arg1 = eproc.arg1;
            EObject arg2 = eproc.arg2;
            eproc.arg0 = null;
            eproc.arg1 = null;
            eproc.arg2 = null;
            eproc.tail = null;
            return start_link__3$body(eproc, arg0, arg1, arg2);
        }