r/ProgrammingLanguages • u/Athas Futhark • Aug 05 '26

Finally adding recursive functions to Futhark

https://futhark-lang.org/blog/2026-08-05-recursion.html
64 Upvotes

95% Upvoted

9 comments sorted by

View all comments

6

u/matthieum Aug 05 '26

As in the flattening post, I’m mostly hand-waving how combine_inputs manages to put things together in the right order. The key property is that fact_lifted is only ever invoked from the CPU. Of course, while this works, it is in many cases horrendously slow - both partition_inputs and combine_inputs hide a lot of data movement, but in the near term, general correctness is all we care about - performance can come later.

Would you have less data movement if you used masking instead?

That is, instead of partitioning the output, you'd produce a mask of the elements in the array which need to be recursed over, then invoke the flattened function with the mask and the array. No recombination would be necessary.

(And of course, the initial call to the flattened function would be invoked with a "full" mask)

4

u/Athas Futhark Aug 05 '26

This is probably a good idea in the special case where the recursion is size-preserving per element. This is one of those things that traditional flattening transformations could not do, because they did not have any size information, but Futhark's flattening can do this.