Tail Call Optimization

Consider the program:

def m2() = {
    var i = 0
    var j = 0

    def loop(): Unit = {
        if (i < 100000) {
            i = i + 1
            j = j + 1
            loop()
        }
    }

    loop()
    i + j
}

m2()

At the moment, the program runs fine, albeit a bit slow.

If we add something to the end, however (literally anything):

def m2() = {
    var i = 0
    var j = 0

    def loop(): Unit = {
        if (i < 100000) {
            i = i + 1
            j = j + 1
            loop()
            i = i + 0 // Could be anything
        }
    }

    loop()
    i + j
}

m2()

we run into a stackoverflow error, even at just 100 000 iterations. This is because we keep pushing a new stack frame to The Stack, while the first example was using tail call optimization.

Tail Call

at the end of the epilogue before, we can deallocate the frame early (i.e move the epilogue above the recursive call) to essentially re-use the frame, so we only ever have the same frame on the stack.

Problem: we pushed the parameters before the main frame, so if we want to pop off just the params, we can't do that.

todo finish this note later