logoalt Hacker News

ethanlipson • yesterday at 10:42 AM • 4 replies • view on HN

Futhark is really such a great idea. I'm not convinced that dependent types are worth the cognitive overhead in general, but it's definitely worth it to include the length as part of the type information for dynamic arrays, e.g.:

  concat(Vec<T, n>, Vec<T, m>) -> Vec<T, n+m>
  matmul(Mat<T, n, m>, Mat<T, m, l>) -> Mat<T, n, l>
  head(Vec<T, n+1>) -> (T, Vec<T, n>)
This would have saved me so much headache debugging CUDA kernels and numpy!! I wish it were a first-class feature in those frameworks, and even general-purpose languages, but alas.

Replies

itishappy • yesterday at 2:27 PM

Here they are in Futhark:

    val concat [n] [m] 't : (xs: [n]t) -> (ys: [m]t) -> *[n + m]t
    val matmul [n] [m] [l] 't : (xs: [n][m]t) -> (ys: [m][l]t) -> *[n][l]t
    val head [n] 't : (x: [n]t) -> t
And here's the pathological case (length cannot be determined at compile time):

    val filter [n] 'a : (p: a -> bool) -> (as: [n]a) -> *[]a
Other pathological cases include conditionals and loops.
ainch • yesterday at 5:21 PM

The Pyrefly type checker is starting to work on this kind of shape hinting - so far it only works on Torch but I believe the plan is for it to work with other array packages (eg. JAX, NumPy)

https://pyrefly.org/en/docs/tensor-shapes/#how-it-works

➕ show 2 replies
VorpalWay • yesterday at 12:02 PM

You can do this with templates in C++ and generics in Rust I'm pretty sure. I think the Eigen C++ library supports this. (I have yet to do a linear algebra heavy Rust project, so I can't speak to the options that exist there.)

➕ show 2 replies