Archivi delle etichette: metaprogrammazione

Template specializzati

Queen_Street_Mill_Warping_5369

In un commento al post Breve paragone tra l’“overloading” in C++, C(11) e Fortran(90) Orlando chiedeva:

cosa cambia con i template?

La risposta in due commenti (1 e 2)

Con i template il C++ “capisce” quali funzioni servono, in base all’uso, e “genera” le funzioni apposite; nello specifico double+double, int+int, double,int. (che queste siano le “deduzioni” del C++ lo puoi vedere usando l’opzione -fdump-rtl-all del gcc e guardando il file .final generato)

p.s. tutto il resto, per lo scopo dell’articolo, è invariato: la differenza è che non siamo stati noi a scrivere esplicitamente le funzioni. Del resto se non vogliamo creare stranezze come quelle della mia miafunz (che calcola di fatto cose diverse) o se abbiamo “solo” l’esigenza della “genericità”, i template tornano utili e ci evitano copia-incolla e copertura di tutti i possibili casi (che siano effettivamente usati o no…)

Nel codice d’esempio avevo esplicitamente definito due funzioni diverse, non tanto nella signature, quanto nella loro funzionalità. Questo escludeva l’uso dei template… In realtà, non proprio… Ed è quello che volevo mostrare in questo post.

Ma prima, qualche ulteriore osservazione.

Quando la miafunz viene chiamata con argomenti il cui tipo non corrisponde a nessuno dei due casi gestiti esplicitamente, il compilatore può applicare le regole di conversione implicita e vedere se riesce a trovare qualcosa di accettabile.

Quando fate di questi esperimenti attivate un po’ di warning accessori. Compilate con

g++ -Wall -Wextra -Wconversion file.cpp -o file

oppure, per gli esempi che usano feature del C++11, con

g++ -std=c++11 -Wall -Wextra -Wconversion file.cpp -o file

Tutte le conversioni che possono potenzialmente dare problemi vengono annunciate con un bel warning. Il codice dell’articolo già citato vi darà un warning su

    return 2.0*a + 2.5*b;

Precisamente:

warning: conversion to ‘int’ from ‘double’ may alter its value [-Wfloat-conversion]

Come ovvio: il conticino lo facciamo con double (2.5*b fa sì che b sia promosso a double) ma poi restituiamo un int. Per far sapere al compilatore che sappiamo cosa accade, possiamo mettere un cast esplicito e così salutiamo il warning.

Potete provare un’altra cosa: rendete d0 un float, invece di un double. Vi accorgerete che il compilatore è perfettamente contento: il float può essere promosso a double senza problemi, e abbiamo una versione di miafunz che accetta un double e un int come argomenti.

Provate il contrario, cioè lasciate che d0 sia double e cambiate miafunz(double,int) così:

int miafunz(float a, int b)
{
    std::cerr << "double, int\n";
    return static_cast<int>(2.0*a + 2.5*b);
}

(Il cast è stato aggiunto per non avere il warning cui accennavo sopra).

Succede una cosa strana: il compilatore ci dice che la chiamata a miafunz(double,int) è ambigua. In pratica sembra che non sappia decidersi se usare miafunz(float,int) o miafunz(int,int). Voi potreste pensare che la scelta sia ovvia (float), ma in realtà in tutte e due i casi la conversione può perdere qualcosa: come può il compilatore decidere? In un certo senso le intenzioni del programmatore non sono chiare: vorrebbe che fosse chiamato miafunz(float,int) perché sa che il d0 contiene un valore tranquillo per un float? O voleva troncare il numero e chiamare miafunz(int,int)?

Anche qui possiamo risolvere l’ambiguità con un cast, se siamo sicuri che non succedano cose brutte con i valori d’ingresso usati…

Template e specializzazioni

Il codice di Orlando di fatto calcola sempre a+b sugli argomenti, mentre con l’overloading esplicito dell’esempio, nel caso di int miafunz(double,int) facciamo proprio un calcolo diverso.

Ora supponiamo che ci vada bene che miafunz possa essere chiamata con tanti tipi diversi, però vogliamo che non sia a+b se viene chiamata con double e int.

Cioè vogliamo un template generico, ma con una specializzazione.

Il C++ ci permette di fornire delle specializzazioni:

#include <iostream>

template<typename T1, typename T2>
int miafunz(T1 a, T2 b)
{
    return a + b;
}

template<>
int miafunz(double a, int b)
{
    std::cerr << "double, int\n";
    return static_cast<int>(2.0*a + 2.5*b);
}

int main()
{
    double d0 = 1.0;
    int di = 2;
    std::cout << miafunz(d0, di) << "\n";
    std::cout << miafunz(5, di) << "\n";
}

Se compilate ed eseguite, l’output sarà

double, int
7
7

Cioè miafunz(d0, di) chiama la versione specializzata per double e int, l’altra chiama uno dei template generati dal compilatore.

Un po’ di introspezione

Con il C++11 abbiamo accesso ad alcune informazione sui tipi dei template. In pratica i template sono diventati ancora più potenti e il programmatore ha ora nuove possibilità all’atto della compilazione.

Come esempio vediamo che è possibile controllare il tipo degli argomenti, sempre a compile time, e decidere di fare cose diverse… senza specializzare il template. (Nel caso dell’esempio direi che è un no-no-no: meglio usare la specializzazione!)

Nell’esempio che segue ho anche usato typeinfo (ok anche pre-C++11), che invece usa informazioni a runtime (cfr. p.es. su Wikipedia, RTTI), che di solito servono per il dynamic_cast.

#include <iostream>
#include <type_traits>
#include <typeinfo>

template<typename T1, typename T2>
int miafunz(T1 a, T2 b)
{
    std::cout <<
        typeid(T1).name() << ", " <<
        typeid(T2).name() << "\n";
    
    if (std::is_same<T1,double>::value &&
        std::is_same<T2,int>::value) {
        std::cout << "cosa?\n";
        return static_cast<int>(2.0*a + 2.5*b);
    }
    
    return static_cast<int>(a + b);
}


int main()
{
    double d0 = 1.0;
    int di = 2;
    std::cout << miafunz(d0, di) << "\n";
    std::cout << miafunz(5, di) << "\n";
}

L’output dell’esecuzione è:

d, i
cosa?
7
i, i
7

Come si può intuire, d sta per double, i per int. Ma i nomi restituiti da typeid(…).name() sono specifici dell’implementazione, cioè del compilatore usato, quindi non vi ci affezionate.

Invece std::is_same è nello standard C++11 e permette di sapere se il tipo T1 è lo stesso di double (nell’esempio specifico), o qualunque altra cosa. Da type_traits abbiamo altre cosucce utili per sapere se il tipo del template ha alcune caratteristiche (provate a dare un’occhiata qui).

Nel nostro caso potremmo volere che T1 e T2 siano tipi aritmetici, perché restituiamo un int e vogliamo che + e * sia interpretabili proprio come ci aspettiamo che lo siano quando di mezzo ci sono solo numeri. In questo caso usiamo std::is_arithmetic<T>::value e nel caso la condizione non sia soddisfatta la compilazione verrebbe bloccata.

A questo scopo possiamo usare static_assert, che mettiamo come primo statement nella funzione:

    static_assert(std::is_arithmetic<T1>::value &&
                  std::is_arithmetic<T2>::value, "non aritmetici");

Se in fase di compilazione l’assertion è falsa, il compilatore dà errore:

error: static assertion failed: non aritmetici

Fibonacci con i template

I template comportano la generazione di codice nel momento della compilazione. In un certo senso sono come le macro, solo che queste non hanno vincoli sintattici (rispetto alla sintassi del C/C++) e sono type-agnostic… anche se si possono usare dei trucchi con typeof — che gcc supporta — e poi abbiamo visto _Generic, che rende una macro non più tanto type-agnostic.

Ma niente di tutto ciò è integrato per bene con le fasi in cui il compilatore conosce il tipo di ogni “oggetto” (che è ciò che ci permette di usare auto, decltype, sizeofstd::is_arithmetic, std::is_same…) Dunque i template sono più intimamente connessi con il compilatore.

Poiché il codice dei template è generato al momento della compilazione, possiamo sfruttarlo per fare un po’ di calcoli che è inutile fare a run-time? La risposta è sì e uno degli esempi classici e tipici può essere quello della successione di Fibonacci. Esiste una definizione ricorsiva molto semplice (quella che vedete su Wikipedia).

Scrivere una funzione che calcoli l’ennesimo termine della successione è qualcosa che dovrebbe risultare semplice. Precisiamo che la ricorsione, in linguaggi che usano lo stack ad ogni chiamata di funzione e non ottimizzano il caso della tail recursion, impone dei limiti (quanto “profonda” può essere la ricorsione prima che lo stack si esaurisca?) e perciò in linguaggi come C/C++ e altri un’implementazione decente della funzione per l’ennesimo termine della successione di Fibonacci cercherà evitare la ricorsione.

Comunque. Vediamo come calcolare un numero della successione al momento della compilazione, usando i template.

#include <iostream>

template<unsigned long long N>
unsigned long long fibo()
{
    static_assert(N > 1, "ops");
    return fibo<N-1>() + fibo<N-2>();
}

template<>
unsigned long long fibo<0>()
{
    return 0;
}

template<>
unsigned long long fibo<1>()
{
    return 1;
}

int main()
{
    std::cout << fibo<89>() << "\n";
}

Lo potete compilare in modo normale, ma in questo caso incappiamo nella stessa trappola della ricorsione. Però è facile, per l’ottimizzatore, “capire” come andrà finire: tutto è già lì, non c’è nessuna informazione che sia presente solo a runtime. Se aggiungete l’opzione -O2 non c’è alcuna chiamata da fare a runtime: il calcolo del numero l’ha fatto in realtà il compilatore! In pratica il codice generato si riduce a qualcosa come:

std::cout << 1779979416004714189ULL << "\n";

Infatti con l’opzione -S potete sbirciare il codice assembly generato:

    subl    $8, %esp
    pushl   $414433753
    pushl   $511172301

Ora lo stack (esp) punta a due parole lunghe (long word; la l della push sta per long), ovvero una quadword (robo a 64bit). L’intel x86 è un processore little endian e questo significa che “scorrendo” la memoria dagli indirizzi più piccoli a quelli più grandi, incontriamo per primi i byte, le word o le long word meno significative.

Dunque il numero a 64 bit a cui ora punta esp (lo stack) è:

414433753 ⋅ 232 + 511172301

Il numero di Fibonacci alla posizione 89 è vicino al limite per un unsigned long long. Se provate ad aumentarlo, vedrete che inizierete a non avere risultati attendibili.

Penso di dovermi fermare qui: ho fatto un post forse un po’ troppo denso.

Post scriptum

Sono uno di quegli sfigati che di default preferisce i 32bit… Compilando l’esempio con -m64 potete vedere che il codice assembly generato è un po’ più chiaro:

    movabsq $1779979416004714189, %rsi

In questo modo è ancora più palese che tutti i conti sono stati fatti veramente a compile time