Subscript and more complex objects

[tmzem]

From reading the docs it seems that subscripts are a way to automate selecting (or yielding) one of its inputs or a subobject thereof, and a call to it basically inlines the selection logic into the caller. Since the returned "selection" is not a first-class concept in the language, i wonder how one would go to implement a data structure that references the original object, like

• iterators (aka ranges/enumerators/generators): normally, the iterator would hold a reference to the iterated-over object
• user-defined span (aka slice)-like types: consider the following case: Lets say we create an indexable Deque type backed by a circular array buffer. Creating a DequeSpan to represent a subsection of the deque would again require a reference to the deque object, as the elements would not necessarily be layed out contiguously inside the buffer.

[kyouko-taiga]

Good question! There are two answers.

The first is that the iterator model that you describe might not be the best abstraction to use in a world of value semantics. Iterators break value independence, which causes hard problems to solve. Consider this example in C++, which exposes undefined behavior.

template<typename T>
auto foo(vector<T> const& a, vector<T> const& b) {
  return (rand() % 2 == 0) ? a.begin() : b.begin();
}

int main() {
  vector a = { 1, 2, 3 };
  auto it = foo(a, { 4, 5, 6 });
  cout << *it << endl; // UB
}

This program is wrong because I didn't carefully consider the lifetimes of the iterator returned by foo. Of course, this kind of problems can be avoided, but only with discipline or complex typing rules (e.g., Rust lifetimes).

Swift, for example, uses a different model. Every collection has an index type representing positions in that collection. You can get indices from methods like firstIndex(where:) (just like you'd get an iterator from find_if in C++), but you cannot access a collection's element without access to the whole. Val will adopt the same model.

public fun main() {
  let s = [1, 5, 2, 9, 8, 7, 3, 6, 4]
  if let t = s.first_index(where: fun(x) { x > 5 }) {
    print(s[t]) // 't' is just an index; we need 's' to access the element
  } 
}

The second answer is that Val does in fact have a mechanism to "hold a reference" to the iterated object. We do not call this mechanism a reference, though, because in Val we prefer to think of a span as a projection of some collection. Instead, we use the term "remote part".

public fun main() {
  var s = [1, 5, 2, 9, 8, 7, 3, 6, 4]
  inout t = &s[in: 1 ..< 5] // 't' is a projection of 's'
  &t.sort()                 // we're sorting a slice (a.k.a. span) of 's'
  print(s)                  // "[1, 2, 5, 8, 9, 7, 3, 6, 4]"
}

[tmzem]

So if I understand your last example right both s and t have the same type (array of int), but t is considered to be a projection of s and thus would block s from being used until the up to the last use of t? And the language has basically built-in support for both single-element-projections as well as subarray-projections? And for any other kind of data structure you would need a combination of the original object + an object describing the accessing pattern (i.e. a list of indices)? And how would that desugar into something like a foreach loop?

Also, have you looked into the more recent feature additions for by-ref-semantics in the C# language? If I understand it right, they allow both mutable and readonly by-ref parameters, -returns and -locals. Further, structs can contain ref fields, but such structs have to be specifically marked "ref struct"s which come with many restrictions to allow reasoning about lifetimes without requiring annotations by the programmer. Regular structs and classes cannot contain any reference fields nor fields of ref struct type in order to avoid the situation of references escaping/spreading into arbitrary data structures. Might be an interesting concept to look into.

[kyouko-taiga]

So if I understand your last example right both s and t have the same type (array of int)

Not exactly. s has type Int[9] (fixed-size array of Int) and t has type Slice<Int[9], inout>. A slice is a generic type that represents a contiguous part of a 1-dimensional collection.

Both types conform to a Collection trait, though, so they behave very similarly w.r.t. algorithms on collections (e.g. sort, rotate, ...).

but t is considered to be a projection of s and thus would block s from being used until the up to the last use of t?

That is correct.

Note also that t is an inout projection here, which makes s completely inaccessible. Should t be an immutable projection, then s would be accessible for reading only.

And the language has basically built-in support for both single-element-projections as well as subarray-projections?

Slices are not a built-in construct. They are defined in the standard library. You can create your own slice-like projections for any custom type. For a non-trivial example, consider the program below:

/// A 3-by-3 matrix.
type Matrix3 {

  /// A submatrix of a matrix.
  type Submatrix<base_access: access> {

    /// The base matrix.    
    var base: remote base_access Matrix3

    /// The area that `self` covers in `base`.
    var area: Area

    /// Accesses the `i`-th column of the submatrix.
    subscript column(_ i: Int): var Slice<Double[9], yielded> {
      inout {
        let start = (i + area.y_range.lower_bound) * 3
        let count = start + area.x_range.length()
        yield &base.components[start ..< (start + count)]
      }
    }

  }

  /// The components of the matrix in column-major order.
  var components: Double[9]

  /// Projects a submatrix exposing the contents of `self` covered by `area`.
  subscript (in area: Area<Int>): var Submatrix<yielded> {
    inout {
      var s = Submatrix(base: &self, area: area)
      yield &s
    }
  }

}

public fun main() {
  var s = Matrix3(components: Buffer(filled_by: fun(x) { Double(x) }))
  let t = s[in: Area(x_range: (0 ..< 2), y_range: (1 ..< 2))]
  print(t.column[0][1]) // Prints 4
}

Matrix3 is a custom type representing a 3-by-3 matrix in column-major order. It has a subscript that projects a submatrix using a custom type. Submatrix is composed of a remote part denoting the projected matrix and an area denoting its bounds.

In main, we first create a matrix and fill each component with a different value (note that the element at m[1,1] is 4). Then, we project a submatrix and bind it to t, which now represents the the two first rows of and the central column of s. Finally, we project the first column of t (which is the second column of s) to index its second element.

[kyouko-taiga]

Also, have you looked into the more recent feature additions for by-ref-semantics in the C# language?

I haven't yet. Thanks for the pointer!

[tmzem]

Thanks a lot for this example, it makes stuff a lot clearer.

One thing I still wonder is how the compiler reasons about the projections resulting from the subscript process. Will it just assume any input to the subscript, including the receiver, could have been chosen/aliased and thus restrict access to any of them until the last use of the projection? I.e., would a subscript getElement(_ from: SomeContainer, _ atIndex: Int): Int also conservatively restrict access to the atIndex value?

[kyouko-taiga]

The compiler considers yielded parameters to be part of the projection and other parameters to be bound in the subscript. The distinction is significant for inout projections formed by subscripts that also accept by-value parameters.

Consider the following example:

// Note that 'a' and 'b' are yielded, while 'is_smaller' is passed by value.
subscript min<T>(_ a: yielded T, _ b: yielded T, by is_smaller: (T, T) -> Bool): T {
  inout { if !is_smaller { yield &b } else { yield &a } }
}

public fun main() {
  var predicate = fun(_ a: Int, _ b: Int) -> Bool { a < b }
  var x = 0
  var y = 42
  inout z = &min[x, y, by: predicate]
  print(predicate(12, 13)) // OK: 'predicate' is not projected
  print(x)                 // error: 'x' is projected
  predicate.deinit()       // error: 'predicate' is let-bound
  &z += 1
}

The compiler has to enforce immutability of predicate, because it could be used in the subscript after the projection ends. However, predicate cannot be part of the projected value (it is not yielded), so it may be accessed whereas x cannot.