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

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?

LikeLiked by 1 person

Derp, yes I messed up. While ‘samewith()’ does replace stack frames in place, that doesn’t help if I let stack build up outside of it. Good catch.

LikeLike