References are like jumps | Hacker News Reader

References are like jumps

without.boats

98 pointstodsacerdoti10 comments

> They see all of this business with lifetimes and ownership as a dirty mess that Rust has had to adopt because it wanted to avoid garbage collection. But this is completely backwards! Rust adopted rules around shared mutable state and this enabled it to avoid garbage collection. These rules are a good idea regardless.

I'm not sure that this is true. Lack of garbage collection and management of shared mutable state are implemented by partially overlapping aspects of the borrow checker.

If Rust eliminated lifetimes and ownership but maintained its rules for & and &mut, it would require garbage collection but still control mutability. On the other hand, if Rust allowed &mut freely and retained lifetimes, then you could have mutable shared state but no need for garbage collection.

The only doubt I have is, maybe freely permitting &mut would make lifetimes unsound? I haven't used Rust enough to be sure.

From what I understand most of the power comes from ensuring there is only one &mut for a value at a given time.

I'd tend to agree with your understanding of the path Rust's development took, but it is certainly not clear cut which led to which. I am certainly willing to be corrected (my memory is getting rough at this point in my life), but I remember the bifurcation of mutability and alias-ability being present in Graydon's original pitch deck, which existed as a prototype with garbage collection being expected to exist. Then after some work, I thought the language devs realized that with some extra rules, which became the lifetime semantics, there was a feasible method for not requiring a garbage collector, but still remain fairly free of manual/explicit memory management by developers.

They're not quite that independent, because the choice of memory management strategy relies on the aliasing rules. But (as the post argues) the aliasing rules don't rely on the memory management strategy.

The guarantee that &mut is unique enables mutations to change the "shape" of an object in memory- e.g. reallocating a Vec to grow it, or overwriting a Box with a new one and freeing the original, or overwriting an enum/union in-place with a different variant.

If &mut were not restricted in this way, then this "eager" memory re-use could cause other references, into the interior of the shape, to dangle. But this is how Rust manages memory- if there may be other references to the old memory, when is it safe to free it, and reuse it with a potentially different type? Lifetimes don't help you here, unless you make them powerful enough to re-encode the same old aliasing rules!

It's important to note that this is not only about heap allocations. The enum/union case, for example, is entirely in-place in Rust. So even if you switch to an arena or type-segregating allocator, and accept that the old references might point to stale or now-unrelated values, you still haven't recovered memory safety. You need to keep the old value, with its old type, in place in memory simultaneously.

GC provides memory safety by making it practical to forbid these kinds of memory layouts to begin with- the program cannot eagerly free an old backing array or heap object, nor can it overwrite an enum in-place. Instead it can only mutate the references themselves, leaving the old value alone for any other references that may still exist.

There is a middle ground, where a language could allow shared mutability with more compact memory layouts, but it requires a different set of restrictions: like GC, no references to array elements or Box/enum/union fields; without a GC, working with these values requires deep copying them. Languages like Java already do this, but only for primitive types where the copy can be atomic. (Or you could use something GC-like, such as reference counting and/or copy-on-write.)

The point of the post is that the Rust approach to memory management is not the only thing that the aliasing rules gives you, because they also aid in local reasoning about your programs, regardless of your approach to memory layout and allocation.

Ah right. That confirms my suspicion then that relaxing &mut would make lifetimes unsound.

Mojo's value semantics make heavy use of ownership and avoids copying as much as possible, see - https://www.youtube.com/watch?v=9ag0fPMmYPQ

After the opening quote by Hoare and a quick intro paragraph, the author says 'What Tony Hoare was writing about when he said that references are like jumps was the problem of mutable, aliased state.' withoutboats is a well known Rust developer, so I guess this assumption about Hoare's quote should not be a surprise.

However, I don't see the text of the quote as reinforcing that perspective. I can see an argument for the article's extrapolation, taking Hoare's seemingly more general lamentations about the semantic existence of references (a semantic group containing at least 'reference, pointer, or indirect address into the languageas an assignable item of data') and then applying to the Rust model of non-aliased, mutable state as an attempt to circumvent the problems Hoare is addressing. But this argument is an attempt at taking a narrowly scoped perspective on a problem, correcting that small slice of the greater problem, and then announcing the entirety of the problem no longer exists. Like I said, understandable why the article would take this direction, I just don't think it truly addresses the totality of Hoare's critique of references as an undesirable semantic abstraction.

The title of the section withoutboats has quoted and the first sentence are unfortunately left out of his selection:

"8. Variables One of the most powerful and most dangerous aspects of machine code programming is that each individual instruction of the code can change the content of any register, any location of store, and alter the condition of any peripheral: it can even change its neighboring instructions or itself. Worse still, the identity of the location changed is not always apparent from the written form of the instruction; it cannot be determined until run time, when the values of base registers, index registers, and indirect addresses are known." [This paragraph is essentially acknowledging that low-level machine code gains its computational power from unlimited ability to alter the state of computation]

Also, the ... following the quote's second paragraph omits the following: "For example, in ALGOL 68, the assignment x : = y; always changes x , but the assignment x: = y+l; if x is a reference variable may change any other variable (of appropriate type) in the whole machine. One variable it can never change is x!" [This quote, which was removed, makes it explicit that Hoare is addressing the mere existence of references]

Both of the omitted sections tend very strongly toward Hoare's actual critiques being the semantic concept of references in high level languages being problematic, not merely mutable state. There is some natural extension of Hoare's discussion of references as means of assignment, which does lead to the 'spooky action' occurances. However, following this section of Hints on Programming Language Design, Hoare talks for a bit about structured programming, scope, and parameter importance. Discussing that without references, programmers have disjoint names for semantic objects and those are only altered/mutated by passing the sole existing object to a procedure as a parameter and having it passed back.

Overall, the TL;DR may be negatively stated as Rust developer gonna view things through a Rust-y lense. However, I think that is an incorrect reading. withoutboats skipped a crucial step in his going from Hoare's critique of referencs, they went directly from the text to an interpretation of the critique focused on aliased, mutable state. There is some discussion to be had about Hoare's assumptions of a single semantic object existing in a one-to-one correspondence with a disjoint source code name, especially in the context of multi-processor and networked programming prevalent in 2024. While I think that a more general solution to Hoare's problem exists and acknowledge Rust's attempts to at least tame a portion of the problem, I don't think any language has 'fixed' this issue.

I agree that it's a leap to jump from 'reference' to 'shared, mutable reference'. But it's a leap I'd make too:

Hoare's quotes reflect the time. I doubt there were good ways to work effectively with immutable references, so you have to take 'mutability' as given. Then all references might be shared + mutable. This persists in the mainstream today. 'Final' != 'immutable'.

But what else does Hoare complain about in that opening para?

* Accidentally mistaking data for references and vice-versa. I feel like that's solved in the mainstream except for some parts of C.

* References not being shared between program runs or across different running programs. I can't say I've run into this problem, but maybe solving it would allow for distributed closures in an actor environment, like in Cloud Haskell.

Yea, I think its fair to say that Hoare was actually arguing for something like "value semantics," because he saw all the problems that references cause. But I would claim you can't actually implement a realistic system without some amount of references, if only to synchronize state between concurrent components, so the language of implementation should restrict references in a similar way to Rust to make using references without error tractable.

My takeaways:

>"What Tony Hoare was writing about when he said that references [a.k.a. pointers] are like jumps was the problem of mutable, aliased state.

If you have in a language the ability to alias two variables so that they refer to the same location in memory, and also the ability to assign values to variables as execution progresses, your ability to locally reason about the behavior of a component of your system becomes badly inhibited." (PDS: This is especially true for code which is shared by multiple threads!)

Related article: "Understanding Pointer Aliasing in C and the `restrict` Keyword": https://hasanisaeed.medium.com/understanding-pointer-aliasin...

>"Depriving the user of the ability to mutate aliased state by accident is critical to enabling the user to easily create correctly functioning systems.

[...]

Rust’s entire claim to fame is that it has shipped a type system intended to solve this problem.

In Rust, references [a.k.a. pointers] are mutable or aliased, but never both

, and the entire system of lifetime variables and borrow analysis is designed to ensure that this remains true."

Reply on news.ycombinator.com