5 ms·

It's astonishing how hard "modern" PL find it to implement parametric polymorphism. Java got it wrong and C# did at least have a hard time. I don't want to talk

It's astonishing how hard "modern" PL find it to implement parametric polymorphism. Java got it wrong and C# did at least have a hard time. I don't want to talk about what C++ did. Go needed years for that feature and now has problems with type constraints (I am not a go expert, though. Maybe these constraints aren't related to their generics?). So far, Rust seems to have gotten it right by essentially copying Haskell. Is it pride that let's "industry" languages ignore decades of PL theory and research? The "design by committee" problem? Or something else entirely?

morelisp 4y ago
Don't Rust and Haskell "solve" this by just copping to an NP-hard compilation task and trying to do it anyway?
- pas 4y ago
  The usual way is to add a lot of special case heuristic for it, hope those work, and if they don't then bail out. (Report an error to the developer, so then they can nudge the types a bit an hope to find a setup where one of the heuristics work.) And it's fine if the error messages are helpful, but this added implicit complexity to the language rightly gives folks the heebie-jeebies (se the recent comments for Rust's GAT patches)
  - orlp 4y ago
    As an N=1 sample point, I've programmed in Rust for years now, extensively using generics, and have not once ran into this issue. NP-hardness only shows the worst case is really difficult. It does not mean that an approach is not useful. For example, Rust's exhaustive pattern matching is also technically NP-hard: https://niedzejkob.p4.team/rust-np/ https://niedzejkob.p4.team/rust-np/
  - morelisp 4y ago
    Yeah, I don't mean to criticize the approach taken by other languages at all. Programmers want powerful type systems and fast compilation times and good error messages, and unfortunately this is one of the cases where things are really fundamentally, mathematically provably, at odds with each other in PL ergonomics. It's a wicked problem, not one you can "get it right". But these "Go's ignoring decades of PL research!" comments are, at best, tiresome even when somewhat true. In this case it's the outright opposite.
vmception 4y ago
Not pride, just little consequence. Its not academia, the grade is getting fast funding or revenue because any language is fine and any performance is good enough because the bottlenecks are somewhere else or irrelevant
mseepgood 4y ago
No, Rust and Haskell didn't solve the NP-completeness problem, which to avoid this is all about.
deleted 4y ago
[deleted]
Laremere 4y ago
Philip Walder, who contributed to the design of Haskell (according to wikipedia, haven't dug deep here) worked with the Go developers on a PL theory underpinning for Go's generics: https://arxiv.org/abs/2005.11710 https://arxiv.org/abs/2005.11710 So, in fact, industry didn't ignore PL theory and research at all.
- cinntaile 4y ago
  Tiny nitpick but it's Wadler, not Walder. Maybe you knew this and it was just a typo.
  - Laremere 4y ago
    Ah, was a typo. Can't edit anymore but thanks for the catch!
deleted 4y ago
[deleted]
comex 4y ago
Every language has its own design features that end up influencing its generics system. Java has subtyping (in the form of class inheritance). Rust has lifetimes and linear types. Go has its ‘structurally typed’ interfaces (which are the reason impossible combinations of constraints exist in the first place). Haskell has none of those, but it has plenty of other features that at least historically caused exponential compilation time [1] and unsoundness [2]. Even C++ arguably falls into that category to an extent. Its template system definitely could have been designed better, and using Haskell-like type signatures like Rust does is arguably a better approach… but Rust trait signatures tend to be more complex and less elegant than Haskell ones, because the simple and elegant ones have runtime overhead that Rust, like C++, isn’t willing to accept. (For example, see functions being a trait as opposed to a type.) And even Rust struggles to match C++ in metaprogramming expressivity, which also helps C++ reduce runtime overhead. Upcoming Rust features like `const fn` and specialization will help with that, but both have been ‘upcoming’ for many years… [1] https://news.ycombinator.com/item?id=8130487 https://news.ycombinator.com/item?id=8130487 [2] https://gitlab.haskell.org/ghc/ghc/-/issues/7148 https://gitlab.haskell.org/ghc/ghc/-/issues/7148
fnord123 4y ago
To go with sibling's comment, Wadler also had a hand in designing Java's generics while Guy Steele was a co-author of the Java Language Specification. And the idea that Eric Meijer ignored PL research is just mistaken. Instead of belly aching about everyone who did it wrong, why not explain what is wrong and why you think so. I mean, I think think Rust didn't do it perfect because I often want to use Box<dyn MyTrait> which is a hassle because I need to mark every function ?Sized if I want to pass a reference to my `x: &T...where T: MyTrait + ?Sized` and I don't enjoy that.
- cpurdy 4y ago
  Additionally, Josh's first generics implementation in Java was reified (like C#), but the necessary JVM changes were delayed, so he had to quickly do a second implementation using erasure. Sometimes, reality bites.
  - fnord123 4y ago
    One of Java's original goals was to work in embedded systems. As such, I think type erasure actually is helpful to reduce the size of compiled artefacts because you haven't monomorphised functions - hence avoiding potential bloat. As in all of engineering, most things are a tradeoff.
    - monocasa 4y ago
      The other proposals I've heard for Java generics didn't monomorphize at compile time but instead modified the .class format to represent generic classes/methods closer to their source representation. Because the embedded systems at the time that cared about code size in Java would have been structured as bytecode interpreters, they arguably would have had smaller binaries without type erasure. The casts the erasure does under the hood are represented as additional bytecode at most call sites, but would have been implicit if generic functions had first class JVM support.
duped 4y ago
No it's just ignorance. PL design is just one of the few areas where academia leads industry by a wide margin in understanding how to design compilers and type systems. Where academia lags and why these features fail to make it into production languages is that industry needs working compilers, build systems, debuggers, package managers, and linters more than it needs any kind of static typing. The other problem is incentive and design approach. The academic approach to PL design is to carefully develop the type system and understand the way the rules interact, proving things like soundness, decidability, etc. the industry approach to software development is MVP. These two approaches are incompatible and lead to different language designs, because you can't slap a carefully designed system on top of a recklessly developed MVP that has been bumped incrementally over a long time. At least not without major time consuming rewrites.
Merovius 4y ago
> So far, Rust seems to have gotten it right by essentially copying Haskell. FWIW I've used Rust for a bit and I disagree that they "got it right". I'm not saying Rust is bad, I like the language. But it's not as if their generics implementation does not have issues. It's just that they are different issues.

morelisp 4y ago

Don't Rust and Haskell "solve" this by just copping to an NP-hard compilation task and trying to do it anyway?

pas 4y ago
The usual way is to add a lot of special case heuristic for it, hope those work, and if they don't then bail out. (Report an error to the developer, so then they can nudge the types a bit an hope to find a setup where one of the heuristics work.) And it's fine if the error messages are helpful, but this added implicit complexity to the language rightly gives folks the heebie-jeebies (se the recent comments for Rust's GAT patches)
- orlp 4y ago
  As an N=1 sample point, I've programmed in Rust for years now, extensively using generics, and have not once ran into this issue. NP-hardness only shows the worst case is really difficult. It does not mean that an approach is not useful. For example, Rust's exhaustive pattern matching is also technically NP-hard: https://niedzejkob.p4.team/rust-np/ https://niedzejkob.p4.team/rust-np/
- morelisp 4y ago
  Yeah, I don't mean to criticize the approach taken by other languages at all. Programmers want powerful type systems and fast compilation times and good error messages, and unfortunately this is one of the cases where things are really fundamentally, mathematically provably, at odds with each other in PL ergonomics. It's a wicked problem, not one you can "get it right". But these "Go's ignoring decades of PL research!" comments are, at best, tiresome even when somewhat true. In this case it's the outright opposite.

vmception 4y ago

Not pride, just little consequence. Its not academia, the grade is getting fast funding or revenue because any language is fine and any performance is good enough because the bottlenecks are somewhere else or irrelevant

mseepgood 4y ago

No, Rust and Haskell didn't solve the NP-completeness problem, which to avoid this is all about.

deleted 4y ago

[deleted]

Laremere 4y ago

Philip Walder, who contributed to the design of Haskell (according to wikipedia, haven't dug deep here) worked with the Go developers on a PL theory underpinning for Go's generics: https://arxiv.org/abs/2005.11710 https://arxiv.org/abs/2005.11710 So, in fact, industry didn't ignore PL theory and research at all.

cinntaile 4y ago
Tiny nitpick but it's Wadler, not Walder. Maybe you knew this and it was just a typo.
- Laremere 4y ago
  Ah, was a typo. Can't edit anymore but thanks for the catch!

deleted 4y ago

[deleted]

comex 4y ago

Every language has its own design features that end up influencing its generics system. Java has subtyping (in the form of class inheritance). Rust has lifetimes and linear types. Go has its ‘structurally typed’ interfaces (which are the reason impossible combinations of constraints exist in the first place). Haskell has none of those, but it has plenty of other features that at least historically caused exponential compilation time [1] and unsoundness [2]. Even C++ arguably falls into that category to an extent. Its template system definitely could have been designed better, and using Haskell-like type signatures like Rust does is arguably a better approach… but Rust trait signatures tend to be more complex and less elegant than Haskell ones, because the simple and elegant ones have runtime overhead that Rust, like C++, isn’t willing to accept. (For example, see functions being a trait as opposed to a type.) And even Rust struggles to match C++ in metaprogramming expressivity, which also helps C++ reduce runtime overhead. Upcoming Rust features like `const fn` and specialization will help with that, but both have been ‘upcoming’ for many years… [1] https://news.ycombinator.com/item?id=8130487 https://news.ycombinator.com/item?id=8130487 [2] https://gitlab.haskell.org/ghc/ghc/-/issues/7148 https://gitlab.haskell.org/ghc/ghc/-/issues/7148

fnord123 4y ago

To go with sibling's comment, Wadler also had a hand in designing Java's generics while Guy Steele was a co-author of the Java Language Specification. And the idea that Eric Meijer ignored PL research is just mistaken. Instead of belly aching about everyone who did it wrong, why not explain what is wrong and why you think so. I mean, I think think Rust didn't do it perfect because I often want to use Box<dyn MyTrait> which is a hassle because I need to mark every function ?Sized if I want to pass a reference to my `x: &T...where T: MyTrait + ?Sized` and I don't enjoy that.

cpurdy 4y ago
Additionally, Josh's first generics implementation in Java was reified (like C#), but the necessary JVM changes were delayed, so he had to quickly do a second implementation using erasure. Sometimes, reality bites.
- fnord123 4y ago
  One of Java's original goals was to work in embedded systems. As such, I think type erasure actually is helpful to reduce the size of compiled artefacts because you haven't monomorphised functions - hence avoiding potential bloat. As in all of engineering, most things are a tradeoff.
  - monocasa 4y ago
    The other proposals I've heard for Java generics didn't monomorphize at compile time but instead modified the .class format to represent generic classes/methods closer to their source representation. Because the embedded systems at the time that cared about code size in Java would have been structured as bytecode interpreters, they arguably would have had smaller binaries without type erasure. The casts the erasure does under the hood are represented as additional bytecode at most call sites, but would have been implicit if generic functions had first class JVM support.

duped 4y ago

No it's just ignorance. PL design is just one of the few areas where academia leads industry by a wide margin in understanding how to design compilers and type systems. Where academia lags and why these features fail to make it into production languages is that industry needs working compilers, build systems, debuggers, package managers, and linters more than it needs any kind of static typing. The other problem is incentive and design approach. The academic approach to PL design is to carefully develop the type system and understand the way the rules interact, proving things like soundness, decidability, etc. the industry approach to software development is MVP. These two approaches are incompatible and lead to different language designs, because you can't slap a carefully designed system on top of a recklessly developed MVP that has been bumped incrementally over a long time. At least not without major time consuming rewrites.

Merovius 4y ago

> So far, Rust seems to have gotten it right by essentially copying Haskell. FWIW I've used Rust for a bit and I disagree that they "got it right". I'm not saying Rust is bad, I like the language. But it's not as if their generics implementation does not have issues. It's just that they are different issues.