Stackframe Reduction

basic.png

plates-by-brooke-lark.jpg

raku-advent-2019-stackframe.md

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

Thanks

Thanks to the MoarVM, NQP, and Rakudo devs for their brilliant work. Thanks to Larry for creating such a wonderful pair of languages. And last, but not least, thanks to the community for being so supportive.

trampoline-by-charles-cheng.jpg