Trampoline, example in Java

Let’s write a simple program to add numbers from n to 0. But instead of using iterative approach, why not try recursive approach?

We call this program sum. We know sum(0) == 0, so this is our base case. How do we arrive at the base case? sum(n) == n sum(n-1), until finally reaching sum(0). The Java code is as follows:

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

Recursion problem?

Recursion has an inherent flaw when the base case is far away from the input value... In most languages, function calls use the program's stack to store function call information, so very large recursions can cause a stack overflow.

But, is there a way to avoid this? Actually, there is. This is an old strategy called trampoline.

Springboard

The basic idea of ​​the springboard strategy is that part of the program returns a "value" or a "continuation". What is continuation? A function that will continue processing.

It’s roughly as follows:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

What is the continuation of

sum?

Let us model sum the program as: Instead of simply recursing, use continuations. One way is to use acc as an object passed via a continuation. So when sum_trampoline(0, acc) is reached, we return acc. How to proceed?

Let’s go from sum_trampoline(n, acc) to sum_trampoline(n-1, acc n). The first input is sum_trampoline(n, 0).

So, the code is as follows:

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

Use types to describe springboards

The springboard needs to be roughly of the following form:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

But this gives a lot of coding freedom and is not very intuitive for the Java world. We can check if it is a continuation by asking the object. What if we asked "Was the value found?" Another thing is that since Java doesn't have sum-types, return trampolim will actually return the trampolim type instead of returning the value. We can go back to trampolim.value().

Finally, a key point is the bootstrapping of the springboard. To do this, we can use a function to convert the input into the appropriate pogo return value. Inputs and results can be generalized for better use:

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

TrampolineStep<R>What about the interface?

It defines three methods:

• gotValue: Asks if the value has been found
• value: Returns the found value
• runNextStep: Returns a value or a continuation

It basically has two states:

• Value found
• It is a continuation

Therefore, we can use static methods to initialize it. For cases where the value has been found, the value needs to be passed:

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

For the case of continuation, you need to pass how to get the next item of the continuation:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sum_trampolineHow will this be achieved?

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

Tail call Fibonacci

The classic implementation of Fibonacci follows the recursive definition:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

There is also an iterative version that expands the Fibonacci definition not recursively, but forward: starting from 0 and 1 until the corresponding values ​​are reached:

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

There is a forward version of this implementation, using "tail call recursion":

static <X> TrampolineStep<X> valueFound(X value) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return true;
        }

        @Override
        public X value() {
            return value;
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return this;
        }
    };
}

Here I separate the input interface, which prepares the numbers that will be used in the tail call recursive Fibonacci. As it moves forward, we start with the mapping fib[0] => 0, fib[1] => 1 and navigate from index 0 until we reach index n.

Fibonacci: From Tail Call to Springboard

The example of

fib_tc illustrates the Fibonacci springboard well:

static <X> TrampolineStep<X> goonStep(Supplier<TrampolineStep<X>> x) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return false;
        }

        @Override
        public X value() {
            throw new RuntimeException("dont call this");
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return x.get();
        }
    };
}

Please note that this is just a skeleton and requires a complete implementation of the TrampolineStep interface and a complete implementation of the trampoline functions to compile and run. Additionally, IN needs to be replaced with a specific input type.

The above is the detailed content of Trampoline, example in Java. For more information, please follow other related articles on the PHP Chinese website!