Страницы

вторник, 9 августа 2016 г.

JavaScript trampolining

Самой ожидаемой фичей ES6 для меня остается proper tail calls (уже рассказывал об этом), которая на сегодня в V8 так и не реализована. Далее покажу один из способов эмуляции "правильного" вызова tail-recursive функций с помощью одного приема по имени trampolining. Название не очень отражает суть, я бы назвал эту технику "развинчивание стэка вручную". Для примера возьмем "традиционную" рекурсивную реализацию функции, возвращающей факториал:

const factorial = (n) => n ? n * factorial(n - 1) : 1;


Выполним tail-call оптимизацию:
const factorial = (n) => {
  const fn = (n, acc) => n ? fn(n - 1, acc * n) : acc;
  return fn(n, 1);
};


По идее в таком виде уже должно работать, если верить этой таблице можно попробовать в ночном билде Node.js v7.0.0, я тестирую в десктопной версии Chrome, результат на скриншоте.

Рецепт приготовления функции к "трамплину" в том, чтобы в случае рекурсивного вызова она возвращала так называемый thunk:
const factorial = (n) => {
  const fn = (n, acc) => n ? () => fn(n - 1, acc * n) : acc;
  return fn(n, 1);
};

Код "трамплина" может выглядеть примерно так:
const trampoline = (fn) => {
  while (typeof fn === 'function') {
    fn = fn();
  }
  return fn;
};

Вот теперь все в елочку:

Для получения вменяемого результата факториала (не Infinity) можно использовать какую-нибудь библиотеку для работы с "большими числами", но это уже совсем другая история...