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

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

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

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

Содержание

Как реализовать язык программирования на JavaScript. Часть 1: Парсер
Как реализовать язык программирования на JavaScript. Часть 2: Интерпретатор
Как реализовать язык программирования на JavaScript. Часть 3: CPS-интерпретатор
Как реализовать язык программирования на JavaScript. Часть 4: Транс-компиляция в JS

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

CPS-интерпретатор

У нашего λзыка есть два недостатка:

Рекурсия ограничена стеком JS, так что у нас нет нормального способа сделать циклы.
Интерпретатор медленный, так что рекурсия очень медленная.

Сейчас мы исправим первый недостаток не обращая внимания на то, что интерпретатор станет ещё медленнее. Мы перепишем интерпретатор в стиле передачи продолжения ("continuation-passing style", CPS).

Что такое "передача продолжения"

Вы делаете это в NodeJS все время:

fs.readFile("file.txt", "utf8", function CC(error, data){
  // эта функция - "продолжение"
  // вместо возвращения результата через 'return',
  // 'readFile' вызовет функцию, передав результат.
});

На каждом шаге есть колбек, который будет вызван тогда, когда нужно продолжить. Стиль передачи продолжения делает передачу управления "явной" — вы не используете ни return, ни throw, ни break или continue. Нет никаких неявных переходов в коде. Нельзя даже использовать циклы for или while с асинхронными функциями. В таком случае, зачем они нам вообще в языке программирования?

Писать код в стиле передачи продолжения сложно и легко наделать ошибок, но мы перепишем только интерпретатор в такой стиль.

Функция `evaluate`

Функция evaluate будет получать три аргумента: выражение (AST), контекст (Environment), и функцию, которая будет вызвана когда будет результат. Вот код, к каждому фрагменту есть объяснение:

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

Для констант, мы просто будем возвращать их значение. Но помните, у нас нет return — мы вместо этого просто вызываем колбек и передаем значение.

      case "num":
      case "str":
      case "bool":
        callback(exp.value);
        return;

Узел var тоже простой — получить переменную из контекста и передать её в функцию:

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

Для узлов assign нам нужно получить значение левого выражения (right). Для этого мы вызываем evaluate, передавая функцию, которая получит результат (для правой части выражения). И дальше мы просто вызываем callback со значением переменной, устанавливая переменную в текущем контексте:

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

Почти то же для узлов типа binary, но здесь нам нужно сначала получить значение поля left, и только потом значение поля right. Дальше просто вызываем колбек, передавая результат операции:

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

Узел let выглядит сложнее, но по факту он прост. У нас есть какое-то число переменных. Их поле def (начальное значение) может быть пустым, в этом случае мы установим его в значение false. Но если значение есть, то нам нужно вызвать evaluate рекурсивно, чтобы получить его.

Если вы раньше работали с NodeJS, вы уже делали такое много раз. Из-за колбеков, мы не можем использовать for, поэтому, мы должны интерпретировать эти выражения по очереди (представляйте функцию evaluate как асинхронную). Функция loop ниже (сразу же вызывается) получает контекст и номер определения, которое требуется обработать:

Если этот номер равен количеству переменных (vars.length), то это значит, что мы уже определили все выражения поэтому мы можем исполнять тело выражения. Обратите внимание, в этот раз мы не вызываем callback, а передаем его в evaluate, который потом его вызовет.

Если этот номер меньше, то нужно рассчитать текущее определение и передать функцию, которая вызовет loop(scope, i + 1), перед этим скопировав контекст.

  case "let":
    (function loop(env, i){
        if (i < exp.vars.length) {
            var v = exp.vars[i];
            if (v.def) evaluate(v.def, env, function(value){
                var scope = env.extend();
                scope.def(v.name, value);
                loop(scope, i + 1);
            }); else {
                var scope = env.extend();
                scope.def(v.name, false);
                loop(scope, i + 1);
            }
        } else {
            evaluate(exp.body, env, callback);
        }
    })(env, 0);
    return;

Узел lambda будет обработан в отдельной функции, как и раньше:

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

Для того, чтобы интерпретировать if, мы сначало интерпретируем условие. Если оно не ложное, то интерпретируем выражение then, в другом случае интерпретируем else если есть, или возвращаем false, если нет. Как и раньше, для then и else мы просто передаем callback, как "действие, которое сделать после выполнения" выражения:

      case "if":
        evaluate(exp.cond, env, function(cond){
            if (cond !== false) evaluate(exp.then, env, callback);
            else if (exp.else) evaluate(exp.else, env, callback);
            else callback(false);
        });
        return;

Узел prog интерпретируется подобно узлу let, но с тем отличием, что нам не нужно ни копировать контекст, ни определять переменные. И снова, у нас есть функция loop, принимающая номер выражения. Когда он равен prog.length, то мы выполнили все выражения и мы просто возвращаем результат последнего выражения (под словом "возвращаем" я имею в виду вызываем callback с ним). Обратите внимание, мы запоминаем последнее значение передавая его как аргумент функции loop (в начале равен false на случая, когда тело пустое):

      case "prog":
        (function loop(last, i){
            if (i < exp.prog.length) evaluate(exp.prog[i], env, function(val){
                loop(val, i + 1);
            }); else {
                callback(last);
            }
        })(false, 0);
        return;

Для узла типа call нам нужно интерпретировать func и тогда все аргументы по порядку. И снова, есть функция loop, которая работает тем же принципом, что и в let или prog, с тем отличием, что теперь она строит массив в результате:

      case "call":
        evaluate(exp.func, env, function(func){
            (function loop(args, i){
                if (i < exp.args.length) evaluate(exp.args[i], env, function(arg){
                    args[i + 1] = arg;
                    loop(args, i + 1);
                }); else {
                    func.apply(null, args);
                }
            })([ callback ], 0);
        });
        return;

Ну и стандартная концовка: если не знаем, что делать — бросаем исключение:

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

Вы могли заметить, что каждый case выше заканчивается ключевым словом return. Но при этом нет возвращаемого значения — результат всегда передается в функцию callback.

Новая функция `make_lambda`

В этом интерпретаторе все функции будут получать "продолжение" как первый аргумент — функция, которую мы должны вызвать, чтобы передать результат. После него — обычные аргументы функции. Вот новый код для функции make_lambda:

function make_lambda(env, exp) {
    if (exp.name) {
        env = env.extend();
        env.def(exp.name, lambda);
    }
    function lambda(callback) {
        var names = exp.vars;
        var scope = env.extend();
        for (var i = 0; i < names.length; ++i)
            scope.def(names[i],
                      i + 1 < arguments.length
                        ? arguments[i + 1]
                        : false);
        evaluate(exp.body, scope, callback);
    }
    return lambda;
}

Он не сильно отличается. Он добавляет новые переменные в новый контекст. Также, мы должны учитывать, что первый аргумент — callback. И под конец используется функция evaluate, чтобы выполнить код функции в новом контексте, но, как и раньше, мы передаем callback.

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

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

В этом интерпретаторе нативные функции получают callback как первый аргумент. Мы должны это помнить, когда мы определяем нативные функции. Вот пример кода для нового интерпретатора:

var code = "sum = lambda(x, y) x + y; print(sum(2, 3));";
var ast = parse(TokenStream(InputStream(code)));
var globalEnv = new Environment();

// define the "print" primitive function
globalEnv.def("print", function(callback, txt){
  console.log(txt);
  callback(false); // call the continuation with some return value
                   // if we don't call it, the program would stop
                   // abruptly after a print!
});

// run the evaluator
evaluate(ast, globalEnv, function(result){
  // the result of the entire program is now in "result"
});

Маленький тест

Давайте попробуем посчитать числа Фибоначчи снова:

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

Но, если мы попробуем найти 27-е число, то мы получим переполнение стека. В общем, стек теперь растем намного быстрее, так что получилось, что теперь мы можем считать число Фибоначчи только до 12-го (как минимум в моем браузере). Это не очень хорошо, поэтому нужно как-то это исправить.

Защищаем стек

В CPS-интерпретаторе стек растет намного быстрее потому, что интерпретатор всегда рекурсивно вызывает функции, никогда не возвращая результат. Хоть и у нас есть return в интерпретаторе, они нужны, но в случае очень глубокой рекурсии мы никогда их не достигаем.

Давайте представим, как наш стек выглядит для очень простой программы. Я покажу псевдо-код и я не добавлял env потому, что это здесь не играет никакой роли:

print(1 + 2 * 3);

## стек:
evaluate( print(1 + 2 * 3), K0 )
  evaluate( print, K1 )
    K1(print)  # это 'var', мы получаем её из контекста
      evaluate( 1 + 2 * 3, K2 )
        evaluate( 2 * 3, K3 )
          evaluate( 2, K4 )
            K4(2)  # 2 это константа, мы вызываем продолжение с ней
              evaluate( 3, K5 )  # то же для 3, но мы заходим ещё глубже
                K5(3)
                  K3(6)  # разультат 2*3
                    evaluate( 1, K6 )  # и снова, константа
                      K6(1)
                        K2(7)  # результат 1+2*3
                          print(K0, 7)  # наконец, мы добрались до вызова 'print'
                            K0(false)  # начало программы. 'print' возвращает 'false'.

Только после последнего вызова, длинная последовательность бесполезных return уменьшают стек. Если мы используем столько места на стеке для простой программы, то сложно представить, что будет для fib(13).

Защита стека

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

Давайте представим, что у нас есть функция GUARD, которая может такое делать. Она получает два значения: функция, которую вызвать, и, аргументы, которые ей нужно передать. Она проверяет: если стек слишком глубокий, она очистит стек и вызовет переданную функцию. В другом случае она ничего не делает.

Используя новую функцию, мы перепишем интерпретатор так, как показано ниже. Я не буду комментировать каждый отдельный случай, там код, который описан раньше, но с использованием функции GUARD:

function evaluate(exp, env, callback) {
    GUARD(evaluate, arguments);
    switch (exp.type) {
      case "num":
      case "str":
      case "bool":
        callback(exp.value);
        return;

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

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

      case "binary":
        evaluate(exp.left, env, function CC(left){
            GUARD(CC, arguments);
            evaluate(exp.right, env, function CC(right){
                GUARD(CC, arguments);
                callback(apply_op(exp.operator, left, right));
            });
        });
        return;

      case "let":
        (function loop(env, i){
            GUARD(loop, arguments);
            if (i < exp.vars.length) {
                var v = exp.vars[i];
                if (v.def) evaluate(v.def, env, function CC(value){
                    GUARD(CC, arguments);
                    var scope = env.extend();
                    scope.def(v.name, value);
                    loop(scope, i + 1);
                }); else {
                    var scope = env.extend();
                    scope.def(v.name, false);
                    loop(scope, i + 1);
                }
            } else {
                evaluate(exp.body, env, callback);
            }
        })(env, 0);
        return;

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

      case "if":
        evaluate(exp.cond, env, function CC(cond){
            GUARD(CC, arguments);
            if (cond !== false) evaluate(exp.then, env, callback);
            else if (exp.else) evaluate(exp.else, env, callback);
            else callback(false);
        });
        return;

      case "prog":
        (function loop(last, i){
            GUARD(loop, arguments);
            if (i < exp.prog.length) evaluate(exp.prog[i], env, function CC(val){
                GUARD(CC, arguments);
                loop(val, i + 1);
            }); else {
                callback(last);
            }
        })(false, 0);
        return;

      case "call":
        evaluate(exp.func, env, function CC(func){
            GUARD(CC, arguments);
            (function loop(args, i){
                GUARD(loop, arguments);
                if (i < exp.args.length) evaluate(exp.args[i], env, function CC(arg){
                    GUARD(CC, arguments);
                    args[i + 1] = arg;
                    loop(args, i + 1);
                }); else {
                    func.apply(null, args);
                }
            })([ callback ], 0);
        });
        return;

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

Для анонимных функций нам нужно было добавить название, чтобы мы могли передать их в функцию GUARD. Я использовал название CC (current continuation). Можно было б использовать arguments.callee, но это устаревшее API.

Также, такое же изменение в make_lambda:

function make_lambda(env, exp) {
    if (exp.name) {
        env = env.extend();
        env.def(exp.name, lambda);
    }
    function lambda(callback) {
        GUARD(lambda, arguments);  // <-- здесь
        var names = exp.vars;
        var scope = env.extend();
        for (var i = 0; i < names.length; ++i)
            scope.def(names[i], i + 1 < arguments.length ? arguments[i + 1] : false);
        evaluate(exp.body, scope, callback);
    }
    return lambda;
}

Реализация GUARD очень простая. Как выйти из глубокого вызова? Используя исключения. Для этого будет глобальная переменная, которая будет указывать, сколько ещё нам можно делать рекурсий. Если она достигает нуля, мы бросаем объект Continuation, в котором будет продолжение — функция и аргументы:

var STACKLEN;
function GUARD(f, args) {
    if (--STACKLEN < 0) throw new Continuation(f, args);
}
function Continuation(f, args) {
    this.f = f;
    this.args = args;
}

И в конце концов, нам нужен цикл, который будет ловить объекты Continuation. Мы должны вызывать интерпретатор через этот цикл чтобы все работало:

function Execute(f, args) {
    while (true) try {
        STACKLEN = 200;
        return f.apply(null, args);
    } catch(ex) {
        if (ex instanceof Continuation)
            f = ex.f, args = ex.args;
        else throw ex;
    }
}

Функция Execute принимает функцию, которую нужно вызвать, и аргументы для её. Она работает в цикле, но обратите внимание на return в случае если функция срабатывает без переполнения стека, мы останавливаемся сразу же. STACKLEN сбрасывается каждый раз, когда мы запускаем итерацию цикла. Значение 200 — подходит хорошо. Когда мы ловим объект Continuation, мы подставляем новую функцию и аргументы, и продолжаем цикл. Также, из-за исключения очищается стек, так что мы можем продолжать.

Чтобы запустить интерпретатор, мы теперь используем Execute:

Execute(evaluate, [ ast, globalEnv, function(result){
    console.log("*** Result:", result);
}]);

Тест

Функция fib теперь будет работать:

fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2);
time( λ() println(fib(20)) );  # 6765, ~300ms

Жаль, но если попробовать найти fib(27), то это займет примерно в четыре раза больше времени, чем обычный интерпретатор. Но зато у нас теперь есть бесконечная рекурсия:

sum = λ(n, ret)
        if n == 0 then ret
                  else sum(n - 1, ret + n);

# compute 1 + 2 + ... + 50000
time( λ() println(sum(50000, 0)) );  # 1250025000, ~700ms

Конечно, λзык намного медленнее, чем JavaScript. Просто представьте, каждый доступ к переменной проходи через объект Environment. Нет смысла пробовать оптимизировать интерпретатор — мы не получим значимого прироста производительности. Чтобы улучшить производительность есть одно решение: компилировать λзык в JS, и это то, что мы сделаем. На сначала, давайте посмотрим, что интересного мы можем сделать, имея CPS-интерпретатор.

Продолжения

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

Переменная callback означает продолжение всей программы. Все, что программа сделает дальше. Мы будем называть эту переменную 'текущее продолжение', или k в коде.

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

globalEnv.def("halt", function(k){});

Это функция, которая ничего не делает. Она получает продолжение (k), но не вызывает его:

println("foo");
halt();
println("bar");

Вывод:

foo

Если вы удалите вызов halt(), то вывод будет таким: foo / bar / ***Result: false (потому, что последний println возвращает false). Но с halt() это выводит только foo. *Теперь нет даже результата потому, что halt() не вызывает продолжения и, поэтому, колбек, который мы передали в evaluate — тот, который выводит строку ***Result, никогда не вызывается. Функция, которая вызвала evaluate не замечает, что программа остановилась. В NodeJS это было бы выстрелом себе в ногу.

Представим, нам нужна функция sleepe, которая останавливает программу, не останавливая работу браузера (поэтому, без тупых циклов). Мы можем легко это реализовать используя нативную функцию:

globalEnv.def("sleep", function(k, milliseconds){
  setTimeout(function(){
    Execute(k, [ false ]); // продолжения ожидают значения, передаем 'false'
  }, milliseconds);
});

Небольшое неудобство в том, что мы должны использовать Execute, так как setTimeout вызовет колбек, который потом выбросит Continuation, и его никто не будет ловить. Вот как это можно использовать:

let loop (n = 0) {
  if n < 10 {
    println(n);
    sleep(250);
    loop(n + 1);
  }
};
println("And we're done");

Вывод:

0
1
2
3
4
5
6
7
8
9
And we're done
***Result: false

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

Это уже то, что вы не можете сделать в обычном JavaScript, за исключением использования ручной передачи продолжения (и также, вы не можете для этого использовать цикл for):

(function loop(n){
  if (n < 10) {
    console.log(n);
    setTimeout(function(){
      loop(n + 1);
    }, 250);
  } else {
    println("And we're done"); // продолжение программы здесь
  }
})(0);

Представьте, как можно использовать API NodeJS в λзыке:

globalEnv.def("readFile", function(k, filename){
  fs.readFile(filename, function(err, data){
    // error handling is a bit more complex, ignoring for now
    Execute(k, [ data ]); // hope it's clear why we need the Execute
  });
});
globalEnv.def("writeFile", function(k, filename, data){
  fs.writeFile(filename, data, function(err){
    Execute(k, [ false ]);
  });
});

Использование:

copyFile = λ(source, dest) {
  writeFile(dest, readFile(source));
};
copyFile("foo.txt", "bar.txt");

И все это работает асинхронно. Больше нет "callback hell".

А вот и более интересный пример. Я написал следующую нативную функцию:

globalEnv.def("twice", function(k, a, b){
  k(a);
  k(b);
});

Программа берет два аргумента a и b и вызывает продолжение дважды, по разу для каждого аргумента. Давайте попробуем её вызвать:

println(2 + twice(3, 4));
println("Done");

Вывод:

5
Done
***Result: false
6
Done
***Result: false

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

Обобщение: `CallCC`

Раньше мы играли с огнем, когда писали нативные функции. В λзыке нет способа прервать исполнение текущего продолжения. Функция CallCC поможет решить эту проблему. Название — аббривиатура функции из Scheme — call-with-current-continuation (который обычно называют call/cc в Scheme).

globalEnv.def("CallCC", function(k, f){
    f(k, function CC(discarded, ret){
        k(ret);
    });
});

Она рефицирует (reifies) текущее продолжение в функцию, которая может быть вызвана прямо из λзыка. Эта функция будет игнорировать свое оригинальное продолжение (discarded) и вместо этого будет вызывать продолжение, которое было передано в функцию CallCC.

Используя эту функцию мы можем реализовать (уже прямо в λзыке, не через нативные функции!) большой набор операторов контроля потока выполнения, о которых мы раньше даже и не думали — начиная от исключений, заканчивая return. Давайте начнем из последнего.

Реализация `return`

foo = λ(return){
  println("foo");
  return("DONE");
  println("bar");
};
CallCC(foo);

Вывод:

foo
***Result: DONE

Функция foo получает аргумент, который делает то же, что и return из JavaScript (но вызывается как обычная функция). Она пропускает текущее продолжение (которое вывело бы 'bar') и выходит из функции, возвращая заданное значение ("DONE"). Конечно, это работает только, если вызывать функцию используя CallCC, чтобы передать продолжение как return. Мы можем создать обертку для этого:

with-return = λ(f) λ() CallCC(f);

foo = with-return(λ(return){
  println("foo");
  return("DONE");
  println("bar");
});

foo();

Вывод:

foo
***Result: DONE

Достоинство этого способа в том, что нам больше не нужно использовать CallCC когда мы вызываем foo. Было бы хорошо, конечно, если бы нам не нужно было принимать return как аргумент или использовать функцию with-return, но в λзыке нет возможности добавлять синтаксический сахар прямо из него, для этого нужно хотя бы модифицировать парсер (+1 для Lisp).

Переходы

Например, нам нужно написать программу, которая будет искать все пары целых положительных чисел до 100 таких, что если их умножение дает 84. Это не сложная задача и вы могли сразу представить два вложенных цикла, чтобы её решить, но здесь мы пойдем другим путем. Мы создадим две функции: guess и fail. Первая будет подбирать число, а вторая говорит ей "попробуй другое число". Мы будем использовать их так:

a = guess(1);  # возвращает какое-то число >= 1
b = guess(a);  # возвращает какое-то число >= a
if a * b == 84 {
  # у нас есть ответ:
  print(a); print(" x "); println(b);
};
fail();  # вернуться к последнему `guess` и попробовать другое значение

Весь код:

fail = λ() false;
guess = λ(current) {
  CallCC(λ(k){
    let (prevFail = fail) {
      fail = λ(){
        current = current + 1;
        if current > 100 {
          fail = prevFail;
          fail();
        } else {
          k(current);
        };
      };
      k(current);
    };
  });
};

a = guess(1);
b = guess(a);
if a * b == 84 {
  print(a); print(" x "); println(b);
};
fail();

Мы можем проделать следующие оптимизации, обратив внимание, что нет смысла продолжать когда a больше, чем корень числа 84, или когда b больше, чем 84 / a. Чтобы это сделать мы можем добавить два аргумента для функции guess: start и end — подбирать числа только в этом промежутке. Но оставим это, поехали дальше.

`try` и `catch` из Common Lisp

Мы добавим две конструкции — catch и throw. Мы можем использовать их так:

f1 = λ() {
  throw("foo", "EXIT");
  print("not reached");
};
println(catch("foo", λ() {
  f1();
  print("not reached");
}));  # выводит EXIT

Функция catch(TAG, function) добавит обработчик, который будет ловить исключения, помеченные TAG'ом, брошенные из function.
Функция throw(TAG, value) выбросит исключение, которое словит ближайший обработчик исключений, помеченных TAG'ом и сделает, чтобы обработчик вернул значение value.

Вот реализация:

## без обработчиков, 'throw' просто выводит ошибку.
## лучше было б реализовать нативную функцию `error`,
## которая будет бросать исключение JavaScript. но я пропущу это.
throw = λ(){
  println("ERROR: No more catch handlers!");
  halt();
};

catch = λ(tag, func){
  CallCC(λ(k){
    let (rethrow = throw, ret) {
      ## установить новый обработчик, который будет ловить заданные исключения.
      throw = λ(t, val) {
        throw = rethrow;  # в любом случае, вернуть старый обработчик.
        if t == tag then k(val)
                    else throw(t, val);
      };
      ## теперь вызвать функцию и сохранить результат.
      ret = func();
      ## если наша функция вернула результат нормально (не через 'throw')
      ## то мы попадем сюда.  возвратить старый обработчик.
      throw = rethrow; # XXX
      ## возвратить результат.
      ret;
    };
  });
};

Пример:

# ...

f1 = λ() {
  throw("foo", "EXIT");
  print("not reached");
};
println(catch("foo", λ() {
  f1();
  print("not reached");
}));

Темная сторона силы

Когда я описывал catch выше, я обратив внимание на то, что обработчик удаляется вручную, когда функция заканчивает выполнение. Это выглядит понятным, если посмотреть на код, но, используя CallCC мы можем обойти то место. С точки зрения философии, здесь есть две точки зрения. Я полностью за "Силу в руки людей" — разрешать людям расширять язык программирования — неплохая идея. Но в данном случае, я думаю, эта возможность играет злую шутку, когда catch/throw не будут работать так, как надо.

Все испортить очень просто. Вы вызываете продолжение, которое находится извне catch. Тогда, предыдущий обработчик throw не будет удален, потому, что catch даже не узнает, что вы уже покинули блок. Например:

exit = false;  # глобальная переменная.
x = 0; # защита: не зацикливаться бесконечно, когда вызываем 'exit()' ниже
CallCC( λ(k) exit = k );
## 'exit()' начнет заново здесь...
if x == 0 then catch("foo", λ(){
  println("in catch");
  x = 1; # защита
  exit();
});
println("After catch");
throw("foo", "FOO");

Вывод:

After catch
After catch
ERROR: No more catch handlers!

Код выше вывел 'After catch' дважды, а потом 'ERROR: No more catch handlers!'. По-правильному было бы, чтобы вывело 'After catch' только один раз, а потом ошибку. Но, мы 'выпрыгнули' из функции, пропустив catch. Строка, которую мы обозначили 'XXX' в определении catch никогда не выполняется, поэтому старый обработчик ошибки не восстанавливается и вызов throw, вызванный извне catch просто прыгнет назад.

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

Это один из многих аргументов против CallCC (точнее, против не разделенных продолжений, как в CallCC). Я верю, что лучшее решение — оставить CallCC на низком уровне и не разрешать использовать его в обычном коде.

Yield

Сначала, давайте посмотрим на примерах, что такое yield:

foo = with-yield(λ(yield){
  yield(1);
  yield(2);
  yield(3);
  "DONE";
});

println(foo());  # 1
println(foo());  # 2
println(foo());  # 3
println(foo());  # DONE

Когда вызвать с yield, он прерывает выполнение функции и возвращает значение. Почти так, как return. Но когда вы вызываете функцию снова, функция продолжает работу функции после того места, где был последний yield, как вы можете видеть в предыдущем примере.

Практический пример:

fib = with-yield(λ(yield){
  let loop (a = 1, b = 1) {
    yield(b);
    loop(b, a + b);
  };
});

## вывести первые 50 чисел Фибоначчи
let loop (i = 0) {
  if i < 50 {
    println(fib());
    loop(i + 1);
  };
};

Функция fib содержит бесконечный цикл. Здесь нет точки останова. Но yield прерывает цикл и возвращает текущее число. Если вызвать функцию ещё раз, она продолжит исполнение там, где она была прервана поэтому чтобы вывести первые 50 чисел Фибоначчи, мы должны просто вызвать её 50 раз.

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

Неудачная попытка реализации

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

Чтобы реализовать yield, может показаться, что нам нужно сохранять начальное продолжение функции. Нам это нужно, чтобы мы могли раньше выйти из функции так, как мы делали это с return. Но, перед тем, как выйти из yield, мы также должны сохранить продолжение самого yield, чтобы мы могли позже вернуться в ту точку внутри функции. Это так кажется, по крайней мере. Мы можем попробовать реализовать это так:

with-yield = λ(func) {
  ## with-yield возвращает функцию без аргументов
  λ() {
    CallCC(λ(kret){        # kret это продолжение для возврата
      let (yield) {

        ## определить yield
        yield = λ(value) { # yield принимает значение, чтобы вернуть его
          CallCC(λ(kyld){  # kyld это продолжение для yield...
            func = kyld;   # ...сохраним его для дальнейшего использования
            kret(value);   # и вернемся.
          });
        };

        ## и, наконец, вызываем функцию, передав ей yield.
        func(yield);
      };
    });
  };
};

Это была моя первая попытка реализовать yield и казалось, что она должна была работать. Но, если мы попробуем запустить первый пример с этой реализацией, то мы получим бесконечный цикл, который будет просто выводить всегда "DONE".

Причина, почему так происходит достаточно интересная. Но для начала, если вы хотите увидеть что-то интересное, попробуйте запустить тот же код, но замените последние 4 строки на это:

println(foo());
foo();

Вывод будет таким же.

Проблема №1: yield никогда не изменяется

Первая проблема, которую можно заметить, это то, что первое продолжение, которое мы сохраняем для yield (kyld, которое становится следующей функцией, которую мы вызываем) есть в таком коде:

  yield(2);
  yield(3);
  "DONE";

Но что такое yield в этом продолжении? Это тот же первый yield, которые по сути возвращает к первому продолжению, которое снова вызывает yield и весь код зацикливает. Хорошо, что это легко исправить. По сути, мы должны создать функцию yield один раз и у нас будет переменная return, которая будет указывать на следующее продолжение:

with-yield = λ(func) {
  let (return, yield) {
    yield = λ(value) {
      CallCC(λ(kyld){
        func = kyld;
        return(value);       # 'return' установлен ниже, при каждом вызове функции
      });                    # он всегда указывает на следующую точку для возврата.
    };                       #
    λ(val) {                 #
      CallCC(λ(kret){        #
        return = kret;       # <- здесь
        func(val || yield);
      });
    };
  };
};

Также, можно заметить, что достаточно только первый раз передать yield в функцию, новая версия yield позволяет каждый раз передавать новое значение (кроме первого раза). Это будет возвращаемым значением самого yield.

Вот пример кода, который базируется на предыдущем, но в нем println(foo()) только три раза:

with-yield = λ(func) {
  let (return, yield) {
    yield = λ(value) {
      CallCC(λ(kyld){
        func = kyld;
        return(value);
      });
    };
    λ(val) {
      CallCC(λ(kret){
        return = kret;
        func(val || yield);
      });
    };
  };
};

foo = with-yield(λ(yield){
  yield(1);
  yield(2);
  yield(3);
  "DONE";
});

println(foo());
println(foo());
println(foo());

Кажется, этот код работает нормально. Это уже лучше по сравнению с первой версией, которая зацикливалась на коде типа print(foo()); foo(). Но что случится, если мы добавим ещё println(foo())? Он снова зациклится...

Проблема №2: WTF?

Причина зацикливания находится немного глубже. Она основана на природе продолжений: в них находится все, что будет происходить дальше включая возвращение результата из функции foo(). Что случается, когда мы возвращаемся из её? — мы начинаем все сначала.

println(foo()); ## yield 1 <----------------- СЮДА ---------------------------+
println(foo()); ## yield 2                                                    |
println(foo()); ## yield 3                                                    |
println(foo()); ## мы достигли "DONE", поэтому первый foo() ВОЗВРАЩАЕТСЯ -->--+

Давайте посмотрим на эту строчку из with-yield:

        func(val || yield);
        #...

Когда функция прерывается вызовом yield, она вызывает продолжение, поэтому выполнение не доходит до строки #.... Но к времени, когда оно дойдет, функция завершит своё выполнение (строка "DONE"), то функция превратится в функцию, возвращающую всегда "DONE" в то место, где она была впервые вызвана. foo() на второй строке просто зацикливается, но все эти "DONE" выводятся первой строкой. Вы можете проверить это таким кодом:

println(foo());
println("bar");
println(foo());
println(foo());
foo();

Вывод будет таким: 1, bar, 2, 3, DONE, bar, DONE, bar, ....

Возможным исправлением будет простая установка func в что-то другое, что возвращает обычным способом. Мы используем функцию, которая просто возвращает "no more continuations":

        val = func(val || yield);
        func = λ() "NO MORE CONTINUATIONS";
        kret(val);

Если попробовать запустить код ниже:

with-yield = λ(func) {
  let (return, yield) {
    yield = λ(value) {
      CallCC(λ(kyld){
        func = kyld;
        return(value);
      });
    };
    λ(val) {
      CallCC(λ(kret){
        return = kret;
        val = func(val || yield);
        func = λ() "NO MORE CONTINUATIONS";
        kret(val);
      });
    };
  };
};

foo = with-yield(λ(yield){
  yield(1);
  yield(2);
  yield(3);
  "DONE";
});

println(foo());
println(foo());
println(foo());
println(foo());

То он больше не будет зацикливаться, но вы будете удивлены выводом:

1
2
3
DONE
NO MORE CONTINUATIONS
NO MORE CONTINUATIONS
NO MORE CONTINUATIONS
***Result: false

Мы ожидали получить 1, 2, 3, DONE, но мы получаем ещё и "NO MORE CONTINUATIONS" три раза. Чтобы понять, что происходит можно попробовать запустить такой код:

print("A. "); println(foo());
print("B. "); println(foo());
print("C. "); println(foo());
print("D. "); println(foo());

## вывод будет таким:
A. 1
B. 2
C. 3
D. DONE
B. NO MORE CONTINUATIONS
C. NO MORE CONTINUATIONS
D. NO MORE CONTINUATIONS
***Result: false

Можно заметить, что ещё одна проблема осталась: функция все ещё возвращается к первому продолжению, но, потому, что функция больше ничего не делает, строка "B." больше не зацикливает.

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

with-yield = λ(func) {
  let (return, yield) {
    yield = λ(value) {
      CallCC(λ(kyld){
        func = kyld;
        return(value);
      });
    };
    λ(val) {
      CallCC(λ(kret){
        return = kret;
        val = func(val || yield);
        func = λ() "NO MORE CONTINUATIONS";
        kret(val);
      });
    };
  };
};

fib = with-yield(λ(yield){
  let loop (a = 1, b = 1) {
    yield(b);
    loop(b, a + b);
  };
});

## вывести первых 50 чисел Фибоначчи
let loop (i = 0) {
  if i < 50 {
    println(fib());
    loop(i + 1);
  };
};

Вывод

1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
***Result: false

Но, если нам нужна нормальная реализация (такая, что не возвращается в место первого вызова), нам нужен новый концепт под названием "отделенные продолжения".

Отделенные продолжения: `reset` и `shift`

Мы собираемся реализовать yield в рамках двух операторов: reset и shift. Они дают "отделенные продолжения" — те, что возвращают как обычные функции. Функция reset создает фрейм, а функция shift продолжает выполнение на один фрейм, вместо использования CallCC.

Обе функции, reset и shift принимают один аргумент — функция. Во время выполнения функции reset, вызов shift позволит нам вернуть значение в место, где был вызов reset.

Давайте посмотрим, как будет выглядеть with-yield:

with-yield = λ(func) {
  let (yield) {
    ## 'yield' использует 'shift' чтобы вернуть значение ближайший
    ## вызов 'reset'. Перед тем, как сделать это, функция сохраняет своё
    ## продолжение в 'func' — поэтому, повторный вызов `func()`
    ## продолжит с того места, где она была остановлена.
    yield = λ(val) {
      shift(λ(k){
        func = k;  # сохранить следующее продолжение
        val;       # вернуть текущее значение
      });
    };
    ## из `with-yield` мы возвращаем функцию без аргументов
    ## которая использует 'reset', чтобы вызвать обычную функцию, передавая
    ## ей функцию 'yield' (в начале) или любое значение
    ## для последующих вызовов
    λ(val) {
      reset( λ() func(val || yield) );
    };
  }
};

Обратите внимание, каждый вызов функции находится в reset. Это нужно, чтобы убедится, что мы не перекрываем все продолжение программы, а только часть до reset. По определению, оно не должно зацикливаться. Когда функция возвращает обычным способом, программа просто продолжит исполнение вместо перехода в место первого вызова функции.

Данная программа работает как нужно:

with-yield = λ(func) {
  let (yield) {
    yield = λ(val) {
      shift(λ(k){
        func = k;
        val;
      });
    };
    λ(val) {
      reset( λ() func(val || yield) );
    };
  }
};

foo = with-yield(λ(yield){
  yield(1);
  yield(2);
  yield(3);
  "DONE";
});

println(foo());  # выводит 1
println(foo());  # выводит 2
println(foo());  # выводит 3
println(foo());  # выводит DONE

Реализация `reset` и `shift`

С реализацией данных операторов могут возникнуть сложности, хотя кода для них нужно немного. Будьте готовы к сложностям. Я покажу вам две реализации. Я не автор данного метода, и я могу вам сказать, что я много думал над ним перед тем, как их реализовать. Я нашел эту программу на Scheme (автор — Oleg Kiselyov). Я рекомендую эти статьи чтобы лучше понять этот концепт.

Используя нативные функции

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

var pstack = [];

function _goto(f) {
    f(function KGOTO(r){
        var h = pstack.pop();
        h(r);
    });
}

globalEnv.def("reset", function(KRESET, th){
    pstack.push(KRESET);
    _goto(th);
});

globalEnv.def("shift", function(KSHIFT, f){
    _goto(function(KGOTO){
        f(KGOTO, function SK(k1, v){
            pstack.push(k1);
            KSHIFT(v);
        });
    });
});

Суть в том, что как reset, так и shift используют _goto, который — необычная функция. У неё нет своего продолжения. Функция _goto получает обычную функцию и вызывает её с продолжением (KGOTO). Любые продолжения, каторые были пойманы во время выполнения f (даже через CallCC) могут только делать что-то с продолжениями только до этого KGOTO, так как дальше ничего нет. Без разницы, возвращает f нормально, или вызывая продолжение, она всеравно вызовет KGOTO, который берет следующее продолжение из стека, и вызывает его на результате.

Функция reset добавляет своё продолжение в стек (KRESET) в стек перед вызовом _goto(th). Если бы она не сделала этого, программа закончила бы работу, потому, что ничего не происходит после _goto. Поэтому, когда функция возвращает любым способом, KGOTO перейдет в KRESET.

И в конец, shift вызывает функцию с продолжением KGOTO поэтому если она возвращает нормально, то KGOTO продолжит из вершины pstack, и передает его в функцию SK, которая может вернуть в точку, где сам shift был вызван (используя продолжение самого shift — KSHIFT). Функция SK — отделенное продолжение — оно может возвратить значение как обычная функция поэтому мы должны добавить её продолжение (k1) в стек тоже. Чтобы показать различие, я добавил ещё функцию shift2, которая работает так же, но без строки pstack.push(k1);:

println(reset(λ(){
    1 + shift( λ(k) k(k(2)) );
}));

println(reset(λ(){
    1 + shift2( λ(k) k(k(2)) );
}));

Вывод:

4
3
***Result: false

Функция shift дает нам продолжение (k), которое является отделенным продолжением до конца reset. В этом случае продолжение — добавить 1 к результату shift:

1 + [?]

Когда мы вызываем k, мы заменяем ? значением. Мы вызываем её дважды — k(k(2)). Мы передаем 2 и продолжаем программу, поэтому внутренний k(2) вернет 3. Поэтому, следующий k(3) передает 3 в место с вопросительным знаком, поэтому конечным результатом будет 4.

shift2 работает неправильно: внутренний k(2) никогда не возвращает результат.

Используя `CallCC`

Как говорили выше, если мы не хотим использовать нативные функции, мы можем использовать только CallCC, чтобы реализовать отделенные продолжения. Код ниже делает то же, что и версия на JS, но, так как у нас нет массивов, мы используем списки для работы со стеком. Код немного длиннее потому, что нам нужны CallCC, чтобы получить текущее продолжение.

Самая интересная часть этого кода — как мы реализовали goto, и почему мы сделали это так (но попробуйте это понять сами):

pstack = NIL;

goto = false;

reset = λ(th) {
  CallCC(λ(k){
    pstack = cons(k, pstack);
    goto(th);
  });
};

shift = λ(f) {
  CallCC(λ(k){
    goto(λ(){
      f(λ(v){
        CallCC(λ(k1){
          pstack = cons(k1, pstack);
          k(v);
        });
      });
    });
  });
};

let (v = CallCC( λ(k){ goto = k; k(false) } )) {
  if v then let (r = v(), h = car(pstack)) {
    pstack = cdr(pstack);
    h(r);
  }
};

В следующей части статьи мы начнем работать над компилятором — теперь наш код будет работать ещё и быстро!

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