21 juli 2015

PROPER TAIL CALLS

development
javascript

The process of one function calling another may end up creating a new stack frame, if the first function returns a result to the second.

function factorial(n) {
  function recur(n, acc) {
    if (n === 0) {
      return acc;
    } else {
      return recur(n - 1, n * acc);
    }
  }
  return recur(n, 1);
}

factorial(100000);

After factorial calls recur, it has nothing else to do. In such situations, the program does not need to return to the calling function when the called function ends. Therefore, after the tail call, the program does not need to keep any information about the calling function in the stack. ES6 takes advantage of this fact and actually do not use any extra stack space when doing a tail call. We say that those implementations support proper tail calls (PTC).

Tail call & tail-recursive

In computer science, a tail call is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive, which is a special case of recursion.

Wikipedia ::

Because a proper tail call uses no stack space, there is no limit on the number of "nested" tail calls that a program can make. For instance, we can call the following function with any number as argument; it will never overflow the stack:

function foo(n) {
  if (n > 0) {
    return foo(n - 1);
  }
}

What qualifies to be a tail call?

A subtle point when we use proper tail calls is what is a tail call. Some obvious candidates fail the criteria that the calling function has nothing to do after the call. For instance, in the following code, the call to bar is not a tail call:

function foo(n) {
  bar(n);
  return;
}

The problem in that example is that, after calling bar, foo still has to discard occasional results from bar before returning. Similarly, all the following calls fail the criteria:

return bar(n) + 1; // must do the addition
return n || bar(n); // must adjust to 1 result
return n && bar(n); // must adjust to 1 result

Here is another scenario:

function sum(...values) {
  return values.shift() + sum(...values);
}

In the above scenario + operation is executed after the recursive call, which disqualifies it to be a proper tail call (PTC).

To change the above function to make a proper tail call, introduce a helper function with an accumulator parameter.

function sum(...values) {
  function sumTo(acc, values) {
    return sumTo(acc + values.shift(), values); // tail-recursive call
  }
  return sumTo(0, values);
}

Currying

Calling a function within a function with different parameters is called currying.

Without proper tail calls, each user move would create a new stack level. After some number of moves, there would be a stack overflow. With proper tail calls, there is no limit to the number of moves that a user can make, because each move actually performs a goto to another function, not a conventional call.