The biggest semantic mess in Futhark(futhark-lang.org)
futhark-lang.org
The biggest semantic mess in Futhark
https://futhark-lang.org/blog/2025-09-26-the-biggest-semantic-mess.html
9 comments
Designing programming languages is hard. I think every nontrivial programming language has at least a few "semantic messes"; even Scheme (R6RS) has a long specification with edge-cases (ex: https://www.r6rs.org/final/html/r6rs/r6rs-Z-H-6.html#node_se...). Meanwhile, C++ is a semantic mess that contains at least a few programming languages.
Any language designed by a large group of people, where the author no longer controls the roadmap turns into a semantic mess.
C++ has a couzy group of friends among mainstream languages, that share similar age.
C++ has a couzy group of friends among mainstream languages, that share similar age.
> Yet an expression such as cols (replicate 0 (replicate 3 0)) should still work (and evaluate to 3)
Denotational or operational semantics: pick one for your programming language and stick to it. The author (who I generally think is very smart) here is striving for denotational semantics (type level data) and trying to torture the operations into supplying the appropriate result. Operationally `cols (replicate 0 (replicate 3 0))` is 0 not 3. So now you have to bend over backwards and implement custom shape functions that not only return weird answers but have to be special cased AND context sensitive - ie without trying the language I'm 100% sure that
Denotational or operational semantics: pick one for your programming language and stick to it. The author (who I generally think is very smart) here is striving for denotational semantics (type level data) and trying to torture the operations into supplying the appropriate result. Operationally `cols (replicate 0 (replicate 3 0))` is 0 not 3. So now you have to bend over backwards and implement custom shape functions that not only return weird answers but have to be special cased AND context sensitive - ie without trying the language I'm 100% sure that
cols (replicate 0 "x")
cols (replicate 0 (replicate k "x"))
If I understand correctly,
cols (replicate 0 "x")
okay i guess you're right since
spoiler alert every single tensor/array/matrix/ML/AI compiler runs into this same problem. there is only one solution: a fixed op set with a fixed number of corresponding shape functions. and then your compiler tries to perform shape inference/propagation. sometimes it works and you can specialize for fixed sizes and sometimes it fails and you get "dynamic" or "unknown" dims in your shapes and you can't do anything. oh well that's life in a universe where the halting problem exists.
def cols [n] [m] 't (x: [n][m]t) : i64 = m
def replicate5 n x = replicate 5 x
cols (replicate5 0 (replicate5 3 0)) == 5
spoiler alert every single tensor/array/matrix/ML/AI compiler runs into this same problem. there is only one solution: a fixed op set with a fixed number of corresponding shape functions. and then your compiler tries to perform shape inference/propagation. sometimes it works and you can specialize for fixed sizes and sometimes it fails and you get "dynamic" or "unknown" dims in your shapes and you can't do anything. oh well that's life in a universe where the halting problem exists.
It is basically dependent types, but there is a specific and intentional omission (no true dependent products) that interacts with another feature (the ability to hide sizes) that ultimately causes the mess. I elaborated on it here: https://futhark-lang.org/blog/2025-09-26-the-biggest-semanti...
> if I had more experience implementing dependently typed languages, then perhaps I would not find it so weird, as it really just makes type constructors similar to functions, which they would be in a fully dependently typed language.
Yeah. I was screaming for most of this piece, because this all seems like standard dependently-typed stuff, and ironically enough implementing full dependent types would probably end up being easier than trying to handle this one feature as a special case.
Yeah. I was screaming for most of this piece, because this all seems like standard dependently-typed stuff, and ironically enough implementing full dependent types would probably end up being easier than trying to handle this one feature as a special case.
This is a poorly named language IMO, since Futhark is the name of Norse runes (which is what I thought this was about). Why do so many programming languages have to be named things that are hard to search for?