Call eval on UDF arguments which are indices in UDF bodies

[WardBrian]

Closes https://github.com/stan-dev/stanc3/issues/1224

Submission Checklist

• [x] Run unit tests
• Documentation
  • [x] OR, no user-facing changes were made

Release notes

Fix an issue where recursive functions which called themselves with a slice of their arguments would lead to infinite template expansion in C++ compilation.

Copyright and Licensing

By submitting this pull request, the copyright holder is agreeing to license the submitted work under the BSD 3-clause license (https://opensource.org/licenses/BSD-3-Clause)

[WardBrian]

I went with the safe but possibly over-eager choice to evaluate whenever a function call in a function body has the same name as the function itself. As noted in the test and in the discussion in #1224, this is not necessarily a recursive call in the context of overloading.

So, this may produce a few extra calls to eval than it needs to.

[nhuurre]

So, this may produce a few extra calls to eval than it needs to.

Unfortunately this misses mutually recursive functions.

functions {
vector test3(vector gamma);
vector test2(vector gamma);
 vector test2(vector gamma) {
   int D = num_elements(gamma);

   if (D == 1)
      return rep_vector(D, 0);
    else
      return test3(gamma[1:D - 1]);
  }
vector test3(vector gamma) {
  return test2(gamma);
}
}
data {
  int N;
  int times;
}
parameters {
  vector[times] gamma;
}
transformed parameters {
  vector[N] z_hat = test2(gamma);
}

[WardBrian]

Yes, it does. I don't think there's any good way around that short of re-implementing most of the C++ compiler's template resolution pass? Or we could eval all indexed arguments to UDF calls within UDFs.

Even if we don't fix the mutually recursive case, I think this change is still an improvement relative to the current behavior

[WardBrian]

Updated to

1) handle void functions

2) Call eval on every indexed argument to a UDF when inside a UDF, to handle possible mutual recursion. My guess is that this is probably not a super common edge case so I don't mind going for the safe option here.

[nhuurre]

Fixing it fully is indeed difficult and even a partial solution is an improvement, yes. eval()ing every UDF call at least avoids the terrible C++ errors. How much does eval() impact performance?

I think the ideal solution would be to do a topological sort and build a DAG whose vertices are functions and edges are calls, and if there are cycles then break them by inserting eval()s.

[WardBrian]

I think the expense of eval will vary depending on the usage. In the simplest of cases, say where the function only cares about the length of the vector but not the values, it will be doing an extra copy each time as a result of the eval. But (I believe, anyway) if the function is doing essentially anything nontrivial it will eventually evaluate the argument anyway

@rok-cesnovar or @SteveBronder may be able to say more about this

[bob-carpenter]

How much does eval() impact performance?

Eigen uses the RAII pattern, so an eval will cause an allocation and copy. So both memory and CPU pressure.

But (I believe, anyway) if the function is doing essentially anything nontrivial it will eventually evaluate the argument anyway

Eigen will only implicitly evaluate an argument if it decides it's more efficient that way. Typical uses that only access values once, like a dot product, won't force an eval.

[WardBrian]

In the short term I think the extra evals are a worthwhile tradeoff for safety. I expect this is probably not super commonly written code by users where UDFs are calling other UDFs with slices of eigen types.

We can later try a more sophisticated analysis as to when they are necessary. I think the proposal @nhuurre makes for that is the correct approach, but implementing that would be nontrivial.

[WardBrian]

I think my latest commit will be the happy-middle of the current options. I've restricted the extra evals to only be applied to functions who have forward declarations. This will catch all functions which could end up being recursive or mutually recursive (at least until we did something like https://github.com/stan-dev/stanc3/issues/976), but won't affect the vast majority of UDFs.

[WardBrian]

@nhuurre thoughts on the current state of this?

I discussed with @rok-cesnovar and we are going to do a minor release with just the recent stanc bug fixes (hopefully including this), Cherry-picking around the to_int and new warnings