7 ms·

That warning doesn't ensure that there's no recursion, as the caveats point out. Indeed, it's trivial to show that ensuring there's no recursion is impossible a

That warning doesn't ensure that there's no recursion, as the caveats point out. Indeed, it's trivial to show that ensuring there's no recursion is impossible as long as you have function pointers. (This is also why languages that claim to be working on a solution to prevent recursion statically are going to fail.)

LegionMammal978 2y ago
In general, analysis becomes impossible when you have function pointers produced and used all over the place. But that doesn't have to be the case if the program is written deliberately to avoid the impossible cases. E.g., if you can separate the set of functions into "functions that (indirectly) are exported or have their address taken" and "functions that (indirectly) invoke a function pointer", then you know that there can't be any recursion through function pointers. Basically just a form of escape analysis. And if you're writing your own language, you can just have explicit 'colored' functions (and corresponding pointers), and enforce that the call graph between different colors has no cycles, and no function invokes a pointer of its own color. Generics would get a bit messy, but it's still far from impossible.
- PhilipRoman 2y ago
  You could probably restrict function pointer values with something like this: if(fptr == x || fptr == y) __builtin_unreachable() Or... if(fptr != z && fptr != w) __builtin_unreachable() But I'm not sure how well today's compilers can take advantage of this. You'd need a strict mode, where any function pointer is assumed to be the worst case. At that point might as well go for a real proof assistant
  - LegionMammal978 2y ago
    A more practical way (short of explicit language support) would be to have an enum and a dispatcher function: enum { CALL_Z, CALL_W }; int call_z_or_w(int which, int arg) { switch (which) { case CALL_Z: return z(arg); case CALL_W: return w(arg); default: __builtin_unreachable(); } } Or you could even do the same thing, but switching on the pointer value instead of an enum. Either way, this lets the compiler statically know where the call may possibly lead to.
- lmm 2y ago
  > E.g., if you can separate the set of functions into "functions that (indirectly) are exported or have their address taken" and "functions that (indirectly) invoke a function pointer", then you know that there can't be any recursion through function pointers. Basically just a form of escape analysis. Sure, in toy examples. But you can't actually do this in a nontrivial codebase that wasn't written to support it from the ground up. > And if you're writing your own language, you can just have explicit 'colored' functions (and corresponding pointers), and enforce that the call graph between different colors has no cycles, and no function invokes a pointer of its own color. Generics would get a bit messy, but it's still far from impossible. Everything is easy when you don't spend 5 minutes thinking about the possible problems with it, much less actually implement the idea you're proposing.
  - fc417fc802 2y ago
    He didn't say "easy", he said "far from impossible". > But you can't actually do this in a nontrivial codebase that wasn't written to support it from the ground up. In the case where this is considered critical for whatever reason, you absolutely could have a somewhat overzealous detector that failed the compilation if triggered. It doesn't need to support every last edge case. You would then address this just as you would any other compiler error - by remediating the failures one by one. If management doesn't want to pay you to do that then perhaps the requirement of "absolutely no recursion ever" wasn't actually so critical.
    - LegionMammal978 2y ago
      Yeah, if you're starting with, say, a heavily object-oriented program, then it would be nigh impossible. But I don't think it would even be extraordinarily difficult, if you start with a style that isn't suffused with dynamic function calls. E.g., languages like C++ and Rust with heavy monomorphization can have callbacks and other fun things without any vtables or function pointers. From an architectural standpoint, the main challenge is layering everything properly so you don't have any circular dependencies, even in untaken branches. Again, how hard this is to achieve depends on the original design, but it's not like circular-dependency-avoidance is something that no one's done before.

LegionMammal978 2y ago

In general, analysis becomes impossible when you have function pointers produced and used all over the place. But that doesn't have to be the case if the program is written deliberately to avoid the impossible cases. E.g., if you can separate the set of functions into "functions that (indirectly) are exported or have their address taken" and "functions that (indirectly) invoke a function pointer", then you know that there can't be any recursion through function pointers. Basically just a form of escape analysis. And if you're writing your own language, you can just have explicit 'colored' functions (and corresponding pointers), and enforce that the call graph between different colors has no cycles, and no function invokes a pointer of its own color. Generics would get a bit messy, but it's still far from impossible.

PhilipRoman 2y ago
You could probably restrict function pointer values with something like this: if(fptr == x || fptr == y) __builtin_unreachable() Or... if(fptr != z && fptr != w) __builtin_unreachable() But I'm not sure how well today's compilers can take advantage of this. You'd need a strict mode, where any function pointer is assumed to be the worst case. At that point might as well go for a real proof assistant
- LegionMammal978 2y ago
  A more practical way (short of explicit language support) would be to have an enum and a dispatcher function: enum { CALL_Z, CALL_W }; int call_z_or_w(int which, int arg) { switch (which) { case CALL_Z: return z(arg); case CALL_W: return w(arg); default: __builtin_unreachable(); } } Or you could even do the same thing, but switching on the pointer value instead of an enum. Either way, this lets the compiler statically know where the call may possibly lead to.
lmm 2y ago
> E.g., if you can separate the set of functions into "functions that (indirectly) are exported or have their address taken" and "functions that (indirectly) invoke a function pointer", then you know that there can't be any recursion through function pointers. Basically just a form of escape analysis. Sure, in toy examples. But you can't actually do this in a nontrivial codebase that wasn't written to support it from the ground up. > And if you're writing your own language, you can just have explicit 'colored' functions (and corresponding pointers), and enforce that the call graph between different colors has no cycles, and no function invokes a pointer of its own color. Generics would get a bit messy, but it's still far from impossible. Everything is easy when you don't spend 5 minutes thinking about the possible problems with it, much less actually implement the idea you're proposing.
- fc417fc802 2y ago
  He didn't say "easy", he said "far from impossible". > But you can't actually do this in a nontrivial codebase that wasn't written to support it from the ground up. In the case where this is considered critical for whatever reason, you absolutely could have a somewhat overzealous detector that failed the compilation if triggered. It doesn't need to support every last edge case. You would then address this just as you would any other compiler error - by remediating the failures one by one. If management doesn't want to pay you to do that then perhaps the requirement of "absolutely no recursion ever" wasn't actually so critical.
  - LegionMammal978 2y ago
    Yeah, if you're starting with, say, a heavily object-oriented program, then it would be nigh impossible. But I don't think it would even be extraordinarily difficult, if you start with a style that isn't suffused with dynamic function calls. E.g., languages like C++ and Rust with heavy monomorphization can have callbacks and other fun things without any vtables or function pointers. From an architectural standpoint, the main challenge is layering everything properly so you don't have any circular dependencies, even in untaken branches. Again, how hard this is to achieve depends on the original design, but it's not like circular-dependency-avoidance is something that no one's done before.