2.4 A Semantic Space for Templates

  Figure 4 illustrates how we may view the semantics of templates. The meaning of a template is a partial function from behaviors to behaviors. This leads us to define the dependency relationship that is most important for a template, as follows:

$$T\ \textbf{\emph{needs}}\ S \equiv \textbf{dom}(\mathcal{M_{T}}(T)) = \mathcal{M_{S}}(S)$$ (3)

The traditional view of a template is that it is a ``transformation'' which ``generates'' an operational program component when it is instantiated , i.e., when it is given another operational program component as an actual parameter. The actual parameter C cannot be just anything; it must implement some specification S. The resulting component C then implements some (usually different) specification S'. This is what we might call the ``macro expansion'' view of a template: C can be obtained by substituting C for the template formal parameter wherever the latter occurs in the string T. In fact, this is how most compilers deal with templates.

  

Figure 4: $\mathcal{M_{T} : T \rightarrow (B \rightarrow B)}$

The view suggested by Figure 4 differs subtly in that a template transformation is one of behaviors (on the diagram's right side), not of strings (on the left side) [Edw95]. When a software engineer creates a template T, whose meaning is some partial function $\mathcal{M_{T}}(T)$, part of the job is to state precisely the domain of this partial function. This is tantamount to characterizing which components T could accept as an actual parameter when instantiated. Defining the domain of $\mathcal{M_{T}}(T)$ is now accomplished by choosing a specification S whose meaning $\mathcal{M_{S}}(S)$ is exactly the subset of behaviors for which $\mathcal{M_{T}}(T)$ is defined.

  

Figure 5: The meaning of template instantiation: applying $\mathcal{M_{T}}(T)$

Figure 5 illustrates how template instantiation works in this framework. Determining the meaning of the instance of T with C as the actual parameter does not involve textual substitution of C for the formal parameter of T. The instantiation simply means $\mathcal{M_{T}}(T)(\mathcal{M_{C}}(C))$.

For example, one way of building a symbol table is to store entries in a binary search tree. We might write code that uses binary search tree functionality as a template T, for which each instance implements a symbol table specification S'. This defers, until system integration time, the choice of implementation C for binary tree specification S. T simply demands the availability of some -- any -- implementation of S. When a particular C that implements S has been selected, the system builder provides it as the actual parameter when instantiating T. The resulting instance has a meaning which lies in $\mathcal{M_{S}}(S')$, i.e., the meaning of the symbol table specification S'.

Most software engineers and programming language designers seem to view templates from the macro expansion viewpoint. So generally it might be appropriate if all the semantic functions involved were consistent with the macro expansion view, to keep the latter from being misleading. In other words, if C' is the result of the string substitution of C for the formal parameter of T, then it should be the case that $\mathcal{M_{T}}(T)(\mathcal{M_{C}}(C))\ =\ \mathcal{M_{C}}(C')$. However, a string transformation resulting in C' technically is not required to define the meaning of T or any instance of T.

The reader should find it a good test of understanding of this framework to be able to identify not just symbolic but physical artifacts that arise in the engineering of physical systems, and which play the same role as templates play in the software world. This emphasizes why it is significant that instantiating a template should not, in general, be viewed in terms of string substitution.

What about specification templates? Although space limitations preclude discussion here, we see the appropriate semantic space for these units being $\mathcal{B} \rightarrow \mathcal{P(B)}$. See [Gib97] for details.