Book in the works by Alexander Stepanov

[Russell Lewis]

Chris R. Miller wrote:
> 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!

Basically, what he means is: "Provide functions which expose all of the 
things that you can do to this data type quickly.  For all the things 
that are going to be slow anyhow, build those as functions that call the 
other, 'fast' functions."

In the example of integers, he says that you need to expose an add() 
function because adding is fast on the hardware.  It is possible, of 
course, to create an add function using a for loop and the increment() 
function, but it's inefficient.