Trampoline

Alrededor de 2 min

Propósito

El patrón Trampoline se utiliza para implementar algoritmos recursivamente en Java sin volar la pila
y para intercalar la ejecución de funciones sin codificarlas juntas.

La recursión es una técnica frecuentemente adoptada para resolver problemas algorítmicos en un estilo de divide y vencerás.
Por ejemplo, el cálculo de la suma acumulativa de Fibonacci y los factoriales. En este tipo de
problemas, la recursividad es más directa que su homóloga de bucle. Además, la recursividad puede
necesitar menos código y parecer más concisa. Hay un dicho que dice que todo problema de recursión puede resolverse
utilizando un bucle a costa de escribir código más difícil de entender.

Sin embargo, las soluciones de tipo recursivo tienen una gran advertencia. Para cada llamada recursiva, normalmente se necesita
un valor intermedio almacenado y hay una cantidad limitada de memoria de pila disponible. Quedarse sin
memoria de pila crea un error de desbordamiento de pila y detiene la ejecución del programa.

Trampoline pattern es un truco que permite definir algoritmos recursivos en Java sin desbordar la
pila.

Ejemplo del mundo real

Un cálculo Fibonacci recursivo sin el problema de desbordamiento de pila utilizando el patrón Trampoline.

En palabras sencillas

El patrón Trampoline permite la recursión sin agotar la memoria de la pila.

Wikipedia dice

En Java, trampoline se refiere al uso de reflection para evitar el uso de clases internas, por ejemplo en
eventos. La sobrecarga de tiempo de una llamada a reflection se intercambia por la sobrecarga de espacio de una clase interna.
Trampolines en Java generalmente implican la creación de un GenericListener para pasar eventos a una clase externa.

Ejemplo programático

Esta es la implementación de Trampoline en Java.

Cuando se llama a get sobre el Trampoline devuelto, internamente se itera llamando a jump sobre el
siempre que la instancia concreta devuelta sea Trampoline, deteniéndose una vez que la instancia
instancia devuelta sea done.

public interface Trampoline<T> {

  T get();

  default Trampoline<T> jump() {
    return this;
  }

  default T result() {
    return get();
  }

  default boolean complete() {
    return true;
  }

  static <T> Trampoline<T> done(final T result) {
    return () -> result;
  }

  static <T> Trampoline<T> more(final Trampoline<Trampoline<T>> trampoline) {
    return new Trampoline<T>() {
      @Override
      public boolean complete() {
        return false;
      }

      @Override
      public Trampoline<T> jump() {
        return trampoline.result();
      }

      @Override
      public T get() {
        return trampoline(this);
      }

      T trampoline(final Trampoline<T> trampoline) {
        return Stream.iterate(trampoline, Trampoline::jump)
            .filter(Trampoline::complete)
            .findFirst()
            .map(Trampoline::result)
            .orElseThrow();
      }
    };
  }
}

Uso del Trampoline para obtener valores Fibonacci.

public static void main(String[] args) {
    LOGGER.info("Start calculating war casualties");
    var result = loop(10, 1).result();
    LOGGER.info("The number of orcs perished in the war: {}", result);
}

public static Trampoline<Integer> loop(int times, int prod) {
    if (times == 0) {
        return Trampoline.done(prod);
    } else {
        return Trampoline.more(() -> loop(times - 1, prod * times));
    }
}

Salida del programa:

19:22:24.462 [main] INFO com.iluwatar.trampoline.TrampolineApp - Start calculating war casualties
19:22:24.472 [main] INFO com.iluwatar.trampoline.TrampolineApp - The number of orcs perished in the war: 3628800

Diagrama de clases

alt text — Trampoline pattern class diagram

Aplicabilidad

Utilice el patrón Trampoline cuando:

Para implementar funciones recursivas de cola. Este patrón permite encender una operación sin pila.
Para intercalar la ejecución de dos o más funciones en el mismo hilo.

Usos conocidos

cyclops-reactopen in new window

Trampoline

Propósito

Explicación

Diagrama de clases

Aplicabilidad

Usos conocidos

Créditos