While

I’m still working on saturn and I recently implemented tail-call optimization. One really neat thing about tail-call optimization is that now, unlike in neptune, loops can be implemented purely within the programming language without any “magic” from the compiler. Okay a little magic is still required to parse the while loop syntax so that

while (i < n) {
System.print_on_stdout(i);
i = i + 1;
}

can be translated into

(fun -> i < n).while(fun {
System.print_on_stdout(i);
i = i + 1;
})

but where the while method was magic in neptune it can be implemented directly in saturn. It turned out, however, that in order for this method to behave as you would expect you have to be careful with how you implement it. My first implementation was pretty straightforward:

while(body) {
if (this()) {
body();
this.while(body);
}
}

The most important property of while, and the reason why it couldn’t be implemented in neptune, is that it must not grow the stack. The way to make this happen is to be sure that the recursive call to while is a tail call which is guaranteed not to grow the stack.

The problem with the method above, or one of the problems, is that in saturn, an if statement is actually a call to the if method. The if statement in the method above corresponds to this:

(this()).if(fun {
body();
this.while(body);
})

Unfortunately, that method call grows the stack. It’s easy to get rid of though, we can just change it into a guard instead:

while(body) {
if (!this()) return;
body();
this.while(body);
}

Now the recursive call to while is not surrounded by any other method calls. However, because of a nasty subtlety the recursive call is still not a tail call.

When is a call a tail call? When the call is the absolutely last thing done in the surrounding method before it returns. It would seem that in the method above the recursive call to while is indeed the very last thing that happens — so it should be a tail call right? The snag is that methods that don’t explicitly return a value implicitly return a dummy value, void. If we could write the method out in full it would correspond to this:

while(body) {
if (!this()) return;
body();
this.while(body);
return void;
}

But as before, it’s easy to get around this. If we return the value of the recursive call instead of letting the method return void the call finally becomes a tail call:

while(body) {
if (!this()) return;
body();
return this.while(body);
}

That is indeed how the method is implemented.

It is unfortunate that the last method call in a method is not a tail call but that would require methods without an explicit return to return the value of the last statement (for some suitable definition) and that brings up endless problems. Returning a void value proved to work very well in neptune so I’m not inclined to change that. Maybe there’s some implementation trick that can allow both things? I suspect there might be.

Anyway, this is one example of tail-call optimization interacting in interesting ways with other features of the language. I’m sure there’ll be more examples along the way.

2 Responses to While

Leave a Reply

Your email address will not be published. Required fields are marked *


*