3 ms·

Futhark by example (2020)

125 points by tosh 6mo ago

ethanlipson 6mo ago
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.
- VorpalWay 6mo ago
  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.)
  - otabdeveloper4 6mo ago
    Yeah, C++ arrays are literally that.
    - deleted 6mo ago
      [deleted]
    - alpinisme 6mo ago
      Arrays are not dynamically sized though (handling runtime sizes) and don’t have efficient append/concat. The point of the dependent types is that you can have the type system track that concat creates an M+N length vector, sort preserves length (and adds a sorted guarantee that slice preserves), etc. Sure you can do a lot with templates, but that’s advanced templates not just “C++ arrays” in a throwaway “literally that” way.
  - ethanlipson 6mo ago
    I'm talking about cases where the array size is not known at compile time. For example, say the user passes in a list of numbers as command line arguments. Then we have argv: Vec<String, argc> If I want to map these to ints, then I'd like a compile-time guarantee that the resulting array nums: Vec<Int, argc> is the same length as argv. Lean and Idris can do this, but AFAIK no commonly used languages can. But unlike general dependent types, these are not hard to wrap one's head around and would save a lot of frustration, in my experience.
- itishappy 6mo ago
  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 6mo ago
  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 https://pyrefly.org/en/docs/tensor-shapes/#how-it-works
  - mathisfun123 6mo ago
    Shape functions and shape analysis are basically mundane infra in almost every ML compiler/language/DSL. https://mlir.llvm.org/docs/Dialects/ShapeDialect/ https://mlir.llvm.org/docs/Dialects/ShapeDialect/
    - ainch 6mo ago
      I didn't know that, thanks for sharing. It makes sense, but then it also makes me wonder why none of the deep learning libraries (Torch, Jax/NNX, Eigen etc...) make this information available. Instead, ML people all have their own schemes for tracking shape information, like commenting '# (b, n, t)' on every line, or suffixing shapes to variable names - and in my experience it's a common source of bugs.
      - mathisfun123 6mo ago
        > Torch, Jax Both of these "make it available". Just because people don't know how to use/find them doesn't mean they're not "available". > Eigen This is not an ML anything, it's a linear algebra library. > like commenting '# (b, n, t)' on every line, or suffixing shapes to variable names There's a difference between tracking shapes in the compiler and specifying shapes in the model.
        ainch 6mo ago
        I think we're talking at cross purposes. The reason I'm excited about the Pyrefly work is that it leverages the type system to infer array shapes statically, which makes it simpler to reason about them when you're writing the code and catch bugs. The fact that people have developed these janky approaches to shape tracking suggests that there's a gap to be filled. Jax and Torch don't do that statically. They obviously have to do it at runtime, but that doesn't address this particular issue. I mention Eigen because array shape hinting is generally useful for any linalg library, not purely for ML applications.
- deleted 6mo ago
  [deleted]
rowanG077 6mo ago
Futhark is pretty great! And I have to say that the maintainer is insanely quick. It has happened on more than one occasion that I reported a bug and it's solved within the day. I have been using Futhark in prod for two years now and never had serious problems.
- Reefersleep 6mo ago
  What is your use case?
- keyle 6mo ago
  Interesting, what do use it for if you can share?
  - rowanG077 6mo ago
    Optimization algorithms. The build in automatic differentiation is great!.
Ferret7446 6mo ago
It would be nice to not name your language after another language. (Yes I know it's a script, that doesn't change my point). I came here expecting something else.
- echoangle 6mo ago
  TIL: https://en.wikipedia.org/wiki/Runes#Runic_alphabets https://en.wikipedia.org/wiki/Runes#Runic_alphabets
- jgrowl 6mo ago
  Jackson Crawford's youtube channel is very helpful academic source. For those that don't know, Futhark is comes from the first 6 letters of the runic alphabet (F, U, Þ, A, R, K) https://www.youtube.com/@JacksonCrawford https://www.youtube.com/@JacksonCrawford
- finaard 6mo ago
  Same here, I was very confused for a bit.
- hmry 6mo ago
  Yeah, when naming your language, it's important to keep mind the expectations of people seeing headlines about articles about your language on blog aggregation sites :^) Now I'm thinking about "Smalltalk by Example" and "Slang by Example"
fulafel 6mo ago
Futhark is a glimmer of light in the wasteland of C/C++ styled low level GPU languages.
- pjmlp 6mo ago
  We also need to have StarLisp back, it would be quite fitting.
guessmyname 6mo ago
Couldn’t have chosen a more difficult (and ambiguous) name to pronounce, could you? It almost sounds like a curse that I often hear people say out in the bad streets of New York City.
- antran22 6mo ago
  Elder [0] and Younger [1] Futhark (or Fuþark) are the name of two runic writing systems used by Germanic and Scandinavian Vikings. The name Futhark is a combination of the first 6 runes /f/, /u/, /ð/, /ɑ/, /r/, and /k/. Similar to how you get the name "alphabet" from the first two letters of Greek's writing system. [0]: https://en.wikipedia.org/wiki/Elder_Futhark https://en.wikipedia.org/wiki/Elder_Futhark [1]: https://en.wikipedia.org/wiki/Younger_Futhark https://en.wikipedia.org/wiki/Younger_Futhark
- jrave 6mo ago
  i had only skimmed this link and not even wondered about the name - but learned the meaning serendipitously within 2 minutes when it popped up in the OTHER hackernews link i had opened: https://news.ycombinator.com/item?id=48118478 https://news.ycombinator.com/item?id=48118478 which links to https://en.wikipedia.org/wiki/England_runestones https://en.wikipedia.org/wiki/England_runestones Futhark appears in the first paragraph! i don't think i ever read the term before
antran22 6mo ago
Was expecting to see some examples of how to read runes, but I am nonetheless equally satisfied. https://en.wikipedia.org/wiki/Elder_Futhark https://en.wikipedia.org/wiki/Elder_Futhark
- CapricornNoble 6mo ago
  Same. Thought I had a copy of Uthark [1][2] on my shelf too but alas I seem to have only retained Svartkonst [3] during the tragic downsizing of my library. [1] https://archive.org/details/karlsson-thomas-uthark-nightside-of-the-runes-2002 https://archive.org/details/karlsson-thomas-uthark-nightside... [2] https://www.84cxrarebooks.com/pages/books/090763/t-ketola-thomas-karlsson/uthark-nightside-of-the-runes https://www.84cxrarebooks.com/pages/books/090763/t-ketola-th... [3] https://www.miskatonicbooks.com/product/thursakyngi-iv-svartkonst-by-ekotu-hardcover-edition-import/ https://www.miskatonicbooks.com/product/thursakyngi-iv-svart...
lucb1e 6mo ago
I was so confused by the word factorial in the first example for a language, but decided to click it and just see what it means Turns out, Futhark != https://en.wikipedia.org/wiki/Futhark https://en.wikipedia.org/wiki/Futhark (runes, old germanic alphabet) That's like calling your programming language Latin?! The title could use some disambiguation...
- WJW 6mo ago
  Eh. Words get overloaded all the time and this is a website focusing on programming after all. Would you consider "Python by example" or "C by example" to need disambiguation because they're not about snakes or about the third letter of the alphabet? Also the very first line on that page is "The Futhark Programming Language" so if you were still confused after that I think it's on you.
  - lucb1e 6mo ago
    If Python were the language spoken in Fictionastan then yes, and C is indeed even more terrible than something like Golang but that predates the internet so it's pretty searchable after all > if you were still confused after that I think it's on you Generally the point of a title (if the domain name doesn't already do it) is to help you understand what it's about so you know whether to click. If it takes a click to read the explanation before you can know whether you're interested, all links on the HN homepage might as well have no string at all and just be "click here to find out what the link is about"
- hnarn 6mo ago
  > That's like calling your programming language Latin?! More accurately it would be like calling it Alphabet, since that takes its name from Alpha Beta (AB) just like the Futhark takes its name from the first letters in it.
- pseudohadamard 6mo ago
  It is a pretty confusing name. Personally I'm waiting for someone to name a programming language Womble. Underground, overground, you're free to use it as long as you work as a team and are tidy and clean.

125 points by tosh 6mo ago

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.

VorpalWay 6mo ago
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.)
- otabdeveloper4 6mo ago
  Yeah, C++ arrays are literally that.
  - deleted 6mo ago
    [deleted]
  - alpinisme 6mo ago
    Arrays are not dynamically sized though (handling runtime sizes) and don’t have efficient append/concat. The point of the dependent types is that you can have the type system track that concat creates an M+N length vector, sort preserves length (and adds a sorted guarantee that slice preserves), etc. Sure you can do a lot with templates, but that’s advanced templates not just “C++ arrays” in a throwaway “literally that” way.
- ethanlipson 6mo ago
  I'm talking about cases where the array size is not known at compile time. For example, say the user passes in a list of numbers as command line arguments. Then we have argv: Vec<String, argc> If I want to map these to ints, then I'd like a compile-time guarantee that the resulting array nums: Vec<Int, argc> is the same length as argv. Lean and Idris can do this, but AFAIK no commonly used languages can. But unlike general dependent types, these are not hard to wrap one's head around and would save a lot of frustration, in my experience.
itishappy 6mo ago
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 6mo ago
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 https://pyrefly.org/en/docs/tensor-shapes/#how-it-works
- mathisfun123 6mo ago
  Shape functions and shape analysis are basically mundane infra in almost every ML compiler/language/DSL. https://mlir.llvm.org/docs/Dialects/ShapeDialect/ https://mlir.llvm.org/docs/Dialects/ShapeDialect/
  - ainch 6mo ago
    I didn't know that, thanks for sharing. It makes sense, but then it also makes me wonder why none of the deep learning libraries (Torch, Jax/NNX, Eigen etc...) make this information available. Instead, ML people all have their own schemes for tracking shape information, like commenting '# (b, n, t)' on every line, or suffixing shapes to variable names - and in my experience it's a common source of bugs.
    - mathisfun123 6mo ago
      > Torch, Jax Both of these "make it available". Just because people don't know how to use/find them doesn't mean they're not "available". > Eigen This is not an ML anything, it's a linear algebra library. > like commenting '# (b, n, t)' on every line, or suffixing shapes to variable names There's a difference between tracking shapes in the compiler and specifying shapes in the model.
      - ainch 6mo ago
        I think we're talking at cross purposes. The reason I'm excited about the Pyrefly work is that it leverages the type system to infer array shapes statically, which makes it simpler to reason about them when you're writing the code and catch bugs. The fact that people have developed these janky approaches to shape tracking suggests that there's a gap to be filled. Jax and Torch don't do that statically. They obviously have to do it at runtime, but that doesn't address this particular issue. I mention Eigen because array shape hinting is generally useful for any linalg library, not purely for ML applications.
deleted 6mo ago
[deleted]

rowanG077 6mo ago

Futhark is pretty great! And I have to say that the maintainer is insanely quick. It has happened on more than one occasion that I reported a bug and it's solved within the day. I have been using Futhark in prod for two years now and never had serious problems.

Reefersleep 6mo ago
What is your use case?
keyle 6mo ago
Interesting, what do use it for if you can share?
- rowanG077 6mo ago
  Optimization algorithms. The build in automatic differentiation is great!.

Ferret7446 6mo ago

It would be nice to not name your language after another language. (Yes I know it's a script, that doesn't change my point). I came here expecting something else.

echoangle 6mo ago
TIL: https://en.wikipedia.org/wiki/Runes#Runic_alphabets https://en.wikipedia.org/wiki/Runes#Runic_alphabets
jgrowl 6mo ago
Jackson Crawford's youtube channel is very helpful academic source. For those that don't know, Futhark is comes from the first 6 letters of the runic alphabet (F, U, Þ, A, R, K) https://www.youtube.com/@JacksonCrawford https://www.youtube.com/@JacksonCrawford
finaard 6mo ago
Same here, I was very confused for a bit.
hmry 6mo ago
Yeah, when naming your language, it's important to keep mind the expectations of people seeing headlines about articles about your language on blog aggregation sites :^) Now I'm thinking about "Smalltalk by Example" and "Slang by Example"

fulafel 6mo ago

Futhark is a glimmer of light in the wasteland of C/C++ styled low level GPU languages.

pjmlp 6mo ago
We also need to have StarLisp back, it would be quite fitting.

guessmyname 6mo ago

Couldn’t have chosen a more difficult (and ambiguous) name to pronounce, could you? It almost sounds like a curse that I often hear people say out in the bad streets of New York City.

antran22 6mo ago
Elder [0] and Younger [1] Futhark (or Fuþark) are the name of two runic writing systems used by Germanic and Scandinavian Vikings. The name Futhark is a combination of the first 6 runes /f/, /u/, /ð/, /ɑ/, /r/, and /k/. Similar to how you get the name "alphabet" from the first two letters of Greek's writing system. [0]: https://en.wikipedia.org/wiki/Elder_Futhark https://en.wikipedia.org/wiki/Elder_Futhark [1]: https://en.wikipedia.org/wiki/Younger_Futhark https://en.wikipedia.org/wiki/Younger_Futhark
jrave 6mo ago
i had only skimmed this link and not even wondered about the name - but learned the meaning serendipitously within 2 minutes when it popped up in the OTHER hackernews link i had opened: https://news.ycombinator.com/item?id=48118478 https://news.ycombinator.com/item?id=48118478 which links to https://en.wikipedia.org/wiki/England_runestones https://en.wikipedia.org/wiki/England_runestones Futhark appears in the first paragraph! i don't think i ever read the term before

antran22 6mo ago

Was expecting to see some examples of how to read runes, but I am nonetheless equally satisfied. https://en.wikipedia.org/wiki/Elder_Futhark https://en.wikipedia.org/wiki/Elder_Futhark

CapricornNoble 6mo ago
Same. Thought I had a copy of Uthark [1][2] on my shelf too but alas I seem to have only retained Svartkonst [3] during the tragic downsizing of my library. [1] https://archive.org/details/karlsson-thomas-uthark-nightside-of-the-runes-2002 https://archive.org/details/karlsson-thomas-uthark-nightside... [2] https://www.84cxrarebooks.com/pages/books/090763/t-ketola-thomas-karlsson/uthark-nightside-of-the-runes https://www.84cxrarebooks.com/pages/books/090763/t-ketola-th... [3] https://www.miskatonicbooks.com/product/thursakyngi-iv-svartkonst-by-ekotu-hardcover-edition-import/ https://www.miskatonicbooks.com/product/thursakyngi-iv-svart...

lucb1e 6mo ago

I was so confused by the word factorial in the first example for a language, but decided to click it and just see what it means Turns out, Futhark != https://en.wikipedia.org/wiki/Futhark https://en.wikipedia.org/wiki/Futhark (runes, old germanic alphabet) That's like calling your programming language Latin?! The title could use some disambiguation...

WJW 6mo ago
Eh. Words get overloaded all the time and this is a website focusing on programming after all. Would you consider "Python by example" or "C by example" to need disambiguation because they're not about snakes or about the third letter of the alphabet? Also the very first line on that page is "The Futhark Programming Language" so if you were still confused after that I think it's on you.
- lucb1e 6mo ago
  If Python were the language spoken in Fictionastan then yes, and C is indeed even more terrible than something like Golang but that predates the internet so it's pretty searchable after all > if you were still confused after that I think it's on you Generally the point of a title (if the domain name doesn't already do it) is to help you understand what it's about so you know whether to click. If it takes a click to read the explanation before you can know whether you're interested, all links on the HN homepage might as well have no string at all and just be "click here to find out what the link is about"
hnarn 6mo ago
> That's like calling your programming language Latin?! More accurately it would be like calling it Alphabet, since that takes its name from Alpha Beta (AB) just like the Futhark takes its name from the first letters in it.
pseudohadamard 6mo ago
It is a pretty confusing name. Personally I'm waiting for someone to name a programming language Womble. Underground, overground, you're free to use it as long as you work as a team and are tidy and clean.