Hlavní navigace

Úvod do jazyka Reason: tail rekurze

20. 2. 2018
Doba čtení: 6 minut

Sdílet

Dnes se opět budeme zabývat rekurzí. Řeč bude o psaní rekurzivních funkcí, jenž potřebují pouze konstantní prostor na zásobníku volání. Vyhneme se tak jeho přeplnění při práci s rozsáhlými strukturami.

Tail cally

Minule jsme si ukázali datovou strukturu seznam a jak pomocí rekurze napsat některé funkce. Například  sum:

let rec sum = (nums) =>
  switch nums {
    | [] => 0
    | [n, ...ns] => n + sum(ns);
  };

Existuje však i jiný způsob, jak tuto funkci zapsat:

let sum' = (nums) => {
  let rec sum' = (nums, s) =>
    switch nums {
      | [] => s
      | [n, ...ns] => sum'(ns, s + n)
    };
  sum'(nums, 0);
}

Rozdíl mezi oběma funkcemi se projeví na dlouhých seznamech:

/* Seznam obsahujici 17 milionu jednicek. */
let longList =
  Array.make(17000000, 1)
  |> Array.to_list;

Volání

Js.log(sum'(longList));

jak by se dalo očekávat, uspěje a vypíše 17000000. Nicméně následující volání

Js.log(sum(longList));

pravděpodobně neuspěje a v závislosti na webovém prohlížeči vypíše chybové hlášení. Google Chrome vypíše

Uncaught RangeError: Maximum call stack size exceeded 

Problém spočívá v tom, že prohlížeč pro každé neukončené volání funkce ukládá data na zásobníku volání (angl. call stack), jenže kapacita zásobníku volání je omezena, tudíž při velikém počtu neukončených volání (hluboké rekurzi) dojde místo na zásobníku volání a je vyhozena výše uvedená výjimka.

S funkcí sum' problém není, neboť rekurze je při kompilaci do JavaScriptu nahrazena while cyklem. Pokud funkce volá sama sebe z tail pozice, dokáže BuckleScript nahradit rekurzi cyklem. Volání z tail pozice neboli tail call (česky koncové volání) znamená, že volání je to poslední, co se ve funkci děje.

Například ve funkci sum' se po volání sum'(ns, s + n) nic dalšího neděje. Zatímco ve funkci sum se po volání sum(ns) ještě volá funkce +, takže se nejedná o tail call. Pokud jsou všechna rekurzivní volání v tail pozici, řekneme, že funkce je tail-rekurzivní. Tedy funkce sum' je tail-rekurzivní a sum nikoliv.

Dalším příkladem tail-rekurzivní funkce je funkce exists:

let rec exists = (pred, list) =>
  switch list {
  | [] => false
  | [x, ...xs] => pred(x) || exists(pred, xs)
  };

Na první pohled se sice může zdát, že volání exists(pred, xs) není to poslední, co se ve funkci děje, nicméně zdání klame. Vtip je ve speciálním vyhodnocování ||, jenž se vyhodnocuje jako

if (pred(x))
  true
else
  exists(pred, xs)

Po přepisu je již patrné, že po rekurzivním volání se nic dalšího neděje. && se chová podobně.

Standardní knihovna a modul List

Ve standardní knihovně Reasonu je modul List, který obsahuje pár užitečných funkcí pro práci se seznamy. Bohužel řada z těchto funkcí není tail-rekurzivních a nefunguje pro dlouhé seznamy. Například

List.map((x) => x + 1, longList);

skončí chybou kvůli nedostatku místa na zásobníku. Dokumentace modulu List uvádí, které funkce nejsou tail-rekurzivní.

Místo List.map lze použít List.rev a List.rev_map, které jsou tail-rekurzivní:

List.rev(List.rev_map((x) => x + 1, longList));

Tail call optimization

Při vzájemné rekurzi více funkcí nedokáže BuckleScript nahradit rekurzivní volání cyklem. Příkladem jsou funkce even a odd z minula

let rec even = (x) => x == 0 || odd (x - 1)
and odd = (x) => x != 0 && even (x - 1);

even(17000000);

které se přeloží na následující JavaScript:

'use strict';

function even(x) {
  if (x) {
    return odd(x - 1 | 0);
  } else {
    return /* true */1;
  }
}

function odd(x) {
  if (x !== 0) {
    return even(x - 1 | 0);
  } else {
    return /* false */0;
  }
}

even(17000000);

Spuštění uvedeného JavaScriptu v Chrome opět vyvolá chybu. Nicméně, když uvedený JavaScript spustíme v Safari, vše zafunguje bez problémů. Jak to? Důvodem je optimalizace tail callů, jenž je součástí standardu ECMAScript 2015 a kterou implementuje bohužel pouze Safari.

Podstatou této optimalizace je fakt, že pokud z aktuální funkce provádíme tail call, tak data na zásobníku pro aktuální funkci už nebudou potřeba, tato data tedy můžeme nahradit daty volané funkce. Volaná funkce se pak stane aktuální funkcí a při provádění tail callu opět záznam na zásobníku pro aktuální funkci nahradíme záznamem volané funkce. Důsledkem je, že si vystačíme s konstantním prostorem na zásobníku bez ohledu na hloubku rekurze. Nevýhodou je, že zásobník volání neobsahuje všechna volání, což snižuje jeho užitečnost při ladění programu.

Stromové struktury

Kromě seznamů existuje řada dalších velmi užitečných rekurzivních datových typů. Příkladem je typ pro reprezentaci JSONu:

type json =
  | Assoc(list((string, json)))
  | Bool(bool)
  | Float(float)
  | Floatlit(string)
  | Int(int)
  | Intlit(string)
  | List(list(json))
  | Null
  | String(string);

Nebo typ, který reprezentuje výrazy v jednoduchém programovacím jazyce:

type expr =
  | Int(expr)
  | Plus(expr, expr)
  | If(expr, expr, expr);

Zde je příklad výrazu:

let expr = If(Plus(Int(-2), Int(2)), Int(4), Int(5));

Při práci s hodnotami rekurzivních typů často používáme rekurzi a pattern matching. Například můžeme napsat funkci, jež výrazy vyhodnotí:

let rec eval = (e) =>
  switch e {
  | Int(i) => i
  | Plus(a, b) => eval(a) + eval(b)
  | If(cond, yes, no) =>
    if (eval(cond) == 0) {
      eval(no)
    } else {
      eval(yes)
    }
  };

Tato funkce ovšem není tail-rekurzivní. Lze to napravit?

Continuation passing style

Odpověd je ano, libovolnou funkci můžeme mechanicky převést na tail-rekurzivní pomocí techniky zvané continuation passing style (CPS). Naší funkci se přidá jeden parametr k (od slova kontinuace; ač je anglický výraz continuation používá se k, nikoliv c). k je funkce, která se má spustit po naší funkci a zpracovat její výsledek.

Zkusme to pro eval (kód se nepřeloží):

let rec eval = (e, k) =>
  switch e {
  | Int(i) => k(i)
  | Plus(a, b) => eval(a) + eval(b)
  | If(cond, yes, no) =>
    if (eval(cond) == 0) {
      eval(no)
    } else {
      eval(yes)
    }
  };

Aby funkce byla tail-rekurzivní, potřebujeme, aby každý eval byl v tail pozici:

let rec eval = (e, k) =>
  switch e {
  | Int(i) => k(i)
  | Plus(a, b) => eval(a, k)
  | If(cond, yes, no) =>
    eval(cond, k)
  };

Výše uvedený kód je špatně. Po vyhodnocení a potřebujeme ještě vyhodnotit b a obě čísla sečíst. A po vyhodnocení cond musíme zjistit, zda vyšla nula, a podle toho vyhodnotit no nebo yes. Jinak řečeno po obou eval ech potřebujeme vykonat další kód. Jak to uděláme? Využijeme kontinuaci! Víme, že ta se vykoná po celém eval u a dostane jeho výsledek. Tedy potřebujeme-li po vyhodnocení a vyhodnotit i b, stačí jednoduše psát eval(a, (x) => eval(b, k)). A potřebujeme-li pak obě čísla sečíst, stačí psát  eval(a, (x) => eval(b, (y) => k(x + y))).

S cond  je to podobné, kód, který chceme vykonat po vyhodnocení cond, vrazíme do kontinuace, jenž předáváme  eval:

let rec eval = (e, k) =>
  switch e {
  | Int(i) => k(i)
  | Plus(a, b) => eval(a, (x) => eval(b, (y) => k(x + y)))
  | If(cond, yes, no) =>
    eval(cond, (x) => x == 0 ? eval(no, k) : eval(yes, k))
  };

Vyhodnocení provedeme následovně:

eval(expr, (x) => x);

Nevýhodou CPS je, že momentálně funguje pouze v Safari nebo při kompilaci do nativního kódu. Kromě CPS existují techniky, jenž mechanicky umožňují odstranit hlubokou rekurzi úplně. Tyto se používají zejména ve funkcionálních jazycích nad JVM, neboť JVM nepodporuje TCO na rozdíl od .NETu. Bohužel tyto další techniky jsou složitější než CPS a mají horší dopad na výkon programu než CPS.

Rovnost a další generované funkce

Testování rovnosti v Reasonu pomocí == není obecně tail-rekurzivní. Podobně tomu je i v dalších jazycích jako F# (u záznamů a variant), Scala (u case class), Kotlin (u data class) nebo Haskell (rovnost vygenerovaná pomocí deriving). Některé jazyky navíc dovedou pro daný typ generovat další funkce, například funkce pro převedení hodnot na řetězec nebo porovnávací funkce, bohužel se opět nejedná o tail-rekurzivní funkce, tudíž při práci s většími strukturami bude docházet k výjimkám kvůli nedostatečné velikosti zásobníku.

CS24 tip temata

Příště moduly v Reasonu

Bohužel, psát kód, který se chová šetrně k zásobníku volání, není v Reasonu úplně snadné. Hlavním problémem je nešťastně napsaná standardní knihovna. Dále pak prohlížeče neimplementující TCO.

Dobrou zprávou je, že jsme probrali základy funkcionálního programování a můžeme se zabývat něčím pokročilejším. Příště to budou moduly v Reasonu.

Autor článku

Zajímá se o programovací jazyky a typové systémy. Téměř deset let svého života zasvětil zkoušení různých programovacích jazyků, aby našel ten nejlepší.