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

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

Seriál: Implementujeme vlastní programovací jazyk. V JavaScriptu. (6 dílů)

  1. Začínáme implementovat vlastní jazyk. V JavaScriptu. 2.2.2017
  2. Píšeme vlastní parser. V JavaScriptu. 13.2.2017
  3. Píšeme vlastní parser. V JavaScriptu. (pokračování) 20.2.2017
  4. Píšeme vlastní interpret. V JavaScriptu. 27.2.2017
  5. Píšeme vlastní interpret. V JavaScriptu. (pokračování) 8.3.2017
  6. Rozšiřujeme náš interpret. V JavaScriptu. 18.4.2017

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.

Začal programovat v roce 1984 s programovatelnou kalkulačkou. Pokračoval k BASICu, assembleru Z80, Forthu, Pascalu, Céčku, dalším assemblerům, před časem v PHP a teď by rád neprogramoval a radši se věnoval starým počítačům.

Věděli jste, že nám můžete zasílat zprávičky? (Jen pro přihlášené.)

Komentáře: 11

Přehled komentářů

Velký zájemce Malý zájem?
expert Re: Malý zájem?
maki Urcite pokracovat
fos4 - velký zájemce 2
Jan
Miloš Re:
Miloš Je to super
Petr Bolf
Jakub Vrána Malý zájem
Milan Výborný seriál, jen tak dál
Oldis
Zdroj: https://www.zdrojak.cz/?p=19685