Tail rekurze v erlangu

14.4.2007 10:06 | Přečteno: 1278× | erlang |

Ve funkcionálních jazycích se spousta (většina?) algorimů zapisuje jako rekurze. Nejinak je tomu i u erlangu. Jenže rekurze je pro normální dnešní CPU fuj a tak se to řeší (a nejen ve funkcionálních jazycích) tzv. tail rekurzí. Prakticky jde o nahrazení rekurze cyklem a nealokuje se kvůli tomu další paměť na zásobníku, ale různé jazyky se s tím umí vyrovnat různě.

Například výpočet faktoriálu:

-module(fact).
-export([fact/1, fact2/1]).

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

fact2(0) -> 1;
fact2(N) when N>0 -> fact2(N-1, N).

fact2(0, Res) -> Res;
fact2(N, Res) -> fact2(N-1, N*Res).

Varianta fact bohužel v erlangu skončí skutečnou rekurzí, kdežto fact2 udělá cyklus kolem fact2/2 kódu. Například Haskel se tuším vypořádá dokonce i s ekvivalentem zápisu fact. Pokud si to chcete vyzkoušet, tak si zkuste vypočítat fact2(50000) a pak fact(50000). To druhé začne velmi záhy swapovat a následně to shodí BEAN pod nímž to spustíte (pokud máte opravdu hodně swapu a paměti, tak si zvolte ještě větší číslo )

       

Komentáře

[Messa]

Tohle umí gcc -O2 taky. (Možná pro někoho samozřejmost, ale mě to překvapilo.)

[Hynek (Pichi) Vychodil]

Na úrovni haskelu nebo erlangu? Předpokládám, že spíš to druhé, ne?

[Messa]

Konkrétně u tohoto příkladu na úrovni Haskelu.

int fact (int n) {
	if (n == 0) return 1;
	return n * fact (n-1); }

a v assembleru je vidět krásná smyčka, žádný call.

Snad nikoho neurážím, že vám sem do funkcionálního programování tahám C

[Hynek (Pichi) Vychodil]

Snad nikoho neurážím, že vám sem do funkcionálního programování tahám C

Nene, dík za informaci. To se hodí vědět.

[Tom.š Ze.le.in]

Otázka je, jak toho dosahuje. Zkusil jsem rekurzi mezi dvěma funkcemi, a zdá se, že nedělá tail call vždy:

int foo (int a, int b);
int bar (int c, int a, int b)
{
        return (0==b) ? a : foo(a, --b);
}

int foo (int a, int b)
{
        return bar(1, a, b);
}

gcc -S -O2 --omit-frame-pointer test.c

foo:
        subl    $12, %esp
        movl    20(%esp), %eax
        movl    $1, 8(%esp)
        movl    %eax, 4(%esp)
        movl    16(%esp), %eax
        movl    %eax, (%esp)
        call    bar
        addl    $12, %esp
        ret

bar:
        movl    8(%esp), %eax
        movl    4(%esp), %edx
        testl   %eax, %eax
        jne     .L8
        movl    %edx, %eax
        ret
.L8:
        subl    $1, %eax
        movl    %eax, 8(%esp)
        jmp     foo

Jinými slovy, je to hezká optimalizace, ale plně bych se na ní při rekurzivním psaní programu nespoléhal (ostatně, norma C nic takového nepožaduje).

[deda.jabko]

v jake verzi to je? v gcc 3.4.6 to nejde ani s -O2 ani s -O3... porad pouziva call...

[Tom.š Ze.le.in]

Mně to funguje v 4.1.1, ale podle changelogu to bylo už v 3.0.1.

[Kyosuke]

Chm, chmm, ten patch poslal už v květnu 2000 Jan Hubička a objevilo se to už v tom úchylném „GCC 2.96“.