Editing Tail call (section)

==Tail recursion modulo cons==
'''Tail recursion modulo cons''' is a generalization of tail-recursion optimization introduced by [[David H. D. Warren]]<ref>D. H. D. Warren, ''DAI Research Report 141'', University of Edinburgh, 1980.</ref> in the context of [[compiler|compilation]] of [[Prolog]], seen as an ''explicitly'' [[Single assignment#Single assignment|''set once'']] language. It was described (though not named) by [[Daniel P. Friedman]] and [[David S. Wise]] in 1974<ref>Daniel P. Friedman and David S. Wise, [http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR19 ''Technical Report TR19: Unwinding Structured Recursions into Iterations''], Indiana University, Dec. 1974. PDF available [https://legacy.cs.indiana.edu/ftp/techreports/TR19.pdf ''here''] (webarchived copy [https://web.archive.org/web/20221023082940/https://legacy.cs.indiana.edu/ftp/techreports/TR19.pdf ''here'']).</ref> as a [[LISP]] compilation technique. 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 the list returned from it (or to perform a constant number of simple data-constructing operations, in general). This call would thus be a ''tail call'' save for ("[[modulo (jargon)|modulo]]") 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 (computer science)|side effect]], as if in an implicit accumulator parameter. The following Prolog fragment illustrates the concept:

===Example code===
{|
|-
|<syntaxhighlight lang="prolog">
% Prolog, tail recursive modulo cons:
partition([], _, [], []).
partition([X|Xs], Pivot, [X|Rest], Bigs) :-
  X @< Pivot, !,
  partition(Xs, Pivot, Rest, Bigs).
partition([X|Xs], Pivot, Smalls, [X|Rest]) :-
  partition(Xs, Pivot, Smalls, Rest).
</syntaxhighlight>
|<syntaxhighlight lang="haskell">
-- In Haskell, guarded recursion:
partition [] _ = ([],[])
partition (x:xs) p 
        | x < p     = (x:a,b)
        | otherwise = (a,x:b)
   where
      (a,b) = partition xs p

</syntaxhighlight>
|-
|<syntaxhighlight lang="prolog">
% Prolog, with explicit unifications:
%     non-tail recursive translation:
partition([], _, [], []).
partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs],
 (  X @< Pivot
 -> partition(Xs,Pivot,Rest,Bigs), Smalls=[X|Rest]
 ;  partition(Xs,Pivot,Smalls,Rest), Bigs=[X|Rest]
 ).
</syntaxhighlight>
|<syntaxhighlight lang="prolog">
% Prolog, with explicit unifications:
%     tail-recursive translation:
partition([], _, [], []).
partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs],
 (  X @< Pivot
 -> Smalls=[X|Rest], partition(Xs,Pivot,Rest,Bigs)
 ;  Bigs=[X|Rest], partition(Xs,Pivot,Smalls,Rest)
 ).

</syntaxhighlight>
|}

Thus in tail-recursive translation such a call is transformed into first creating a new [[Node (computer science)|list node]] and setting its <code>first</code> field, and ''then'' making the tail call with the pointer to the node's <code>rest</code> field as argument, to be filled recursively. The same effect is achieved when the recursion is ''guarded'' under a lazily evaluated data constructor, which is automatically achieved in lazy programming languages like Haskell.

===C example===
The following fragment defines a recursive function in [[C (programming language)|C]] that duplicates a linked list (with some equivalent Scheme and Prolog code as comments, for comparison):
{|
|-valign="top"
|rowspan="2"|
<syntaxhighlight lang="c">
typedef struct list {
    void *value;
    struct list *next;
} list;

list *duplicate(const list *ls)
{
    list *head = NULL;

    if (ls != NULL) {
        list *p = duplicate(ls->next);
        head = malloc(sizeof *head);
        head->value = ls->value;
        head->next = p;
    }
    return head;
}
</syntaxhighlight>
|<syntaxhighlight lang="scheme">
;; in Scheme,
(define (duplicate ls)
  (if (not (null? ls))
    (cons (car ls)
          (duplicate (cdr ls)))
    '()))
</syntaxhighlight>
|-
|<syntaxhighlight lang="prolog">
%% in Prolog,
duplicate([X|Xs],R):-
  duplicate(Xs,Ys),
  R=[X|Ys].
duplicate([],[]).
</syntaxhighlight>
|}

In this form the function is not tail recursive, because control returns to the caller after the recursive call duplicates the rest of the input list. Even if it were to allocate the ''head'' node before duplicating the rest, it would still need to plug in the result of the recursive call into the <code>next</code> field ''after'' the call.{{efn|Like this:
<syntaxhighlight lang="c">
if (ls != NULL) {
  head = malloc( sizeof *head);
  head->value = ls->value;
  head->next = duplicate( ls->next);
}</syntaxhighlight>
}}
So the function is ''almost'' tail recursive. Warren's method pushes the responsibility of filling the <code>next</code> field into the recursive call itself, which thus becomes tail call.{{efn|Like this:
<syntaxhighlight lang="c">
if (ls != NULL) {
  head = malloc( sizeof *head);
  head->value = ls->value;
  duplicate( ls->next, &(head->next));
}</syntaxhighlight>
}} Using  sentinel head node to simplify the code, 

{|
|-valign="top"
|rowspan="2"|
<syntaxhighlight lang="c">
typedef struct list {
    void *value;
    struct list *next;
} list;
void duplicate_aux(const list *ls, list *end);

list *duplicate(const list *ls)
{  
    list head;

    duplicate_aux(ls, &head);
    return head.next;
}

void duplicate_aux(const list *ls, list *end)
{
    if (ls != NULL) {
        end->next = malloc(sizeof *end);
        end->next->value = ls->value;
        duplicate_aux(ls->next, end->next);
    } else {
        end->next = NULL;
    }
}
</syntaxhighlight>
|<syntaxhighlight lang="scheme">
;; in Scheme,
(define (duplicate ls)
  (let ((head (list 1)))
    (let dup ((ls  ls)
              (end head))
      (cond
        ((not (null? ls))
         (set-cdr! end (list (car ls)))
         (dup (cdr ls) (cdr end)))))
    (cdr head)))
</syntaxhighlight>
|-
|<syntaxhighlight lang="prolog">
%% in Prolog,
duplicate([X|Xs],R):-
   R=[X|Ys],
   duplicate(Xs,Ys).
duplicate([],[]).
</syntaxhighlight>
|}

The callee now appends to the end of the growing list, rather than have the caller prepend to the beginning of the returned list. The work is now done on the way ''forward'' from the list's start, ''before'' the recursive call which then proceeds further, instead of ''backward'' from the list's end, ''after'' the recursive call has returned its result. It is thus similar to the accumulating parameter technique, turning a recursive computation into an iterative one.

Characteristically for this technique, a parent [[call frame|frame]] is created on the execution call stack, which the tail-recursive callee can reuse as its own call frame if the tail-call optimization is present.

The tail-recursive implementation can now be converted into an explicitly iterative implementation, as an accumulating [[Loop (computing)#Loops|loop]]:
{|
|-valign="top"
|rowspan="2"|
<syntaxhighlight lang="c">
typedef struct list {
    void *value;
    struct list *next;
} list;

list *duplicate(const list *ls)
{
    list head, *end;
    end = &head;
    while (ls != NULL)
    {
        end->next        = malloc(sizeof *end);
        end->next->value = ls->value;
        ls = ls->next;
        end = end->next;
    }
    end->next = NULL;
    return head.next;
}
</syntaxhighlight>
|<syntaxhighlight lang="scheme">
 ;; in Scheme,
 (define (duplicate ls)
   (let ((head (list 1)))
     (do ((end head (cdr end))
          (ls  ls   (cdr ls )))
         ((null? ls) (cdr head))
       (set-cdr! end (list (car ls))))))
</syntaxhighlight>
|-
|<syntaxhighlight lang="prolog">
%% in Prolog,
%% N/A
</syntaxhighlight>
|}