Polymake is accompanied by a moderate collection of template classes that have proved to be useful for development of the client programs. Throughout this documentation it is called Polymake Template Library (PTL). It is designed in the spirit of and based on the STL. It should by no means be seen as an independent, self-consistent, or in whatever sense complete product, as it is being developed gradually and by demand, along with new polymake clients. On the other hand, there is no reason to hide it from the polymake users, as it provides a good starting point for any individual extension of the polymake system.
Not every class defined in PTL is of interest to a developer of client programs. There are a lot of auxiliary helper classes, whose purpose one could classify, according to the recent trends, as a sort of meta-programming. Therefore the main focus of this documentation lies on the really important classes, such as vectors, matrices or graphs. The separation in "important" and "auxiliary" classes is also manifested in their assigning to various namespaces.
As already mentioned, PTL is based on STL and makes exhaustive use of the three main concepts of the latter: containers, iterators, and functors. There is a subtle difference, however, in the implementation of algorithms: in STL, they are designed to work with iterators, while in PTL the most of them accept containers as arguments. PTL containers are more than pure data structures, they bear some additional semantic, in that they belong to one of the generic families.
Besides of real containers, which own their data as prescribed by the standard, PTL makes a heavy use of pseudo-containers classes. The latter implement though the standard container interface, but do not possess any data at all; instead, they refer to other container objects supplying the data items. There are three kinds of pseudo-containers in PTL: alias, masquerade, and lazy containers.
Many operators defined for PTL container classes, such as vector and matrix arithmetic, set-theoretical operations, etc., don't perform the computations immediately, but rather create a temporary object which "remembers" the operands and the operation and evaluates it later, on demand. This is a well-known technique called lazy evaluation, sometimes also referred to as expression templates. It helps to spare unnecessary computations and copying of objects.
The lazy objects fit well in the container concept of PTL, as they always belong to the same generic family and implement the same container interface as the result of the real operation would do.
The most of top-level PTL data structures keep their data attached to a smart pointer combined with a reference counter.
This technique provides for cheap copy and assignment operations and return of complex objects by value.
As long as several objects are not changed, they can safely share a single physical collection of data.
A non-const access eventually forces the creation of one's own copy of the data (so called copy-on-write strategy.)
Obviously, there's also a drawback of reference counting, since the counter checking produces some overhead.
So, one should declare one's objects const whenever one can - this will surely bring a considerable runtime gain.
In general, another danger usually entailed by reference counting is the possibility of creating self-referenced cyclic structures which can never get destroyed. However, this is impossible in the PTL, since we do not use any recursive list structures.
Many of the PTL container classes have "relative" classes having much the same sematics and interface but different data organization as the "primary" class. Especially the wide deployment of the lazy evaluation technique has born a plenty of relative classes. For instance, an object representing a sum of two vectors or a slice of a vector (both using lazy evaluation) should be usable in every context where a normal vector object (or at least an immutable one) is accepted.
The classical approach here would be to define an abstract vector base class with all methods declared as pure virtual functions, and derive everything from it. Although it would be a clearer design, it causes a serious performance penalty due to the fact that virtual functions practically inhibit inlining, and thus impair the compiler's optimization. Fortunately, a template library can make use of more tricky concepts.
A generic class is a template analogon for a classical abstract class. PTL defines a generic class template
for each family of related classes, for instance, GenericVector
for everything looking like a vector. As in the abstract class approach, all concrete classes have to be derived
from the generic class. And exactly as an abstract class, a generic class should not be instantiated "naked"; to
enforce this, its constructor and destructor are always defined protected.
To eliminate the need for virtual functions, an instance of the generic class has to know statically (i.e., already during the compilation,) what concrete class it belongs to. This is achieved by parameterizing the generic class (you remember, it's a template!) with the concrete class derived from it. Staying by the vectors, an example would look like this:
template <typename _Vector>
class GenericVector {
typedef _Vector top_type;
...
};
template <typename ElementType>
class Vector : public GenericVector< Vector<ElementType> > ...
It this setting it is very easy for the generic class instance to achieve the full concrete object: it's just
a static_cast<top_type*>(this). Such an inverted cast is explicitly allowed by the ANSI/ISO
Standard C++. To keep the code more readable, each generic class defines a top() method encapsulating
exactly this cast (in fact, two methods, with and without const.)
The same cast can be applied by every external function working with class families as well:
template <typename _Vector>
void f(const GenericVector<_Vector>& v) {
int s=v.top().size();
...
}
In many cases, however, the cast is not necessary, since many methods are defined already in the generic class; please consult the documentation of the corresponding class family.
The generic classes can also carry additional attributes, allowing for more fine-granular distinction between
overloaded template functions. All these attributes are declared with default settings extracted
from the concrete class, therefore the application functions don't always need to refer to them explicitly.
The real PTL definition of the GenericVector class has the vector element type as the second parameter:
template <typename _Vector, typename ElementType=typename _Vector::element_type>
class GenericVector {
typedef ElementType element_type;
...
};
Now you can easily distinct between two versions of an algorithm, one requiring two vectors of identical element type, and another handling the heterogeneous case:
// homogeneous case template <typename _Vector1, typename _Vector2, typename ElementType> void f(const GenericVector<_Vector1, ElementType>& v1, const GenericVector<_Vector2, ElementType>& v2); // heterogeneous case template <typename _Vector1, typename _Vector2> void f(const GenericVector<_Vector1>& v1, const GenericVector<_Vector2>& v2);
Caveats
However smart this technique might be, it has its not negligible caveats. First of all, it is the problem of so called
code bloat: each function designed to work with a generic family has to be a template in its turn.
Often this "templatization" spreads itself over the entire program module, stopping only at the main()
function. This leads to considerable code size growth and to an immense time and memory consumption by the compiler.
Another problem arises when you make a mistake in your template code: the compiler diagnostics are very heavy to understand, most of them referring to the code you had not written yourself, namely the guts of the template library. Mistakes also often stay undiscovered for long periods of time, until the method containing it is really used (due to the lazy template instantiation deployed by the most of the modern C++ compilers.) There are some recently invented approaches that can alleviated this, in particular the concept checks originating from the Boost library. They will be probably built in PTL, as soon as their deployment in STL will seem stable enough.