From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id EA917BB81 for ; Fri, 2 Dec 2005 16:18:02 +0100 (CET) Received: from ext.lri.fr (ext.lri.fr [129.175.15.4]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jB2FI2CW005971 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Fri, 2 Dec 2005 16:18:02 +0100 Received: from smtp.lri.fr (serveur3-5 [129.175.3.5]) by ext.lri.fr (Postfix) with ESMTP id 6A0D9202424; Fri, 2 Dec 2005 16:18:02 +0100 (CET) Received: from pc9-152 (pc9-152 [129.175.9.152]) by smtp.lri.fr (Postfix) with ESMTP id 6D54BCED98; Fri, 2 Dec 2005 16:18:01 +0100 (CET) Received: from filliatr by pc9-152 with local (Exim 3.36 #1 (Debian)) id 1EiCfD-00018q-00; Fri, 02 Dec 2005 16:17:31 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <17296.25990.261724.744405@gargle.gargle.HOWL> Date: Fri, 2 Dec 2005 16:17:26 +0100 To: Erik de Castro Lopo Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Reporting on sucess/failure of tail recursion In-Reply-To: <20051202211627.128cbfc5.ocaml-erikd@mega-nerd.com> References: <20051202200957.2fb14d49.ocaml-erikd@mega-nerd.com> <55541.132.166.133.216.1133515788.squirrel@panel.lost-oasis.net> <20051202211627.128cbfc5.ocaml-erikd@mega-nerd.com> X-Mailer: VM 7.19 under Emacs 21.4.1 From: Jean-Christophe Filliatre X-Virus-Scanned: by amavisd-new at lri.fr X-Miltered: at nez-perce with ID 439065AA.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 recursion:01 filliatre:01 filliatr:01 lri:01 recursive:01 recursive:01 basile:01 rec:01 node:01 filliatre:01 lri:01 filliatr:01 writes:01 tail:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 Erik de Castro Lopo writes: > with a no-recursive outer function and a tail recursive inner function. > It would still be nice to know if the inner function is tail recursive. As already explained by Basile, the right notion is that of "tail call" not of "tail recursive function" (you can define it as "all recursive calls are tail calls", but it is less precise). For instance, the following function let rec fold f s accu = match s with Empty -> accu | Node(l, v, r, _) -> fold f r (f v (fold f l accu)) has two recursive calls, one which is not a tail call (fold f l accu) and one which is (fold f r ...) Being warned of non-tail calls may be useful in some situations, but I guess the issue is often the call to a library function that is not tail recursive. That's why you need the documentation to be explicit about that... -- Jean-Christophe Filliātre (http://www.lri.fr/~filliatr)