Template Metaprogrammierung
-
audacia schrieb:
Wenn ich mich nicht täusche, erfordern die letzten beiden Beispiele mehr oder weniger die Turing-Vollständigkeit der "Sprache" TMP.
Die Turing-Vollständigkeit von C++-Templates ist theoretisch gegeben. Was nicht gegeben ist, ist die genügende Unterstützung des Compilers. Beispielsweise steigen die meisten Compiler schon bei einer relativ geringen Rekursionstiefe (17 ist vom Standard empfohlen) von templates aus und schmeißen hin: http://www.netvor.sk/~umage/docs/C++ Templates are Turing Complete.pdf
Auf dem 2009er Foren-Treffen hatten wir "Joseph's Problem" zu lösen. Beim Versuch, das per TMP-Spielerei vom Compiler erledigen zu lassen hat der MSVC 2008 schon bei ziemlich kleinen Werten aufgegeben
-
Angeregt von einem anderen Thread in diesem Forum, kam mir die Idee, dass man elektrische Widerstandswerte aus Farbcodierungen berechnen könnte. Dann könnte man zur Compilezeit systematisch eine Liste aller möglichen Widerstände erstellen lassen. Fällt zwar auch ein bisschen unter "Wozu braucht man das?" ist aber immerhin eine spannendere Aufgabe als eine Fakultät zu berechnen und kann auch nicht zur Programmierzeit durch einen schnellen Griff zum Taschenrechner ersetzt werden.
Weiterhin kommen hier im Forum regelmäßig dumme Fragen nach Hausaufgaben, die dann oft mit Templatemetaprogrammen beantwortet werden. Oder Geschwindigkeitsoptimierungsfragen, wo Compilezeitlösungen auch immer ganz vorne mit dabei sind. Beispiele:
Optimiertes Zählen der Dezimalstellen einer Zahl. War jedoch letztendlich langsamer als die if-Kaskade.
Frage-Antwort Spiel bei dem alle möglichen Pfade zur Compilezeit ausgewertet werden.
-
Die größten TMP-Helden sind sowieso die Macher von Boost. Meine Favoriten: boost.proto und das damit implementierte boost.spirit
-
-Shelling- schrieb:
Da hast du Recht Nexus, auf solche Fragen habe ich mich innerlich auch schon vorbereitet. Allerdings habe ich maximal 20 Minuten Zeit und meine Zuhörerschaft besteht zu 100% aus Java Programmierern
Umso mehr solltest du darauf achten, ihre Vorurteile nicht zu bestätigen! Sie müssen nach dem Vortrag enttäuscht darüber sein, dass Java sowas nicht bietet :p
-
Erstmal Entschuldigung für meine lange Abwesenheit
Zweitens dann vielen vielen Dank für eure Anregungen und Ideen.Ich hab mir eure Ideen angeschaut und mich dazu entschlossen, auch etwas komplexere Sachen als Beispiele aufzunehmen. Den Rest werde ich wohl als weitere Wegweiser für die Zuhörer nutzen.
Nexus schrieb:
-Shelling- schrieb:
Da hast du Recht Nexus, auf solche Fragen habe ich mich innerlich auch schon vorbereitet. Allerdings habe ich maximal 20 Minuten Zeit und meine Zuhörerschaft besteht zu 100% aus Java Programmierern
Umso mehr solltest du darauf achten, ihre Vorurteile nicht zu bestätigen! Sie müssen nach dem Vortrag enttäuscht darüber sein, dass Java sowas nicht bietet :p
Ich halte die C++ Flagge schon recht häufig hoch, du glaubst gar nicht, wie oft mich die Java Generics stören
-
Boost.Spirit wollte ich auch gerade erwähnen.
Aber auch andere Boost Libraries machen nicht halt vor TMP, allen voran natürlich die Boost.MPL
Anwendungsbeispiele findet man z.B. in der Boost.Statechart oder auch in so "ordinären" Libraries/Klassen wie Boost.Variant (Stichwort Static Visitor).
-
drakon schrieb:
Denkanstösse sind schwierig. Man muss einfach mal eine Idee haben was man so machen könnte (und das ist sehr vieles; siehe dazu mal "Modern C++ Design" von Andrej Alexandrescu).
Man kann eigentlich noch recht viele Probleme (oder zumindest Teile davon) auf etwas mappen, dass zur Kompilierungszeit gemacht werden kann und dann kann man da üblicherweise auch etwas mit Metaprogrammierung erreichen.Mal eine kleine Idee, die mir während einer Zugfahrt gekommen ist:
http://www.drakon.ch/index.php?id=&offset=2&mobile=0&show_entry=94musste da die römischen Zeichen und Regeln mit dem Telefon nachschlagen..
Ist natürlich nur eine Spielerei, aber immerhin nicht das übliche Rekursive Gedöns und nicht so abgedreht wie Typlisten.
Der Trick ist doch das #define am Anfang. Zählen defines auch zu Metaprogrammierung?
-
hhhhmmmmm schrieb:
Der Trick ist doch das #define am Anfang. Zählen defines auch zu Metaprogrammierung?
Das #define erspart nur lästiges Tippen. Man könnte es genauso gut ausschreiben oder in eine Metafunktion packen. Die eigentliche Metaprogrammierung liegt ja woanders.
Und prinzipiel: #define und Metaprogrammierung können sich mitunter ganz gut ergänzen.
-
ipsec schrieb:
[...]Das #define erspart nur lästiges Tippen.[...]
Nichts anderes tut TMP letzten Endes auch. Und ja, Defines zählen zur Metaprogrammierung.
-
Tachyon schrieb:
ipsec schrieb:
[...]Das #define erspart nur lästiges Tippen.[...]
Nichts anderes tut TMP letzten Endes auch.
Nein. Das Templatemetaprogramm wird tatsächlich ausgeführt und etwas berechnet. Das kann man nicht durch Tipparbeit ersetzen, man braucht mindestens noch einen Taschenrechner und ein Gerät welches Entscheidungen treffen kann. Sprich: einen Computer.
Und ja, Defines zählen zur Metaprogrammierung.
Ja, ich würde sie trotzdem auch dazu zählen, weil sie in kleinem Umfang etwas erlauben, was der Metaprogrammierung sehr ähnlich ist (so lange man nicht hinter die Kulisse guckt).
-
SeppJ schrieb:
Nein. Das Templatemetaprogramm wird tatsächlich ausgeführt und etwas berechnet.[...]
Ein TMP erzeugt Programmcode aus Templatecode zur Compilezeit, welcher dann ausgeführt werden kann. Das tun Makros auch.
-
Anderswo schon mal verlinkt: http://vimeo.com/7211030 . Wenn ihr Macros aus Scheme oder Lisp sehen und verstehen wuerdet ... Naja, was soll's.
-
Tachyon schrieb:
SeppJ schrieb:
Nein. Das Templatemetaprogramm wird tatsächlich ausgeführt und etwas berechnet.[...]
Ein TMP erzeugt Programmcode aus Templatecode zur Compilezeit, welcher dann ausgeführt werden kann. Das tun Makros auch.
Nein! Das ist ein ganz großer Unterschied zwischen einer simplen Textersetzung und einer Turing-vollständigen Programmiersprache.
Erklär mir mal, wie du ein static assert durch mehr Tippen ausgleichen willst. Oder wie du das Berechnen von Zahlenfolgen zur Compilezeit durch Tippen ausgleichen willst (außer mit einem anderen Programm diese Zahlen zu Berechnen und dann abzutippen).
-
SeppJ schrieb:
Tachyon schrieb:
SeppJ schrieb:
Nein. Das Templatemetaprogramm wird tatsächlich ausgeführt und etwas berechnet.[...]
Ein TMP erzeugt Programmcode aus Templatecode zur Compilezeit, welcher dann ausgeführt werden kann. Das tun Makros auch.
Nein! Das ist ein ganz großer Unterschied zwischen einer simplen Textersetzung und einer Turing-vollständigen Programmiersprache.
Erklär mir mal, wie du ein static assert durch mehr Tippen ausgleichen willst. Oder wie du das Berechnen von Zahlenfolgen zur Compilezeit durch Tippen ausgleichen willst (außer mit einem anderen Programm diese Zahlen zu Berechnen und dann abzutippen).
Den Static-Assert kann ich z.B. durch tippen bekommen, indem ich an jeder Stelle an der geprüft werden soll ein Array hinbastel, dass im Fehlerfall die Größe -1 bekommt.
Berechnungen z.B. N! bekommt ich, indem ich den Code bis N von Hand eintippe. (N=5 -> 2 * 3 * 4 * 5 -> mehr Tipparbeit). Der TMP-Code für ! wird ja nicht zur Laufzeit ausgeführt, sondern es wird zur Compilezeit eine Konstante erzeugt.
-
Tachyon schrieb:
SeppJ schrieb:
Tachyon schrieb:
SeppJ schrieb:
Nein. Das Templatemetaprogramm wird tatsächlich ausgeführt und etwas berechnet.[...]
Ein TMP erzeugt Programmcode aus Templatecode zur Compilezeit, welcher dann ausgeführt werden kann. Das tun Makros auch.
Nein! Das ist ein ganz großer Unterschied zwischen einer simplen Textersetzung und einer Turing-vollständigen Programmiersprache.
Erklär mir mal, wie du ein static assert durch mehr Tippen ausgleichen willst. Oder wie du das Berechnen von Zahlenfolgen zur Compilezeit durch Tippen ausgleichen willst (außer mit einem anderen Programm diese Zahlen zu Berechnen und dann abzutippen).
Den Static-Assert kann ich z.B. durch tippen bekommen, indem ich an jeder Stelle an der geprüft werden soll ein Array hinbastel, dass im Fehlerfall die Größe -1 bekommt.
Berechnungen z.B. N! bekommt ich, indem ich den Code bis N von Hand eintippe. (N=5 -> 2 * 3 * 4 * 5 -> mehr Tipparbeit). Der TMP-Code für ! wird ja nicht zur Laufzeit ausgeführt, sondern es wird zur Compilezeit eine Konstante erzeugt.Das war gar nicht die Frage. Da C++ auch ohne TMP Turing-vollständig ist, kannst du alle Berechnungen von TMP-Programmen natürlich auch ohne TMP berechnen.
-
Michael E. schrieb:
Das war gar nicht die Frage. Da C++ auch ohne TMP Turing-vollständig ist, kannst du alle Berechnungen von TMP-Programmen natürlich auch ohne TMP berechnen.
Aber die Antwort.
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.
-
Dass man alles, was TMP berechnet, von Hand berechnen kann, ist klar, da wir Menschen auch "Turing-vollständig" sind.
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.)
-
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.
-
Michael E. schrieb:
Dass man alles, was TMP berechnet, von Hand berechnen kann, ist klar, da wir Menschen auch "Turing-vollständig" sind.
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.
-
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.
