Tail rekurze v erlangu (diskuse)

[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“.