Questions tagged [tailrecursion-modulo-cons]

Tail recursion modulo cons is similar to ordinary tail-recursion, except that the recursive call is made inside a tail call to a data cons tructor.

It was introduced by David H. D. Warren in the context of compilation of Prolog in 1980. It was described (though not named so) by Daniel P. Friedman and David S. Wise in 1974 as a LISP compilation technique.

If we first make the recursive call to find out its result, and only then create the data record to be returned holding that recursive result (as well as some additional, "local" data in other fields), the overall call is not tail. It would be tail, if not for the cons truction of that data record to be returned as the overall result.

Instead, that data record can be cons tructed (i.e. allocated and have all its local data fields filled) before the recursive call is made which fills the remaining slot.

This recursive call thus becomes actual tail call, open to tail call optimization.

In terms of e.g. lists this means building them in top-down manner, having the recursion extend the list's tail, as opposed to the bottom-up order where the recursive call builds the whole tail first and only then the head element is prepended to it, as in regular recursion.

It is thus closely related to co recursion, and to the "tail recursion with accumulator" technique, which itself is closely related to monoidal types of values where

   A + (B + (C + (D + (....))))  ==   (A + B) + (C + (D + (....)))
                                 ==  ((A + B) + C) + (D + (....))
                                 ==  ....

The prototypical example is list_copy in Prolog:

list_copy( [], [] ).
list_copy( [A|B], [A|C] ) :- list_copy( B, C ).

This is the consequence of rule's head being instantiated before its body is entered. The tail nature of the call becomes even clearer when re-written with explicit unifications,

list_copy( X, Y ) :- 
    X=[], Y=[]
    ;   %% (* OR *)
    X=[A|B], Y=[H|C], H=A, list_copy( B, C ).

See also:

• Technical Report TR19: Unwinding Structured Recursions into Iterations.
  Daniel P. Friedman and David S. Wise (Dec 1974) _{(webarchived copy).}
• D. H. D. Warren, DAI Research Report 141, University of Edinburgh, 1980.
• Tail Recursion Modulo Context — An Equational Approach, Microsoft Research 2022.
• Tail mod cons in OCaml (search for "tail_mod_cons" on SO).
• TRMC in Elm.