Tail call Blog Post

self-tail-call-opt.md

A common misconception about functional languages is that they are slow, and that function calls is inherently slow compared to looping. However, most functional languages, and now Elm, provide a way for you to write loops: tail-recursion.

What is a Tail Call?

When you define a function, you will usually call other functions to build a return value. But sometimes, you directly return the value returned by another function. This is called a tail call.

Specifically, a an expression is in tail position if it is the body of the function, or if it is in tail position of the result of an if or case statement that is in tail position. Function calls made to calculate argument parameters, or used in the right-hand side of a let declaration, are not in tail position.

Consider the following code for Maybe.oneOf, in the core libraries:

oneOf : List (Maybe a) -> Maybe a
oneOf maybes =
  case maybes of
    [] ->
        Nothing
    maybe :: rest ->
        case maybe of
          Nothing -> oneOf rest
          Just _ -> maybe

Here, the recursive call oneOf rest is in tail position: it's the body of the branch of a case statement, which is the body of the branch of a case statement, which is the body of the function.

How to Write Tail Recursive Code?

Usually, a recursive function can be translated into a tail-recursive function by adding an extra argument, called an accumulator.

Let's consider summing all the elements in a list. The naive way to write this is as follows:

sum : List Int -> Int
sum myList =
  case myList of
    [] -> 0
    
    x :: xs ->
      x + (sum xs) 

Normally when you write a recursive function, you find the results for the smallest (base) case, and you find the relationship between a complex case and its sub-cases. Here: the sum of an empty list is 0, and the sum of a list head and a tail is found by adding the head to the sum of the tail.

The key to writing tail-recursive code is adding the accumulator, the parameter representing the "results so far". We accumulate information as we take apart our data (thus the name), processing each part until we've built up our final value.

To write our sum function using tail-recursion, we make the following changes:

• We add a helper function, which is recursive
• We add an extra argument to the helper, the accumulator
• The return value of the base case becomes the initial value for the accumulator
• The base-case of our helper function returns the accumulator
• The recursive case just calls the function itself, with smaller arguments, and the accumulator updated.
• The main function just calls the helper with the proper initial value

We would rewrite our sum function as follows:

tailSum : List Int -> Int
tailSum myList = 
  let
    helper l accum =
      case l of
        [] -> accum

        x :: xs -> helper xs (x + accum)
  in 
    helper myList 0

Notice what we've done here:

• The base case of 0 for an empty list now becomes the initial value to our helper
• The accumulator argument stores the sum of all the elements we've seen so far
• For the helper's base case (empty list), we simply return the accumulator, since it contains the sum of all the elements we've seen
• For the helper's recursive case, we update the accumulator (sum of values we've seen so far) to include the new element x, and gives the tail of the list as the next value to be processed.
• Our sum function just calls the helper with the argument, as well as the initial accumulator value.

Not all functions can be written in this form, but many can, and it's the best practice to write them like this to avoid stack overflows when possible.

Accumulators aren't always necessary. In Maybe.oneOf, we don't need an accumulator, because we look at each element in a list, and either instantly return (if it is a Just value), or forget about it (if it is a Nothing). If we needed to remember things about what we'd seen in the list, for example, the number of Nothing elements we'd passed over, we would need an accumulator parameter to store that information.

What does the JavaScript Output Look Like?

When you write a program with self-tail-recursion (i.e. a function calling itself using tail-recursion), Elm can translate it into a while loop. The tail call is simply translated into assigning new values for the arguments, with a jump to the top of the loop.

Here's what the JS output for the Maybe.oneOf function above looks like:

   var oneOf = function (maybes) {
      while (true) {
         oneOf: {
            switch (maybes.ctor)
            {case "::": {
                    switch (maybes._0.ctor)
                    {case "Just": return maybes._0;
                       case "Nothing":
                       var _Temp0 = maybes._1;
                         maybes = _Temp0;
                         break oneOf;}
                    _U.badCase($moduleName,
                    "between lines 64 and 66");
                 }
               case "[]": return Nothing;}
            _U.badCase($moduleName,
            "between lines 59 and 66");
         }
      }
   };

As you can see, we now loop through the whole list without performing any function calls.

The main performance improvements we've noticed here are with dictionaries. You can now have a dictionary with hundreds of thousands of elements, and folding over, or looking up, a value in the dictionary is done using tail recursion. This is much faster, and avoids the "too much recursion" errors previous code had.

Limitations?

Most functional languages support the optimization we've described for any tail call, not just for self-tail-calls. However, we're holding back on this for a number of reasons:

• JavaScript has no goto statement, meaning there would be a lot of overhead in order to make code that supports this.
• The next JS Standard, ECMAScript 6, requires that browsers optimize tail-calls. So eventually browsers will do this optimization for us.
• There is already a trampoline library for people who really really need this feature.

The link to the trampoline library directs to this page instead.