View mode: basic / threaded / horizontal-split · Log in · Help
September 06, 2008
Book in the works by Alexander Stepanov
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
September 06, 2008
Re: Book in the works by Alexander Stepanov
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!
September 06, 2008
Re: Book in the works by Alexander Stepanov
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.
September 06, 2008
Re: Book in the works by Alexander Stepanov
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
September 06, 2008
Re: Book in the works by Alexander Stepanov
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)
September 06, 2008
Re: Book in the works by Alexander Stepanov
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.
September 07, 2008
Re: Book in the works by Alexander Stepanov
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.
September 07, 2008
Re: Book in the works by Alexander Stepanov
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.
September 07, 2008
Re: Book in the works by Alexander Stepanov
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
September 08, 2008
Re: Book in the works by Alexander Stepanov
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!
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home