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


Andrei

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!

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.

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

Andrei Alexandrescu wrote:

> resolves the recent digitalmars.d debate on interface design

1) This seems to be a misinterpretation of the citation.

Whether a specific procedure belongs to the computational basis of a type T is a matter of the specification of that type T. This specification cannot be inferred from the content of that citation.


2) Applied to the specific problem the framwework of the citation only says:

| iff a type T=List needs a random access operator according to its | specification, and there is no basis from which such an operator | can be built more efficiently, then that random access operator, | probably opIndex, is _allowed_ to be in the computational basis.

It is allowed to be in the computational basis, iff it makes the basis more _expressive_.

It is _required_ to be in the computational basis, iff it enables the basis to be more efficient.


3) If an analogy to numbers is allowed, then a procedure of a computational basis of a type might be similar to a prime number, and a set of procedures might be similar to a set of prime numbers.

Sorrily Stepanov gives no answer for the immidiately rising question what the restriction of a finite computational basis implies for computational hard/intractable problems.

-manfred


-- 
If life is going to exist in this Universe, then the one thing it cannot afford to have is a sense of proportion. (Douglas Adams)

Andrei Alexandrescu wrote:
> 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.

I have downloaded it, but with the amount of other things on my plate reading a 107 page document has to take back-burner to a few other tasks.

Manfred_Nowak Wrote:
> Sorrily Stepanov gives no answer for the immidiately rising question what the restriction of a finite computational basis implies for computational hard/intractable problems.

and care to explain how exactly what you said is not balderdash laminated in elevated words.

superdan wrote:
> Manfred_Nowak Wrote:
>> Sorrily Stepanov gives no answer for the immidiately rising question what the restriction of a finite computational basis implies for computational hard/intractable problems.
> 
> and care to explain how exactly what you said is not balderdash laminated in elevated words.

Because I'm reading the document and it has mathematical proofs as well as numerous (about 133) citations to works widely regarded as fact.

Read before declaring it BS.  Otherwise we have to refer you the dictionary under the entry of "bigotry" for your information.

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

Chris R. Miller Wrote:

> superdan wrote:
> > Manfred_Nowak Wrote:
> >> Sorrily Stepanov gives no answer for the immidiately rising question what the restriction of a finite computational basis implies for computational hard/intractable problems.
> > 
> > and care to explain how exactly what you said is not balderdash laminated in elevated words.
> 
> Because I'm reading the document and it has mathematical proofs as well as numerous (about 133) citations to works widely regarded as fact.
> 
> Read before declaring it BS.  Otherwise we have to refer you the dictionary under the entry of "bigotry" for your information.

no you read before telling me to read before declaring it bs. gotta put you in my dictionary under "confused" eh. question was addressed to manfred.

fwiw i think stepanov is an intercoursin' mad genius. thanx andrei for the link. you're mah nigga!