Эмуляция хвостовой рекурсии в JavaScript

function add(n,acc) {   if(n===0) return acc;   return add(n-1,acc+n); }

Изначально функция вызывается с параметром acc=0. В случае, если n не равно нулю, метод вызывает сам себя с другими параметрами и возвращает результат. Компилятор (или интерпретатор, или виртуальная машина) могут понять, что текущий вызов функции в стеке уже не нужен, стереть его и заменить следующим вызовом. Таким образом, рекурсия не приводит к разрастанию стека. Строго говоря, хвостовой вызов не обязан обращаться к текущей функции: вызов любой другой тоже может быть хвостовым. Главное условие: вызов функции и возврат её результата должны быть последними действиями в текущей функции. К примеру, в такой реализации метода хвостовой рекурсии нет, так как после вызова происходит ещё сложение:

function add(n) {   if(n===0) return 0;   return n+add(n-1); }

По ряду причин хвостовая рекурсия в JavaScript не поддерживается (обсуждение на эту тему есть на StackOverflow). Поэтому вызов вроде add(100000,0) завершится исключением. На Хабре предпринимались попытки решить эту проблему через setTimeout, но это выглядит не очень честно и не очень красиво. Более изящное решение для языка Python было предложено с использованием «трамплина». Похожий подход для JavaScript рассмотрен здесь. Но мне захотелось, чтобы работало быстро и чтобы функцию можно было записать прямо как в примере выше. Посмотрим, что можно сделать.

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

$tail$label:while(true) {    <основное тело>;    return; }

Тогда перейти на начало функции можно с помощью continue $tail$label. Как же заменить вызов функции на такой переход? Лёгкий способ, который пришёл на ум, — подменить функцию другой, которая кидает исключение. Тогда можно его поймать и переписать параметры. Выглядеть это будет примерно так:

function add(n,acc) {   function add() {throw arguments;}   while(true) {     try {       if(n===0) return acc;       return add(n-1,acc+n);     }     catch($tail$ex) {       n = $tail$ex[0];       acc = $tail$ex[1];     }   } }

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

Но такое писать каждый раз не хотелось бы, задача-то была писать просто. Как же переделать простую функцию в такую? Декомпилируем исходный текст функции (с помощью toString), подправим её и скомпилируем назад с помощью eval примерно так:

Function.prototype.tail = function() {   var funcStr = Object.toString.apply(this);   var paramsPos = funcStr.indexOf('(');   var paramsEndPos = funcStr.indexOf(')');   var bodyPos = funcStr.indexOf('{');   var bodyEndPos = funcStr.lastIndexOf('}');   var name = funcStr.substring("function".length, paramsPos).replace(/\s*/g, "");   var args = funcStr.substring(paramsPos+1, paramsEndPos).replace(/\s*/g, "").split(",");   var body = funcStr.substring(bodyPos+1, bodyEndPos);   var paramPassString = "";   for(var i=0; i<args.length; i++)     paramPassString += args[i]+"=$tail$ex["+i+"];";   var newBody = "function "+name+"() {throw arguments;} while(true) {try{"+body+     "return;}catch($tail$ex) {"+paramPassString+"}}";   return eval("var $tail$function = function "+name+"("+args.join(",")+") {\n"+     newBody+"};$tail$function"); }

Сперва в исходном тексте функции ищется её имя, аргументы и тело. Затем перед телом и после него генерируются дополнительные строчки, после чего всё собирается назад в функцию. У такого подхода следующие ограничения:

• Функция должна иметь имя;
• Функция должна вызывать саму себя исключительно хвостовым способом;
• Вызов самой себя не должен находиться в try-catch блоке (в принципе, это следует из предыдущего).

Таким образом в то время как add(100000,0) падает, add.tail()(100000,0) прекрасно всё считает.

Но какова цена такого решения? Для удобства профилирования добавим в прототип Function вспомогательную функцию time:

Function.prototype.time = function(n) {   var start = new Date();   var result;   var error;   for(var i=0; i<n; i++) {     try {       result = this();     }     catch(ex) {       error = ex;     }   }   var time = new Date()-start;   var funcStr = Object.toString.apply(this);   var bodyPos = funcStr.indexOf('{');   var bodyEndPos = funcStr.lastIndexOf('}');   var body = funcStr.substring(bodyPos+1, bodyEndPos).replace(/^\s*/, "").replace(/\s*$/, "");   if(error)     console.log("Code: "+body+"; error: "+error+"; time="+time/n);   else     console.log("Code: "+body+"; result: "+result+"; time="+time/n); }

Функция в качестве аргумента принимает количество запусков и усредняет время. Добавим таких тестов:

var addTail = add.tail(); (function() {return add(10000,0)}).time(500); (function() {return add(100000,0)}).time(500); (function() {return addTail(10000,0)}).time(500); (function() {return addTail(100000,0)}).time(500);

Теперь запустим всё это добро в Google Chrome 25 и увидим разочаровывающий результат:

Code: return add(10000,0); result: 50005000; time=0.102 Code: return add(100000,0); error: RangeError: Maximum call stack size exceeded; time=0.162 Code: return addTail(10000,0); result: 50005000; time=2.392 Code: return addTail(100000,0); result: 5000050000; time=24.826 

Хотя мы теперь не ограничены числом итераций, но снижение производительности в 24 раза не может порадовать. Что можно сделать ещё?

Чтобы обойтись без очевидно медленных вещей (исключения и обращений arguments), придётся залезть в само тело функции, которую мы меняем. Здесь, конечно, в идеале следует написать парсер JavaScript (можно на базе jslint.js). Но для иллюстрации мысли пойдут и регулярные выражения, хоть они и потребуют кода в определённом формате.

Function.prototype.tail2 = function() {   var funcStr = Object.toString.apply(this);   var paramsPos = funcStr.indexOf('(');   var paramsEndPos = funcStr.indexOf(')');   var bodyPos = funcStr.indexOf('{');   var bodyEndPos = funcStr.lastIndexOf('}');   var name = funcStr.substring("function".length, paramsPos).replace(/\s*/g, "");   var args = funcStr.substring(paramsPos+1, paramsEndPos).replace(/\s*/g, "").split(",");   var body = funcStr.substring(bodyPos+1, bodyEndPos);   body = body.replace(new RegExp("return\\s+"+name+"\\s*\\((.+?)\\);", "g"),     function(match,argsStr) {       var passArgs = argsStr.split(",");       var result = "";       for(var i=0; i<args.length; i++)         result+="var $tail$arg"+i+"="+passArgs[i]+";"       for(var i=0; i<args.length; i++)         result+=args[i]+"="+"$tail$arg"+i+";"       return "{"+result+"continue $tail$label;}";     });   var newBody = "$tail$label:while(true) {"+body+"return;}";   return eval("var $tail$function = function "+name+"("+args.join(",")+") {"+newBody+"};$tail$function"); }

Здесь мы каждое вхождение строки вида return <имя функции>(val1, val2, ..., valN) превращаем в блок, где через промежуточные переменные присваиваем новые значения аргументам, а затем вызываем continue. Сразу оговорюсь, что код очень наивный и легко сломается, если у вас есть дополнительные скобки или, к примеру, оператор ?: в выражении return.

Протестируем:

var addTail2 = add.tail2(); (function() {return addTail2(10000,0)}).time(500); (function() {return addTail2(100000,0)}).time(500);

Результаты впечатляют:

Code: return addTail2(10000,0); result: 50005000; time=0.022 Code: return addTail2(100000,0); result: 5000050000; time=0.222

Стало даже быстрее оригинала! Конечно, сейчас мы экономим на вызовах функций.

Что бы ещё протестировать? Возьмём оригинальную функцию для нахождения чисел Фибоначчи из вышеупомянутой статьи:

function cpsFib(n, prev, cur, _return) {     if (n < 2) {         return _return(cur);     }     return cpsFib(--n, cur, cur + prev, _return); }  function identity(x) {return x}  var cpsFibTail = cpsFib.tail(); var cpsFibTail2 = cpsFib.tail2(); (function() {return cpsFib(1300, 0, 1, identity)}).time(5000); (function() {return cpsFibTail(1300, 0, 1, identity)}).time(5000); (function() {return cpsFibTail2(1300, 0, 1, identity)}).time(5000);

Результаты:

Code: return cpsFib(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.0222 Code: return cpsFibTail(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.3436 Code: return cpsFibTail2(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.0036

Если же взять реализацию из статьи, то получится так:

Code: return cpsFib.tco(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.187

Побыстрее, чем наш вариант с исключениями, но всё же в 8 раз медленнее обычной рекурсивной формы и в 52 раза медленнее нашей оптимизированной.

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