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=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 724C8BC0A for ; Sat, 19 May 2007 14:58:41 +0200 (CEST) Received: from ipmail01.adl2.internode.on.net (ipmail01.adl2.internode.on.net [203.16.214.140]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l4JCwcSQ021168 for ; Sat, 19 May 2007 14:58:40 +0200 X-IronPort-AV: E=Sophos;i="4.14,556,1170595800"; d="scan'208";a="131134942" Received: from ppp59-172.lns2.syd6.internode.on.net (HELO [192.168.1.201]) ([121.44.59.172]) by ipmail01.adl2.internode.on.net with ESMTP; 19 May 2007 22:28:36 +0930 Subject: Re: [Caml-list] tail rec From: skaller To: Basile STARYNKEVITCH Cc: caml-list@inria.fr In-Reply-To: <464E8B1B.7080800@starynkevitch.net> References: <1179543365.26755.33.camel@rosella.wigram> <464E8B1B.7080800@starynkevitch.net> Content-Type: text/plain Date: Sat, 19 May 2007 22:58:32 +1000 Message-Id: <1179579512.18119.36.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.10.1 Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 464EF47F.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; 0200,:01 basile:01 compiler:01 compiler:01 recursive:01 factorial:01 implements:01 ocaml:01 recursion:01 basile:01 angles:98 sourceforge:01 wrote:01 wrote:01 rec:01 On Sat, 2007-05-19 at 07:28 +0200, Basile STARYNKEVITCH wrote: > skaller wrote: > > I have a silly idea. Introduce a new construction: > > > > let tailrec f .. > > > > This is the same as let rec except it checks every direct call to f > > is in tail position (and bombs out the compiler if not). > > > While I also want a similar construct or help, I believe your proposal > is wrong. What would be needed is a tailrec operator keyword that makes > the compiler check that a given call is in tail position. It is not a > function which is tail recursive, it is a call which is. > > In that way, the classical factorial does not have any tail call, so > > let rec fact n = if n <= 0 then 1 else n * tailrec fact (n - 1) Felix actually implements this for procedure calls: instead of f x; or call f x; you can write: jump f x; In that context, it is not a compiler *check* but sugar for call f x; return; which forces the call to be tail. This is only for procedure calls though, not function applications. For Ocaml, it would seem your suggestion should use the keyword 'return': let rec fact n = if n <= 0 then 1 else n * return fact (n-1) is pretty obviously an error, and a C/C++ programmer would understand this. The problem with your idea is that it doesn't allow the programmer to do this: let rec fact n = .... Hum. Is this tail rec? I'm a GOOD programmer => I'm LAZY. With my suggestion I could just write: let tailrec fact n = .. to check a claim that 'fact' isn't gratuitously non-tail rec. The point is, I'm trying to establish a property of the function implementation: ALL direct recursion is tailed. In a longer chain of let rec .. and .. and this is only a single keyword change. Your suggestion would require writing 'tailrec' or 'return' in advance for every call .. and no GOOD programmer would do that because good programmers are lazy. It would be the other way. First you write let tailrec .... and now you get an error because there is a real and essential non-tail call .. so you annotated that call: else x::(f y) is an error because f isn't tailed but this is right so: else x::(rec f y) has to be written to disable the check on that f. In fact, I could go a step further and suggest ALL let rec should be forced to be tailrec, so the ONLY way to do a non tail call is write rec f y The compiler then issues a warning when 'rec' is used but the call actually is in tail position. Unfortunately this breaks existing code so it would have to be enabled by a compiler switch. In summary then: what you (Basile) suggest is technically sound, and could ALSO be implemented! However the two features address the same issue from opposite angles. My proposal assures a whole function or list of function is directly tail rec, whereas yours is extremely local and checks individual explicitly annotated calls. So from a software engineering/development viewpoint they have quite different utility .. and they're not exclusive! -- John Skaller Felix, successor to C++: http://felix.sf.net