One of the hallmarks of functional programming is the concept and adoption of recursion. Be it basic recursive functions, recursive data types or generalized recursion schemes; functional programmers like to use it everywhere. So important is recursion that the Scala compiler has a phase specifically to handle tail call transformations.
In this post, I'm going to introduce you to mutual tail recursion by way of the TwoTails compiler plugin. This plugin, now at version 0.3.0, adds support to Scala for tail call transformations on mutually recursive functions. It opens up the technique for general use without having to resort to Trampolines or risking StackOverflowErrors.
A Basic Example: Ping-Pong!
So before we get into the why or how, let's give a basic example of what mutual tail recursion looks like. Below is the classic "ping-pong" which was used to showcase Akka performance. Here, we're less concerned with performance and "messages" per second than we are with overflowing the call stack:
Like @tailrec but Different
Tail recursion works on a single function whose control path has a circular dependence with itself. Mutual tail recursion is more generalized; the circular dependency of each function call forms a directed cyclic graph with a closed walk and each recursive call is located at the tail position. You can think of @tailrec as a mutually recursive function call graph consisting of a single vertex.
All of that is a fancy way of saying if you start at "ping" and go to "pong" there exists a logical branch wherein you could wind back up in "ping," e.g. ping(3) in the example above satisfies this condition. It can also be described in graphical form. In the picture below, functions in the place "B," "C," "D," and "E" are mutually recursive; "A" and "F" are not. If all the calls of "B" through "E" are in tail position, TwoTails can transform them:
Example of a hypothetical dependency graph of function calls
Mutual Tail Recursion in Practice
Theoretically, any set of mutually recursive methods can be rewritten as a single recursive method. In practice, doing so adds at least one level of indirection and results in one very bloated method. Furthermore, code written to avoid mutual recursion where it should naturally exist becomes more difficult to predict control flow and harder to test due to increased cyclomatic complexity.
Said another way, recursion results in less code compared to stateful, iterative approaches. Mutual recursion builds upon this but organizes and groups code according to specific function resulting in smaller methods. More direct access to each algorithmic component yields more direct testing of logical branches. This in turns reduces bug counts and improves the ability of developers to maintain a living code base.
Such compelling virtues are a strong positive for mutual recursion but prior to TwoTails Scala did not natively support mutual tail call transformations at the compiler stage. Instead, code attempting to avoid stack overflows while retaining the such a structure had to be cast in terms of Continuation Passing Style or Trampolines. The additional artifacts required added to the cognitive overhead, increased boilerplate and leaked implementation details ("Zounds! These methods are recursive. Look at their return types.")
To witness and by way of contrasting the previous example, here is the same "ping-pong" code written in vanilla Scala using trampoline styled recursion:
Note, that every "loop" (an invocation of TailCalls.tailcall) creates a TailRec object, a thunk, and an anonymous function calling that thunk. For finishing touches but not required, two helper methods were added to preserve the same public interface and hide the implementation details that trampolines were used.
The Case for TwoTails
There is nothing wrong with going the trampolined route for handling mutually recursive algorithms. Indeed, for stack safe mutually recursive but not tail call recursive algorithms it is one of the only ways (assuming it can be structured with monadic bindings.) Given a choice, however, code devoid of trampolines is both simpler to read and more direct to write.
TwoTails allows for the expression of mutually tail recursive functions to be written directly in vanilla Scala with a familiar annotation approach; methods are prepended with @mutualrec (styled after @tailrec.). It does so without introducing or requiring additional data structures and adds no additional project library dependencies. In fact, being a compiler plugin (it adds a new phase prior to tailcalls) means that once code is compiled, no trace of TwoTails remains in the generated JAR files.
Version 0.3.0 of TwoTails has been officially released for Scala 2.11.8 with plans to support 2.12.0 in the near future. It has currently not been tested with other compiler plugins or macro based methods. Happily, it has been accepted into incubator status of TypeLevel and it is hoped it can move to full member status with enough adoption. What this means is that the project will continue to evolve, will actively look for people to use it and wants to hear about any reported issues.