Re: [Caml-list] List.rev

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

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