Re: Récursivité terminale

[Chung-chieh Shan <ccshan@post.harvard.edu>]

(So that's how you say "tail-recursive" in French...)

Xavier Leroy <Xavier.Leroy@inria.fr> wrote in article <49CB9854.1020707@inria.fr> 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, List.map 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 "List.map 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
numbers.

-- 
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
100 Days to close Guantanamo and end torture http://100dayscampaign.org/
http://www.avaaz.org/en/end_the_war_on_terror/