From: ········@bayou.uh.edu
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <5l27qb$2fm$1@Masala.CC.UH.EDU>
David Hanley (·····@nospan.netright.com) wrote:
[Snip]
: So far, the only issue I've been able to really understand
: has been the speed issue-- C++ will do a lot of things pretty fast.
: Some of the others I've not been able to quite figure out.
: C++ lets you use addresses naturally. Ok. Why is that the 'right way'
: for an algorithms library... etc... I think it would help a bit
: if you could explain why some of these lisp or ML bits aren't
: quite right for what you want.
The impression that I got from reading his postings was that while
he could do STL in other languages, he couldn't do them in the same
way that he did them in C++. For example, one could implement the
kind of functionality available in STL, but the interface would be
different. I failed to see why that was a problem -- C++ couldn't
do many things the same way Scheme or numerous other languages
could either.
The bottom line to me was whether or not a particular implementation
has any real disadvantages, and not whether a different technique
was used in its construction. For instance was the design of
a different method unduly difficult? Was it unduly inflexible?
Maybe I'm mistaken, but the impression I'm getting is that he
found that he couldn't do a 1-1 translation from C++ to Scheme
(obviously) and concluded "therefore it can't be done" without
realizing that maybe it could be done (and done better) in
Scheme, it just needed a different approach since Scheme is
a much different language.
: I read your posting several times, but there's some point in it
: I'm somehow missing. Do you have any papers, perhaps? Maybe something
: that is longer will make some of the points clearer.
I would love to see this as well. I would love to see as much
information as is necessary to allow others to try their hand at
solving what he failed to solve, and to see why he reached his
specific conclusion.
: dave
--
Cya,
Ahmed
Sneaking in the backdoor with dirty magazines,
So your mother wants to know what are all those stains on your jeans.
"Orgasm Addict" by the Buzzcocks
From: Thant Tessman
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <3374BFA3.15FB@nospam.acm.org>
········@bayou.uh.edu wrote:
> The impression that I got from reading [Stepanov's] postings was
> that while he could do STL in other languages, he couldn't do them
> in the same way that he did them in C++. [...]
No. He originally claime that he couldn't do it at all, implying
that it couldn't be done at all, which is, as many people have
shown, nonsense. His story has changed significantly since then.
-thant
--
"Yeah yeah yeah yeah yeah yeah yeah yeah yeah!" -- Robin Scott, "M Factor"
From: Alexander Stepanov
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <3374E3F9.4DAA@mti.sgi.com>
You win. I promise never to post a single netnews message again. The
medium belongs to people like you.
Thant Tessman wrote:
>
> ········@bayou.uh.edu wrote:
>
> > The impression that I got from reading [Stepanov's] postings was
> > that while he could do STL in other languages, he couldn't do them
> > in the same way that he did them in C++. [...]
>
> No. He originally claime that he couldn't do it at all, implying
> that it couldn't be done at all, which is, as many people have
> shown, nonsense. His story has changed significantly since then.
>
> -thant
>
> --
> "Yeah yeah yeah yeah yeah yeah yeah yeah yeah!" -- Robin Scott, "M Factor"
--
Alexander Stepanov
········@mti.sgi.com
Silicon Graphics
2011 N. Shorline Boulevard
Mountain View, CA 94043-1389
tel.: (415)933-6121
From: Erik Naggum
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <3072299272287916@naggum.no>
* Alexander Stepanov -> Thant Tessman
| You win. I promise never to post a single netnews message again. The
| medium belongs to people like you.
the first article you responded to in this thread was mine, where I said
that I thought the Standard Template Library was "remarkably good work",
but also a "magnificient waste" because it is done in C++. I implied that
I thought the ideas were great but the choice of giving them concrete shape
in C++ was unfortunate. however, I realize that I don't understand your
ideas. I also don't buy that C++ is the only language in which you could
implement them, to the extent that I do understand them. finally, I firmly
believe that when something can be done only in C++, that proves it must be
flawed at the core. I have programmed in lots of languages over the past
16 years, and I see _nothing_ in C++ that invites me to use this language,
not even the Standard Template Library. all I have ever learned from all
of my mistakes and my research tells me that C++ is a language that should
only be used by the kind of people who invent stupid ways to avoid hurting
themselves when doing something wrong instead of learning to do something
right -- the kind of people who need to be led to water to realize they
must drink and then don't understand that any water could do equally well,
but cling to the same way they were led in the past.
I went through the first C++ draft that was rejected by conscientious
international standards consultants in a large number of countries, and I
have spent a fair amount of time with the second C++ draft. C++ was the
first language that managed to turn my stomach. (the second was Perl.) I
can't program in C++ because the urge to fix the stupid language is so
overpowering that I can't concentrate on any actual problem. I thought the
Standard Template Library would be a redeeming quality in this refuse of a
language, but if it is so broken that it only fits with the C++ model of
the world and of computation in general, it's like finding a 1000-carat
diamond in a heap of nuclear waste -- only by keeping sufficient distance
can one appreciate it. my only experience with the Standard Template
Library has been its specification, which, unlike the rest of the junk, is
actually readable. (if you wrote the text of those parts of the standard,
you should still be commended for its high quality and clarity.)
but, really, if you can _only_ do it in C++, all of my experience tells me
that that means you're doing something very seriously wrong. if you wish
to publish a paper on this work (which I would eagerly read), please don't
tie it to C++, but show what it needs to be implemented, so others can
implement it for you in other languages, and please be open to that, or so
other languages can be created without the crud that permeates C++. e.g.,
a language based on the Standard Template Library might actually be a good
language. as has already been noted, programming in C++ with and without
templates is like programming in two different languages. there's no need
to keep the moronic aspects of C++ if the ideas in the Standard Template
Library have significant merit on their own.
[cc'ed since you promise never to post. I'm not sure that means you're not
going to read news anymore, either.]
#\Erik
--
if we work harder, will obsolescence be farther ahead or closer?
Alexander Stepanov <········@mti.sgi.com> wrote:
: You win. I promise never to post a single netnews message again. The
: medium belongs to people like you.
: Thant Tessman wrote:
: >
: > [crap deleted - Oleg.]
Incorrect.
Everybody knows about killfiles. My newsreader (tin) offers a rare
feature, which you can think of as "revive". Basically, I only see
posts from people I list in advance. This way, I see about 5-10 posts
a day in comp.lang.c++. You are in the list, Tessman is not. I only
know about his existance, because you quoted him.
The ~5 posts you've posted in the last couple of days, were the most
enlighting, I've ever read, on the history of GP. And the "small talk"
on the GP itself and the crap one has to put up with in commercial
setup, is second only to your articles/interviews :-). I have no doubts
that there are many more lurkers like me, while only the St. Andy
is in the active crusade (and non-so-St. Bjarne is in fragmentary one).
Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
Andrew Koenig wrote:
>
> In article <············@Masala.CC.UH.EDU> ········@Bayou.UH.EDU (········@bayou.uh.edu) writes:
>
> > The impression that I got from reading his postings was that while
> > he could do STL in other languages, he couldn't do them in the same
> > way that he did them in C++.
>
> A more accurate statement might be that he could not make make STL-like
> libraries in other languages do all the things that they can do in C++,
> different interface or not.
Ok. That's possible, but I don't seem to recall that being
demonstrated yet.
[ vector example snipped ]
> However, as Alex pointed out, C++ offers a useful solution to that problem,
> namely a partial template specialization:
>
> template<class T> void swap(vector<T>& x, vector<T>& y) {
> x.swap(y);
> }
>
> What we have said is that if x and y are vectors -- which can be determined
> during compilation
It can be determined _sometimes_ in a true generic system you don't
always know at compile time. It would be pretty useful to have the
mechanism employable
at both complile and run time.
So, it ml, you might have:
fun swap( v1 , v2 ) = (* do a generic swap *)
and a specialized version:
fun swap( v1:Vector , v1:Vector ) = (* do a fast vector swap *)
swap( v1 , v2 ) = (* do the generic swap *)
> An important point about the partical specialization technique is that the
> decision is made at compile time, with no run-time overhead at all.
> What Alex was pointing out is that C++ is one of very few languages
> that allows such compile-time type decisions. It is certainly the only
> such language that is any anywhere near such widespread use.
It would be posible for the compiler to determine the specialized
version to call
to either compile or run-time, depending. I know you will point out
that this
is not a required optimization, which is true. I certianly agree that
SML would
profit by more highly optimizing compilers.
So, would it be valid to assume that the issue is only one of speed and
not of
language power? Because when you say 'You can't do the STL in language
X' it
sounds like 'X' will not implement it properly, eg, have all the
features.
Once again, all I'm really getting out of this discussion is that the
STL was
written in C++ because it was beleived it would run faster. If this is
the case, fine.
What I was trying to understand was if there were any features in C++
which
make STL qualitatively better in some other way than speed, as compared
to
the alternatives which have been mentioned. If the ML or scheme
compiler had
a good optimizer which made code run as fast as C/C++ would they have
been
valid target languages? If not, why not? I think this would be an
interesting discussion.
> Alex wrote a generic algorithms library in Scheme before he ever learned C++.
Cool. In what way is the C++ one better?
dave
David Hanley <·····@nospan.netright.com> writes:
> > A more accurate statement might be that he could not make make STL-like
> > libraries in other languages do all the things that they can do in C++,
> > different interface or not.
>
> Ok. That's possible, but I don't seem to recall that being
> demonstrated yet.
Of course Alex didn't demonstrate that; he never claimed to have done
anything of the sort. "Proof" is a very strong concept.
What Alex said was much simpler: he spent many years trying to write a
library of generic algorithms, he tried many different languages, and
the only library he designed that was satisfactory was the one written
in C++.
This doesn't mean that it's impossible to write a library of generic
algorithms in some other language, only that Alex didn't manage to do
it. If you think that Scheme would be a good language for
implementing a generic algorithm library, then I encourage you to try
to implement one. If you succeed then the world will have one more
generic algorithm library, and if you fail then you'll have learned
something. Either outcome would be progress.
It's worth remembering, though, that there are very few people in the
world who have as much experience implementing generic algorithms as
Alex does; there's something to be said for taking someone else's
experience seriously. One thing I've learned about this game is that
there's no substitute for actually implementing something; just saying
"this is possible" means nothing. Until you've actually implemented
it, you don't know whether or not it's possible. On several
occasions, I've found that seemingly small details turned out to be
crucial.
For my current understanding of the C++ STL, I am indebted to
the 28 April 1995 draft of the C++ standard. Now, that draft
is riddled with errors, and it's two years old by now, so my
information is clearly out of date. If there is a current
draft that I can get a copy of, I will be only too pleased to
update my information.
My understanding is that Alex Stepanov wanted to provide a practically
efficient, highly generic, data structures and algorithms library, and
that he chose C++ as the vehicle for this after experimenting with
other languages.
I want to use a single example to argue that the C++ version of the STL,
as specified in chapter 23 of the 28 April 1995 draft of the C++ standard,
is not efficient, in the same sense in which Stepanov argues that versions
in other languages were not efficient. That is, I am going to offer an
example of a natural operation that I think sequences "ought" to support
efficiently, and we'll find that the version of the STL described in the
reference I am using does not support it efficiently.
Let us imagine a sequence type which supports the following operations:
size(S) -> N charge C[j] = 1
fetch(S, I[j]) -> E charge C[j] = 1
store(S, I[j], E) -> () charge C[j] = 1
insert(S, I[j], T[j]) -> () charge C[j] = 1 + size(T[j])
delete(S, I[j], N[j]) charge C[j] = 1
S is the type of sequences, I is the type of indices (I write in terms of
natural number indices, but that doesn't actually matter), N is the naturals,
and E is the type of elements
I shall say that this sequence type supports
LINEAR (ascending) TRAVERSAL UPDATES
if and only if the cost of a series of M operations
where the indices I[j] are monotone non-decreasing is
O(N + sum j = 1 to M of C[j])
where N is the initial size of the sequence.
I shall say that this sequence type supports
linear descending traversal updates
if and only if the cost of a series of M operations
where the indices I[j] are monotone non-increasing is
O(N + sum j = 1 to N of C[j])
where N is the initial size of the sequence.
I shall say that this sequence type supports
linear bidirectional traversal updates
if and only if it supports both ascending and descending
linear traversal updates.
Note: I have assumed in the formulas above that a subsequent index may
not land inside the elements inserted by insert(). If that _is_ allowed,
replace C[j] for insert() by 1 + 2*size(T[j]). Note also that I am talking
about processing the _whole_ sequence; I am assuming the same kind of
dynamic allocation strategy that the C++ STL uses for vectors; the charges
are _not_ costs for the individual operations.
It should be fairly obvious that
- there are array-based implementations of sequences
that can easily support linear bidirectional traversal updates.
- there are tree-based implementations of sequences
that can easily support linear bidirectional traversal updates
- there are doubly-linked list-based implementations of sequences
that can easily support linear bidirectional traversal updates
- there are singly-linked and fractionally-linked list-based
implementations of sequences
that can easily support linear ascending traversal updates
- there are sequential-access file-based implementations of sequences
that can easily support linear ascending traversal updates.
The operation costs imposed by chapter 23 of the 28 April 1995 draft of
the C++ standard not only fail to guarantee linear ascending traversal
updates, they guaranteee QUADRATIC cost for this common combination of
operations.
Is this a straw man argument? Have I come up with something which isn't
done fast, but which no-one in his right mind would _want_ to do fast?
Well, ascending traversal updates are simply an application to sequences
of traditional sequential file processing. fetch() is read(), store() is
rewrite(), insert() at the end is write(), and delete() is delete().
PL/I and COBOL have these operations built into there syntax.
Note: if we restrict insert() to act only at the appropriate and of
the sequence, the quadratic cost mandated by the 1995 draft C++ standard
_still_ follows.
I mentioned fractionally linked lists above. In order to provide the
operations called for by the algorithms section (chapter 25 of the said
draft), the STL list<T> class forces you to pay the storage and time
overheads of doubly-linked lists, *even when* singly- or fractionally-
linked lists are sufficiently powerful for the operations you actually
want. I don't call that efficient either.
Note: in 20 years of doing things with lists, the number of applications
where I found doubly-linked lists worth using can be counted on the fingers
of one hand. For example, to support linear ascending traversal update,
a singly-linked list needs only one extra pointer and one extra counter over
the obvious implementation. (Twice that if you can go back into an
insertion.)
--
Will maintain COBOL for money.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.
From: Fergus Henderson
Subject: C/C++ object identity (was: C++ briar patch (Was: Object IDs are bad))
Date:
Message-ID: <5lotr8$e7n@mulga.cs.mu.OZ.AU>
Ironically, although C and C++ do in practice have the memory model that
Alexander Stepanov wanted, this is not actually guaranteed by their
respective standards! Neither the C standard nor the C++ draft working
paper guarantee that pointer equality tests will reflect object identity.
For example, given
int x, y;
if (&x == &y) ...
then according to the current C++ draft working paper the result is
unspecified. For the same example, the C standard is unclear; depending
on how you interpret it, either
(a) the pointer comparison results in undefined behaviour, or
(b) the result is guaranteed to be false -- but then by the same
interpretation, in the following example
int xa[1], ya[1];
if (xa + 1 == ya || xa == ya + 1) ...
the condition is also guaranteed to be false, which would imply
that most existing C implementations don't conform to the standard.
[These problems are undoubtably unintentional mistakes in the C standard
and the C++ DWP, and certainly don't reflect the true intent of the language
designers or standards committees involved.]
NB: Followups redirected to comp.std.{c,c++}.
--
Fergus Henderson <···@cs.mu.oz.au> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger ···@128.250.37.3 | -- the last words of T. S. Garp.
In article <··········@research.att.com> ···@research.att.com (Andrew Koenig) writes:
>In article <············@Masala.CC.UH.EDU> ········@Bayou.UH.EDU (········@bayou.uh.edu) writes:
>
>> The impression that I got from reading his postings was that while
>> he could do STL in other languages, he couldn't do them in the same
>> way that he did them in C++.
>
>A more accurate statement might be that he could not make make STL-like
>libraries in other languages do all the things that they can do in C++,
>different interface or not.
<snip an example of specialised generic functions>
First of all, swapping vectors in Lisp is always fast because
everything looks like a reference.
But to address your more general point...
The same thing can be done in CLOS with generic functions. Generic
functions can be as specialised as you want, and you can specialise
over as many of the arguments as you want.
(defgeneric swap ((vector v1) (vector v2))
(let (tmp (v1 internal-mem))
(setq (v1 internal-mem) (v2 internal-mem))
(setq (v2 internal-mem) tmp)))
Assuming that there is a vector class with some internal-mem pointer
to the real memory as in your C++ example.
Can anyone come up with a real example of what Lisp supposedly lacks
over C++?
·············@Alcatel.com.au (Chris Bitmead uid(x22068)) writes:
>Can anyone come up with a real example of what Lisp supposedly lacks
>over C++?
I think I've finally got my head around this STL question.
You *can* do this kind of thing very efficiently indeed in Scheme,
USING PARTIAL EXECUTION.
You write nice clean code that pokes around at its arguments just
a little bit and then decides which of several algorithms to use.
Partial execution (also known as partial evaluation) takes advantage
of information available at `compile' time and optimises all those
choices away.
What's the difference between C and Scheme here?
+ Scheme is such a simple language that it's practical to build
partial executors.
- Partial execution is not a standard part of Scheme environments;
heck, even a compiler isn't. You can't _rely_ on it being there.
- C++ is such a horrendously complex language that it is not yet
practical to build partial executors. (It _has_ been done, with
some success, for C. Some day it _will_ be done for C++.)
+ However, at the price of forcing the programmer to use two
different languages, the compiler _can_ evaluate one of them
at compile time, and that IS a standard part of the language.
Reading through the C++ draft standard is an education in how to
use the second language in C++. If you are used to functional
programming, it's not hard, but it's a rather weird feeling to
see how it gets used in C++.
--
Will maintain COBOL for money.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.
From: Hrvoje Niksic
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <kigg1vn8vn3.fsf@jagor.srce.hr>
··@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
> Reading through the C++ draft standard is an education in how to
> use the second language in C++. If you are used to functional
> programming, it's not hard, but it's a rather weird feeling to
> see how it gets used in C++.
This sounds interesting. Can you provide an example?
--
Hrvoje Niksic <·······@srce.hr> | Student at FER Zagreb, Croatia
--------------------------------+--------------------------------
main(){printf(&unix["\021%six\012\0"],(unix)["have"]+"fun"-0x60);}