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 OAA22207; Sun, 2 May 2004 14:05:07 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA22208 for ; Sun, 2 May 2004 14:05:06 +0200 (MET DST) Received: from smtp.web.de (smtp07.web.de [217.72.192.225]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i42C55EV028908 for ; Sun, 2 May 2004 14:05:05 +0200 Received: from [217.185.147.118] (helo=wiko) by smtp.web.de with smtp (WEB.DE 4.101 #91) id 1BKFiS-0001YM-00 for caml-list@inria.fr; Sun, 02 May 2004 14:05:04 +0200 Message-ID: <005001c4303e$00bf7730$7693b9d9@wiko> From: "Andreas Rossberg" To: "caml-list" 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> <1083399017.20722.25.camel@pelican.wigram> Subject: Re: [Caml-list] List.rev Date: Sun, 2 May 2004 14:07:12 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2800.1409 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1409 X-Miltered: at nez-perce with ID 4094E3F1.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; rossberg:01 caml-list:01 sourceforge:01 tail-rec:01 recursion:01 formed:98 stack:02 stack:02 wrote:03 tail:03 meaningless:03 meaningful:04 functional:06 cheers:06 uses:06 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk skaller wrote: > > 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 Sorry, but isn't talking about a stack even less meaningful implementation-driven "gibberish"? Usually, a functional language definition does not mention anything like a stack. In fact, some major FP implementations don't even use a stack. Tail recursion at least is a clear syntactic property that can be defined without referring to implementation techniques. That a tail-recursive function uses constant space is then a well-understood QOI issue. No serious FP implementation would dare not to meet this criterion. Cheers, - Andreas ------------------- 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