Finally adding recursive functions to Futhark

Futhark, an unusual functional language, has not supported recursive functions until now. This absence is not due to a disdain for recursion, as the language's compiler contains numerous recursive definitions. Instead, the reason lies in the difficulty of compiling recursive functions across all positions on every backend. Futhark prefers to make promises it can keep, hence the delay.

Recursion has been a contentious issue since Futhark's inception. The language is hardware-agnostic and data parallel, which complicates the implementation of recursive functions, especially on GPUs where threads have tiny stacks and memory allocation is impractical within GPU code. Additionally, the total memory requirements for recursive functions depend on dynamic control flow decisions, making pre-allocation a challenge.

Despite the complexities, Futhark's compiler backends for CPUs handle recursion smoothly. However, allowing recursion on GPU targets necessitates composing language restrictions from all supported compiler targets, a task complicated by the desire for orthogonality and the inability to predict future machines and functions.

Futhark's core datatype (arrays) is not inductive, limiting the scope of recursion. The language provides loop syntax for tail recursion, though it does not plan to support actual tail call optimization. Nevertheless, recursion proves useful in divide-and-conquer algorithms, many of which are awkward to express in Futhark and require manual transformation.

To address this, the solution lies in flattening. By flattening an expression map f xs where f contains recursion, the recursion is effectively moved outside of parallel code sections. For instance, a simple recursive function, like the factorial function, can be transformed to operate on an array instead of a single value. This lifted function simulates a single iteration of the recursion and performs recursive calls with remaining elements that haven't reached the base case.

While flattening offers a general solution for recursion, it is primarily necessary for GPU backends. The process introduces significant data movement, which may result in slow performance initially. However, the focus remains on general correctness, with performance improvements to follow.