Template Metaprogrammierung

Tachyon

knivil schrieb:

Diese Argumentation ist Schwachsinn. Du kannst auch alle Anweisungen des Programms von Hand ausfuehren z.B. mit Stift und Zettel, dauert nur etwas ...

TMP ist mehr als simple Textersetzung. Du gibst ein Code vor (Templates), der ausgefuehrt wird. Ob das zur Compilezeit geschieht, ist dabei voellig irrelevant.

Guck Dir die Definition für "Metaprogrammierung" an. Zum Beispiel im Tanenbaum, oder meinetwegen auch bei Wikipedia.

SeppJ

Tachyon schrieb:

Wie aber lässt du deinen Compiler ohne TMP die Fakultät ausrechnen? (Explizit, nicht darauf vertrauend, dass er 1*2*3*4*5 auswerten wird.)

Das TMP tut doch genau das. Für jedes N wird eine Folge von Konstanten 2..N und das Produkt der Elemente gebildet. N ist kein Parameter der zur Laufzeit änderbar ist, sondern es gint eine zur Compilezeit beststehende Menge an Folgen und deren Produkten. Entweder habe ich ein TMP, welches für jedes zur Compilezeit gegebene N die Konstante berechnet, oder ich schreibe für jedes benötigte N die die Folge samte Multiplikation von Hand hin. Auch muss man in beiden Fällen muss die Rechenvorschrift kennen.

Nein, das tut die TMP eben nicht. Durch TMP wird der Compiler explizit gezwungen, diese Konstanten auszurechnen.

Zeig mir mal wie du mit Arrays und ohne Templates ein static_assert schreibst, welche prüft, ob ein Typ T ein Pointer ist.

Tachyon schrieb:

Ein TMP tut nichts anderes, als aus einer Template-Parametrisierung zur Compilezeit! Code/Konstanten/Typen zu generieren. Anstatt ein Template zu nehmen, kann ich auch den Code für alle im Programm benutzen Template-Parameter (die ja zur Compilezeit bereits existieren müssen), von Hand eintippen.

Du verwechselst TMP mit normalen Templates. Normale Templates sind letztendlich so etwas wie eine typsichere Textersetzung. Der Trick bei der TMP ist aber, dass man den Compiler mittels der Regeln für partielle Spezialisierung dazu bringt, so viel mehr zu tun als nur Text zu ersetzen.

ipsec

TMP ist mehr als Textersetzung, nämlich wenn es um Rekursion geht. Beispiel:

template<int n>
struct sum
{
    int value = n + summe<n-1>::value;
};

template<>
struct summe<0>
{
    int value = 0;
}

Die Spezialisierung kann man schecht ausschreiben. Das müsste dann etwa so aussehen:

// summe<2>::value ausgeschrieben:
// Spezialisierung
2 == 0 ? 0 : 
// n +
2 +
// summe<3-1>::value
    // Spezialisierung
    2-1 == 0 ? 0 :
    // n +
    (2-1) +
    // summe<(2-1)-1>::value
        // Spezialisierung
        (2-1)-1 == 0 :
        // n +  // !!! Dieser Teil wird nie erreicht, muss aber beim Ausschreiben hingeschrieben werden !!!
        ((2-1)-1) +
        // summe<((2-1)-1)-1>::value
            // usw.

Lange Rede kurzer Sinn: Ausschreiben ermöglicht keinen Rekursionsabbruch. Zur Laufzeit würde es funktionieren, aber man wäre mit dem Schreiben unendlich lange beschäftigt.
Aus diesem Grund geht auch keine Rekursion mit Makros.
Reines Ausschreiben (was man ja mit Makros machen kann) ist somit nicht turingvollständig.

static_assert hat damit aber nichts zu tun, das basiert nicht auf der Turingvollständigkeit. Sämtliche Berechnungen mit Typen kann man nicht ausschreiben, weil Typen keine Ausdrücke sein können (außer in der TMP).

Tachyon

Ich habe doch gar nicht gesagt, das TMP nur Textersetzung macht. Ich habe gesagt, dass es Tiparbeit erspart.

Zum Beispiel Pointerprüfung:
Du schreibst einen Code, der im Fall T == Pointer ein Stück Code compiliert, und im Fall T != Pointer einen anderen. Das kann ich auch mit Überladung erreichen. Man muss bloß viel mehr Aufwand betreiben.

Was Du natürlich nicht machen kannst, ist, dass ein Template im Fall T == Pointer nicht kompiliert. Das ist aber ein Problem, dass überhaupt erst durch Templateprogrammierung entsteht.

Tachyon

ipsec schrieb:

Lange Rede kurzer Sinn: Ausschreiben ermöglicht keinen Rekursionsabbruch.

Die Notwendigkeit für einen automatisierten Rekursionsabbruch ergibt sich überhaupt erst aus der TMP.

hustbaer

Also Freunde.
Rekursion und ein bisschen Rechnen geht mit dem PP auch. Wenn auch leider nur sehr umständlich.

ipsec

... und mit beschränkter Rekursionstiefe. Also wie als würde ich in meinem Summebeispiel willkürlich irgendwann aufhören.

Naja die Diskussion ist auch etwas akademisch. Auf jeden Fall ist TMP etwas mehr als Codegenerierung auf Basis von stupider Textersetzung, man kann die Templates in der Regel zwar ausschreiben (summe<3>::value == 3+2+1+0), muss dazu aber selber etwas rechnen (z.B. "berechnen", wann der Rekursionsabbruch erreicht ist).

Michael E.

hustbaer schrieb:

ein bisschen Rechnen geht mit dem PP auch.

Wie?

Sowas wie boost::proto als Mittel der TMP ist doch schon sehr praktisch:
http://cpp-next.com/archive/2011/01/expressive-c-expression-optimization/

SeppJ

Michael E. schrieb:

hustbaer schrieb:

ein bisschen Rechnen geht mit dem PP auch.

Wie?

Das ist das was ich oben meinte mit "wenn man nicht hinter die Kulissen guckt".

Man kann z.B. so etwas machen:

#define result_3_4 7

#define add(a,b) result_ ## a ## _ ## b

add(3,4)   // ist 7 zur Compilezeit (sogar schon davor!)

Wenn das jetzt ein fleißiger Schreiberling für alle Zahlen bis 100 und für das kleine Einmaleins macht und das alles in einer Headerdatei versteckt, könnte man den Eindruck bekommen, dass man mit dem Präprozessor richtig rechnen kann.

HighLigerBiMBam

Ich sehs kommen, der nächste Trend beginnt: Präprozessor Meta Programming... Für die Geeks unter den Geeks denen TMP zu trivial ist.

Eisflamme

Für die Fakultät ist das sogar noch viel besser. Das toppt dann auch die Template-Lösung! Und es gibt keine Einschränkung in der Rekursionstiefe :p

SeppJ

HighLigerBiMBam schrieb:

Ich sehs kommen, der nächste Trend beginnt: Präprozessor Meta Programming... Für die Geeks unter den Geeks denen TMP zu trivial ist.

Alles schon gemacht. Sogar in einem produktivem Programm. Denn mit TMP kann man manche Dinge nicht (oder nurschlecht) machen die mit Präprozessor trivial sind, beispielsweise Zeichenketten zur Compilezeit erzeugen ist mit TMP die Hölle bis unmöglich.

Das Programm war dann am Ende natürlich so unwartbar und unleserlich, dass ich dann später doch alles auf eine Laufzeitlösung umgeschrieben habe (trotz boost::preprocessor welches schon viel zur Lesbarkeit beiträgt). Weil das resultierende Programm weitaus leserlicher war, war es dann auch ein leichtes zu optimieren und dadurch war das Endergebnis wesentlich (ca. 30%) schneller als das Metaprogrammierungsmonster.

In dieser Anekdote steckt bestimmt irgendeine Moral, aber ich finde sie nicht :p .

knivil

für jedes N wird eine Folge von Konstanten 2..N und das Produkt der Elemente gebildet. N ist kein Parameter der zur Laufzeit änderbar ist

Du sagst doch selbst: gebildet. Also ausgerechnet. Und natuerlich zur Compilezeit, da das Programm zur Compilezeit ausgewertet wird und nicht zur Laufzeit.

Ein TMP erzeugt Programmcode aus Templatecode zur Compilezeit, welcher dann ausgeführt werden kann. Das tun Makros auch.

Nein, Makros im Sinne von C sind da wesentlich eingeschraenkter. C++ Templates und Makros auf eine Stufe zu stellen ist falsch.

Guck Dir die Definition für "Metaprogrammierung" an. Zum Beispiel im Tanenbaum, oder meinetwegen auch bei Wikipedia.

Dito. Dir wird von vielen gesagt, dass du falsch liegst. Vielleicht haben sie ja recht. Auch haette ich gern noch gewusst, in welchem Buch von Tanenbaum etwas ueber Metaprogrammierung zu finden ist.

Ich habe doch gar nicht gesagt, das TMP nur Textersetzung macht. Ich habe gesagt, dass es Tiparbeit erspart.

Doch du hast TMP auf die Stufe von C-Makros gesetzt. Dein Hauptargument ist dabei die Tipparbeit, alles andere scheint nur eine untergeordnete Rolle zu spielen. Dabei gibt es soviel mehr Moeglichkeiten, dass Tipparbeit eher eine untergeordnete Rolle spielt.

Zu SeppJ:
Wieso war denn die Laufzeitlösung schneller? Was könnte denn – wenn man die Laufzeit betrachtet – effizienter sein, als alles schon zuvor berechnen zu lassen?

knivil

Generierter Code war eben suboptimal. Metaprogrammierung bedeutet nicht, das alles zur Compilezeit ausgerechnet wird.

pumuckl

Der Vergleich von Makros und TMP ist wie der Vergleich von Äpfeln und Birnen. Oder von Perl und C++.
Klar, beide ersparen Tipparbeit. Aber Tipparbeit spare ich auch, indem ich eine höhere Programmiersprache benutze und nicht alles in Assembler schreibe. Darüber hinaus sind beide aber so unterschiedlich wie Tag und Nacht. Es gibt Dinge, die man bei makros machen kann und in TMP nicht, es gibt Dinge die man in beidem machen kann, wobei je nach Problemstellung das eine oder das andere geeigneter ist. Beides in einen Topf zu werfen, nur weil beide Tipparbeit sparen ist aber ausgemachter Blödsinn.

hustbaer

knivil schrieb:

Nein, Makros im Sinne von C sind da wesentlich eingeschraenkter. C++ Templates und Makros auf eine Stufe zu stellen ist falsch.

Ich würde mal sagen das kommt drauf an wie viele Stufen man hat

knivil

Oder Treppen ...

SeppJ

Fast2_unreg schrieb:

Zu SeppJ:
Wieso war denn die Laufzeitlösung schneller? Was könnte denn – wenn man die Laufzeit betrachtet – effizienter sein, als alles schon zuvor berechnen zu lassen?

Vorher: Statische Polymorphie, zig automatisch generierte Funktionen.
Nachher: Schicke Laufzeitpolymorphie, wenige kleine, übersichtliche Funktionen.

Also anstatt generiertem Code der so aussah:

void do_something_foo(foo1);
void do_something_foo(foo2);
void do_something_foo(foo3);
void do_something_foo(foo4);

// ...

Foo1 foo1[count_of_foo1];
Foo1 foo2[count_of_foo2];
Foo1 foo3[count_of_foo3];
Foo1 foo4[count_of_foo4];

// ...

for (int i=0; i<count_of_foo1; ++i)
  do_something(foo1[i]);
for (int i=0; i<count_of_foo2; ++i)
  do_something(foo2[i]);
for (int i=0; i<count_of_foo3; ++i)
  do_something(foo3[i]);
for (int i=0; i<count_of_foo4; ++i)
  do_something(foo4[i]);

hatte ich hinterher etwas wie

void do_something(foo*); // Eigentlich mit Referenzen, aber ich will die Laufzeitpolymorphie hervorheben

// ...

Foo *foo[count_of_foos];

// ...

for (int i=0; i<count_of_foos; ++i)
  do_something(foo[i]);

Das ist schon einmal wesentlich weniger Overhead durch die Schleifen, dadurch natürlich mehr Overhead durch Polymorphie. Bei mir war das aber wesentlich günstiger zugunsten der Polymorphie.

Außerdem konnte der Compiler den handgeschriebenen Code wesentlich besser inlinen. Vermutlich, weil eben nur eine Funktion an genau einer Stelle eingefügt werden musste, anstatt vier leicht verschiedene Funktionen an vier Stellen die das Ergebnis sehr aufgebläht hätten. Weil mein Code aus vielen kleinen spezialisierten Funktionen bestand (wie man es ja bei gutem Stil macht ) haute auch das ganz gewaltig rein.

Ja, ich war ehrlich gesagt auch etwas überrascht. Die Regel, dass sauberer Code schnellerer Code ist, stimmt wirklich.