Basic Theory and Practice

Juicy does not support explicit iteration.

Explicit iteration is not necessary. For many languages, explicit iteration is necessary because recursion has an inherent memory overhead. For many uses of recursion, there need not be an overhead associated with this recursion, because it can be removed with tail call elimination.

Juicy does tail call elimination. As such there is no memory overhead
associated with many uses of recursion.

Not all forms of recursion are amenable to this optimization. If a recursive call is used to generate the value returned from a function then the current stack frame does not need to be preserved for further computation and thus the function called can return directly into the function that called the returning function.

This should be much clearer with an example.

Line numbers have been added for clarity.

1 factorial(n) {
2   if n == 0 {
3     return 1;
4   }
5   return n*factorial(n-1);
6 }

This program is a typical recursive implementation of factorial.

The recursive call on line 5 is of particular interest. In this program, when the factorial call is made, the value must be returned to the calling function so that it can multiply it by n before returning the result to its caller.

Because the value n must be remembered at each level of recursion, the memory used grows with the depth of recursion needed.

To make a version of this program that can be optimized, we must not need to remember anything from the calling context to do after the call.

Here I will implement an example that can be optimized.

factorialTail(n,accumulator) {
  if (n == 0) {
    return accumulator;
  }
  return factorialTail(n-1,n*accumulator);
}

You may notice that this function must also be called differently, with an accumulator of 1 as shown here. This would find the factorial of 7.

factorialTail(7,1);

We can create a wrapper around factorial tail to not have to write the accumulator on each use.

factorial(n) = factorialTail(n,1);

As a general rule, if you want tail recursion, then your recursion should be of the form:

func(arg) {
...
  return func(...);
...
}

The important part if that whenever the form return FOO(...args...) is seen, the call to FOO is optimized into a tail call. A call need not be recursive to be optimized, but that is often where it is most important.

Debugging

Some languages, such as Python, purposefully don't support tail recursion. They do this because not preserving the stack from of the caller necessarily makes it no longer possible for a debugger to track all calls through these frames.

Juicy currently does not produce assembly with debugging annotations. When this functionality is added, a --debug compile option will also be added. This option will not only add the annotations, but will also turn off tail call optimization so that debugging will not be impeded.