On uniqueness and mutability

[madmalik]

Rusts central idea is to disallow mutability and aliasing at the same time (a little bit simplified). I'd like to discuss if it'd be useful to infuse a similar concept into a dynamic language.

Why?

• Shared mutable data is a source of bugs.
• Unique values makes resource management easier. I don't want to close my file handles manually, thank you very much. ;)
• It may be a key for easy interop with rust (move values from rust into the runtime and move them out later, or knowing that if the rust part holds references into the runtime heap they cannot be mutated)

How would that work?

• the functional route: pervasive immutability and persistent data structures (like clojure, erlang etc.)
• every reference has to be unique. Aliasing is impossible and values can only be moved or cloned (may have a big performance impact)
• make values immutable as soon as they are shared and check that on runtime (for example with reference counting and allow mutation on reference counts of one)

I don't know if a scripting language is the right place for this concept, but it seems to be mostly unexplored beside pervasive immutability.

Side node: Stack based (or concatenative) languages lend them self quite naturally to this concept since all standard operations are moving and copying/aliasing is explicit. Here is a quite old but interesting article about that: Henry G. Baker: Linear Logic and Permutation Stacks

[pliniker]

I've been considering the same line of thought for the past 4 days. I have questions without answers...

Take a general purpose mainstream imperative language, say Python since I'm a Python dev too, but change it to only persistent data structures and strict move/clone semantics for values.

• Where would a Python programmer be surprised by these semantics? How could these surprises be avoided or minimized?
  • Cyclic data structures would work differently
    • a = []; a.append(a) wouldn't be possible
    • how often does this really happen?
    • weak references
  • ...?

[pliniker]

Other languages that look imperative but are built on a functional/immutable foundation:

• https://reasonml.github.io/
• https://elixir-lang.org/

[brendanzab]

Reason and OCaml allow arbitrary mutation though (via ref cells). Not sure how much the compiler does to figure out whether sections of code are pure or impure. This will be made easier once the algebraic effect system comes with Multicore OCaml - I think they are experimenting with a region system for tracking ref cells - was mentioned in the linked presentation.

Haskell is adding linear types, using an approach similar to quantitative type theory:

• https://ghc.haskell.org/trac/ghc/wiki/LinearTypes
• Linear types ghc-proposals/ghc-proposals#111
• https://arxiv.org/abs/1710.09756
• http://edsko.net/2017/01/08/linearity-in-haskell/
• https://bentnib.org/quantitative-type-theory.html

They don't really address borrowing (ie. regions) though.

[pliniker]

@brendanzab thanks! Type theory is my weak area but I think I understand linear types somewhat now.

Wondering what this could look like in a dynamic language...

[brendanzab]

Feel free to ask me on Gitter if you have any questions on the TT stuff - I'm still learning, but explaining stuff helps me get my head around things.

As @aatxe mentioned on gitter, you could remove values tagged as 'affine' from the evaluation context as they are consumed. You would have to do it in a threadsafe way of course. It would be interesting to see how that would fare in practice though, given all the troubles we have getting ownership right in Rust with the help of a type checker I imagine it could result in many runtime exceptions.

I'm more interested in the interface between statically typed languages with native support for linear/affine types and potentially non-uniform data representations. It would be nice to reduce the overhead of that bridge as much as possible.

[madmalik]

It would be interesting to see how that would fare in practice though, given all the troubles we have getting ownership right in Rust with the help of a type checker I imagine it could result in many runtime exceptions.

Thats my concern too. I could imagine that it gets somewhat easier since the system would be a little more permissive than static ownership tracking, but it also may be a lot harder because of the missing help from the static analysis, which would be a little bit unfortunate for a language whose main purpose is to be easier than rust. ;)

Thats one of the reasons i'm really interested in stack based languages and their point-free style of programming. In principle, the concept that things are not there anymore when they are given away or used up should not be that unintuitive. Imo it's hard because we are using aliases (names) for things, and than disallow aliasing them.

[brendanzab]

One thing I just thought of: Rust already has dynamic alias checking in the form of RefCell<T>!

[madmalik]

Cyclic data structures would work differently

• a = []; a.append(a) wouldn't be possible
• how often does this really happen?

I would be probably ok without support for cyclic data structures. In my experience, truly cyclic data structures like graphs are often better served with a representation that is not a literal graph of objects but something like an edge list or an adjacency matrix, depending on the problem at hand. Also there is always the possibility to either work with ids instead of references or implement the data structure in Rust and provide an API.

[mattgreen]

I favor pervasive immutability with well-documented escape hatches for corner cases. In working with mainstream languages that support this concept, (whether opt-in or by default), is that I don't need mutability for most problems. It is also easier when the implementor and the user are on the same page. Also, when reading code, it is enormously helpful to be able to assume immutability unless otherwise specified.

If you take this approach then you must have great documentation on when and how to handle cases like cyclic data structures.