Cannot infer return type for simple recursive function with literal base case

[DanilaFe]

Chapel can't infer the return type of the following function:

proc fib(x: int) {
    if x <= 1 then return 1;
    return fib(x - 1) + fib(x - 2);
}

writeln(fib(0..#20));

This is odd considering there's a clear, not-param-elided return statement at the very top. The above prints:

fib.chpl:1: error: unable to resolve return type of function 'fib'
fib.chpl:1: In function 'fib':
fib.chpl:3: error: called recursively at this point

[bradcray]

A long-time complaint from users. I don't know of an inherent reason this is and suspect we were just lazy, scared, or short on time when implementing return type resolution originally.

[cassella]

This seems pretty comparable to the second example in #12755

[mppf]

I wanted to check if the new resolver did any better, but unfortunately it runs into an internal error:

operator <=(lhs: int, rhs: int): bool {
  return __primitive("<=", lhs, rhs);
}
operator +(lhs: int, rhs: int): int {
  return __primitive("+", lhs, rhs);
}
operator -(lhs: int, rhs: int): int {
  return __primitive("-", lhs, rhs);
}

proc fib(x: int) {
    if x <= 1 then return 1;
    return fib(x - 1) + fib(x - 2);
}

$ ./build/frontend-test/resolution/testInteractive bb.chpl
...
Error: recursion encountered in query resolveFunctionByInfoQuery

If we specify the return type of fib then it does compile.

It'd be good to adjust the new resolver to handle this case better (whether it is giving an error message like production or inferring the return type of fib as int in this case).

[damianmoz]

You see the problem even with a non-literal base.

proc fib(x: int)
{
    const v = 1:int;

    if x <= 1 then
        return v;

    return fib(x - 1) + fib(x - 2);
}

proc main
{
    writeln(fib(89));
    return(0);
}

The solution does not look easy. In the last line of fib(), you are asking the compiler to deduce the type without knowing the type. Personally I regard type deduction within a proc as an bonus benefit and use it only as a way to simplify the code. For recursive routines, why not just inform the user that the type needs to be specified. I would not consider that a burden but then I hardly ever use recursion in my HPC programming which is dominated by linear algebra routines.

[damianmoz]

Apologies for hitting comment too early and having an unfinished sentence with cut-and-past rubbish towards the end of the original post. I got interrupted by a phone call when I was deep in thought and the finger-brain co-ordination suffered catastrophic failure as I got shocked back into dealing with reality.

[bradcray]

@damianmoz : I don't think Daniel was implying that non-param bases are supported; more like "even cases that are as simple and self-evident as a param don't work—why not?"

I don't see your case (or Daniel's) as being particularly difficult given that Chapel procedures must have a single return type along all reachaable paths. The way I would approach it is:

• ignore all return statements whose expressions rely on a recursive call
• compute the return type in the normal way by considering the expression types of all other return statements
• assume that is the return type of the procedure
• resolve the procedure normally and if any of the recursive calls cause problems, issue an error (i.e., don't try to unify return types between the recursive and base-case calls).

In your example, this means:

• First we'd ignore the final return statement
• Focusing on the rest of the code, we'd determine that v is an int and that since we're returning v, we'll conjecture that the return type is int
• Then we'll resolve the whole procedure, filling in int for the recursive calls, determine that int + int is int, so the recursive branch is also returning int, so the program is legal

For recursive routines, why not just inform the user that the type needs to be specified.

This is effectively what we've been doing since the outset, and it's not unreasonable, but it also seems inconsistent with the rest of the language. And sometimes, it can make routines somewhere between difficult and impossible to write—I seem to recall that writing recursive routines that return arrays was a major problem for some users in the past (and may still be).