Tail Call Optimization by Base Jumping off the Stack

Tail calls are the one technique of iteration in most useful languages. So implementation help is completely essential.

For instance, Scheme requires tail name optimization as a part of its language specification (PDF):

3.5 Correct tail recursion

Implementations of Scheme are required to be correctly tail-recursive. A Scheme implementation is correctly tail-recursive if it helps an unbounded variety of lively tail calls. A name is lively if the referred to as process would possibly nonetheless return.

Over time numerous options have been developed to satisfy this requirement akin to trampolines, goto‘s, compiler optimizations, and so on. Some of the uncommon was proposed by Henry Baker in his paper CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A. (PDF).

Cheney on the M.T.A. requires writing a compiler and runtime. Code is transformed into continuation passing type and compiled right into a sequence of C features. When this system runs these features are referred to as like regular C features however they by no means return. The stack retains rising and rising…

This system periodically checks to see if a stack dimension restrict is reached. When that occurs a Cheney copying garbage collector is used to repeat dwell information from the stack to the heap. As soon as all of the dwell objects on the stack are copied this system calls longjmp to return to the underside of the stack, calls into the following operate, and maintain going.

A technique to think about that is that as a substitute of utilizing a trampoline we’re going to BASE bounce off the stack once in a while:

On the one hand that is type of insane 😮. Applications should not alleged to work this fashion!

Then once more, recursive calls are assured to by no means trigger a stack overflow as a result of every part is periodically cleared from the stack. Thus Cheney on the M.T.A ensures tail name optimization.

In truth this strategy offers all of the “exhausting” stuff {that a} useful programming language runtime wants – tail name optimization, generational rubbish assortment, and continuations.

Listed below are code examples from Cyclone Scheme demonstrating how Cheney on the M.T.A works in follow.

Cyclone’s runtime makes use of the next operate to arrange a brand new trampoline. The underside of the stack is explicitly marked utilizing setjmp. After a rubbish assortment code will resume execution on the following line after setjmp. At that time the code finds the following operate – gc->cont, our continuation – and calls into it:

void Cyc_start_trampoline(gc_thread_data * thd)
{
  // Tank, load the bounce program
  setjmp(*(thd->jmp_start));

  if (obj_is_not_closure(thd->gc_cont)) {
    Cyc_apply_from_buf(thd, thd->gc_num_args, thd->gc_cont, thd->gc_args);
  } else {
    closure clo = thd->gc_cont;
   (clo->fn)(thd, clo, thd->gc_num_args, thd->gc_args);
  }

  fprintf(stderr, "Inner error: ought to by no means have reached this linen");
  exit(1);
}

The snippet under demonstrates how C features could also be written utilizing Baker’s strategy. All compiler-generated and primitive features that decision into different features have to be written on this type:

object Cyc_make_vector(object cont, object len, object fill) {
  object v = NULL;
  int i;
  Cyc_check_int(len);

  // Reminiscence for vector could be allotted immediately on the stack
  v = alloca(sizeof(vector_type));

  // Populate vector object
  ((vector)v)->tag = vector_tag;
  ... 

  // Verify if GC is required, then name into
  // continuation with the brand new vector
  return_closcall1(cont, v);
}

A macro return_closcall1 is used to examine if the stack restrict has been reached – if that’s the case a minor assortment is triggered by way of GC(). In any other case one other macro closcall1 is used to name into the following operate:

#outline return_closcall1(td, clo, a1) {
 char prime;
 object buf[1]; buf[0] = a1;
 if (stack_overflow(&prime, (((gc_thread_data *)information)->stack_limit))) {
     GC(td, clo, buf, 1);
     return; // By no means reached
 } else {
     closcall1(td, (closure) (clo), buf);                                      
     return; // By no means reached
 }
}

And right here is GC, the wrapper for Cyclone’s minor rubbish collector. The code retrieves places of the highest/backside of the stack, calls into gc_minor to gather objects utilizing Cheney’s algorithm, and the calls longjmp to base bounce again to the beginning of the trampoline:

void GC(void *information, closure cont, object * args, int num_args)
{
  char tmp;
  object low_limit = &tmp;      // That is one finish of the stack...
  object high_limit = ((gc_thread_data *) information)->stack_start;

  int alloci = gc_minor(information, low_limit, high_limit, cont, args, num_args);
  ...

  // Let all of it go, Neo...
  longjmp(*(((gc_thread_data *) information)->jmp_start), 1);
}

There may be sufficient happening it gc_minor that it’s exterior the scope of this text. However the code is offered on GitHub in case you are curious.

That is all for now. Thanks for studying! 🎉