slang
slang copied to clipboard
Mechanisms to simplify bounded recursion
A user was noting that there are cases where they want to have the effect of recursion up to some bounded depth, despite current GPU shader compilation targets not supporting recursion.
This could be faked with preprocessor trickery. Here's a (bad) example of a bounded-recursive factorial function:
#define DEFINE_F(N,N_1) int f##N(int n) { if(n == 0) return 1 else return n * f##N_1(n-1); }
int f0(int n) { return 1; }
DEFINE_F(1,0)
DEFINE_F(2,1)
DEFINE_F(3,2)
Ignoring the fact that factorial is a terrible example to use in this case, this approach is also really mess and hard to work with (you can make it more readable by using #include
instead of macros, but the central problem is the same).
If we didn't care about the generality of the language, we could add a custom attribute that implements the kind of expansion above directly, e.g.:
int f_base(int n) { return 1; }
[sortOfRecursive(3,f_base)]
int f(int n) { if(n==0) return 1; else return n*f(n-1); }
In this case we are assuming that the sortOfRecursive
attribute will make three copies of f
, one for each requested recursion depth, and route calls from one level to the next lower, with f_base
being used as the level-0
definition.
This seems to be an implementable pattern (ignoring issues around mutally recursive calls for a second...), but it seems extremely magical in a way that doesn't sit well with me.
As a final option, if we have better support for parameters and operations that need to be compile-time evaluable (similar to C++ constexpr
) we could potentially just write the recursive version more directly (again, ignoring that factorial is a terrible example in this case):
int f_rec<let DEPTH : int>( int n)
{
constexpr if(DEPTH == 0)
{
return 1; // base case for recursive expansion
}
else
{
if(n == 0) return 1; else return n*f_rec<DEPTH-1>(n-1);
}
}
int f(int n) { return f_rec<3>(n); }
This last option seems to be the most appealing to me conceptually, since it is a more general-purpose feature. We'd have to see how many impediments there are to implementing something like a constexpr if
(assuming we can pick a syntax we are okay with).
Recursion in GLSL can be implemented using macros, so this can probably be done in Slang as well.
Going to move this to "not planned" for now until given other priorities --- if there's a clear use case that drives the need for this that could help cause us to revisit the prioritization though...