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 PAA26504; Sun, 2 May 2004 15:30:06 +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 PAA26617 for ; Sun, 2 May 2004 15:30:05 +0200 (MET DST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i42DU0EV006089 for ; Sun, 2 May 2004 15:30:02 +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 i42DTvk2057853; Sun, 2 May 2004 22:59:58 +0930 (CST) Subject: Re: [Caml-list] List.rev From: skaller Reply-To: skaller@users.sourceforge.net To: Andreas Rossberg Cc: caml-list In-Reply-To: <005001c4303e$00bf7730$7693b9d9@wiko> 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> <005001c4303e$00bf7730$7693b9d9@wiko> Content-Type: text/plain Message-Id: <1083504596.20722.308.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 02 May 2004 23:29:57 +1000 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 4094F7D9.000 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 rossberg:01 model:01 allocator:01 incompatible:01 inverted:01 implementor:01 stepanov:01 desiring:99 model:01 recursion:01 abstraction:01 abstraction:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sun, 2004-05-02 at 22:07, Andreas Rossberg wrote: > > 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"? That depends on the conformance model. One can certainly speak of auxilliary storage requirements. In C++, one can be definite about STL heap storage (because the store is obtained by definite calls to an allocator). > Usually, a functional language definition > does not mention anything like a stack. A purely semantic definition may well not. Such a definition is generally considered inadequate for a library precisely because it doesn't include performance requirements. > In fact, some major FP > implementations don't even use a stack. Indeed .. Felix doesn't use the machine stack for procedure calls, its incompatible with high speed context switching of control inverted algorithms on a typical Unix box. However, Ocaml does, and, the distinction between heap and stack is actually quite important to many clients: many systems have a lot of potential heap, but only limited stack. That doesn't mean distinguishing auxilliary heap and stack is the right thing to do. I think it might be, but I don't know, and there is a value judgement involved deciding how much freedom an implementor should have. It isn't necessary to specify performance: but I do believe there is a consensus to do so. Certainly that belief is *firmly* held in the C++ world now, since STL introduced the idea to the committee that such requirements were an integral part of a specification. [There is actually a story here: there was concern that the requirements on STL Sort were so high that NO known implementation could meet them bar one: the one Stepanov provided, which was subject to a Patent held by HP. HP was asked to relinquish its intellectual property rights and did.] So, I'm not desiring to force my view on what conformance model should be used, and how tight the specs are, only that if specs are given, they be normative well formed coherent requirements. Its quite possible to *define* the term 'tail-rec' in the library preable and thereby avoid the current problem that the requirement doesn't mean anything. > Tail recursion at least is a clear syntactic property Yes. I agree. But the standard library isn't defined in Ocaml but a more abstract semantics. Clearly one wishes to allow for Ocaml implementations, C implementations, and even machine code implementations. The usual technique is to specify a machine abstraction, define semantics in terms of that, and then bind the compiler performance to the abstraction. > 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. First, Ocaml isn't a FP. One can certainly introduce O(n) auxilliary store in a loop (or tail rec function) using mutable state. Second, I do agree that one expects a tail recursive calls to be implemented as loops. This is a serious problem in Felix because it generates C: procedures are easily optimised: they never use C-stack except transiently, functions are not quite so easy because they do. Third, tail-rec in Ocaml isn't quite so clear due to exception handling (still well defined though). Fourth, it is quite possible for a code to contain both tail calls and non-tail calls: use linear stack, instead of quadradic for example. Tail-rec or not is too black and white. Fifth: a tail rec function can still be high complexity. It depends on the actual implementation. You CAN sort a list using a tail-rec bubble sort... or a tail rec function allocating n copies of the list for fun .. (yeah it still wouldn't blow the stack ..) So generally, I do agree that the fact the Ocaml docs now say 'tail-rec' where before there was no annotation at all: this is a Good Thing (TM). I don't want the implication removed from the library! I'd just like to see it stated more normatively. No hurry either. Just a note to think about, because there are more and more people using Ocaml, and that does tend to make any imprecision come out, especially new users not familiar with the 'common understanding' about things like 'tail-rec'. BTW: for some STL algorithms, the EXACT number of calls the algorithm makes to the copy constructor is mandated. (The copy algorithm). The question arose if an implementation was permitted to make a copy like this: tmp = *p++ *q++ = tmp and the answer is NO, that is banned. Exactly n calls are allowed and no more. Each object is copied *exactly* once. No 'O' notation about 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