Separate Compilation for Templates and Run Time Generics
Bill Clare
Template Compilation and Mapping of Capabilities
In some previous postings here, I suggested that current notions for Concepts can be generalized.
This is a short note that attempts to highlight approaches related to separate compilation of templates and, along the way, to suggest how this is closely related to run time support for generic mapping. Since I don’t pretend to be an expert on C++ in particular, there may be some significant shortcomings in the approach suggested here. However, the basics seem sound and readily achievable.
The note attempts to outline an approach to mapping a compiled template to other types, functions, and values. A similar approach could allow type-safe compile time verification for dynamic runtime mappings of compiled templates to actual objects.
The basic mapping issues are independent of notions of Concepts. However, an extension of the basic notions of Concepts is discussed that can considerably generalize this mapping. Concepts are discussed in terms of Capabilities, which are defined as declarations of interfaces between different syntax and programming constructs that have common semantics. The key point is that, in addition to verifying consistency, the Capability specification can also supply a mapping from the use of a syntax construct to that of an actual supplied construct.
This note discusses template compilation in terms of Abstract Types, how these types can be mapped to concrete classes and types, and how Capabilities can provide flexible and general mapping support. In addition, some suggestions are offered on runtime function overloading for discriminated union types.
Template Compilation
Templates, as currently specified, depend on substitution of parameters for their instantiation. An alternative is compilation with incomplete, or Abstract Types, and then mapping, rather than substituting, these types for concrete implementations.
Templates can be compiled with declarations of the constructs they use. In particular, template parameter types can be declared as Abstract Types. Additional declarations specify required relationships among these types, such as derived types, and types used and returned in expressions.
Abstract Types are essentially incomplete class definitions that can be extended to refer to complete concrete types. They abstract from the concept of class in terms of undefined size and layout. Abstract Types abstract from base types in that they can be extended with mappings rather than with derivation. Abstract types can occur for the interfaces of the generic construct as well as for use in internal code. In the former case, generic parameters can be resolved from use of the interface; in the latter case, parameters need to be declared explicitly.
Compilation of the generic assures that the Abstract Types and related declarations are sufficient and consistent. A separate process can verify that a set of supplied declarations are sufficient to map to a complete or partial specialization. This can occur when the mapping is needed, or it can occur independently based on a mapping specification from the required types and functions, to the supplied constructs.
Mapping Abstract Types
Compilation of a template binds its code to offsets in the Abstract Type specification, and its function calls to references. For mapping of offsets to a member function reference or pointer, the mapping simply replaces the pointer. Mapping to other literal values within a class relies on binding to an explicit, or implicit accessor (getter), which uses an offset to the inner member. This offset is then mapped to an actual offset in the concrete type.
This mapping can occur at compile time to create partially or completely specialized classes and functions, based only on the declarations for the generic and support constructs.
Run time mapping allows separately compiled generics to be used with independently compiled objects. Mapping occurs through constructors and initializers. Here, where the compiler would verify the syntax of the supplied parameters, it also creates a mapping to the required parameter. This capability could, and in fact currently does, at least to some extent, occur independently of template generated constructs. Ordinarily, sets of generic parameters that have mutual dependencies need to declared, constructed or initialize together. Otherwise, run time checking is required, in these cases, to ensure that parameters used are consistent with earlier settings.
Capabilities
Capabilities, as an extension of Concepts, are useful in specifying mappings between used and supplied constructs, particular where direct substitution, or language defined conversions, are insufficient.
Capabilities describe, specify and document interfaces, both from the supplier and to the user. They can be specified, symmetrically, by both the user and the supplier. The notion of a capability is, in fact, fundamental to any software; that is, software is built from constructs that use capabilities to construct new capabilities. Understanding a program comes from clear specifications of the capabilities of its constructs and its interfaces.
Users and suppliers of a Capability can be independent of each other and of the Capability mappings. Capabilities provide a specification for what is necessary, sufficient and optional for components to satisfy the interface requirements. This flexibility addresses issues of both under and over specifying a requirement. Ultimately the notion of a Capability removes dependencies, in that code can be extended and to a large extent modified, by the user of the Capability, by the supplier of the Capability, and in the specification of the Capability itself, without impact to the source or object code of any of the other players.
Also the user can provide alternative ways to access a Capability, or a supplier can provide alternative implementations, or both are possible. Algorithms and containers in the STL are good examples of this. Selection of alternatives can often be through function overloading, or a hierarchy of derived classes, or by ordering of explicit mapping functions, or explicit tests can be built into the generic code.
The mapping specification also provides an extension point for inserting generic “aspects”, or observers, for debug, logging, performance monitoring, security verification, notifications, implementation and business metrics, etc.
The notion of Capability is an extension of what is currently proposed for Concepts, and can use much of its approach to syntax. Such declarations are useful even without templates and generic programming. For instance, Alexander Stepanov’s book on software was titled Elements of Programming. The elements happen to be elucidated in terms of general template parameter type interfaces, but much of the discussion applies to software interfaces in general.
In C++, and other languages, a capability to perform an operation (or represent data) can be expressed in multiple ways. For instance, a binary operator such as “add” of comparable, but not identical, types might be expressed as a member function of the class of either type, or as non-member functions with the types in either order. Ordinarily the implementation definitions of these functions are all essentially identical. A more general example might be an iteration Capability that can be supported with a “for” construct or through recursion. More general still might be algorithm or business processes, that can be supported in multiple ways depending on context.
Generic Capabilities
Abstract Types provide a form of Capability. Declarations of these types, as well as ordinary types, can be simplified and enhanced through syntax (and semantic) capabilities of proposed Concepts.
Here, a Capability defines a basic functionality, syntax in which it can be accessed, syntax in which it can be supported and mappings between access and support. So there are three declarations of interest here. Fundamental is the Capability, and particularly a declaration of how alternate specification forms can be mapped to each other. In addition, a user of the capability declares which implementations it needs, and also alternative constructs it can use. The supplier declares which implementations it provides.
This suggests three key words: “capability”, “uses” and “supports”. In a few cases, it is also useful to limit a supplied capability, e.g. “without”. (An example might be to support insert and remove operations for a vector, while disallowing “operator [ ]”. )
Runtime Function Overloading
Much of the power of template metaprogramming comes through the ability to specialize implementations based on function overloading, with specific functions chosen through compile time selection.
Some of this capability could be extended, for both generic and ordinary functions, through runtime selection of overloaded functions. This could be implemented for discriminated unions, which provide an index for identification of the current use of the type. Other means of application determination of a discriminant could also be supported.
Here, the base function passes the argument list to an implementation function accessed through the discriminators from a possibly multidimensional array of function pointers.
In some cases, the compiler could actually build such a table, from available declarations, with exceptions provided for missing entries. Alternatively, missing entries would be flagged by the loader, and run time checks could be made for their existence.
Abstractions
Not surprisingly the basics of template processing deal with fundamental abstractions. Capability, at both implementation and modeling levels, is perhaps the most fundamental of all software abstractions. A small number of examples can suggest the range of applicability.
For template processing, Capabilities deals with different forms of common syntax. For instance, std::invoke has 6 mechanisms for function calls. Mapping of arguments to parameters is an arcane art that can made more accessible; e.g. based on simply declaring a parameter as “in” or “out”. More importantly though, Capabilities address such issues as multiple dispatch and type extensions, other than through hierarchical inheritance. This later is important, for instance, in modelling actor-role relations, and, more fundamentally still, for Entity-Relationship models.
At higher levels, Capabilities address various forms of API’s for invoking common services.
At intermediate levels are abstractions for communication services – serialization, protocols, remote program calls; for data and data structures - transforms, mapping, insert, find; for control structures – choices and pattern selection, visitors, state machines. For instance, in the last example, state is modelled in various implementations as a variable, a function or an object.