3 ms·

Is there a reason we're not seeing linear types in more languages? I'm not familiar with how difficult it is to implement or if there are usage issues that end

Is there a reason we're not seeing linear types in more languages? I'm not familiar with how difficult it is to implement or if there are usage issues that end up showing only after a while?

lmm 2y ago
Plenty of new research languages are coming out with linear types. Building a mainstream language is extremely expensive these days, to the point that probably only a handful of companies can attempt it. I work in Scala which teeters on the edge of mainstream, and it's not the language itself that needs major backing, it's all the other stuff - IDEs, library repositories, build tools, profilers. I would love to leap into e.g. Idris, which does have linear types, but who's going to write an IDE for it? Even Rust struggles with this. And it's very hard to retrofit linear types onto an existing language, if you can even get a quorum in favour of doing so. Haskell is trying, and I wish them well, but it's not going to be easy, and again they're barely mainstream.
- nequo 2y ago
  > Even Rust struggles with this. The Rust language server seems really good. What have you been missing there?
  - thoasdfwdas 2y ago
    It was years before we had rust-analyzer.
    - shepmaster 2y ago
      A year and a half doesn't seem like bad turnaround time to me. shrug On June 27, 2016, Microsoft announced a collaboration with Red Hat and Codenvy to standardize [Language Server Protocol]'s specification — https://en.wikipedia.org/wiki/Language_Server_Protocol https://en.wikipedia.org/wiki/Language_Server_Protocol vs initial Date: 2017-12-21 22:25:45 +0300 — https://github.com/rust-lang/rust-analyzer/commit/a63222cd240d9b5405826783603f3b391c90885d https://github.com/rust-lang/rust-analyzer/commit/a63222cd24...
      - thoasdfwdas 2y ago
        I've been using rust since 2010
o11c 2y ago
Besides the question of usability, there are at least 3 major problems that come up in the vicinity of linear types (some also apply to ownership in general): * Do you assume trivial moves? Because that's not a safe assumption. Related, many examples only really work for local variables, and otherwise rely on special language object holders or something, which even if they can also be implemented in user code often break safety elsewhere. * What, exactly, happens to your objects when a task unwinds? * What do you do about leaked cycles? * Inheritance is no longer a simple part of the language. And trust me, you do want inheritance. It's not that these questions don't have possible answers (a few of which are touched on in the linked article), but there are no easy answers.
- verdagon 2y ago
  I'm glad you brought inheritance up! This rule has solved it nicely in my experience: if a struct is linear, then it can only inherit linear interfaces. And implementation inheritance works because it's really just a combination of interface inheritance + composition + method forwarding, none of which seem to have any particular trouble with linear types. Even if a language really wanted to have linear types in reference-counted objects, I don't think we'd see cycles in practice. Generally, for a reference-counted object to contain a linear type, we'd need exactly one reference to be the special "linear reference" (think a linear flavor of unique_ptr) which has ultimate responsibility for "consuming" (albeit not deleting) the contents. Making a unique_ptr cycle is much harder than making a regular RC cycle, so I'm not too worried, even if it is theoretically possible. Re: trivial moves, I'm not sure what you mean. The system works through the entire program, not just local variables. Also, the `onException` method would also handle panics. Hope that helps!
  - o11c 2y ago
    As for inheritance - I'm increasingly convinced that it is a useful idea to have an explicit `Object` (or `BaseObject`, to deal with languages where primitives are special) class at the root of the hierarchy, rather than relying on some nebulous type-checker-only `Top` type (sometimes called `Any`, though that usually has additional footguns). One thing I do think is a mistake in languages that have an `Object` class is that it is often not abstract. In particular it is often used for sentinel-like objects (with no contents - the lack of a name is annoying), to say nothing of Javascript's mess. Is "top-most interface" really a sufficient concept? As much as I've come to love late-defined traits (among others, no more PIMPL), I'm not convinced we can really afford to stop thinking in terms of an OO tree, or even to give up on multiple inheritance You don't need RC to have a cycle - it already occurs with a pair of structs that refer to each other using `mut Option[Unique[T]]`. Rust seems to have settled for "document it aggressively, and otherwise ignore it" ... yet code very similar to this is actually very useful, so (with a few extra layers of nesting) it often does appear spontaneously in the wild. But the whole point of linear types is that you can no longer just say "leaks are okay I guess". Moving even a small 64KB buffer isn't actually trivial even if your type system thinks it is by composition, but most linear-ish type systems seem to aggressively use destructuring (possibly via pattern-matching) which relies on moving the members. Not to mention all the other actually-useful things C++ move constructors can do (update peer objects, for example). While "move-by-default" is a definite winner, "trivial-move-only" is not. The question of "what exactly happens so I can move out of a language-defined Option[T], leaving None ... vs how can a user-defined variant type choose to do something similar" is significantly complicated by nontrivial moves.
verdagon 2y ago
There are a couple technical reasons: 1. In RC and tracing GC languages, a linear object would need exactly one special "linear" reference to it, which would be responsible for eventually "consuming" (though not deleting) the object by handing it to its final destination function. (You can tell, I'm trying real hard to not say destructor here) 2. In single-ownership languages like C++, Rust, etc. we've been conflating the destructor to handle two things: fulfilling the object's final purpose, and handling exceptions/panics. It seemed convenient at the time, but it also prevented linear types. But honestly, I think we were just stuck in a local maximum. There was no reason to change those points because we didn't know about higher RAII, and we didn't know about higher RAII because those two points prevented linear types. But with more of us exploring this new area (Vale, Austral, maybe even Mojo!), I daresay we'll one day see linear types and higher RAII entering the mainstream. Especially if someone can come up with a better name!
- robert-wallis 2y ago
  How about COO - Close Object Obligation? And you could sound like a pigeon saying "coo" during talks explaining it.
  - verdagon 2y ago
    Hah I like this one! PS. Congrats! https://verdagon.dev/blog/easter-egg-notes https://verdagon.dev/blog/easter-egg-notes
- NeutralForest 2y ago
  Thanks for the answer! Not gonna lie, I don't have the background to understand all your articles, just enough to see that you're pushing the boundary on what's possible and it's really cool!
  - verdagon 2y ago
    Thanks! And yeah I get that a lot >_> You're always welcome to swing by the discord where I can give a less arcane explanation! (https://discord.gg/SNB8yGH https://discord.gg/SNB8yGH)

Is there a reason we're not seeing linear types in more languages? I'm not familiar with how difficult it is to implement or if there are usage issues that end up showing only after a while?

lmm 2y ago

Plenty of new research languages are coming out with linear types. Building a mainstream language is extremely expensive these days, to the point that probably only a handful of companies can attempt it. I work in Scala which teeters on the edge of mainstream, and it's not the language itself that needs major backing, it's all the other stuff - IDEs, library repositories, build tools, profilers. I would love to leap into e.g. Idris, which does have linear types, but who's going to write an IDE for it? Even Rust struggles with this. And it's very hard to retrofit linear types onto an existing language, if you can even get a quorum in favour of doing so. Haskell is trying, and I wish them well, but it's not going to be easy, and again they're barely mainstream.

nequo 2y ago
> Even Rust struggles with this. The Rust language server seems really good. What have you been missing there?
- thoasdfwdas 2y ago
  It was years before we had rust-analyzer.
  - shepmaster 2y ago
    A year and a half doesn't seem like bad turnaround time to me. shrug On June 27, 2016, Microsoft announced a collaboration with Red Hat and Codenvy to standardize [Language Server Protocol]'s specification — https://en.wikipedia.org/wiki/Language_Server_Protocol https://en.wikipedia.org/wiki/Language_Server_Protocol vs initial Date: 2017-12-21 22:25:45 +0300 — https://github.com/rust-lang/rust-analyzer/commit/a63222cd240d9b5405826783603f3b391c90885d https://github.com/rust-lang/rust-analyzer/commit/a63222cd24...
    - thoasdfwdas 2y ago
      I've been using rust since 2010

o11c 2y ago

Besides the question of usability, there are at least 3 major problems that come up in the vicinity of linear types (some also apply to ownership in general): * Do you assume trivial moves? Because that's not a safe assumption. Related, many examples only really work for local variables, and otherwise rely on special language object holders or something, which even if they can also be implemented in user code often break safety elsewhere. * What, exactly, happens to your objects when a task unwinds? * What do you do about leaked cycles? * Inheritance is no longer a simple part of the language. And trust me, you do want inheritance. It's not that these questions don't have possible answers (a few of which are touched on in the linked article), but there are no easy answers.

verdagon 2y ago
I'm glad you brought inheritance up! This rule has solved it nicely in my experience: if a struct is linear, then it can only inherit linear interfaces. And implementation inheritance works because it's really just a combination of interface inheritance + composition + method forwarding, none of which seem to have any particular trouble with linear types. Even if a language really wanted to have linear types in reference-counted objects, I don't think we'd see cycles in practice. Generally, for a reference-counted object to contain a linear type, we'd need exactly one reference to be the special "linear reference" (think a linear flavor of unique_ptr) which has ultimate responsibility for "consuming" (albeit not deleting) the contents. Making a unique_ptr cycle is much harder than making a regular RC cycle, so I'm not too worried, even if it is theoretically possible. Re: trivial moves, I'm not sure what you mean. The system works through the entire program, not just local variables. Also, the `onException` method would also handle panics. Hope that helps!
- o11c 2y ago
  As for inheritance - I'm increasingly convinced that it is a useful idea to have an explicit `Object` (or `BaseObject`, to deal with languages where primitives are special) class at the root of the hierarchy, rather than relying on some nebulous type-checker-only `Top` type (sometimes called `Any`, though that usually has additional footguns). One thing I do think is a mistake in languages that have an `Object` class is that it is often not abstract. In particular it is often used for sentinel-like objects (with no contents - the lack of a name is annoying), to say nothing of Javascript's mess. Is "top-most interface" really a sufficient concept? As much as I've come to love late-defined traits (among others, no more PIMPL), I'm not convinced we can really afford to stop thinking in terms of an OO tree, or even to give up on multiple inheritance You don't need RC to have a cycle - it already occurs with a pair of structs that refer to each other using `mut Option[Unique[T]]`. Rust seems to have settled for "document it aggressively, and otherwise ignore it" ... yet code very similar to this is actually very useful, so (with a few extra layers of nesting) it often does appear spontaneously in the wild. But the whole point of linear types is that you can no longer just say "leaks are okay I guess". Moving even a small 64KB buffer isn't actually trivial even if your type system thinks it is by composition, but most linear-ish type systems seem to aggressively use destructuring (possibly via pattern-matching) which relies on moving the members. Not to mention all the other actually-useful things C++ move constructors can do (update peer objects, for example). While "move-by-default" is a definite winner, "trivial-move-only" is not. The question of "what exactly happens so I can move out of a language-defined Option[T], leaving None ... vs how can a user-defined variant type choose to do something similar" is significantly complicated by nontrivial moves.

verdagon 2y ago

There are a couple technical reasons: 1. In RC and tracing GC languages, a linear object would need exactly one special "linear" reference to it, which would be responsible for eventually "consuming" (though not deleting) the object by handing it to its final destination function. (You can tell, I'm trying real hard to not say destructor here) 2. In single-ownership languages like C++, Rust, etc. we've been conflating the destructor to handle two things: fulfilling the object's final purpose, and handling exceptions/panics. It seemed convenient at the time, but it also prevented linear types. But honestly, I think we were just stuck in a local maximum. There was no reason to change those points because we didn't know about higher RAII, and we didn't know about higher RAII because those two points prevented linear types. But with more of us exploring this new area (Vale, Austral, maybe even Mojo!), I daresay we'll one day see linear types and higher RAII entering the mainstream. Especially if someone can come up with a better name!

robert-wallis 2y ago
How about COO - Close Object Obligation? And you could sound like a pigeon saying "coo" during talks explaining it.
- verdagon 2y ago
  Hah I like this one! PS. Congrats! https://verdagon.dev/blog/easter-egg-notes https://verdagon.dev/blog/easter-egg-notes
NeutralForest 2y ago
Thanks for the answer! Not gonna lie, I don't have the background to understand all your articles, just enough to see that you're pushing the boundary on what's possible and it's really cool!
- verdagon 2y ago
  Thanks! And yeah I get that a lot >_> You're always welcome to swing by the discord where I can give a less arcane explanation! (https://discord.gg/SNB8yGH https://discord.gg/SNB8yGH)