Začínáme implementovat vlastní jazyk. V JavaScriptu.

Začínáme seriál, který vás v jednoduchosti provede tvorbou parseru, interpretu a kompilátoru vlastního jazyka. To vše bude implementováno v JavaScriptu. V prvním díle si představíme náš λazyk.

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

Prolog k seriálu (Slova překladatele)

Před mnoha lety jsem si, po přečtení článku Pierse Cawleyho Higher Order JavaScript, uvědomil, že JavaScript pro mne nebude už nikdy stejný jako dřív. Objevil jsem krásu funkcionální tváře JavaScriptu, a byl jsem ztracen.

Něco podobného se mi před časem stalo s tutoriálem od Mihai Bazona. Je v něm krásně popsáno, jak napsat lexer, parser, posléze i interpreter a kompiler nějakého jazyka, který připomíná trošku Lisp. Nakonec jsem jej požádal o souhlas s překladem a vydáním. Jeho „Jasně, proč ne?“ mě velmi potěšilo. V následujících textech budete mít příležitost zjistit, co mi na tom udělalo radost.

Důležité upozornění, tak důležité, že ho dám tučně:
Pokud máte dojem, že autor textu je debil, protože tam má chyby a nedodělky a měl by něco implementovat jinak a takhle to bude pomalé, tak počkejte do dalších dílů. Je pravděpodobné, že přesně to se řeší třeba o dvě kapitoly dál.

Pokud se s tímto dojmem budete potýkat častěji, tak je to znamení, že celá série není pro vás. Je pro lidi, které zajímá „zajímavé programování“, i když není výsledkem něco hyper ultra nového…

Když jsem napsal, že takovou sérii článků připravuju, komentoval to kdosi tím, že by (samozřejmě) bylo lepší použít nástroj XYZ v Javě, který dovoluje psaní ultra rychlých parserů… Proboha, proč?! Já nechci psát ultrarychlé parsery, já chci vědět, jak se píše parser, co je uvnitř a jak to funguje. jinými slovy: chci vědět, jak funguje motor, nechci prodávat nejrychlejší auta na světě.

Ale dosti za mne, pojďte a otevřte hlavy vědění. Ať se vám seriál líbí.


Jak implementovat programovací jazyk v JavaScriptu

Zde je návod, jak implementovat vlastní programovací jazyk v JavaScriptu. Pokud jste někdy psali interpreter nebo překladač, pak tu pravděpodobně nenajdete nic nového. Ale pokud používáte regulární výrazy k “parsování” čehokoli, co vypadá jako programovací jazyk, pak si prosím přečtěte alespoň kapitolu o parsování. Pojďme psát méně zabugovaný kód!

Obsah je seřazen od jednoduchého ke složitějšímu. Doporučuju nepřeskakovat, pokud si nejste naprosto jisti, že dané téma zvládáte. Když se ztratíte, tak se vždycky můžete vrátit zpátky.

Cílová skupina tohoto návodu jsou průměrní programátoři v JavaScriptu / NodeJS.

Co se naučíme?

  • Co je to parser a jak ho napsat
  • Jak napsat interpreter
  • Co jsou pokračování (continuation) a proč jsou důležitá
  • Psaní kompileru
  • Jak převést kód do continuation-passing style (předávání pokračování)
  • Několik základních optimizačních technik
  • Příklady toho, co náš λazyk (v orig.: λanguage) nabízí navíc oproti prostému JS

Mezitím budu argumentovat, proč jsou Lispovské jazyky skvělé. Jazyk, se kterým budeme pracovat, nebude Lisp. Má bohatší syntax (klasickou infixovou notaci, kterou všichni známe) a je zhruba tak silný jako Scheme, s výjimkou maker. Bohužel (či bohudík) jsou makra hlavní zbraní Lispu, kterou jiné jazyky stěží porazí (pokud nejsou samy Lispovským dialektem). [Ano, znám SweetJS… Těsně vedle.]

Ale ze všeho nejdřív si pojďme vysnít svůj programovací jazyk.

Popis našeho λazyka

Dřív, než se pustíme do čehokoli, bychom si měli ujasnit, co je naším cílem. Je skvělé dát dohromady velmi pečlivě formální gramatiku, ale já hodlám být v tomto návodu popisnější, takže začnu několika příklady v našem λazyce:

# toto je komentář

println("Hello World!");

println(2 + 3 * 4);

# funkce jsou uvozeny slovem `lambda` nebo znakem `λ`
fib = lambda (n) if n < 2 then n else fib(n - 1) + fib(n - 2);

println(fib(15));

print-range = λ(a, b)             # `λ` je synonymum pro `lambda`
                if a <= b then {  # `then` je volitelné, jak je vidět níž
                  print(a);
                  if a + 1 <= b {
                    print(", ");
                    print-range(a + 1, b);
                  } else println("");        # newline
                };
print-range(1, 5);

Všimněte si, že identifikátory mohou obsahovat i znak minus (print-range). Je to věc osobního vkusu: já vždy dávám mezery kolem operátorů, nemám moc rád camelCase a minus je hezčí než podtržítko. Hezká věc na psaní jazyků je, že si je můžete navrhnout tak, jak se vám líbí. :)

Výstup výše uvedeného kódu je:

Hello World!
14
610
1, 2, 3, 4, 5

Λazyk vypadá trochu jako JavaScript, ale je jiný. Zaprvé, nejsou tu žádné příkazy, jen výrazy. Výraz vrací hodnotu a může být použitý všude tam, kde je očekávaná jakákoli hodnota. Středníky jsou zapotřebí pro oddělení výrazů v sekvenci. Složené závorky { a } vytváří takovou sekvenci, a samy jsou výrazem. Jeho hodnota je hodnota posledního vyhodnoceného výrazu. Následující kód je platný program:

a = {
  fib(10);  # nemá žádný efekt, ale je vyhodnoceno
  fib(15)   # poslední středník můžete vypustit
};
print(a); # vypíše 610

Funkce jsou uvozeny klíčovým slovem “lambda” nebo λ (jsou to synonyma). Za tímto slovem musí být v závorkách seznam jmen proměnných, oddělených čárkami (seznam může být i prázdný) jako v JavaScriptu – jsou to jména argumentů. Tělo funkce je jednoduchý výraz, ale může to být i sekvence, zavřená do {}. Není žádný příkaz “return” (nejsou tu žádné příkazy) – hodnota posledního vyhodnoceného výrazu ve funkci je zároveň návratová hodnota z funkce.

Není žádné “var”. Pokud chcete vytvořit novou proměnnou, použijte to, co se v JavaScriptu nazývá IIFE (Immediately Invoked Function Expression, tedy definice anonymní funkce, která je rovnou vykonána). Použijte “lambda” a deklarujte proměnné jako argumenty. Proměnné jsou viditelné v těle funkce, a funkce jsou uzávěry (closures), jako v JavaScriptu.

I samotný if je výraz. V JavaScriptu dosáhnete stejného efektu ternárním operátorem:

a = foo() ? bar() : baz();           // JavaScript
a = if foo() then bar() else baz();  # λazyk

Klíčové slovo “then” je nepovinné, pokud větev začíná otevírací složenou závorkou (a následuje tedy sekvence), jak můžete vidět ve funkci print-range výše. V jiných případech je povinné. Klíčové slovo “else” je povinné pouze tehdy, když je použita větev “else”. Znovu: “then” a “else” berou jako své tělo jeden výraz, který ale může být ve formě sekvence výrazů, oddělených středníky a uzavřené do {}. Pokud část “else” chybí a výsledek podmínky je false, je výsledkem celého výrazu “if” také false. Když o tom mluvíme, tak false je jediná “nepravdivá” hodnota v celém λazyce.

if foo() then print("OK");

Vytiskne “OK” tehdy a pouze tehdy, pokud výsledek volání foo() NENÍ roven false. Pro úplnost je i klíčové slovo true, ale opravdu vše, co není právě rovno false (v JS je to operátor ===) bude interpretováno jako true (včetně prázdného řetězce “” a nuly).

Všimněte si také, že není důvod vyžadovat závorky okolo podmínky ve výrazu if. Není chyba, pokud je tam napíšete, otvírací závorka zahajuje výraz, ale jsou jen nadbytečné.

Celý program je vyhodnocován tak, jako by byl sám uzavřen do složených závorek, proto je potřeba jednotlivé výrazy oddělovat středníkem, s výjimkou posledního.

Tak, toto je náš λazyk. Není nezbytně skvělý. Syntax vypadá jednoduše, ale má svá úskalí. Řada vlastností chybí, jako objekty a pole – na ně se teď soustředit nechceme, protože nejsou podstatné pro náš cíl. Pokud chápete vše, co jsme si dosud řekli, budete schopni toto vše bez problémů implementovat.

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

V dalším díle si napíšeme parser pro tento λazyk.

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é.)

Zdroj: https://www.zdrojak.cz/?p=19491