Jednoduchý interpreter

Abychom si to zrekapitulovali: napsali jsme tři funkce – InputStream, TokenStream a parse. Máme-li zdrojový kód v řetězci, AST z něho vygenerujeme pomocí:

var ast = parse(TokenStream(InputStream(code)));

Napsání interpreteru je snazší, než psaní parseru. Musíme procházet AST a vyhodnocovat výrazy v jejich pořadí.

Prostředí

Klíčová věc, nezbytná ke správnému vykonání kódu, je prostředí (environment) – struktura, která udržuje přiřazení proměnných. Tuto strukturu předáváme jako argument naší funkci evaluate. Pokaždé, když narazíme na uzel typu “lambda” (připomínám: jde o definici funkce), musíme přidat do prostředí proměnné (podle argumentů funkce) a inicializovat je podle předaných hodnot. Pokud argument zastiňuje proměnnou z vnějšího jmenného prostoru (scope – budu zde používat slova prostředí a prostor jako vzájemně zaměnitelné), musíme si dát pozor a před návratem z funkce správně vrátit předchozí hodnoty.

Nejjednodušší způsob, jak toto zajistit, je využít prototypovou dědičnost z JavaScriptu. Když vstoupíme do funkce, vytvoříme nové prostředí, nastavíme jeho prototyp na vnější (rodičovské) prostředí a vyhodnotíme tělo funkce v tomto novém prostředí. Ve chvíli, kdy z funkce odejdeme, nemusíme dělat nic – rodičovské prostředí stále obsahuje to, co v něm bylo před vstupem do funkce.

Zde je definice objektu Environment:

function Environment(parent) {
    this.vars = Object.create(parent ? parent.vars : null);
    this.parent = parent;
}
Environment.prototype = {
    extend: function() {
        return new Environment(this);
    },
    lookup: function(name) {
        var scope = this;
        while (scope) {
            if (Object.prototype.hasOwnProperty.call(scope.vars, name))
                return scope;
            scope = scope.parent;
        }
    },
    get: function(name) {
        if (name in this.vars)
            return this.vars[name];
        throw new Error("Undefined variable " + name);
    },
    set: function(name, value) {
        var scope = this.lookup(name);
        // nedovolíme globální definici z vnořeného přostředí
        if (!scope && this.parent)
            throw new Error("Undefined variable " + name);
        return (scope || this).vars[name] = value;
    },
    def: function(name, value) {
        return this.vars[name] = value;
    }
};

Objekt Environment má rodiče (parent), který ukazuje na rodičovské prostředí. Pro globální objekt je rodič roven null. Objekt má vlastnost vars, která udržuje přiřazení proměnných. Proměnné jsou inicializovány pomocí Object.create(null) u globálního prostoru, nebo pomocí Object.create(parent.vars) pro vnořená prostředí.

Prostředí má následující metody:

• extend() pro vytvoření podprostoru
• lookup(name) pro vyhledání prostoru, v němž je daná proměnná definována
• get(name) pro získání hodnoty proměnné. Pokud není definovaná, vyhazuje chybu.
• set(name, value) pro nastavení hodnoty proměnné. Tato metoda musí najít prostor, v němž je proměnná definovaná. Pokud není nalezena a my nejsme v globáním prostoru, vyhazuje chybu.
• def(name, value) vytváří proměnnou v aktuálním prostoru (popřípadě ji zastiňuje – shadow)

Funkce Evaluate

Prostředí máme, můžeme se tedy věnovat hlavnímu problému. Funkce pro vyhodnocení bude jeden velký příkaz switch, který se podle typu uzlu rozhodne, co je třeba udělat, a vyhodnotí daný uzel. Okomentujeme si jednotlivé případy:

function evaluate(exp, env) {
    switch (exp.type) {

Pro uzly s konstantní hodnotou vrátíme jejich hodnotu:

      case "num":
      case "str":
      case "bool":
        return exp.value;

Proměnné jsou získány z prostředí. Vzpomeňte si, že uzel “var” obsahuje jméno proměnné ve vlastnosti “value”:

      case "var":
        return env.get(exp.value);

U přiřazení musíme ověřit, zda je levá strana nějaká proměnná (token “var”). Pokud ne, vyhazujeme chybu – v tuto chvíli nepodporujeme jiné typy přiřazení. Pak použijeme env.set pro nastavení hodnoty. Všimněte si, že hodnotu, kterou budeme přiřazovat, nejprve rekurzivně vyhodnotíme pomocí volání funkce evaluate.

      case "assign":
        if (exp.left.type != "var")
            throw new Error("Cannot assign to " + JSON.stringify(exp.left));
        return env.set(exp.left.value, evaluate(exp.right, env));

„Binární“ uzly aplikují operátor na dva operandy. Funkci apply_op si napíšeme později, je velmi prostá. Opět musíme zavolat rekurzivně evaluátor k tomu, abychom získali levý a pravý operand:

      case "binary":
        return apply_op(exp.operator,
                        evaluate(exp.left, env),
                        evaluate(exp.right, env));

Uzel “lambda” je vlastně vytvoření JavaScriptové uzávěry (closure), takže jej budeme moci volat z okolního JavaScriptového kódu stejně jako jakoukoli jinou funkci. Použijeme k tomu funkci make_lambda, kterou si napíšeme později:

      case "lambda":
        return make_lambda(env, exp);

Vyhodnocení uzlu “if” je jednoduché: nejprve vyhodnotíme podmínku. Pokud není false, pak vyhodnocujeme větev “then” a vracíme její hodnotu. V opačném případě vyhodnocujeme větev “else”, pokud existuje, nebo vracíme false.

      case "if":
        var cond = evaluate(exp.cond, env);
        if (cond !== false) return evaluate(exp.then, env);
        return exp.else ? evaluate(exp.else, env) : false;

Uzel “prog” je sekvence výrazů. Stačí rekurzivně vyhodnotit jeden po druhém a vrátit hodnotu posledního vyhodnoceného. U prázdné sekvence je vrácena hodnota false.

      case "prog":
        var val = false;
        exp.prog.forEach(function(exp){ val = evaluate(exp, env) });
        return val;

U uzlu “call” musíme zavolat funkci. Nejprve vyhodnotíme funkci, která by měla vrátit normální javascriptovou funkci (viz výše debata o make_lambda), pak vyhodnotíme argumenty a vykonáme danou funkci.

      case "call":
        var func = evaluate(exp.func, env);
        return func.apply(null, exp.args.map(function(arg){
            return evaluate(arg, env);
        }));

Víc možností nemáme, takže sem bychom se neměli nikdy dostat. Ale čistě pro případ, že přidáme nové typy uzlů a zapomeneme upravit evaluátor, si sem hodíme jednoznačné upozornění.

      default:
        throw new Error("I don't know how to evaluate " + exp.type);
    }
}

Toto je jádro evaluátoru, a jak můžete vidět, je opravdu jednoduché. Musíme ještě napsat dvě funkce, které jsme výše použili. Začněme funkcí apply_op coby tou jednodušší:

function apply_op(op, a, b) {
    function num(x) {
        if (typeof x != "number")
            throw new Error("Expected number but got " + x);
        return x;
    }
    function div(x) {
        if (num(x) == 0)
            throw new Error("Divide by zero");
        return x;
    }
    switch (op) {
      case "+"  : return num(a) + num(b);
      case "-"  : return num(a) - num(b);
      case "*"  : return num(a) * num(b);
      case "/"  : return num(a) / div(b);
      case "%"  : return num(a) % div(b);
      case "&&" : return a !== false && b;
      case "||" : return a !== false ? a : b;
      case "<"  : return num(a) < num(b);
      case ">"  : return num(a) > num(b);
      case "<=" : return num(a) <= num(b);
      case ">=" : return num(a) >= num(b);
      case "==" : return a === b;
      case "!=" : return a !== b;
    }
    throw new Error("Can't apply operator " + op);
}

Funkce vezme operátor a dva argumenty. Následuje nudný switch, který je aplikuje. Na rozdíl od JavaScriptu, který aplikuje jakýkoli operátor na jakýkoli argument a nestará se, zda to dává smysl či ne (1 + “” mu nedělá problém), my vyžadujeme, aby operandy byly číselné a u dělení aby dělitel nebyl nula. Používáme k tomu malé pomocné funkce num a div. Pro řetězce si definujeme něco jiného později.

Poznámka autora: Dopustil jsem se chyby, která se táhne zbytkem textu: výrazy typu a() && b() nebo a() || b() vždy vykonají obě funkce. To je samozřejmě špatně, správně by se funkce b() měla vyhodnocovat v závislosti na pravdivostní hodnotě funkce a(). Oprava je jednoduchá – v parseru stačí změnit binární operátory || a && na uzel typu “if”), ale ještě jsem to neudělal. Hanba mi!

Make_lambda

Funkce make_lambda je trochu rafinovanější:

function make_lambda(env, exp) {
    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;
}

Jak vidíte, vrací prostou JS funkci, která uzavírá do closure prostředí a výraz k vyhodnocení. Je důležité si uvědomit, že nic z toho se neděje ve chvíli, kdy se uzávěra vytváří – ale v okamžiku vykonání rozšíří prostředí, které bylo uzavřeno v okamžiku vytvoření, o nové proměnné (argumenty a jejich hodnoty). Pokud je při volání předáno méně parametrů, než má funkce argumentů, jsou ty chybějící nahrazeny hodnotou false. Nakonec jen vyhodnotí tělo funkce v nově vytvořeném prostoru.

Primitivní funkce

Je patrné, že náš jazyk neposkytuje žádné možnosti komunikace s okolím. V některých příkladech kódů budu používat funkce print() a println(), ale nikde je nedefinuju. Definuju si je jako tzv. “Primitiva” – napíšu si je v JavaScriptu a vložím do globálního jmenného prostoru.

Dejme si vše dohromady a vyzkoušejme si, jak náš parser a interpreter fungují:

// Testovací kód
var code = "sum = lambda(x, y) x + y; print(sum(2, 3));";

// Pamatujte: parser bere TokenStream, který vzniká z InputStreamu
var ast = parse(TokenStream(InputStream(code)));

// Vytvoříme globální prostředí
var globalEnv = new Environment();

// definujeme primitivní funkci print
globalEnv.def("print", function(txt){
   console.log(txt);
});

// spustíme evaluátor
evaluate(ast, globalEnv); // mělo by do konzole vypsat “5”

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

V příští díle si konečně začneme s naším λazykem hrát. Pro netrpělivé zatím odkážeme testovací konzoli našeho λazyka.

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.