Projekt Mori aneb perzistentní datové struktury pro JavaScript

Obsah

1. Projekt Mori aneb perzistentní datové struktury pro JavaScript

2. Základní vlastnosti datových struktur v knihovně Mori

3. Neměnnost (immutability) datových struktur

4. Perzistence datových struktur

5. První demonstrační příklad: použití knihovny Mori na webové stránce

6. Seznamy a vektory

7. Druhý demonstrační příklad: použití seznamů a vektorů

8. Sekvence a lazy sekvence

9. Základní funkce pro práci se sekvencemi

10. Třetí demonstrační příklad: použití funkcí first a rest

11. Funkce range, take a map

12. Čtvrtý demonstrační příklad: použití funkcí range, take a map

13. Repositář se zdrojovými kódy všech dnešních demonstračních příkladů

14. Odkazy na Internetu

1. Projekt Mori aneb perzistentní datové struktury pro JavaScript

V několika posledních letech se vývojáři používající programovací jazyk JavaScript mohli setkat se dvěma zajímavými fenomény. Prvním fenoménem je postupné rozšiřování použití tohoto (nutno říci, že mnohdy neprávem podceňovaného) jazyka z webových browserů i do dalších aplikačních oblastí, zejména na servery a taktéž, i když v poněkud menší míře, na desktopy. Využití JavaScriptu na serverech sice ve skutečnosti není žádný nový či přelomový objev, protože podobnou funkci již kdysi dávno (konkrétně od roku 1994) nabízel komerční webový server nazvaný Netscape Enterprise Server (jednalo se o technologii pojmenovanou Server-Side JavaScript aneb SSJS), ovšem teprve s rozvojem známého a populárního projektu Node.js je možné mluvit o masivní adaptaci JavaScriptu i na serverech.

Na desktopu se JavaScript používá například v desktopovém prostředí GNOME (Gjs) či ve Windows Store, zajímavé je ovšem i jeho využití například v textovém editoru Atom (který je vnitřně rozdělen na klientskou a serverovou část, zjednodušeně lze říci, že klientská část je kombinací JavaScriptu a browseru). Navíc se objevují i „šílenosti“ typu OS.js, které ukazují možnosti tohoto jazyka i vyspělost jeho interpretrů.

Druhým fenoménem, s nímž se již mohlo setkat poměrně velké množství vývojářů, je vznik mnoha rozmanitých transpřekladačů (transcompilers, source-to-source compilers), jejichž cílovým jazykem je právě JavaScript. Připomeňme si, že transpřekladače jsou nástroje sloužící pro překlad algoritmů zapsaných v nějakém zdrojovém programovacím jazyce do zvoleného cílového jazyka (ovšem nikoli do nativního kódu či do bajtkódu, protože to už je role běžných překladačů). V současnosti existuje již poměrně velké množství transpřekladačů do JavaScriptu, nejpopulárnější jsou pak transpřekladače pro jazyky CoffeeScript, ClojureScript, TypeScript, Dart a Haxe. Nesmíme ovšem zapomenout ani na jazyk Wisp, s nímž jsme se již na stránkách Roota potkali [1] [2].

A právě v souvislosti s CoffeeScriptem, ClojureScriptem a v neposlední řadě i Wispem se setkáme s potřebou použití perzistentních (neměnných) datových struktur. Jednou z knihoven, která perzistentní datové struktury programátorům používajícím (nejenom) JavaScript nabízí, je knihovna Mori.

2. Základní vlastnosti datových struktur v knihovně Mori

Interně je knihovna Mori naprogramována poměrně neobvyklým způsobem, protože všechny perzistentní datové struktury, které jsou v ní implementovány, ve skutečnosti pochází z ClojureScriptu, jehož starší verzi jsme si již na stránkách Rootu popsali (nastal již ovšem ten pravý čas si někdy představit i novou verzi tohoto jazyka). Knihovna Mori tedy umožňuje, aby i programátoři používající „pouhý“ JavaScript (či TypeScript popř. CoffeeScript) měli přístup k optimalizovaným algoritmům vyvinutých v rámci projektu ClojureScript, aniž by se přitom bylo nutné učit odlišný přístup k tvorbě programů, který je v Clojure a ClojureScriptu vyžadován. Nicméně se vraťme k již zmíněným perzistentním datovým strukturám, které jsou v knihovně Mori uživatelům dostupné. Jedná se o neměnné seznamy (list), vektory (vector), množiny (set), mapy (map) a taktéž fronty (queue):

Povšimněte si, že mapy a množiny mohou být implementovány dvěma odlišnými způsoby, v závislosti na tom, zda mají být jejich prvky setříděny či nikoli.

3. Neměnnost (immutability) datových struktur

Všech pět typů datových struktur (seznamů, vektorů, množin, map a front) má několik důležitých společných vlastností. Základní vlastností společnou všem pěti typům datových struktur je jejich neměnnost (immutability). To znamená, že již ve chvíli, kdy je některá datová struktura vytvořena, je po celou další dobu její existence v běžícím programu určen její obsah, tj. hodnoty všech prvků struktury. Na první pohled to sice možná může vypadat zvláštně, ale i s takto se chovajícími strukturami je možné v reálným programech pracovat a to dokonce velmi efektivním způsobem (navíc se i zjednodušuje testování aplikace). Ostatně i v samotném JavaScriptu jsou některé hodnoty a objekty neměnné. Pravděpodobně nejviditelnějším příkladem jsou řetězce a samozřejmě taktéž všechny hodnoty primitivního datového typu (číslo, pravdivostní hodnota, …).

4. Perzistence datových struktur

Kromě neměnnosti (immutability) je další společnou vlastností všech čtyř typů kolekcí jejich persistence. Většina standardních funkcí poskytovaných knihovnou Mori se totiž snaží o to, aby jednou vytvořené sekvence (dejme tomu pro jednoduchost seznam) mohly být znovupoužity i v případě, že je vytvořen nový seznam, který v sobě obsahuje i seznam starší. Ten stále existuje a mohou na něj existovat reference používané například i v jiných paralelně běžících workerech či ve vláknech (pokud interpret JavaScriptu podporuje tvorbu většího množství vláken).

Vzhledem k tomu, že se obsah starého seznamu nemůže změnit (seznam je neměnitelný), může například funkce conj (což je obdoba funkce cons známé již z LISPu) jednoduše k seznamu přidat nový první prvek (head) s tím, že tento prvek ukazuje na původní seznam – jinými slovy není nutné, alespoň v tomto případě, vytvářet kopii (ať již plytkou či hlubokou) původního seznamu, což přispívá k tomu, že mnohé operace nad kolekcemi jsou ve skutečnosti velmi rychlé, i když by se podle jejich popisu mohlo zdát, že jejich implementace vyžaduje provedení časově složitých operací. Je pouze důležité si zvolit správnou datovou strukturu, což se v praxi týká rozhodování mezi použitím seznamů, vektorů či front.

5. První demonstrační příklad: použití knihovny Mori na webové stránce

Všechny datové struktury poskytované knihovnou Mori jsou implementovány formou objektů, tj. nelze s nimi zacházet jako s polem atd. – veškeré manipulace se provádí přes k tomu určené funkce. Ovšem Mori umožňuje převádět „své“ datové struktury na struktury zpracovávané JavaScriptem, což může být velmi užitečné ve chvíli, kdy se tato knihovna začíná používat v již rozpracovaném projektu. V dnešním prvním demonstračním příkladu je ukázáno, jak se vytvoří perzistentní seznam s využitím konstruktoru mori.list(), jak se následně zjistí počet prvků tohoto seznamu a taktéž způsob převodu perzistentního seznamu pomocí funkce mori.toJs() na běžné JavaScriptové pole:

// ------------------------------------------------------------
// Knihovna Mori: demonstrační příklad číslo 1
// ------------------------------------------------------------
 
// vytvoření perzistentního seznamu
var moriList = mori.list(1,2,3);
 
// výpočet délky perzistentního seznamu
var listSize = mori.count(moriList);
 
// převod perzistentního seznamu na "normální" JavaScriptové pole
var jsList = mori.toJs(moriList);
 
// výpis základních informaci o perzistentním seznamu i o jeho
// JavaScriptové variantě
console.log("List size: " + listSize);
console.log("List to JavaScript: " + jsList);
 
 
 
// ------------------------------------------------------------
// Výpis typu objektu moriList a jsList - první varianta
// ------------------------------------------------------------
console.log("Using typeof:");
// operátor typeof nám moc nepomůže v případě objektových typu
console.log("jsList type:   " + typeof jsList);
console.log("moriList type: " + typeof moriList);
 
 
 
// ------------------------------------------------------------
// Výpis typu objektu moriList a jsList - druha varianta
// ------------------------------------------------------------
console.log("Using Object.toString():");
// získáme referenci na toString a uložíme do proměnné toClass
var toClass = {}.toString
 
// Výpis informace o typech objektu
console.log("jsList type:   " + toClass.call(jsList));
console.log("moriList type: " + toClass.call(moriList));
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

Obrázek 1: Výpis na konzoli zachycený ve Firebugu.

Příklad je napsán takovým způsobem, aby ho bylo možné použít na webové stránce; konzolový výstup bude čitelný například přes Firebug ve Firefoxu popř. s využitím nástroje Inspect Page v prohlížeči Midori (ovšem i další webové prohlížeče používají podobné ladicí nástroje). Samotná webová stránka je pojata skutečně minimalisticky, protože vyžaduje pouze načtení dvou skriptů – samotné knihovny Mori a zdrojového kódu prvního demonstračního příkladu. Zdrojový kód mori.js získáte instalací knihovny příkazem npm install mori (soubor bude umístěn v adresáři ~/node_modules/mori), zdrojový kód uložený v souboru mori₀₁.js byl vypsán před tímto odstavcem:

<!doctype html>
<html>
    <head>
        <title>Mori tests #01</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_01.js"></script>
    </head>
    <body>
        <h1>Mori tests #01</h1>
    </body>
</html>

V ladicí konzoli webového prohlížeče by se po otevření výše uvedené testovací stránky měly objevit tyto řádky:

List size: 3
List to JavaScript: 1,2,3
Using typeof:
jsList type:   object
moriList type: object
Using Object.toString():
jsList type:   [object Array]
moriList type: [object Object]

Povšimněte si, že moriList je z pohledu JavaScriptu „nějakým“ obecným objektem, zatímco jsList je plnohodnotné JavaScriptové pole (jeho prvky ovšem již s původním seznamem nemusí sdílet stejný paměťový prostor!).

Obrázek 2: Výpis na konzoli zachycený v nástroji Inspect Page (Midori).

6. Seznamy a vektory

Způsob vytváření seznamů a vektorů s využitím konstruktorů mori.list již známe. Podobně se tvoří vektory konstruktorem mori.vector. Kromě toho knihovna Mori obsahuje i množství funkcí, které buď vrací stav dané datové struktury, vrací jeden vybraný prvek z této struktury, nebo vrací novou strukturu s přidaným či ubraným prvkem. Jedná se o následující funkce (povšimněte si, že zde není použit klasický OOP přístup, což je ale v tomto případě spíše výhoda; podrobnosti si řekneme později):

Poznámka: funkce mori.first() ve skutečnosti není omezena pouze na seznamy a vektory, protože ji je možné použít i na obecné sekvence a dokonce i na lazy sekvence popsané v dalších kapitolách.

Některé funkce z výše uvedené tabulky se chovají stejně pro seznamy i pro vektory, další funkce jsou však odlišné v chápání, který „konec“ datové struktury je modifikován, či z kterého „konce“ se mají vracet prvky:

Důležité je při optimalizaci aplikací i porovnání výpočetní složitosti některých funkcí z předchozí tabulky, protože právě odlišná složitost může výrazným způsobem ovlivnit výkonnost celé aplikace, zejména tehdy, pokud se budou používat kolekce s velkým množstvím prvků. Zajímavé je, že funkce count má v obou případech konstantní složitost: O(1). To znamená, že v knihovně Mori nemá smysl si dopředu počítat a pamatovat počet prvků seznamu. Naproti tomu funkce nth se sice u obou typů kolekcí chová stejně, má však výrazně odlišnou složitost: O(n) v případě seznamů (lineární složitost) a O(log₃₂N) v případě vektorů (logaritmická složitost). U krátkých vektorů (do 32 prvků) je složitost konstantní a i u delších vektorů je počet kroků nutných pro získání n-tého prvku velmi malý (například dva kroky pro vektory o délce přibližně 1000 prvků atd., maximálně se jedná o sedm kroků). Složitost funkce peek je v případě vektoru taktéž rovna O(log₃₂N), na rozdíl od funkce last se složitostí O(N) – v případě vektorů tedy vždy používejte peek!

Povšimněte si, že vektory ve skutečnosti neodpovídají složitostí některých funkcí běžně chápaným vektorům-jednorozměrným polím. Je tomu tak z toho důvodu, že v knihovně Mori jsou vektory implementovány odlišným způsobem a to zejména proto, aby bylo možné jednoduše implementovat funkci conj, tj. aby se již vytvořená datová struktura mohla sdílet mezi větším množstvím vektorů (to je možné i díky jejich neměnnosti).

7. Druhý demonstrační příklad: použití seznamů a vektorů

Ve druhém demonstračním příkladu jsou ukázány základní vlastnosti některých výše popsaných funkcí, zejména chování ve chvíli, kdy je datová struktura (seznam či vektor) prázdná. Nejprve se podívejme na zdrojový kód příkladu, který je hodně „ukecaný“, a to kvůli přehlednosti:

// ------------------------------------------------------------
// Knihovna Mori: demonstrační příklad číslo 2
// ------------------------------------------------------------
 
// vytvoření čtyř seznamu různé délky
var list1 = mori.list(1,2,3);
var list2 = mori.list(1,2);
var list3 = mori.list(1);
var list4 = mori.list();
 
// vytvoření čtyř vektoru různé délky
var vector1 = mori.vector(1,2,3);
var vector2 = mori.vector(1,2);
var vector3 = mori.vector(1);
var vector4 = mori.vector();
 
 
 
// ------------------------------------------------------------
// Výpis informaci o délkách seznamu a vektoru
// ------------------------------------------------------------
console.log("List1 size: " + mori.count(list1));
console.log("List2 size: " + mori.count(list2));
console.log("List3 size: " + mori.count(list3));
console.log("List4 size: " + mori.count(list4));
 
console.log("Vector1 size: " + mori.count(vector1));
console.log("Vector2 size: " + mori.count(vector2));
console.log("Vector3 size: " + mori.count(vector3));
console.log("Vector4 size: " + mori.count(vector4));
 
 
 
// ------------------------------------------------------------
// Vyzkoušení funkce conj
// ------------------------------------------------------------
console.log("Using conj:");
 
console.log("conj list1: " + mori.conj(list1, 42));
console.log("conj list2: " + mori.conj(list2, 42));
console.log("conj list3: " + mori.conj(list3, 42));
console.log("conj list4: " + mori.conj(list4, 42));
 
console.log("conj vector1: " + mori.conj(vector1, 42));
console.log("conj vector2: " + mori.conj(vector2, 42));
console.log("conj vector3: " + mori.conj(vector3, 42));
console.log("conj vector4: " + mori.conj(vector4, 42));
 
 
 
// ------------------------------------------------------------
// Vyzkoušení funkce pop
// ------------------------------------------------------------
console.log("Using pop:");
 
console.log("pop list1: " + mori.pop(list1));
console.log("pop list2: " + mori.pop(list2));
console.log("pop list3: " + mori.pop(list3));
// následující volání skončí chybou!
//console.log("pop list4: " + mori.pop(list4));
 
console.log("pop vector1: " + mori.pop(vector1));
console.log("pop vector2: " + mori.pop(vector2));
console.log("pop vector3: " + mori.pop(vector3));
// následující volání skončí chybou!
//console.log("pop vector4: " + mori.pop(vector4));
 
 
 
// ------------------------------------------------------------
// Vyzkoušení funkce peek
// ------------------------------------------------------------
console.log("Using peek:");
 
console.log("peek list1: " + mori.peek(list1));
console.log("peek list2: " + mori.peek(list2));
console.log("peek list3: " + mori.peek(list3));
console.log("peek list4: " + mori.peek(list4));
 
console.log("peek vector1: " + mori.peek(vector1));
console.log("peek vector2: " + mori.peek(vector2));
console.log("peek vector3: " + mori.peek(vector3));
console.log("peek vector4: " + mori.peek(vector4));
 
 
 
// ------------------------------------------------------------
// Vyzkoušení funkce first
// ------------------------------------------------------------
console.log("Using first:");
 
console.log("first list1: " + mori.first(list1));
console.log("first list2: " + mori.first(list2));
console.log("first list3: " + mori.first(list3));
console.log("first list4: " + mori.first(list4));
 
console.log("first vector1: " + mori.first(vector1));
console.log("first vector2: " + mori.first(vector2));
console.log("first vector3: " + mori.first(vector3));
console.log("first vector4: " + mori.first(vector4));
 
 
 
// ------------------------------------------------------------
// Vyzkoušení funkce last
// ------------------------------------------------------------
console.log("Using last:");
 
console.log("last list1: " + mori.last(list1));
console.log("last list2: " + mori.last(list2));
console.log("last list3: " + mori.last(list3));
console.log("last list4: " + mori.last(list4));
 
console.log("last vector1: " + mori.last(vector1));
console.log("last vector2: " + mori.last(vector2));
console.log("last vector3: " + mori.last(vector3));
console.log("last vector4: " + mori.last(vector4));
 
 
 
// ------------------------------------------------------------
// Vyzkoušení funkce distinct
// ------------------------------------------------------------
console.log("Using distinct:");
 
console.log("distinct []: " + mori.distinct(mori.list()));
console.log("distinct [1]: " + mori.distinct(mori.list(1)));
console.log("distinct [1 2]: " + mori.distinct(mori.list(1,2)));
console.log("distinct [1 2 1]: " + mori.distinct(mori.list(1,2,1)));
console.log("distinct [1 2 1 2]: " + mori.distinct(mori.list(1,2,1,2)));
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

Zdrojový kód HTML stránky použité pro spuštění druhého demonstračního příkladu v prohlížeči:

<!doctype html>
<html>
    <head>
        <title>Mori tests #02</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_02.js"></script>
    </head>
    <body>
        <h1>Mori tests #02</h1>
    </body>
</html>

Příklad by měl po svém spuštění na konzoli (webového prohlížeče) vypsat tyto zprávy:

List1 size: 3
List2 size: 2
List3 size: 1
List4 size: 0
Vector1 size: 3
Vector2 size: 2
Vector3 size: 1
Vector4 size: 0
Using conj:
conj list1: (42 1 2 3)
conj list2: (42 1 2)
conj list3: (42 1)
conj list4: (42)
conj vector1: [1 2 3 42]
conj vector2: [1 2 42]
conj vector3: [1 42]
conj vector4: [42]
Using pop:
pop list1: (2 3)
pop list2: (2)
pop list3: ()
pop vector1: [1 2]
pop vector2: [1]
pop vector3: []
Using peek:
peek list1: 1
peek list2: 1
peek list3: 1
peek list4: null
peek vector1: 3
peek vector2: 2
peek vector3: 1
peek vector4: null
Using first:
first list1: 1
first list2: 1
first list3: 1
first list4: null
first vector1: 1
first vector2: 1
first vector3: 1
first vector4: null
Using last:
last list1: 3
last list2: 2
last list3: 1
last list4: null
last vector1: 3
last vector2: 2
last vector3: 1
last vector4: null
Using distinct:
distinct []: ()
distinct [1]: (1)
distinct [1 2]: (1 2)
distinct [1 2 1]: (1 2)
distinct [1 2 1 2]: (1 2)

Obrázek 3: Výpis na konzoli zachycený v nástroji Inspect Page (Midori).

Povšimněte si chování funkce mori.pop, která skončí s chybou ve chvíli, kdy se jí předá prázdná datová struktura, ať již se jedná o seznam či o vektor:

Obrázek 4: Funkce mori.pop volaná pro prázdný seznam.

Obrázek 5: Funkce mori.pop volaná pro prázdný vektor.

8. Sekvence a lazy sekvence

Na všechny datové typy, které jsou v knihovně Mori programátorům nabízeny, se můžeme dívat jako na různým způsobem implementované datové kolekce (collections), které je možné velmi snadno převést na takzvané sekvence, a to konkrétně s využitím funkce seq. Mnohdy se dokonce konverze datové kolekce na sekvenci provede automaticky uvnitř jiné funkce (s vlastními daty se přitom většinou žádným způsobem nemanipuluje, konverze znamená, že se pouze použije obecnější pohled na data). To ale současně znamená, že všechny datové typy (tj. sekvence) mají společné rozhraní, které svými základními možnostmi zhruba odpovídá iterátorům známým například z programovacího jazyka Java (ve skutečnosti sice jazyk JavaScript pojem „rozhraní“ (interface) nepoužívá ve stejném smyslu jako jazyk Java, ovšem funkce pro práci se sekvencemi lze skutečně použít například jak pro seznamy, tak i pro vektory, mapy atd., bez ohledu na to, jaká datová struktura je pro implementaci sekvence použita).

V knihovně Mori existuje pro práci se sekvencemi poměrně velké množství funkcí, jejichž skládáním je možné vytvořit i dosti komplikované algoritmy. Navíc, což je pro implementaci mnoha algoritmů taktéž velmi důležité, podporuje knihovna Mori i vytváření a manipulaci s takzvanými línými sekvencemi (lazy sequence), v nichž se nové datové prvky vytváří či zjišťují až ve chvíli, kdy je to skutečně zapotřebí. A vzhledem k tomu, že mnohdy není zapotřebí přečíst všechny prvky nějaké líné sekvence, znamená to, že lze bez větších problémů pracovat i s nekonečnými sekvencemi (samozřejmě se však nesmíme snažit vyhodnotit/přečíst všechny prvky nekonečné sekvence, na druhou stranu je možné aplikovat funkci, která z jedné nekonečné líné sekvence vytvoří odlišnou línou sekvenci, a to bez toho, aby došlo k přeplnění operační paměti). Použití běžných sekvencí i líných sekvencí si ukážeme na několika demonstračních příkladech.

9. Základní funkce pro práci se sekvencemi

Naprostý základ pro práci se sekvencemi tvoří dvojice funkcí nazvaných first a rest. Funkce first vrací první prvek v sekvenci, popř. speciální hodnotu null v případě, že je sekvence prázdná. Funkce rest vrací zbylé prvky v sekvenci, popř. prázdnou sekvenci ve chvíli, kdy je sekvence prázdná či obsahuje pouze jeden prvek. U běžných sekvencí, například seznamů, jsou tyto funkce implementovány přímočaře, ovšem v případě lazy sekvencí se prvky vrácené pomocí funkce first vyhodnocují až za běhu aplikace, například pomocí nějaké generátorové funkce. Tímto způsobem je možné pracovat i s nekonečnými sekvencemi, u nichž už z principu nelze dopředu znát celkový počet prvků atd. (viz též závěr předchozí kapitoly).

10. Třetí demonstrační příklad: použití funkcí first a rest

Třetí demonstrační příklad je velmi jednoduchý. Nejprve jsou vytvořeny čtyři seznamy, přičemž třetí seznam obsahuje pouze jeden prvek a seznam čtvrtý je prázdný. Následně je vytvořena čtveřice vektorů se stejným počtem prvků. Délky (počty prvků) všech čtyř seznamů i všech čtyř vektorů jsou vypsány do konzole a posléze je ukázáno chování funkcí first a rest, popř. i kombinace těchto funkcí:

// ------------------------------------------------------------
// Knihovna Mori: demonstrační příklad číslo 3
// ------------------------------------------------------------
 
// vytvoření čtyř seznamu různé délky
var list1 = mori.list(1,2,3);
var list2 = mori.list(1,2);
var list3 = mori.list(1);
var list4 = mori.list();
 
// vytvoření čtyř vektoru různé délky
var vector1 = mori.vector(1,2,3);
var vector2 = mori.vector(1,2);
var vector3 = mori.vector(1);
var vector4 = mori.vector();
 
 
 
// ------------------------------------------------------------
// Výpis informaci o délkách seznamu a vektoru
// ------------------------------------------------------------
console.log("List1 size: " + mori.count(list1));
console.log("List2 size: " + mori.count(list2));
console.log("List3 size: " + mori.count(list3));
console.log("List4 size: " + mori.count(list4));
 
console.log("Vector1 size: " + mori.count(vector1));
console.log("Vector2 size: " + mori.count(vector2));
console.log("Vector3 size: " + mori.count(vector3));
console.log("Vector4 size: " + mori.count(vector4));
 
 
 
// ------------------------------------------------------------
// Vyzkoušení funkce first
// ------------------------------------------------------------
console.log("Using first:");
 
console.log("first list1: " + mori.first(list1));
console.log("first list2: " + mori.first(list2));
console.log("first list3: " + mori.first(list3));
console.log("first list4: " + mori.first(list4));
 
console.log("first vector1: " + mori.first(vector1));
console.log("first vector2: " + mori.first(vector2));
console.log("first vector3: " + mori.first(vector3));
console.log("first vector4: " + mori.first(vector4));
 
 
 
// ------------------------------------------------------------
// Vyzkoušení funkce rest
// ------------------------------------------------------------
console.log("Using rest:");
 
console.log("rest list1: " + mori.rest(list1));
console.log("rest list2: " + mori.rest(list2));
console.log("rest list3: " + mori.rest(list3));
console.log("rest list4: " + mori.rest(list4));
 
console.log("rest vector1: " + mori.rest(vector1));
console.log("rest vector2: " + mori.rest(vector2));
console.log("rest vector3: " + mori.rest(vector3));
console.log("rest vector4: " + mori.rest(vector4));
 
 
 
// ------------------------------------------------------------
// Kombinace rest+first
// ------------------------------------------------------------
console.log("Using rest+first:");
 
console.log("rest+first list1: " + mori.first(mori.rest(list1)));
console.log("rest+first list2: " + mori.first(mori.rest(list2)));
console.log("rest+first list3: " + mori.first(mori.rest(list3)));
console.log("rest+first list4: " + mori.first(mori.rest(list4)));
 
console.log("rest+first vector1: " + mori.first(mori.rest(vector1)));
console.log("rest+first vector2: " + mori.first(mori.rest(vector2)));
console.log("rest+first vector3: " + mori.first(mori.rest(vector3)));
console.log("rest+first vector4: " + mori.first(mori.rest(vector4)));
 
 
 
// ------------------------------------------------------------
// Kombinace rest+rest
// ------------------------------------------------------------
console.log("Using rest+rest:");
 
console.log("rest+rest list1: " + mori.rest(mori.rest(list1)));
console.log("rest+rest list2: " + mori.rest(mori.rest(list2)));
console.log("rest+rest list3: " + mori.rest(mori.rest(list3)));
console.log("rest+rest list4: " + mori.rest(mori.rest(list4)));
 
console.log("rest+rest vector1: " + mori.rest(mori.rest(vector1)));
console.log("rest+rest vector2: " + mori.rest(mori.rest(vector2)));
console.log("rest+rest vector3: " + mori.rest(mori.rest(vector3)));
console.log("rest+rest vector4: " + mori.rest(mori.rest(vector4)));
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

Zdrojový kód HTML stránky použité pro spuštění třetího demonstračního příkladu v prohlížeči:

<!doctype html>
<html>
    <head>
        <title>Mori tests #03</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_03.js"></script>
    </head>
    <body>
        <h1>Mori tests #03</h1>
    </body>
</html>

Na výstupu vygenerovaném demonstračním příkladem je nejzajímavější chování funkce first v případě, že se jí předá prázdná sekvence: vrátí se null. Naproti tomu funkce rest vrátí v případě sekvence s jedním prvkem prázdnou sekvenci; stejná hodnota se vrátí i ve chvíli, kdy se funkci rest na vstup předá prázdná sekvence (což je vlastně logické a očekávatelné chování, protože se do programového kódu nemusí zbytečně vkládat další podmínky):

List1 size: 3
List2 size: 2
List3 size: 1
List4 size: 0
Vector1 size: 3
Vector2 size: 2
Vector3 size: 1
Vector4 size: 0
 
Using first:
first list1: 1
first list2: 1
first list3: 1
first list4: null
first vector1: 1
first vector2: 1
first vector3: 1
first vector4: null
 
Using rest:
rest list1: (2 3)
rest list2: (2)
rest list3: ()
rest list4: ()
rest vector1: (2 3)
rest vector2: (2)
rest vector3: ()
rest vector4: ()

Obrázek 6: První část výstupu demonstračního příkladu.

Obrázek 7: Druhá část výstupu demonstračního příkladu.

11. Funkce range, take a map

Vlastnosti lazy sekvencí a taktéž nekonečných lazy sekvencí plně vyniknou až ve chvíli, kdy začneme používat funkce, které s těmito sekvencemi umí manipulovat, a to bez nutnosti výpočtu jednotlivých prvků sekvence. Nejprve se seznámíme s funkcí mori.range sloužící k vytvoření lazy sekvence čísel. Této funkci lze předat tři parametry mori.range(start, end, step) určující první číselnou hodnotu v sekvenci, limitní hodnotu a krok (ten udává počet prvků sekvence). Ovšem parametry je možné vynechat; když se například vynechá první parametr, bude mít první prvek v sekvenci hodnotu 0, když se vynechá parametr poslední, bude krok roven jedné. To znamená, že volání:

mori.range(10)

vytvoří lazy sekvenci:

(0 1 2 3 4 5 6 7 8 9)

jejíž prvky jsou však vyhodnoceny až ve chvíli, kdy je to zapotřebí (nebo taky nikdy!). Zajímavější je volání:

mori.range()

které vytvoří nekonečnou lazy sekvenci.

Funkce mori.take na svém vstupu očekává celé číslo n a libovolnou (lazy) sekvenci. Vrátí se taktéž lazy sekvence, mající ovšem maximálně n prvků původní sekvence. Prvky se nevyhodnocují, proto tato funkce bez problémů pracuje i s nekonečnými sekvencemi.

Třetí funkcí je funkce mori.map, která dokáže pro každý prvek vstupní (lazy) sekvence zavolat jinou zvolenou funkci. Výsledkem mori.map je druhá lazy sekvence. Ovšem pozor: zvolená funkce se pro prvky nevolá ihned, ale „líně“ až ve chvíli, kdy je to skutečně zapotřebí (v mnoha případech tedy nikdy). Proto i funkce map může pracovat s nekonečnými sekvencemi.

12. Čtvrtý demonstrační příklad: použití funkcí range, take a map

Podívejme se nyní na okomentovaný čtvrtý demonstrační příklad, v němž se kombinují možnosti výše popsaných funkcí range, map a take. Za povšimnutí stojí zejména možnost využít ve funkci map anonymní funkci či libovolnou (pojmenovanou) funkci. Tyto funkce nejsou v příkladu zcela čisté, protože provádějí výpis na konzoli. Právě díky tomu je patrné, kdy se tyto funkce ve skutečnosti volají, tj. kdy se z lazy sekvence stane běžná (vyhodnocená, realizovaná) sekvence:

// ------------------------------------------------------------
// Knihovna Mori: demonstrační příklad číslo 4
// ------------------------------------------------------------
 
// konstrukce nekonečné lazy sekvence
var sequence1 = mori.range();
 
// z nekonečné lazy sekvence získáme konečnou línou sekvenci s 10 prvky
var sequence2 = mori.take(10, sequence1);
 
// realizace druhé sekvence + její výpis
console.log("sequence2=" + sequence2);
 
// funkce použitá ve funkcích map
function twice(element) {
    console.log('processing:', element);
    return 2 * element;
}
 
// mapujeme uživatelskou funkci na *konečnou* sekvenci
var sequence3 = mori.map(twice, sequence2);
 
// mapujeme uživatelskou anonymní funkci na *konečnou* sekvenci
var sequence4 = mori.map(function(element) {
    console.log('processing:', element);
    return -2 * element
}, sequence2);
 
// obě nové vytvořené sekvence vypíšeme
// (tím se 'realizuji')
console.log("sequence3=" + sequence3);
console.log("sequence4=" + sequence3);
 
// nyní mapujeme uživatelskou funkci na *nekonečnou* sekvenci
var sequence5 = mori.map(twice, sequence1);
 
// nyní mapujeme uživatelskou anonymní funkci na *nekonečnou* sekvenci
var sequence6 = mori.map(function(element) {
    console.log('processing:', element);
    return -1 * element
}, sequence1);
 
// obě nově vytvořené sekvence vypíšeme
// (tím se 'realizuji')
console.log("sequence5 begins with: " + mori.take(10, sequence5));
console.log("sequence6 begins with: " + mori.take(10, sequence6));
 
// mapování může mít několik "vrstev", stále se však jedna o lazy
// sekvence, které se prozatím nerealizuji (mezikrok je taktéž nekonečná sekvence!)
var sequence7 = mori.map(twice, mori.map(twice, sequence1));
 
// sekvence vypíšeme
// (tím se 'realizuje')
console.log("sequence7 begins with: " + mori.take(10, sequence7));
 
 
 
// ------------------------------------------------------------
// Finito
// ------------------------------------------------------------

Zdrojový kód HTML stránky použité pro spuštění čtvrtého demonstračního příkladu v prohlížeči:

<!doctype html>
<html>
    <head>
        <title>Mori tests #04</title>
        <meta charset="utf-8">
        <script src="mori.js"></script>
        <script src="mori_03.js"></script>
    </head>
    <body>
        <h1>Mori tests #04</h1>
    </body>
</html>

Obrázek 8: Výsledek běhu demonstračního příkladu..

13. Repositář se zdrojovými kódy všech dnešních demonstračních příkladů

Demonstrační příklady, na nichž jsme si ukazovali vlastnosti knihovny Mori, byly uloženy do Git repositáře dostupného na adrese https://github.com/tisnik/pre­sentations. V tabulce zobrazené pod tímto odstavcem naleznete na zdrojové kódy těchto příkladů přímé odkazy:

14. Odkazy na Internetu

1. Mori na GitHubu
   https://github.com/swannodette/mori
2. Mori: popis API (dokumentace)
   http://swannodette.github.io/mori/
3. Mori: Benchmarking
   https://github.com/swanno­dette/mori/wiki/Benchmarking
4. Functional data structures in JavaScript with Mori
   http://sitr.us/2013/11/04/functional-data-structures.html
5. Immutable.js
   https://facebook.github.io/immutable-js/
6. Persistent data structure
   https://en.wikipedia.org/wi­ki/Persistent_data_structu­re
7. Understanding Clojure's Persistent Vectors, pt. 1
   http://hypirion.com/musin­gs/understanding-persistent-vector-pt-1
8. Hash array mapped trie (Wikipedia)
   https://en.wikipedia.org/wi­ki/Hash_array_mapped_trie
9. Java theory and practice: To mutate or not to mutate?
   http://www.ibm.com/develo­perworks/java/library/j-jtp02183/index.html
10. Efficient persistent (immutable) data structures
    https://persistent.codeplex.com/
11. Netscape Enterprise Server (Wikipedia)
    https://en.wikipedia.org/wi­ki/Netscape_Enterprise_Ser­ver
12. SSJS Reference Guide (Server-Side JavaScript)
    http://docs.oracle.com/cd/E19957–01/816–6410–10/816–6410–10.pdf
13. Atom: moderní textový editor
    http://www.root.cz/clanky/atom-moderni-textovy-editor/
14. Atom: moderní textový editor (dokončení)
    http://www.root.cz/clanky/atom-moderni-textovy-editor-dokonceni/
15. Propojení světa LISPu se světem JavaScriptu s využitím transpřekladače Wisp
    http://www.root.cz/clanky/propojeni-sveta-lispu-se-svetem-javascriptu-s-vyuzitim-transprekladace-wisp/
16. Propojení světa LISPu se světem JavaScriptu s využitím transpřekladače Wisp (2.část)
    http://www.root.cz/clanky/propojeni-sveta-lispu-se-svetem-javascriptu-s-vyuzitim-transprekladace-wisp-2-cast/
17. Wisp na GitHubu
    https://github.com/Gozala/wisp
18. Wisp playground
    http://www.jeditoolkit.com/try-wisp/
19. REPL v prohlížeči
    http://www.jeditoolkit.com/in­teractivate-wisp/
20. Minification (programming)
    https://en.wikipedia.org/wi­ki/Minification_(programmin­g)
21. Clojure Macro Tutorial (Part I, Getting the Compiler to Write Your Code For You)
    http://www.learningclojure­.com/2010/09/clojure-macro-tutorial-part-i-getting.html
22. Clojure Macro Tutorial (Part II: The Compiler Strikes Back)
    http://www.learningclojure­.com/2010/09/clojure-macro-tutorial-part-ii-compiler.html
23. Clojure Macro Tutorial (Part III: Syntax Quote)
    http://www.learningclojure­.com/2010/09/clojure-macro-tutorial-part-ii-syntax.html
24. Tech behind Tech: Clojure Macros Simplified
    http://techbehindtech.com/2010/09/28/clo­jure-macros-simplified/
25. Fatvat – Exploring functional programming: Clojure Macros
    http://www.fatvat.co.uk/2009/02/clo­jure-macros.html
26. Eulerovo číslo
    http://cs.wikipedia.org/wi­ki/Eulerovo_??slo
27. List comprehension
    http://en.wikipedia.org/wi­ki/List_comprehension
28. List Comprehensions in Clojure
    http://asymmetrical-view.com/2008/11/18/list-comprehensions-in-clojure.html
29. Clojure Programming Concepts: List Comprehension
    http://en.wikibooks.org/wi­ki/Clojure_Programming/Con­cepts#List_Comprehension
30. Clojure core API: for macro
    http://clojure.github.com/clo­jure/clojure.core-api.html#clojure.core/for
31. cirrus machina – The Clojure for macro
    http://www.cirrusmachina.com/blog/com­ment/the-clojure-for-macro/
32. Clojure.org: Clojure home page
    http://clojure.org/downloads
33. Clojure.org: Vars and the Global Environment
    http://clojure.org/Vars
34. Clojure.org: Refs and Transactions
    http://clojure.org/Refs
35. Clojure.org: Atoms
    http://clojure.org/Atoms
36. Clojure.org: Agents as Asynchronous Actions
    http://clojure.org/agents
37. A Couple of Clojure Agent Examples
    http://lethain.com/a-couple-of-clojure-agent-examples/
38. Clojure – Functional Programming for the JVM
    http://java.ociweb.com/mar­k/clojure/article.html
39. Clojure quick reference
    http://faustus.webatu.com/clj-quick-ref.html
40. 4Clojure
    http://www.4clojure.com/
41. ClojureDoc
    http://clojuredocs.org/
42. Clojure (Wikipedia EN)
    http://en.wikipedia.org/wiki/Clojure
43. Clojure (Wikipedia CS)
    http://cs.wikipedia.org/wiki/Clojure
44. Riastradh's Lisp Style Rules
    http://mumble.net/~campbe­ll/scheme/style.txt
45. Dynamic Languages Strike Back
    http://steve-yegge.blogspot.cz/2008/05/dynamic-languages-strike-back.html
46. Scripting: Higher Level Programming for the 21st Century
    http://www.tcl.tk/doc/scripting.html
47. Java Virtual Machine Support for Non-Java Languages
    http://docs.oracle.com/ja­vase/7/docs/technotes/gui­des/vm/multiple-language-support.html
48. The Lua VM, on the Web
    https://kripken.github.io/lu­a.vm.js/lua.vm.js.html
49. Lua.vm.js REPL
    https://kripken.github.io/lu­a.vm.js/repl.html
50. lua2js
    https://www.npmjs.com/package/lua2js
51. lua2js na GitHubu
    https://github.com/basicer/lua2js-dist
52. Seriál o programovacím jazyku Lua
    http://www.root.cz/serialy/pro­gramovaci-jazyk-lua/
53. Source-to-source compiler
    https://en.wikipedia.org/wiki/Source-to-source_compiler
54. JavaScript is Assembly Language for the Web: Sematic Markup is Dead! Clean vs. Machine-coded HTML
    http://www.hanselman.com/blog/Ja­vaScriptIsAssemblyLanguage­ForTheWebSematicMarkupIsDe­adCleanVsMachinecodedHTML­.aspx
55. JavaScript is Web Assembly Language and that's OK.
    http://www.hanselman.com/blog/Ja­vaScriptIsWebAssemblyLangu­ageAndThatsOK.aspx
56. Dart
    https://www.dartlang.org/
57. CoffeeScript
    http://coffeescript.org/
58. TypeScript
    http://www.typescriptlang.org/
59. Lua (programming language)
    http://en.wikipedia.org/wi­ki/Lua_(programming_langu­age)
60. Static single assignment form (SSA)
    http://en.wikipedia.org/wi­ki/Static_single_assignmen­t_form
61. LuaJIT 2.0 SSA IRhttp://wiki.luajit.org/SSA-IR-2.0
62. The LuaJIT Project
    http://luajit.org/index.html
63. LuaJIT FAQ
    http://luajit.org/faq.html
64. LuaJIT Performance Comparison
    http://luajit.org/performance.html
65. LuaJIT 2.0 intellectual property disclosure and research opportunities
    http://article.gmane.org/gma­ne.comp.lang.lua.general/58908
66. LuaJIT Wiki
    http://wiki.luajit.org/Home
67. LuaJIT 2.0 Bytecode Instructions
    http://wiki.luajit.org/Bytecode-2.0
68. Programming in Lua (first edition)
    http://www.lua.org/pil/contents.html
69. Lua 5.2 sources
    http://www.lua.org/source/5.2/
70. Tcl Plugin Version 3
    http://www.tcl.tk/software/plugin/
71. JavaScript: The Web Assembly Language?
    http://www.informit.com/ar­ticles/article.aspx?p=1856657
72. asm.js
    http://asmjs.org/
73. List of languages that compile to JS
    https://github.com/jashke­nas/coffeescript/wiki/List-of-languages-that-compile-to-JS
74. REPL
    https://en.wikipedia.org/wi­ki/Read%E2%80%93eval%E2%80%93prin­t_loop
75. The LLVM Compiler Infrastructure
    http://llvm.org/ProjectsWithLLVM/
76. clang: a C language family frontend for LLVM
    http://clang.llvm.org/
77. emscripten
    http://kripken.github.io/emscripten-site/
78. LLVM Backend („Fastcomp“)
    http://kripken.github.io/emscripten-site/docs/building_from_source/LLVM-Backend.html#llvm-backend
79. Emscripten – Fastcomp na GitHubu
    https://github.com/kripken/emscripten-fastcomp
80. Clang (pro Emscripten) na GitHubu
    https://github.com/kripken/emscripten-fastcomp-clang
81. Why not use JavaScript?
    https://ckknight.github.i­o/gorillascript/