From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA10060; Sat, 1 May 2004 10:10:25 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA10174 for ; Sat, 1 May 2004 10:10:24 +0200 (MET DST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i418ALSH009370 for ; Sat, 1 May 2004 10:10:22 +0200 Received: from [192.168.1.200] (ppp116-155.lns1.syd2.internode.on.net [150.101.116.155]) by smtp3.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i418AIk2043358; Sat, 1 May 2004 17:40:19 +0930 (CST) Subject: Re: [Caml-list] List.rev From: skaller Reply-To: skaller@users.sourceforge.net To: William Lovas Cc: caml-list In-Reply-To: <20040501070844.GB19707@force.stwing.upenn.edu> References: <20040430175429.GB11118@online.fr> <4092A448.6080909@1969.ws> <1083376750.2581.183.camel@pelican.wigram> <1083388377.2581.383.camel@pelican.wigram> <20040501070844.GB19707@force.stwing.upenn.edu> Content-Type: text/plain Message-Id: <1083399017.20722.25.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 01 May 2004 18:10:18 +1000 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 40935B6D.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 sourceforge:01 2004:99 lovas:01 abnormally:01 suboptimal:01 tail-rec:01 9660:01 glebe:01 formed:98 nsw:01 snail:02 overflow:02 optimized:02 checkout:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sat, 2004-05-01 at 17:08, William Lovas wrote: > In many functional languages, O'Caml included, it's assumed that tail calls > are optimized to jumps, so that tail recursive functions do not allocate > any stack space for each recursive call. (I believe in Scheme this is even > included in the language specification.) > > With that in mind, you can read "This function is not tail recursive" as a > behavioral specification, "This function might terminate abnormally due to > stack overflow" -- and that's a useful side effect to document. Indeed. I know that. But it is suboptimal. There are better ways to write specifications that (a) refer to an implementation that isn't exhibited and (b) assume tail-rec implies no stack allocation The first is called 'ill formed formula', and the second is called 'unwarranted assumption'. So the spec is (a) meaningless gibberish and (b) even if the implementation were exhibited it says nothing about the performance. Yet it is easy enough to say O(n) time and O(1) stack and mean that this is a *requirement* on the implementation and a guarrantee to the programmer. That is the intent, why not say it? -- John Skaller, mailto:skaller@users.sf.net voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners