Book in the works by Alexander Stepanov

[Bill Baxter]

On Sat, Sep 6, 2008 at 3:01 PM, Andrei Alexandrescu
<SeeWebsiteForEmail at erdani.org> wrote:
> See http://www.stepanovpapers.com/eop/eop.pdf for an interesting read. The
> school of thought put forth by Stepanov resolves the recent digitalmars.d
> debate on interface design (e.g. whether opIndex should be part of a list
> interface) by favoring designs that define primitive efficient operations
> from which others, potentially less efficient, can be derived. On pages 5-6:
>
> "A computational basis for a type is a finite set of procedures that enable
> the construction of any other procedure on the type. A basis is efficient if
> and only if any procedure implemented using it is as efficient as an
> equivalent procedure written in terms of an alternative basis. For example,
> a basis for unsigned 32-bit integers providing only zero, equality, and the
> successor function is not efficient since the implementation of addition in
> terms of successor is linear."

Just to clarify:  you mean that Stepanov's answer is that there should
not be any method to obtain the nth item in a linked list because it
is not a fundamental operation?  Because it can be synthesized using a
sequence of calls to "next()"?

That may be, but without reading the whole thing, it's not really
clear from just the above quote that Stepanov is advocating that
anything not in the basis should not be in a class.

Even if that is what he advocates, then surely he doesn't go so far as
to advocate that a library should not provide *any* operation that a
user can write themselves in an efficient way.  A major point of a
library is to provide common operations on data types.

So in that case I don't really see how Stepanov resolves the debate
about using opIndex for a list.  He says opIndex/nth is not part of
the type's basis, but he doesn't say you shouldn't have an nth
function.  So maybe he claims it should be a free function outside the
class, in which case the question is trivially resolved for the case
of D since D doesn't allow operators to be defined outside a class
right now.   But that kind of answers it with a technicality.  It
doesn't answer the real question being debated here of whether
offering an opIndex is an implicit promise of a fast indexing
operator.

Or maybe your point was that Stepanov says O(n) linear search *is*
fast for a linked list because it's as fast as it can be given the
linked list basis?  So then it should be ok to use opIndex?

--bb