Hraní s λazykem

Jakkoli je náš λazyk v tuto chvíli prostý, je (teoreticky) schopen vyřešit jakýkoli problém, který je možno strojově řešit. To jsem si nevymyslel, to vím díky tomu, že chlápci chytřejší než kdy budu já – Alonzo Church a Alan Turing – dokázali, že lambda-kalkulus je ekvivalentní Turingovu stroji, a náš λazyk funguje jako lambda kalkul.

V praxi to znamená, že i když náš λazyk neobsahuje některé základní featury, můžeme je implementovat pomocí toho, co už máme, a dokonce v něm můžeme napsat interpreter jiného jazyka. Vážně.

Poznámka překladatele: Pokud se vám v tomto bodě zdá, že autor přehání a že λazyk je hříčka, která třeba zemře i při poměrně mělké rekurzi, vydržte s kritikou ještě nějaký čas, autor dál ukáže, jak se třeba tyto problémy řeší, předvede generátory a yield nebo optimalizující překlad do JavaScriptu.

Cykly

Cykly nejsou nezbytné, když máme rekurzi. Už jsme si ukázali příklad, který něco takového dělal. Pojďme si to vyzkoušet.

print_range = λ(a, b) if a <= b {
                        print(a);
                        if a + 1 <= b {
                          print(", ");
                          print_range(a + 1, b);
                        } else println("");
                      };
print_range(1, 10);

Pozn. překl.: Testovací konzole pro vyzkoušení příkladů z článku je k dispozici na adrese jsfiddle.net.

Ve skutečnosti máme poměrně zásadní problém, pokud zvedneme rozsah na, řekněme, 1000 místo 10. Já jsem dostal chybu “Maximum call stack size exceeded” po nějakých 600 průbězích. To je proto, že evaluátor je rekurzivní a vyčerpá zásobník JavaScriptu. To je zásadní věc, ale existují řešení. Možná budete mít cukání přidat nějaká iterační klíčová slova, jako for či while, ale nedělejme to. Rekurze je hezká, nemusíme ji zahazovat. Později si ukážeme, jak toto omezení obejít.

Datové struktury (či spíš jejich neexistence)

Náš λazyk obsahuje tři datové typy. Čísla, řetězce a boolean. Možná se zdá nemožné vytvořit složené datové struktury jako objekty nebo seznamy. Ve skutečnosti máme jeden typ navíc: funkci. V lambda kalkulu můžeme použít funkce k vytvoření libovolné datové struktury, včetně objektů s dědičností. Ukážeme si příklad – vytvoření seznamů.

Dejme tomu, že si vytvoříme funkci cons, která konstruuje speciální objekt, v němž jsou dvě hodnoty; nazvěme si tento objekt “cons cell” nebo “pár”. Pojmenujeme si jednu z těchto hodnot “car” a druhou “cdr”, protože tak se jmenují v Lispu po desetiletí. Můžeme použít funkce car a cdr k vyzvednutí jednoho či druhého prvku z daného páru. Tedy:

x = cons(10, 20);
print(car(x));    # vypíše 10
print(cdr(x));    # vypíše 20

S tímto můžeme snadno definovat seznam:

Seznam je objekt, jehož první element je car a zbytek jeho elementů je cdr. Ale cdr může obsahovat jen jednoduchou hodnotu. Tato hodnota je seznam. Seznam je objekt, jehož první element je car a zbytek jeho elementů je cdr. Ale cdr může obsahovat jen jednoduchou hodnotu. Tato hodnota je seznam. A tak dále… Rekurze: viz rekurze

Jde tedy o rekurzivní datovou strukturu. Jeden problém ale zůstává: kde to celé skončí? Intuitivně řekneme, že konec je tam, kde je cdr prázdný. Jenže jak definujeme “prázdné”? Uděláme si k tomu speciální objekt, který nazveme NIL. Bude to technicky opět pár (můžeme aplikovat car i cdr, ale výsledek bude opět NIL), ale nebude to opravdový pár. Řekněme, že to bude falešný pár. Seznam čísel 1, 2, 3, 4 a 5 pak stvoříme takto:

x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL)))));
print(car(x));                      # 1
print(car(cdr(x)));                 # 2  V Lispu je zkratka cadr
print(car(cdr(cdr(x))));            # 3                     caddr
print(car(cdr(cdr(cdr(x)))));       # 4                     cadddr
print(car(cdr(cdr(cdr(cdr(x))))));  # 5  a pro toto už žádná zkratka není

Vypadá to nechutně, když nemáme patřičnou podporu v syntaxi (trocha cukru by neškodila). Ale chtěl jsem vám jen ukázat, že je možné vytvořit datovou strukturu i v našem “omezeném” jazyce. Zde jsou definice:

cons = λ(a, b) λ(f) f(a, b);
car = λ(cell) cell(λ(a, b) a);
cdr = λ(cell) cell(λ(a, b) b);
NIL = λ(f) f(NIL, NIL);

Když jsem poprvé viděl impolementaci cons / car / cdr tímto způsobem, byl jsem vyděšen tím, že není zapotřebí if (ale to není překvapivé, původní lambda kalkulus žádné if neobsahuje). Samozřejmě, že to žádný jazyk nedělá tímto způsobem, protože to je velmi neefektivní, ale to nedělá výše uvedený způsob méně krásným. Česky řečeno, výše napsané dělá toto:

• Cons bere dvě hodnoty a vrací funkci, která je uzavírá (closure). Tato funkce je “cell object”. Má jeden argument, funkci f, a když ji vyvolá, předá jí právě ty dvě hodnoty, které má uzavřené v closure.
• Car vezme “cell object” (tedy tu výše zmíněnou funkci) a zavolá ji. Jako parametr (=f) jí předá funkci, která vezme dva parametry a vrátí první.
• Cdr je jako car, ale funkce se trochu liší: vrací druhý argument
• NIL se tváří jako cell, tedy minimálně tím, že je to funkce, která má jeden argument, funkci f, ale při vyvolání jí předá (NIL, NIL), takže car i cdr získají jen hodnotu NIL.

cons = λ(a, b) λ(f) f(a, b);
car = λ(cell) cell(λ(a, b) a);
cdr = λ(cell) cell(λ(a, b) b);
NIL = λ(f) f(NIL, NIL);

x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL)))));
println(car(x));                      # 1
println(car(cdr(x)));                 # 2
println(car(cdr(cdr(x))));            # 3
println(car(cdr(cdr(cdr(x)))));       # 4
println(car(cdr(cdr(cdr(cdr(x))))));  # 5

Tento kód můžete vyzkoušet v testovací konzoli (pozn. red.).

Je mnoho algoritmů pracujících se seznamy, které můžeme implementovat pomocí rekurze. Jako příklad si nadefinujme funkci foreach, která aplikuje funkci na každý prvek seznamu:

foreach = λ(list, f)
            if list != NIL {
              f(car(list));
              foreach(cdr(list), f);
            };
foreach(x, println);

A ještě jeden příklad, který vytvoří seznam celých čísel v zadaném rozsahu:

range = λ(a, b)
          if a <= b then cons(a, range(a + 1, b))
                    else NIL;

# tisk druhých mocnin čísel 1..8
foreach(range(1, 8), λ(x) println(x * x));

Seznamy, které jsme si vytvořili, jsou neměnné (nelze změnit hodnotu car ani cdr poté, co jsou jednou definované). Většina Lispů nabízí nějaký způsob, jak prvky seznamu změnit. V jazyku Scheme se tyto funkce nazývají set-car! a set-cdr! V Common Lispu se jmenují sugestivně rplaca / rplacd. Tentokrát dám přednost konvenci z jazyka Scheme:

cons = λ(x, y)
         λ(a, i, v)
           if a == "get"
              then if i == 0 then x else y
              else if i == 0 then x = v else y = v;

car = λ(cell) cell("get", 0);
cdr = λ(cell) cell("get", 1);
set-car! = λ(cell, val) cell("set", 0, val);
set-cdr! = λ(cell, val) cell("set", 1, val);

# v tomto případě může být NIL reálným cons
NIL = cons(0, 0);
set-car!(NIL, NIL);
set-cdr!(NIL, NIL);

## test:
x = cons(1, 2);
println(car(x));
println(cdr(x));
set-car!(x, 10);
set-cdr!(x, 20);
println(car(x));
println(cdr(x));

Zde je názorná ukázka toho, jak lze stvořit proměnnou složenou datovou strukturu. Nebudu vysvětlovat, jak to funguje, je to poměrně pochopitelné.

Mohli bychom se posunout dál, ukázat si například definici objektů, ale bez změny syntaxe λazyka by byl výsledek velmi ošklivý. Druhá možnost je udělat změny do tokenizeru / parseru a možná přidat nějakou sémantiku k evaluátoru. To je to, co mainstreamové jazyky dělají, a je to mnohokrát potřebný krok k dozažení lepšího výkonu. To si ukážeme v dalším dílu.

Pokračování příště

Příště si ukážeme, jak do našeho λazyka přidat nové syntaktické konstrukce.

Přeloženo z originálního tutoriálu, jehož autorem je Mihai Bazon. Překlad vychází s laskavým autorovým svolením.