Experiment with Lobster-like memory management

[LifeIsStrange]

http://aardappel.github.io/lobster/memory_management.html

Reading this blog has been mind-blowing to me, as there would be an algorithm that would:

1. Be as safe as an automatic GC.
2. Remove most of rust memory management expressiveness limitations (e.g can't have two mutable pointers aliasing), interior mutability, etc
3. can optionally enforce some constraints if wanted by the developper (e.g no aliasing)
4. the biggest point here: Remove 95% of the needed boilerplate and bookkeeping tax that every rust developper currently has (lifetimes annotations, etc)

Rust has an issue about implementing automatic garbage collection:
rust-lang/rfcs#415
The reason would be to massively help the language to become more mainstream by reducing the learning curve, and the cognitive overhead of day to day programming thus increasing developper productivity on their problem domain.

Experimenting with Lobster-like memory management, if a success, would bring us closer to that goal, without any tax on runtime performance.
This seems to me like the future: almost automatic, compile time garbage collection.

Rust would really gain momentum with such a killer feature.

[bjorn3]

e.g can't have two mutable pointers aliasing

That restriction is necessary to prevent iterator invalidation and data races. A better name for mutable references would have been unique references.

---

From the linked page:

it will insert a reference count increase only for this particular use

Please no implicit reference counting. Also reference counting requires heap allocation, which may not even be possible in #![no_std] environments.

The reason for this is that a lot of the power of Lobster centers around its “Flow Sensitive Type Specialization”, meaning it type checks functions in call-graph order, and specializes them based on types.

Rust doesn't use any non-local type inference (except for impl Trait, but that only allows a DAG, not an arbitrary call graph) This is beneficial for both compilation speed, as a change to a single function body won't affect any other function, and it is beneficial for understanding code, as you don't have to look at every function in a crate to find out what code does. It also means that changes to a function body can't accidentally cause something else to break.

[LifeIsStrange]

@bjorn3 allowing multiple mutable pointers to alias is a debate that we do not need.
Let's say that the rust-lobster algorithm will keep this "limitation" as a sound decision.
The eventuality of allowing aliasing could be discussed far later, as of now let's assume it isn't allowed.

The main remaining point is to eliminate lifetime annotations.

The reason for this is that a lot of the power of Lobster centers around its “Flow Sensitive Type Specialization”, meaning it type checks functions in call-graph order, and specializes them based on types.
Your answer to this is interesting and I have not the required expertise to tell if your argument totally prevent rust from implementing said algorithm.

It's up to rust developers to, after a rigorous analysis, determine if the “Flow Sensitive Type Specialization” (or a variant) is absolutely not applicable in any extent to rust.
If such conclusion is drawn, rust will be condemned to still require lifetime annotations. The constraints that might create the lobster algorithm must be substracted to the constraints it removes. If the resulting utility weight is negative then this issue should be experimented, otherwise it should be closed.

[workingjubilee]

Yes.
Specifically, this is an interesting idea, but to the extent that this idea is useful and interesting, this is already what NLL is.

Otherwise, it relies on certain assumptions (e.g. presence of a memory management unit) that would not be appropriate on a language level and it relies on certain rules in terms of lifetimes that would make usage of this unpredictable. Namely, lifetime rules are encoded in type signatures in Rust. This means changes purely interior to a function should not alter calling the function in Rust. Lobster's description here contains no such limitation. So it may be very appropriate for Lobster but not necessarily appropriate for Rust.