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

    Если кто-то ещё не знает, что такое хвостовая рекурсия, вот простой пример метода, складывающего в лоб натуральные числа от 1 до n (n≥0):
    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) {...}
    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. Обычно это используется вирусами да обфускаторами, но вероятно, этот инструмент можно использовать и в других целях.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 23

      +10
      Самомодифицирующийся код вообще штука крайне дырявая по своей сути, да и отладчики и анализаторы малость с ума сходят от такого.
        0
        К тому же, он не поддаётся JIT-компиляции, и тратится время на парсинг нового кода. Генерировать код во время загрузки — нормально, генерировать функцию каждую рекурсию — тормоза.
          +1
          Никто и не предлагал генерировать функцию каждый раз :-)
            0
            Код функций, созданных конструктором Function, поддается компиляции.
            +1
            Относитесь к этому, как к макросам на препроцессоре Си. Тоже страшная вещь, из-за которой могут возникнуть трудноотлавливаемые ошибки (да и отладчикам с анализаторами туго), но программисты на Си нередко их используют :-)
            • UFO just landed and posted this here
                0
                Макросами тоже не пользуюсь, практически. Но в макрос хотя-бы не может прилетать рандомный код из интернета.
              0
              Зачем в приведенном примере вообще рекурсия и даже отдельная функция? Всё можно было сделать циклом с аккумулятором. А если рекурсия разветвляющаяся (типа заливки или двоичного дерева), лучше использовать массив-стек.
                0
                Вижу, у кого-то есть противоположное мнение. Не могли бы вы разъяснить?
                  +1
                  Минус я не ставил, но попробую ответить: just for fun
                    +3
                    Статья — о хвостовой рекурсии, а не о подсчете чисел Фибоначчи. Любая рекурсивная функция (из тех, что можно переписать в вид с хвостовой рекурсией) сгодилась бы, но рекурсивный алгоритм подсчета числ Фибоначчи используется здесь (а также во многих других местах) как стандартный пример рекурсии.
                      +3
                      Вероятно, что автор просто не нашел лучше примера, чем просто описать крайне простую операцию через хвостовую рекурсию. Это крайне похоже на пример с факториалом, который считают через рекурсию. (Пример неудачный, я с вами согласен)
                      У меня было другое представление о хвостовой рекурсии (это набросок, подробнее в вики):

                      function A() { /*условия*/ B(); } function B() { /* условия */ A(); }

                      Так почему же несогласны? Автор попытался изложить материал на примере, пускай и неудачном, но за что его так сильно пинать?
                        0
                        Тут дело не в примере. Хвостовая рекурсия всегда может быть записана как цикл с аккумулятором, так что единственное зачем это нужно — just for fun.
                          0
                          Собственно, функция tail2 как раз это и делает — переписывает код с хвостовой рекурсией в код с циклом :-) Разумеется, никто не мешает сразу организовать цикл самому программисту.
                            +3
                            Может-то может. Вот только очень часто запись через рекурсию компактнее и проще для понимания.
                          +4
                          ну это как когда объясняют вычитание на примере «у тебя было 3 яблока, ты отдал одно Васе ...» и тот кому объясняют спрашивает «а почему, собственно, я должен отдавать яблоки Васе?»
                          0
                          Данные функции даны как примеры! Они выполняют свою роль демонстрации метода.
                          +5
                          Для ненормального программирование — вполне сойдёт.
                          Надо только не забыть внутрь текста для eval добавить комментарий, что тут полная жопа и дебажить даже не стоит пытаться.
                            +1
                            Вместо
                            return eval("var $tail$function = function "+name+"("+args.join(",")+") {"+newBody+"};$tail$function");
                            
                            можно обойтись
                            return Function(args.join(','),newBody)
                            

                            А так — довольно интересное решение, жаль контекст объявления функции теряется.
                              0
                              Контекст легко вернуть:

                              var that = this;
                              return function () {
                                  return Function(args.join(','), newBody).call(that);
                              }
                              
                                +2
                                Не о том контексте речь — речь о области видимости переменных, если так понятней.
                                var foo=21;
                                !function(){
                                  var foo=42;
                                  function fn1(){
                                    console.log(foo)}
                                  var src=fn1.toString();
                                  var fn2=Function(src.substring(src.indexOf('{')+1,src.lastIndexOf('}')));
                                  fn1();//=>42
                                  fn2();//=>21
                                  }()
                                
                                С eval'ом примерно та же ситуация, но с другого бока — функция объявляется не в глобальном контексте, а в контексте замыкания Function.prototype.tail.
                              0
                              Клёва. А почему бы подобное не сделать в общем случае? Вроде же, понятно, когда вызов хвостовой в общем случае.
                                0
                                Вы имеете в виду хвостовые вызовы других функций (не себя)? В теле одной функции этого так просто не сделаешь, получится подобие трамплина, который описан по ссылке в статье. Это медленно. Да, можно написать такой препроцессор, который хвостовые вызовы преобразует так, как требуется в этой статье.

                              Only users with full accounts can post comments. Log in, please.