Book in the works by Alexander Stepanov

[Andrei Alexandrescu]

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!

The jargon is appropriately defined before being used. It's hard to 
explain it without actually pasting the contents of the first pages 
here, so you may want to read them if interested.

For all I know Stepanov largely defines his own taxonomy. I like it 
because it extends notions familiar from mathematics into the realm of 
programming. For example "computational basis" is akin to the vectorial 
basis - a set of linearly independent vectors that define an entire 
space, see e.g. http://en.wikipedia.org/wiki/Basis_(linear_algebra). The 
set is minimal and complete. Similarly, my understanding of the term 
"computational basis" of a type is the set of functions with that 
describe all operations for that type. The basis can be more or less 
"good" in both vector space and programming.


Andrei