que - ¿Cómo entender el trampolín en JavaScript?
manipular elementos html javascript (3)
Aquí está el código:
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)
})
}
He leído que el trampolín se usa para hacer frente al problema de desbordamiento, por lo que la función no solo mantendrá la llamada y la pila.
Pero, ¿cómo funciona este fragmento? Especialmente la función de trampoline ? ¿Qué hizo exactamente por el while y cómo logró su objetivo?
Gracias por cualquier ayuda :)
El ciclo while continuará ejecutándose hasta que la condición sea faly.
fn && typeof fn === ''function'' será falso, ya sea si fn es falso o si fn es una función.
La primera mitad es en realidad redundante, ya que los valores falsy tampoco son funciones.
El trampolín es solo una técnica para optimizar la recursión y evitar excepciones de desbordamiento de pila en lenguajes que no admiten tail call optimization como la implementación de Javascript ES5 y C #. Sin embargo, ES6 probablemente tendrá soporte para la optimización de la cola de llamadas.
El problema con la recursión regular es que cada llamada recursiva agrega un marco de pila a la pila de llamadas, que puede visualizar como una pirámide de llamadas. Aquí hay una visualización de llamar a una función factorial recursivamente:
(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6
Aquí hay una visualización de la pila donde cada tablero vertical es un marco de pila:
---|---
---| |---
---| |---
--- ---
El problema es que la pila tiene un tamaño limitado, y el apilamiento de estos marcos de pila puede desbordar la pila. Dependiendo del tamaño de la pila, un cálculo de un factorial más grande desbordaría la pila. Es por eso que la recursión regular en C #, Javascript etc. podría considerarse peligrosa .
Un modelo de ejecución óptimo sería algo así como un trampolín en lugar de una pirámide, donde cada llamada recursiva se ejecuta en su lugar y no se acumula en la pila de llamadas. Esa ejecución en lenguajes compatibles con la optimización de llamadas podría ser similar a la siguiente:
(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6
Puedes visualizar la pila como un trampolín que rebota:
---|--- ---|--- ---|---
--- --- ---
Esto es claramente mejor ya que la pila siempre tiene solo un cuadro, y desde la visualización también se puede ver por qué se llama un trampolín. Esto evita que la pila se desborde.
Dado que no tenemos el lujo de la tail call optimization de la tail call optimization en Javascript, tenemos que encontrar una manera de convertir la recurrencia regular en una versión optimizada que se ejecutará a la moda trampolín.
Una forma obvia es deshacerse de la recursión y reescribir el código para que sea iterativo.
Cuando eso no es posible, necesitamos un código un poco más complejo en el que, en lugar de ejecutar directamente los pasos recursivos, utilicemos higher order functions para devolver una función de envoltura en lugar de ejecutar el paso recursivo directamente, y permitir que otra función controle la ejecución.
En su ejemplo, la función de repetición ajusta la llamada recursiva regular con una función y devuelve esa función en lugar de ejecutar la llamada recursiva:
function repeat(operation, num) {
return function() {
if (num <= 0) return
operation()
return repeat(operation, --num)
}
}
La función devuelta es el siguiente paso de la ejecución recursiva y el trampolín es un mecanismo para ejecutar estos pasos de forma controlada e iterativa en el ciclo while:
function trampoline(fn) {
while(fn && typeof fn === ''function'') {
fn = fn()
}
}
Por lo tanto, el único propósito de la función de trampolín es controlar la ejecución de forma iterativa, y eso garantiza que la pila solo tenga un único marco de pila en la pila en un momento dado.
Usar un trampolín es obviamente menos eficiente que la recursión simple, ya que estás "bloqueando" el flujo recursivo normal, pero es mucho más seguro.
Las otras respuestas describen cómo funciona un trampolín. La implementación dada tiene dos inconvenientes, uno de los cuales es incluso dañino:
- El protocolo de trampolín depende solo de las funciones. ¿Qué sucede si el resultado de la operación recursiva también es una función?
- Debe aplicar la función recursiva con la función de trampolín en todo su código de llamada. Este es un detalle de implementación que debe estar oculto.
Esencialmente, la técnica del trampolín trata con la evaluación perezosa en un lenguaje evaluado con entusiasmo. Aquí hay un enfoque que evita los inconvenientes mencionados anteriormente:
// 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
La evaluación perezosa se lleva a cabo localmente dentro de la repeat . Por lo tanto, su código de llamada no necesita preocuparse por ello.