4 ms·

Not that object-oriented languages are particularly good at it, but defining and using abstract data types in C is a pain: (0) Forward declarations are the onl

Not that object-oriented languages are particularly good at it, but defining and using abstract data types in C is a pain: (0) Forward declarations are the only way not to explicitly reveal the representation of types, but you have to pay an indirection tax for it, whether you actually need indirection or don't. (1) Without heavily abusing the preprocessor, there is no way to express the fact that two abstract data types expose the same interface. (2) Again, without heavily abusing the preprocessor, there is no way to make common algorithms work on abstract data types that have a common interface.

yawaramin 9y ago
(0) True, but the default assumption really should be that the indirection tax is fine. There are plenty of non-realtime C apps. If you're really seeing a slowdown, then by all means trade off some of that abstraction power. (1) & (2) You could use conversion functions, no? E.g.: typedef struct ordering_t* ordering; typedef struct person_t* person; typedef struct business_t* business; ordering ordering_of_person(person); ordering ordering_of_business(business); void* sort(void*, ordering);
- catnaroek 9y ago
  (0) The indirection tax is not fine. I want both nice abstractions and efficient implementations. (1) and (2) Your proposal doesn't work, because different abstract data types are, well, different, even if they expose the same operations. (Perhaps you're confusing “abstract data types” with “abstract classes”?) If you don't believe me, try merging a binomial heap and a pairing heap.
jcelerier 9y ago
> Forward declarations are the only way not to explicitly reveal the representation of types, but you have to pay an indirection tax for it, whether you actually need indirection or don't. How would you solve this while still allowing object files to compile like they do ? e.g. if I have a .c file with a function void f(some_type t) { ... } the compiler has to know at that point what is the size of t so that it can allocate the correct space on the stack at the beginning of the function when compiling it. You could fix this with some kind of module system but this would mean that you'd always need the whole module which may be multiple megabytes vs a .hpp which is generally small (or a forward-declaration which is negligible). Regarding 3, C11 has some generics nowadays: http://en.cppreference.com/w/c/language/generic http://en.cppreference.com/w/c/language/generic so for simple stuff it can be done (and for more complex stuff you'd be much better served by c++ templates)
- catnaroek 9y ago
  > You could fix this with some kind of module system but this would mean that you'd always need the whole module which may be multiple megabytes (...) You don't need the whole module. You need the module's interface to compile anything that depends on the module. Of course, type sizes and alignments must be a part of the interface in a C-like language. But “exporting sizes and alignments” doesn't necessitate “exporting the entire internal representation of the type”, cf. Rust. > (...) vs a .hpp which is generally small (or a forward-declaration which is negligible). You can't forward-declare type sizes and alignments. This is precisely why you must pay the aforementioned indirection tax. > Regarding (2), C11 has some generics nowadays Which is just a compile-time switch statement on types. You still have to write separate implementations of generic algorithms for every concrete type on which you want to use them. > (and for more complex stuff you'd be much better served by c++ templates) The pain associated to using C++ templates is exactly what happens when you try to do generic programming in a language with no support for abstract type specifications.
slrz 9y ago
> (0) Forward declarations are the only way not to explicitly reveal the representation of types, but you have to pay an indirection tax for it, whether you actually need indirection or don't. If you don't want the indirection, you need to declare at least size and alignment requirements. So why not go ahead and just do that. struct typename { uchar xxx[THE_SIZE]; } __attribute__((aligned($your_alignment))); If your compiler doesn't support such alignment specification, there are ways to work around that. > (2) Again, without heavily abusing the preprocessor, there is no way to make common algorithms work on abstract data types that have a common interface. There are. Look at any bigger C project to discover them. A common approach is the use of "ops" structures containing function pointers that are filled depending on the type in use. Yes, doing all of this manually tends to be more cumbersome than it might be using other more modern languages. Just as manual memory management tends to be more painful than working in a proper garbage-collected environment. If you still pick C for writing your program, you probably don't mind it or have some other reason for sticking with C.
- catnaroek 9y ago
  > (horrible snippet) If that's how you define abstract data types in C, then I'll stick to my current practice of not defining abstract data types in C, for obvious reasons. > A common approach is the use of "ops" structures containing function pointers that are filled depending on the type in use. Maybe you're confusing ADTs with objects? They aren't the same thing at all[0]. The point to ADTs is delimiting the scope where implementation details (e.g., whether a set data structure is implemented as a red-black tree or an AVL tree) are relevant. The point to objects is deferring until runtime the decision to use this or that implementation (e.g., callbacks). ADTs in general needn't pay an indirection tax. And using objects when ADTs suffice for your modularity purposes is a sign of being a very stupid programmer. [0] http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf > If you still pick C for writing your program, you probably don't mind it or have some other reason for sticking with C. The latter.

yawaramin 9y ago

(0) True, but the default assumption really should be that the indirection tax is fine. There are plenty of non-realtime C apps. If you're really seeing a slowdown, then by all means trade off some of that abstraction power. (1) & (2) You could use conversion functions, no? E.g.: typedef struct ordering_t* ordering; typedef struct person_t* person; typedef struct business_t* business; ordering ordering_of_person(person); ordering ordering_of_business(business); void* sort(void*, ordering);

catnaroek 9y ago
(0) The indirection tax is not fine. I want both nice abstractions and efficient implementations. (1) and (2) Your proposal doesn't work, because different abstract data types are, well, different, even if they expose the same operations. (Perhaps you're confusing “abstract data types” with “abstract classes”?) If you don't believe me, try merging a binomial heap and a pairing heap.

jcelerier 9y ago

> Forward declarations are the only way not to explicitly reveal the representation of types, but you have to pay an indirection tax for it, whether you actually need indirection or don't. How would you solve this while still allowing object files to compile like they do ? e.g. if I have a .c file with a function void f(some_type t) { ... } the compiler has to know at that point what is the size of t so that it can allocate the correct space on the stack at the beginning of the function when compiling it. You could fix this with some kind of module system but this would mean that you'd always need the whole module which may be multiple megabytes vs a .hpp which is generally small (or a forward-declaration which is negligible). Regarding 3, C11 has some generics nowadays: http://en.cppreference.com/w/c/language/generic http://en.cppreference.com/w/c/language/generic so for simple stuff it can be done (and for more complex stuff you'd be much better served by c++ templates)

catnaroek 9y ago
> You could fix this with some kind of module system but this would mean that you'd always need the whole module which may be multiple megabytes (...) You don't need the whole module. You need the module's interface to compile anything that depends on the module. Of course, type sizes and alignments must be a part of the interface in a C-like language. But “exporting sizes and alignments” doesn't necessitate “exporting the entire internal representation of the type”, cf. Rust. > (...) vs a .hpp which is generally small (or a forward-declaration which is negligible). You can't forward-declare type sizes and alignments. This is precisely why you must pay the aforementioned indirection tax. > Regarding (2), C11 has some generics nowadays Which is just a compile-time switch statement on types. You still have to write separate implementations of generic algorithms for every concrete type on which you want to use them. > (and for more complex stuff you'd be much better served by c++ templates) The pain associated to using C++ templates is exactly what happens when you try to do generic programming in a language with no support for abstract type specifications.

slrz 9y ago

> (0) Forward declarations are the only way not to explicitly reveal the representation of types, but you have to pay an indirection tax for it, whether you actually need indirection or don't. If you don't want the indirection, you need to declare at least size and alignment requirements. So why not go ahead and just do that. struct typename { uchar xxx[THE_SIZE]; } __attribute__((aligned($your_alignment))); If your compiler doesn't support such alignment specification, there are ways to work around that. > (2) Again, without heavily abusing the preprocessor, there is no way to make common algorithms work on abstract data types that have a common interface. There are. Look at any bigger C project to discover them. A common approach is the use of "ops" structures containing function pointers that are filled depending on the type in use. Yes, doing all of this manually tends to be more cumbersome than it might be using other more modern languages. Just as manual memory management tends to be more painful than working in a proper garbage-collected environment. If you still pick C for writing your program, you probably don't mind it or have some other reason for sticking with C.

catnaroek 9y ago
> (horrible snippet) If that's how you define abstract data types in C, then I'll stick to my current practice of not defining abstract data types in C, for obvious reasons. > A common approach is the use of "ops" structures containing function pointers that are filled depending on the type in use. Maybe you're confusing ADTs with objects? They aren't the same thing at all[0]. The point to ADTs is delimiting the scope where implementation details (e.g., whether a set data structure is implemented as a red-black tree or an AVL tree) are relevant. The point to objects is deferring until runtime the decision to use this or that implementation (e.g., callbacks). ADTs in general needn't pay an indirection tax. And using objects when ADTs suffice for your modularity purposes is a sign of being a very stupid programmer. [0] http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf > If you still pick C for writing your program, you probably don't mind it or have some other reason for sticking with C. The latter.