Day 3 – Stack Frame Reduction

Stack Frame Reduction

What is a Stack Frame?

 width=

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:

basic
Didn’t Larry start with Basic?

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!

trampoline-by-charles-cheng
Everything is better with trampolines, with penguins, in space, or on ice.

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) }) }
}

Published by tmtvl

Martial artist and Linux user. Does a little Java development with a helping of Perl on the side.

One thought on “Day 3 – Stack Frame Reduction

  1. I’m not really sure, how does this prevent stack frames generation:

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

    It seems, I need to save the current call state to multiply the result of (next) samewith and return the multiple. Aren’t these accumulated on stack? Am I missing something?

    Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: