Procesy

Zásobník volaní

Zásobník volaní (call stack) je štruktúra, ktorá je využívaná v implementácií každého súčasného programovacieho jazyka. Jedným z prejavov existencie zásobníka volaní je jeho výpis, ktorý vidíte pri vyhodení nezachytenej výnimky v jazyku Java — stack trace, napríklad

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
      at Main.sayHello(Main.java:8)
      at Main.main(Main.java:4)

V tomto výpise vidíme postupnosť volaných funkcií od tej, v ktorej nastala výnimka až k funkcii main, z ktorej sa začalo vykonávanie programu. Informácie, ktoré vidíme vo výpise, sú počas behu programu uložené v zásobníku volaní.

Zásobník volaní obsahuje aktivačné záznamy (stack frames) pre každe volanie funkcie alebo metódy. V momente volania funkcie je pre ňu vytvorený záznam a uložený na vrchu zásobníka. Keď sa vykonávanie funkcie ukončí, jej záznam sa zo zásobníka odstráni a vykonávanie sa vráti k volajúcej funkcii.

Súčasťou aktivačného záznamu sú hodnoty lokálnych premenných funkcie, jej parametrov a návratová adresu — pozícia v programe, ktorá nasleduje za volaním funkcie a na ktorej bude pokračovať vykonávanie po návrate do volajúcej funkcie.

Použitie zásobníka volaní je nevyhnutné ak programovací jazyk má podporovať rekurzívne volania funkcií. Každé volanie funkcie totiž môže mať odlišné hodnoty parametrov a premenných a ďalšie volanie funkcie nesmie prepísať premenné predchádzajúceho volania, ktoré ešte nebolo ukončené. Napríklad prvé verzie jazyka Fortran nepodporovali rekurziu, keďže nepoužívali zásobník volaní a namiesto toho alokovali priestor pre lokálne premenné staticky.

Použitie zásobníka je zároveň dôvodom, prečo je rekurzívna implementácia algoritmu zvyčajne menej efektívna ako iteratívna. Každé rekurzívne volanie totiž vyžaduje vytvorenia ďalšieho aktivačného záznamu. Pritom je možné prekročiť maximálnu veľkosť zásobníka čo spôsobí chybu stack overflow. Tento problém je obzvlášť podstatný pri funkcionálnych programovacích jazykoch, ktoré využívajú rekurziu namiesto iterácie.

Optimalizácia koncových volaní

Riešením problému nižšej efektivity rekurzie je použítie optimalizácia koncových volaní (tail call optimization). Ide o to, že pri niektorých volaniach funkcií je možné nevytvárať nový aktivačný záznam, ale prepísať záznam volajúcej funkcie. Možné je to vtedy, ak volajúca funkcia už za aktuálnym volaním nevykonáva žiadne operácie okrem návratu výsledku. Vtedy si môžeme byť istí, že lokálne premenné a parametre volajúcej funkcie už určite nebudú potrebné. Takéto volanie sa nazýva koncovým volaním (tail call). Napríklad volanie funkcie bar v príklade nižšie je koncovým volaním.

function foo(data) {
    // nejaké výpočty ...
    return bar(data);
}

Pri koncovom volaní teda prekladač môže nahradiť vytvorenie nového aktivačného záznamu prepísaním záznamu volajúcej funkcie. Návratová adresa zostane pôvodná a parametre a lokálne premenné sa využijú pre nové volanie. Vďaka takejto optimalizácii môže byť rekurzia rovnako efektívna ako iterácia, čo bolo ukázané v článku známom ako Lambda: The Ultimate GOTO.

Optimalizácia koncových volaní alebo koncovej rekurzie je štandardne implementovaná vo väčšine funkcionálnych programovacích jazykov. Mnohé prekladače jazyka C tiež dokážu vykonať takúto optimalizáciu. Mnohé bežné jazyky ako Java, C#, Python ju však nepodporujú.

Uveďme si príklad využitia optimalizácie koncových volaní z knihy Structure and Interpretation of Computer Programs. Ide o rekurzívnu implementáciu výpočtu faktoriálu v jazyku Scheme. Jednoduchá definícia funkcie factorial vyzerá takto (Scheme ako dialekt LISPu používa prefixný zápis operátrov):

(define (factorial n)
  (if (= n 1) 
      1 
      (* n (factorial (- n 1)))))

V tomto prípade však rekurzívne volanie funkcie factorial nie je koncovým, lebo za ním nasleduje ešte vynásobenie výsledku hodnotou n. Riešením je definícia pomocnej funkcie iter, ktorá očakáva medzivýsledok výpočtu ako parameter.

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

Introspekcia zásobníka volaní v Jave

Vráťme sa však k reflexii. Bolo by logické, aby nám reflexia umožňovala počas behu programu zistiť obsah zásobníka volaní. V prvých verziách jazyka Java však táto možnosť priamo implementovaná nebola, preto bolo potrebné využiť trik.

Ako som už spomínal, informácie zo zásobníka volaní sú vypisované pri vyhodení výnimky. To znamená, že objekt výnimky k nim musí mať prístup. Skutočne dokumentácia triedy Throwable, od ktorej dedia všetky výnimky uvádza

„A throwable contains a snapshot of the execution stack of its thread at the time it was created.“

To znamená, že stačí vytvoriť inštanciu triedy Throwable, použiť jej metódu printStackTrace(), zachytiť jej výstup a z neho vytiahnuť potrebné informácie. Neskôr, v Jave 1.4 sa pridala aj špeciálna metóda getStackTrace(), ktorá vracia pole objektov StackTraceElement, z ktorých je možné získať základné informácie o metódach, záznamy ktorých sú uložené v zásobníku volaní.

Uveďme príklad z knihy Java Reflection in Action. Majme rozhranie loggera s funkciou na zaznamenanie udalosti:

public interface Logger {
    void logRecord(String className,
                   String methodName,
                   int lineNum,
                   String message,
                   int logRecordType);
    ...
}

Použitie takéhoto loggera by bolo veľmi nepraktické, keďže pri každom volaní logRecord by sme museli ručne zadať názov triedy a metódy a tiež číslo riadku. Tieto informácie sa však pri zmenách kódu budú meniť. Hlavne číslo riadku veľmi rýchlo nebude zodpovedať aktuálnemu stavu. Oveľa lepšie by bolo takéto rozhranie:

public interface Logger {
    void logRecord(String message,
                   int logRecordType);
    ...
}

Realizácia tohto rozhrania môže využiť zásobník volania na zistenie informácií o volajúcej metóde.

public void logRecord(String message, int logRecordType) {
    Throwable ex = new Throwable();
    StackTraceElement ste = ex.getStackTrace()[1];
    String callerClassName = ste.getClassName();
    String callerMethodName = ste.getMethodName();
    int callerLineNum = ste.getLineNumber();
    ...

V Jave 9 sa doplnilo úplne nové API pre introspekciu zásobníka — StackWalker. Toto API už nie je nijak spojené s výnimkami a poskytuje nástroje filtrovania údajov, ktoré umožňujú zvyšiť efektivitu práce so zásobníkom. Viac informácií získate v článku Deep Dive into Java 9's Stack-Walking API.

Literatúra

• Java Reflection in Action. Chapter 5: Call stack introspection
• Arnaud Roger: Deep Dive into Java 9’s Stack-Walking API