explicit tail call syntax

[thejoshwolfe]

Progress

---

Proposal:

return @tailCall(foo, a, b, c);
// roughly equivalent to:
return foo(a, b, c);

The purpose of @tailCall() is to ensure that a tail call happens. If it cannot, the @tailCall() produces a compile error.

Here are some cases where a tail call is impossible:

• if the @tailCall() expression is not the operand of a return operator. e.g. return @tailCall(foo) - 1.
• if there are defer statements that would run after the @tailCall(). e.g. {defer bar(); return @tailCall(foo);}.
• if there is an implicit cast to convert the return value of the called function into the return value of the calling function. e.g. foo returns u8 and the caller returns ?u8.

See also #157.

[jfo]

This reminds me of clojure's recur keyword.

I am curious about how the compiler currently handles tail calls in code like:

fn r(x:u8) -> u8 {
    if (x < 10) {
        return r(x + 1);
    } else {
        return x;
    }
}

This is afaict never going to need any more than one stack frame. Would it currently use more than one? Is it possible / desirable to have the compiler identify tail call optimizable functions implicitly and what would / does that look like on the backend? Is the @tailCall built-in simply an assertion tool to verify that or would it be required to call it to perform the optimization? I would like for TCO to exist and I would similarly like to have a way to ask the compiler to verify that it is occurring, so I am 👍 in general, I'm just curious (and generally uninformed, currently) about how the specifics would look.

[ruffianeo]

I am not sure about the proposed syntax. Instead of it having function wrapper syntax (complex), a simple return tailcall foo(a,b,c) keyword would do. Working in the same spirit as the C ´´register`` keyword. It communicates intent and the compiler can deliver the news, if its not as the programmer hopes.

In order to make use of tail calls, as in the fold use case (which can be implemented as tail calls in other languages), thought should be spent on how a dynamically growing accumulator would work. filter predicate values = fold (\ acc value -> if predicate value then (value:acc) else acc) [] values. Sorry for the Haskell syntax.. I just found Zig today...

[andrewrk]

This is actually implemented already in the form of @call. However this issue is still open because the detection of when to emit a compile error is not implemented yet. I do not plan to add any additional syntax or builtins.

[dvmason]

The @call syntax is perfectly fine, but it really needs to work, and it often doesn't now.

[tauoverpi]

The @call(.{ .modifier = .always_tail, foo, .{}) is rather painfull to write when using tailcalls as usually there's quite a few of them when writing interpreters/parsers this way and usually (from what I've seen) it tends to also generate better code than while (cond) switch (x) {} style.

[wooster0]

Maybe you can write a function to make it shorter to type, like it was attempted here?

zig/src/crash_report.zig

Lines 548 to 554 in 225ed65

	inline fn goTo(comptime func: anytype, args: anytype) noreturn {
	// TODO: Tailcall is broken right now, but eventually this should be used
	// to avoid blowing up the stack. It's ok for now though, there are no
	// cycles in the state machine so the max stack usage is bounded.
	//@call(.{.modifier = .always_tail}, func, args);
	@call(.{}, func, args);
	}

[dvmason]

The current explicit syntax is ugly/painful, but if it worked properly, I could certainly deal with it.

The biggest problem is that it currently needs the type signatures of the caller and the target functions to match. All that should be required is that the return types match. The workaround is incredibly ugly, sometimes requiring horribly semantically invalid type casts, saving data in crazy places, or inlining code that should be in a function.

Automatic detection may be a bit trickier (which may include what to do with error unions and defer). But for explicit use, requiring no outstanding defer, and less-useful stack reporting for errors (as already happens for inlines), are perfectly reasonable limitations.

Please, please, please fix the implementation of the explicit case! The availability of explicit tail-calls was one of the features that led me to using Zig. Rust may get this soonish (see: this Reddit comment) - I don't know if that link is relevant.

[dvmason]

As I said, I could live with the current syntax if it worked properly. However, ideally, I would like to see the normal return/call syntax retained. So,

return foo(1,2,3); // optional tail call - up to the compiler to use/not
return @call(.{.modifier = .always_tail}, foo, .{1,2,3}); // current, ugly syntax - required tail call - error if it can't be done
return tailcall foo(1,2,3); // requires new keyword but retains function call syntax
@tailcall(return) foo(1,2,3); // doesn't require a new keyword but retains the function call syntax
return @tailcall(foo)(1,2,3); // doesn't require a new keyword but searching for 'foo(' won't find it.

[Vexu]

Note that the type signatures matching requirement is inherited directly from LLVM: llvm/llvm-project#54964

[dvmason]

Thanks, @Vexu for the comment... I've added a comment to that thread.

[dvmason]

I'm building a runtime and use tailcall extensively! The problem with debugging and tailcalls is that tracebacks aren't very useful... but I found a trick.

I've mildly complained about return @call(tailCall, afun, .{ ... before, but I've become a fan of this approach, because I define a constant:

pub const tailCall: std.builtin.CallModifier = if (show_error_stack) .never_inline else .always_tail;

and then use that in all of my tailcalls. Then, if I need traceback, I simply define show_error_stack to be true, and all my tailcalls become normal calls and show up in the traceback. I wish I could do something similar for inline - which I also use extensively - because they also mess with tracebacks (as they should!). So I remove the inline and add // INLINE as a comment on the line so I can find them all later and revert them.

[dvmason]

What would be very nice would be if inline functions could be called as tailcalls. Ideally it would check if the inlined function ended with a tailcall, but even if it didn't that would be fine. This would simplify a lot of my code.

[filasieno]

Sorry to revive a zombie thread.

I'm building a runtime and use tailcall extensively!

I'm doing the same for a project of mine.

@dvmason do you have any strategy to tail call functions that do not have the same parameters as the caller ?