Dr. Carlo Pescio
Tabelle Compile-Time come Metaprogrammi Template

Pubblicato su C++ Informer No. 1, Dicembre 1997

Uno dei primi "trucchi" che si imparano quando si inizia a scrivere qualche programmino grafico e' di pre-calcolare tutto il possibile: in questo modo possiamo sfruttare al massimo la potenza di calcolo per svolgere i soli compiti essenziali durante le animazioni. La fase di pre-calcolo puo' avvenire allo startup del programma, ma naturalmente questo porta ad un rallentamento iniziale. Possiamo anche pensare di pre-calcolare i dati separatamente, ed introdurli nel programma come array di costanti; in questo caso non avremo rallentamenti a run-time, ma ovviamente la manutenzione del codice diventera' piuttosto pesante.
Il problema del pre-calcolo non si applica solo ai programmini di grafica: anzi, ogni tanto emerge in contesti decisamente inaspettati. Recentemente, nella progettazione del software per un sistema embedded ci siamo trovati in una situazione abbastanza complicata:

- il dispositivo doveva essere operativo "immediatamente" dopo l'accensione, senza pause dovute all'inizializzazione.

- l'hardware target era piuttosto economico (come sempre nei sistemi embedded) e quindi pre-calcolare alcune tabelle sarebbe stato un grande vantaggio.

- il pre-calcolo aveva come risultato valori interi, ma alcuni passi intermedi erano piu' semplici da svolgere in floating point. L'hardware target non disponeva di istruzioni per floating point, che dovevano essere emulate via software (quindi in modo "lento").

- non avevamo memoria di massa, quindi non potevamo mettere le tabelle in file esterni all'eseguibile.

- volevamo evitare gli inevitabili problemi di manutenzione dovuti ad eventuale codice con tabelle di valori inseriti esplicitamente.

Molto spesso in situazioni cosi' controverse si riuncia a soddisfare uno dei requisiti, tipicamente l'ultimo perche' il software e' comunque la parte piu' malleabile. A volte, pero', spendere un po' piu' di tempo a pensare e progettare porta ad un risultato di gran lunga migliore.
In questo caso particolare, sarebbe stato un grande vantaggio poter descrivere il contenuto della tabella tramite un algoritmo, non come insieme di valori, ma fare in modo che l'algoritmo venisse eseguito a tempo di compilazione. In tal modo, il risultato finale sarebbe stato un codice mantenibile ed un eseguibile contenente i valori precalcolati: il meglio dei due mondi.
In C++, questo e' ottenibile usando una tecnica di programmazione relativamente recente, nota come template metaprogramming [1], [2], che mi ha gia' permesso di affrontare e risolvere diversi problemi considerati "impossibili" [3], [4].
Anche in questo caso, una soluzione completa al problema delle "tabelle precalcolate" come metaprogramma richiede poche righe di codice, e si riusa con facilita'. Come sempre, ottenere codice facile da riusare significa impegnarsi un po' di piu' nelle prime fasi dello sviluppo, in cambio di benefici in fase di manutenzione e di futuri sviluppi.
L'intera implementazione si riduce al seguente listato, che comprende anche due esempi di utilizzo:

// -- codice riusabile di pre-calcolo

template< int i, int j,  class F, class V > struct T ;

template< int i, class F, class V > struct T< i, 0, F, V >
  {
  T() {}
  V val[ i ] ;
  V operator[](int n) const { return( val[ n ] ) ; }
  } ;

template< int i, int j, class F, class V > struct T :
public T< i, j - 1, F, V >
  {
  T() { val[j-1] = F::f(j-1) ; } 
  } ;

template< int d, class F, class V = int > struct Table :
public T< d, d, F, V >
  {
  Table() {}
  } ;

// -- Due semplici casi di utilizzo:

// Una funzione che eleva al quadrato
struct Square
  {
  static int f( int i ) { return i * i ; }
  } ;

// Una funzione che eleva al cubo
struct Cube
  {
  static int f( int i ) { return i * i * i ; }
  } ;


int main()
  {
  // Una tabella con i primi 4 quadrati
  // (come interi)
  const Table< 4, Square > t ;

  // Una tabella con i primi 3 cubi,
  // come double
  const Table< 3, Cube, double > t1 ; 
  
  // si usano come normali array
  int n = t1[ 2 ] ;  
  int m = t[ 1 ]  + n ;

  return( 0 ) ;
  }
Vediamo nel dettaglio l'implementazione, che ha comunque richiesto l'uso di alcune recenti estensioni del C++ (specializzazione parziale, default template parameter), e che pertanto non funziona ancora su diversi compilatori (tra cui Microsoft e Borland).
Per ottenere una tabella precalcolata dobbiamo dapprima definire una struct opportuna, che implementi una funzione inline f( int ), avente il compito di valutare l'elemento i-esimo della tabella. Nel listato sopra, due esempi sono la struct Square, che usiamo per per-calcolare una tabella di quadrati, e Cube che usiamo per una tabella di cubi.
Per definire una tabella basata su una struct S ed avente dimensione (ad esempio) 3 scriviamo poi:

const Table< 3, S > t ;
Notiamo che, essendo una tabella pre-calcolata, la dimensione dovra' avere un valore noto a compile-time, tipicamente una costante come nell'esempio sopra.
Il compilatore espande questa dichiarazione in:
const Table< 3, S, int > t ;

in quanto il terzo parametro di Table ha come default int (questo corrisponde all'idea che in molti casi reali, le tabelle precalcolate saranno a valori interi). Nuovamente (si veda la definizione di Table), questo corrisponde a:

const T< 3, 3, S, int > t ;
Questo corrisponde a chiamare il costruttore di T< 3, 3, S, int > sull'oggetto t. Come e' fatto questo costruttore? Torniamo a vedere la dichiarazione del template T. Nel caso generale e' data come segue:

template< int i, int j, class F, class V > struct T :
public T< i, j - 1, F, V >
  {
  T() { val[j-1] = F::f(j-1) ; } 
  } ;

Il che corrisponde a dire, nel nostro esempio concreto:
struct T< 3, 3, S, int > : public T< 3, 2, S, int >
  {
  T() { val[ 2 ] = S::f( 2 ) ; }
  } ;

Ovvero, T< 3, 3, S, int > deriva da T< 3, 2, S, int > e inizializza il terzo elemento (indice 2 partendo da 0) dell'array val usando S::f( 2 ).
Il compilatore deve ora istanziare T< 3, 2, S, int >, e chiamarne il relativo costruttore, essendo questa una classe base di T< 3, 3, S, int >.
T< 3, 2, S, int > sara' a sua volta derivata da T< 3, 1, S, int > e inizializzera' il secondo elemento di val. T< 3, 1, S, int > sara' derivata da T< 3, 0, S, int > ed inizializzera' il primo elemento di val. Naturalmente occorre impedire una regressione all'infinito: per fare questo nei metaprogrammi si usa la specializzazione dei template. In questo caso usiamo la specializzazione parziale (in quanto non specializza tutti i parametri, ma solo alcuni, in questo caso solo il secondo):

template< int i, class F, class V > struct T< i, 0, F, V >
  {
  T() {}
  V val[ i ] ;
  V operator[](int n) const { return( val[ n ] ) ; }
  } ;
Come vedete, questa versione del template "fissa" il terzo parametro a 0, che pertanto sparisce dalla lista dei parametri. Quando il compilatore deve istanziare T< 3, 0, S, int >, non usa la clausola generale come ha fatto sinora, ma quella piu' specializzata possibile, ovvero quella sopra. La versione specializzata dichiara l'array dei valori (utilizzando la dimensione, rimasta inalterata nel primo parametro del template, ed il tipo, dato dal quarto parametro), e definisce l'operatore [] per accedere agli elementi.
Riassumendo, il codice generato dal compilatore nel caso di
const T< 3, 3, S, int > t ;

dichiara un oggetto t contenente un array (di nome val) di 3 interi, e ne inizializza il contenuto come segue:

t.val[ 2 ] = S::f( 2 ) ;
t.val[ 1 ] = S::f( 1 ) ;
t.val[ 0 ] = S::f( 0 ) ;
S::f e' una funzione inline, che viene espansa dal compilatore; se i suoi parametri sono costanti (come in questo caso), viene anche valutata a compile-time su ogni buon compilatore.
Supponiamo che il parametro S sia in realta' Square, la struct data nell'esempio precedente. Allora il codice diventa:

t.val[ 2 ] = 4 ;
t.val[ 1 ] = 1 ;
t.val[ 0 ] = 0 ;
Ovvero una tabella, calcolata a compile-time, contenente i primi tre quadrati; il compilatore ha trasformato il nostro codice iniziale, che fa solo riferimento ad un algoritmo, in un insieme di valori, tutto a tempo di compilazione. Ovviamente, scrivere funzioni che pre-calcolino (ad esempio) tabelle di seni e coseni e' un po' piu' difficile di Square e Cube, e richiede tipicamente di espandere in serie la funzione, ma la soluzione data sopra si puo' utilizzare in generale: e' sufficiente implementare la struct/funzione che genera i singoli elementi della tabella, ed il codice generale di pre-calcolo si occupera' del resto. Una nota finale: avrete notato che il template Table ha la sola funzione di fornire un default per il tipo degli elementi e di derivare dal template T, passando due volte la dimensione. Il primo parametro manterra' il valore sino alla fine, e sara' usato dalla clausola di specializzazione parziale per dimensionare l'array. Il secondo diminuira' ad ogni passo, e sara' usato dalla clausola generale come indice dell'elemento da inizializzare.
Questa idea di "sdoppiare" un parametro e' forse l'elemento piu' "creativo" del metaprogramma, poiche' non e' direttamente suggerito ne' dal problema iniziale, ne' dalla pratica della metaprogrammazione. Si tratta pero' di una tecnica che torna utile in diversi casi, probabilmente un piccolo pattern/idioma di codifica che non e' ancora stato classificato. Sicuramente, ricordo di averlo usato parecchi anni fa in Lisp, ed anche piu' recentemente in assembly [5]. E' sempre interessante scoprire che alcune idee, apparentemente limitate alla risoluzione di un singolo problema, finiscono poi per avere un impiego molto piu' generale del previsto.

Bibliografia
[1] Carlo Pescio, "Algoritmi come Metaprogrammi Template in C++", Computer Programming No. 56.
[2] Todd Veldhuizen, "Using C++ Template Metaprograms", C++ Report Vol 7 No 4.
[3] Carlo Pescio, "Binary Constants using Template Metaprogramming", C/C++ Users Journal, February 1997.
[4] Carlo Pescio, "Portable Parameterized Integers Using Template Metaprogramming", C++ Report, July/August 1997.
[5] Carlo Pescio, "Sorting in Small Memories", Electronic Design, Vol. 44 No. 8, April 1996.

Biografia
Carlo Pescio (pescio@eptacom.net) svolge attività di consulenza, progettazione e formazione in ambito internazionale. Ha svolto la funzione di Software Architect in grandi progetti per importanti aziende europee e statunitensi. È autore di numerosi articoli su temi di ingegneria del software, programmazione C++ e tecnologia ad oggetti, apparsi sui principali periodici statunitensi, nonché dei testi "C++ Manuale di Stile" ed "UML Manuale di Stile". Laureato in Scienze dell'Informazione, è membro dell'ACM, dell'IEEE e dell'IEEE Technical Council on Software Engineering.