TECH Signal 390
Finally adding recursive functions to Futhark
↗
Illustration only Photo by Maarten Deckers on Unsplash
Futhark now supports recursive functions by moving recursion out of GPU kernels through flattening, after previously omitting them due to stack and memory constraints.
Engineers writing data-parallel array code can now express natural divide-and-conquer algorithms directly in Futhark instead of manually transforming them into loops. This reduces boilerplate and brings the language closer to other functional parallel models, while still preserving the guarantee that the generated GPU code remains stack-safe.
Written by elseif from the cluster below · every claim links back to a sourceThe three things worth knowing
Recursive functions were omitted because GPU threads have tiny stacks and cannot allocate memory dynamically, making recursion impractical in data-parallel kernels.
The new approach uses flattening to interchange recursion with map operations, executing recursive control flow on the CPU while the GPU handles the data-parallel parts.
Although recursion is now available, the language designers note it may see limited use because Futhark’s array-centric style and loop constructs already cover most needed patterns.
THE READ
What the cluster adds up to.
The change adds a general mechanism for recursion that works across all Futhark backends. When a function containing recursion appears inside a map, the flattening pass moves the recursive control flow outside the parallel region, so it runs on the CPU. This allows the GPU to execute only the data-parallel portion of the computation, preserving the original guarantee of stack-safe kernels.
Adopting this feature requires writing recursive functions in a form that can be flattened, typically as the body of a map over an array. There is no additional syntax to learn, but developers must ensure the recursion does not depend on GPU-specific resources or unbounded stack allocation on the CPU, otherwise the flattening step will fail or produce inefficient code.
The solution stops working for recursion that cannot be lifted out of a parallel context, such as recursive calls that appear inside a reduction or inside code that must stay on the GPU for performance reasons. In those cases the compiler will reject the program or fall back to an unoptimized path, and the programmer must rewrite the algorithm using loops or explicit stack management.
Historically, Futhark removed recursive functions in 2017 because early implementations crashed the compiler when used in unsuitable places. The language’s focus on arrays and loop constructs meant the absence of recursion was rarely felt, but the new flattening-based approach restores the ability to write divide-and-conquer algorithms naturally while still meeting the strict safety guarantees required for GPU execution.
Written by elseif from the cluster below · checked for specifics the sources never containedTHE CLUSTER