Proper Tail Calls (PTC) v JavaScriptu

Výraz "Proper Tail Call" jsem slyšel už několikrát a vždy mi to připadalo jako kouzlo. A i když jsem už přečetl pár článků, nikdy jsem to pořádně nepochopil... až do dneška. 🎉

Sledoval jsem přednášku "Základy funkčního programování v ES6" od Jeremyho Fairbanka a později jsem si přečetl článek "Vše o rekurzi, PTC, TCO a STC v JavaScriptu" od Lucase F. Costy a konečně jsem to pochopil.

Předpokládejme, že máte tento skript:

function factorial(n) {
    console.trace();
    if (n === 0) {
        return 1;
    }
    
    // no proper tail call
    return n * factorial(n - 1);
}

factorial(2);

Při spuštění pomocí v Node.js vypíše následující:

Trace
    at factorial (/private/tmp/ptc.js:4:13)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...
Trace
    at factorial (/private/tmp/ptc.js:4:13)
    at factorial (/private/tmp/ptc.js:9:16)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...
Trace
    at factorial (/private/tmp/ptc.js:4:13)
    at factorial (/private/tmp/ptc.js:9:16)
    at factorial (/private/tmp/ptc.js:9:16)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...

Vidíte, že zásobník volání se zvětšuje a zvětšuje kvůli rekurzivní povaze factorial . To může vést ke slavnému RangeError: Maximum call stack size exceeded chyba, když jej spustíte s opravdu vysokým číslem (zkoušel jsem to s 100000 a to selhalo).

Pokud nyní optimalizujete funkci ve skriptu, aby prováděla správná koncová volání, můžete tento problém obejít.

'use strict';

function factorial(n, total = 1) {
    console.trace();
    if (n === 0) {
        return total;
    }

    // proper tail call
    return factorial(n - 1, n * total);
}

factorial(2);

Nyní výstup vypadá následovně.

Trace
    at factorial (/private/tmp/ptc.js:13:13)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...
Trace
    at factorial (/private/tmp/ptc.js:13:13)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...
Trace
    at factorial (/private/tmp/ptc.js:13:13)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...

Vidíte – velikost zásobníku hovorů se nezvětšila. 🎉 To znamená, že tímto způsobem nenarazíte na Maximum call stack size exceeded chyba. Skvělé věci!

Existují však určitá omezení. Lucas je popisuje ve svém článku následovně:

Teď bych mohl jít do detailů tohoto tématu a popsat, co dělá správný nářez, ale Lucas a Jeremy to už udělali mnohem lépe, než jsem uměl já. Takže v případě, že je to pro vás také novinka, vřele doporučuji podívat se na přednášku a článek.

Poznámka:v době psaní článku jsou správná koncová volání podporována pouze prohlížeči Safari a Webkit.