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.

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

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

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)

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

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)

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.

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

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.

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.