Implement tail call optimization

[masak]

A tail call is any call in "last position" in a routine. Although, they could be to any other routine, in this issue let's first focus on recursive tail calls.

I'm thinking a macro recurse(...) which will semantically just call the current routine with those same parameters, except the call doesn't create a new stack frame, it re-uses the current one.

That sounds like it'd require special VM support, and sure, there could be a dedicated call instruction that does this. But it can always be desugared into a local jump to the top of the routine, preceded by parameter assignments.

I got to thinking about this when I saw Dylan's implementation of while:

define macro while
  { while (?test:expression) ?:body end }
    => { local method _while-loop ()
           if (?test) ?body; _while-loop() end;
         end method _while-loop;
         _while-loop() }
end macro while;

That's cute, and elegant. In 007 with the proposed recurse, this would look like this:

@parsed(...)
macro statement:while({ expr: test, block: body }) {
    quasi {
        func whileLoop() {
            if ({{{test}}}) {
                {{{body}}};
                recurse();
            }
        }
    }
}

Or even, #484 willing, like this:

@parsed(...)
macro statement:while({ expr: test, block: body }) {
    quasi func {
        if ({{{test}}}) {
            {{{body}}};
            recurse();
        }
    }
}

[masak]

The reason I want recurse to be explicit instead of automatically inferred is that sometimes, it's more important to preserve the stack frames (for stack traces and the like). It feels like a trade-off that should sit in the hands of the programmer.

That said, everything is fair of you predeclare. I don't see a problem with having a module that would detect all the places in the scope it's injected where recurse could be used, and automatically substituting it.

[masak]

That said, everything is fair of you predeclare. I don't see a problem with having a module that would detect all the places in the scope it's injected where recurse could be used, and automatically substituting it.

Or, perhaps more useful, a @tco attribute you can put on a function turning all potential tail recursions into actual ones.

[masak]

This macro should somehow register itself as "routine-terminating", so that (among other things) we get linter warnings when putting statements (or even intra-expression sequence points) temporally after a recurse().

[masak]

A more extreme version would be to have tail recursion optimization be on by default, but to have the @tco attribute give an error at compile time if not all calls are tail.