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


e

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

 Chris R. Miller wrote:

 Andrei Alexandrescu wrote:

 See http://www.stepanovpapers.com/eop/eop.pdf for an interesting read=






=2E

 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, c=






an

 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=






s

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






ve

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






ly

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




re

 though, so some clarification would be appreciated!


=20
 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:
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.


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


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

 Chris R. Miller Wrote:
=20

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






ated in elevated words.

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




l

 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.


=20
 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 manf=
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 =


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


 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. 


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












on=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 lam=










inated in elevated words.

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








ell

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






ut you in my dictionary under "confused" eh. question was addressed to ma=
nfred.=20

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




g,

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




n

 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=






r the link. you're mah nigga!

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




nk

 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.


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


ll explain again.

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


hat the restriction of a finite computational basis implies for computati=
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=


ted in elevated words."

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


k the man is not spilling just verbose prolix bs. like for example matt w=
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=


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


=2E

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.


 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!


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.


 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!


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


  Of course you can get the nth item from a list, but it is not efficient.
There are
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 reply "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
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