Sind rekursive Templatefunktionen wohlgeformt?

otze

Hallo,

ich versuche in letzter Zeit, meine Templatekonstrukte einfacher lesbar zu machen, indem ich sie viel stärker wie normalen Code aussehen lasse. Hier mal ein simples Beispiel:

//Foo ist irgendein typ
struct Foo{};

//Bar ist ein beliebiger Wrapper der Teil eines expression templates ist
template<class T>
struct Bar{
    Bar(T const& t);
    T const& get()const;
};

template<class T>
Bar<T> makeBar(T const& t){
    return Bar<T>(t);
}

//nun möchte ich gerne zählen, ob die Anzahl der "Bar"s 
//in einem template Ausdruck gerade ist
template<class T>
bool evenBars(Bar<T> const& bar){
    return !evenBars(bar.get());
}
bool evenBars(Foo const& foo){
    return true;//0 ist gerade
}

//test:
Foo foo;
std::cout<<evenBars(makeBar(makeBar(foo)));//ausgabe true

Anstatt irgendeinen Klassentyp zu verwenden, bei dem ich dann mit statischen Konstanten den Wert abfrage, möchte ich eine einfache Funktion haben.

Das war das Vorgeplänkel. Nun würde ich das gerne in Templatelogik einbauen:

template<class T>
void myFunc(T const& t){
    //ist die Anzahl der "Bar" in T ungerade, funktioniert myFunc nicht. 
    //Also: gerade machen
    if(!evenBars(t)){
        myFunc(makeBar(t));
        return;
    }
    //okay, Anzahl der Bars ist gerade, hier jetzt irgendwas tolles machen
}

Die Frage ist: ist der Code wohlgeformt? Dies ist ein rekursiver Aufruf einer Templatefunktion, bei der die Typen der Argumente sich ändern. Der Compiler hat also zwei Möglichkeiten:

1. Er instantiiert myFunc<T>. Er analysiert das if() und sieht, dass es entweder konstant true oder false ist. wenn es false ist, optimiert er den Zweig komplett heraus, ohne das Innere weitere zu betrachten. In diesem Fall terminiert das Metaprogramm nach maximal 2 Schritten.

2. Der Compiler instantiiert myFunc<T> komplett ohne die Bedingung des if() zu betrachten. Das heißt er wird als nächstes myFunc<Bar<T> > instantiieren unabhängig des Wertes von evenBars<T>. In der Instantiierung wird er wieder myFunc<Bar<Bar<T> > > instantiieren -> Das Metaprogramm terminiert nicht und der Compiler gelangt in eine Endlosschleife.

Ich bin mir bewusst, dass ich das alles mit Typlogik und verschiedenen Funktion zur besten Zufriedenheit lösen kann. Aber das ist unglaublich viel Aufwand für eine eigentlich einfache Sache.

Sagt der Standard etwas dazu aus, wie der Compiler in einem solchen Fall vorgehen muss? Oder sagt er sogar, dass dieses Programm nicht wohlgeformt ist?

otze schrieb:

wenn es false ist, optimiert er den Zweig komplett heraus, ohne das Innere weitere zu betrachten.

Träumst du? Ein static_if gibt es noch nicht in C++.

Wenn du C++11 verwendest, musst du lediglich eine Überladung von myFunc hinzufügen (dem Rest muss nur noch ein constexpr verpasst werden), das hält sich IMHO noch in Grenzen.

camper

otze schrieb:

Oder sagt er sogar, dass dieses Programm nicht wohlgeformt ist?

nein, der Standard sagt, dass das Ergebnis unbegrenzter impliziter Instantiierung undefiniert ist... also im Prinzip ja (14.7.1/15)

C++11 schrieb:

14.7.1 Implicit instantiation [temp.inst]
[...]
3 Unless a function template specialization has been explicitly instantiated or explicitly specialized, the function template specialization is implicitly instantiated when the specialization is referenced in a context that requires a function definition to exist. Unless a call is to a function template explicit specialization or to a member function of an explicitly specialized class template, a default argument for a function template or a member function of a class template is implicitly instantiated when the function is called in a context that requires the value of the default argument.

===>

C++11 schrieb:

3.2 One definition rule [basic.def.odr]
[...]
3 Every program shall contain exactly one definition of every non-inline function or variable that is odr-used in that program; no diagnostic required. The definition can appear explicitly in the program, it can be found in the standard or a user-defined library, or (when appropriate) it is implicitly defined (see 12.1, 12.4 and 12.8). An inline function shall be defined in every translation unit in which it is odr-used.

===>

C++11 schrieb:

3.2 One definition rule [basic.def.odr]
[...]
2 An expression is potentially evaluated unless it is an unevaluated operand (Clause 5) or a subexpression thereof. A variable whose name appears as a potentially-evaluated expression is odr-used unless it is an object that satisfies the requirements for appearing in a constant expression (5.19) and the lvalue-to-rvalue conversion (4.1) is immediately applied. this is odr-used if it appears as a potentially-evaluated expression (including as the result of the implicit transformation in the body of a non-static member function (9.3.1)). A virtual member function is odr-used if it is not pure. A non-overloaded function whose name appears as a potentially-evaluated expression or a member of a set of candidate functions, if selected by overload resolution when referred to from a potentially-evaluated expression, is odr-used, unless it is a pure virtual function and its name is not explicitly qualified. [ Note: This covers calls to named functions (5.2.2), operator overloading (Clause 13), user-defined conversions (12.3.2), allocation function for placement new (5.3.4), as well as non-default initialization (8.5). A copy constructor or move constructor is odr-used even if the call is actually elided by the implementation. —end note ][...]

Der Ausdruck

myFunc(makeBar(t));

wird potentiell ausgewerted in obigem Sinne (unabhängig davon, dass man ggf. beweisen könnte, dass er für einen bestimmten Typ nie tatsächlich ausgewertet wird), folglich muss die entsprechende Funktion existieren, folglich wird diese Spezialisierung implizit instantiiert werden.

Das ganze funktioniert also nur, wenn du es mit konstanten Ausdrücken zu tun hast, denn dann werden Teile, die nicht ausgewertet werden auch nicht odr-genutzt. Beispiel

template <int N>
struct foo   // Hab den Namen dieser Funktion vergessen 
{
    static const int value = N == 1 ? 1 : N % 2 == 0 ? foo<N/2>::value : foo<3*N+1>::value;
};

314159265358979

Du hast zu viel Zeit, stimmts camper?

Bashar

Kann m.E. nur 2. sein, weil Optimierungen zum Laufzeitverhalten gehören und nicht die statische Typprüfung beeinflussen können.

camper

314159265358979 schrieb:

Du hast zu viel Zeit, stimmts camper?

Scheint so; schliesslich verschwende ich sie, um deine Frage zu beantworten.

otze

Wow. Danke für diese tolle Antwort, Camper. Exakt das, was ich gesucht habe. Naja. Dann überlege ich mir wohl besser was neues, um meine Logik zu vereinfachen. In dem Fall könnte ich auch einfach code duplizierung betreiben und beide Fälle explizit behandeln.

//edit foo ist in deinem Flal wohl die Collatz-Folge?

krümelkacker

314159265358979 schrieb:

Du hast zu viel Zeit, stimmts camper?

Naja, er ist schon recht selektiv, was die Beantwortung von Fragen angeht. Und wenn's dann soweit ist, gibt's meist 'ne gute, ausführliche…

314159265358979

Ich hab das jetzt nicht mal böse gemeint, genau das wundert mich eben. Hätte nicht die Motivation wegen jedem Mist den Standard zu durchsuchen.

camper

otze schrieb:

//edit foo ist in deinem Flal wohl die Collatz-Folge?

ja, allerdings ist mir gerade aufgefallen, dass das Beispiel so nicht funktioniert. Auch in diesem Fall kommt es (ohne zusätzliche Spezialisierungen) zu unbegrenzter rekursiver Instantiierung. Damit die Instantiierung abbrechen kann, müsste nachgewiesen werden, dass foo<...>::value in einem konstanten Ausdurck verwendet werden kann. Dass ist aber nur der Fall, wenn es sich um ein konstantes Objekt handelt (dieser Test erfordert keine Instantiierung), der mit einem konstanten Ausdruck initialisiert wurde (hierfür ist eine Instantiierung erforderlich).

pumuckl

314159265358979 schrieb:

Hätte nicht die Motivation wegen jedem Mist den Standard zu durchsuchen.

Ich wage zu behaupten, dass std::camper da nicht lange suchen muss sondern ziemlich genau weiß, wo die Dinge stehen

314159265358979

Das mag schon sein, aber das auch kopieren und so.