Tail Call - Tail Recursion Modulo Cons

Tail recursion modulo cons is a generalization of tail recursion optimization introduced by David H. D. Warren in the context of compilation of Prolog, seen as an explicitly set-once language. As the name suggests, it applies when the only operation left to perform after a recursive call is to prepend a known value in front of a list returned from it (or to perform a constant number of simple data-constructing operations in general), which would thus be tail call save for the said cons operation. But prefixing a value at the start of a list on exit from a recursive call is the same as appending this value at the end of the growing list on entry into the recursive call, thus building the list as a side effect, as if in an implicit accumulator parameter. The following Prolog fragment illustrates the concept:

partition(, _, ). % -- Haskell translation: partition(, Pivot, Bigs) :- % partition _ = (,) X @< Pivot, !, % partition (x:xs) p | x < p = (x:a,b) partition(Xs, Pivot, Rest, Bigs). % | True = (a,x:b) partition(, Pivot, Smalls, ) :- % where partition(Xs, Pivot, Smalls, Rest). % (a,b) = partition xs p % to be compiled not as this: % but as this: partition(, _, ). partition(, _, ). partition(, Pivot, Smalls, Bigs) :- partition(, Pivot, Smalls, Bigs) :- ( X @< Pivot ( X @< Pivot -> partition(Xs,Pivot,Rest,Bigs),Smalls= -> Smalls=,partition(Xs,Pivot,Rest,Bigs) ; partition(Xs,Pivot,Smalls,Rest),Bigs= ; Bigs=,partition(Xs,Pivot,Smalls,Rest) ). ).

Thus such a call is transformed into creating a new list node, setting its first field, and then making a tail call which is also passed a pointer to where its result should be written (here, the node's rest field).

As another example, consider a function in C language that duplicates a linked list:

list *duplicate(const list *input) { list *head; if (input != NULL) { head = malloc(sizeof *head); head->value = input->value; head->next = duplicate(input->next); } else { head = NULL; } return head; }

In this form the function is not tail-recursive, because control returns to the caller after the recursive call duplicates the rest of input list. Even though it actually allocates the head node prior to duplicating the rest, the caller still has to plug in the result from the callee into the next field. So the function is almost tail-recursive. Warren's method gives the following purely tail-recursive implementation which passes the head node to the callee to have its next field set by it:

list *duplicate(const list *input) { list head; duplicate_aux(input, &head); return head.next; } void duplicate_aux(const list *input, list *end) { if (input != NULL) { end->next = malloc(sizeof *end); end->next->value = input->value; duplicate_aux(input->next, end->next); } else { end->next = NULL; } }

Note how the callee now appends to the end of the list, rather than have the caller prepend to the beginning. Characteristically for this technique, a parent frame is created here in the execution call stack, which calls (non-tail-recursively) into the tail-recursive callee which could reuse its call frame if the tail-call optimization were present in C, thus defining an iterative computation.

This properly tail-recursive implementation can be converted into explicitly iterative form:

list *duplicate(const list *input) { list head, *end; for ( end = &head; input != NULL; input = input->next, end = end->next ) { end->next = malloc(sizeof *end); end->next->value = input->value; } end->next = NULL; return head.next; }