[proposal] Automatic deref for Reference

[lattner]

Hi all,

I put together a proposal to outline how automatic deref of the Reference type can work in Mojo, I'd love thoughts or comments on it. I'm hoping to implement this in the next week or two:
https://github.com/modularml/mojo/blob/main/proposals/auto-dereference.md

-Chris

[taylorpool]

Based on your proposal, I am also in favor of the eager decay option. It removes the need for functions to explicitly, by default, reason about argument references, which seems like it will generally simplify ergonomics.

[Moosems]

I think the proposal is very well written and personally like the eager decay model of the two options.

[Ryul0rd]

I'm also in favor of the eager decay model.

[dmitry-salin]

Eager decay model is better. In Rust, lifetimes is simply an annotation (implicit or explicit) and one of the compiler internals. Mojo takes it one step further and the entire Reference becomes just an annotation for some non-zero address in memory. It would also be nice to have a compiler optimization for the Optional type, such that:

sizeof[Optional[Reference[type, _, _]]]() == sizeof[Reference[type, _, _]]()

[lattner]

100%! I don't think we do this today, but I have always assumed we would get around to it at some point. Swift includes all these optimizations, stealing representations like NULL for tagged enums, using low bits in aligned pointers, as well as using hardware features like TBI on aarch64. Mojo should learn all these tricks!

[soraros]

I quite like the second-class reference ("eager decay") idea. It's not clear how Ref interacts with inout, borrowed and owned. Is the former now simply more elaborate syntax for the latter? How does decaying work for reference of reference? Can we have an example where a "lvalue" is actually on the LHS of an assignment (r[] = val, brackets actually make things clearer)?

I'm not sure if it's by design, it seems that we can't change the "pointee". It's a bit weird, as var r is essentially let r.

var a = 1
var b = 1
var r = Reference(a)
r = Reference(b)  # doesn't work

[nmsmith]

Per the proposal, I believe Reference(a) and Reference(b) wouldn't do what you want them to do here. They "decay" immediately, because they are RValues. So r will have type Int.

This is why Chris added a type annotation in the proposal: var r: Reference[...] = .... This is apparently meant to prevent the decay from happening.

[soraros]

To be clear, I'm using current semantics/spelling in the code snippet.

[lattner]

It's not clear how Ref interacts with inout, borrowed and owned. Is the former now simply more elaborate syntax for the latter?

Yes, you can think of it that ways. The argument conventions are "sort of" like the rust magic for Reference arguments with implied lifetimes. It is only "sort of" though:

1. ✅ Borrowed is very analogous to an immut reference.
2. inout is more than a mutable reference because it works with computed LValues like getattr/setattr and getitem/setitem where you have to read into a temporary and write back out after the call.
3. owned is more than a mutable reference, because it indicates an ownership transfer from the caller to the callee as well.

I'm not sure if it's by design, it seems that we can't change the "pointee". It's a bit weird, as var r is essentially let r.

This isn't actually a mutability thing, you can do this for example with today's compiler:

var r = Reference(a)
r = Reference(a)  # does work

The issue you're running into is that the typeof(r) includes the lifetime set of "a", and "b" isn't in the lifetime set. It is theoretically possible to do what you want, but we don't have any of the syntax wired up so it requires an eldrich horror of mlir magic to do so. References are still coming, this proposal is one step forward, not the end.

[soraros]

I think I understand the semantics of inout etc. What I meant by "interaction" is really what would happen if we use Reference with one of these convention markers. Another thing is that the argument convention doesn't necessarily use a reference in case of reg type, but lit.ref doesn't seem to have the same semantics?

It would be easier if we can see what each case lowers to.

[nmsmith]

I would be nice to get a definition for LValue, RValue and BValue etc. The definitions used in the C++ community don't necessarily apply to Mojo, because the language is so dramatically different/simpler.

[lattner]

I have a tech talk I presented internally, I should totally share it publicly at some point. Please hassle @jackos about it, he can tell me what to do. :)

[jackos]

Hi @nmsmith it's published now: https://www.youtube.com/watch?v=9ag0fPMmYPQ

[nmsmith]

As I've mentioned elsewhere, a major problem that needs to be resolved is the following:

var items: List[Reference[Reference[T, ...], ...]] = ...
items[0] = ???   # What am I intending to mutate? What am I _allowed_ to mutate?

There are three kinds of mutations that a programmer might want to perform upon items[0]:

• Mutate the item, i.e. mutate the variable of type Reference[Reference[T, ...], ...].
• Mutate the item's pointee, i.e. mutate the variable of type Reference[T, ...].
• Mutate the item's pointee's pointee, i.e. mutate the variable of type T.

Also, items[0] is a function call that itself returns a Reference, so there is one additional level of nesting to reason about.

Quite possibly, to resolve this issue (and also issues with the meaning of ==), we will need two memory-safe reference types:

• C++-style references (auto-derefing, and not designed to be stored in collections)
• Rust-style references (auto-deref is limited to method calls, and thus references are easier to store and reassign)

Maybe this would cause more problems than it solves though—it could force people to write a lot of "adapter" code to switch between working with these types.

If we want to stick with a single reference type, I suspect we will need a mechanism for selecting the "number of decays" that we want an expression (e.g. items[0]) to experience. Today, we use the [] operator for this.

[lattner]

Yes, this is likely to be an issue, I'll need to implement this to really understand. My today belief is that items[0] = will be a non-decayed LValue of Reference[Reference[T, ...], ...] type, no change ther. The issue is the ??? will decay to an xValue of T, so it probably won't work.

It's not clear to me how much we should care about this though. If you want to see something horrifying, try to get a C++ compiler to pushback into a std::vector<int&> x; value. It isn't clear to me that we should complicate the model for this.

[lattner]

Oh it occurs to me that one simple workaround is that you can do:

@value
struct MyRef[T]: var state: Reference[T..]
var items: List[Reference[MyRef[T]]]

and then you can control the decay precisely if you really care.

[nmsmith]

It's not clear to me how much we should care about [reassigning references] though.

I suspect that programmers who want a first-class "safe pointer" type, as opposed to C++-style references (with associated limitations), would be frustrated by the inability to reassign references, and by the inability to control the level of deref. Systems programmers need this level of control. And Rust programmers already have it: Rust's reference type allows deref to be manually controlled with *.

IMO whatever design is chosen, we must ensure that the ergonomics of Reference isn't compromised in situations where you are trying to explicitly manipulate references. In other words, we need to make sure auto-deref doesn't solve one problem, but then introduce a second problem. We'll end up playing a game of whack-a-mole.

Your workaround (introducing a MyRef type) works for the same reason that my T with <lifetime> sugar does. Namely, if we introduce a second reference type, we can avoid the need for Reference to serve all of the use-cases we've been discussing. But IMO what you've named MyRef should be Reference, and what you've named Reference should be T with <lifetime>, and it should only be used for labelling function arguments/results. 🙂

[yinonburgansky]

From the proposal I got the impression that you can control the level of decay by the type annotation:

var items: List[Reference[Reference[T, ...], ...]] = ...

var item = items[0]  # decay to type T 
var ref1: Reference[T, ...] = items[0]
var ref2: Reference[Reference[T, ...], ...] = items[0]
var ref3: Reference[Reference[Reference[T, ...], ...]] = items[0]

maybe to mutate the reference we can reuse the inout keyword

var items: List[Reference[Reference[T, ...], ...]] = ...

inout a = items[0]
inout b = items[1]
a, b = b, a  # swap the inner type T items - mutate Reference[T, ...]

inout ref_a: Reference[T, ...] = items[0]
inout ref_b: Reference[T, ...] = items[1]
ref_a, ref_b = ref_b, ref_a  # swap the references - mutate Reference[Reference[T, ...], ...]

inout ref2_a: Reference[Reference[T, ...], ...] = items[0]
inout ref2_b: Reference[Reference[T, ...], ...] = items[1]
ref2_a, ref2_b = ref2_b, ref2_a  # swap the list elements- mutate Reference[Reference[Reference[T, ...], ...]]

this also works nicely in for-loop like was mentioned in lifetimes-keyword-renaming

var my_list = List(1, 2, 3)
for inout x in my_list:
    x += 1
print(my_list)  # prints [2, 3, 4]

[melodyogonna]

+1 for the eager decay option if it makes things easier to learn and teach.

[nmsmith]

Maybe instead of associating auto-deref with the Reference type (which as mentioned earlier, introduces a bunch of issues), we could instead introduce syntactic sugar for declaring a return type as being a lit.ref, i.e. an "already dereferenced" reference. Something like:

struct List[T: CollectionElement]:
    fn get_item(
        self: Reference[Self, _, _], i: Int
    ) -> T with self.lifetime:
        ...

Here, T with self.lifetime is sugar for a lit.ref that points to a variable of type T with the lifetime self.lifetime. (The mutability is implied by the lifetime, so doesn't need to be stated separately.)

A method call whose return type is of this form would have the same affordances as an argument:

• If the returned lit.ref is mutable, it behaves like an inout argument of type T.
• If the returned lit.ref is immutable, it behaves like a borrowed argument of type T.

And if the caller wants to "upgrade" the return type into a first-class Reference, they can just wrap it in the Reference() constructor.

Virtually all functions in the standard library that currently return References would switch to this T with <lifetime> syntax. This would prevent the "leakage" problem discussed in Chris's proposal, where Mojo users who don't know/care about References are accidentally exposed to them.

We'd need to consider how functions returning T with <lifetime> should behave when used as higher-order functions or in generic contexts etc, but this seems solvable.

[lattner]

We could definitely consider such a thing, and if we were going to do so then you could also do the same with arguments as well: fn [xyzlife: lifetime] method(self with xyzlife, ... or something. I'd like to avoid redesigning the whole feature at this point, but it is something to consider conceptually.

[nmsmith]

That's true: T with <lifetime> could also make sense for arguments.

When used as a return type, IMO it's helpful to think of this syntax as declaring a "reverse argument" (or an argument to a continuation). By that I mean: you're passing a variable "by reference", but you're passing it backwards to the caller, rather than forwards to another callee.

This seems perfectly reasonable, and easy to teach. It especially makes sense for generators, since a yield statement is effectively sugar for calling a continuation: you can provide any number of arguments, and receive any number of results. (And a generator could conceivably be allowed to return a reference to one of its local variables, because these variables are able to live longer than the yield statement.)

[soraros]

@nmsmith I think now you are in the Swift modify accessor territory, which IIRC Chris explicitly said Mojo was trying to avoid.

[rd4com]

maybe this could make it work without too much changes? :

struct Reference[..., is_decay:Bool=True]:
    fn __getitem__(self: Self[_,_,_,_,False])->Reference[
        self.type, self.is_mutable ,self.lifetime ,self.address_space, True
    ]:
        return __get_ref_as_decay(self)

[nmsmith]

I think adding an extra parameter to Reference, which is already quite bursting at the seams with parameters, would make the type harder to work with.

IMO it makes more sense to have a distinct type.

[ivellapillil]

I am also in favour of eager decay model. Developers need to worry much less about how references are interacting with rest of the code compared to the persistent model.

[helehex]

I'm ok with eager decay

[rd4com]

Yes, decay is like ASAP, nice ! 👍

It would be helpful for new-comers too by reducing the amount of brackets.

Great 🎉

[caimhs]

honestly, I believe the "eager decay" way is more ergonomic, but it fits better how C++ does things, where you can't directly reference a reference, so you need to use the "reference_wrapper" for this.

My feeling is that referencing a reference is such a niche thing that a wrapper would be fine. But, we're kinda stuck, since "Reference" is the perfect name for it already.

Maybe we could add some more reference structs to Mojo if it doesn't overcomplicate things?
We could have something like this:

let ri: Inout[T] = ... // Mutable reference, automatically decays when needed
let rb: Borrowed[T] = ... // Immutable reference, also automatically decays
let rr: Reference[...] = ... // Reference wrapper, no automatic decay

Another option is that decay could only happen in specific situations like function calls, returns, or when the assignment target naturally expects the underlying type.

For example:

var s = "Hello World!"
var r1 = Reference(s)   // Reference[String]
var r2 = Reference(r1) // Reference[Reference[String]]

var s1: String = r2      // Decay happens here, s1 gets the original string
var s2: Reference[String] = r2 // Decay happens here, s2 gets Reference[String]

var s3 = r2      // No decay, s3 is Reference[Reference[String]]
var s4: Reference[...] = r2 // No decay, s4 is Reference[Reference[String]]

[lattner]

For thread hygiene, I'll close this - the design has evolved, keeping with the "eager decay" concept, but with a different implementation over here: #2874