[erlang] : Warum ist tail recursion so viel effizienter als normale Rekursion was den Speicherverbrauch angeht?

s.T.

normale Rekursion:

fac(0) -> 1;
2.fac(N) when N > 0 -> N*fac(N-1).

**
VS.**

teil recursion

tail_fac(N) -> tail_fac(N,1).
2. 
3.tail_fac(0,Acc) -> Acc;
4.tail_fac(N,Acc) when N > 0 -> tail_fac(N-1,N*Acc).

Warum ist letztere so viel effizienter was den Speicherverbrauch angeht?
Ich meine: wegen der Rekursion wird doch in beiden Fällen etwas zwischengespeichert?!?

erkurz schrieb:

s.T.

normale Rekursion:

fac(0) -> 1;
fac(N) when N > 0 -> N*fac(N-1).

**
VS.**

teil recursion

tail_fac(N) -> tail_fac(N,1).
 
tail_fac(0,Acc) -> Acc;
tail_fac(N,Acc) when N > 0 -> tail_fac(N-1,N*Acc).

EDIT: sry, beim Kopieren hab ich die Zeilennummern vergessen zu löschen

mngbd

erkurz schrieb:

Warum ist letztere so viel effizienter was den Speicherverbrauch angeht?
Ich meine: wegen der Rekursion wird doch in beiden Fällen etwas zwischengespeichert?!?

Nö, im zweiten Fall kann man ein goto an den Anfang der Funktion draus machen.

mngbd

Etwa so:

int tail_fact(int n, int acc)
{
anfang:
    if (n == 0)
        return acc;
    else
    {
        // und jetzt entweder ein tail call
        return tail_fact(n - 1, n * acc);
        // oder ein goto:
        acc = n * acc;
        n = n - 1;
        goto anfang;
    }
}

Editier, editier, ...: aber jetzt stimmts.

mngbd schrieb:

erkurz schrieb:

Warum ist letztere so viel effizienter was den Speicherverbrauch angeht?
Ich meine: wegen der Rekursion wird doch in beiden Fällen etwas zwischengespeichert?!?

Nö, im zweiten Fall kann man ein goto an den Anfang der Funktion draus machen.

Ja gut. was intern passiert sollte mich ja nicht interessieren, oder?
Ich kapier es nicht, da in beiden Fällen pro Stackframe ja das Ergebnis zwischengespeichert wird.

Bei "fac(N) when N > 0 -> Nfac(N-1)." für N = 4 wirds daraus ja:
"4*3*21" wobei jede zahl in je einem Stackframe steckt und solang zwischengespiechert wird, bis der base case nicht erreicht wurde.

Bei "tail_fac(N,Acc) when N > 0 -> tail_fac(N-1,N*Acc)." wird es doch auch zwischen gespeichert, hierbei sogar 2 werte: N und Acc.

Oder muss ich mich wirklich damit abfinden, dass der erlang interpreter bei tail recursion intern ein goto draus macht?

Mir fehlt hier irgendwie eine sinnvolle Begründung

mngbd

erkurz schrieb:

Oder muss ich mich wirklich damit abfinden, dass der erlang interpreter bei tail recursion intern ein goto draus macht?

Ja. Der macht das, weil er's kann. Damit fallen auch alle Stackframes bis auf den ersten weg. Und wahrscheinlich nicht nur bei tail recursions, sondern bei allen tail calls.

mngbd schrieb:

Etwa so:

int tail_fact(int n, int acc)
{
anfang:
    if (n == 0)
        return acc;
    else
    {
        // und jetzt entweder ein tail call
        return tail_fact(n - 1, n * acc);
        // oder ein goto:
        acc = n * acc;
        n = n - 1;
        goto anfang;
    }
}

Editier, editier, ...: aber jetzt stimmts.

Du hast doch in dem Beispiel im Kommentar selber geschrieben "oder ein goto". Klar, goto ist effizient, da iteriert man einfach drüber. Aber "return tail_fact(n - 1, n * acc);" bleibt doch dennoch ein rekursiver aufruf, zudem einer bei dem zwei sachen zwischengespeichert werden müssen: n & acc.

mngbd schrieb:

erkurz schrieb:

Oder muss ich mich wirklich damit abfinden, dass der erlang interpreter bei tail recursion intern ein goto draus macht?

Ja. Der macht das, weil er's kann. Damit fallen auch alle Stackframes bis auf den ersten weg. Und wahrscheinlich nicht nur bei tail recursions, sondern bei allen tail calls.

Hmm okay, das Umdenken ist dann bisschen doof für mich.

mngbd

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.

erkurz schrieb:

Aber "return tail_fact(n - 1, n * acc);" bleibt doch dennoch ein rekursiver aufruf, zudem einer bei dem zwei sachen zwischengespeichert werden müssen: n & acc.

Ja, klar. Aber vergleich das mal mit den 100 Stackframes, die du brauchst, um 100! mit der ersten Variante zu berechnen.

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.

mngbd

Tim schrieb:

Huch? Ist das so? Der gcc hat bei mir iirc immer tail-recursions wegoptimiert. Nicht dass ich ihn extra daraufhin getestet hätte.

Ich schätze, dass der das macht, wenn er das behauptet. Ich hab zwar dunkel in Erinnerung, dass er es auf irgendeiner Plattform behauptet, doch nicht gemacht hat, aber egal. 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.

nman

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.

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.

nman

Ach ja, zum Thema: Ich fand das Paper von Guy Steele zum Thema sehr erhellend:
Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO (Achtung, eingescanntes Uralt-Paper, aber sehr interessant und aufschlussreich.)

mngbd

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.

hustbaer

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.

mngbd

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.

rüdiger

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)

rapso

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?