← Back to context

Comment by amluto

7 hours ago

Neat!

I have a question about immutability. In Rust, if I have a shared reference to T (an &T a variable or a parameter), then I have a restriction that I can't modify T or anything in it (which Valen thinks is annoyingly restrictive, and I tend to agree), but I also have a promise that no one else will modify it. The latter is quite nice: it makes the optimizer happier (improves aliasing analysis), makes threading happier (nothing descended from the reference can have data races while the reference is alive), and makes me happier (I don't need to think about descendent values being mutated).

Valen can call into Rust, and I think I can see how, at the site of any particular call, Valen can tell that no one is mutating the referent or its descendents: in a single-threaded world, the only thing executing is the current line of code or a maybe a few consecutive lines of code, and the compiler can see the function's signature and any mutable references therein, and if there is no permission to modify a descendent, then it doesn't get modified.

But in a multithreaded world, especially if calling into Rust in a thread, doesn't there need to be a way to guarantee the immutability of an object across an entire region of code? How does that work in Valen?

And for making immutability more comprehensible to people and to local analysis in general, would a special type of reference meaning "yes, this one really is fully frozen and there are no mutable paths into it for the entire lifetime of this reference" be a nice feature?

(Aside: I've occasionally contemplated whether Rust would benefit from another flavor of reference: no-access. A no-access reference would guarantee the referent's existence but could coexist with shared and with mutable references. Safe code would be unable to read or write through such a reference. Other than making some cell-like types mildly less mind-bending, I'm not convinced I have an actual justification for this thing. This would give Rust three flavors of references.

But I can imagine a Valen-like language having three flavors of references: frozen references (cannot use them to mutate and there's a promise that no one else can either), exclusive references (fully mutable, etc, just like Rust's &mut) and flexible references (the kind of reference in the blog post).)

9 comments

amluto

Reply
verdagon  5 hours ago

Awesome question, you're getting at the good stuff.

Short answer: Valen would have something similar to Fn and FnMut (but phrased in terms of effects rather than Fn vs FnMut). In other words, we would be able to express "a closure that does not modify anything it captures", or rather, "a closure that has no mut effects".

That closure, because it doesn't modify anything it captures, would be safe to share among multiple threads in a structured-concurrency-like / std::thread::scope-ish way.

The key here is that one _can_ express immutable references in Valen; an immutable reference is a reference that the containing function doesn't express a `mut` effect for. And once we have immutable references, we get all of the nice concurrency benefits that Rust trailblazed.

I'd also like to make a way to do the above without a function call, perhaps using something like the `parallel` keyword I described in [0].

A no-access reference is an interesting idea. That could be a more powerful way to express may_dangle. In Valen, I hope to have an "opaque" group to express something like that.

I don't know whether it's a good idea, but in Valen I'm trying to decouple access capabilities away from the reference types as much as possible. We'll see if that bet pays off.

[0] https://verdagon.dev/blog/seamless-fearless-structured-concu...

  • amluto  4 hours ago

    > The key here is that one _can_ express immutable references in Valen; an immutable reference is a reference that the containing function doesn't express a `mut` effect for. And once we have immutable references, we get all of the nice concurrency benefits that Rust trailblazed.

    I'm contemplating this. Is it enough?

    Suppose I have an object (I'm not even trying to get the syntax right, especially since Valen's syntax appears a bit different from Rust's):

        let obj: T = ...;

    And I also create a structured concurrency thingy in the same scope:

        let workgroup: StructuredConcurrencyThingy = ...;

    Now I pass references to both of these down the callchain, through a few functions, maybe via some structs with lifetime parameters, and in the inner function I do this:

        workgroup.submit(move || print_in_rust(obj));

    where print_in_rust is a Rust function taking &T. (I haven't the faintest clue how to spell that in Valen.) So I'm making a closure, and the closure captures obj, and the closure needs obj to exist and be immutable for the lifetime of the closure, which exceeds the creating function's lifetime. It's bounded by the workgroup's lifetime, and Rust is fine with this.

    But, if I'm understanding you right, the immutability of the referent of obj depends on the signatures of everything in the callchain that might execute during the lifetime of the closure. How does that work?

    edit: On further contemplation, I don't think that actual concurrency is needed to illustrate it. I think the same issue exists if I have a T<'a> that has a method that takes an &'a reference (probably like store_a_reference(&mut self, ref: &'a u32)) and dereferences ref both immediately and later and asserts that it sees the same value both times.

    • verdagon  2 hours ago

      Sorry, I think my attempts to simplify/explain ended up confusing things. I'll try to be a little more precise.

      In Rust, a reference is forever shared/immutable or forever unique/mutable.

      In Valen, a reference is... "it depends". Specifically, it depends on the context.

      It's similar to a &GhostCell<T>, where its mutability isn't determined yet because the GhostToken isn't present yet.

      So, what determines the mutability at any given point in time? The function's `mut` effects (or lack of them) for the group/path that the reference is pointing to.

      So we can imagine a `execute_on_4_threads` function like this:

          func execute_on_4_threads<C', F: Func<void, (), C>>(
      workgroup: &W,
      closure: F
    ) { ... }

      (`Func<void, (), C>` is a trait for a function that returns void, takes no extra parameters, and names its captures as group C).

      The most relevant fact here is that this function doesn't declare any `mut` effects at all (not on C, not on W's group, nothing), so nothing is being mutated. (And because of that, this function's callees also can't have any `mut` effects; they also can't mutate the data)

      Now let's say we changed `workgroup`'s type to `&W in w`, and added a `mut(w)` to the function, to describe that we might modify the workgroup.

      At that point, we would still know that we can invoke the closure from 4 threads, because we declared no relationship between `w` and `C`, so the compiler assumes (and enforces) that they're disjoint, have no overlap, nothing in one aliases anything in the other.

      Hopefully that helps. Maybe I should write a blog post on this, my posts are usually clearer than my HN comments.

      (Also, I'm not sure I understand your edit, if you could clarify that would be much appreciated)

      1 reply →

AlotOfReading  5 hours ago 

    I've occasionally contemplated whether Rust would benefit from another flavor of reference: no-access.

Most of the uses for this I can think of are best solved by opaque pointers for FFI. Having a rust-native reference just seems incongruous. Like, does it have size and alignment info? How would it interact with NLL? The only way I can imagine it working is if it extended referent lifetime throughout the lexical lifetime of the reference, but that defeats the purpose of NLL.

Rust solves a similar problem in closures with unique immutable references, but they're not quite the same.

  • amluto  4 hours ago

    In my mind, a no-access reference would have exactly the same lifetime rules (except for the exclusivity part) as any other reference. And they'd have the same size and lifetime rules.

    Unsafe Rust could promote a no-access reference to a shared or a mutable reference, and the unsafe code would be responsible for not violating exclusivity rules but would have a guarantee that the referent actually exists. Using unsafe code to create a no-access reference to a nonexistent object or to a misaligned object would be UB.

    Safe code could convert the other way:

        let a: &mut u32 = ...;
    let b: &noaccess u32 = a;
    let c: &u32 = ...;
    let d: &noaccess u32 = c;

    This is not an entirely serious proposal.

    • AlotOfReading  3 hours ago

      Under NLL, reference lifetime is defined by the places where the reference is used, and noaccess types can't be used. So then reference lifetime has to devolve to the spans where the reference is live, which is only defined lexically.

      So for example:

          let mut data = vec!['a', 'b', 'c'];
    let b: &noaccess [char] = &data[..];
    data.push('d'); // Does this error?

      Hence the question

      1 reply →

    • zozbot234  3 hours ago

      It may be interesting to focus on how exactly these planned "no-access" references would differ from raw pointers? Access through raw pointers is an unsafe operation already.