[erlang] : Warum ist tail recursion so viel effizienter als normale Rekursion was den Speicherverbrauch angeht?
-
nman schrieb:
Hm? Common-Lisp-Compiler müssen IIRC Tail Calls laut Standard auch nicht optimieren und trotzdem tut das praktisch jeder Compiler und Commmon-Lisper verwenden es sehr oft und gerne.
Ist ja auch ein grundvernünftiges Feature. Trotzdem müssen sie unter Umständen dazusagen, dass sie sich darauf verlassen haben; und im schlimmsten Fall müsste man den Code dann umschreiben, um ihn mit einer anderen Sprach-Implementation zu verwenden, obwohl sie standardkonform ist.
Da fragt man sich, warum das eigentlich nicht wie in Scheme oder Lua oder ... vorgeschrieben ist. Scheinbar sind proper tail calls erst so richtig in Mode gekommen, nachdem der letzte CL-Standard verabschiedet wurde.
-
mngbd schrieb:
Was mir viel mehr auf die Nerven geht, ist dass man sowas einfach in den C-Standard schreiben könnte. Sonst will es doch kaum jemand verwenden. Aber dann wäre ja der heilige Compiler ein wenig aufwendiger.
C++ Compiler sind schon aufwendig genug, und da willst du noch sowas verlagnen?
Klar könnte man es in den Standard schreiben, wie viele andere Dinge auch. Nur was nützt es? Auch ohne zusätzliche Auflagen im Standard gibt es keinen einzigen standard-konformen C++ Compiler. Soll heissen: es würde dir garnix bringen, da es einfach nicht jeder C++ Compiler implementieren würde. Auch wenn es im Standard steht.
-
hustbaer schrieb:
C++ Compiler sind schon aufwendig genug, und da willst du noch sowas verlagnen?
Weil es die Stärke der Sprache erhöht, ohne irgendeine Änderung an der Syntax und der Semantik. Aber ich hab da eher an C gedacht.
AIM 353 ist zu dem Thema vielleicht auch lesenswert.
-
mngbd schrieb:
Aber ich hab da eher an C gedacht.
Es ist halt einfach nicht so schick in C. In C schreibt man die Enrekursion halt gleich als Iteration. Wie sich das entwickelt hätte wenn man solche Optimierungen von Anfang an drin gehabt hätte mag ich nicht beurteilen, aber heute ist da der Zug schon mehrfach abgefahren.
-
Tim schrieb:
mngbd schrieb:
erkurz schrieb:
Hmm okay, das Umdenken ist dann bisschen doof für mich.
Aber wohl auch nur, weil die meisten C(++)-Compiler solche naheliegenden Optimierungen nicht machen.
Huch? Ist das so? Der gcc hat bei mir iirc immer tail-recursions wegoptimiert. Nicht dass ich ihn extra daraufhin getestet hätte.
Wobei der GCC da wohl ein Experte ist. Andere Compiler (icc, suncc, msvc) machen das wohl nicht: http://dl.fefe.de/optimizer-isec.pdf (s.32)
-
rüdiger schrieb:
Tim schrieb:
mngbd schrieb:
erkurz schrieb:
Hmm okay, das Umdenken ist dann bisschen doof für mich.
Aber wohl auch nur, weil die meisten C(++)-Compiler solche naheliegenden Optimierungen nicht machen.
Huch? Ist das so? Der gcc hat bei mir iirc immer tail-recursions wegoptimiert. Nicht dass ich ihn extra daraufhin getestet hätte.
Wobei der GCC da wohl ein Experte ist. Andere Compiler (icc, suncc, msvc) machen das wohl nicht: http://dl.fefe.de/optimizer-isec.pdf (s.32)
mein VC macht das seit version 6 (anno 1999).
Es gibt aber bei jedem compiler bedingungen unter welchen er das macht, genau wie mit (N)RVO.
Wenn man sichergehen will dass das gemacht wird, bleibt nichts anderes als ins disassembly zu schauen.
-
rüdiger schrieb:
Tim schrieb:
mngbd schrieb:
erkurz schrieb:
Hmm okay, das Umdenken ist dann bisschen doof für mich.
Aber wohl auch nur, weil die meisten C(++)-Compiler solche naheliegenden Optimierungen nicht machen.
Huch? Ist das so? Der gcc hat bei mir iirc immer tail-recursions wegoptimiert. Nicht dass ich ihn extra daraufhin getestet hätte.
Wobei der GCC da wohl ein Experte ist. Andere Compiler (icc, suncc, msvc) machen das wohl nicht: http://dl.fefe.de/optimizer-isec.pdf (s.32)
Ist das überhaupt richtig tail-recursive?
-
Tim schrieb:
Ist das überhaupt richtig tail-recursive?
Hmm, ich weiss auch nicht, was er mit der Folie sagen will. Die Fakultaetsfunktion ist nicht Endrekursiv (tail recursiv).
-
Da kam der CCC in ihm durch und musste freie Software lobhudeln
-
Als Laie würde ich mal sagen, da steckt entweder ziemlich viel Magie in der gcc-Opti, oder sie haben eine spezielle Transformation für genau dieses Muster.
-
rapso schrieb:
Wenn man sichergehen will dass das gemacht wird, bleibt nichts anderes als ins disassembly zu schauen.
Zumindest die glibc kann das bis zur Laufzeit transparent halten:
http://www.gnu.org/s/libc/manual/html_node/Backtraces.htmlBashar schrieb:
Als Laie würde ich mal sagen, da steckt entweder ziemlich viel Magie in der gcc-Opti, oder sie haben eine spezielle Transformation für genau dieses Muster.
Zumindest das Muster "Rekursion modulo primitive Operation, die keinen neuen Speicher anfordert" müsste man eigentlich immer in einen tail call + Akkumulator verwandeln können, oder?
-
µngbd schrieb:
Zumindest das Muster "Rekursion modulo primitive Operation, die keinen neuen Speicher anfordert" müsste man eigentlich immer in einen tail call + Akkumulator verwandeln können, oder?
Bin auch Laie, aber das geht scheinbar wirklich so einfach. Unter den Einschränkungen, dass der Körper aus einem einzelnen if besteht, dass der Rekursionsabbruch im then-Teil ist, und dass nur das erste Argument bei der Rekursion verändert wird, geht das in Scheme zB so:
(define (rec->tail fun-def) (let ((name (caadr fun-def)) (first-arg (cadadr fun-def)) (rest-args (cddadr fun-def)) (if-expr (caddr fun-def))) (let ((test (cadr if-expr)) (then-part (caddr if-expr)) (else-part (cadddr if-expr))) (let ((operation (car else-part)) (first-operand (cadr else-part)) (new-arg (car (cdaddr else-part)))) `(define ,(cons name (cons first-arg rest-args)) (define (tail-rec ,first-arg acc) (if ,test acc (tail-rec ,new-arg (,operation ,first-operand acc)))) (tail-rec ,first-arg ,then-part))))))Das geht natürlich mit der Fakultät:
> (rec->tail '(define (fact n) (if (zero? n) 1 (* n (fact (- n 1)))))) (define (fact n) (define (tail-rec n acc) (if (zero? n) acc (tail-rec (- n 1) (* n acc)))) (tail-rec n 1))Aber auch mit exotischeren Dingen, solange nur das erste Argument verändert wird:
> (rec->tail '(define (fold lst proc init) (if (null? lst) init (proc (car lst) (fold (cdr lst) proc init))))) (define (fold lst proc init) (define (tail-rec lst acc) (if (null? lst) acc (tail-rec (cdr lst) (proc (car lst) acc)))) (tail-rec lst init)) ;; die beiden fold-Versionen reagieren gleich, zB: (fold '(1 2 3 4) + 0) (fold '(1 2 3 4) cons '())Heureka.
-
Man kann jede Rekursion in eine Endrekursion mittels Continuation ueberfuehren. Manchmal geht es aber nicht immer mit einem einfachen Akkumulator, sondern man tauscht Stack gegen Heap.
-
knivil schrieb:
Man kann jede Rekursion in eine Endrekursion mittels Continuation ueberfuehren.
Ja, klar. Aber dazu muss man in jedem Durchlauf Closures erzeugen, was in manchen Sprachen nicht geht. Aber mein Muster geht immer.
-
mngbd schrieb:
Bin auch Laie ... Unter den Einschränkungen ... mein Muster geht immer
Diese Argumentationskette kann ich nicht ganz nachvollziehen.
Nein, ich habe mir dein Schema noch nicht angesehen. Vielleicht magst du es mal auf die Tuerme von Hanoi anwenden (aber nicht nur fuer 3 Scheiben, sondern fuer beliebig viele).
-
knivil schrieb:
mngbd schrieb:
Bin auch Laie ... Unter den Einschränkungen ... mein Muster geht immer
Diese Argumentationskette kann ich nicht ganz nachvollziehen.
Hehe, da hast du recht. Ich hab dieses Muster gemeint, aber in allen mir bekannten Sprachen, die anderen Einschränkungen sorgen nur dafür, dass es genau so aussieht, und nicht zB <test> negiert und then-Teil & else-Teil vertauscht sind:
(define (funktion x ...) (if <test> <letzter-wert-der-rekursion> (<operator> (funktion (<irgendwas> x) ...))))Das ist mir schon oft untergekommen. So könnte die magische tail recursion von Fefes gcc zustandekommen.
knivil schrieb:
Vielleicht magst du es mal auf die Tuerme von Hanoi anwenden (aber nicht nur fuer 3 Scheiben, sondern fuer beliebig viele).
Mal nachsehen, aber ich fürchte, das wird nichts.
