Re: [Caml-list] List.rev

[skaller <skaller@users.sourceforge.net>]

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