Non-mutating data references in Val

[tzakharko]

I am trying to understand what limitations are there to the value semantics in Val.

Consider a common problem where one has to parse some in-memory data buffer (e.g. contents of a source file) and then perform some operations on the resulting structure. It is desirable that the parser output contains the location of the relevant span in the original data buffer which can be either used for further processing or user diagnostics. In a language that supports references I would use a span-like construct (pointer + length) that points into the original data and does not allow mutability. This is safe (no mutation = no problem), efficient (no data copies) and easy to reason about (clear ownership structure). There is of course the challenge of managing the lifetimes, but that is mostly an exercise in good software design.

Would it be possible to implement a similar pattern in Val or does value semantics dictate that each span must be a separate copy?

[kyouko-taiga]

There are several ways to approach your use case without reference semantics.

First, you can represent a range with a pair of positions in a collection and use the collection to get accessed to the referred span. For example:

public fun main() {
  var s = [0, 1, 2, 3, 4, 5, 6]
  let t = 1 ..< 4
  &s[1] += 1
  print(s.count()) // 7
  print(s[in: t])  // [2, 2, 3]
}

The key here is that we are not storing access to the data structure in another object, so as to respect the whole/part relationships of our program. t denotes a range in a buffer without conferring access to that buffer.

Second, you can get spans if you use projections in Val. For example:

public fun main() {
  var s = [0, 1, 2, 3, 4, 5, 6]
  let u = s[in: 1 ..< 4]
  // &s[1] += 1
  print(s.count()) // 7
  print(u)         // [1, 2, 3]
}

u is a projection of s that presents a slice (a.k.a. a span) in the range 1 ..< 4. You can use that slice as an object on its own. It may even be mutable!

To preserve value semantics, however, you cannot uncomment line 3. s is not allowed to change while the projection is alive. Accessing it immutably is fine, as we show at line 4, but uncommenting line 3 would be an error, caught at compile-time.

Notice that both solutions satisfy your requirements. They are safe and efficient. Nothing got copied.

There is of course the challenge of managing the lifetimes, but that is mostly an exercise in good software design.

Well, it turns out that managing lifetimes is actually a rather difficult exercise that even experienced software developers can get wrong. The advantage of value semantics is that it prevents mistakes by design because the compiler always catches them.

[tzakharko]

Thanks @kyouko-taiga for an in-depth reply. The solution with indices would be also my first approach (and I use it extensively in my own software). But it does come with a somewhat annoying overhead of having to explicitly supply the data buffer every time the value is needed (on that note, I often dream about a fast and efficient language with statically checked dependent types but I digress...)

Projections would be the ideal solution, but only if projections could "escape" the local scope and be copied and stored elsewhere. I don't suppose that designing a compiler that could track projections across multiple data structures and complex code is even feasible.

[kyouko-taiga]

But it does come with a somewhat annoying overhead of having to explicitly supply the data buffer every time the value is needed

It is true that allowing iterators, spans, etc. to access the referred storage is convenient. But that convenience comes at a very high cost, as it robs the ability for you and your compiler to reason locally about your code. Dave Abrahams talked about this issue at CppCon this year. A video should be posted on the YouTube channel soon.

I don't suppose that designing a compiler that could track projections across multiple data structures and complex code is even feasible.

Projections cannot escape the lifetime of the projecting object. It is precisely this mechanism that guarantees the correct use of the lifetimes in the program. You can, however, pass them to functions with the let or inout convention. That is why the call to print is legal in my example. You may also store them in other data structure (e.g., a slice of a slice) as long as these data structures cannot escape.

public fun main() {
  let s = [0, 1, 2, 3, 4, 5, 6]
  let t = s[in: 1 ..< 4]
  let u = t.suffix[after: 1] // 'u' stores 't'
  print(u)                   // [2, 3]
}

Val aims to remain as simple as possible, so we worked to avoid bringing pointer lifetime annotations into the language. Other approaches have walked this path and met success. Rust is a good example to a large extent. Even more expressive prototype languages can be found in scientific literature (e.g., Walker and Morrisett, 2001, Balabonski et al., 2016).

[tzakharko]

It is true that allowing iterators, spans, etc. to access the referred storage is convenient. But that convenience comes at a very high cost, as it robs the ability for you and your compiler to reason locally about your code.

Oh, absolutely, and I really like Val's refreshing decision to remove reference semantics altogether. I do believe that Rust would be in a better place if it didn't chase down that rabbit hole.

Of course, the drawback is that by removing references you lose coupling between linked data structures and have to maintain those couplings explicitly. This is also not effortless and can lead to hard to detect bugs as well (and likely comes with performance overhead). But those would be logical bugs, not safety bugs, and explicit complexity management is likely result in a better code overall, so I agree that the tradeoff is probably worth it. For everything else there is still unsafe, right? :)

[kyouko-taiga]

For everything else there is still unsafe, right? :)

Yes!