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.
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.
ČLÁNKY DO MAILU