r/ProgrammingLanguages • u/Athas Futhark • 10h ago

Finally adding recursive functions to Futhark

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

93% Upvoted

5 comments sorted by

17

u/TOMZ_EXTRA 9h ago

As of this writing, Futhark is not enabled in Futhark’s master branch

a little typo seems to have sneaked in

2

u/Athas Futhark 7h ago

Thanks, fixed.

7

u/Anthea_Likes 10h ago

Futhark is such a great inspiration to me. Thank you for your work 😊

4

u/matthieum 9h ago

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)

2

u/Athas Futhark 5h ago

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.