Хабрахабр

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

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

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

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

Содержание

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

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

  • Рекурсия ограничена стеком 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;

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

case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); evaluate(exp.right, env, function(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 выглядит сложнее, но по факту он прост. Но если значение есть, то нам нужно вызвать evaluate рекурсивно, чтобы получить его. Их поле def (начальное значение) может быть пустым, в этом случае мы установим его в значение false.

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

Если оно не ложное, то интерпретируем выражение then, в другом случае интерпретируем else если есть, или возвращаем false, если нет. Для того, чтобы интерпретировать if, мы сначало интерпретируем условие. Как и раньше, для 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;

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

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;

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

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

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

Новая функция 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;
}

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

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

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

Мы должны это помнить, когда мы определяем нативные функции. В этом интерпретаторе нативные функции получают 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)) );

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

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

Я покажу псевдо-код и я не добавлял 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'.

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

Защита стека

Все, что нужно сделать после какого-то выражения, происходит в 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); }
}

Я использовал название CC (current continuation). Для анонимных функций нам нужно было добавить название, чтобы мы могли передать их в функцию GUARD. Можно было б использовать 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; }
}

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

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

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

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

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

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

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

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

Вывод:

foo

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

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

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

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

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

Реализация return

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

Вывод:

foo
***Result: DONE

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

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

Вывод:

foo
***Result: DONE

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

Переходы

Это не сложная задача и вы могли сразу представить два вложенных цикла, чтобы её решить, но здесь мы пойдем другим путем. Например, нам нужно написать программу, которая будет искать все пары целых положительных чисел до 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();

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

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

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

Это выглядит понятным, если посмотреть на код, но, используя CallCC мы можем обойти то место. Когда я описывал catch выше, я обратив внимание на то, что обработчик удаляется вручную, когда функция заканчивает выполнение. Я полностью за "Силу в руки людей" — разрешать людям расширять язык программирования — неплохая идея. С точки зрения философии, здесь есть две точки зрения. Но в данном случае, я думаю, эта возможность играет злую шутку, когда 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' только один раз, а потом ошибку. Код выше вывел 'After catch' дважды, а потом 'ERROR: No more catch handlers!'. Строка, которую мы обозначили 'XXX' в определении catch никогда не выполняется, поэтому старый обработчик ошибки не восстанавливается и вызов throw, вызванный извне catch просто прыгнет назад. Но, мы 'выпрыгнули' из функции, пропустив catch.

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

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

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

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

Почти так, как return. Когда вызвать с yield, он прерывает выполнение функции и возвращает значение. Но когда вы вызываете функцию снова, функция продолжает работу функции после того места, где был последний 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 содержит бесконечный цикл. Если вызвать функцию ещё раз, она продолжит исполнение там, где она была прервана поэтому чтобы вывести первые 50 чисел Фибоначчи, мы должны просто вызвать её 50 раз. Но yield прерывает цикл и возвращает текущее число.

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

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

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

Нам это нужно, чтобы мы могли раньше выйти из функции так, как мы делали это с return. Чтобы реализовать yield, может показаться, что нам нужно сохранять начальное продолжение функции. Это так кажется, по крайней мере. Но, перед тем, как выйти из 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); }; }); };
};

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

Но для начала, если вы хотите увидеть что-то интересное, попробуйте запустить тот же код, но замените последние 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); #...

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

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

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

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

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. Обе функции, reset и shift принимают один аргумент — функция.

Давайте посмотрим, как будет выглядеть 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, который — необычная функция. Любые продолжения, каторые были пойманы во время выполнения f (даже через CallCC) могут только делать что-то с продолжениями только до этого KGOTO, так как дальше ничего нет. Функция _goto получает обычную функцию и вызывает её с продолжением (KGOTO). Без разницы, возвращает f нормально, или вызывая продолжение, она всеравно вызовет KGOTO, который берет следующее продолжение из стека, и вызывает его на результате.

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

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

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

Вывод:

4
3
***Result: false

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

1 + [?]

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

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

Используя CallCC

Код ниже делает то же, что и версия на JS, но, так как у нас нет массивов, мы используем списки для работы со стеком. Как говорили выше, если мы не хотим использовать нативные функции, мы можем использовать только CallCC, чтобы реализовать отделенные продолжения. Код немного длиннее потому, что нам нужны 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); }
};

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть