154 lines
5.2 KiB
Markdown
Raw Permalink Normal View History

---
layout: pattern
title: Trampoline
folder: trampoline
permalink: /patterns/trampoline/
2019-11-16 21:56:40 +02:00
categories: Behavioral
language: en
tags:
- Performance
---
## Intent
2020-07-25 15:48:21 +03:00
2020-09-13 18:35:23 +03:00
Trampoline pattern is used for implementing algorithms recursively in Java without blowing the stack
and to interleave the execution of functions without hard coding them together.
2018-01-20 13:36:43 +03:00
## Explanation
2020-07-25 15:48:21 +03:00
Recursion is a frequently adopted technique for solving algorithmic problems in a divide and conquer
style. For example, calculating Fibonacci accumulating sum and factorials. In these kinds of
problems, recursion is more straightforward than its loop counterpart. Furthermore, recursion may
need less code and looks more concise. There is a saying that every recursion problem can be solved
using a loop with the cost of writing code that is more difficult to understand.
2020-07-25 15:48:21 +03:00
However, recursion-type solutions have one big caveat. For each recursive call, it typically needs
2020-09-13 18:35:23 +03:00
an intermediate value stored and there is a limited amount of stack memory available. Running out of
stack memory creates a stack overflow error and halts the program execution.
2020-07-25 15:48:21 +03:00
Trampoline pattern is a trick that allows defining recursive algorithms in Java without blowing the
2020-09-13 18:35:23 +03:00
stack.
2020-07-25 15:48:21 +03:00
Real-world example
2020-07-25 15:48:21 +03:00
> A recursive Fibonacci calculation without the stack overflow problem using the Trampoline pattern.
In plain words
> Trampoline pattern allows recursion without running out of stack memory.
Wikipedia says
2020-09-13 18:35:23 +03:00
> In Java, trampoline refers to using reflection to avoid using inner classes, for example in event
> listeners. The time overhead of a reflection call is traded for the space overhead of an inner
> class. Trampolines in Java usually involve the creation of a GenericListener to pass events to
> an outer class.
2020-07-25 15:48:21 +03:00
**Programmatic Example**
Here's the `Trampoline` implementation in Java.
2020-09-13 18:35:23 +03:00
When `get` is called on the returned Trampoline, internally it will iterate calling `jump` on the
returned `Trampoline` as long as the concrete instance returned is `Trampoline`, stopping once the
returned instance is `done`.
2020-07-25 15:48:21 +03:00
```java
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) {
2020-10-04 14:17:10 +03:00
return new Trampoline<T>() {
2020-07-25 15:48:21 +03:00
@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();
}
};
}
}
```
Using the `Trampoline` to get Fibonacci values.
```java
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) {
2020-07-25 15:48:21 +03:00
if (times == 0) {
return Trampoline.done(prod);
2020-07-25 15:48:21 +03:00
} else {
return Trampoline.more(() -> loop(times - 1, prod * times));
2020-07-25 15:48:21 +03:00
}
}
2020-09-13 18:35:23 +03:00
```
Program output:
```
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
2020-07-25 15:48:21 +03:00
```
2018-01-20 13:36:43 +03:00
## Class diagram
2020-09-13 18:35:23 +03:00
![alt text](./etc/trampoline.urm.png "Trampoline pattern class diagram")
## Applicability
2020-09-13 18:35:23 +03:00
Use the Trampoline pattern when
* For implementing tail-recursive functions. This pattern allows to switch on a stackless operation.
* For interleaving execution of two or more functions on the same thread.
2020-07-25 15:48:21 +03:00
## Known uses
2020-07-25 15:48:21 +03:00
* [cyclops-react](https://github.com/aol/cyclops-react)
2020-07-25 15:48:21 +03:00
## Credits
* [Trampolining: a practical guide for awesome Java Developers](https://medium.com/@johnmcclean/trampolining-a-practical-guide-for-awesome-java-developers-4b657d9c3076)
* [Trampoline in java ](http://mindprod.com/jgloss/trampoline.html)
2020-07-25 15:48:21 +03:00
* [Laziness, trampolines, monoids and other functional amenities: this is not your father's Java](https://www.slideshare.net/mariofusco/lazine)
* [Trampoline implementation](https://github.com/bodar/totallylazy/blob/master/src/com/googlecode/totallylazy/Trampoline.java)
* [What is a trampoline function?](https://stackoverflow.com/questions/189725/what-is-a-trampoline-function)
* [Modern Java in Action: Lambdas, streams, functional and reactive programming](https://www.amazon.com/gp/product/1617293563/ref=as_li_qf_asin_il_tl?ie=UTF8&tag=javadesignpat-20&creative=9325&linkCode=as2&creativeASIN=1617293563&linkId=ad53ae6f9f7c0982e759c3527bd2595c)
* [Java 8 in Action: Lambdas, Streams, and functional-style programming](https://www.amazon.com/gp/product/1617291994/ref=as_li_qf_asin_il_tl?ie=UTF8&tag=javadesignpat-20&creative=9325&linkCode=as2&creativeASIN=1617291994&linkId=e3e5665b0732c59c9d884896ffe54f4f)