The C Containers Library

[jacob navia]

To:
John Benito
Convener
ISO/IEC JTC1/SC22/WG14
110 Shady Brook Court
Santa Cruz, CA 95065-9728
USA

From:

Jacob Navia
41 rue Maurice Ravel
93430 Villetaneuse
France

Villetaneuse, July 8th 2012

Dear Sir,

I would like to present the document:

"The C Containers Library"

to the committee for consideration for standardization.

This document has been discussed in the French C++ standardization
group of the AFNOR since there isn't a group for the C language
exclusively any more. C and C++ share the same group.

This document is available at the following address:

http://ccl.googlecode.com/files/ccl.pdf

I have setup a google project with the source code of the sample
implementation as described in the above document. Its address is:

http://code.google.com/p/ccl/

I have been working in this project approximately for three years and
the document is still far from perfect, but I consider that it now
gives a clear idea of the scope of this undertaking and about how can
it be implemented.

I presented the very first release of this project on June 24th 2010
to the comp.std.c and comp.lang.c discussions groups. I had started to
design and implement the library approximately a year before.

In the document you will find:

o An introduction that describes the layout, the motivations, and an
overview of what parts of the document are to be considered normative
specifications.
o Two introductory chapters explaining things informally.
o Two normative chapters (Auxiliary interfaces and the Containers)
o A description of the sample implementation with some commented code
excerpts.
o Applications and examples
o The "templated" form of the containers explained.

I have tried to keep the language of the specifications clear and
concise, but I have avoided trying to mimic "standardese" since I
believe that the explanations should be understood by all programmers
using the library without any artificial restrictions. As a model, I
used the language used in the "RFC"s of the interenet, specifications
that proved quite useful but are in plain language, understood by
everyone.

My goal in this first approach is to start a technical report (TR) that
could be further discussed within the community.

I thank you in advance for your attention. I remain available at any
time for any question you may have concerning this project.

Yours sincerely

Jacob Navia
Programmer

 

[aftnix]

To:
John Benito
Convener
ISO/IEC JTC1/SC22/WG14
110 Shady Brook Court
Santa Cruz, CA 95065-9728
USA

From:

Jacob Navia
41 rue Maurice Ravel
93430 Villetaneuse
France

Villetaneuse, July 8th 2012

Dear Sir,

I would like to present the document:

"The C Containers Library"

to the committee for consideration for standardization.

This document has been discussed in the French C++ standardization
group of the AFNOR since there isn't a group for the C language
exclusively any more. C and C++ share the same group.

This document is available at the following address:

http://ccl.googlecode.com/files/ccl.pdf

I have setup a google project with the source code of the sample
implementation as described in the above document. Its address is:

http://code.google.com/p/ccl/

I have been working in this project approximately for three years and
the document is still far from perfect, but I consider that it now
gives a clear idea of the scope of this undertaking and about how can
it be implemented.

I presented the very first release of this project on June 24th 2010
to the comp.std.c and comp.lang.c discussions groups. I had started to
design and implement the library approximately a year before.

In the document you will find:

o An introduction that describes the layout, the motivations, and an
overview of what parts of the document are to be considered normative
specifications.
o Two introductory chapters explaining things informally.
o Two normative chapters (Auxiliary interfaces and the Containers)
o A description of the sample implementation with some commented code
excerpts.
o Applications and examples
o The "templated" form of the containers explained.

I have tried to keep the language of the specifications clear and
concise, but I have avoided trying to mimic "standardese" since I
believe that the explanations should be understood by all programmers
using the library without any artificial restrictions. As a model, I
used the language used in the "RFC"s of the interenet, specifications
that proved quite useful but are in plain language, understood by
everyone.

My goal in this first approach is to start a technical report (TR) that
could be further discussed within the community.

I thank you in advance for your attention. I remain available at any
time for any question you may have concerning this project.

Yours sincerely

Jacob Navia
Programmer

I actually don't understand the reason why you are posting it here?
A short post with "hey i have submitted ccl to ISO" would suffice.

 

[jacob navia]

Le 26/07/12 22:13, aftnix a écrit :

I actually don't understand the reason why you are posting it here?
A short post with "hey i have submitted ccl to ISO" would suffice.

No, I think it wouldn't suffice.

I wanted that the people that follow this develoments know why I am
posting that now.

By the way the proposal was accepted for discussion in the next meeting
of the committee at Portland, October 22th to October 26th.

jacob

 

[wkaras]

To:
John Benito
Convener
ISO/IEC JTC1/SC22/WG14
110 Shady Brook Court
Santa Cruz, CA 95065-9728
USA

From:

Jacob Navia
41 rue Maurice Ravel
93430 Villetaneuse
France

Villetaneuse, July 8th 2012

Dear Sir,

I would like to present the document:

"The C Containers Library"

to the committee for consideration for standardization.

This document has been discussed in the French C++ standardization
group of the AFNOR since there isn't a group for the C language
exclusively any more. C and C++ share the same group.

This document is available at the following address:

http://ccl.googlecode.com/files/ccl.pdf

I have setup a google project with the source code of the sample
implementation as described in the above document. Its address is:

http://code.google.com/p/ccl/

I have been working in this project approximately for three years and
the document is still far from perfect, but I consider that it now
gives a clear idea of the scope of this undertaking and about how can
it be implemented.

I presented the very first release of this project on June 24th 2010
to the comp.std.c and comp.lang.c discussions groups. I had started to
design and implement the library approximately a year before.

In the document you will find:

o An introduction that describes the layout, the motivations, and an
overview of what parts of the document are to be considered normative
specifications.
o Two introductory chapters explaining things informally.
o Two normative chapters (Auxiliary interfaces and the Containers)
o A description of the sample implementation with some commented code
excerpts.
o Applications and examples
o The "templated" form of the containers explained.

I have tried to keep the language of the specifications clear and
concise, but I have avoided trying to mimic "standardese" since I
believe that the explanations should be understood by all programmers
using the library without any artificial restrictions. As a model, I
used the language used in the "RFC"s of the interenet, specifications
that proved quite useful but are in plain language, understood by
everyone.

My goal in this first approach is to start a technical report (TR) that
could be further discussed within the community.

I thank you in advance for your attention. I remain available at any
time for any question you may have concerning this project.

Yours sincerely

Jacob Navia
Programmer

Although this clearly has value as it is, I think it would be an improvement if these non-intrusive containers were layered on top of intrusive containers.

 

[James Kuyper]

That's somewhat counterproductive. Whether or not jacob wants it to be,
his proposal, if accepted, would have to be translated into standardese
for inclusion in the C standard. The goal of the standard is not to make
the explanations as easy to understand as possible - that's what text
books are for. The standard needs to have specifications sufficiently
precise to avoid ambiguity, even if that makes them harder to
understand. It must cover the corner cases, even if mentioning the
corner cases interferes with understanding what's supposed to happen in
the normal case.

The need to perform that translation will tend to discourage adoption of
the proposal, all else being equal. On the other hand, someone as
unsympathetic as jacob is to the use of standardese is unlikely to
perform a good translation, so perhaps it is best if he doesn't even
try. If it is adopted, it would almost certainly need a significant
re-write anyway before it could be approved, even if it were written in
fluent standardese.

 

[jacob navia]

Le 26/07/12 22:45, (e-mail address removed) a écrit :

Although this clearly has value as it is, I think it would be an improvement

if these non-intrusive containers were layered on top of intrusive
containers.
How can you maintain the inner structure of the container hidden in
intrusive containers?

Please explain

jacob

 

[jacob navia]

Le 26/07/12 22:52, James Kuyper a écrit :

On the other hand, someone as
unsympathetic as jacob is to the use of standardese is unlikely to
perform a good translation, so perhaps it is best if he doesn't even
try.

Can you please translate that into plain english?

Thanks

jacob

 

[Alan Curry]

Le 26/07/12 22:52, James Kuyper a écrit :

Can you please translate that into plain english?

Thanks

ISO standards are written like legislation, not documentation. The
target audience isn't programmers who want to use the language; it's
lawyers who want to be able to officially place blame when something
goes wrong.

James is saying that you aren't capable of writing in the legalistic
style of an ISO standard.

Just reading the stuff is tedious. Writing it must be even more so.

 

[jacob navia]

Le 27/07/12 00:29, Alan Curry a écrit :

ISO standards are written like legislation, not documentation. The
target audience isn't programmers who want to use the language; it's
lawyers who want to be able to officially place blame when something
goes wrong.

Have you read the RFCs?

They are written in a language anybody can understand. And they have
less ambiguities than the C standard.

My point is that even if you write specifications in a lawyer friendly
language, they do not get better because of that. It is just that the
people that can understand what they mean are less numerous since
now you need to read standardese and correctly interpret it.

James is saying that you aren't capable of writing in the legalistic
style of an ISO standard.

I really do not know. For instance if you look at the normative parts of
the documentation they are in my opinion quite clear and they specify
correctly the APIs.

Just reading the stuff is tedious. Writing it must be even more so.

I wanted a documentation that is easy to read and to understand by the
greatest amount of people, and at the same time it is clear, leaving
no ambiguous words. It is a tall order but I think I come close.

Anyway if I fdidn't think that I wouldn't have presented it to the
committee.

Thanks for your input.

jacob

 

[jacob navia]

Le 26/07/12 22:56, jacob navia a écrit :

Le 26/07/12 22:52, James Kuyper a écrit :

Sorry I misunderstood what you said.

I read:

Then in my mind I added a comma here, so that sentence was separated
from the rest and thought you were treating me of "unsympathetic"

I am getting completely paranoid, actually now in a second reading I see
that you are referring to me as being unsympathetic to standardese
what is correct.

That is why I asked for a translation.

Well, now is clearer.


Sorry about this confusion.

 

[wkaras]

Le 26/07/12 22:45, wkaras a �crit :

> Although this clearly has value as it is, I think it would be an improvement

if these non-intrusive containers were layered on top of intrusive
containers.
>

How can you maintain the inner structure of the container hidden in
intrusive containers?

Please explain

jacob

It's not hidden, that's part of the instrusive aspect of it. If you look at the examples using this intrusive AVL tree code that I wrote:

http://wkaras.webs.com/cavl_tree.html

maybe that would be the best way to show you what I mean. The Boost library also now has instrusive containers (in C++ of course) but simpler if somewhat less flexible.

I'm address more your example implementation (which I'm guessing is highly portable). I'm just suggesting it might be worth the effort to repackage the container implementations as directly-usable instrusive containers, and have the intrusive containers become an optional layer on top.

There could be some minor performance penalties. For example, a straight-forward instrusive AVL tree would require the element to be contained (without copying) to have within it the structure:

typedef struct { void *left, *right; char balance_factor; } AVL_FIELDS;

The container could insist this struct be at byte offset 0 in the element. Or the offset could be configurable for each container, allowing an element to be in multiple trees (or other containers) as the same time. The costbeing the added overhead of getting and adding the offset each time AVL_FIELDS is referenced.

 

[wkaras]

To:
John Benito
Convener
ISO/IEC JTC1/SC22/WG14
110 Shady Brook Court
Santa Cruz, CA 95065-9728
USA

From:

Jacob Navia
41 rue Maurice Ravel
93430 Villetaneuse
France

Villetaneuse, July 8th 2012

Dear Sir,

I would like to present the document:

"The C Containers Library"

to the committee for consideration for standardization.

This document has been discussed in the French C++ standardization
group of the AFNOR since there isn't a group for the C language
exclusively any more. C and C++ share the same group.

This document is available at the following address:

http://ccl.googlecode.com/files/ccl.pdf

I have setup a google project with the source code of the sample
implementation as described in the above document. Its address is:

http://code.google.com/p/ccl/

I have been working in this project approximately for three years and
the document is still far from perfect, but I consider that it now
gives a clear idea of the scope of this undertaking and about how can
it be implemented.

I presented the very first release of this project on June 24th 2010
to the comp.std.c and comp.lang.c discussions groups. I had started to
design and implement the library approximately a year before.

In the document you will find:

o An introduction that describes the layout, the motivations, and an
overview of what parts of the document are to be considered normative
specifications.
o Two introductory chapters explaining things informally.
o Two normative chapters (Auxiliary interfaces and the Containers)
o A description of the sample implementation with some commented code
excerpts.
o Applications and examples
o The "templated" form of the containers explained.

I have tried to keep the language of the specifications clear and
concise, but I have avoided trying to mimic "standardese" since I
believe that the explanations should be understood by all programmers
using the library without any artificial restrictions. As a model, I
used the language used in the "RFC"s of the interenet, specifications
that proved quite useful but are in plain language, understood by
everyone.

My goal in this first approach is to start a technical report (TR) that
could be further discussed within the community.

I thank you in advance for your attention. I remain available at any
time for any question you may have concerning this project.

Yours sincerely

Jacob Navia
Programmer

I would just comment generally that the C++ STL started out as an implementation, the standardese came later. And I don't believe it was Stepanov who wrote the standardese.

I prefer a portable open-source implementation even with no standard to standard with no portable open-source implementation.

 

[jacob navia]

Le 27/07/12 03:46, (e-mail address removed) a écrit :

It's not hidden, that's part of the instrusive aspect of it. If you look at the examples using this intrusive AVL tree code that I wrote:

http://wkaras.webs.com/cavl_tree.html

That address doesn't work: I get a 404...

 

[jacob navia]

I see what you mean, but the problem is that there is no separation from
the container to the rest of the software...

That means that any ch ange of the container structure that can't be
hidden needs a complete recompilation of all the client software.

OK, some containers like single linked lists could be easy to do
bit others would be much more complex.

The way the AI would look would need to be radically different
too.

I will wait till your address

http://wkaras.webs.com/cavl_tree.html

to see what you have in mind concerning the API.

 

[gwowen]

That address doesn't work: I get a 404...

http://www.oocities.org/wkaras/gen_c/cavl_tree.html

 

[James Kuyper]

....
I would just comment generally that the C++ STL started out as an implementation, the standardese came later. And I don't believe it was Stepanov who wrote the standardese.

Yes, and getting the standardese right was a major pain for the C++
committee, judging from the discussions I saw on comp.std.c++. They were
willing to make that effort because they considered the STL a major
valuable addition to C++. Jacob faces the challenge of getting the C
committee comparably enthusiastic about the "C Containers Library".

 

[wkaras]

Yes, and getting the standardese right was a major pain for the C++

committee, judging from the discussions I saw on comp.std.c++. They were

willing to make that effort because they considered the STL a major

valuable addition to C++. Jacob faces the challenge of getting the C

committee comparably enthusiastic about the "C Containers Library".

The STL containers have been a big driver of adoption of C++ in place of C. A powerful C container library (which this appears to be) would be very important to maintaining C as a viable alternative. So it should not be that big of a challenge.

 

[wkaras]

Le 27/07/12 03:46, wkaras a �crit :




That address doesn't work: I get a 404...

Ooops. http://wkaras.webs.com/gen_c/cavl_tree.html

( http://www.oocities.org/wkaras/gen_c/cavl_tree.html is an identical copy.)

 

[James Kuyper]

The STL containers have been a big driver of adoption of C++ in place of C. A powerful C container library (which this appears to be) would be very important to maintaining C as a viable alternative. So it should not be that big of a challenge.

C++ has many features which are not part of C, that made STL powerful
while remaining relatively easy to implement and use. Adding those
features to C would remove much of the distinction between C and C++.
The only point in keeping C and C++ alive simultaneously is the
differences between them - C is the simpler, easier language to
implement, learn, and read; C++ is the more complicated higher-level
language that makes certain concepts (such as STL) a lot easier to
implement and use. C would lose most of that simplicity advantage if all
of those C++ features were added to it.

jacob has proposed that some of those features be added, but not all of
them; in any event that's not what this proposal is about. The
Containers Library is a kludge that attempts to work somewhat like STL,
without all of the C++-specific features that STL relies upon, and
that's what's going to make this a difficult concept to sell to the
committee.

 

[wkaras]

C++ has many features which are not part of C, that made STL powerful

while remaining relatively easy to implement and use. Adding those

features to C would remove much of the distinction between C and C++.

The only point in keeping C and C++ alive simultaneously is the

differences between them - C is the simpler, easier language to

implement, learn, and read; C++ is the more complicated higher-level

language that makes certain concepts (such as STL) a lot easier to

implement and use. C would lose most of that simplicity advantage if all

of those C++ features were added to it.



jacob has proposed that some of those features be added, but not all of

them; in any event that's not what this proposal is about. The

Containers Library is a kludge that attempts to work somewhat like STL,

without all of the C++-specific features that STL relies upon, and

that's what's going to make this a difficult concept to sell to the

committee.

Why do you feel it's a kludge? Because he's using void pointers to make the code generic, that is, usable with different types? Isn't that why void pointers were added to C, for that purpose?

Containers are not anything esoteric, they are at least as widely used as floating point, to give an example. Casting mistakes when using void pointers can be hairy. But the overall effort, and the overall chance of a bug making it into released code, is less than rewriting containers like AVL trees and hash tables over and over for specific types.