Reference Counting and Tail Calls

One thing I thought about today is reference counting in combination with tail calls. Imagine a function like this:

function f(x) { return g(x+1); }

Now consider that x is a reference counted object and that x + 1 creates a new object. The call to g(x + 1) shall be in tail call position.

In most reference counted languages, the reference to an argument is owned by the caller. That is, f() owns the reference to x + 1. In that case, the call to g() would no longer be in a tail call position, as we still have to decrease the reference count after g() exits.

An alternative would be that the callee owns the reference. This however, will most likely create far more reference count changes than a caller-owns language (increase reference count in caller, decrease reference count in callee). For example, the following function requires an increment before the call to g().

function f1(x) { return g(x); }

Does anyone have any ideas on how to solve the problem of tail calls while avoiding the callee-owns scenario? Something that does not require a (non-reference-counting) garbage collector would be preferably.

8 thoughts on “Reference Counting and Tail Calls

    1. This should work well in most cases if I am not mistaken. In the case where ownership is not transferred, we basically end up with 2-3 additional instructions (CMP, JE) before each RET; and a cold code path for the tail call case. If a function then tail calls again, we have some more branches for cleaning up the arguments and preparing the new call, but it should work.

  1. You could side-step the problem, by, for example, storing x+1 in a variable owned by the function outside the recursive/tail call and passing in a reference. It’s not general, but might do in a specific situation.

    Otherwise, you have to transfer ownership of the object to the called function before its called, which probably means automatic memory management is out of the question. But manual should be easy enough.

    You’ve got me curious now. What’s this for?

  2. There is a technique that is employed in C++ sometimes. You call the function like “return g(move(x))”. The idea behind this is that move() creates some kind of proxy object that transfers the single shared ownership, avoiding the up/down of the reference counter. Now, to get to the mentioned “g(x+1)”, that is equivalent to “g(plus(x, 1))” which then becomes “g(plus(move(x), 1))”.

    If possible, I’d also consider avoiding reference counting and stay with exclusive ownership, but that is not always possible. A function would then already declare in its interface that it takes exclusive ownership of a passed object.

    1. It’s not about the x that is problematic. The only problematic thing is x + 1. x can have its reference count decreased just fine. The target language cannot avoid automatic memory management in any way, so no exclusive ownerships.

Comments are closed.