Generic programming in C

[Michael Foukarakis]

Gene a crit :

[...]

Generating code from templates like this is pretty standard in larger
code bases. But I've generally seen a short script in a language like
awk or perl used to transform the template instead of C.  I think what
you've done in C represents one line of Perl, for example.
I do not think so, if you look carefully at the code you will see that
it does more than what you believe. And in any case, I do not want to
force the users of the library to install another programming language
and all the associated hassle...

Nobody relies on one programming language for everything. If one
doesn't know sed/awk, (s)he's doomed anyway.

I never got the hang of sed and I find awk very limited (lack of
anchored patterns). I use perl for what i used to use awk for. It *is*
a bit of pain to have to download it and it is gigantic for what I
want.  Serves me right for using Windows.

Again: replace sed/awk with anything else. My example is not
important, the principle is.

impressive. On a desk top 2.3k is down in the noise.


no one is compelling you to use it. The void* appraoch is less
typesafe. Usually pretty ugly too.



could we have some specific criticism. If his code is broken or unsafe
we'd like to know why.

Ben Bacarisse pointed out quite a few errors. I think they're enough
to illustrate the point.

no one is twisting your arm

What the hell. Why are you getting so wound up? I'm asking a direct
question and your only response is an asinine comment? Let me clarify
my intentions to your amusing little mind:

I'm asking because I'm INTERESTED.

"C Unleashed" (if I recall corrctly) uses a generic approach (though
less sophisticated tahn Jacob's)


type safety. A quick an easy way to produce efficeint container code.

Finally, a real answer. Comment below.

well if he's done it plainly isn't inadequate

C is not fully capable of introspection. This is a fact. It is the
reason behind the following:
- the extra preprocessing step(s) in producing the "template library".
- the inability to deal with some cases (see above posts) or avoiding
significant storage costs for such types.

, hence the inadequacy. My question still stands - what is the real
benefit offered here, because it's not usability, user friendliness,
or "being generic", all of which are crucial in development and usage
of containers and libraries in general.

as opposed to what?

I'm not interested in the obvious.

I disagree

Why? Is there a point to libraries that are being implemented without
the intention of ever being used?

I think you've already made your mind up.

No, I haven't, that's why I'm asking questions. If you won't help me,
why don't you just go find your lost manhood elsewhere.

 

[Ian Collins]

Look, why don't you try abandoning that monolithic pov for a few
seconds, and understand what I'm asking: Given your (or anybody
else's) two versions of a container, what practical advantages does
your "template library" offer over the generic one?

The classic answer is type safety and efficiency.

An example often cited is the difference between qsort and a template
base sort. There isn't anything the compiler can do to optimise sorting
for a particular type with a "generic" function like qsort. On the
other hand, with a template the compiler knows the types being sorted
and can optimise accordingly.

Even a trivial operation such as searching will be much more efficient
for a template based container. Not having to use function pointers may
lead to a reduction in code size for the template based version. It
certainly would for sorting or searching an array of int for example.

A "generic" container will normally use void* for elements, which is
fine for containers of pointers to objects, but truly horrible for
containers of objects (a sorted list of int for example). In the case
of containers of pointers to objects, the template approach can add a
zero cost, type safe wrapper round the "generic" container. The wrapper
handles the casting to and from void* and the wrapper functions, being
trivial, will be optimised away.

 

[Michael Foukarakis]

The classic answer is type safety and efficiency.

An example often cited is the difference between qsort and a template
base sort.  There isn't anything the compiler can do to optimise sorting
for a particular type with a "generic" function like qsort.  On the
other hand, with a template the compiler knows the types being sorted
and can optimise accordingly.

Even a trivial operation such as searching will be much more efficient
for a template based container.  Not having to use function pointers may
lead to a reduction in code size for the template based version.  It
certainly would for sorting or searching an array of int for example.

I agree, although I can only guess the extent in which those
optimizations will save space/time.

A "generic" container will normally use void* for elements, which is
fine for containers of pointers to objects, but truly horrible for
containers of objects (a sorted list of int for example).  In the case
of containers of pointers to objects, the template approach can add a
zero cost, type safe wrapper round the "generic" container.  The wrapper
handles the casting to and from void* and the wrapper functions, being
trivial, will be optimised away.

While you are right, I'm still questioning the usefulness of a list
([vector|tree|...]) of basic types. It just feels like it's too much
space and effort for something that could be done with a int[]. But I
guess that's all academic, and the answer depends heavily on intent
and application.

 

[Ian Collins]

A "generic" container will normally use void* for elements, which is
fine for containers of pointers to objects, but truly horrible for
containers of objects (a sorted list of int for example). In the case
of containers of pointers to objects, the template approach can add a
zero cost, type safe wrapper round the "generic" container. The wrapper
handles the casting to and from void* and the wrapper functions, being
trivial, will be optimised away.

While you are right, I'm still questioning the usefulness of a list
([vector|tree|...]) of basic types. It just feels like it's too much
space and effort for something that could be done with a int[]. But I
guess that's all academic, and the answer depends heavily on intent
and application.

Over in C++ land, they are very common. Everywhere one would use a
dynamic array of something in C, in C++ a vector tends to be used
abstract away the memory management.

 

[jacob navia]

Ian Collins a écrit :

The classic answer is type safety and efficiency.

Exactly.

An example often cited is the difference between qsort and a template
base sort. There isn't anything the compiler can do to optimise sorting
for a particular type with a "generic" function like qsort. On the
other hand, with a template the compiler knows the types being sorted
and can optimise accordingly.

Even a trivial operation such as searching will be much more efficient
for a template based container. Not having to use function pointers may
lead to a reduction in code size for the template based version. It
certainly would for sorting or searching an array of int for example.

A "generic" container will normally use void* for elements, which is
fine for containers of pointers to objects, but truly horrible for
containers of objects (a sorted list of int for example). In the case
of containers of pointers to objects, the template approach can add a
zero cost, type safe wrapper round the "generic" container. The wrapper
handles the casting to and from void* and the wrapper functions, being
trivial, will be optimised away.

Another point is that in my implementation (I do not know if in C++ that holds)
you can customize the generated code. For instance it doesn't make sense to
have a pointer to objects that are smaller than a pointer size. It would be
much better to store directly the object in the place of the pointer and
access it directly.

 

[jacob navia]

Ian Collins a écrit :

A "generic" container will normally use void* for elements, which is
fine for containers of pointers to objects, but truly horrible for
containers of objects (a sorted list of int for example). In the case
of containers of pointers to objects, the template approach can add a
zero cost, type safe wrapper round the "generic" container. The wrapper
handles the casting to and from void* and the wrapper functions, being
trivial, will be optimised away.

While you are right, I'm still questioning the usefulness of a list
([vector|tree|...]) of basic types. It just feels like it's too much
space and effort for something that could be done with a int[]. But I
guess that's all academic, and the answer depends heavily on intent
and application.

Over in C++ land, they are very common. Everywhere one would use a
dynamic array of something in C, in C++ a vector tends to be used
abstract away the memory management.

The same holds here. True, you can program a flexible array in C (the proof is that I did it!) but
many people will not do that because of the effort involved. If there is a ready-made library to do
that for you it becomes much easier to do one.

 

[bartc]

Morris Keesan a écrit :

True. That is an oversight. Thanks

'const's are just extra clutter (imo). What is odd though is having an input
string called InputString, and an output string called just output, rather
than OutputString.

 

[Nick Keighley]

[...]

If you start like this, granted your penis is bigger.

happy now?

What? Why don't you try addressing my question. I'm trying to learn
something and you keep acting like a douche.

well you satrted on the penis size stuff. Why'd you do that if you
wanted an intelligent discussion?

 

[lawrence.jones]

An example often cited is the difference between qsort and a template
base sort. There isn't anything the compiler can do to optimise sorting
for a particular type with a "generic" function like qsort.

It can, with a little effort, implement qsort as an inline function,
which then allows at least as much optimization as templates do.

 

[Nick Keighley]

Ian Collins a écrit :

A "generic" container will normally use void* for elements, which is
fine for containers of pointers to objects, but truly horrible for
containers of objects (a sorted list of int for example).  In the case
of containers of pointers to objects, the template approach can add a
zero cost, type safe wrapper round the "generic" container.  The wrapper
handles the casting to and from void* and the wrapper functions, being
trivial, will be optimised away.
While you are right, I'm still questioning the usefulness of a list
([vector|tree|...]) of basic types. It just feels like it's too much
space and effort for something that could be done with a int[]. But I
guess that's all academic, and the answer depends heavily on intent
and application.

Over in C++ land, they are very common.  Everywhere one would use a
dynamic array of something in C, in C++ a vector tends to be used
abstract away the memory management.

The same holds here. True, you can program a flexible array in C (the proof is that I did it!) but
many people will not do that because of the effort involved. If there is a ready-made library to do
that for you it becomes much easier to do one.

this is a very good point. In C++ I pick vector for most data
structures. And automatically get a flexible array. Implementing the
same thing in C isn't particularly difficult but isn't usually worth
the trouble.

 

[Andrew Poelstra]

'const's are just extra clutter (imo). What is odd though is having an input
string called InputString, and an output string called just output, rather
than OutputString.

const assures the user he can pass string literals.

const assures the programmer that, if he does something Bad and
modifies a supposedly-input string, the compiler will catch him.

const makes the interface more concise and descriptive.

 

[Nick Keighley]

Again: replace sed/awk with anything else. My example is not
important, the principle is.

perhaps its the way you phrase things. I know of plenty of programmers
that don't use these sorts of tools. I'd never thought of them as
"doomed". Limited perhaps.

Ben Bacarisse pointed out quite a few errors. I think they're enough
to illustrate the point.

I hadn't read that post at the time. I note Jacob responded positivly
pretyty much all of it (actually probably all of it). His early
implementation has bugs they are being fixed.

What the hell. Why are you getting so wound up? I'm asking a direct
question and your only response is an asinine comment? Let me clarify
my intentions to your amusing little mind:

I'm asking because I'm INTERESTED.

you don't give that impression. It seems more like "I don't think this
is a good idea in C and I can't see any reason for it". This is even
after a couple of people have pointed out the possible benefit.

[...]

type safety. A quick and easy way to produce efficient container code.

Finally, a real answer. Comment below.
[...]

well if he's done it plainly isn't inadequate

C is not fully capable of introspection. This is a fact. It is the
reason behind the following:
- the extra preprocessing step(s) in producing the "template library".

C++ jumps through rather similar hoops under the hood

- the inability to deal with some cases (see above posts) or avoiding
significant storage costs for such types.

, hence the inadequacy. My question still stands - what is the real
benefit offered here, because it's not usability, user friendliness,
or "being generic",

again you just say that

all of which are crucial in development and usage
of containers and libraries in general.



Why? Is there a point to libraries that are being implemented without
the intention of ever being used?

I don't see those things as saying the same thing. I thought you were
asking for a particular application. Containers don't work that way.
What application *wouldn't* it work on.

find a C++ that uses an STL container and explain why the same sort of
thing couldn't be used with a generic container in C

No, I haven't, that's why I'm asking questions. If you won't help me,
why don't you just go find your lost manhood elsewhere.

ok you've memorised the puffin book of freud...

I think we're probably done here

 

[Keith Thompson]

No, I haven't, that's why I'm asking questions. If you won't help me,
why don't you just go find your lost manhood elsewhere.

If you were really interested in having a serious discussion, you
probably wouldn't make silly remarks like that. If you're more
interested in annoying people, that's a great way to do it.

 

[Keith Thompson]

const assures the user he can pass string literals.

Alas, string literals aren't const.

But it does make it possible to pass an argument of type const char*.

const assures the programmer that, if he does something Bad and
modifies a supposedly-input string, the compiler will catch him.

const makes the interface more concise and descriptive.

Agreed.

 

[Andrew Poelstra]

Alas, string literals aren't const.

I meant, the user /knows/ he can /safely/ pass string literals.
Sadly, you are correct that the compiler doesn't care either way.

 

[lawrence.jones]

Alas, string literals aren't const.

But they're also not modifiable, so const *does* provide assurance. It
doesn't provide license, just assurance.

 

[Nick]

Nick a écrit :


Since you know nothing but that prototype

The way a lot of people program, of course!

you do not know that a NULL
value for output makes strrepl calculate the length of the required
string if all the replacements would be done. That can be used to
allocate a new buffer or ensure that no buffer overflows happen. Then,
you call it with a correct buffer.

I explained that in the text and used it in the code.

That means it /can/ be used safely, not that it will. I still feel that
a prototype like that is inviting the user to use it unsafely.

There's not much you can do about it, I grant. And that's one of the
problems I see with what you're trying to do with C - it doesn't have
the infrastructure to support it.

You really want this function to take "strings", not "C strings". The
problem is that if you do this you end up re-inventing C++ (and while
there's almost certainly an argument for doing it better, I doubt
there's a market for it).

This is, I think, why no major list, string, hash or whatever library
has really taken over - unless you have the whole lot all integrated you
end up with so many limitations that you don't get most of the benefits.

I think it's a bold thing you're doing, but ultimately I can't see it
taking off - it falls too much between C and C++.

 

[jacob navia]

Nick a écrit :

The way a lot of people program, of course!

You should read the documentation/manual page of a function you do not know.
Yes, it can be used unsafely.

That means it /can/ be used safely, not that it will. I still feel that
a prototype like that is inviting the user to use it unsafely.

This is a difference of viewpoint here. You are used to C++ hand holding and need
a complex machinery to guarantee you that no errors can happen.

C has a different philosophy, that leads to simpler code that can be as sure as
C++ code.

There's not much you can do about it, I grant. And that's one of the
problems I see with what you're trying to do with C - it doesn't have
the infrastructure to support it.

To support what? String replacement?

Yes it has.

To support hand holding?

No it doesn't.

You really want this function to take "strings", not "C strings". The
problem is that if you do this you end up re-inventing C++ (and while
there's almost certainly an argument for doing it better, I doubt
there's a market for it).

lcc-win provides counted strings using operator overloading. I have
proposed that change to the language many times.

This is, I think, why no major list, string, hash or whatever library
has really taken over - unless you have the whole lot all integrated you
end up with so many limitations that you don't get most of the benefits.

I do not think so.

I think it's a bold thing you're doing, but ultimately I can't see it
taking off - it falls too much between C and C++.

Yes, I know your position. I will fail, the library *will fail, etc.
I disagree.

jacob

 

[Nick]

Nick a écrit :

You should read the documentation/manual page of a function you do not know.
Yes, it can be used unsafely.


This is a difference of viewpoint here. You are used to C++ hand holding and need
a complex machinery to guarantee you that no errors can happen.

No I'm not. I've never written C++ in my life. Not even to the extent
of tweaking a couple of lines in a pre-existing program (the way I could
say I've written PL/I or Perl for example).

I am used to people using functions that write unknown length strings
into string pointers, and what happens when they do.

lcc-win provides counted strings using operator overloading. I have
proposed that change to the language many times.

As I've suggested, the problem with strings with length is that there
are at least two ways of doing them - each of which has major advantages
and disadvantages. You don't need operator overloading to do it, of
course - that's another tack entirely.

It seems to me that you need to use your simpler enhancements (library,
not language syntax) to build the later features on - so use your
strings here rather than C-strings.

I do not think so.

So which major list, string, hash or whatever library has really taken
over then? Or do you mean that after 20+ years you're going to succeed
where everyone else has failed (do you have any idea how many such
libraries are available)?

Yes, I know your position. I will fail, the library *will fail, etc.
I disagree.

I didn't say "you would fail". I said "I don't see it taking off". Why
do you always turn any comments into some sort of personal attack on
yourself? It's very unbecoming. Nevertheless, wouldn't you be
expecting some sort of widespread take-up by now if it was to be the
success that every previous attempt has not been?

 

[Kenny McCormack]

If you were really interested in having a serious discussion, you
probably wouldn't make silly remarks like that. If you're more
interested in annoying people, that's a great way to do it.

God almighty, you (Kiki) are one piece of work!

--

No, I haven't, that's why I'm asking questions. If you won't help me,
why don't you just go find your lost manhood elsewhere.

CLC in a nutshell.