zwarich

@joe @slava @foonathan @dotstdy @ianh There is another approach that I didn’t mention but that Swift also dabbles in, which is copy-on-write based on dynamic reference uniqueness (as determined by a reference count). We also used this in Lean, in a more “pure” form where the mutable updates were made more explicit, but it has a few major drawbacks:

1) You are forced to use immediate reference counting, which means immediate *atomic* reference counting in a multithreaded environment. Lean goes a step further than Swift and uses non-atomic reference updates if the object hasn’t yet escaped to multiple threads, but in a way this makes things worse because the gap between single-threaded and multi-threaded code gets even wider.

2) I’m not sure it’s possible to make a compiler that always meets user expectations of when copies will occur. Ensuring uniqueness often requires a linear flow of use-to-def edges, and it is not obvious when a def should “depend” on a prior use, especially across function calls (and especially across ABI boundaries). There are also situations where the optimizer can recognize that a value is non-unique anyways and thus all use-to-def edges can be ignored, although at least this has heavy overlap with RC-related optimizations that you probably want to do anyways.

I had some conversations with Andy and Michael on the Swift team long ago about these problems, and am somewhat familiar with the “ownership SSA” solution that they came up with, but I don’t know how it turned out in practice. When I worked on Lean, some of my biggest improvements were in this area, but the logical next steps seemed like a huge upgrade in compiler complexity. It felt like dealing with this problem would slowly become the main focus of the compiler.

3) It’s difficult to make concurrency primitives (e.g. a mutex owning its contents) that stay on the happy path of single-threaded reference uniqueness. We never did this for Lean, but I think it would require some dynamic escape analysis that goes back and poisons the value stored in the mutex if any sufficiently derived value escapes.

@slava @joe @foonathan @dotstdy @ianh I thought about this some more the past few days and one of the things that I keep coming back to is that if you add mutation to your language you’re faced with the problem of data races, and the type system features for the elimination of data races don’t look all the different from ownership systems used by safe systems languages. There is Midori (https://www.cs.drexel.edu/~csg63/papers/oopsla12.pdf), Pony (https://www.ponylang.io/media/papers/fast-cheap.pdf), Verona (https://www.microsoft.com/en-us/research/publication/reference-capabilities-for-flexible-memory-management/), etc. Of course, you could take the Java/C# copout of making data races memory safe (and maybe tack on the Go approach of optional dynamic race detection), but the issues that arise from this model are not very easy to debug.

@joe @foonathan @dotstdy @ianh Another funny realization is that if all return values are returned by writing to a passed reference, then you could have functions with no actual return values and only out-params (with the appropriate pointer type that must be written before returning). It's the use of resources like registers (which may be implicitly used by other code in the function) that necessitates presenting a value at the point of return.

You could take this to the next level and actually have out-params that "steal" registers when written to, but at that point you're probably in meme language territory.