Как реализовать язык программирования на JavaScript. Часть 2: Интерпретатор

Автор оригинала: Mihai Bazon
  • Перевод
  • Tutorial

Здравствуйте! Представляю вам вторую часть моего перевода руководства реализации своего языка программирования на JavaScript — PL Tutorial.


От переводчика


Мы создадим свой язык программирования — λзык (в оригинале — λanguage). В процессе создания мы будем использовать достаточно много интересных техник, таких как рекурсивный спуск, стиль передачи управления, базовые техники оптимизации. Будет создано две версии интерпретатора — обычный и CPS-интерпретатор, транс-компилятор в JavaScript.


Автор оригинала — Mihai Bazon, автор известной библиотеки UglifyJS (инструмент для минимизации и форматирования JS-кода).



P.S. В интерпретаторе и компиляторе есть баг: в выражениях типа a() && b() или a() || b() всегда исполняются обе части. Это, конечно, неправильно потому, что a() ложно для оператора &&, или не ложно для оператора ||, то значение b() уже не играет никакой роли. Это несложно исправить.


Простой интерпретатор


В предыдущей части мы написали 3 функции: InputStream, TokenStream и parse. Чтобы получить AST из кода мы используем следующий код:


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

Написать интерпретатор легче, чем парсер: мы просто рекурсивно проходим дерево и исполняем выражения в их нормальном порядке.


Контекст (Environment)


Для правильного исполнения кода нам нужен контекст — объект, содержащий все переменные в данном месте. Он будет передаваться как аргумент в функцию evaluate.


Каждый раз, когда мы входим в узел lambda, мы должны добавить в контекст новые переменные — аргументы функции. Если аргумент перекрывает переменную из внешнего блока, мы должны восстановить старое значение переменной после выхода из функции.


Самый простой способ сделать это — использовать прототипное наследование JavaScript. Когда мы входим в новую функцию, мы создаем новый контекст, устанавливаем внешний контекст как его прототип, и вызывать функцию в новом контексте. Благодаря этому, нам ничего — во внешнем контексте останутся все его переменные.


Вот реализация объекта 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);
        // не разрешаем устанавливать неопределенные переменные не в глобальном контексте
        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;
    }
};

Объект Environment имеет поле parent, которое указывает на внешний контекст. Оно будет равно null для глобального контекста. У него есть поле vars, в котором есть все переменные, принадлежащие данному контексту. Для глобального контекста оно сразу равно пустому объекту (Object.create(null)) и копии переменных родительского контекста (Object.create(parent.vars)) для неглобального.


У него есть несколько методов:


  • extend() — скопировать текущий контекст.
  • lookup(name) — найти контекст, в котором определена переменная с именем name.
  • get(name) — получить значение переменной с именем name. Бросает исключение, если переменная не была определена.
  • set(name, value) — установить значение переменной. Данный метод ищет контекст, в котором определена переменная. Если она не определена, и мы находимся не в глобальном контексте, то будет брошено исключение.
  • def(name, value) — создает (или перекрывает, или переопределяет) переменную в текущем контексте.

Функция evaluate


Теперь, когда у нас есть объект Environment, мы можем перейти к решению основной проблемы. Данная функция будет большим блоком switch, которая будет делать какое-то действие в зависимости от типа переданного узла:


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

Для литералов мы просто возвращаем его значение:


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

Переменные берутся из контекста (название переменной содержится в поле value):


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

Для присваивания мы должны убедится, что с левой стороны у нас стоит название переменной (узел var). Если нет, то мы просто бросаем исключение (мы не поддерживаем присваивание чему-либо, кроме переменных). Дальше, мы устанавливаем значение переменной, используя env.set. Обратите внимание, правая часть выражения должна быть рассчитана используя рекурсивный вызов 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));

Для узла типа binary мы должны применить оператор для обоих операндов. Мы напишем функцию apply_op позже. Также, мы вызываем evaluate для обеих частей выражения:


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

Узел типа lambda будет возвращать обычное JavaScript-замыкание, поэтому его можно вызывать, как обычную функцию даже из JavaScript. Я добавил функцию make_lambda, которую покажу позже:


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

Исполнение узла if достаточно простое: сначала мы находим значение условия. Если оно не ложное, то возвращаем значение ветки then. Иначе, если есть ветка else, то её значение, или 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;

Узел prog — последовательность выражений. Мы просто исполняем все выражения по-порядку и берем значение последнего (значение пустой последовательности — false):


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

Для узла типа call нам нужно вызвать функцию. Перед этим мы найдем значение самой функции, найдем значения всех аргументов и вызовем функцию использую apply:


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

Сюда мы никогда не попадем, но на случай, если мы в парсер добавим новый тип узла и забудем добавить его в интерпретатор:


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

Это была основная часть интерпретатора. Выше мы использовали две функции, которые мы пока не реализовали, так что начнем:


apply_op:


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);
}

Она получает тип оператора и аргументы. Простой и понятный switch. В отличие от JavaScript, который может принимать любые значения, как переменные, даже те, которые не имеют никакого смысла. Мы требуем, чтобы операнды арифметических операторов были числами и не разрешаем деление на ноль. Для строк мы придумаем что-то потом.


make_lambda:


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;
}

Как вы можете видеть выше, она возвращает обычную JavaScript-функцию, которая использует переданный контекст и AST функции. Вся работа выполняется только тогда, когда вызывается сама функция: создается контекст, устанавливаюся аргументы (если их недостаточно, они стают false). Дальше просто исполняется тело функции в новом контексте.


Нативные функции


Как вы могли видеть, у нас не было способов взаимодействовать с JavaScript из нашего языка. Раньше я использовал функции print и println, но я их нигде не определял. Мы должны написать их на JavaScript и просто добавить в глобальный контекст.


Вот пример такого кода:


// здесь кауой-то тестовый код
var code = "sum = lambda(x, y) x + y; print(sum(2, 3));";

// помните, функция parse берет TokenStream, который в свою очередь берет InputStream
var ast = parse(TokenStream(InputStream(code)));

// создать глобальный контекст
var globalEnv = new Environment();

// определить "нативную" функцию "print"
globalEnv.def("print", function(txt){
  console.log(txt);
});

// интерпретировать
evaluate(ast, globalEnv); // выведет 5

Весь код


Вы можете скачать весь код, который мы за все это время написали. Его можно запустить используя NodeJS. Просто передайте код в стандартный поток:


echo 'sum = lambda(x, y) x + y; println(sum(2, 3));' | node lambda-eval1.js

Примеры кода


Наш λзык программирования хоть и простой, но (теоретически) может решить любую задачу, которая вообще может быть решена компьютером. Это потому, что некоторые чуваки, умнее, чем я когда-либо буду — Алонзо Чёрч и Алан Тьюринг — в своё время доказали доказали, что λ-исчисления (лямбда исчисления) эквивалентны машине Тюринга, а наш λзык реализует λ-исчисления.


Это значит, что даже, если в нашем языке нет каких-то возможностей, мы всеравно сможем реализовать их используя то, что у нас уже есть. Или, если это сделать сложно, мы можем написать интерпретатор для другого языка на этом.


Циклы


Циклы — не проблема, если у нас есть рекурсия. Я уже показывал пример цикла, реализованного поверх рекурсии. Давайте попробуем сделать это ещё раз.


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);

Но здесь у нас есть проблема: если мы увеличим количество итераций, скажем, к 1000. Я, к примеру, получаю ошибку “Maximum call stack size exceeded” уже после 600. Это случается потому, что нас интерпретатор рекурсивный и рекурсия достигает максимальной глубины.


Это серьезная проблема, но есть решение. Очень хочется добавить новые конструкции для итерации (for или while), но давайте попробуем обойтись без них. Рекурсия выглядит красиво, так что давайте её оставим. Мы позже увидим, как обойти данное ограничение.


Структуры данных (их отсутствие)


В нашем λзыке есть три типа данных: числа, строки и булев тип. Может показаться, что невозможно создать сложные типы, такие как массивы, или объекты. Но это не тат, у нас есть ещё один тип: функция. Оказывается, что если следовать λ-исчислениям, то мы можем создать любые структуры данных, включая объекты, даже с наследованием.


Я покажу это на примере списков. Давайте представим, что у нас есть функция cons, которая создает объект, содержащий два значения. Давайте назовем этот объект "ячейка" или "пара". Назовем одно из значений "car", а другое — "cdr". Просто потому, что они так называются в Lisp. Теперь, если у нас есть объект "cell", то мы можем получить его значения, используя функции car и cdr:


x = cons(10, 20);
print(car(x));    # выводит 10
print(cdr(x));    # выводит 20

Теперь мы можем легко определить список:


Список — пара, содержащая первый элемент в `car` и остальные элементы в `cdr`. Но `cdr` может содержать только одно значение! Это значение будет списком. Список — пара, содержащая первый элемент в `car` и остальные элементы в `cdr`. Но `cdr` может содержать только одно значение! Это значение будет списком. […]

Это получается рекурсивный тип данных. Но остается одна проблема: когда нужно останавливаться? Логически, мы должны остановиться когда cdr — пустой список. Но что такое "пустой список"? Для этого давайте добавим новый объект под названием "NIL". Оно может быть использовано как пара (мы можем использовать car и cdr на нем, но их результатом будет сам NIL). Теперь давайте создадим список из элементов 1, 2, 3, 4, 5:


x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL)))));
print(car(x));                      # 1
print(car(cdr(x)));                 # 2  а Lisp это аббревиатура. cadr
print(car(cdr(cdr(x))));            # 3                           caddr
print(car(cdr(cdr(cdr(x)))));       # 4                           cadddr
print(car(cdr(cdr(cdr(cdr(x))))));  # 5  но для этого нет аббревиатуры.

Это выглядит ужасно, когда для этого нет специального синтаксиса. Но я просто хотел показать, что это можно сделать используя уже существующие возможности λзыка. Вот реализация:


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

Когда я впервые увидел cons/car/cdr сделанные таким способом, я удивился что для них не нужно ни одного if (но это ни странно учитывая тот факт, что его нет в оригинальных λ-исчислениях). Конечно, никакой язык программирования не делает это таким путем, потому, что это крайне неэффективно, но это не делает λ-исчисления менее красивыми. Понятным языком, этот код делает следующее:


  • функция cons берет два значения (a и b) и возвращает функцию, которая держит их. Та функция — тот самый объект пары. Она берет аргумент и вызывает его для обеих значений пары.
  • функция car вызывает переданный аргумент, передавая функцию, которая возвращает первый аргумент.
  • функция cdr делает то же самое, что и функция car, но с той лишь разницей, что переданная функция возвращает второй аргумент.
  • функция NIL работает так же, как и cons, но возвращает пару, у которой два значения равны 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

Есть много алгоритмов на списках, которые могут быть реализованы рекурсивно и выглядят логически. Например, вот функция, которая вызывает переданную функцию для каждого элемента списка:


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

А вот и ещё одна, которая создает список для промежутка чисел:


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

# выводит квадраты чисел от 1 до 8
foreach(range(1, 8), λ(x) println(x * x));

Списки, которые мы реализовали выше иммутабельны (мы не может изменить car или cdr после того, как список был создан). В большинстве Lisp'ов есть функции, чтобы изменить пару. В Scheme они называются set-car!/set-cdr!. В Common Lisp — rplaca/rplacd. В этот раз мы используем названия из 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);

# теперь NIL может быть обычным объектом
NIL = cons(0, 0);
set-car!(NIL, NIL);
set-cdr!(NIL, NIL);

## примеры:
x = cons(1, 2);
println(car(x)); # 1
println(cdr(x)); # 2
set-car!(x, 10);
set-cdr!(x, 20);
println(car(x)); # 10
println(cdr(x)); # 20

Это показывает, что мы можем реализовать мутабельные структуры данных. Я не буду углубляться в то, как оно работает, это понятно из кода.


Мы можем пойти дальше и реализовать объекты, но без изменений в синтаксисе это будет сложно сделать. Другой выход — реализовать новый синтаксис в токенизаторе/парсере и добавить их оброботку в интерпретаторе. Это делают все основные языки программирования, и это нужно, чтобы добиться нормальной производительности. Мы добавим новый синтаксис в следующей части статьи.


[От переводчика: если Вас заинтересовали лямбда-исчисления, на Хабре есть классная статья, посвящённая данной теме: Лямбда-исчисление на JavaScript.]


Новые синтаксические конструкции


Наш λзык имеет достаточно мало синтаксических конструкций. Например, нет прямого способа добавить новые переменные. Как я раньше говорил, мы обязаны использовать IIFE, поэтому это выглядит примерно так:


(λ(x, y){
  (λ(z){ ## it gets worse when one of the vars depends on another
    print(x + y + z);
  })(x + y);
})(2, 3);

Мы добавим ключевое слово let. Это позволит нам писать примерно так:


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

Для каждой переменной в блоке let, должны быть доступны предыдущие переменные даже из того же блока. Поэтому, код выше будет эквивалентен следующему:


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

Эти изменения могут быть сделаны прямо в парсере и тогда не будут требовать изменений в интерпретаторе. Вместо того, чтобы добавлять новый узел let, мы можем превращать его в узлы call и lambda. Это значит, что мы в нашем языке не делали никаких семантических изменений — это называется "синтаксический сахар", и операция превращения этого в узлы AST, которые существовали раньше, называется "рассахаривание" (оригинал: "desugaring").


Тем не менее, мы должны изменить парсер в любом случае. Давайте добавим новый узел "let" потому, что он может быть интепретирован эффективнее (не нужно создавать замыкания и вызывать их сразу же, нам нужно только скопировать и изменить контекст).


Также, мы добавим поддержку "let с именем", который был в Scheme. Он позволяет легче создавать циклы:


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

Это "рекурсивный" цикл, который считает сумму 10 + 9 +… + 0. Раньше мы должны были бы делать это так:


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

Также, чтобы сделать это проще, мы добавим синтаксис "функций с именем". Это будет выглядеть так:


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

Модификации, которые для этого нужно сделать:


  • Поддержка опционального названия после ключевого слова lambda. Если оно присутствует, то мы должны в текущий контекст добавить переменную, которая будет указывать на саму функцию. Это ровно то же, как работают функции с именем в JavaScript.
  • Поддержка нового ключевого слова let. Дальше идет необязательное название и список (возможно пустой) определений переменных в такой форме: foo = EXPRESSION, разделенных запятыми. Тело выражения let — одно выражение (которое, конечно, может быть последовательностью выражений).

Изменения в парсере


Сначала, маленькое изменение в токенизаторе, добавим ключевое слово let в список ключевых слов:


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

Изменим функцию parse_lambda, чтобы она считывала необязательное название:


function parse_lambda() {
    return {
        type: "lambda",
        name: input.peek().type == "var" ? input.next().value : null, // эта строчка
        vars: delimited("(", ")", ",", parse_varname),
        body: parse_expression()
    };
}

Теперь добавим функцию, которая парсит выражение 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(),
    };
}

Это обрабатывает два случая. Если после let есть токен типа var, то это let с именем. Дальше, мы читаем список определений используя функцию delimited, так как они в скобках и разделены запятыми, и используем функцию parse_vardef, которая показана ниже. Дальше мы возвращаем узел типа call, который сразу вызывает функцию с именем (IIFE). Аргументы функции — переменные, определенные в let, а узел call передаст значения как аргументы. И, конечно, тело функции прочитано используя parse_expression().


Если это простой let, тогда мы возвращаем узел типа let с полями vars и body. Поле vars содержит массив переменных в таком формате: { name: VARIABLE, def: AST }, которые парсятся следующей функцией:


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

Также, нужно добавить проверку на новый тип выражения в функцию parse_atom:


// может быть перед проверкой на parse_if
if (is_kw("let")) return parse_let();

Изменения в интерпретаторе


Так как мы решили изменить структуру AST вместо того, чтобы "рассахаривать" его в старые типы узлов, мы должны добавить обработку новой логики в интерпретатор.


Для того, чтобы добавить поддержку опционального названия функции, мы изменяем функцию make_lambda:


function make_lambda(env, exp) {
    if (exp.name) {                    // эти
        env = env.extend();            // строки
        env.def(exp.name, lambda);     // мы
    }                                  // добавили
    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;
}

Если у функции есть название, то, когда мы создаем замыкание, мы делаем копию контекста, и добавляем функцию в контекст. Остальное остается таким же.


И под конец, чтобы обрабатывать узел типа let, мы добавим следующий case в интерпретатор:


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);

Обратите внимание, для каждой переменной создается новый контекст в который добавляется новая переменная. После этого мы просто исполняем тело в последнем контексте.


Примеры


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);

# бросает ошибку т.к. переменные привязаны к телу let
# print(x + y + z);

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

Производительность интерпретатора


Если коротко — он черепаха.


Но давайте проверим. Мы будем использовать двойную рекурсивную функцию для чисел Фибоначчи, потому, что это не требует много места на стеке и при этом, время выполнения растет экспоненциально аргументу. Мы сравним время выполнения этой функции в JavaScript и в нашем λзыке.


Я добавил такие функции:


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;
});

Функция time принимает функцию, вызывает её и выводит в консоль время, которое потребовалось, чтобы выполнить это функцию.


fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2);

print("fib(10): ");
time( λ() println(fib(10)) );
print("fibJS(10): ");
time( λ() println(fibJS(10)) );

println("---");

На моем компьютере, в браузере Google Chrome, для последнего n (27), наш λзык отрабатывает больше, чем секунду, тогда как JS работает за 4 миллисекунды. Это, конечно, очень плохо.


Мы можем и будем компилировать наш λзык в JavaScript. Чтобы обойти ограничение рекурсии, мы можем добавить ключевые слова for/while; сложные структуры данных и даже исключения могут использоваться из JS. Но зачем тогда мы делали новый язык программирования? В JS есть свои недостатки, да и просто добавлять новый синтаксис нам недостаточно.


Поэтому, мы перед этим создадим интерпретатор в стиле передачи управления, немного поиграем с продолжениями и тогда создадим транспилятор в почти эффективный JavaScript, но с новыми фичами, которых нет в JavaScript.


Мы пробуем создать язык, который лучше, чем базовый. Скорость исполнения важна, но это не главная цель.


Заключение


Эти изменения было сделать не очень сложно, так как мы написали весь код сами. Но что, если бы весь этот код написал кто-то другой; тем более, что если это был бы стандартный язык, который установлен у каждого и он ожидал чтобы программы отвечали конкретному синтаксису? Такой язык — JavaScript. Представьте, если бы вы хотели добавить новую конструкцию в JavaScript — можете ли вы это сделать? Возможно, даже если бы вы предложили это тем, кто поддерживает стандарт JavaScript, прошли бы годы чтобы ваше предложение было рассмотрено, принято, стандартизировано и везде реализовано. В JavaScript мы ограничены синтаксисом (кроме случая, если мы реализуем свой язык поверх него).


Я говорил, что я хотел доказать, что Lisp — великий язык программирования: в нем мы можем добавить новые синтаксические конструкции без изменений реализации парсера/интерпретатора/компилятора. Это делает жизнь проще, не требуя, чтобы эти конструкции были приняты комитетом и т.д. В Lisp мы свободны. Если бы в Lisp не было функций с именем или конструкции let, мы могли бы их добавить используя меньше кода, даже чем нужно было выше и при этом они выглядели бы как обычные конструкции для Lisp.


Следующая часть: Как реализовать язык программирования на JavaScript. Часть 3: CPS-интерпретатор

  • +12
  • 2,5k
  • 8
Поделиться публикацией

Комментарии 8

    0
    Извините, конечно, но Вы не думали реализовать на JavaScript язык программирования идеалогии Форт (Forth) и решило ли бы это какие то Ваши «проблемы»?

    Пример этого подхода:
    A FORTH running on HTA, HTML, Node.js, NW.js, Chrome Extension, Chrome App, and more. Play now:

    P.S. Форт включают и в такие проекты RtForth — Forth implemented in Rust, designed for real-time applications.
    И fibonacci на Forth очень тривиальная и быстрая задача.
      0

      Нет, не думал, тем более, это перевод. Вообще, статья нацелена на понимание устройства языков программирования. Числа Фибоначчи используются чисто для оценки производительности.

      +1
      Спасибо за статью, что бы рекурсия не вызывала «Maximum call stack size exceeded», нужно реализовать хвостовой вызов, он конечно сейчас тоже имеет ограничение на количество вложенных вызовов, но оно намного больше.
        0

        В следующей части статьи это ограничение будет решено (в общем, там глубина рекурсии вообще будет неограниченной).

          0

          P.S. А также в статье будет оптимизация хвостовой рекурсии.

          +1
          В интерпретаторе и компиляторе есть баг: в выражениях типа a() && b() или a() || b() всегда исполняются обе части.

          а разве автор говорил, что логические операторы работают по короткой схеме?

          ЗЫ
          статья отличная
            0

            Спасибо большое! Автор оставил такое на каждой странице, начиная с интерпретатора:

            0

            Циклы через рекурсию, потому что это красиво (на самом деле — нет), мегасвичи, захардкоженные операторы.
            Читатель, смотри, удивляйся, но никогда так не делай в реальных проектах.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое