Вот код:
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 и как он достиг своей цели?
Спасибо за любую помощь:)
Цикл while будет продолжать работать до тех пор, пока условие не будет ложным.
fn && typeof fn === 'function' будет ложным, если сам fn является фальшивым, или если fn - это что-то иное, чем функция.
Первая половина фактически избыточна, поскольку значения фальши также не являются функциями.
Батут - это просто метод оптимизации рекурсии и предотвращения исключений на языках, которые не поддерживают 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()
}
}
Таким образом, единственной целью функции батута является управление исполнением итеративным способом, и это гарантирует, что стек будет иметь только один стек стека в стеке в любой момент времени.
Использование батута, очевидно, менее показательно, чем простая рекурсия, поскольку вы "блокируете" нормальный рекурсивный поток, но это намного безопаснее.
В других ответах описывается, как работает батут. Однако данная реализация имеет два недостатка, один из которых даже вреден:
По сути, техника батута относится к ленивой оценке на нетерпеливом языке. Вот подход, который позволяет избежать упомянутых выше недостатков:
// 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