From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.3 required=5.0 tests=SPF_FAIL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 03849BBAF for ; Fri, 27 Mar 2009 04:39:46 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvUAAOfny0lQW+UCe2dsb2JhbACWAAEBFiIErEuGRohNg3cG X-IronPort-AV: E=Sophos;i="4.38,430,1233529200"; d="scan'208";a="26421185" Received: from main.gmane.org (HELO ciao.gmane.org) ([80.91.229.2]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/AES256-SHA; 27 Mar 2009 04:39:45 +0100 Received: from list by ciao.gmane.org with local (Exim 4.43) id 1Ln2v0-00033t-9F for caml-list@inria.fr; Fri, 27 Mar 2009 03:39:42 +0000 Received: from user-160vtiu.cable.mindspring.com ([76.15.246.94]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 27 Mar 2009 03:39:42 +0000 Received: from ccshan by user-160vtiu.cable.mindspring.com with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 27 Mar 2009 03:39:42 +0000 X-Injected-Via-Gmane: http://gmane.org/ To: caml-list@inria.fr From: Chung-chieh Shan Subject: Re: =?ISO-8859-1?Q?R=E9cursivit=E9?= terminale Date: Thu, 26 Mar 2009 23:37:49 -0400 Message-ID: References: <20090326153839.8kzcsd6k0sg0csoc@webmail.u-strasbg.fr> <49CB9854.1020707@inria.fr> X-Complaints-To: usenet@ger.gmane.org X-Gmane-NNTP-Posting-Host: user-160vtiu.cable.mindspring.com User-Agent: tin/1.9.4-20090211 ("Rieclachan") (UNIX) (Linux/2.6.28 (i686)) Sender: news X-Spam: no; 0.00; terminale:01 gmane:01 arises:01 first-order:01 factorial:01 sig:01 terror:98 wrote:01 functions:01 caml:02 rewritten:02 essentially:02 parameter:02 parameter:02 cps:02 (So that's how you say "tail-recursive" in French...) Xavier Leroy 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/