Version française
Home     About     Download     Resources     Contact us    
Browse thread
Récursivité terminale
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Chung-chieh Shan <ccshan@p...>
Subject: Re: Récursivité terminale
(So that's how you say "tail-recursive" in French...)

Xavier Leroy <> wrote in article <> in gmane.comp.lang.caml.inria:
> A technique that always works is to convert your function to
> continuation-passing style.  The resulting code is hard to read and
> not particularly efficient, though.
> It is possible to do better in a number of specific cases.  Functions
> operating over lists can often be made tail-rec by adding an
> "accumulator" parameter and reversing the accumulator at the end.
> For instance, f l (not tail-rec) can be rewritten as
> List.rev (List.rev_map f l) (tail-rec).

In fact, it is always possible to do better in the sense above:
the accumulator parameter arises mechanically as the result of
defunctionalizing the continuation in a CPS program.  For example, if we
transform " f l (not tail-rec)" into CPS then defunctionalize
it, we get essentially "List.rev (List.rev_map f l) (tail-rec)".

Sometimes we can improve upon the first-order representation of
continuations chosen mechanically by defunctionalization.  The factorial
function is an example: defunctionalization represents a continuation
by a list of numbers, but we can replace the list by the product of the

Edit this signature at
100 Days to close Guantanamo and end torture