safe recursion

[andrewrk]

Accepted Proposal

---

If we solve #157 then we'll know at compile-time the maximum stack usage of the entire call graph.

Except for recursion. Recursion - whether direct or indirect - represents a loop in the graph.

Here you can see indirect recursion B->C->E->D->B...

Recursion is problematic because it can happen a number of times that is only known at runtime, whereas the stack size is determined at compile-time. If too much recursion happens, we get stack overflow. Apart from being an annoying bug, stack overflow is a real concern for embedded software, which typically must resort to heuristics to find out just how small of a stack size they can get away with using.

But recursion is very useful. It's an intuitive way to reason about control flow. @Hejsil wrote zig's self-hosted parser without recursion, and it is not as straightforward as recursive programming.

So what do we do?

We have our cake and eat it, too. That's what we do.

Looking at the graph above again, we can have every function call in the graph be normal, except for D calling B. That's the only entrance into the cycle. So we can make there be a compile error for a normal function call from D to B. To make a function call which starts a cycle, you have to use a builtin:

const new_stack = try allocator.alloc(u8, @stackSize(function));
defer allocator.free(new_stack);
_ = @recursiveCall(new_stack, function, args);

It is a compile error to use @recursiveCall when you could have used a normal function call, and it is a compile error to use a normal function call when you must use @recursiveCall. So the compiler always tells you what to do.

I've prototyped how this would be emitted to LLVM using inline assembly, and I am talking to the LLVM mailing list to find out what's the best way to accomplish this. http://lists.llvm.org/pipermail/llvm-dev/2018-May/123217.html

There's another, simpler way we can have safe recursion, by limiting the amount of recursion at compile-time. This would be another builtin, that would look like this:

var cycles_left: usize = undefined;
_ = @limitedRecursiveCall(999, &cycles_left, function, args);
if (cycles_left == 0) @panic("recursion limit exceeded");

This would work the same way except instead of allocating memory on the heap, we specify the maximum number of cycles, and the function call fails if the cycle limit is exceeded. Then when calculating the stack upper bound, we multiply the cycle stack size by the recursion limit.

So you then would decide at compile time how much stack space you're going to ask for from the OS.

The benefit of this idea is that it actually does not depend on any changes to LLVM and we could implement it even before #157 is finished.

Until #105 is done we would have to specify the Recursive or LimitedRecursive calling convention on the first node getting called in the cycle (B in the picture).

[bnoordhuis]

Interesting proposal. Do I understand right that both builtins work (and can only work) under a closed world assumption?

How does @recursiveCall deal with function pointers? I saw mention of computing the set of all possible values but that seems (P-)hard.

About @limitedRecursiveCall, how is the counter propagated and what decrements it?

---

FWIW, I've been thinking along similar lines as @limitedRecursiveCall:

fn f(@rec n: usize) { if (n > 0) g(n-1); }
fn g(@rec n: usize) { if (n > 0) f(n-1); }

The idea being that the compiler knows n is special and "trivially" reduces on every call. Doesn't give a stack upper bound (at least not without further analysis) but it does guarantee termination with direct and indirect function calls and mutual recursion.

I'm using "trivially" kind of hand-wavy because I'm not sure what the compiler can trivially infer. There is probably something clever that can be done with comptime expressions.

[bheads]

This could be really cool if you can solve all the corner cases. How would the compiler handle allocating on the stack?

http://man7.org/linux/man-pages/man3/alloca.3.html

[andrewrk]

How would the compiler handle allocating on the stack?

@alloca in zig was removed and is not a supported use case: #225 (comment)

We will have a builtin function to annotate extra stack usage for the places we need it. For example if you use inline assembly to modify the stack pointer directly then you may need to use @annotateStackUsage(1234) with the number of bytes possibly used.

External functions could change the stack pointer in this way as well; external functions will support annotations to specify the stack usage upper bound per function.

I'm thinking about writing a tool which analyses binaries and disassembles functions to automatically compute these annotations.

[andrewrk]

About @limitedRecursiveCall, how is the counter propagated and what decrements it?

I didn't think this through very well. I'll have to re-think it. It would work for direct recursion where we can add secret parameters, but we wouldn't want to have to change the calling convention of every function in the cycle.

[kyle-github]

This is a hard problem to solve generally due to NP completeness.

That said, why not start small and work at this for a while?

For instance, rather than trying various constraints like recursion limits, just have checked stack allocation only for call graphs that do not have cycles.

Over time you either chip away at the various other cases or people start writing code for embedded systems that does not use recursion.

There is very little Zig code out there today and it seems like you may be trying to solve the problem without any solid data.

Put in the checks you need to double check actual usage in test blocks.

test " ensure stack size" { assert(@maxStack() < 1024); .... }

I am typing on a phone so I have no idea how this will get formatted!

The idea is that the built-in above would return usize and if there was any recursion at all would either panic or return the maximum usize value.

As more code is written and you see the patterns that are safe, then you can relax the constraints with more complicated and refined rules.

[andrewrk]

I did a proof of concept of this and it's now available for use: @newStackCall

This proof of concept means that, even though we don't have all the features done yet for safe recursion, the ideas will work. So recursion is OK to use, it's not evil, and the compiler will help you remove the possibility of stack overflow in a future version of zig.

What's left to do for this issue:

• Builtin function to tell you the maximum stack size of a given function #157
• compile error for recursion without @newStackCall
• runtime safety check for @newStackCall to make sure the stack given is big enough

the other day I was reading On Recursion, Continuations and Trampolines

... and looked up CPS were It says:

As CPS and TCO eliminate the concept of an implicit function return, their combined use can eliminate the need for a run-time stack. Several compilers and interpreters for functional programming languages use this ability in novel ways.

my gut feeling is that this can't be true, otherwise everyone would just do it, or there is some other major drawback hiding

[andrewrk]

The drawback of TCO is that you can't always do it. See #694

We have CPS in the form of coroutines and indeed it solves the recursion issue. I plan to revisit this issue with that in mind.