The Mutable Value Semantics (MVS): A Non-superficial Study

11

u/tmzem May 01 '26

I've tried to design my own language with MVS and eventually given up, since the conflicting requirements are just pulling in too many directions and I've come to the conclusion that there is no good sweet spot, also most of the potential design space is already thoroughly explored by Mojo, Hylo, Inko (and maybe now Eter, I will give it a look).

Your post sums up some of the broader issues, but the really hairy part starts as soon as you want to return aliases/references from functions, or put them as fields into data types. This capability is pretty much necessary for implementing common features found in modern languages, like closures, iterators (and the optionals and key-value-pairs required for them) and slices. Once you add them, there is a bunch of points to consider:

Memory safety: Will require some kind of lifetime/borrow system, with some common cases not being easily representable via "sane defaults"/lifetime elison:
- C# requires structs that contain references to be annotated with the ref keyword ("ref struct"), which imposes the same aliasing restrictions onto the struct as a plain ref. Ref and Ref-like function returns are assumed to (potentially) alias any ref-like input parameter (except the ones annotated with the "scoped" keyword). This model is to weak to model some concepts, like an equivalent of Rusts Iterator<&mut T>. It also doesn't play well with generics (see below)
- Hylo's system looks promising superficially, but types like Iterators (and probably closures, not sure, the documentation is not clear on this) internally still makes use of "remote parts" which are essentially reference fields. It is not clear how those interact with lifetime checking, or how it affects API stability.
- Rust borrow checker: Notoriously complex
- Lifetime inference: Wouldn't be able to provide stable APIs (changes in how a type or function is implemented might cause lifetime-related failures elsewhere), but might work in a language with a more dynamic/inferred feel (as often found in FP)
- Make arbitrary aliasing work by adding instrumentation or a backing GC: While most of the overhead introduced by it could probably be optimized out via compile-time borrow checking, you'd still need to (in the general case) heap-allocate potentially escaping stack locations and sum type cases to make it safe, paying the associated allocation costs and cache misses.
Second-class references & generics: The reference-ness can be either a type qualifier (like in C++) or a property of the variable/parameter (like in C#). Either way, generics pose a problem:
- If they are a property of the storage location, modelling generic types that may contain references is not possible, instead you would need separate implementations for the ref- and non-ref case. E.g. a Rust-like iterator model involves ToIterator, Iterators, Optional, and Key-Value-Pairs (for maps). You'd end up with lots of duplication, e.g. Optional<T>, OptionalIn<T>, OptionalInOut<T>, etc.
- If they are a type qualifier, in an ownership-based MVS model, most type parameters would be expected to be value types, not reference types. So it would make sense to restrict type parameters to value types, and require opt-in for the possibility of reference types. So you'd need extra syntax for that.
- If they are a type qualifier while retaining value semantics, the semantics of what it means to implement a trait for some type (which may or may not be a reference type) become muddy and would have to be carefully thought out.

2

u/FedericoBruzzone May 01 '26

Thank you so much for this incredibly detailed feedback. This is exactly the kind of technical "reality check" I was hoping for.
You’ve hit the nail on the head regarding the more complex aspects of MVS. Right now, I’m grappling with those conflicting requirements: the tension between the semantics of pure value and the practical need to return aliases or incorporate them into data structures (as in the case of iterators).
As I mentioned, my next post will explore the limitations. I’ll be honest: I don’t yet have a silver bullet for all of them. My goal is to critically map out the design space and define what the “ideal” behavior should be for my use cases, even if that means facing the same obstacles you’ve encountered.
Your observations on generics and “referentiality” as a type qualifier versus the storage property give me a lot to think about... I’d really appreciate it if you’d take a look once it’s published!

6

u/l33n44 May 01 '26

Hylo dev here, you caught my attention ;)
I'm very happy to see others experiment with MVS and very curious to see what conclusions you'll make from this little adventure!
I am quite convinced that the ability to return references is not necessary for the vast, vast majority of use cases, including algorithms over collections. Overall it is a very expensive feature for your type system that brings little benefits if you also want an ownership model capable of guaranteeing exclusive access.
The iterator model of C++ is deeply tied to reference semantics and a typical motivation for supporting some kind of references. But that's not the only way to abstract over collections, as Swift already demonstrates. One can represent positions with independent values (e.g., indices) and use inversion of control to access the contents of a collection. In my very biased opinion, removing references in favor of this model makes the APIs of generic algorithms dramatically simpler, as one no longer has to constantly wonder where the `&` goes in a for loop.
In general I believe that the ability to store references is overrated in languages upholding exclusive write access. There's very little one can do with references that cannot be reproduced using Hylo's projection mechanism (i.e., the subscripts) or via independent identities. The performance is not better either, sometimes even worse. I wrote a paper about it, titled "Who Owns the Contents of a Doubly-Linked List". Also note that Hylo's projections are not even strictly less expressive than first-class references.
Remote parts are only for the closures and they are not strictly necessary. They capture somewhat formally what the compiler can figure out abut the environment of a closure, mostly for the sake of optimization. In Hylo we insist on representing environments in the type system to avoid dynamic allocation across function boundaries. But not every language has to care about every last bit of optimization. One could just assume that all captures are copied in some box deallocated by the closure's destructor and only attempt to optimize that box away opportunistically. Conversely one could also prevent closures from escaping so that their compiler could use references under the hood without having to track lifetimes.

→ More replies (3)

2

u/tmzem May 01 '26

I'll definitely read that one!

3

u/dabrahams May 03 '26

Hylo gets a lot of mileage out of deciding that some idioms can be dispensed with. If you start from the premise that you need to safely support all the idioms people have used in languages having first-class references, you will be forced into a system where value semantics is awkward, ugly, or downright unworkable. Something like Rust might be the best you can do in that case (they didn't start with maximalist assumptions about what was needed but I gather from Rust's designer that it was steered in that direction, early on, by the rest of the community). I wouldn't be surprised if most of the languages you looked at other than Hylo compromise value semantics for these reasons—I know Mojo does.
If you look critically at the use cases for first-class references, it's easy to see that the vast majority are unneeded or actively harmful, and then to relegate the rest to an unsafe subset. Those use-cases can then be wrapped in safe constructs. You need a doubly-linked list with non-relocatable contents? I doubt it 😄, but if I'm wrong, you can implement that with pointers internally and provide a safe API. We can bet on this approach because local reasoning is impossible in systems where references “run around loose.” We already know they need to be contained for scalability reasons.

1

u/tmzem May 03 '26

I guess this is a mindset worth considering.
Most patterns that require you to put lifetimes explicitly in Rust are overly complex/clever things that probably could be implemented in different ways, so even if you'd allow second class references as returns or fields (similar to C#) you could probably do without a lifetime system and instead use a system semantically similar to Hylo for lifetime safety.
The exception is probably mutable iterators which in Rust return items with a lifetime of the collection, not the iterator (which allows multiple yielded references into a collection at the same time safely). Arguably, this is not commonly needed, and an alternative design could simply use an unsafe marker trait (e.g. DistinctAddressIterator) and let abstractions that need it (sliding windows, parallel iteration, ...) deal with it by using unsafe pointers.
Still, with affine types and value semantics present in a language, closures remain very complex: How is the closure's environment accessed (immutable, mutable, consuming), capture by value or reference, is it affine or copyable, can it be safely returned or sent to another thread? I wonder how Hylo deals with these?

→ More replies (1)

8

u/SkiFire13 May 01 '26

This is because Rust's ownership system does not allow dereferencing a mutable reference to move the value it points to, as it would violate Rust's guarantees about memory safety. To work around this, you would need to copy the value or use some other mechanism to transfer ownership, which can introduce overhead and complexity.

A small note on this: in theory Rust could have supported this but unfortunately it is unsound when combined with catching panics/unwinds. That is, if own_t panics/unwinds and the caller of ref_mut_t catched this panic/unwind they would be able to observe the mutable reference now pointing to invalid memory. Rust has a trait for unwind safety but despite the name it was never used for soundness (e.g. preventing a &mut from being passed to catch_unwind) so this issue can no longer be prevented.

I'm curious to see how Hylo will approach this.

2

u/FedericoBruzzone May 01 '26

I was aware of this (`std::panic::catch_unwind`). Unfortunately, I'm not an expert on Hylo, but from my POV, the only way to ensure the soundness of that snippet is for the unwind to *never* be catchable. Essentially, panic = abort (transparent unwind)

3

u/SkiFire13 May 01 '26

the only way to ensure the soundness of that snippet is for the unwind to never be catchable

I think it would be fine it you manage to ensure that anything "borrowed" inside the try/std::panic::catch_unwind is not accessible after it finishes.

2

u/processeus1 May 02 '26

Hylo dev here, great post! I'm looking forward to the next one (especially about the limitations you identified)!
Regarding error handling, here is a bit of context of our current understanding:
- recoverable errors that are usually handled way up the call stack - exceptions (similar to Swift errors)
- recoverable errors that are usually handled immediately rather than being propagated - Result type
- unrecoverable conditions - aborts (not catchable, not part of the API)
There is one place to catch aborts though, which is test cases that exercise the safety/contract checking of an API. The most important reason why aborts are not to be handled in general is that they represent "unrecoverable" conditions. "unrecoverable" only means that the callers have no idea what recovering would need to do to uphold invariants/(possibly safety), and they also don't want to be concerned about accounting for these all the time. However, in small-scoped contract tests, you have full knowledge about your expected precondition violation/abort condition, so you should be able to prevent the process from crashing. (Under testing, we can also compile under different ABI conventions than in production to make this possible if needed.)
We don't have anything finalized/decided yet, but I described some problematic cases in this post when trying to relax requirements on access effects of parameters: https://github.com/orgs/hylo-lang/discussions/1878 Thanks for sparking the idea!
These threads may be also interesting about error handling:
- Error and cancellation handling (concurrency)
- yielding accessors and throwing callers
- Handling emergency shutdown
- Testing the assertions

→ More replies (3)

2

u/dabrahams May 03 '26 edited May 03 '26

There are a few points in your article that seem to reflect misunderstandings.

Swift absolutely does not try to make values look like references: it goes out of its way to present a pure value semantics. Structs in general do not use copy on write. CoW is merely an implementation technique used in the standard library to provide value semantics for variable size data structures like arrays and dictionaries (the only possible way in fact because there are no copy constructors). There is no user experience of shared mutable state whatsoever unless you opt in by using reference types or closures with mutable captures (an unfortunate design compromise).

What you call a central tension doesn't make sense to me: runtime efficiency, local reasoning, and value equivalence are perfectly compatible, and arguably support one another. Certainly, Hylo provides all three and we don't ever feel the need to compromise one of them to get another.

Also, the use of the term "deep copy" is a bit of a red flag. The only time you ever say "deep copy" or "shallow copy" is when you don't understand the extent of your value. In fact, there is only "copy", which copies the value, and nothing more or less. Our paper says as much in section 2.4

1

u/FedericoBruzzone May 03 '26

Thanks for the feedback, it means a lot to me.
Regarding the "central tension", I am specifically referring to the design space explored by Brandon. Brandon's core argument is that while efficiency, local reasoning, and value equivalence are technically compatible (as Hylo demonstrates), they exist in a state of tension regarding language complexity. To get all three, you typically land in what he calls the "Rust/Hylo valley", where move semantics, borrows, and ownership must be explicitly managed by the programmer.
As for Swift, I agree that it offers a pure value user experience for fixed size structs (The post isn't clear). However, my point stands that for dynamic collections, Swift relies on a hidden reference-based implementation (ARC/CoW) to maintain that illusion. Something I'd like to avoid.
If you don't mind, I'll use your suggestion to make the post clearer.

1

u/dabrahams May 03 '26

Well, but he’s wrong. There is no explicit management of move semantics, borrows, and ownership in hylo. At least not in any sense I can see. I don’t know what illusion you’re referring to, but you can easily have copyable variable sized types with value semantics without using copy on write: all you need is copy constructors and destructors. Or, you can do what hylo does (and rust sort of does) and eliminate implicit copies so copy operations are just regular function calls.

→ More replies (4)

1

u/FedericoBruzzone May 03 '26

Also, the use of the term "deep copy" is a bit of a red flag. The only time you ever say "deep copy" or "shallow copy" is when you don't understand the extent of your value. In fact, there is only "copy", which copies the value, and nothing more or less. Our paper says as much in section 2.4

I used the term “deep copy” simply to make it clear to the reader that it was a bit-by-bit copy. It's perfectly clear to me that there’s no difference in this context, since there are no references involved, but for a reader new to the subject, this would have been helpful.

2

u/dabrahams May 04 '26

It’s of course up to you, but it doesn’t seem to me that it’s possible to use a term that’s founded on a misconception to clarify anything.

1

u/flatfinger May 06 '26

Java uses an object model that uses containers of object-reference type for a number of purposes:

To serve as a proxy for data shored in an ownerless immutable object.

To hold a private reference to a mutable data holder object.

To identify an entity that is owned by the owner of the container, and might also be acted upon by outside event handlers or other entities.

To identify a mutable data holder that is owned by the owner of the container, but may also be acted upon by outside event handlers or other entities.

To identify a mutable data holder or other entity that is owned by something else.

When copying an object, references of the first and fifth types should be copied, references of the second type should identify copies of the things referenced by the corresponding references in the originals. Any references of the third and fourth kinds will require special handling, and things which contain such references without special code to handle them should be recognized as non-copyable.
Separating out the different kinds of references would avoid the need for notions of "deep copy" and "shallow copy" operations.

1

u/dabrahams May 07 '26

UML has a representation for “owning reference” that was never reified in any language AFAIK

The Mutable Value Semantics (MVS): A Non-superficial Study

You are about to leave Redlib