proper tail calls

proper-tail-calls.md

A simple explanation of proper tail calls

I thought I could teach a little bit about proper tail calls in an easy to understand way!

• First I'll explain a little about normal function calls - most people will already know this so it's just a refresher.
• Then I'll show what the stack will look like for a sample program I made.
• After that I explain a bit about what tail calls are and show what the stack would look like for the same program executed in tail call mode.

I hope that will help people understand what exactly this tail call stuff is!

normal function calls

First off, a bit about how normal function calls work. I made this example code to help explain it:

function inc(x) {
 return x + 1;
}

console.log(inc(3));

So what happens when we call inc(3)? A few things:

• The javascript engine saves it's place onto the stack.
• It puts the parameters onto the stack
• It jumps into the function

First it pushes what is called a return address onto the stack, this points to the code console.log(---) that will be run after the inc function returns its output value.

Second it needs to put all the parameters onto the stack, we only have one here: the number 3. Inside the inc function it looks up its argument x by checking near the top of the stack.

Third once it is finished computing x + 1 it pops everything that it has used off of the stack and then pops the return address off and jumps to that.

Summary

Function calls are an abstraction made from a certain way of using a stack and jumps together.

Visually if the stack started like this:

- - -------.
           |
- - -------'

then to do a call we push on the return address, then the parameter x

- - -------.-----.----.
           | RET |  x |
- - -------'-----'----'

then we jump into the inc function which uses up both those things and puts the stack back to what it was before jumping back.

Tail Calls

So what actually is a tail call, and why does it matter?

It's a call that happens at the 'end' of a function, basically any time you have return f(----) that call to f is a tail call.

The reason it matters is tail calls waste memory!

I've written a tiny program that builds a song up to explain this:

function fly(x) {
 return "I don't know why she swallowed a fly!";
}

function spider(x) {
 return fly("She swallowed a spider to catch the fly, " + x);
}

function bird(x) {
 return spider("She swallowed a bird to catch the spider, " + x);
}

console.log(bird(""));

First with normal calls

So when you call bird it calls spider which calls fly. The stack frames will look like this:

set up stack for calling bird

- - -------.-----.---.
           | RET | x |
- - -------'-----'---'

call bird

- - -------.-----.---.-----.---.
           | RET | x | RET | x |
- - -------'-----'---'-----'---'

bird adds a bit to the song
calls spider

- - -------.-----.---.-----.---.-----.---.
           | RET | x | RET | x | RET | x |
- - -------'-----'---'-----'---'-----'---'

spider adds a bit to the song
calls fly

- - -------.-----.---.-----.---.-----.---.
           | RET | x | RET | x | RET | x |
- - -------'-----'---'-----'---'-----'---'

fly adds a bit to the song
return from fly

- - -------.-----.---.-----.---.
           | RET | x | RET | x |
- - -------'-----'---'-----'---'

return from spider

- - -------.-----.---.
           | RET | x |
- - -------'-----'---'

return from bird

- - -------.
           |
- - -------'

and then the song is printed out.

Now with tail calls

Because each call is a tail call there is no work done in any of the return steps except popping a couple bits off the stack, the return steps are pretty much useless!

It would be more efficient if each function just gave its stack frame to the next so that the next function can return for it - that's exactly what proper tail calls are.

Let's see it visually!

set up stack for calling bird

- - -------.-----.---.
           | RET | x |
- - -------'-----'---'

call bird

- - -------.-----.---.
           | RET | x |
- - -------'-----'---'

bird adds a bit to the song
tail calls into spider

- - -------.-----.---.
           | RET | x |
- - -------'-----'---'

spider adds a bit to the song
tail calls into fly

- - -------.-----.---.
           | RET | x |
- - -------'-----'---'

fly adds a bit to the song
return from fly

- - -------.
           |
- - -------'

and then the song is printed out.

The optimization

If you compare the two execution traces you can see that

• The stack always stayed smaller (less memory was used!)
• The program completed in fewer steps (it's faster too!)

So proper tail calls are an optimization that improves the execution of your code!