Tail-recursive even/odd

Tail calls are a way to save on call stack space. If a function call happens as a last thing a function performs, then it is possible for a language implementation to optimize the call by getting rid of all temporary values on the stack before the call is made.

Consider this implementation of even and odd functions in Python:

def even(x):
    if x == 0:
        return True
    return odd(x-1)

def odd(x):
    if x == 0:
        return false
    return even(x-1)

Here, the recursive calls are in the "tail" position, and thus in theory it is possible to just discard the caller's stack and proceed with evaluating the callee without making a regular function call. In Python there are no tail calls, but it's not hard to implement in a virtual machine.

So, this is what I did in my virtual machine. Here's the same example written in the VM assembly:

;; Pick a reasonably big number
;; to demonstrate that we don't
;; use stack much
(const val 1000000)
(const one 1)
(const zero 0)

(sr 3)
(setjump r0 even)
(mov r1 val)
(call r0 1)

(aeq r0 one)
(retnil)

;; Even implementation
(label even)
(sr 3)
(jeq r0 zero even-end)

(setjump r1 odd)
(sub r2 r0 one)
(tailcall r1 1)

(label even-end)
(ret one)

;; Odd implementation
(label odd)
(sr 3)
(jeq r0 zero odd-end)

(setjump r1 even)
(sub r2 r0 one)
(tailcall r1 1)

(label odd-end)
(ret zero)

In places where we want to make a tail call, instead of using call, you need to use tailcall. But otherwise the way you write such calls would be the same.