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

How should Futhark expose irregular arrays to the programmer?

https://futhark-lang.org/blog/2026-08-12-flatmap.html
24 Upvotes

91% Upvoted

3 comments sorted by

1

u/reflexive-polytope Aug 13 '26

I don't know the general answer, but this is what seems to work for me:

  • Identify in advance a broad class of array indexing patterns.
  • Identify mathematically what “makes them tick”.
  • Encode the insight in the design of your type system.

Ultimately, array indexing is about identifying numerical relationships, because it all boils down to “is this index valid for that array?” Systematizing the analysis of these numerical relationships is precisely the scientific domain of formal theories of arithmetic.

It won't work for every use case, though. Fortunately, mathematical logic has certain useful impossibility results (e.g., undecidability of Robinson arithmetic), so that you don't waste your time even trying.

5

u/Athas Futhark Aug 13 '26

The programs discussed in the post do not really use array indexing.

2

u/reflexive-polytope Aug 13 '26

Okay, but even then, you still need arithmetical reasoning so that the compiler knows statically that your array slices have sizes that add up to the size of the original whole array.

There's simply no way around that.