Как понять батут в JavaScript?

Вот код:

function repeat(operation, num) {
  return function() {
    if (num <= 0) return
    operation()
    return repeat(operation, --num)
  }
}

function trampoline(fn) {
  while(fn && typeof fn === 'function') {
    fn = fn()
  }
}

module.exports = function(operation, num) {
  trampoline(function() {
    return repeat(operation, num)
  })
}

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

Но как работает этот сниппет? Особенно функция trampoline? Что он сделал именно с помощью while и как он достиг своей цели?

Спасибо за любую помощь:)

Ответ 1

Цикл while будет продолжать работать до тех пор, пока условие не будет ложным.

fn && typeof fn === 'function' будет ложным, если сам fn является фальшивым, или если fn - это что-то иное, чем функция.

Первая половина фактически избыточна, поскольку значения фальши также не являются функциями.

Ответ 2

Батут - это просто метод оптимизации рекурсии и предотвращения исключений на языках, которые не поддерживают tail call optimization, как реализация Javascript ES5 и С#. Однако ES6, вероятно, будет поддерживать оптимизацию хвостового вызова.

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

(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0)))) 
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

Вот визуализация стека, где каждая вертикальная черта представляет собой стек стека:

         ---|---
      ---|     |---
   ---|            |--- 
---                    ---

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

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

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

Вы можете визуализировать стек как прыгающий батут:

   ---|---   ---|---   ---|---
---      ---       ---

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

Поскольку у нас нет роскоши tail call optimization в Javascript, нам нужно выяснить способ превратить регулярную рекурсию в оптимизированную версию, которая будет выполняться в батуте.

Один очевидный способ - избавиться от рекурсии и переписать код для итерации.

Если это невозможно, нам нужен более сложный код, вместо того, чтобы непосредственно выполнять рекурсивные шаги, мы будем использовать higher order functions, чтобы вернуть функцию-обертку вместо прямого выполнения рекурсивного шага и позволить другой функции управлять выполнением.

В вашем примере функция repeat переносит регулярный рекурсивный вызов с помощью функции и возвращает эту функцию вместо выполнения рекурсивного вызова:

function repeat(operation, num) {
    return function() {
       if (num <= 0) return
       operation()
       return repeat(operation, --num)
    }
}

Возвращенная функция является следующим шагом рекурсивного выполнения, а батут - это механизм для выполнения этих шагов управляемым и итеративным способом в цикле while:

function trampoline(fn) {
    while(fn && typeof fn === 'function') {
        fn = fn()
    }
}

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

Использование батута, очевидно, менее показательно, чем простая рекурсия, поскольку вы "блокируете" нормальный рекурсивный поток, но это намного безопаснее.

http://en.wikipedia.org/wiki/Tail_call

http://en.wikipedia.org/wiki/Trampoline_%28computing%29

Ответ 3

В других ответах описывается, как работает батут. Однако данная реализация имеет два недостатка, один из которых даже вреден:

Протокол трамплина зависит только от функций. Что делать, если результат рекурсивной операции также является функцией?
Вам нужно применить рекурсивную функцию с функцией батута в вашем кодовом коде. Это деталь реализации, которая должна быть скрыта.

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

// a tag to uniquely identify thunks (zero-argument functions)

const $thunk = Symbol.for("thunk");

//  eagerly evaluate a lazy function until the final result

const eager = f => (...args) => {
  let g = f(...args);
  while (g && g[$thunk]) g = g();
  return g;
};

// lift a normal binary function into the lazy context

const lazy2 = f => (x, y) => {
  const thunk = () => f(x, y);
  return (thunk[$thunk] = true, thunk);
};

// the stack-safe iterative function in recursive style

const repeat = n => f => x => {
  const aux = lazy2((n, x) => n === 0 ? x : aux(n - 1, f(x)));
  return eager(aux) (n, x);
};

const inc = x => x + 1;

// and run...

console.log(repeat(1e6) (inc) (0)); // 1000000