Book in the works by Alexander Stepanov

[Chris R. Miller]

Andrei Alexandrescu 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."

In terms that those of us less practiced in the deeper jargon of
computer science might understand?  I read that about five times and
couldn't figure out exactly what was being said.  I gather he's making a
case that a specification should provide a primitive guarantee of
efficiency, but that it is not necessary for that guarantee to be
enforced in the case of less-primitive algorithms making use of the
construct which the specification applies to.  I'm still not at all sure
though, so some clarification would be appreciated!

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 258 bytes
Desc: OpenPGP digital signature
URL: <http://lists.puremagic.com/pipermail/digitalmars-d-announce/attachments/20080906/6d6d47fa/attachment.pgp>