www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Book in the works by Alexander Stepanov

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Sep 05 2008
next sibling parent reply "Chris R. Miller" <lordSaurontheGreat gmail.com> writes:
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

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 b=

 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:
=20
 "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!
Sep 06 2008
next sibling parent Russell Lewis <webmaster villagersonline.com> writes:
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.
Sep 06 2008
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Sep 06 2008
parent "Chris R. Miller" <lordSaurontheGreat gmail.com> writes:
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

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=



 part of a list interface) by favoring designs that define primitive
 efficient operations from which others, potentially less efficient, c=



 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 i=



 efficient if and only if any procedure implemented using it is as
 efficient as an equivalent procedure written in terms of an alternati=



 basis. For example, a basis for unsigned 32-bit integers providing on=



 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=


 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 su=


 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.=
Sep 06 2008
prev sibling parent Derek Parnell <derek psych.ward> writes:
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
Sep 07 2008
prev sibling next sibling parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
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)
Sep 06 2008
parent reply superdan <super dan.org> writes:
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.
Sep 07 2008
parent reply "Chris R. Miller" <lordSaurontheGreat gmail.com> writes:
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

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

and care to explain how exactly what you said is not balderdash laminat=

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.
Sep 07 2008
parent reply superdan <super dan.org> writes:
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!
Sep 07 2008
next sibling parent reply "Chris R. Miller" <lordSaurontheGreat gmail.com> writes:
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

superdan wrote:
 Chris R. Miller Wrote:
=20
 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=20
 computational hard/intractable problems.




 Because I'm reading the document and it has mathematical proofs as wel=


 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=

red.=20 State of reading. I'm not declaring it anything until I'm done reading, and it's more than a little rash to jump to the "balderdash" conclusion without reading it. Less than half the time more than half of me is inclined to agree with your classification of myself.
 fwiw i think stepanov is an intercoursin' mad genius. thanx andrei for =

He certainly knows how to write in a manner which encourages me to think he's smart. Whether or not he's got anything worth noting I have not personally verified yet. If he bothered to distill his research into more layman's terms I'd be able to get through it much faster and without the constant work of all the careful reading. Moral of these three posts: bsing anything creates more bs than there was to begin with.
Sep 07 2008
parent reply superdan <super dan.org> writes:
Chris R. Miller Wrote:

 superdan wrote:
 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.


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.

State of reading. I'm not declaring it anything until I'm done reading, and it's more than a little rash to jump to the "balderdash" conclusion without reading it. Less than half the time more than half of me is inclined to agree with your classification of myself.
 fwiw i think stepanov is an intercoursin' mad genius. thanx andrei for the
link. you're mah nigga!

He certainly knows how to write in a manner which encourages me to think he's smart. Whether or not he's got anything worth noting I have not personally verified yet. If he bothered to distill his research into more layman's terms I'd be able to get through it much faster and without the constant work of all the careful reading. Moral of these three posts: bsing anything creates more bs than there was to begin with.

very confused eh. but don't you worry my friend. won't let you down. i'll explain again. manfred said: "Sorrily Stepanov gives no answer for the immidiately rising question what the restriction of a finite computational basis implies for computational hard/intractable problems." that did not make sense to me. so i wrote him back: "and care to explain how exactly what you said is not balderdash laminated in elevated words." because that's what seemed to me. computational basis has nothing to do with intractable problems as far as i see both. notice that i used `you' meaning `you mr. manfred novak born in plzen on march 5th 1979, owning a pink pet rock and an autograph from weird al'. capisci? so the balderdash thing was about manfred's words not the ones in the book. hope this clears the skies. now onto some actual content. i am also reading thru the doc and i think the man is not spilling just verbose prolix bs. like for example matt wilson does (man am i happy he stayed with c++ and left d alone). i don't think he can lower level much more before losing precision. take for example his uniquely represented stuff on page 2-3. the notion rang to me instantly because in the past i'd been bit by such issues with 1's complement and floating point nums. if he wanted to give up on the uniquely represented term then he'd have to give up on the entire idea of unique representation. but then he can'd build on that anymore so all of his algos and stuff lose substance and will sometimes not work. because many algos do assume unique representation or other stuff he defines. to me stepanov's art is to put in the clear things that were subliminal.
Sep 08 2008
parent "Chris R. Miller" <lordSaurontheGreat gmail.com> writes:
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

superdan wrote:
 Chris R. Miller Wrote:
=20
 superdan wrote:
 Chris R. Miller Wrote:

 superdan wrote:
 Manfred_Nowak Wrote:
 Sorrily Stepanov gives no answer for the immidiately rising questi=






 what the restriction of a finite computational basis implies for=20
 computational hard/intractable problems.






 Because I'm reading the document and it has mathematical proofs as w=




 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.




nfred.=20
 State of reading.  I'm not declaring it anything until I'm done readin=


 and it's more than a little rash to jump to the "balderdash" conclusio=


 without reading it.

 Less than half the time more than half of me is inclined to agree with=


 your classification of myself.

 fwiw i think stepanov is an intercoursin' mad genius. thanx andrei fo=



 He certainly knows how to write in a manner which encourages me to thi=


 he's smart.  Whether or not he's got anything worth noting I have not
 personally verified yet.  If he bothered to distill his research into
 more layman's terms I'd be able to get through it much faster and
 without the constant work of all the careful reading.


 Moral of these three posts: bsing anything creates more bs than there
 was to begin with.

very confused eh. but don't you worry my friend. won't let you down. i'=

=20
 manfred said:
=20
 "Sorrily Stepanov gives no answer for the immidiately rising question w=

onal hard/intractable problems."
=20
 that did not make sense to me. so i wrote him back:
=20
 "and care to explain how exactly what you said is not balderdash lamina=

=20
 because that's what seemed to me. computational basis has nothing to do=

meaning `you mr. manfred novak born in plzen on march 5th 1979, owning a= pink pet rock and an autograph from weird al'. capisci? so the balderdas= h thing was about manfred's words not the ones in the book.
=20
 hope this clears the skies.

Like taking down the Hindenburgh! Man.. I thought you were calling the research paper BS... English has too great a potential for ambiguity. Someone should make a second version which fixes this bug ;^)
 now onto some actual content. i am also reading thru the doc and i thin=

ilson does (man am i happy he stayed with c++ and left d alone).
=20
 i don't think he can lower level much more before losing precision. tak=

to me instantly because in the past i'd been bit by such issues with 1's= complement and floating point nums. if he wanted to give up on the uniqu= ely represented term then he'd have to give up on the entire idea of uniq= ue representation. but then he can'd build on that anymore so all of his = algos and stuff lose substance and will sometimes not work. because many = algos do assume unique representation or other stuff he defines.
=20
 to me stepanov's art is to put in the clear things that were subliminal=

Still largely incomprehensible to me, but I'm trying to work my way through it. My disadvantage is having not yet taken Calculus (taking precalc right now though!) Much of his math is using notations that are very foreign to me, so I constantly have to look them up myself! Ah, it's like reading Knuth all over again... only shorter.
Sep 08 2008
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
superdan wrote:
 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.

laminated in elevated words.

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!

Hmmm... a(nother) fan of Pulp Fiction I presume? :o) Andrei
Sep 07 2008
parent superdan <super dan.org> writes:
Andrei Alexandrescu Wrote:

 superdan wrote:
 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.

laminated in elevated words.

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!

Hmmm... a(nother) fan of Pulp Fiction I presume? :o)

correctamundo!!
Sep 08 2008
prev sibling parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
superdan wrote:

 question was addressed to manfred.

I cannot answer your question because I do not understand the content. Please note that I never vistited any territory with english speaking people, whereas you seem to be a genius in using the english tongue. -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)
Sep 08 2008
parent reply superdan <super dan.org> writes:
Manfred_Nowak Wrote:

 superdan wrote:
 
 question was addressed to manfred.

I cannot answer your question because I do not understand the content. Please note that I never vistited any territory with english speaking people, whereas you seem to be a genius in using the english tongue.

that don't stop you from using them big words eh. to clarify. you said "Sorrily Stepanov gives no answer for the immidiately rising question what the restriction of a finite computational basis implies for computational hard/intractable problems." since you wrote it i can only presume you understand it. i do not. moreover i feel it's wrong. so why don't you please explain it to me.
Sep 08 2008
parent "Manfred_Nowak" <svv1999 hotmail.com> writes:
superdan 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. 


 please explain it to me.  

Every natural number has a prime factorization and the set of prime numbers is infinite. Therefore: if one is restricted to a finite set of prime numbers for the use in a prime factorization then there exist natural numbers for which one will not be able to build a prime factorization, based on the given restricted set. My prerequisite for the citation above was "If an analogy to numbers is allowed [...]". Under this prerequisite and the contents of the paragraph immediately above, one would be allowed to conclude: | for _some_ given specification of a type `T', the restriction of a | finite computational basis for `T' might imply, that there exist | problems based on the specification of `T', that cannot be solved | efficiently by using that _finite_ basis If the word "some" above can be generalized to "any", then this would be a severe strike into the face of the fans of the reusable components view on programming, to which Stepanov belongs. However, if one stays with the "some", then one has to give criteria on how one can decide whether a given specification is efficiently fulfillable with a finite computational basis. Those that are considered not fulfillable by a finite basis might be those, which are considered hard or intractable in the known sense. I am quite surprised, that hard/intractable problems might show up on something I considered mostly harmless until reading Stepanov: the specification of a type, for which a finite computational basis is known. A simple solution would be, that my prerequisite "analogy to numbers" is disallowed, but I do not see any obvious reason for this disallowance and I would be glad, if Stepanov would provide some guidance. Therefore: | Sorrily Stepanov gives no answer ... -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)
Sep 08 2008
prev sibling next sibling parent reply "Bill Baxter" <wbaxter gmail.com> writes:
On Sat, Sep 6, 2008 at 3:01 PM, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> 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."

Just to clarify: you mean that Stepanov's answer is that there should not be any method to obtain the nth item in a linked list because it is not a fundamental operation? Because it can be synthesized using a sequence of calls to "next()"? That may be, but without reading the whole thing, it's not really clear from just the above quote that Stepanov is advocating that anything not in the basis should not be in a class. Even if that is what he advocates, then surely he doesn't go so far as to advocate that a library should not provide *any* operation that a user can write themselves in an efficient way. A major point of a library is to provide common operations on data types. So in that case I don't really see how Stepanov resolves the debate about using opIndex for a list. He says opIndex/nth is not part of the type's basis, but he doesn't say you shouldn't have an nth function. So maybe he claims it should be a free function outside the class, in which case the question is trivially resolved for the case of D since D doesn't allow operators to be defined outside a class right now. But that kind of answers it with a technicality. It doesn't answer the real question being debated here of whether offering an opIndex is an implicit promise of a fast indexing operator. Or maybe your point was that Stepanov says O(n) linear search *is* fast for a linked list because it's as fast as it can be given the linked list basis? So then it should be ok to use opIndex? --bb
Sep 07 2008
parent reply Alix Pexton <_a_l_i_x_._p_e_x_t_o_n_ _g_m_a_i_l_._c_o_m_> writes:
Bill Baxter wrote:
 On Sat, Sep 6, 2008 at 3:01 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> 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."

Just to clarify: you mean that Stepanov's answer is that there should not be any method to obtain the nth item in a linked list because it is not a fundamental operation? Because it can be synthesized using a sequence of calls to "next()"? That may be, but without reading the whole thing, it's not really clear from just the above quote that Stepanov is advocating that anything not in the basis should not be in a class. Even if that is what he advocates, then surely he doesn't go so far as to advocate that a library should not provide *any* operation that a user can write themselves in an efficient way. A major point of a library is to provide common operations on data types. So in that case I don't really see how Stepanov resolves the debate about using opIndex for a list. He says opIndex/nth is not part of the type's basis, but he doesn't say you shouldn't have an nth function. So maybe he claims it should be a free function outside the class, in which case the question is trivially resolved for the case of D since D doesn't allow operators to be defined outside a class right now. But that kind of answers it with a technicality. It doesn't answer the real question being debated here of whether offering an opIndex is an implicit promise of a fast indexing operator. Or maybe your point was that Stepanov says O(n) linear search *is* fast for a linked list because it's as fast as it can be given the linked list basis? So then it should be ok to use opIndex? --bb

I think the way toapply this the the Linked List opIndex debate is to say that: The most efficient way to implement opIndex(n) for a linked list is to call next() n times where next() is a procedure that is accepted as a part of List's basis (or the node's, or the iterator's.) As that opIndex() would be composed of only procedures from the basis, it is not a part of the basis itself. If you really need to get the nth item in your list then you can write your own procedure, because the basis for the List contains the procedures needed, i.e. Next. If I find myself needing to regularly get the nth item from a linked list I would start to ask myself why I was using a list in the first place. A...
Sep 08 2008
parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
Alix Pexton wrote:

 If I find myself needing to regularly get the nth item from a
 linked list I would start to ask myself why I was using a list in
 the first place. 

What is a "linked list"? This question is motivated by your stated incompatibility of the "get the nth item"-operation with a "linked list". I do not see such an incompatibility. -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)
Sep 08 2008
next sibling parent Don <nospam nospam.com.au> writes:
Manfred_Nowak wrote:
 Alix Pexton wrote:
 
 If I find myself needing to regularly get the nth item from a
 linked list I would start to ask myself why I was using a list in
 the first place. 

What is a "linked list"? This question is motivated by your stated incompatibility of the "get the nth item"-operation with a "linked list". I do not see such an incompatibility.

Using 'get the nth item' with a linked list is like using a brick as a hammer. Sure, you can do it, and sometimes you have to. But if you're doing it a lot, something is badly wrong. It's not something that should be encouraged.
Sep 08 2008
prev sibling parent reply Alix Pexton <_a_l_i_x_._p_e_x_t_o_n_ _g_m_a_i_l_._c_o_m_> writes:
Manfred_Nowak wrote:
 Alix Pexton wrote:
 
 If I find myself needing to regularly get the nth item from a
 linked list I would start to ask myself why I was using a list in
 the first place. 

What is a "linked list"? This question is motivated by your stated incompatibility of the "get the nth item"-operation with a "linked list". I do not see such an incompatibility. -manfred

other data structures that are more efficient for indexing (usually at the expense of requiring more space.) A...
Sep 08 2008
parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
Alix Pexton wrote:

 Of course

I do not see the answer to my question in your replay; same holds for Don. So I repeat my question with some words Stepanov might use: What is the specification for the type T="linked list" or T="list"? Without such a specification every musing on functions/procedures is forlorn hope in the framework of Stepanov. -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)
Sep 08 2008
parent "Manfred_Nowak" <svv1999 hotmail.com> writes:
Robert Jacques wrote:

 see: http://en.wikipedia.org/wiki/Linked_list

Sorry, no. That describes what a _data structure_ named "linked list" might look like, but no "specification of a type" in Stepanovs sense. -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)
Sep 08 2008
prev sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 08 Sep 2008 18:50:52 -0400, Manfred_Nowak <svv1999 hotmail.com>  
wrote:

 Alix Pexton wrote:

 Of course

I do not see the answer to my question in your replay; same holds for Don. So I repeat my question with some words Stepanov might use: What is the specification for the type T="linked list" or T="list"? Without such a specification every musing on functions/procedures is forlorn hope in the framework of Stepanov. -manfred

Manfred, it sounds like you want the definition of a linked list, see: http://en.wikipedia.org/wiki/Linked_list
Sep 08 2008