Přejít k navigační liště

Zdroják » JavaScript » Rozšiřujeme náš interpret. V JavaScriptu.

Rozšiřujeme náš interpret. V JavaScriptu.

Články JavaScript

Máme vlastní λazyk. Máme jeho parser a máme jeho interpret. Ale nám nestačí. Dnes budeme vylepšovat.

Přidání nových konstrukcí

Náš jazyk je zatím poměrně chudý. Například neexistuje způsob, jak vytvořit novou proměnnou. Už jsem zmiňoval, že musíme použít IIFE, takže by to mělo vypadat nějak takto (hloupý příklad, ale lepší jsem nevymyslel):

(λ(x, y){
  (λ(z){ ## a bude to horší, když bude jedna proměnná záviset na druhé
    print(x + y + z);
  })(x + y);
})(2, 3);

Přidáme si klíčové slovo let, které nám dovolí napsat takovouto konstrukci:

let (x = 2, y = 3, z = x + y) print(x + y + z);

Pro každou z těchto definic jsou viditelné proměnné, deklarované před ní. Tento zápis by se dal přepsat třeba takto:

(λ(x){
  (λ(y){
    (λ(z){
      print(x + y + z);
    })(x + y);
  })(3);
})(2);

Taková změna se dá zařídit přímo v parseru a nevyžaduje žádné změny v evaluátoru. Namísto přidání vyhraženého typu uzlu “let” proměníme celou konstrukci do nodů “call” a “lambda”. Všimněte si, že nepřidáváme žádné sémantické novinky do jazyka. Nazývá se to “syntaktický cukr” a proces, kdy se v AST tato konstrukce rozkládá do už existujících uzlů je známa též jako “odslazení” (desugaring).

My tentokrát ale půjdeme jinou cestou a opravdu si přidáme uzel typu “let”. Důvodem je, že tento uzel budeme moci vyhodnotit mnohem efektivněji – nepotřebujeme ve skutečnosti vytvářet uzávěry a hned je volat, stačí nám jen rozšířit jmenný prostor o nové proměnné.

Když už budeme dělat změny parseru a evaluátoru, přidáme podporu pro “pojmenovaný let”, který je známý z jazyka Scheme. Dovoluje definovat výrazy s cyklem mnohem snazším způsobem:

print(let loop (n = 10)
        if n > 0 then n + loop(n - 1)
                 else 0);

Toto je rekurzivní cyklus, který počítá součet 10 + 9 + … + 0. V jazyce, jaký máme dosud, to musíme zapsat zhruba takto:

print((λ(loop){
         loop = λ(n) if n > 0 then n + loop(n - 1)
                              else 0;
         loop(10);
       })());

Abychom si to usnadnili, přidáme i koncept “pojmenované funkce”. Budeme tedy schopní psát konstrukce jako:

print((λ loop (n) if n > 0 then n + loop(n - 1)
                           else 0)
      (10));

Zrekapitulujme si modifikace, které potřebujeme udělat:

  • Přidat volitelné jméno za klíčové slovo “lambda”. Pokud bude zadané, pak musí prostředí, v němž funkce běží, definovat toto jméno a nastavit mu hodnotu rovnou této funkci. To je přesně totéž, co se děje v JavaScriptu při vytváření pojmenované funkce.
  • Přidat podporu nového klíčového slova “let”. Za tímto slovem je nepovinné jméno a uzávorkovaný seznam (i prázdný) proměnných, zapsaný ve formě jméno = VÝRAZ, a oddělených čárkami. Vlastní tělo let je výraz (který může být samozřejmě {sekvence})

Nutné změny v parseru

Nejprve uděláme malou změnu tokenizéru – přidáme slovo let do seznamu klíčových slov

var keywords = " let if then else lambda λ true false ";

Musíme modifikovat parse_lambda v parseru tak, abychom mohli uložit volitelné jméno funkce:

function parse_lambda() {
    return {
        type: "lambda",
        // tady je ta změna - následující řádek jsme přidali
        name: input.peek().type == "var" ? input.next().value : null, 

        vars: delimited("(", ")", ",", parse_varname),
        body: parse_expression()
    };
}

Přidáme parser pro klíčové slovo let:

function parse_let() {
    skip_kw("let");
    if (input.peek().type == "var") {
        var name = input.next().value;
        var defs = delimited("(", ")", ",", parse_vardef);
        return {
            type: "call",
            func: {
                type: "lambda",
                name: name,
                vars: defs.map(function(def){ return def.name }),
                body: parse_expression(),
            },
            args: defs.map(function(def){ return def.def || FALSE })
        };
    }
    return {
        type: "let",
        vars: delimited("(", ")", ",", parse_vardef),
        body: parse_expression(),
    };
}

Parser vyhodnocuje oba případy. Pokud je za klíčovým slovem “let” token typu “var”, jedná se o pojmenovaný let. Přečteme si definice proměnných funkcí delimited(), protože jsou v závorkách a oddělené čárkami, a použijeme pomocnou funkci parse_vardef, která je definovaná níže. Pak vrátíme uzel “call”, který vyvolá pojmenovaný funkční výraz (takže výsledkem celého uzlu je IIFE. Argumenty této funkce jsou proměnné, definované v let, a samotný “call” se postará o to, aby byly jejich hodnoty v args. Tělem je pak výraz, získaný, jak jinak, pomocí parse_expression().

Pokud nejde o pojmenovaný let, vrátíme uzel typu “let”, v němž jsou proměnné (vars) a tělo (body). Proměnné obsahují objekty ve tvaru {name: VARIABLE, def: AST}, tak jak je rozparsuje funkce parse_vardef:

function parse_vardef() {
    var name = parse_varname(), def;
    if (is_op("=")) {
        input.next();
        def = parse_expression();
    }
    return { name: name, def: def };
}

Nakonec musíme zařídit, aby funkce parse_atom správně zpracovala slovo “let”, tak přidáme následující řádek:

// může být před obsluhou parse_if
if (is_kw("let")) return parse_let();

Změny v evaluátoru

Protože jsme se rozhodli implementovat novou funkcionalitu přímo v AST namísto odslazení do existujících AST uzlů, musíme upravit i evaluátor, aby reflektoval provedené změny.

Nejprve musíme změnit make_lambda.

function make_lambda(env, exp) {
    if (exp.name) {                    // tyto
        env = env.extend();            // řádky
        env.def(exp.name, lambda);     // jsem
    }                                  // přidal
    function lambda() {
        var names = exp.vars;
        var scope = env.extend();
        for (var i = 0; i < names.length; ++i)
            scope.def(names[i], i < arguments.length ? arguments[i] : false);
        return evaluate(exp.body, scope);
    }
    return lambda;
}

Pokud je zadané jméno funkce, pak rozšíříme aktuální jmenný prostor a definujeme jméno, které bude na tento prostor ukazovat. Zbytek se nemění.

Nakonec přidáme do evaluátoru jeden case pro obsluhu slova let:

case "let":
  exp.vars.forEach(function(v){
      var scope = env.extend();
      scope.def(v.name, v.def ? evaluate(v.def, env) : false);
      env = scope;
  });
  return evaluate(exp.body, env);

Všimněte si, že rozšiřuje scope pro každou proměnnou a definuje ji tím, že vyhodnotí inicializační kód, pokud nějaký je. Nakonec vyhodnotí samotné tělo.

Pojďme to otestovat:

println(let loop (n = 100)
          if n > 0 then n + loop(n - 1)
                   else 0);

let (x = 2, y = x + 1, z = x + y)
  println(x + y + z);

# vypíše chybu, protože proměnné jsou vidět jen v těle
# print(x + y + z);

let (x = 10) {
  let (x = x * 2, y = x * x) {
    println(x);  ## 20
    println(y);  ## 400
  };
  println(x);  ## 10
};

Udělat tyto změny nebylo příliš složité, protože si jazyk píšeme sami. Ale co kdyby ho napsal někdo jiný a my neměli zdrojové kódy, nebo dokonce kdyby šlo o jazyk, který používá velké množství lidí a očekávají, že syntax bude rigidní? Příkladem takového jazyka je třeba právě JavaScript. Představte si, že chcete přidat novou jazykovou konstrukci do JavaScriptu – můžete? Spíš ne, ačkoli můžete navrhnout svou změnu těm chlápkům, co se o JS starají. Bude trvat velmi dlouho, než váš návrh bude posouzen, schválen, standardizován a implementován. Pokud si nad JS neimplementujeme vlastní jazyk, nemáme šanci… (Ostatně všechny ty CoffeeScripty a Babelify nedělají nic jiného – pozn.překl.)

Říkal jsem vám, že budu občas tvrdit, že Lisp je skvělý. V Lispu můžeme přidávat syntaktické konstrukce, aniž bychom měnili implementaci parseru / evaluátoru / kompileru, což nám zjednodušuje život: nemusíme tyto konstrukce cpát všem uživatelům daného jazyka a nemusíme čekat roky na to, než nějaký výbor návrhy schválí a někdo jiný je implementuje. Lisp je v tomto svobodný. Pokud by Lisp neměl pojmenované funkce nebo konstrukci let, můžeme je doplnit pomocí menšího množství kódu, než jsme potřebovali v této kapitole, a budou vypadat jako by v jazyce byly zabudované.

Jak jsme rychlí?

Stručná odpověď: děsně pomalí!

Ale pojďme to otestovat. Použijeme funkci s dvojitou rekurzí pro výpočet Fibonacciho posloupnosti, protože nemá příliš velké nároky na zásobník a čas provedení roste exponenciálně s růstem n. Porovnáme pak rychlost provádění v JavaScriptu a v našem jazyce. Přidal jsem proto dvě primitivní funkce:

globalEnv.def("fibJS", function fibJS(n){
  if (n < 2) return n;
  return fibJS(n - 1) + fibJS(n - 2);
});

globalEnv.def("time", function(fn){
  var t1 = Date.now();
  var ret = fn();
  var t2 = Date.now();
  println("Time: " + (t2 - t1) + "ms");
  return ret;
});

Na svém stroji s Google Chrome jsem naměřil následující výsledky:

fib(10): 55
Time: 6ms
fibJS(10): 55
Time: 1ms
---
fib(20): 6765
Time: 57ms
fibJS(20): 6765
Time: 0ms
---
fib(27): 196418
Time: 975ms
fibJS(27): 196418
Time: 3ms

Poslední volání pro n=27 zabralo téměř sekundu, zatímco JavaScriptová implementace si vyžádala tři milisekundy. To je samozřejmě naprosto nepřijatelné.

Můžeme (a také to nakonec uděláme) zkompilovat λazyk do JavaScriptu. Abychom se vyhnuli omezení při rekurzi, můžeme přidat klíčová slova pro cykly, komplexní datové struktury jako pole a objekty, navíc i výjimky – a všechno tohle budeme implementovat týmiž konstrukcemi z JavaScriptu. A kde je pointa? JavaScript má své chyby, to ano, ale připlácnout novou syntax nad tu jeho nepřinese žádnou slávu ani užitek.

Místo toho jsem se rozhodl přijít s další potravou pro vaše mozky a společně odhalit, jak napsat evaluátor v continuation-passing style (předávání pokračování). Pohrajeme si s pokračováními (continuations) a pak si napíšeme kompiler, který vytvoří kód skoro tak efektivní jako byste ho psali v JavaScriptu, ale s některými rozšířenými sémantickými schopnostmi, které JavaScript nemá.

Zkusíme vytvořit něco lepšího, než nabízí cílový jazyk. Rychlost bude důležitá, ale není to hlavní cíl.

Konec seriálu

Pro malý zájem byl překlad seriálu ukončen.

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.

Komentáře

Subscribe
Upozornit na
guest
14 Komentářů
Nejstarší
Nejnovější Most Voted
Inline Feedbacks
View all comments
Velký zájemce

Malý zájem? Podle čeho se to měří?

Co udělat pro to, aby to pokračovalo?

expert

Asi podle toho, ze se pod clanky nestrhl zadny flamewar.

maki

Zdravim,

taktiez neviem, podla coho sa meria zaujem, ale jedno viem: vdaka za Vase clanky, ktore sa citaju ‚jednym dychom‘. Urcite pokracovat, pokial to bude mozne.

Co sa tyka samotneho serialu, zaujimala ma hlavne cast, aku parsovaciu techniku pre expressions ste pouzili (resp,. autor). Ak sa nemylim, tak TDOP (Top Down Operator Precedence).

Urcite stoji za precitanie:

http://effbot.org/zone/simple-top-down-parsing.htm#attribute-and-item-lookups
http://javascript.crockford.com/tdop/tdop.html

fos4 - velký zájemce 2

Já se přidávám za to, aby bylo pokračování. Ačkoliv do komentářů nepíšu, tak na článek z této série se vždy těším a s chutí si ho přečtu. Takže se ptám také, co udělat proto,a by se pokračovalo?

Jan

Já si tento seriál také rád četl. Psali jste malý zájem, ale malý zájem koho? Čtenářů, nebo snad autora, který už má malý zájem překládat?

Miloš

TO se nediv. Ono překládat něco stojí dost času, mám to vyzkoušené. A když by to bylo zbytečně….

Miloš

Dobrý den,
já se taky vždycky těšil. I když minulý díl jsem moc nevstřebal. Ale to je inteligencí a lambda-nezkušeností.
Zato parsování textu mě zajímá, kdysi jsem si hrál s editorem a ANTLRem & co.
Také prosím o pokračování.
Miloš

Petr Bolf

Chápu, že překládání je časově náročné a že místo toho můžete třeba pájet součástky na Arduinu, což je jistě zábavnější, ale i tak se přimlouvám za pokračování. A to i přesto, že pointu si lze přečíst v originální, globální angličtině. Díky

Jakub Vrána

Malý zájem se dá jasně poznat z toho, že u žádného z předchozích dílů nebyl ani jeden komentář. Sice by to mohlo souviset i s tím, že všechny předchozí díly měly komentáře zakázané, ale co už.

Milan

Děkuji za tento překlad. Takové články / seriály na Zdrojáku už dlouho chyběly. Informatika není jen o tom, nějak poslepovat skládačku, ale i o tom, promyslet problém do hloubky. A právě o tom seriál je. Neučí, jak vzít nějakou módní technologii, která nějakým kouzlem vyřeší náš problém. Článek učí, jak fungují překladače a programovací jazyky. Když budete potřebovat ve svém projektu nějaký DSL (domain specific language), můžete se při jeho návrhu odpíchnout právě od tohoto seriálu. A je jedno, zda překladač napíšete v javascriptu nebo v něčem jiném, tento článek totiž ukazuje princip, jak toho dosáhnout. I když to tak může vypadat, udělat si vlastní překladač není jen hříčka. Například díky vlastnímu DSL můžeme přizpůsobovat aplikaci různým požadavkům zákazníků, aniž bychom museli měnit kód samotné aplikace. Podobně jako rozšíříte funkcionalitu Excelu díky VBA.

Chtělo by to tady víc takových článků, které se zabývají algoritmy a rozborem problémů. Nebo třeba optimalizací. Ne všechny projekty jsou jen přehazování dat mezi formulářem a databází a tahání dat z databází a nějakém zobrazení. Občas nemůže být „jen programátoři“.

Nic proti článkům, které popisují nové funkce programovacích jazyků, nástroje, knihovny. Ty jsou také potřeba a čtu je s radostí. A pak ušetří spoustu práce nebo posunou aplikace o kousek jiným směrem, aby nezahnily v čase.

Takže se přimlouvám za pokračování překladu.

Oldis

No tak zatím sme všichni sledovali jak se to vyvine, takže ještě nebylo o čem flamovat

Petr

Prakticky každý den jsem otevíral Zdrojak.cz, abych se podíval, jestli je další díl seriálu. To zatím u mně žádný jiný seriál nezpůsobil.
Takže pokud tenhle seriál končí, tak se asi znovu vrátím k periodě jeden měsíc…

milos

ja jsem na tom podobne

Milos

Na druhou stranu nám nic nebrání pokračovat v originále.

Enum a statická analýza kódu

Mám jednu univerzální radu pro začínající programátorty. V učení sice neexistují rychlé zkratky, ovšem tuhle radu můžete snadno začít používat a zrychlit tak tempo učení. Tou tajemnou ingrediencí je statická analýza kódu. Ukážeme si to na příkladu enum.