#### Archived

This topic is now archived and is closed to further replies.

# "Concepts" and Generic Programming

This topic is 5833 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Over and over agaon on these forums I see questions about how to organize bunches of objects and perform common operations on them. Most of the time, the answer given is to create an inheritance heirarchy and provide an interface class at the root (with a generic name like CObject or CCreatures - why do name warts persist anyway?). The reasoning is that these objects share common properties and thus can be connected in this way, which is quite sound. The question, therefore, is whether or not the use of concepts and generic programming can replace this (sometimes messy) use of inheritance and polymorphism, and whether it provides any practical gains in terms of code size and maintainability. Oh, but what are concepts some of you ask? A concept (in this particular context - generic programming, hereinafter GP) is an abstract specification of the requisite properties of a type in order for a generic algorithm to be applied to it or a generic data type be instantiated by it An example of a concept would be iterators in the Standard Template Library. The various iterator types require varying functionality (pre- and/or post-increment, access by dereference, etc) and embody different variations on the concept - refinements in this case because they place additional requirements on the base iterator concept. Obviously, a concept thus defines an abstract type - much like a (pure virtual?) base class. Unlike a base class, a concept isn''t necessarily expressed in code: a simple concept might be that the type provide an Update method (perhaps to be called while iterating through a sequential container). An immediate advantage of concepts over inheritance heirarchies is that the programmer does not have to locate her new class in the inheritance "family tree"; each instantiation of the concept can be completely independent (or may utilize inheritance as well). But what about virtual functions and the ability to fall back on that code? It means we only write the code once unless a particular class needs to override the base version. Well, in generic programming we only write the code once as well, and provide (partial) template specializations where we deem necessary. Unlike with virtual functions, however, there is no confusion when different ancestors in the inheritance tree override the base function; template specializations are unique. Another benefit of concepts and generic programming is the fact that a class can easily conform to multiple concepts (even retroactively) without upsetting any other functionality (so long as the concepts do not require, say, member functions with identical signatures). A convenient example is the .begin() and .end() methods provided by sequential STL container classes which allow the controlled sequence to be accessed via input and/or output iterators. To fit into multiple heirarchies, a class must engage in multiple inheritance which is often a troublesome topic. Is it then only ignorance of the power and availability of concepts and generic programming that keep them from proliferating all the more, or are there other issues involved? It is known that C++ is not well taught (both online and off), and Java, for one, as yet lacks generic programming facilities. Are these major contributing factors? Do you agree or disagree with my analyses? What are your opinions and experiences on/with concepts and generic programming?

##### Share on other sites
I was about to post a quick reply along the lines of "there are things you can''t solve with generic programming", but then I decided to try it out in my compiler first.... and found out I was wrong

Generic programming can be a very powerful tool to allow for "interfaces", without ANY underlying assumption aside from having a particularly named member function in the class around which the template is being instantiated - a problem I''ve run into more than once.

So I guess you''re partially right in that C++ isn''t really being taught to its full potential. I could have used this method of specialisation a lot!

People might not remember what you said, or what you did, but they will always remember how you made them feel.

##### Share on other sites
As far as concepts are concerned, the C++ Standard committee once considered the addition of signatures to the language. When a function declared a signature as the type of its parameter, the parameter's actual interface would have been checked for the presence of all the methods present in the signature's declaration, without need for the object to actually inherit from the signature. Thus no hierarchy would be involved. It was dropped.

(Note to Hackers: g++ 2.95 still has signatures as a deprecated feature. They're gone from g++ 3.0 ).

Good idea ? Bad idea ? C++ templates are somewhat more versatile though not as intuitive. One typical gripe is against the error reporting, when the failure occurs deep inside the STL. Boost now provides static concept-check facilities (dynamic behaviour is still the exclusive domain of OOP), but it is a tad late for the reputation of the STL.
The page-long error messages produced by parameterized classes did little to help either, especially when policy classes (e.g. Allocator, traits classes...) get involved. Things are getting better (VC7, g++3), but it's still not ideal.

And even if you stay within the boundaries of ANSI C++, templates are a relatively recent feature. Feature support was sketchy until recently, e.g. VC's issues with partial specialisation (no boost::lambda for you) or the broken STL implementations (Dinkumware).

The STL may have some tricky issues but they aren't overwhelming, (e.g. modifying a sequence while iterating), but books like Meyer's Effective STL help a lot. Problem is to find the right books, and to be willing to learn.

As long as there are people (e.g. here on gamedev) still caught using deprecated libraries (prestandard iostream), obsolete documentation (idem), or simply poorly-written books -- novices are a prime and hight vulnerable target -- you shouldn't be surprised that 'advanced' concepts' (read - anything somewhat counter-intuitive, or not covered in "The Complete Idiot's Guide to Beginner's C++ for Dummies in 24 hours" ) remain largely ignored (unless you're a software engineer, then you invent programming paradigms).

Now, if you are willing to give compile-time type safety up, you can move on to languages like ObjectiveC or SmallTalk, where call-by-name is the norm : regardless of the place of your type in the OO hierarchy, if it implements a method with a matching signature, the call is made; if not, you're in deep trouble. They essentially merge GP and OOP, which is why SmallTalk is still popular nowadays : in that respect it is more flexible than C++.

In my personal experience, people just go by the STL's reputation (lets face it, 'generic progamming' is nearly synonymous with 'C++ STL'). A C (as in 'cast-and-macro') programmer friend's arguments where that C++ templates, along with inheritance and overloading, could too easily be misused... no amount of arguing convinced him.

It stands to reason that once you know one language well enough, you are reluctant to go and learn another one, which doesn't make you immediately productive (case in point, my father uses PCSOFT's WinDev and just cannot find the time, nor the motivation, to learn any other language).

I gave a talk about the STL (though now I think I should have presented it in another way) to my work group; the reactions were mixed though negative overall. I also may actually give an exposé (and possibly a series of C++ lectures if I find the time and if there is some interest) to the incoming graduate class when fall comes.

To conclude, let me point out N. Josuttis upcoming book C++ Templates which should be a more approachable introduction to GP (along with Koenig & Moo's Accelerated C++) than Modern C++ Design.

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]

[edited by - Fruny on June 25, 2002 6:17:11 AM]

##### Share on other sites
In my latest project, I''ve been almost exclusively using a generic programming standpoint. Unless a problem has specifically required some type of polymorphism (which could be solved using function pointers, but less cleanly), I''ve been using a templated approach. There are two things which don''t sit very well with me, however.

One is that I don''t actually have an in-code specification for certain generic types. For instance I might have a renderer implementation without a need for a base class. Without the need for some kind of abstract base class, there is no clean way to enforce a particular interface that I have seen, that the compiler can use. Instead, errors will manifest themselves when functions are asked to be called which do not exist in an implementation.

The second issue deals with compatibility. If I have a templated media system which takes a renderer and a windowing system as parameters, there are no clean facilities to check whether or not the chosen implementations of the renderer and windowing system are even compatible with one another. Instead, the compiler may flag errors which are indirectly related (when I ask for a clean facility, I basically mean a facility which directly checks your concepts, rather than falls back on indirect errors), or the compiler will not find any errors at all, but your program will crash at run-time.

Certainly you can avoid these two issues if you are careful in your design. But better explicit support to address these issues would certainly be nice.

"Don''t be afraid to dream, for out of such fragile things come miracles."

##### Share on other sites
Thank you for very well-reasoned responses.

MKV:
I''ve sometimes wondered whether it would be worth the while to write a free compiler that encourages/emphasizes Standard C++ (C++98) as a teaching tool to wean the masses off the old ways - with appropriate documentation, of course.

Fruny:
I''m not sure how I feel about signatures; I think I''d have voted against them had any asked me. I do think, though, that it would be useful to have a method of specifying concepts in code as Redleaf said. I remember an article in CUJ about parsing STL error messages (MSVC) - primarily stripping out/condensing the template type descriptions. Better debugging support would probably help with the acceptance of generic programming (correctly, as you said, represented to most by the STL), but since so few are aware of it or have tried it if aware, it''s probably not as impactful as I might imagine.

Redleaf:
Currently, the only way to "specify" concepts in code, and I use "specify" loosely, is selective use of template type names:

template < typename ConceptType > class SomeClass {...};

for a class that is to be instantiated by a ConceptType. ConceptType must, of course, be documented somewhere the programmer has acccess to - perhaps in comments?

There are some template metaprogramming tricks that can be used to ensure certain properties of the classes used to instantiate the template (for example ensuring that the class declaration exists in full), but they are limited in scope and fairly convoluted. It would be nice to have a language feature to completely specify the concept and ancillary co-relationships as well.

Oh, well...

##### Share on other sites
Well, remember writing some OO code for the first time?
Writing good templates is hard too. Perhaps harder, because it''s a less mature technique.

I just want to emphasize that templates are not a replacement for OO (nor vice-versa). They compliment eachother. Templates are for compile-time polymorphism, OO is for run-time polymorphism. You can emulate one using the other, but the results are horrendous in both cases.

quote:

One is that I don''t actually have an in-code specification for certain generic types.

Looks like the history is ''signature'' is the experimental (and deprecated) construct to model concepts in code. Perhaps it (or something like it) will be revisited in the near future with C++0x, the idea wasn''t really fleshed out until the BGL was developed, even though the stl makes extensive use of them.

The other problem with concepts, is how would you define them? One of the nice thing about concept-based generic programming, is that you only have to implement what is required. Adding signature/concept checking would defeat that, unless it everything in it was optional... which begs the question, why formally define it?

If you do want something in code now, you can make an template base class for the concept definition, and place a CompileTimeAssertion inside each concept''s methods. Inheriting from the impure base mean there''s no virtuosity overhead, but the base class method will be invoked unless you override them in the derived class. If a base class method is invoked, you''ll get a CompileTimeAssertion from the base template code, IFF that method is required.
(And if you''re a lazy bastard like me, you''d use a macro around the method names to automagically generate the code for the compile-time-assertions).
If you do try this, lemme know how well it works out.

quote:

To fit into multiple hierarchies, a class must engage in multiple-inheritance which is often a troublesome topic.

The only troublesome aspect of MI, is the ''dreaded-diamond shaped-inheritance''. This issue is entirely avoided by templates, because you "instance" a class using a template. Each ''template class instance'' is unique, ergo you never generate the dreaded diamond (or at least, it''s completely feasible to utterly avoid it). (Yes, if you place a static in a template, they don''t collide, each class definition get''s its own static property - it is exactly as though you defined two different classes).

quote:

Another benefit of concepts and generic programming is the fact that a class can easily conform to multiple concepts (even retroactively) without upsetting any other functionality

Yes, this a testament to their reusability. Also note that generic algorithms can adapt to existing non-generic legacy code, and are forward-compatible with new libraries. Again, I direct your attention to the BGL, and their property map, which allows you to choose the representation and interface to your graph data. Obviously using the provided representations is painless, and pre-built adaptors are provided for popular libraries such as LEDA. Supporting a new C or C++ based graph library is just a matter of writing the property map for it.

quote:

Is it then only ignorance of the power and availability of concepts and generic programming that keep them from proliferating all the more, or are there other issues involved?

Templates raise the abstraction bar above the heads of all but the largest corporations. The additional abstraction makes it that much more difficult to design & implement the library. It''s unattractive to a company to massively over-engineer their design & code, and then give away the source for anyone to use it.
Most template libraries are truly free - not some viral GPL "free".
I think the intrinsic openness of template libraries is a good thing, because it promotes peer-reviewed template libraries for everyone to use.

There’s a lot of template libraries already available, and as it’s the nature of the beast, they tend to focus on very broad (one could say generic) programming domains.

##### Share on other sites
quote:
Original post by MadKeithV
I was about to post a quick reply along the lines of "there are things you can''t solve with generic programming", but then I decided to try it out in my compiler first.... and found out I was wrong

With the advent of partial specialization, it was shown that C++ templates (alone) formed a turning complete language.

And you thought IOCCC C entries were hard to follow...

##### Share on other sites
quote:
Original post by Magmai Kai Holmlor
With the advent of partial specialization, it was shown that C++ templates (alone) formed a turning complete language.

And you thought IOCCC C entries were hard to follow...

I really miss partial specialisation in Visual C++. Ironically, the very first major problem I ran into when trying to learn templates/generic programming was exactly that. I was writing template vector classes (the mathematical concept, not the container type), and wanted to "partially specialise" for 2D, 3D and 4D those operations which I knew to be performance critical.

And THEN I ran into the "not supported" section of the MSDN

People might not remember what you said, or what you did, but they will always remember how you made them feel.

##### Share on other sites
The most popular compiler in the world does not like templates. (VC++ 6), that''s why GP is not popular enough.

There are also some old programmers around which refuses to learn about GP and STL. Sadly, there are in a higher management position and makes decisions on the project rather than the younger STL capable programmer.

For usings GP and cepts to replace inheritance, I believe you have to use PTS (Partial template specialization). It''s messy and "popular" compiler don''t support it.

I find virtual functions wins.

For the case of the concept providing a "Update" method, you would not be able to store it in a STL container. You can''t have different templates types, without resorting to a base template class and PTS or the boost "any" library.

Which again defeats the purpose of trying to use GP as inheritance, no?

##### Share on other sites
quote:
Original post by Void
You can''t have different templates types, without resorting to a base template class and PTS or the boost "any" library.

Which again defeats the purpose of trying to use GP as inheritance, no?

As far as I see, it doesn''t - since in the case of inheritance, you would need to derive anyway. Using Generic Programming AND Inheritance/Polymorphism, you can create a base class that provides the basic "Update" method, purely virtual or any other way you like. Then using templated classes derived from the base class, you now have a class-unaware mechanism for "polymorphic" code calling.

Like the following:

  class A{public:void Update() { cout << "This is A"; }};class B{public:void Update() { cout << "This is B"; }};class BaseGenericUpdateClass{public:virtual void Update() = 0;};template< class T >class GenericUpdateClass : public BaseClass{public:GenericUpdateClass();~GenericUpdateClass();void Update() { m_t.Update(); }private:T m_t;}typedef GenericUpdateClass< ClassA > AUpdate;typedef GenericUpdateClass< ClassB > BUpdate;typedef stack<BaseGenericUpdateClass * > GenericUpdateContainer;GenericUpdateContainer c;AUpdate *a = new AUpdate();BUpdate *b = new BUpdate();c.push( a );c.push( b );while( !c.is_empty() ){BaseGenericUpdateClass *pUC = c.pop();pUC->Update();}

The advantage of the above code over "normal" inheritance-only polymorphism is that the container now contains implementations that have nothing do to with eachother, class-wise, but simply provide an update method. ANYTHING that provides the Update method can be wrapped in the GenericUpdateClass - and with some extra work you can even Update classes that have a differently-named Update function - using either partial specialisation of the GenericUpdateClass, or deriving another class from BaseGenericUpdateClass.

The downside is that compile-time checking will only throw an error if you actually try to instantiate a typedef that is invalid - for which there are workarounds, but you still have to be diligent enough to do them.

People might not remember what you said, or what you did, but they will always remember how you made them feel.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 14
• 12
• 9
• 12
• 37
• ### Forum Statistics

• Total Topics
631425
• Total Posts
3000015
×