Book in the works by Alexander Stepanov

Derek Parnell derek at psych.ward
Sun Sep 7 15:11:22 PDT 2008


On Sat, 06 Sep 2008 00:11:57 -0700, 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 too am no CS major, but my translation of this into human speech goes
something like ...


The term "computational basis" for a type is the set of fundamental 'things
that it can do' (its basic functionality) that can be used to build other
abilities for the type.

A "basis" is deemed efficient only when anything built with it can't be
made more efficient if it was instead built with some alternate "basis". 

For example, a basis for unsigned 32-bit integers (uint) that only has
zero, equality, and a successor function is not efficient since the
implementation of 'addition' using the successor function can only 'add 1'
each time it is called, so adding '4' to uint needs four calls to the
successor function.

-- 
Derek Parnell
Melbourne, Australia
skype: derek.j.parnell


More information about the Digitalmars-d-announce mailing list