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

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. CA says:

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

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