Stack Frame Reduction

What is a Stack Frame?

For those not familiar with the stack, it is a bit of memory for your program to use. It is fast but limited.
Whenever you call a procedure (function, method,… naming is a complicated thing) your program gets a bit of storage on the stack, which we call a frame.
The stack frame gets used for storing parameters, local variables, temporary storage, and some information about the calling context.
This means that if you have a recursive procedure call your program keeps asking for stack frames until you eventually return a value and the memory is freed up.

A quick and simple example:

Let us take the standard example of a basic recursive sorting algorithm:

sub factorial (Int $n --> Int) {
        $n == 0 ?? 1 !! $n * factorial($n - 1)
}

This is a very simple example of recursion, and usually we don’t have to worry about stack frame buildup in this code. That said, this is a good starting point for showing how to reduce the buildup.

GOTO reduction:

This way of reducing stack frame buildup should be familiar to most people, it’s the way procedural programming handles recursion.

The most basic implementation of this pattern looks like this:

sub factorial (Int $n is copy --> Int) {
        my Int $result = 1;
        MULT:
        $result *= $n;
        $n--;
        goto MULT if $n > 0;
        return $result;
};

GOTO is not yet implemented in Raku, but it should be fairly obvious we can easily replace this with an existing keyword:

sub factorial (Int $n is copy --> Int) {
        my Int $result = 1;
        while $n > 0 {
                $result *= $n;
                $n--;
        }
        return $result;
}

This does defeat the purpose of trying to use recursion, though. Therefore Raku offers the samewith keyword:

sub factorial (Int $n --> Int) {
        $n == 0 ?? 1 !! $n * samewith($n - 1);
}

There we go, recursion without incurring a thousand stack frames. I still think we’re missing something, though…

TRAMPOLINE!

A trampoline is a design pattern in Functional Programming. It is a little complicated compared to normal GOTO-style reduction, but in the right hands it can be very powerful.
The basics behind the trampoline pattern are as follows:

• We can expect to do something with the value we’re computing.
• We can just pass our TODO into the function that computes the value.
• We can have our function generate its own continuation.

sub trampoline (Code $cont is copy) {
        $cont = $cont() while $cont;
}

So we pass the trampoline a function. That function is called. The function optionally returns a follow-up. As long as we get a follow-up, we keep calling it and assigning the result until we’re done.

It requires a little reworking of the factorial function:

sub factorial (Int $n, Code $res --> Code) {
        $n == 0 ?? $res(1) !! sub { factorial($n - 1, sub (Int $x) { $res($n * $x) }) }
}

To unpack that heap of stacked functions:

• If $n is 0, we can just move on to the continuation.
• Otherwise we return an anonymous function that calls factorial again.
• The previous step propagates until we arrive at 0, where we get the result called with 1.
• That multiplies the previous $n with 1, and propagates the result backwards.
• Eventually the result is propagated to the outermost block and is passed into the continuation.

The way we would use the trampoline then follows:

trampoline(sub { factorial($n, sub (Int $x) { say $x; Nil }) });

Again, a bunch of tangled up functions to unpack:

• We send an anonymous function to the trampoline that calls factorial with a number $n, and an anonymous continuation.
• The continuation for the factorial is to say the result of the factorial and stop (the Nil).

Bonus round

Why would you use a trampoline for something that could be done easier with a regular for loop?

sub factorial-bounce (Int $n --> Code) {
        sub { factorial($n, sub ($x) { say $x, factorial-bounce($x) }) }
}