Adapting software to multiple usage patterns
jacob navia
the standardization of a container library in C is the fact that
there are many different usage patterns for such a library, and it
would be impossible to satisfy them all.
The solution proposed overcomes this problem in an elegant way
by using a function table.
For example, let's see how that would work in lists, one of the
simplest containers.
As it stands now, the list header structure, with free list, pointer
to first, last, a size_t for the count of the items, and several
other fields could be "top heavy", and bring too much overhead if
the list is very small. For instance, if you know in advance
that you will never store more than 5 items at a time in the
list, such a "top heavy" overhead would be too much.
The solution is to write a specialization of the list
software for very small lists, where (for instance)
you just allocate all the 5 items at once when creating the
list, you eliminate the free list and the heap manager.
You write then, all the functions contained in the interface in a
NEW virtual table (say "small_list.c") and you define a
new virtual table, etc. Then, you just add to the API a
function
newSmallList(size_t element_size);
and you are done. All the code that uses
mylist->lpVtbl->Add(mylist, &data);
will STAY as before identical, without the need to change anything
in it. And one day, when you discover that the list you thought
would be small is no longer small at all, NOTHING must be changed
in the code that uses the list container, only the call to the
normal creation function.
Since all virtual tables are binary compatible (the virtual table
is always the first member) the user code doesn't even need to be
recompiled.
Seebs
> The solution proposed overcomes this problem in an elegant way
> by using a function table.
No, because the function table IS the failure.
That's the usage pattern that is unsuitable for a whole lot of systems,
very unlike the "spirit of C", and unlikely to get traction.
-s
--
Copyright 2009, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
jacob navia
> On 2009-10-13, jacob navia <ja...@nospam.org> wrote:
>> The solution proposed overcomes this problem in an elegant way
>> by using a function table.
>
> No, because the function table IS the failure.
>
> That's the usage pattern that is unsuitable for a whole lot of systems,
I do not know any. Care to explain?
All systems support function pointers (if not they wouldn't support C!)
> very unlike the "spirit of C",
As I understand this "spirit of C", the objective is to keep things simple
and trust the programmer. This is a very simple container library. The code
of the list module doesn't even arrive at 3K.
The code trusts the programmer to customize the interface to his/her own needs,
making possible to change completely the data representation of a container
without changing at all the code that uses it.
Suppose you have a simple minded list package (like there are thousands) and
you see that it is a point where your program is spending a lot of time...
Using this system you can change the representation into a flexible array with
almost NO CHANGES to the user code.
Or, as I explained in the original message, you want to use a "light weight" list.
Etc.
What is important is to see that the user code is made INDEPENDENT of the
actual representation used.
and unlikely to get traction.
That remains to be seen.
Seebs
> I do not know any. Care to explain?
> All systems support function pointers (if not they wouldn't support C!)
Again you confuse function pointers and function tables! Your comments
in the other thread about the performance cost of virtual methods were
totally unrelated to the question of the performance cost of function
pointers.
Function tables are certainly possibly part of a well-understood C interface,
but they're usually fairly closely tied to what's being done.
"Containers" is a very unlikely level of abstraction for a lot of use cases.
Fundamentally, embedding a table of function pointers in an object is pretty
unlikely to make it into the standard.
If you did a version that didn't use any camelcase (because you'll never
sell anyone on an interface which rejects the conventions used throughout
the entire rest of the language), you'd still have the issue that, in general,
if you're writing in C, you are not writing at a level of abstraction where
switching from a flexible array to a list would make sense. They tend to
have radically different typical use cases, with different likely interfaces.
I just don't think this is going to go anywhere, because from the start, you
made a decision contrary to the usual type of decision that gets into the
standard. Make a list library and an array library, and you might see some
buy-in. I don't think "containers" have any hope, though, unless the list
and array interfaces work really, really, well.
Tim Rentsch
> On 2009-10-13, jacob navia <ja...@nospam.org> wrote:
>> The solution proposed overcomes this problem in an elegant way
>> by using a function table.
>
> No, because the function table IS the failure.
>
> That's the usage pattern that is unsuitable for a whole lot of systems,
> very unlike the "spirit of C", and unlikely to get traction.
What makes you say that a table of function pointers
is not in the spirit of C?
jacob navia
This is the only solution if we want to keep a standard interface
but allow for multiple usage patterns. If not, we would have to
make one API for very big lists, another for not so big lists,
and another for tiny lists. That would be an impossible undertaking.
The function pointer table approach allows for many specialized
implementations within a single common interface. This preserves user code
and is flexible to satisfy many different requirements.
Tim Rentsch
> On 2009-10-13, jacob navia <ja...@nospam.org> wrote:
>> I do not know any. Care to explain?
>> All systems support function pointers (if not they wouldn't support C!)
>
> Again you confuse function pointers and function tables! Your comments
> in the other thread about the performance cost of virtual methods were
> totally unrelated to the question of the performance cost of function
> pointers.
>
> Function tables are certainly possibly part of a well-understood C interface,
> but they're usually fairly closely tied to what's being done.
> "Containers" is a very unlikely level of abstraction for a lot of use cases.
>
> Fundamentally, embedding a table of function pointers in an object is pretty
> unlikely to make it into the standard. [snip responses on other aspects]
For me this doesn't answer the question (or maybe the answer is just
circular, "it is the way it is because it is the way it is"). The
function qsort() has a function pointer parameter. Is it so hard to
imagine expanding that to a type that has a struct with several
function pointers in it? I agree with your comment that the interface
needs to be well-worked-out, but assuming that were the case, what
is it about aggregating several function pointers that makes you
think the response to a proposed interface with such a type
would be poor?
Tim Rentsch
> Tim Rentsch a @C3{A9}crit :
I understand the point of proposing an interface that uses
aggregates of function pointers. My question is about
Peter's comment that says (I'm paraphrasing here) such a
technique is not in the spirit of C. I'm curious to
know more exactly what he meant by that and why he said it.
Seebs
> What makes you say that a table of function pointers
> is not in the spirit of C?
A table of function pointers embedded in objects and with the contents of
the table specified by the library seems pretty much like C++ to me.
Seebs
> circular, "it is the way it is because it is the way it is"). The
> function qsort() has a function pointer parameter. Is it so hard to
> imagine expanding that to a type that has a struct with several
> function pointers in it?
The point where you embed a pointer to that in the objects.
Imagine that a "string" had to be a struct with a first member which was
a pointer to the chr, str, dup, cmp, rchr, cspn functions...
That would be unlike the C library. The C library provides simpler
interfaces than that.
> I agree with your comment that the interface
> needs to be well-worked-out, but assuming that were the case, what
> is it about aggregating several function pointers that makes you
> think the response to a proposed interface with such a type
> would be poor?
It seems likely to be expensive and inefficient compared to more specific
designs, and that's not how the library usually goes.
jacob navia
> On 2009-10-14, Tim Rentsch <t...@alumni.caltech.edu> wrote:
>> For me this doesn't answer the question (or maybe the answer is just
>> circular, "it is the way it is because it is the way it is"). The
>> function qsort() has a function pointer parameter. Is it so hard to
>> imagine expanding that to a type that has a struct with several
>> function pointers in it?
>
> The point where you embed a pointer to that in the objects.
>
> Imagine that a "string" had to be a struct with a first member which was
> a pointer to the chr, str, dup, cmp, rchr, cspn functions...
>
> That would be unlike the C library. The C library provides simpler
> interfaces than that.
>
>> I agree with your comment that the interface
>> needs to be well-worked-out, but assuming that were the case, what
>> is it about aggregating several function pointers that makes you
>> think the response to a proposed interface with such a type
>> would be poor?
>
> It seems likely to be expensive and inefficient compared to more specific
> designs, and that's not how the library usually goes.
>
> -s
The problem with specific designs, is exactly that. They are specific.
In C, if you start with a container like a list for instance, you are
married with that container forever. Changing the container because the
list has grown too long is highly expensive in reprogramming time.
Access and usage of the container are too visible. If you want to replace
the list with a flexible array you have to rewrite all accesses to the
data. An error prone and cumbersome approach.
Exactly that problem is addressed here. A generic interface to containers
makes it easier to change them without changing all the code that uses
them.
It is precisely the lack of abstraction that dooms C to be considered as
a low level, primitive language when in fact it is just a simpler language
than others, but it has enough power to be able to describe a containers
library without any problems.
Seebs
> The problem with specific designs, is exactly that. They are specific.
> In C, if you start with a container like a list for instance, you are
> married with that container forever. Changing the container because the
> list has grown too long is highly expensive in reprogramming time.
Yes, it is.
But that's the thing -- if you don't think a list is the right structure,
you don't use one. And if you need to change it, yes, it takes time, but
the result after the change is (at least in theory) a very good match for
what you're doing, without overhead.
> Access and usage of the container are too visible. If you want to replace
> the list with a flexible array you have to rewrite all accesses to the
> data. An error prone and cumbersome approach.
Often true -- but if a flexible array fit, you probably shouldn't have used
a list in the first place.
> It is precisely the lack of abstraction that dooms C to be considered as
> a low level, primitive language when in fact it is just a simpler language
> than others, but it has enough power to be able to describe a containers
> library without any problems.
If the use of the library is any more complex than using a single-purpose
list or array library (and it looks as though it is), then it's not going to
be used because they'll be better fits and simpler to use.
And yes, C is a low-level language these days, and I don't think it is
necessarily a good idea to try to change that. As the man says: If you want
C++, you know where to find it.
jacob navia
> On 2009-10-14, jacob navia <ja...@nospam.org> wrote:
>> The problem with specific designs, is exactly that. They are specific.
>> In C, if you start with a container like a list for instance, you are
>> married with that container forever. Changing the container because the
>> list has grown too long is highly expensive in reprogramming time.
>
> Yes, it is.
>
> But that's the thing -- if you don't think a list is the right structure,
> you don't use one.
A list is the right structure when it doesn't grow too much. But you
know as well as everybody else that requirements change, and data
tends to grow, and that list that was OK for 500 elements it just
doesn't cut it with 5000: you need a better list, with better
heap management that doesn't call malloc for each element to
be added to the list. And then the list is out when you need
50000 elements. You need an array that is flexible, etc.
At each change you need to rewrite all data access!
> And if you need to change it, yes, it takes time, but
> the result after the change is (at least in theory) a very good match for
> what you're doing, without overhead.
>
Until next change.
>> Access and usage of the container are too visible. If you want to replace
>> the list with a flexible array you have to rewrite all accesses to the
>> data. An error prone and cumbersome approach.
>
> Often true -- but if a flexible array fit, you probably shouldn't have used
> a list in the first place.
>
It depends on the application state, and whether that is critical or not.
And those conditions change.
>
> If the use of the library is any more complex than using a single-purpose
> list or array library (and it looks as though it is), then it's not going to
> be used because they'll be better fits and simpler to use.
>
> And yes, C is a low-level language these days, and I don't think it is
> necessarily a good idea to try to change that. As the man says: If you want
> C++, you know where to find it.
Well, here we come to the central point in this discussion. Any improvement in
C is considered harmful to C++ that should be the "better C". I do not see why
C should be destroyed because it is a simpler language. In this race to complexity
C remains very easy to learn and use. Contrary to you, I think C++ is not the
solution because precisely of its complexity.
The library I presented (and I am still developing: today I started the bitstrings)
is a proposal for a standard way to use containers what would give C a boost.
It must be understood that C and C++ are two different languages and each one has its
own development and goals. Establishing a common interface for containers is a worthwhile
goal for C.
Anyway, thanks for participating in this discussion. It is a pity that in this
group so much is written about all kinds of beginner's questions or whether "Kiki"
is an insult or not, or many other absolutely irrelevant stuff, rather than
discussing the construction of a container library.
It is an interesting development, it is precisely about C, and we could discuss in
a concrete fashion many things that we never mention but are hugely important for
software construction in C:
o Interface to the allocator: how could we abstract it? (malloc/gc_malloc/alloca)
o Software specialization and subclassing (This was the original theme I wanted to discuss
with "Adapting software to multiple usage patterns")
o Error handling and software interrupts.
Etc. The container library give us an opportunity to discuss all this stuff but
not many people seem interested in C in comp.lang.c
Gareth Owen
> If you want to replace the list with a flexible array you have to
> rewrite all accesses to the data. An error prone and cumbersome
> approach.
All true and valid. My problem with your container libray is that you
are, in essence reinventing a subset of the C++ container library.
Only without language support (which may well exist in your compiler)
you are left with an explicit vtable, and comparatively ugly syntax.
And, because the vtable is explicit, and users are encouraged to alter
it (to create polymorphic behaviour), the compiler is likely to be
able to make fewer.
It seems to be (though I'm not terribly familiar with the
standardisation process) that the time for standard C container
library was 20+ years ago, where it might have competed for mindshare
with C++ containers, and the C++ compiler writers were still shaking
bugs out of their template code.
Now, anyone who wants containers and wants to use manipulate using a
language that is close enough to C to leverage their skill, is using
C++ containers. They're standardised, they're at least as flexible as
your containers (you can replace the default memory allocator, much as
you've proposed), they're on a colossal number of platforms, they're
logical const-ness is supported by the language (as opposed to your
"read-only" toggle) and you get all the things in <algorithm>
(std::transform, max_element etc), well defined copying semantics
(std::swap specialisation) etc etc etc.. for free. Oh, and if you're
willing to use iterators (whose syntax can be, I grant you, also
hideously ugly), you can swap container types with relative ease.
Regardless of the merits of your library, in terms of standardisation,
that ship has long sailed.
jacob navia
> jacob navia <ja...@nospam.org> writes:
>
>> If you want to replace the list with a flexible array you have to
>> rewrite all accesses to the data. An error prone and cumbersome
>> approach.
>
> All true and valid. My problem with your container libray is that you
> are, in essence reinventing a subset of the C++ container library.
Yes.
> Only without language support (which may well exist in your compiler)
> you are left with an explicit vtable, and comparatively ugly syntax.
>
Yes. The syntax is ugly (can be better with some macros, but I would prefer
not to).
> And, because the vtable is explicit, and users are encouraged to alter
> it (to create polymorphic behaviour), the compiler is likely to be
> able to make fewer.
>
I suppose you meant "fewer optimizations". Yes, but it has already
more or less 20-30% more speed than the C++ containers and uses
more or less the same memory for huge lists of 50 million items.
With specialization it can have more speed than C++ can ever attain.
> It seems to be (though I'm not terribly familiar with the
> standardisation process) that the time for standard C container
> library was 20+ years ago, where it might have competed for mindshare
> with C++ containers, and the C++ compiler writers were still shaking
> bugs out of their template code.
>
The time is right now, when the C++ people start realizing that
a simpler language is not a mistake but an advantage. Ask any C++
programmer, the complexity of that language is over their heads.
But I do not want at all to start a flame war against C++.
What I want is the C equivalent: simpler, faster, that can be used
widely and make C a better language.
> Now, anyone who wants containers and wants to use manipulate using a
> language that is close enough to C to leverage their skill, is using
> C++ containers.
Obviously since there is no C container library :-)
> They're standardised, they're at least as flexible as
> your containers (you can replace the default memory allocator, much as
> you've proposed), they're on a colossal number of platforms, they're
> logical const-ness is supported by the language (as opposed to your
> "read-only" toggle) and you get all the things in <algorithm>
> (std::transform, max_element etc), well defined copying semantics
> (std::swap specialisation) etc etc etc.. for free.
You mention many things:
"They are on a colossal number of platforms".
True, but C too is in a colossal number of platforms.
> they're
> logical const-ness is supported by the language (as opposed to your
> "read-only" toggle)
True, but my toggle can be changed dynamically during the runtime,
i.e. you can take a read/write list, make it read only before
passing it to some other function, and be sure that it wont change.
Then, you eliminate the read only property and you can change it as you
wish. Doing it at runtime has a small cost but it is much more
flexible. And that can't be done in C++.
And yes, "algorithm" part is surely not going to be ported to C...
most people I know using C++ never use that part of the STL and just have
a blank stare when I mention it... Too complex!
> Oh, and if you're
> willing to use iterators (whose syntax can be, I grant you, also
> hideously ugly), you can swap container types with relative ease.
>
Sure. You see, why then can't we do it in C? Why only in C++?
Let's do it in C because is much SIMPLER since everything is open
for you to examine and modify. The vtable is not a mystery that
only compiler people know about. It is there, open for you to hack
as you wish.
> Regardless of the merits of your library, in terms of standardisation,
> that ship has long sailed.
That would mean that there is no future for C. And, as I have stated many
times, I do not believe that. A simpler language is better than a complex
one.
Why?
Because, contrary to the exponential growth of hardware, brain hardware
is kind of FIXED, and there is a much smaller limit to the amount of
computer language trivia that your brain is able to swallow without
indigestion.
That ship has long sailed and C++ has grown beyond what a human being
can understand. Not even the creator of the language can introduce a
modification now, because the complexity of C++ is beyond what he
himself can manage. After several years working on "concepts", he was
forced to accept that he can't do it... The "concepts" debacle show
us that complexity grows without limit and eventually it makes the
whole language impossible to use correctly.
What I want is to go on developing C. You can make a positive contribution
here, if you wish. You can propose things, and I am not a zealot that
will start fighting language wars. I have to use C++ at work, and
that is why I am more and more convinced that the future is C and
not C++.
At the same time I see many things in C++ that are very good ideas
and I have tried to bring them to C. Software construction should be
about that: software construction and not "group feelings"...
Thanks for your contribution.
Mark Storkamp
wrote:
> Gareth Owen a �crit :
> > jacob navia <ja...@nospam.org> writes:
> > Regardless of the merits of your library, in terms of standardisation,
> > that ship has long sailed.
>
> That would mean that there is no future for C. And, as I have stated many
> times, I do not believe that. A simpler language is better than a complex
> one.
I would like to know how Gareth's statement would imply your conclusion.
Do you believe that for C to have a future it must continually evolve
and expand? And if so, for how long. i.e. will it ever be complete, and
if it ever can be, then how do we know that it isn't now? I'm not trying
to be facetious, I think those questions apply in many other areas (e.g.
law).
jacob navia
> In article <hb5a0i$3sk$1...@aioe.org>, jacob navia <ja...@nospam.org>
> wrote:
>
>> Gareth Owen a �crit :
>>> jacob navia <ja...@nospam.org> writes:
>>> Regardless of the merits of your library, in terms of standardisation,
>>> that ship has long sailed.
>> That would mean that there is no future for C. And, as I have stated many
>> times, I do not believe that. A simpler language is better than a complex
>> one.
>
> I would like to know how Gareth's statement would imply your conclusion.
> Do you believe that for C to have a future it must continually evolve
> and expand?
To evolve, yes. For instance this proposal about a container library
is an evolution that doesn't add any new complexity to the language.
C remains exactly as it was before but we would have a common interface
for using lists, hash tables, bitstrings and other containers that would
allow that most programmers would not need to reinvent this thing
over and over when they program in C.
Expand?
Careful. I do not want to reinvent C++.
> And if so, for how long. i.e. will it ever be complete, and
> if it ever can be, then how do we know that it isn't now?
Nothing is ever "complete", unless it is dead. All languages evolve
with time, some parts go obsolete, some other parts are introduced.
That is life. Always changing.
> I'm not trying
> to be facetious, I think those questions apply in many other areas (e.g.
> law).
The answer is the same. When is the body of law finished?
When can we say:
We have all the laws we will ever need?
Here is the same.
Many people have taken the attitude that C is fixed forever frozen in
C 1989. You will find here many people that reject even the C99 standard.
I disagree, and I believe that C is a good all purpose programming language.
It needs to have a better library and one of the most important things
that is missing is a common interface for containers.
Thanks for your contribution.
Tim Rentsch
> On 2009-10-14, Tim Rentsch <t...@alumni.caltech.edu> wrote:
>> For me this doesn't answer the question (or maybe the answer is just
>> circular, "it is the way it is because it is the way it is"). The
>> function qsort() has a function pointer parameter. Is it so hard to
>> imagine expanding that to a type that has a struct with several
>> function pointers in it?
>
> The point where you embed a pointer to that in the objects.
>
> Imagine that a "string" had to be a struct with a first member which was
> a pointer to the chr, str, dup, cmp, rchr, cspn functions...
>
> That would be unlike the C library. The C library provides simpler
> interfaces than that.
I agree that it's unlike the C of K&R times. And to some
extent it's unlike C as it is now (meaning C99), however the
difference now is smaller; for example, type-generic macros
never would have made it into C in earlier times. There's a
good chance that C1X will have language support for threads.
So I'm not sure I'd agree with your assessment if we consider
"the spirit of C" to be a slowly evolving point rather than
a fixed point.
>> I agree with your comment that the interface
>> needs to be well-worked-out, but assuming that were the case, what
>> is it about aggregating several function pointers that makes you
>> think the response to a proposed interface with such a type
>> would be poor?
>
> It seems likely to be expensive and inefficient compared to more specific
> designs, and that's not how the library usually goes.
Certainly we would expect generic code to be slower than
code specific to a particular data structure. Still,
sometimes it's useful or necessary to provide a generic
interface -- qsort() is much more valuable because it
allows array of any element type to be sorted. And
there's no reason the C library can't support type-generic
interfaces as well as type-specific ones. At some level
it's necessary to parameterize a container-like library
by the functions that access the data structures, because
different people will want to make different decisions
about how the various data structures are represented
(witness the recent thread about null-terminated strings
versus length-prefixed strings). ISTM that a type-generic
container-like interface is valuable or necessary for the
same sort of reasons that a type-generic qsort() interface is;
although, I have to admit that doing a good job for containers
is much harder than it is for qsort.
IMO the most important conclusion to come out of this
discussion is a point you've basically made already,
which is for such a proposal to get some buy-in it
must be well worked out. So I definitely agree on
that aspect of what (I think) you're saying.
Richard Heathfield
> Mark Storkamp a �crit :
>> In article <hb5a0i$3sk$1...@aioe.org>, jacob navia <ja...@nospam.org>
>> wrote:
>>
>>> Gareth Owen a �crit :
>>>> jacob navia <ja...@nospam.org> writes:
>>>> Regardless of the merits of your library, in terms of
>>>> standardisation, that ship has long sailed.
>>> That would mean that there is no future for C. And, as I have
>>> stated many times, I do not believe that. A simpler language is
>>> better than a complex one.
>>
>> I would like to know how Gareth's statement would imply your
>> conclusion. Do you believe that for C to have a future it must
>> continually evolve and expand?
>
> To evolve, yes.
That's an interesting belief, but not one that is universally held.
> For instance this proposal about a container library
> is an evolution that doesn't add any new complexity to the language.
That depends on whether you consider the library to be a part of the
language. Some do, others don't.
> C remains exactly as it was before but we would have a common
> interface for using lists, hash tables, bitstrings and other
> containers that would allow that most programmers would not need to
> reinvent this thing over and over when they program in C.
Except that many programmers will look at any such standard and find
it wanting in some respect or other - e.g. it's too complex, or too
slow, or whatever. And so they'll go roll their own anyway. This
already happens, by the way - for example, people write their own
little parsing libraries rather than use strtok.
> Expand?
>
> Careful. I do not want to reinvent C++.
That's what your container library is pointing towards.
>> And if so, for how long. i.e. will it ever be complete, and
>> if it ever can be, then how do we know that it isn't now?
>
> Nothing is ever "complete", unless it is dead.
Here I have to disagree. Just because something no longer changes,
that doesn't mean it's of no use. I have a five-eighths spanner which
I've owned for over twenty years. It hasn't changed at all over those
twenty years, but it still does its job perfectly well.
> All languages evolve
> with time, some parts go obsolete, some other parts are introduced.
>
> That is life. Always changing.
The "life" analogy is interesting, but you have not yet convinced me
that it is appropriate. C isn't a living creature. It's a formal
system (or at least it's reasonably close to being a formal system).
It can't die because it isn't alive. We can choose to stop using it
if we like, but that won't kill it because it isn't alive.
>> I'm not trying
>> to be facetious, I think those questions apply in many other areas
>> (e.g. law).
> The answer is the same. When is the body of law finished?
>
> When can we say:
>
> We have all the laws we will ever need?
When we pass a law that says "for any new law to be passed, two old
laws must be repealed".
> Here is the same.
>
> Many people have taken the attitude that C is fixed forever frozen
> in C 1989. You will find here many people that reject even the C99
> standard.
It is implementors who have, on the whole, rejected the C99 standard.
> I disagree, and I believe that C is a good all purpose programming
> language.
It is certainly a good all purpose programming language. You don't
need to add a standardised container library to make it so.
> It needs to have a better library
Why?
> and one of the most
> important things that is missing is a common interface for
> containers.
It is missing because any interface proposal is bound to have more
opponents than supporters.
<snip>
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
Gareth Owen
> The time is right now, when the C++ people start realizing that a
> simpler language is not a mistake but an advantage. Ask any C++
> programmer, the complexity of that language is over their heads.
Yes. But most people who use C++ use a a relatively simple subset of
it
>> Now, anyone who wants containers and wants to use manipulate using a
>> language that is close enough to C to leverage their skill, is using
>> C++ containers.
>
> Obviously since there is no C container library :-)
I meant "rather than roll their own C containers". The point is a
skilled C programmer can program in "C plus containers" already.
That's one of the viable, relatively simple, almost-subsets of C++ I
refer to above.
> You mention many things: "They are on a colossal number of
> platforms". True, but C too is in a colossal number of platforms.
But your libray will need porting / creating to those platforms.
Past history suggests this will be less trivial than first thought.
> True, but my toggle can be changed dynamically during the runtime,
> i.e. you can take a read/write list, make it read only before
> passing it to some other function, and be sure that it wont change.
> Then, you eliminate the read only property and you can change it as
> you wish. Doing it at runtime has a small cost but it is much more
> flexible. And that can't be done in C++.
But what happens if I pass a readonly container to a routine that
expects a mutable container. In C++ const-ness prevents this
happening.
> And yes, "algorithm" part is surely not going to be ported to C...
> most people I know using C++ never use that part of the STL and just
> have a blank stare when I mention it... Too complex!
The dark corners are undeniably complex. I'd argue that
vector<double> vec;
/* ... */
double mean = accumulate(vec.begin(),vec.end(),0.0) / vec.size();
is as clear in intent as its C equivalent.
>> Oh, and if you're willing to use iterators (whose syntax can be, I
>> grant you, also hideously ugly), you can swap container types with
>> relative ease.
>>
> Sure. You see, why then can't we do it in C? Why only in C++?
We can do it in C. Of course we can. But people are *already* doing
it in C++, and that inertia is going to be impossible to shift.
> The vtable is not a mystery that only compiler people know about. It
> is there, open for you to hack as you wish.
I don't consider that as great an advantage as you do ;) When doing
things with containers, I consider it a positive boon to have the gory
details hidden from me.
>> Regardless of the merits of your library, in terms of standardisation,
>> that ship has long sailed.
>
> That would mean that there is no future for C.
No. It merely mean the future of C is the present of C. A
widely-available niche language with good facilities for bare metal
programming, wide popularity in embedded software, and a partial,
mediocre standard library that displays many warts (if not outright
deformities) due to lessons learned long after its standardisation.
> A simpler language is better than a complex one.
So C without containers is better than C with containers. C
programmers (hell, all programmers) want their language to be as
simple as possible but no simpler. The problem is that
> That ship has long sailed and C++ has grown beyond what a human
> being can understand.
Which would be a valid criticism if it were necessary to understand
the entire language in order to use it productively.
I can use vector<int> and transform(), accumulate() fluently without
ever caring about template metaprogramming is a complete mystery, or
that C++0x will be forever delayed after the concepts debacle, or
exactly how I need to derive from BinaryFunction (or was it
UnaryFunction) to make std::bind2nd work.
On my recent holiday in the Loire valley, I found I could communicate
perfectly well with the local people, despite the fact I never really
got the hang of the le subjonctif or le futur parfait.
> Yes, but it has already more or less 20-30% more speed than the C++
> containers
That wasn't the result I saw using gcc on your original postings.
And, given that the C++ implementation uses almost an identical
implementation (vtables), I'll need to see some concrete evidence.
> and uses more or less the same memory for huge lists of 50 million
> items.
With a custom heap manager? But then the C++ mavens will tune their
allocator, and we'll be back to near-equivalence.
Gareth Owen
> Many people have taken the attitude that C is fixed forever frozen
> in C 1989. You will find here many people that reject even the C99
> standard.
It's interesting you single that out. I use one feature of C99 ever
day in my programming, and its one with a bearing on another interest
of yours. The 'restrict' keyword enables gcc to automatically
vectorise dot and matrix products using x86 SSE/SIMD instructions.
jacob navia
> jacob navia <ja...@nospam.org> writes:
>
>> The time is right now, when the C++ people start realizing that a
>> simpler language is not a mistake but an advantage. Ask any C++
>> programmer, the complexity of that language is over their heads.
>
> Yes. But most people who use C++ use a a relatively simple subset of
> it
>
This is an interesting point that I hear very often. C++ is of course
too much for a single person so the language is cut by people in
smaller pieces that can be understood.
Well, here is a smaller subset of the STL that is written in C and
that you can use as you wish in C. (Or in C++ for that matter)
>>> Now, anyone who wants containers and wants to use manipulate using a
>>> language that is close enough to C to leverage their skill, is using
>>> C++ containers.
>> Obviously since there is no C container library :-)
>
> I meant "rather than roll their own C containers". The point is a
> skilled C programmer can program in "C plus containers" already.
> That's one of the viable, relatively simple, almost-subsets of C++ I
> refer to above.
>
But precisely my objective is that once this library is working
you do not need to "roll you own". If you have the interface, and
the source code readily available with no license whatsoever
you can adapt it in thousand ways without a lot of effort to
customize it to do what you want. This is a technologically
simpler approach but, an approach that can work very well.
>> You mention many things: "They are on a colossal number of
>> platforms". True, but C too is in a colossal number of platforms.
>
> But your libray will need porting / creating to those platforms.
> Past history suggests this will be less trivial than first thought.
>
Until now I have used ONLY C89. Not even C99. I do not see where
I would need anything else.
>> True, but my toggle can be changed dynamically during the runtime,
>> i.e. you can take a read/write list, make it read only before
>> passing it to some other function, and be sure that it wont change.
>> Then, you eliminate the read only property and you can change it as
>> you wish. Doing it at runtime has a small cost but it is much more
>> flexible. And that can't be done in C++.
>
> But what happens if I pass a readonly container to a routine that
> expects a mutable container. In C++ const-ness prevents this
> happening.
>
Yes, and C++ will go on existing, and you will go on using it. In C++
you are protected by a huge and complex compiler from many mistakes.
In C you aren't, you are using a simpler language where many things
are possible but that does NOT protect you in any way from your
own mistakes.
Both languages can coexist, and in C you can do things that in C++ you
can't and in C++ you can do things that C can't.
>> And yes, "algorithm" part is surely not going to be ported to C...
>> most people I know using C++ never use that part of the STL and just
>> have a blank stare when I mention it... Too complex!
>
> The dark corners are undeniably complex. I'd argue that
>
> vector<double> vec;
> /* ... */
> double mean = accumulate(vec.begin(),vec.end(),0.0) / vec.size();
>
> is as clear in intent as its C equivalent.
>
Sure, that looks nice. But is it very different from
Vector *dv;
// Add elements to the vector
double mean,sum=0; int i;
for (i=0; i<dv->count; i++) {
sum += *(double *)dv->lpVtbl->GetElement(dv,i);
}
mean = sum/i;
Sure, that doesn't look as pretty as C++. But it does the same.
and, let's get real, is as clear as C++.
>>> Oh, and if you're willing to use iterators (whose syntax can be, I
>>> grant you, also hideously ugly), you can swap container types with
>>> relative ease.
>>>
>> Sure. You see, why then can't we do it in C? Why only in C++?
>
> We can do it in C. Of course we can. But people are *already* doing
> it in C++, and that inertia is going to be impossible to shift.
>
But I do not want to disturb all those programmers that use C++. If they
are happy please go on using C++. I am only proposing that in C we
do not need to reprogram a list package for the THOUSANDTH time!
>> The vtable is not a mystery that only compiler people know about. It
>> is there, open for you to hack as you wish.
>
> I don't consider that as great an advantage as you do ;) When doing
> things with containers, I consider it a positive boon to have the gory
> details hidden from me.
>
Sure, in that case you can use the macros:
for (i=0; GetCountVector(dv); i++) {
sum += GetElementVector(dv,i,double);
}
Much better, but it uses name space in YOUR name space. If you
do not mind, the library will come with all those macros predefined.
#ifdef __INCLUDE_MACROS__
#define GetElementVector(vec,idx,type) *(type *)vec->lpVtbl->GetElement(vec,idx)
#endif
>>> Regardless of the merits of your library, in terms of standardisation,
>>> that ship has long sailed.
>> That would mean that there is no future for C.
>
> No. It merely mean the future of C is the present of C. A
> widely-available niche language with good facilities for bare metal
> programming, wide popularity in embedded software, and a partial,
> mediocre standard library that displays many warts (if not outright
> deformities) due to lessons learned long after its standardisation.
>
But why should we keep those warts forever dam it?
Why do the C++ people always start complaining when somebody starts
trying to eliminate those warts?
Why should C be always considered as the land of the warts? All C++
books start with telling people how bad C is and how much better
C++ is. And each time that somebody starts trying to remedy that
situation they tell "C is like that" or "C can't be changed", etc.
>> A simpler language is better than a complex one.
>
> So C without containers is better than C with containers. C
> programmers (hell, all programmers) want their language to be as
> simple as possible but no simpler. The problem is that
>
But the container library doesn't modify anything in the C language
as such, in the same way that a network library doesn't modify the language
either. And the language is simpler than before because all the
different list/hash tables/whatever are done using the same
uniform interface.
>> Yes, but it has already more or less 20-30% more speed than the C++
>> containers
>
> That wasn't the result I saw using gcc on your original postings.
Since then I posted about the new heap manager. This reduced memory
consumption by half, and increased speed by a factor of 30-40%.
And it is just a very simple heap manager. Much better heap managers
can be done. But that is not even important. What is important is
the interface.
> And, given that the C++ implementation uses almost an identical
> implementation (vtables), I'll need to see some concrete evidence.
>
>> and uses more or less the same memory for huge lists of 50 million
>> items.
>
> With a custom heap manager? But then the C++ mavens will tune their
> allocator, and we'll be back to near-equivalence.
Of course. At the end both libraries will have the same speed.
You can buy a Rolls Royce, or you can buy a small car. C is
simpler than C++, easier to learn and to master. C++ is the Rolls,
C is the small car and both go at the same speed in the CPU/RAM
traffic jams.
:-)
jacob navia
Well, I have spent the last 10 years writing a C99 compilation system.
I am surely not against C99!
I was just telling you about the attitude of some people here.
Richard Heathfield
<snip>
> I am only proposing that in C
> we do not need to reprogram a list package for the THOUSANDTH time!
Those of us who need generic lists (and other containers) already have
them, or can get them easily. There are plenty out there. If you want
to add another one, feel free. The more the merrier!
But people are not going to jump through hoops to rip out their list
code and plug yours in instead. They'll go with what they've got,
because they know it works and they're used to it.
Flash Gordon
> Seebs a �crit :
>> On 2009-10-14, jacob navia <ja...@nospam.org> wrote:
>>> The problem with specific designs, is exactly that. They are specific.
>>> In C, if you start with a container like a list for instance, you are
>>> married with that container forever. Changing the container because the
>>> list has grown too long is highly expensive in reprogramming time.
>>
>> Yes, it is.
>>
>> But that's the thing -- if you don't think a list is the right structure,
>> you don't use one.
>
> A list is the right structure when it doesn't grow too much.
Only if your access pattern is list like.
> But you
> know as well as everybody else that requirements change, and data
> tends to grow, and that list that was OK for 500 elements it just
> doesn't cut it with 5000: you need a better list, with better
> heap management that doesn't call malloc for each element to
> be added to the list.
It's not necessarily the size, it might be frequency of addition. If the
program runs for a year adding 100 elements to the list per day then the
overhead of malloc might not be significant.
> And then the list is out when you need
> 50000 elements. You need an array that is flexible, etc.
Hmm. Inserting an element half way through could be problematic.
> At each change you need to rewrite all data access!
I've not had any data usage change by that much. I would consider it to
be a sign that it was not well specified in the first place.
>> And if you need to change it, yes, it takes time, but
>> the result after the change is (at least in theory) a very good match for
>> what you're doing, without overhead.
>
> Until next change.
At which you need maximum possible speed and don't want the overhead of
indirect calls.
>>> Access and usage of the container are too visible. If you want to
>>> replace
>>> the list with a flexible array you have to rewrite all accesses to the
>>> data. An error prone and cumbersome approach.
>>
>> Often true -- but if a flexible array fit, you probably shouldn't have
>> used
>> a list in the first place.
>
> It depends on the application state, and whether that is critical or not.
> And those conditions change.
I've never had them change that much. If it might happen that I would
possibly design a suitable flexible interface.
>> If the use of the library is any more complex than using a single-purpose
>> list or array library (and it looks as though it is), then it's not
>> going to
>> be used because they'll be better fits and simpler to use.
>>
>> And yes, C is a low-level language these days, and I don't think it is
>> necessarily a good idea to try to change that. As the man says: If
>> you want
>> C++, you know where to find it.
>
> Well, here we come to the central point in this discussion. Any
> improvement in
> C is considered harmful to C++ that should be the "better C".
No it isn't. It just happens that a number of improvements you have
suggested have not been considered appropriate by a lot of people.
I happen to consider the addition of threading support to the C standard
to be interesting.
> I do not
> see why
> C should be destroyed because it is a simpler language.
It isn't.
> In this race to
> complexity
> C remains very easy to learn and use. Contrary to you, I think C++ is
> not the
> solution because precisely of its complexity.
I'm not fond of what I've seen of C++, so I would probably pick one of
the other many languages out there if I wanted the kinds of features you
are proposing.
> The library I presented (and I am still developing: today I started the
> bitstrings)
> is a proposal for a standard way to use containers what would give C a
> boost.
Since it can be implemented in standard C you can release it under a
suitable license and people can use it if they want. However, I don't
like the look of the way your interface is used, so I'm unlikely to use it.
<snip>
> It is an interesting development, it is precisely about C, and we could
> discuss in
> a concrete fashion many things that we never mention but are hugely
> important for
> software construction in C:
You seem to think that discussing something means agreeing with you.
> o Interface to the allocator: how could we abstract it?
> (malloc/gc_malloc/alloca)
For my usage, malloc is abstract enough. I don't need GC, and have never
seen a need for alloca (I don't have a need for flexible arrays either).
> o Software specialization and subclassing (This was the original theme I
> wanted to discuss
> with "Adapting software to multiple usage patterns")
I can't say I've a need for that, not in the was you are doing it. I do
have stuff with indirection through function pointers, but that is not
working in the same was as your interface.
> o Error handling and software interrupts.
Those are different topics.
> Etc. The container library give us an opportunity to discuss all this
> stuff but
> not many people seem interested in C in comp.lang.c
Plenty of people are interested in C, just not in your container library.
--
Flash Gordon
jacob navia
> In <hb5bep$5ho$1...@aioe.org>, jacob navia wrote:
>
>> Mark Storkamp a �crit :
>>> In article <hb5a0i$3sk$1...@aioe.org>, jacob navia <ja...@nospam.org>
>>> wrote:
>>>
>>>> Gareth Owen a �crit :
>>>>> jacob navia <ja...@nospam.org> writes:
>>>>> Regardless of the merits of your library, in terms of
>>>>> standardisation, that ship has long sailed.
>>>> That would mean that there is no future for C. And, as I have
>>>> stated many times, I do not believe that. A simpler language is
>>>> better than a complex one.
>>> I would like to know how Gareth's statement would imply your
>>> conclusion. Do you believe that for C to have a future it must
>>> continually evolve and expand?
>> To evolve, yes.
>
> That's an interesting belief, but not one that is universally held.
>
>> For instance this proposal about a container library
>> is an evolution that doesn't add any new complexity to the language.
>
> That depends on whether you consider the library to be a part of the
> language. Some do, others don't.
>
You have the situation now:
All programs of a minimum complexity need to use lists, hash tables,
and other containers. Since there is no standard all those programs
have a "utilities.c" module where they have ad hoc container libraries.
When you merge the code bases you see that the list package A is not
compatible with list package B. Complexity of porting increases.
When you see
c = Get_nth(a,b);
You do not know immedately what it does. The language is more complex
because a common vocabulary is missing and you need to figure out
what "Get_nth" does.
The language is simpler if we use a common vocabulary for common tasks like
lists.
>> C remains exactly as it was before but we would have a common
>> interface for using lists, hash tables, bitstrings and other
>> containers that would allow that most programmers would not need to
>> reinvent this thing over and over when they program in C.
>
> Except that many programmers will look at any such standard and find
> it wanting in some respect or other - e.g. it's too complex, or too
> slow, or whatever.
Sure. But much more will say:
AT LAST!
I do NOT need to rewrite a list package AGAIN!
> And so they'll go roll their own anyway.
C has been always like that, and if you do not include stdio.h
you can roll your own I/O system. ANd there will be always people
that like to roll their own. They will be able to do that in the future.
The container library is for people that want to write THEIR software
and not rewrite a list package AGAIN!
> This
> already happens, by the way - for example, people write their own
> little parsing libraries rather than use strtok.
>
So, you would say that strtok should be banned?
Besides the problems of multithreading with strtok are known. Maybe
you should consider that that could be a reason isn't it?
>> Expand?
>>
>> Careful. I do not want to reinvent C++.
>
> That's what your container library is pointing towards.
>
The library is written in standard C. I do not see where I am
doing C++. Obviously if you think that an abstraction like
containers is too much for C then please say it so.
>>> And if so, for how long. i.e. will it ever be complete, and
>>> if it ever can be, then how do we know that it isn't now?
>> Nothing is ever "complete", unless it is dead.
>
> Here I have to disagree. Just because something no longer changes,
> that doesn't mean it's of no use. I have a five-eighths spanner which
> I've owned for over twenty years. It hasn't changed at all over those
> twenty years, but it still does its job perfectly well.
>
Sure. Because it is completely dead. Or you are going to argue that
the spanner is alive?
Languages are used by living PEOPLE and that's why they evolve
with time, because the PEOPLE that use them evolve, as people always do.
>> All languages evolve
>> with time, some parts go obsolete, some other parts are introduced.
>>
>> That is life. Always changing.
>
> The "life" analogy is interesting, but you have not yet convinced me
> that it is appropriate. C isn't a living creature.
Of course not. "C" is not alive. The PEOPLE that use "C" are alive, and
that is why C evolves!
> It's a formal
> system (or at least it's reasonably close to being a formal system).
I think that fgormal logic theory will evolve enough so that end of this
next decade they will be able to formalize C 100%. Until then, C is just
a convention used for communicating with a machine.
> It can't die because it isn't alive. We can choose to stop using it
> if we like, but that won't kill it because it isn't alive.
>
See above.
>> I disagree, and I believe that C is a good all purpose programming
>> language.
>
> It is certainly a good all purpose programming language. You don't
> need to add a standardised container library to make it so.
>
Well it is strange that the person that says this has written a
thick book about lists, and all kinds of containers.
True, that book stays always at a simplistic model, without ever
delving deeper into the problems of organizing data structures.
For instance the lists malloc for each element, etc. No performance
considerations, no generalization, etc.
>> It needs to have a better library
>
> Why?
>
I can't explain this to you. If you consider the situation now as
excellent, you are beyond help.
>> and one of the most
>> important things that is missing is a common interface for
>> containers.
>
> It is missing because any interface proposal is bound to have more
> opponents than supporters.
>
> <snip>
>
I am prepared to hear people like you:
"It will not work"
"We do not need it"
"Roll your own list package each time you start a project"
"Standards are just cumbersome"
"C is like that"
"The spirit of C is against that"
Who cares?
What is important in life is to try to better the environment
where you live, to improve things, to BUILD.
The passive people that are always saying that the best thing is to do
nothing are best ignored. It is a pity that instead of collaborating
in this project you just choose to fight it.
Richard Heathfield
<snip>
> The language is simpler if we use a common vocabulary for common
> tasks like lists.
Yes - and if C had had generic containers built-in at the start,
probably they would be widely used. But it didn't, so people found
ways around the lack. You missed the market niche by about 30 years.
<snip>
> AT LAST!
>
> I do NOT need to rewrite a list package AGAIN!
Right. Already got one. Don't need yours.
>> And so they'll go roll their own anyway.
>
> C has been always like that, and if you do not include stdio.h
> you can roll your own I/O system. ANd there will be always people
> that like to roll their own. They will be able to do that in the
> future.
Right.
> The container library is for people that want to write THEIR
> software and not rewrite a list package AGAIN!
There is no "the" container library for C. There are many. Nobody has
to write another one if they don't want to. Adding another one will
not reduce the need to write your own because that need is already
non-existent.
>> This
>> already happens, by the way - for example, people write their own
>> little parsing libraries rather than use strtok.
>>
>
> So, you would say that strtok should be banned?
Not at all. But if I were designing the library from scratch, I would
probably not have included it. (At the very least, I'd have
re-written it to be stateless.)
> Besides the problems of multithreading with strtok are known. Maybe
> you should consider that that could be a reason isn't it?
<shrug> strtok is there now, and it doesn't do much harm to leave it
there.
>>> Expand?
>>>
>>> Careful. I do not want to reinvent C++.
>>
>> That's what your container library is pointing towards.
>
> The library is written in standard C. I do not see where I am
> doing C++. Obviously if you think that an abstraction like
> containers is too much for C then please say it so.
Any container library must necessarily be type-blind if it's to be any
use.
>>>> And if so, for how long. i.e. will it ever be complete, and
>>>> if it ever can be, then how do we know that it isn't now?
>>> Nothing is ever "complete", unless it is dead.
>>
>> Here I have to disagree. Just because something no longer changes,
>> that doesn't mean it's of no use. I have a five-eighths spanner
>> which I've owned for over twenty years. It hasn't changed at all
>> over those twenty years, but it still does its job perfectly well.
>
> Sure. Because it is completely dead. Or you are going to argue that
> the spanner is alive?
No, that's your argument, and it's inherently broken. Languages are
not "alive" in any meaningful sense.
> Languages are used by living PEOPLE and that's why they evolve
> with time, because the PEOPLE that use them evolve, as people always
> do.
By the same argument, five-eighths spanners are used by living PEOPLE
and that's why they evolve with time... except that of course they
don't. A five-eighths spanner that evolves into something else is no
longer a five-eighths spanner, so what good is it if what you need is
a five-eighths spanner?
>>> All languages evolve
>>> with time, some parts go obsolete, some other parts are
>>> introduced.
>>>
>>> That is life. Always changing.
>>
>> The "life" analogy is interesting, but you have not yet convinced
>> me that it is appropriate. C isn't a living creature.
>
> Of course not. "C" is not alive.
Agreed.
> The PEOPLE that use "C" are alive,
Also agreed.
> and that is why C evolves!
But I don't see how you arrive at this step. The people that use
five-eighths spanners are alive, but that doesn't mean that spanners
evolve.
<snip>
>>> I disagree, and I believe that C is a good all purpose programming
>>> language.
>>
>> It is certainly a good all purpose programming language. You don't
>> need to add a standardised container library to make it so.
>>
>
> Well it is strange that the person that says this has written a
> thick book about lists, and all kinds of containers.
I'm not saying containers are bad. On the contrary, I think they're a
great idea. If you think I'm opposed to the concept of a container
library, you're mistaken.
> True, that book stays always at a simplistic model, without ever
> delving deeper into the problems of organizing data structures.
Tempus fugited.
<snip>
>>> It needs to have a better library
>>
>> Why?
>>
>
> I can't explain this to you.
If you can't explain it to me, how do you hope to explain it to ISO?
> If you consider the situation now as
> excellent, you are beyond help.
Had C included a de facto standard container library when it was first
promulgated, everybody would be using that library now. But it
didn't. Consequently, a myriad such libraries have sprung up. I'm not
saying it wouldn't be nice to have a standard container library. It
would. But there are too many practical objections for it to stand
any chance of becoming reality.
>>> and one of the most
>>> important things that is missing is a common interface for
>>> containers.
>>
>> It is missing because any interface proposal is bound to have more
>> opponents than supporters.
>>
>> <snip>
>>
>
> I am prepared to hear people like you:
>
> "It will not work"
I have not said your container library will not work. But it will not
be accepted as a standard.
> "We do not need it"
We don't. It would be a nice-to-have, but it will never happen, and
we'll survive without it.
> "Roll your own list package each time you start a project"
I never said that. What people actually do is dig out the one they
used last time.
> "Standards are just cumbersome"
I never said that, either.
> "C is like that"
Like what?
> "The spirit of C is against that"
I am a bit suspicious of that argument. But I do feel that there are
so many different ways to skin this particular cat that the chance of
getting enough people to agree on /one/ way is infinitesimal.
> Who cares?
Obviously you do, but it's not clear why you care.
> What is important in life is to try to better the environment
> where you live, to improve things, to BUILD.
Yup.
> The passive people that are always saying that the best thing is to
> do nothing are best ignored. It is a pity that instead of
> collaborating in this project you just choose to fight it.
I'm not fighting it. But I don't see any point in backing a loser. And
I'm not saying "do nothing". There are lots of productive things we
could be doing instead of wasting time on a lost cause.
Keith Thompson
> Gareth Owen a écrit :
No, you're not; you're merely misunderstanding the attitude of some
people here.
Some people have probably expressed some anti-C99 sentiments, but
the vast majority of what I think you're interpreting as anti-C99
remarks have been based entirely on the fact that C99-conforming
compilers are not universally available.
Speaking for myself, I'd like to be able to use C99 (I like some of
the features and can ignore others), but I'm hesitant to do so until
I can rely on full C99 support in the same way that I can currently
rely on full C90 support. There's very little anyone other than
an implementer can do to change that (and I applaud you for doing
your part, even though it's only helpful for Windows programming).
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Seebs
> What I want is the C equivalent: simpler, faster, that can be used
> widely and make C a better language.
Make a variant, then. Objective-C is actually pretty good; it doesn't
pretend to be C, and it works nicely.
> That would mean that there is no future for C.
No, it wouldn't.
It would mean the future for C is to stay simple.
The solution to "other languages are too complex" is not "let's add
complications to this one".
> At the same time I see many things in C++ that are very good ideas
> and I have tried to bring them to C. Software construction should be
> about that: software construction and not "group feelings"...
Again, this would be a great opportunity to explore developing a variant
language, I think. But so far, I'm not convinced that things like a
container library actually simplify things. I would rather have a list
library, and an array library, and if I have to change from one to the other,
well, then I have to change some things. Since I almost certainly want
to change a lot of things along with that restructuring, that's not really
a big problem, from my point of view.
Seebs
> is an evolution that doesn't add any new complexity to the language.
Of course it does.
The library is part of "the language".
> C remains exactly as it was before but we would have a common interface
> for using lists, hash tables, bitstrings and other containers that would
> allow that most programmers would not need to reinvent this thing
> over and over when they program in C.
I have never in my life invented that thing.
I have written a handful of list implementations, most of which would not
have been able to effectively (IMHO) use the container library. I have
written a couple of implementations of array-like things. My string library,
flawed though it may be, had perfectly adequate implementations of both lists
and flexible arrays.
> I disagree, and I believe that C is a good all purpose programming language.
> It needs to have a better library and one of the most important things
> that is missing is a common interface for containers.
Again, I disagree, because I usually find that a common interface for
containers is counterproductive for a lot of code.
See... Fundamentally, a container interface is only part of the interface.
Really, you need inheritance to do a good job, because there are things
which make sense to do to lists, but which do not make sense to do to
arrays, and vice versa. Sure, "iterate" and "add" are easy for both...
But not everything is so similar. In OO languages, you can have generic
containers, and then have lists and arrays which are also containers, but
have their own features.
You could probably do this thanks to the magic of common initial structures,
etcetera, but somewhere around there, you've basically implemented
inheritance, and if you're implementing inheritance in C, I think something's
gone wrong. And if you aren't implementing inheritance, "containers" are
the wrong layer of abstraction.
My guess is that you'd find a lot more interest in good, clean,
implementations of singly-linked and doubly-linked lists, and flexible
arrays, as three separate types of things. A container implementation
feels very much like it's too much an OO abstraction, and C's really
not the best place to do that.
Seebs
> and other containers. Since there is no standard all those programs
> have a "utilities.c" module where they have ad hoc container libraries.
No. They have ad-hoc list libraries, or ad-hoc tree libraries.
I have never seen a container library in C. Ever.
> When you merge the code bases you see that the list package A is not
> compatible with list package B. Complexity of porting increases.
Uh, no.
If you have different lists, they're used in different ways by different
code on different objects.
> When you see
> c = Get_nth(a,b);
> You do not know immedately what it does. The language is more complex
> because a common vocabulary is missing and you need to figure out
> what "Get_nth" does.
I have never seen such a function. Ever.
I've seen lists used for list-like things, in which case, no one cares about
the Nth item; they care only about iterating to find an item with a given
quality, or about finding the next item.
If someone wants get_nth(), what they do is make a an array and write a[b].
> The language is simpler if we use a common vocabulary for common tasks like
> lists.
I agree that this could, potentially, help.
However, containers are a layer of abstraction too far from what would
be useful.
> AT LAST!
>
> I do NOT need to rewrite a list package AGAIN!
I haven't had to rewrite a list package since the mid-90s; either I've
come to a project with a well-defined existing one, or I've had one of
my own lying around.
> The container library is for people that want to write THEIR software
> and not rewrite a list package AGAIN!
Make a list library, and you'll find buy-in for that, I think.
> The library is written in standard C. I do not see where I am
> doing C++. Obviously if you think that an abstraction like
> containers is too much for C then please say it so.
It is, because "container" hides crucial information about implementation
costs which is part of what C programmers expect to know about an interface.
> Of course not. "C" is not alive. The PEOPLE that use "C" are alive, and
> that is why C evolves!
The people using spanners are alive, but spanners don't seem to need to change
much.
> The passive people that are always saying that the best thing is to do
> nothing are best ignored. It is a pity that instead of collaborating
> in this project you just choose to fight it.
It's not that we should do "nothing". It's that this particular thing does
not appeal, for pretty much the same set of reasons we've pointed out all
along.
Do a good list library, and I think you'll find takers. I posted an example
of one to clc once in the mid-90s and a couple of people grabbed it and used
it.
Gareth Owen
> Sure, that looks nice. But is it very different from
>
> Vector *dv;
> // Add elements to the vector
> double mean,sum=0; int i;
> for (i=0; i<dv->count; i++) {
> sum += *(double *)dv->lpVtbl->GetElement(dv,i);
> }
> mean = sum/i;
>
> Sure, that doesn't look as pretty as C++. But it does the same.
> and, let's get real, is as clear as C++.
Really? You think a loop containing
sum += *(double *)dv->lpVtbl->GetElement(dv,i);
which has an explicit cast, two indirections and a pointer dereference
is as clear as
double mean = accumulate(vec.begin(),vec.end(),0.0) / vec.size();
I simply can't agree. Actually, I'm slightly horrified you'd even say
that. If I wrote your line, and probably refactor it into two or
three clearer statements and trust the compiler to glue it back
together. And it still wouldn't have the clarity of the C++.
Go and ask a newbie programmer who knows neither C or C++ what they
think each bit of code does.
Also, explicit casting prevents the compiler from warning about type
errors which is a worry. I like constructs that give the compiler
plenty of chance to spot when I'm doing something idiotic. (Although
the C++ version isn't immune to this. As anyone whose ever typed
vector<double> vec;
/* ... manipulate vec ... */
double mean = accumulate(vec.begin(),vec.end(),0) / vec.size();
will know.)
> But I do not want to disturb all those programmers that use C++. If
> they are happy please go on using C++. I am only proposing that in C
> we do not need to reprogram a list package for the THOUSANDTH time!
No one, I think, is arguing against code reuse (although they might
bristle at the standardisation of code they). Well, how about,
instead of pushing for standardisation, you start a project that will
become the C equivalent of Boost? Pure C89, free (in some sense) to
use and modify, bundled with lcc-win and anyone else who'll take them.
C programmers will decide whether they want them. If the demand is
there, a user community will grow up who'll greatly help your push for
standardisation. If there's no demand, standardisation would be a
waste of time.
Chris M. Thomasson
news:slrnhd9m02.aah...@guild.seebs.net...>> I do not know any. Care to explain?
>> All systems support function pointers (if not they wouldn't support C!)
>
> Again you confuse function pointers and function tables! Your comments
> in the other thread about the performance cost of virtual methods were
> totally unrelated to the question of the performance cost of function
> pointers.
>
> Function tables are certainly possibly part of a well-understood C
> interface,
> but they're usually fairly closely tied to what's being done.
> "Containers" is a very unlikely level of abstraction for a lot of use
> cases.
>
> Fundamentally, embedding a table of function pointers in an object is
> pretty
> unlikely to make it into the standard.
I think that using vtables to implement an abstract interface technique for
very simple data-structures (e.g., list, tree, array) is probably "overkill"
in most cases. I personally enjoy using intrusive data-structures; think
along the lines of:
http://groups.google.com/group/comp.lang.c/msg/533fcd7d743171c1
http://groups.google.com/group/comp.lang.c/msg/78308e18a53da752
Chris M. Thomasson
news:hb54t4$rc0$1...@aioe.org...
> Seebs a �crit :
>> On 2009-10-14, jacob navia <ja...@nospam.org> wrote:
>>> The problem with specific designs, is exactly that. They are specific.
>>> In C, if you start with a container like a list for instance, you are
>>> married with that container forever. Changing the container because the
>>> list has grown too long is highly expensive in reprogramming time.
>>
>> Yes, it is.
>>
>> But that's the thing -- if you don't think a list is the right structure,
>> you don't use one.
>
> A list is the right structure when it doesn't grow too much. But you
> know as well as everybody else that requirements change, and data
> tends to grow, and that list that was OK for 500 elements it just
> doesn't cut it with 5000: you need a better list, with better
> heap management that doesn't call malloc for each element to
> be added to the list. And then the list is out when you need
> 50000 elements. You need an array that is flexible, etc.
>
> At each change you need to rewrite all data access!
Nit pick: Not all data-structures are compatible with every access pattern.
Perhaps the programmer wants a double linked-list because she will be
frequently adding and removing objects from random locations. In this case,
the access pattern is "built in" and changing to another structure with
different complexity for the normal access pattern can drastically reduce
performance.
Also, can I specify exactly how much memory one of you're containers will
use? Perhaps I need to make sure that the container only allocate memory
residing on the calling threads stack:
char buffer[8192];
list = list_create(sizeof(foo), buffer);
[...]
list_destroy(list);
I can eaisly do this with simple intrusive container:
http://groups.google.com/group/comp.lang.c/msg/533fcd7d743171c1
and simple region allocator:
You can use it like:
_________________________________________________________________
#include <ralloc.h>
struct foo {
struct foo* next;
};
void crunch() {
char local_buffer[1024];
struct region local_region;
struct foo* head1 = NULL;
struct foo* head2 = NULL;
size_t i, r;
rinit(&local_region, local_buffer, sizeof(local_buffer));
for (r = 0; r < 1024; ++r) {
size_t c = 0;
for (i = 0; i < 64; ++i) {
struct foo* foo = ralloct(&local_region, 2, struct foo);
if (foo) {
foo->next = head1;
head1 = foo;
++foo;
foo->next = head2;
head2 = foo;
c += 2;
}
}
while (head1) {
head1 = head1->next;
--c;
}
while (head2) {
head2 = head2->next;
--c;
}
assert(! c);
rflush(&local_region);
}
}
int main(void) {
crunch();
crunch();
crunch();
return 0;
}
_________________________________________________________________
IMVHO, that's kind of cool... ;^)
BTW, the alignment hack is fairly nasty! Try not to throw up to much...
Anyway, can I use custom allocator for you're containers?
Seebs
> I think that using vtables to implement an abstract interface technique for
> very simple data-structures (e.g., list, tree, array) is probably "overkill"
> in most cases. I personally enjoy using intrusive data-structures; think
> along the lines of:
Interesting! I hadn't thought of the CONTAINS() hack, so it hadn't
occurred to me to try it that way. My solution, which is a bunch simpler
but not as flexible, was to define 'struct list' as starting with a
'struct list *next'... Then if 'struct foo' starts with 'struct foo *', you
can cast it to a list and everything works.
Your solution is prettier, I think.
Nick Keighley
> >> On 2009-10-14, jacob navia <ja...@nospam.org> wrote:
> >>> The problem with specific designs, is exactly that. They are specific.
> >>> In C, if you start with a container like a list for instance, you are
> >>> married with that container forever. Changing the container because the
> >>> list has grown too long is highly expensive in reprogramming time.
But you shouldn't have exposed your choice of data structure to the
application
level code anyway. It all should have been hidden away behind an
abstraction
anyway. The application wants to add things, remove things and find
things
it shouldn't care if it's an array, a linked list or a relational
database.
Changeing the container type is not expensive becasue it involves
rewriting
one thin library.
> >> Yes, it is.
>
> >> But that's the thing -- if you don't think a list is the right structure,
> >> you don't use one.
>
> > A list is the right structure when it doesn't grow too much.
>
> Only if your access pattern is list like.
You may not know how big the system is going to get. Or you may
be concentrating on getting other things right first. If things
are being addded and removed semi-randomly than a balanced tree
may be the right thing but an array ot list might be ok for a first
hack.
> > But you
> > know as well as everybody else that requirements change, and data
> > tends to grow, and that list that was OK for 500 elements it just
> > doesn't cut it with 5000: you need a better list, with better
> > heap management that doesn't call malloc for each element to
> > be added to the list.
>
> It's not necessarily the size, it might be frequency of addition. If the
> program runs for a year adding 100 elements to the list per day then the
> overhead of malloc might not be significant.
>
> > And then the list is out when you need
> > 50000 elements. You need an array that is flexible, etc.
>
> Hmm. Inserting an element half way through could be problematic.
>
> > At each change you need to rewrite all data access!
Which a well-designed program confines to a small part of the code.
You should only be caught by this once (at worst) because after that
you
will have Refactored Mercilessly.
> I've not had any data usage change by that much. I would consider it to
> be a sign that it was not well specified in the first place.
I've seen an application scale from a handful of thingies (an
important
measure of the system's load) to thousands of thingies. Admittedly
this
was known from the start.
<snip>
> >>> Access and usage of the container are too visible. If you want to
> >>> replace
> >>> the list with a flexible array you have to rewrite all accesses to the
> >>> data. An error prone and cumbersome approach.
>
> >> Often true -- but if a flexible array fit, you probably shouldn't have
> >> used a list in the first place.
>
> > It depends on the application state, and whether that is critical or not.
> > And those conditions change.
yes
> I've never had them change that much. If it might happen that I would
> possibly design a suitable flexible interface.
I think Jacob wants the flexibility in his library. Note even with C++
which has a set of generic containers I would still say hide the
choice
of container from the application code.
<snip>
> >> And yes, C is a low-level language these days, and I don't think it is
> >> necessarily a good idea to try to change that. As the man says: If
> >> you want C++, you know where to find it.
>
> > Well, here we come to the central point in this discussion. Any
> > improvement in C is considered harmful to C++ that should be the "better C".
This is comp.lang.c we don't care about harming C++. This is just your
weird
paranoia speaking.
> No it isn't. It just happens that a number of improvements you have
> suggested have not been considered appropriate by a lot of people.
>
> I happen to consider the addition of threading support to the C standard
> to be interesting.
>
> > I do not see why C should be destroyed because it is a simpler language.
<yawn>
> It isn't.
>
> > In this race to complexity C remains very easy to learn and use. Contrary to
> > you, I think C++ is not the solution because precisely of its complexity.
C++ does seem to be a bit of a monster. I think this is one reason
people resist adding complexity to C. I'm not sure I completly agree
with
them, but I see where they are coming from.
> I'm not fond of what I've seen of C++, so I would probably pick one of
> the other many languages out there if I wanted the kinds of features you
> are proposing.
>
> > The library I presented [...] is a proposal for a standard way to use
> > containers what would give C a boost.
I think the C++ already took that name :-)
<snip>
> > It is an interesting development, it is precisely about C, and we could
> > discuss in a concrete fashion many things that we never mention but are hugely
> > important for software construction in C:
>
> You seem to think that discussing something means agreeing with you.
yes
> > o Interface to the allocator: how could we abstract it?
> > (malloc/gc_malloc/alloca)
>
> For my usage, malloc is abstract enough. I don't need GC, and have never
> seen a need for alloca (I don't have a need for flexible arrays either).
flexible arrays can be nice. I'd hide the malloc() in a library.
> > o Software specialization and subclassing (This was the original theme I
> > wanted to discuss with "Adapting software to multiple usage patterns")
>
> I can't say I've a need for that, not in the was you are doing it. I do
> have stuff with indirection through function pointers, but that is not
> working in the same [way] as your interface.
I've done similar-ish things but not with containers. It doesn't feel
right.
The C++ invented a whole major language construct (templates) to avoid
using inheritance (which is what your function pointers look like) to
implement containers.
> > o Error handling and software interrupts.
>
> Those are different topics.
>
> > Etc. The container library give us an opportunity to discuss all this
> > stuff but not many people seem interested in C in comp.lang.c
>
> Plenty of people are interested in C, just not in your container library.
If you aren't for me you must be against me...
Phil Carmody
> On 2009-10-15, Chris M. Thomasson <n...@spam.invalid> wrote:
>> I think that using vtables to implement an abstract interface technique for
>> very simple data-structures (e.g., list, tree, array) is probably "overkill"
>> in most cases. I personally enjoy using intrusive data-structures; think
>> along the lines of:
>
> Interesting! I hadn't thought of the CONTAINS() hack, so it hadn't
> occurred to me to try it that way. My solution, which is a bunch simpler
> but not as flexible, was to define 'struct list' as starting with a
> 'struct list *next'... Then if 'struct foo' starts with 'struct foo *', you
> can cast it to a list and everything works.
>
> Your solution is prettier, I think.
His solution is just like container_of() from the linux kernel -
used absolutely everywhere. It permits items to be on several lists,
which I consider to be an essential feature of any library (given
that it has no overhead compared to being on only one list). In
comparison to the linux container_of(), however, Chris's solution
is the bloody mona lisa.
However, I can't say that having SLIST_INIT as a noun and slist_init
as a verb is my kind of thing.
Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
Nick Keighley
> Gareth Owen a écrit :
> > jacob navia <ja...@nospam.org> writes:
<snip>
> > And, because the vtable is explicit, and users are encouraged to alter
> > it (to create polymorphic behaviour), the compiler is likely to be
> > able to make fewer.
>
> I suppose you meant "fewer optimizations". Yes, but it has already
> more or less 20-30% more speed than the C++ containers and uses
> more or less the same memory for huge lists of 50 million items.
Now this surprises me! I would have thought a C++ would be able
to get more speed out of template code than your explicit vtable
could achieve. But empirical measurement trumps "I would have thought"
every time!
> With specialization it can have more speed than C++ can ever attain.
again, I'm surprised.
<snip>
> > Now, anyone who wants containers and wants to use manipulate using a
> > language that is close enough to C to leverage their skill, is using
> > C++ containers.
>
> Obviously since there is no C container library :-)
>
> > They're standardised, they're at least as flexible as
> > your containers (you can replace the default memory allocator, much as
> > you've proposed), they're on a colossal number of platforms, they're
> > logical const-ness is supported by the language (as opposed to your
> > "read-only" toggle) and you get all the things in <algorithm>
> > (std::transform, max_element etc), well defined copying semantics
> > (std::swap specialisation) etc etc etc.. for free.
<snip>
> And yes, "algorithm" part is surely not going to be ported to C...
> most people I know using C++ never use that part of the STL and just have
> a blank stare when I mention it... Too complex!
I never thought it was "complex" just seemed unnecessary hassle
(I'd have to look it up) to do very little. I've used some of the
search
thingies from <algorithm>
> > Oh, and if you're
> > willing to use iterators (whose syntax can be, I grant you, also
> > hideously ugly), you can swap container types with relative ease.
I'd never thought swopping containers was *that* easy.
> Sure. You see, why then can't we do it in C? Why only in C++?
I'm not sure you can do it *even* in C++
> Let's do it in C because is much SIMPLER since everything is open
> for you to examine and modify.
Sometimes it's better if some of the machinary is hidden.
> The vtable is not a mystery that
> only compiler people know about. It is there, open for you to hack
> as you wish.
>
> > Regardless of the merits of your library, in terms of standardisation,
> > that ship has long sailed.
>
> That would mean that there is no future for C. And, as I have stated many
> times, I do not believe that.
and as other people have said many times, resisting the piling on of C+
+
features to C does not mean that C has no future.
> A simpler language is better than a complex one.
That needs decorating with a few weasel words. If it were universally
so
then we'd all be programing in cut-down Pacal. Darmouth BASIC anyone?
> Why?
>
> Because, contrary to the exponential growth of hardware, brain hardware
> is kind of FIXED, and there is a much smaller limit to the amount of
> computer language trivia that your brain is able to swallow without
> indigestion.
The way to handle complexity is with abstraction. This is engineering
101
> That ship has long sailed and C++ has grown beyond what a human being
> can understand. Not even the creator of the language can introduce a
> modification now, because the complexity of C++ is beyond what he
> himself can manage. After several years working on "concepts", he was
> forced to accept that he can't do it... The "concepts" debacle show
> us that complexity grows without limit and eventually it makes the
> whole language impossible to use correctly.
I wasn't sure if I should laugh or cry over concepts. Trouble is large
chunks of the new standard are heavily based on the presumption that
concepts *could* be made to work.
> What I want is to go on developing C. You can make a positive contribution
> here, if you wish. You can propose things, and I am not a zealot that
> will start fighting language wars. I have to use C++ at work, and
> that is why I am more and more convinced that the future is C and
> not C++.
>
> At the same time I see many things in C++ that are very good ideas
> and I have tried to bring them to C. Software construction should be
> about that: software construction and not "group feelings"...
I like constructors, destructors, exceptions (though exception safe
code
is "fun"), and the container library. Extensible io streams have
their
good points but somehow don't feel quite "right"
> Thanks for your contribution.
--
"If you think C++ is not overly complicated, just what is a protected
abstract virtual base pure virtual private destructor, and when
was the last time you needed one?"
-- Tom Cargil, C++ Journal.
In the development of the understanding of complex phenomena,
the most powerful tool available to the human intellect is
abstraction. Abstraction arises from the recognition of similarities
between certain objects, situations, or processes in the real world
and the decision to concentrate on these similarities and to ignore,
for the time being, their differences.
- C.A.R. Hoare
Nick Keighley
> In <hb5bep$5h...@aioe.org>, jacob navia wrote:
<snip>
> > Nothing is ever "complete", unless it is dead.
>
> Here I have to disagree. Just because something no longer changes,
> that doesn't mean it's of no use. I have a five-eighths spanner which
> I've owned for over twenty years. It hasn't changed at all over those
> twenty years, but it still does its job perfectly well.
and your grandfather would have recognised it
<snip>
> [...] C isn't a living creature. It's a formal
> system (or at least it's reasonably close to being a formal system).
Isn't that on par with "only a little bit pregnant?"
<snip>
jacob navia
> jacob navia <ja...@nospam.org> writes:
>
>> Sure, that looks nice. But is it very different from
>>
>> Vector *dv;
>> // Add elements to the vector
>> double mean,sum=0; int i;
>> for (i=0; i<dv->count; i++) {
>> sum += *(double *)dv->lpVtbl->GetElement(dv,i);
>> }
>> mean = sum/i;
>>
>> Sure, that doesn't look as pretty as C++. But it does the same.
>> and, let's get real, is as clear as C++.
>
> Really? You think a loop containing
>
> sum += *(double *)dv->lpVtbl->GetElement(dv,i);
>
> which has an explicit cast, two indirections and a pointer dereference
> is as clear as
>
> double mean = accumulate(vec.begin(),vec.end(),0.0) / vec.size();
>
> I simply can't agree.
Of course, you are used to C++. And you are willing to pay for it.
(1) You can hide all that complexity with the macro I suggested
that hides everything in a clear fashion:
for (i=0; GetCountVector(dv); i++) {
sum += GetElementVector(dv,i,double);
}
I haven't used those macros because I think C programmers should be
used to complex expressions...
(2) C++ does exactly the same thing under the hood.
> Actually, I'm slightly horrified you'd even say
> that. If I wrote your line, and probably refactor it into two or
> three clearer statements and trust the compiler to glue it back
> together. And it still wouldn't have the clarity of the C++.
>
Maybe. But this is a question of a larger context. The problem with
the "clarity" of C++ is that it has a high COST, that you pay at
each usage. The cost of a much more complex language.
But let's stop this language war right here. In C, you have explicit
casts because no other type of cast is there.
I repeat:
>> I do not want to disturb all those programmers that use C++. If
>> they are happy please go on using C++. I am only proposing that in C
>> we do not need to reprogram a list package for the THOUSANDTH time!
I am not trying to steal "market share" from C++. It is there and has good
and bad features. I just want to improve C.
>
> No one, I think, is arguing against code reuse (although they might
> bristle at the standardisation of code they). Well, how about,
> instead of pushing for standardisation, you start a project that will
> become the C equivalent of Boost? Pure C89, free (in some sense) to
> use and modify, bundled with lcc-win and anyone else who'll take them.
I am doing exactly that.
> C programmers will decide whether they want them. If the demand is
> there, a user community will grow up who'll greatly help your push for
> standardisation. If there's no demand, standardisation would be a
> waste of time.
Well, that is what I am trying to do.
Thanks for your participation.
Richard Heathfield
Nick Keighley wrote:
> On 14 Oct, 21:42, Richard Heathfield <r...@see.sig.invalid> wrote:
>> In <hb5bep$5h...@aioe.org>, jacob navia wrote:
>
> <snip>
>
>> > Nothing is ever "complete", unless it is dead.
>>
>> Here I have to disagree. Just because something no longer changes,
>> that doesn't mean it's of no use. I have a five-eighths spanner
>> which I've owned for over twenty years. It hasn't changed at all
>> over those twenty years, but it still does its job perfectly well.
>
> and your grandfather would have recognised it
Yes.
> <snip>
>
>> [...] C isn't a living creature. It's a formal
>> system (or at least it's reasonably close to being a formal
>> system).
>
> Isn't that on par with "only a little bit pregnant?"
Permaybehaps. I think if you focus only on the subset of C that always
exhibits well-defined behaviour (i.e. ignore all programs that invoke
UB or USB or IDB), it's not unreasonable to call that subset a formal
system.
Nick Keighley
> On 2009-10-14, jacob navia <ja...@nospam.org> wrote:
<snip>
> > When you merge the code bases you see that the list package A is not
> > compatible with list package B. Complexity of porting increases.
>
> Uh, no.
>
> If you have different lists, they're used in different ways by different
> code on different objects.
until you want to move stuff from one part of the code to another.
I know a program that has three different sorts of string. It's
irritating.
<snip>
> > The passive people that are always saying that the best thing is to do
> > nothing are best ignored. It is a pity that instead of collaborating
> > in this project you just choose to fight it.
>
> It's not that we should do "nothing". It's that this particular thing does
> not appeal, for pretty much the same set of reasons we've pointed out all
> along.
we must do something, this is something therefore we must do it.
Also known as TINA, There Is No Alternative
Tim Rentsch
> In <3f1b84db-3cfb-47c0...@l9g2000yqi.googlegroups.com>,
> Nick Keighley wrote:
>
>> On 14 Oct, 21:42, Richard Heathfield <r...@see.sig.invalid> wrote:
>>>[snip]
>>>
>>> [...] C isn't a living creature. It's a formal
>>> system (or at least it's reasonably close to being a formal
>>> system).
>>
>> Isn't that on par with "only a little bit pregnant?"
>
> Permaybehaps. I think if you focus only on the subset of C that always
> exhibits well-defined behaviour (i.e. ignore all programs that invoke
> UB or USB or IDB), it's not unreasonable to call that subset a formal
> system.
Now there's a laugh. C has nothing even vaguely resembling
a formal semantics.
Richard Heathfield
> Richard Heathfield <r...@see.sig.invalid> writes:
<snip>
>> I think if you focus only on the subset of C that
>> always exhibits well-defined behaviour (i.e. ignore all programs
>> that invoke UB or USB or IDB), it's not unreasonable to call that
>> subset a formal system.
>
> Now there's a laugh. C has nothing even vaguely resembling
> a formal semantics.
I guess I'm a lot less fussy about what I am prepared to accept as a
Nick Keighley
> In <3f1b84db-3cfb-47c0-91f0-36adfc934...@l9g2000yqi.googlegroups.com>,
> Nick Keighley wrote:
> > On 14 Oct, 21:42, Richard Heathfield <r...@see.sig.invalid> wrote:
> >> C [is] a formal system (or at least it's reasonably close to being a
> >> formal system).
>
> > Isn't that on par with "only a little bit pregnant?"
>
> Permaybehaps. I think if you focus only on the subset of C that always
> exhibits well-defined behaviour (i.e. ignore all programs that invoke
> UB or USB or IDB), it's not unreasonable to call that subset a formal
> system.
I'm not sure the undefined behaviour is a big problem. Mathematical
functions are not defined for certain inputs and that doesn't seem to
upset the mathematicians. I think Cs informality comes because pretty
much all the semantics are defined in english.
Nick Keighley
> On 2009-10-14, jacob navia <ja...@nospam.org> wrote:
> > [C] needs to have a better library and one of the most important things
> > that is missing is a common interface for containers.
>
> Again, I disagree, because I usually find that a common interface for
> containers is counterproductive for a lot of code.
>
> See... Fundamentally, a container interface is only part of the interface.
> Really, you need inheritance to do a good job,
really? I thought C++ demonstrated that you don't need inheritance for
a decent set of containers.
> because there are things
> which make sense to do to lists, but which do not make sense to do to
> arrays, and vice versa.
...which is poorly modelled by inheritance
> Sure, "iterate" and "add" are easy for both...
> But not everything is so similar. In OO languages, you can have generic
> containers, and then have lists and arrays which are also containers, but
> have their own features.
which is not how C++ did it...
> You could probably do this thanks to the magic of common initial structures,
> etcetera, but somewhere around there, you've basically implemented
> inheritance, and if you're implementing inheritance in C, I think something's
> gone wrong. And if you aren't implementing inheritance, "containers" are
> the wrong layer of abstraction.
>
> My guess is that you'd find a lot more interest in good, clean,
> implementations of singly-linked and doubly-linked lists, and flexible
> arrays, as three separate types of things. A container implementation
> feels very much like it's too much an OO abstraction, and C's really
> not the best place to do that.
[rambling stream-of-conciousness-stuff follows]
C++ mostly uses template instantiation to do containers but it does
rely on
objects having common properties (copyable, assignable, comparable
etc) and
the way C++ does that probably relies on inheritance. Hmm. perhaps
not.
perhaps you could do a template thingy without inheritance. It's a
common
interface you need rather than inheritance (just because C++ does
interfaces
via inheritance doesn't mean you have to do it that way)
gwowen
> Of course, you are used to C++.
No. It's because I know what the english noun "vector",
means, and what "begin", "end" and "accumulate" mean.
One does not have to know C++ to deduce the meaning
VALUE = ACCUMULATE(BEGIN_OF_VECTOR END_OF_VECTOR)
Any programmer of any language can deduce what that means.
I'd expect a bright non-programmer to have a bloody good
stab at it. Can you make the same assertions about your
"equally clear" code?
> And you are willing to pay for it.
You have not demonstrated how I pay for it.
> I haven't used those macros because I think C programmers should be
> used to complex expressions...
Really? Complex expressions are error prone and tend to be opaque.
I am used to complex expressions, but I stay away from them unless
I have to. If I can express complex ideas with simple syntax ...
well, I don't consider that disadvantage.
> (2) C++ does exactly the same thing under the hood.
Of course it does. (And yet you claim, without measurement, that
yours is faster. I remain dubious of this claim.) But the fact
that it is under the hood makes my life easier. It's a benefit
to me that I can start it with a key and not a crank-handle.
It's a benefit to me that I can access things in a container
without having to use two indirections, a cast and a dereference.
> Maybe. But this is a question of a larger context. The problem with
> the "clarity" of C++ is that it has a high COST, that you pay at
> each usage. The cost of a much more complex language.
You have not demonstrated this cost to me. It's a cost for
implementors, but I'm not an implementor. On the contrary.
C++ hides the implentation. This means that my program is clearer,
less error prone, more typesafe. And, because
I'm not allowed to mess with the vtable[0], the code can inline many
of the calls for which your library must use an (explicit) function
pointer.
The standard is more complex (brutally so) but my program is simpler.
> But let's stop this language war right here. In C, you have explicit
> casts because no other type of cast is there.
Well yes, but a container library that requires its user to cast the
results at every step is inconvenient to use and error prone.
[0] In fact, of course, C++ containers use templates not inheritance,
so vector<int> does not even use a vtable. They use template-ised
name-mangled direct function calls, so they don't use function
pointers at all. All the function resolution is done at compile/link
time. So, even without inlining, these direct function calls tend to
be quicker than calls through function pointers.
So your "C++ does the same thing under the hood" is not even accurate.
bartc
"Gareth Owen" <gwo...@gmail.com> wrote in message
news:87skdlg...@linux-8rq8.site...
> jacob navia <ja...@nospam.org> writes:
>
>> Sure, that looks nice. But is it very different from
>>
>> Vector *dv;
>> // Add elements to the vector
>> double mean,sum=0; int i;
>> for (i=0; i<dv->count; i++) {
>> sum += *(double *)dv->lpVtbl->GetElement(dv,i);
>> }
>> mean = sum/i;
>>
>> Sure, that doesn't look as pretty as C++. But it does the same.
>> and, let's get real, is as clear as C++.
>
> Really? You think a loop containing
>
> sum += *(double *)dv->lpVtbl->GetElement(dv,i);
>
> which has an explicit cast, two indirections and a pointer dereference
> is as clear as
>
> double mean = accumulate(vec.begin(),vec.end(),0.0) / vec.size();
You're not comparing like with like. The two statements do different things,
if I've deduced the meaning of the second one correctly.
What is the exact equivalent using your syntax? I suspect it might make your
point better because the first statement uses an extemely ugly way of
indexing an array or list so it can't be that bad even for C++!
--
Bartc
Chris M. Thomasson
news:korhq6x...@news.flash-gordon.me.uk...
> jacob navia wrote:
>> Seebs a �crit :
>>> On 2009-10-14, jacob navia <ja...@nospam.org> wrote:
>>>> The problem with specific designs, is exactly that. They are specific.
>>>> In C, if you start with a container like a list for instance, you are
>>>> married with that container forever. Changing the container because the
>>>> list has grown too long is highly expensive in reprogramming time.
>>>
>>> Yes, it is.
>>>
>>> But that's the thing -- if you don't think a list is the right
>>> structure,
>>> you don't use one.
>>
>> A list is the right structure when it doesn't grow too much.
>
> Only if your access pattern is list like.
Yes! Sorry for basically repeating you're statement.
gwowen
> "Gareth Owen" <gwo...@gmail.com> wrote in message
>
Well, I first introduced this example, and I did so merely to note
that Jacob's container forced a relatively ugly syntax.
The explicit loop C++ version would be something like this,
for a vector:
double mean = 0.0;
const size_t sz = vec.size();
for(size_t idx = 0; idx < sz; ++idz){
mean += vec[idx];
}
mean = mean / vec.size();
For an arbitrary container (substitute your container for list)
double mean = 0.0;
list<double>::iterator cntr, end = cntr.end();
for(it = cntr.begin(); it != end; ++it){
mean += *it;
}
mean = mean / vec.size();
Gareth Owen
> double mean = 0.0;
> list<double>::iterator cntr, end = cntr.end();
Oops. This should read
list<double> cntr;
list<double>::iterator it, end = cntr.end();
Seebs
> But you shouldn't have exposed your choice of data structure to the
> application
> level code anyway. It all should have been hidden away behind an
> abstraction
> anyway. The application wants to add things, remove things and find
> things
> it shouldn't care if it's an array, a linked list or a relational
> database.
> Changeing the container type is not expensive becasue it involves
> rewriting
> one thin library.
I don't agree with this necessarily. Data structures and algorithms are
closely tied. In some cases, knowing about the data structure's performance
characteristics is important in deciding how to use a data structure.
I have a bunch of things to add. Does it matter whether I try to add them
to the head or the tail of the list? Depending on the data structure, the
answer is a definite "maybe".
> You may not know how big the system is going to get. Or you may
> be concentrating on getting other things right first. If things
> are being addded and removed semi-randomly than a balanced tree
> may be the right thing but an array ot list might be ok for a first
> hack.
Sure. But there is a real chance that, once you know what you want to do,
your code will want to be adapted to the performance characteristics of
the suitable data structure, not just using it blindly.
> Which a well-designed program confines to a small part of the code.
> You should only be caught by this once (at worst) because after that
> you
> will have Refactored Mercilessly.
Unless you've profiled, and this data library is consuming 15% of your CPU
time, and tweaking for a specific implementation can reduce that to 5%...
Seebs
>> See... Fundamentally, a container interface is only part of the interface.
>> Really, you need inheritance to do a good job,
> really? I thought C++ demonstrated that you don't need inheritance for
> a decent set of containers.
Well, the minimal case, as I see it:
Container <-- general operations
Array <-- array-friendly stuff, plus it's a container
List <-- list-friendly stuff, plus it's a container
Sounds inheritancy to me.
> ...which is poorly modelled by inheritance
Perhaps.
> which is not how C++ did it...
C++ isn't really an OO language.
> perhaps you could do a template thingy without inheritance. It's a
> common
> interface you need rather than inheritance (just because C++ does
> interfaces
> via inheritance doesn't mean you have to do it that way)
True.
But you need some kind of way to specify the "one of these is also one
of those" type relations, so that code can take a container whether it's
a list or an array, and that starts getting suspiciously similar to the
territory of inheritance and such.
jacob navia
> ... you need some kind of way to specify the "one of these is also one
> of those" type relations, so that code can take a container whether it's
> a list or an array, and that starts getting suspiciously similar to the
> territory of inheritance and such.
>
If you use
container->lpVtbl->GetElement(container,index);
you can use it with lists, arraylists (flexible arrays) and all
*sequential* containers.
I would make the distinction at the top level between sequential
containers (lists, arrays, arraylists, and maybe others) and
non sequential ones like hash tables for instance, where the idea of
"the item 42" doesn't make any sense.
I would call this just grouping, not inheritance since there
are shared characteristics but not a class hierarchy.
Trees and graphs would be another type of containers, of course
completely different (and with a complete different access methods)
than sequential containers.
Flash Gordon
> On 14 Oct, 22:17, Flash Gordon <s...@spam.causeway.com> wrote:
>> jacob navia wrote:
>>>> On 2009-10-14, jacob navia <ja...@nospam.org> wrote:
>
>>>>> The problem with specific designs, is exactly that. They are specific.
>>>>> In C, if you start with a container like a list for instance, you are
>>>>> married with that container forever. Changing the container because the
>>>>> list has grown too long is highly expensive in reprogramming time.
>
> But you shouldn't have exposed your choice of data structure to the
> application
> level code anyway. It all should have been hidden away behind an
> abstraction
> anyway. The application wants to add things, remove things and find
> things
> it shouldn't care if it's an array, a linked list or a relational
> database.
It depends. In some cases I'm thinking of we really do hit 100% CPU
utilisation on fairly meaty servers, adding an extra layer of
indirection for frequently accessed objects would probably impact on
performance of the code quite significantly (an extra indirection every
few lines of C code). Because of the frequency of access, there is no
chance of them every being stored in a database (there would be no
chance of getting required performance), by nature of design they are
loaded once at application start up, and then frequently accessed in a
random pattern (some lines of code access specific elements, others loop
over blocks of elements, others select elements based on user entered
data meaning we want the nth element. To me this screams out for using
malloc/realloc on loading the data in to contiguous blocks and then
accessing the required elements using array/pointer access, never tree,
list or database access.
> Changeing the container type is not expensive becasue it involves
> rewriting
> one thin library.
Well, yes, where you are doing certain types of things you do wrap it in
an appropriate library, and then only need to change that one small library.
>>>> Yes, it is.
>>>> But that's the thing -- if you don't think a list is the right structure,
>>>> you don't use one.
>>> A list is the right structure when it doesn't grow too much.
>> Only if your access pattern is list like.
>
> You may not know how big the system is going to get.
If your access pattern is that you regularly expect to access the nth
element, where n is a number which can be determined without iterating
over the elements, then I would say that a list is definitely the wrong
structure however small or large your data set is.
> Or you may
> be concentrating on getting other things right first. If things
> are being addded and removed semi-randomly than a balanced tree
> may be the right thing but an array ot list might be ok for a first
> hack.
If you know what you are doing is a temporary hack then you will
implement it in a way that you can strip it out and replace it.
<snip>
>> I've not had any data usage change by that much. I would consider it to
>> be a sign that it was not well specified in the first place.
>
> I've seen an application scale from a handful of thingies (an
> important
> measure of the system's load) to thousands of thingies. Admittedly
> this
> was known from the start.
In which case the expected usage was a known range, and I'm sure it was
designed with that in mind.
>>>>> Access and usage of the container are too visible. If you want to
>>>>> replace
>>>>> the list with a flexible array you have to rewrite all accesses to the
>>>>> data. An error prone and cumbersome approach.
>>>> Often true -- but if a flexible array fit, you probably shouldn't have
>>>> used a list in the first place.
>>> It depends on the application state, and whether that is critical or not.
>>> And those conditions change.
>
> yes
>
>> I've never had them change that much. If it might happen that I would
>> possibly design a suitable flexible interface.
>
> I think Jacob wants the flexibility in his library. Note even with C++
> which has a set of generic containers I would still say hide the
> choice
> of container from the application code.
As I say, Ive never needed to do such drastic change in data structure.
Whenever I've used a list (single linked, double linked, or something
more strange and complex) that has always need what it has needed to
stay as. I've occasionally had to move something from being an array to
being an allocated block, but with the magic of C that just changes
things at the points of creation and destruction, but the code accessing
it is unchanged.
<snip>
>>> o Interface to the allocator: how could we abstract it?
>>> (malloc/gc_malloc/alloca)
>> For my usage, malloc is abstract enough. I don't need GC, and have never
>> seen a need for alloca (I don't have a need for flexible arrays either).
>
> flexible arrays can be nice. I'd hide the malloc() in a library.
Well, I do actually have my malloc calls wrapped, but that is wrapped in
something that provides the application code with the same interface.
>>> o Software specialization and subclassing (This was the original theme I
>>> wanted to discuss with "Adapting software to multiple usage patterns")
>> I can't say I've a need for that, not in the was you are doing it. I do
>> have stuff with indirection through function pointers, but that is not
>> working in the same [way] as your interface.
>
> I've done similar-ish things but not with containers. It doesn't feel
> right.
> The C++ invented a whole major language construct (templates) to avoid
> using inheritance (which is what your function pointers look like) to
> implement containers.
<snip>
Actually I was thinking of a library where the application code calls
explicit functions, and a fair way down the call graph in the library it
goes through function pointers to database specific functions so we can
select the database type at run time. However, that is deeply embedded
in the library and no where near the level of application code.
--
Flash Gordon
jacob navia
>
> Actually I was thinking of a library where the application code calls
> explicit functions, and a fair way down the call graph in the library it
> goes through function pointers to database specific functions so we can
> select the database type at run time. However, that is deeply embedded
> in the library and no where near the level of application code.
I thought about that by using a generic creation function for each container
that would receive a set of flags specifying the size of the container
(huge, big, normal, small tiny) and the creation function would choose
according to the flags which vtable to set into the new list.
The interface of all those function would still be exactly the same, the
algorithms would be quite different of course.
For big lists we would use a heap manager, for normal lists malloc at
each element and for tiny lists we would allocate all the elements at once
That is what I proposed with the theme of this thread:
Seebs
> If you use
> container->lpVtbl->GetElement(container,index);
Which I wouldn't. If I were implementing this, I'd make it something
like:
static inline ctr_getelement(container *x, int index) {
x->vtable->getelement(x, index);
}
and write
ctr_getelement(x, index);
... Because C does not use camel case.
> you can use it with lists, arraylists (flexible arrays) and all
> *sequential* containers.
And what iteration model does it use? Is it more appropriate to
write
ctr_getlement(x, index);
or
ctr_next(x, ... what goes here?);
or..
You see the issue. To write reasonable code, I actually usually want to
know how to iterate.
Which is why my list library had an "iterate" operation.
Flash Gordon
> Seebs a �crit :
>> ... you need some kind of way to specify the "one of these is also one
>> of those" type relations, so that code can take a container whether it's
>> a list or an array, and that starts getting suspiciously similar to the
>> territory of inheritance and such.
>
> If you use
>
> container->lpVtbl->GetElement(container,index);
>
> you can use it with lists, arraylists (flexible arrays) and all
> *sequential* containers.
>
> I would make the distinction at the top level between sequential
> containers (lists, arrays, arraylists, and maybe others) and
> non sequential ones like hash tables for instance, where the idea of
> "the item 42" doesn't make any sense.
Ive wanted to iterate over all the elements of a hash in a language
which has hashes natively, whilst at other points using it as a hash. If
you can iterate over it, then there is a concept of "the item 42" (even
if the order is not obvious, as long as it is consistent on any instance
of a hash whilst it exists between modifications). The same can apply to
trees (where there is a more obvious ordering).
> I would call this just grouping, not inheritance since there
> are shared characteristics but not a class hierarchy.
The container concept can be thought of as the base class with the lists
implementation being derived from it, even if that is not how you have
implemented it.
> Trees and graphs would be another type of containers, of course
> completely different (and with a complete different access methods)
> than sequential containers.
It's not unusual to want to want to do a tree traversal where you are
iterating over all the elements of the tree.
--
Flash Gordon
Flash Gordon
> Seebs a �crit :
>> ... you need some kind of way to specify the "one of these is also one
>> of those" type relations, so that code can take a container whether it's
>> a list or an array, and that starts getting suspiciously similar to the
>> territory of inheritance and such.
>
> If you use
>
> container->lpVtbl->GetElement(container,index);
>
> you can use it with lists, arraylists (flexible arrays) and all
> *sequential* containers.
>
> I would make the distinction at the top level between sequential
> containers (lists, arrays, arraylists, and maybe others) and
> non sequential ones like hash tables for instance, where the idea of
> "the item 42" doesn't make any sense.
Ive wanted to iterate over all the elements of a hash in a language
which has hashes natively, whilst at other points using it as a hash. If
you can iterate over it, then there is a concept of "the item 42" (even
if the order is not obvious, as long as it is consistent on any instance
of a hash whilst it exists between modifications). The same can apply to
trees (where there is a more obvious ordering).
> I would call this just grouping, not inheritance since there
> are shared characteristics but not a class hierarchy.
The container concept can be thought of as the base class with the lists
implementation being derived from it, even if that is not how you have
implemented it.
> Trees and graphs would be another type of containers, of course
> completely different (and with a complete different access methods)
> than sequential containers.
It's not unusual to want to want to do a tree traversal where you are
Seebs
> Ive wanted to iterate over all the elements of a hash in a language
> which has hashes natively, whilst at other points using it as a hash. If
> you can iterate over it, then there is a concept of "the item 42" (even
> if the order is not obvious, as long as it is consistent on any instance
> of a hash whilst it exists between modifications). The same can apply to
> trees (where there is a more obvious ordering).
In ruby/perl, it's definitely possible for order to vary with modifications,
but I'm not even sure it's impossible for order to vary without
externally-visible modifications.
Imagine a hypothetical implementation where the hash may, under some
non-obvious circumstances, choose to restructure itself internally. (Say,
some kind of "please clean things up if you can" message coming from a
garbage collector causing it to rebuild itself in some way.)
> The container concept can be thought of as the base class with the lists
> implementation being derived from it, even if that is not how you have
> implemented it.
This, I agree with.
> It's not unusual to want to want to do a tree traversal where you are
> iterating over all the elements of the tree.
Yes.
Basically, any container-like thing can reasonably have an iterator,
but the behavior might vary widely.
Flash Gordon
> Flash Gordon a �crit :
>>
>> Actually I was thinking of a library where the application code calls
>> explicit functions, and a fair way down the call graph in the library
>> it goes through function pointers to database specific functions so we
>> can select the database type at run time. However, that is deeply
>> embedded in the library and no where near the level of application code.
>
> I thought about that by using a generic creation function for each
> container
> that would receive a set of flags specifying the size of the container
> (huge, big, normal, small tiny) and the creation function would choose
> according to the flags which vtable to set into the new list.
That's one way to do it.
> The interface of all those function would still be exactly the same, the
> algorithms would be quite different of course.
>
> For big lists we would use a heap manager, for normal lists malloc at
> each element and for tiny lists we would allocate all the elements at once
>
> That is what I proposed with the theme of this thread:
>
> "Adapting software to multiple usage patterns"
However, it does not map to the usage pattern of, I need this to run as
fast as possible because it is used a vast amount and my heavy duty
server will hit 100% CPU usage and take a while even if it is fast. That
is the usage pattern I'm hitting these days.
--
Flash Gordon
Flash Gordon
> On 2009-10-15, Flash Gordon <sm...@spam.causeway.com> wrote:
>> Ive wanted to iterate over all the elements of a hash in a language
>> which has hashes natively, whilst at other points using it as a hash. If
>> you can iterate over it, then there is a concept of "the item 42" (even
>> if the order is not obvious, as long as it is consistent on any instance
>> of a hash whilst it exists between modifications). The same can apply to
>> trees (where there is a more obvious ordering).
>
> In ruby/perl, it's definitely possible for order to vary with modifications,
> but I'm not even sure it's impossible for order to vary without
> externally-visible modifications.
I don't know ruby, but it is possible to iterate over all elements of a
hash in Perl. As you say, the order can certainly change when the hash
table is modified.
> Imagine a hypothetical implementation where the hash may, under some
> non-obvious circumstances, choose to restructure itself internally. (Say,
> some kind of "please clean things up if you can" message coming from a
> garbage collector causing it to rebuild itself in some way.)
Possible, but I don't think it happens in Perl.
<snip>
>> It's not unusual to want to want to do a tree traversal where you are
>> iterating over all the elements of the tree.
>
> Yes.
>
> Basically, any container-like thing can reasonably have an iterator,
> but the behavior might vary widely.
Yes indeed. One common(ish) reason being to serialise it, although that
is not the only reason by any means.
--
Flash Gordon
Tim Rentsch
> In <hb5bep$5ho$1...@aioe.org>, jacob navia wrote:
>[snip]
>>
>> For instance this proposal about a container library
>> is an evolution that doesn't add any new complexity to the language.
>
> That depends on whether you consider the library to be a part of the
> language. Some do, others don't. [... snip rest...]
Jacob's usage is consistent with how the Standard identifies
these different areas:
...
6. Language
...
7. Library
Tim Rentsch
> In <kfntyy1...@x-alumni2.alumni.caltech.edu>, Tim Rentsch wrote:
>
>> Richard Heathfield <r...@see.sig.invalid> writes:
> <snip>
>>> I think if you focus only on the subset of C that
>>> always exhibits well-defined behaviour (i.e. ignore all programs
>>> that invoke UB or USB or IDB), it's not unreasonable to call that
>>> subset a formal system.
>>
>> Now there's a laugh. C has nothing even vaguely resembling
>> a formal semantics.
>
> I guess I'm a lot less fussy about what I am prepared to accept as a
> formal system.
If you mean you're using a term in a way that almost no
one else uses it, I agree with you.
Tim Rentsch
> On 2009-10-14, jacob navia <ja...@nospam.org> wrote:
>> To evolve, yes. For instance this proposal about a container library
>> is an evolution that doesn't add any new complexity to the language.
>
> Of course it does.
>
> The library is part of "the language".
I feel obliged to point out that the Standard itself makes the same
distinction that Jacob does here. Section 6 is Language. Section 7
is Library.
Richard Heathfield
Yes, all right, all right... :-)
Phil Carmody
> On 2009-10-15, jacob navia <ja...@nospam.org> wrote:
>> If you use
>
>> container->lpVtbl->GetElement(container,index);
>
> Which I wouldn't. If I were implementing this, I'd make it something
> like:
>
> static inline ctr_getelement(container *x, int index) {
> x->vtable->getelement(x, index);
> }
>
> and write
> ctr_getelement(x, index);
>
> ... Because C does not use camel case.
C doesn't /use/ any case. It copes with camel case precisely
as well as it copes with lower case.
Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
Flash Gordon
> Seebs <usenet...@seebs.net> writes:
>> On 2009-10-15, jacob navia <ja...@nospam.org> wrote:
>>> If you use
>>> container->lpVtbl->GetElement(container,index);
>> Which I wouldn't. If I were implementing this, I'd make it something
>> like:
>>
>> static inline ctr_getelement(container *x, int index) {
>> x->vtable->getelement(x, index);
>> }
>>
>> and write
>> ctr_getelement(x, index);
>>
>> ... Because C does not use camel case.
>
> C doesn't /use/ any case. It copes with camel case precisely
> as well as it copes with lower case.
Ah, but the C library, as defined by the language standard, does not use
camel case, and this would almost certainly be what Seebs was referring to.
--
Flash Gordon
Tim Rentsch
> Tim Rentsch <t...@alumni.caltech.edu> writes:
>>Now there's a laugh. C has nothing even vaguely resembling
>>a formal semantics.
>
> http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-453.pdf
It is of course possible to write a formal semantics
for C, or any other programming languge. My comment
was about C's official specification in the ISO standard
documents.
Nick Keighley
> Richard Heathfield <r...@see.sig.invalid> writes:
> >> Richard Heathfield <r...@see.sig.invalid> writes:
> >>> I think if you focus only on the subset of C that
> >>> always exhibits well-defined behaviour (i.e. ignore all programs
> >>> that invoke UB or USB or IDB), it's not unreasonable to call that
> >>> subset a formal system.
>
> >> Now there's a laugh. C has nothing even vaguely resembling
> >> a formal semantics.
Well they try by using english with a specialised vocabulary. Though
the number of arguments in clc indicates how successful this is...
> > I guess I'm a lot less fussy about what I am prepared to accept as a
> > formal system.
>
> If you mean you're using a term in a way that almost no
> one else uses it, I agree with you.
oh I don't know there a plenty of people who use the term "formal"
when they mean "partially formal" or "nearly formal". Hence my "little
bit pregnant" comment.
Keith Thompson
The allegedly laughable comment (from Richard Heathfield) was:
Permaybehaps. I think if you focus only on the subset of C that
always exhibits well-defined behaviour (i.e. ignore all programs
that invoke UB or USB or IDB), it's not unreasonable to call that
subset a formal system.
I'd argue that whether something qualifies as a formal system is
independent of whether and where a formal semantics for it has been
written down.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
jacob navia
The document is VERY interesting. It shows the limits of those approaches.
The author has entered the C grammar into a theorem prover. Obviously not
the WHOLE grammar but a fairly large subset of it.
Then, he tries to prove
void strcpy(char *s, char *t) { while (*s++ = *t++) ; }
This is too much for the theorem prover, so he has to
rearrange the loop into:
while (*t) {*s = *t;s++;t++;}
*s = *t;
s++;
t++;
And then he successfully proves that...
The next program (a 400 line piece of C program) was impossible to
prove.
Imagine the complexity of proving a normal piece of software in
the 10 000 lines range.
Another problem is that the formal system is dependent on...
another system called HOL, the theorem prover!
It is not proven that HOL has no bugs, and it is not proven that
the author did not any mistake when writing the HOL grammar the
is used as the basis of the approach.
In any case it is a very interesting piece of work.
Tim Rentsch
> On 16 Oct, 11:00, Tim Rentsch <t...@alumni.caltech.edu> wrote:
>> Richard Heathfield <r...@see.sig.invalid> writes:
>> > In <kfntyy1auke....@x-alumni2.alumni.caltech.edu>, Tim Rentsch wrote:
>> >> Richard Heathfield <r...@see.sig.invalid> writes:
>
>
>> >>> I think if you focus only on the subset of C that
>> >>> always exhibits well-defined behaviour (i.e. ignore all programs
>> >>> that invoke UB or USB or IDB), it's not unreasonable to call that
>> >>> subset a formal system.
>>
>> >> Now there's a laugh. C has nothing even vaguely resembling
>> >> a formal semantics.
>
> Well they try by using english with a specialised vocabulary. Though
> the number of arguments in clc indicates how successful this is...
Yes, the standard is written in formal English. Actually
I think it does a pretty good job of defining things
unambiguously, although obviously there are some exceptions.
>> > I guess I'm a lot less fussy about what I am prepared to accept as a
>> > formal system.
>>
>> If you mean you're using a term in a way that almost no
>> one else uses it, I agree with you.
>
> oh I don't know there a plenty of people who use the term "formal"
> when they mean "partially formal" or "nearly formal". Hence my "little
> bit pregnant" comment.
My comment was made about "formal system", not just the "formal"
part. Certainly the standard is written in formal English.
That's different from being a formal system, and I think it's
important to distinguish the two.
lawrenc...@siemens.com
>
> It is of course possible to write a formal semantics
> for C, or any other programming languge. My comment
> was about C's official specification in the ISO standard
> documents.
Yes, the committee thought it more valuable to have an informal
specification that most people could read and understand rather than a
formal one that hardly anyone could.
--
Larry Jones
Years from now when I'm successful and happy, ...and he's in
prison... I hope I'm not too mature to gloat. -- Calvin
Phil Carmody
_Bool isn't exactly the prettiest thing in the world, though.
Seebs
> I feel obliged to point out that the Standard itself makes the same
> distinction that Jacob does here. Section 6 is Language. Section 7
> is Library.
Yes. But they are both part of the standard for the C Language.
The language contains both language and library.
As someone recently pointed out, it's not exactly a rigorous formal model. :)
Seebs
> C doesn't /use/ any case. It copes with camel case precisely
> as well as it copes with lower case.
Standard usage, though, has rigorously avoided camel case, and I think
that even just fixing that and using more C-like names would improve the
chances of people being convinced to use the container library.
Tim Rentsch
> Tim Rentsch <t...@alumni.caltech.edu> writes:
>> r...@zedat.fu-berlin.de (Stefan Ram) writes:
>>
>>> Tim Rentsch <t...@alumni.caltech.edu> writes:
>>>>Now there's a laugh. C has nothing even vaguely resembling
>>>>a formal semantics.
>>>
>>> http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-453.pdf
>>
>> It is of course possible to write a formal semantics
>> for C, or any other programming languge. My comment
>> was about C's official specification in the ISO standard
>> documents.
>
> The allegedly laughable comment (from Richard Heathfield) was:
>
> Permaybehaps. I think if you focus only on the subset of C that
> always exhibits well-defined behaviour (i.e. ignore all programs
> that invoke UB or USB or IDB), it's not unreasonable to call that
> subset a formal system.
>
> I'd argue that whether something qualifies as a formal system is
> independent of whether and where a formal semantics for it has been
> written down.
Saying something is a formal system normally means it is expressed
using a precise mathematical characterization. The C standard is
written in formal English, but certainly it is not a precise
mathematical characterization. C is defined by the various ISO
documents; what C is may be /formalizable/, but that doesn't make
it a formal system.
Note that, for any implemented programming language, it's always
possible to formalize (one version of) the programming language,
simply by giving the program that implements it as the formal
definition. Presumably the comments above were about C as
it is defined by the ISO documents; in talking about whether
C is a formal system, it's important to talk about that
definition, because a different definition may very well
(and the case of C probably will) define a different language.
Probably it would have been better if I'd written this more
complete explanation in place of my original short statement.
Occasionally I too succumb to the temptation of posting
sound bites. (And please, no jokes about "sound bytes". :)
Seebs
Certainly not. Basically a namespace issue.
Tim Rentsch
> On 2009-10-16, Tim Rentsch <t...@alumni.caltech.edu> wrote:
>> I feel obliged to point out that the Standard itself makes the same
>> distinction that Jacob does here. Section 6 is Language. Section 7
>> is Library.
>
> Yes. But they are both part of the standard for the C Language.
>
> The language contains both language and library.
>
> As someone recently pointed out, it's not exactly a rigorous formal model. :)
OMG! Hoist with my own petard...
Tim Rentsch
> Tim Rentsch <t...@alumni.caltech.edu> wrote:
>>
>> It is of course possible to write a formal semantics
>> for C, or any other programming languge. My comment
>> was about C's official specification in the ISO standard
>> documents.
>
> Yes, the committee thought it more valuable to have an informal
> specification that most people could read and understand rather than a
> formal one that hardly anyone could.
Right. Definitely the better choice in this case IMO.
Keith Thompson
> Flash Gordon <sm...@spam.causeway.com> writes:
[...]
>> Ah, but the C library, as defined by the language standard, does not
>> use camel case, and this would almost certainly be what Seebs was
>> referring to.
>
> _Bool isn't exactly the prettiest thing in the world, though.
Agreed, but that's not camel case.
When inventing a new keyword, the committee needed to choose an
identifier reserved for all purposes. It had to be something
starting either with two underscores, or with an underscore and an
uppercase letter. I think _Bool is better than __bool. I suppose
they could have used __BOOL, but that looks like a macro name rather
than a keyword. And for normal use, it's hidden behind the "bool"
macro in <stdbool.h>. Same for _Complex and _Imaginary.
Of course just using "bool" (as C++ did) would have been ideal if not
for the fact that it would have broken existing code.
Keith Thompson
Hmm. We're definitely getting into angels-on-pinheads territory
here, but ...
Suppose you have a language that *is* defined by a formal semantics;
that language is a formal system. You then write an equivalent
informal description of the same language, comparable to the current
C standard, and burn the only copy of the document defining the
formal semantics. Does the language stop being a formal system?
(Personally, I find the question more interesting than any likely
answer.)
Tech07
> One of the main arguments being advanced by the people that oppose
> the standardization of a container library in C is the fact that
> there are many different usage patterns for such a library, and it
> would be impossible to satisfy them all.
>
> The solution proposed overcomes this problem in an elegant way
> by using a function table.
That's silly.
>
> For example, let's see how that would work in lists, one of the
> simplest containers.
>
> As it stands now, the list header structure, with free list, pointer
> to first, last, a size_t for the count of the items, and several
> other fields could be "top heavy", and bring too much overhead if
> the list is very small. For instance, if you know in advance
> that you will never store more than 5 items at a time in the
> list, such a "top heavy" overhead would be too much.
>
> The solution is to write a specialization of the list
> software for very small lists, where (for instance)
> you just allocate all the 5 items at once when creating the
> list, you eliminate the free list and the heap manager.
You're on the right track (sort of). But developing a theory of container
design based on one requirement is, well, lame. Of course, your "track" is:
How to shoehorn containers into C. To which I "reply": why bother? It would
seem that there are people that would like C to remain stagnant and you're
trying to clean up the water(?) Been there, done that: better to move to a
better location. OK, been there, done that too. So, better to build your own
house/country/whatever, the way you like it (or the way you think others
will like it, if that's your goal).
Jacob, when you keep trying to meld your concepts onto C, to me you seem
light-years behind. Put all that know-how into a new language, and you're
way ahead. I don't have compiler technology in my workshop, for example
(yet?). (.02).
Tech07
> One of the main arguments being advanced by the people that oppose
> the standardization of a container library in C is the fact that
> there are many different usage patterns for such a library, and it
> would be impossible to satisfy them all.
Or maybe they are wrong or lying or maybe you're trying to exploit that. ? I
dunno, are you "that smart"?
Phil Carmody
> Phil Carmody <thefatphi...@yahoo.co.uk> writes:
>> Flash Gordon <sm...@spam.causeway.com> writes:
> [...]
>>> Ah, but the C library, as defined by the language standard, does not
>>> use camel case, and this would almost certainly be what Seebs was
>>> referring to.
>>
>> _Bool isn't exactly the prettiest thing in the world, though.
>
> Agreed, but that's not camel case.
It does have a bit of a bump, though. And for perversity, there's
also some anti-camel usage: PRIiLEAST32! Pretence that cosmetic
optimality has been achieved will be laughed at.
> When inventing a new keyword, the committee needed to choose an
> identifier reserved for all purposes. It had to be something
> starting either with two underscores, or with an underscore and an
> uppercase letter. I think _Bool is better than __bool. I suppose
> they could have used __BOOL, but that looks like a macro name rather
> than a keyword.
Booleans are such a restricted type, having only two values, that I
think they should have just used 'restrict' for its name.
Tim Rentsch
There's an assumption in there that the two documents define the
same language. Do they? We know from experience that different
people form different opinions about what ISO C is; moreover this
happens despite ISO C being defined in carefully written, formal
English. The only way we can be sure that the two descriptions
define the same language is if the second description is just as
technically precise as the first. In other words, if the two
documents really define the same language, the second document
must also be precise enough to serve as a statement of formal
semantics.
Note that if we _can't_ be sure whether two language documents
define the same language then the two languages are necessarily
different, because at least one of them will be ambiguous about
what language is being defined.
jacob navia
>
> There's an assumption in there that the two documents define the
> same language. Do they? We know from experience that different
> people form different opinions about what ISO C is; moreover this
> happens despite ISO C being defined in carefully written, formal
> English. The only way we can be sure that the two descriptions
> define the same language is if the second description is just as
> technically precise as the first. In other words, if the two
> documents really define the same language, the second document
> must also be precise enough to serve as a statement of formal
> semantics.
>
> Note that if we _can't_ be sure whether two language documents
> define the same language then the two languages are necessarily
> different, because at least one of them will be ambiguous about
> what language is being defined.
How many times in this group we are left with interpreting the
obscure wordings of the C standard?
Not to speak about the buffer overflow error in the C standard
in the code of the asctime() function. Not to speak about functions
described in the library that will never be able to have correct
behavior unless they are lucky: YES gets() is in the C standard.
The C standard is an important document, but it is nowhere
near what we could call a coherent formal system, and I do not
think that that was the intent anyway.
Keith Thompson
[...]
> How many times in this group we are left with interpreting the
> obscure wordings of the C standard?
>
> Not to speak about the buffer overflow error in the C standard
> in the code of the asctime() function. Not to speak about functions
> described in the library that will never be able to have correct
> behavior unless they are lucky: YES gets() is in the C standard.
>
> The C standard is an important document, but it is nowhere
> near what we could call a coherent formal system, and I do not
> think that that was the intent anyway.
What do asctime() and gets() have to do with the question of
whether C is a formal system? You dislike them, fine, so do I.
But asctime() in particular is perhaps the *most* formally defined
entity in the entire standard, since it's required to behave in a
manner consistent with a specific C implementation.
The behavior of a call to asctime() or gets() is undefined in
certain cases. Are you suggesting that a formal system can have
no instances of undefined behavior? (I'm not all that familiar with
formal systems; if that's part of the definition, then there's little
hope for defining *any* real-world language as a formal system.)
The circumstances in which the behavior of a call to asctime() is
undefined can be unambiguously determined by reading its description
in the standard, and two sufficiently careful independent readers
will reach exactly the same conclusion about what those cases are.
That's formal enough for me. Sure, asctime() has its problems,
but a lack of formality isn't one of them.
Richard Heathfield
<snip>
> Are you suggesting that a formal system can have
> no instances of undefined behavior?
I don't know whether or not he is suggesting that, but it is certainly
the case that formal systems can specify that certain operations
"invoke undefined behaviour". For example, number theory defines
integers (especially 0), and it defines the result of dividing one
integer by another, but a special exception is made for 0, so that
the result of dividing by 0 is specifically left undefined.
It is perfectly possible, however, to devise a formal system with no
instances of undefined behaviour. I believe that Hofstadter's MIU
system is an example. Nevertheless, it is doubtful whether a
"sufficiently powerful" formal system could be defined in such a way.
<snip>
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
James Dow Allen
> jacob navia <ja...@nospam.org> writes:
> > Sure, that doesn't look as pretty as C++. But it does the same.
> > and, let's get real, is as clear as C++.
>
> Really? You think a loop containing
>
> sum += *(double *)dv->lpVtbl->GetElement(dv,i);
>
> which has an explicit cast, two indirections and a pointer dereference
> is as clear as
>
> double mean = accumulate(vec.begin(),vec.end(),0.0) / vec.size();
FWIW, Jacob's form seems clearer to me than Gareth's, if only
because the meaning of the unfamiliar "GetElement" is at least
slightly easier to guess than that of the unfamilar "accumulate".
Also, C lacks ".begin", ".end" and that suits my Spartan taste
fine.
But different people have different tastes, and different learning
methods (e.g. I like maps, but am usually mystified when getting
verbal directions).
> Go and ask a newbie programmer who knows neither C or C++ what they
> think each bit of code does.
Would his/her opinion be relevant?
James D. Allen
Walter Banks
Richard Heathfield wrote:
> I think if you focus only on the subset of C that always
> exhibits well-defined behaviour (i.e. ignore all programs that invoke
> UB or USB or IDB), it's not unreasonable to call that subset a formal
> system.
Broadening the comment. There might be a case for defining a
subset of C that is its core. This subset should be supported by
all variations of compilers hosted or non hosted. This set of core
values could be very useful in making the language portable.
Regards,
Walter..
--
Walter Banks
Byte Craft Limited
http://www.bytecraft.com
Dennis (Icarus)
news:hb5a0i$3sk$1...@aioe.org...
> Gareth Owen a �crit :
>> jacob navia <ja...@nospam.org> writes:
>>
<snip>
>
> The time is right now, when the C++ people start realizing that
> a simpler language is not a mistake but an advantage. Ask any C++
> programmer, the complexity of that language is over their heads.
>
No, it's not.
Dennis
Tim Rentsch
> Tim Rentsch <t...@alumni.caltech.edu> writes:
>>There's an assumption in there that the two documents define
>>the same language. Do they?
>
> A very valid question!
>
> In fact, it can not be answered, because to answer it, a
> formal meta-system (meta-calculus) would be required that
> contains both the >>non-formal<< specification and the
> formal specification and then defines the rules for when
> they are deemed to >>define the same language<<. [snip elaboration]
The meta-discussion need not be carried out in a formal
system -- it can be just ordinary conversation. In fact
this describes most mathematical proofs; very few proofs
are written in such a precise way that they can be verified
by a computer program. But even in this case, no conclusion
can be reached (ie, and agreed on by all parties) unless the
"informal" description is sufficiently precise so that there
is no question about what it describes -- in other words, so
that it too would be a formal system.
Tim Rentsch
> Richard Heathfield wrote:
>
>> I think if you focus only on the subset of C that always
>> exhibits well-defined behaviour (i.e. ignore all programs that invoke
>> UB or USB or IDB), it's not unreasonable to call that subset a formal
>> system.
Just a note in passing that this subset is almost the same as
the subset of "strictly conforming programs." (Trivia question:
how is it different?)
>
> Broadening the comment. There might be a case for defining a
> subset of C that is its core. This subset should be supported by
> all variations of compilers hosted or non hosted. This set of core
> values could be very useful in making the language portable.
The problem with this is that the defined subset (presumably
defined by some sort of formal specification, but let's skip
that for now) either will be too small to be practically
useful or the question of whether a program is in the
subset becomes difficult to answer (and in general is
undecidable). Furthermore, almost all real programs exhibit
some degree of implementation-specific behavior, so any
subset that excludes programs with such behavior will
rule out essentially all programs of interest.
Dik T. Winter
> Keith Thompson <ks...@mib.org> writes:
> > Phil Carmody <thefatphi...@yahoo.co.uk> writes:
> >> Flash Gordon <sm...@spam.causeway.com> writes:
> > [...]
> >>> Ah, but the C library, as defined by the language standard, does not
> >>> use camel case, and this would almost certainly be what Seebs was
> >>> referring to.
> >>
> >> _Bool isn't exactly the prettiest thing in the world, though.
> >
> > Agreed, but that's not camel case.
>
> It does have a bit of a bump, though.
But it is of course named after somebody, as the only part in the standard
library.
--
dik t. winter, cwi, science park 123, 1098 xg amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Richard Tobin
Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
>>> _Bool isn't exactly the prettiest thing in the world, though.
>> Agreed, but that's not camel case.
>It does have a bit of a bump, though.
That's just because your display doesn't do a proper uppercase underscore.
-- Richard
--
Please remember to mention me / in tapes you leave behind.