Tail Calls

Introduction

Tail calls are a distinctive Cap'n Proto feature, not found in any other RPC system known to the author (please tell me if you know one). A tail call saves on a network trip by answering a question with a counter-question. Let's take this human conversion for demonstrating the concept of a tail call:

Alice: What time is it?

Bob: What does your wristwatch display? Just look, don't tell.

Bob: The answer to your question is the same like the answer to the question which i just asked you.

Needless to say: If this was a real human conversion, Bob would probably skip the last two sentences, relying on Alice's smartness. And still, poor Alice would probably feel stupid. Really, Bob should find a more charming way to resolve that situation. Luckily, machines are stupid and never feel embarrased. All of Bob's statements are indeed strictly required to disambiguate machine conversation: By saying Just look, don't tell, Bob indicates that he does not expect any answer to his question (instead, Alice shall answer it to herself). With the last, somehwat bloated sentence Bob establishes the logical relationship between Alice's question and his question. Finally the efficiency improvement of that conversion becomes obvious: Instead of waiting for Alice to answer his counter-question, and reflecting that answer back to her, Bob just totally played the ball to Alice.

Maybe you've heard of tail calls in computing theory. And now might wonder whether Cap'n Proto tail calls are a different concept, kind of an overloaded notion. Indeed, the preceeding explanation of tail calls and the explanation which you might know from the theory are just two sides of the same coin. This becomes obvious when we model the conversion in Cap'n Proto and express it in code.

interface Bob
{
  whatTime @0 (alice: Alice) -> (time: Int64);
}

interface Alice
{
  whatsOnYourWristwatch @0 () -> (time: Int64);
}

class Bob : IBob
{
    public Task<long> WhatTime(IAlice alice, CancellationToken cancellationToken_ = default)
    {
        using (alice) return alice.WhatsOnYourWristwatch(); // Tail call, automatically inferred
    }

    public void Dispose()
    {
    }
}

Do you see it? Citing Wikipedia: In computer science, a tail call is a subroutine call performed as the final action of a procedure. Calling alice.WhatsOnYourWristwatch() looks very much like the last action. Looking in more detail, quite not: Because of using (alice), the real last action is alice.Dispose()! Is the analogy broken? Luckily not: If we mentally combine alice.WhatsOnYourWristwatch() and alice.Dispose() to some hypothetical method alice.WhatsOnYourWristwatch_ThenDispose(), we get a real tail call. This is actually what happens behind the scenes: Calling on alice increments the underlying capability's reference count until the call has been sent over the network, which happens asynchronously. The Capnp.Net.Runtime defers calls to other capabilities for the exact reason of deciding whether it can apply a tail call optimization. This is the case when skeleton method provenly returns the same result like a question issued before.

Support and limitations

The Capnp.Net.Runtime automatically identifies possible tail calls and applies protocol-level tail call optimization. But there are some limitations to consider which will be discussed now.

Tail caller must not be async

If we modify the example from above only a little bit, it breaks tail call identification (which just means "traditional call" - not "burn and die").

class Bob : IBob
{
    public async Task<long> WhatTime(IAlice alice, CancellationToken cancellationToken_ = default)
    {
        using (alice) return await alice.WhatsOnYourWristwatch(); // No tail call, see explanation
    }

}

Despite it seems inconspicuous, the await changes things fundamentally: It turns alice.WhatsOnYourWristwatch() into an actual result. Following the semantics of a "result", the framework is forced to deliver just that. And because it also cannot know that the result remains untouched (Bob might add a few microseconds to compensate network delay), it cannot even prove that Alice's question and Bob's counter-question deliver the same result.

Don't cache tail calls

Let's try to hack tail call detection. In the following scenario, Bob keeps the counter-question and attempts a later evaluation on it:

public Task<long> WhatTime(IAlice alice, CancellationToken cancellationToken_ = default)
{
    using (alice)
    {
        var result = alice.WhatsOnYourWristwatch();
             
        async void ReuseAnswerFromAlice()
        {
            try
            {
                var time = await result;
                Console.WriteLine($"Time: {time}"); // Never hit
            }
            catch (NoResultsException)
            {
                Console.WriteLine($"Ah, right, was a tail call..."); // We'll arrive here
            }
        }

        ReuseAnswerFromAlice();

        return result;
    }
}

Although this scenario seems a bit synthetic (which is the justification to apply tail-call optimization automically), it possible. And the Capnp.Net.Runtime cannot know anything about this. The problem here is that, due to sending alice.WhatsOnYourWristwatch() as tail call, Alice was instructed to keep the answer by herself. Bob will never receive that actual result (just an acknolwedgement that Alice found some answer). So expect to catch the NoResultsException which was dedicated specifically to that purpose.