How can we represent C++ style iterators in Val?

[kyouko-taiga]

C++ uses iterators as one of its core idioms. A represents a position in a collection and provides access to that position. Because Val upholds value uniqueness, one may wonder how iterators can be expressed in Val or, more generally, any data structure that provides access to another object.

Here are my thoughts on this topic. I will use std::string_view as a running example.

Disclaimer: I am not a C++ expert and am therefore likely to overly generalize. Feel free to correct me in the answers.

As projections:

The first approach uses remote parts and is the closest to what (AFAIU) one does in C++. It roughly matches how I implemented Iterator in this gist. More generally, I think this is how we should implement slices in Val. In that sense, a string view is just a slice of a string.

public typealias StringView<a: let | set> = Slice<a, String>

public type Slice<base_access: let | set, Base: Collection> {
  /// The collection of which `self` is a slice.
  var base: remote base_access Base
  /// The start index of `self` in `base`.
  var _start_index: Base.Index
  /// The end index of `self` in `base`.
  var _end_index: Base.Index
}

conformance Slice: Collection { ... }

A lot of the heavy lifting is done the Collection trait, which operates exactly like Swift's.

Here's a usage example. Consider the following C++ program:

int main() {
  const string s = "abc";
  string_view t(s);
  t.remove_prefix(1);
  cout << t << endl;
  cout << s << endl;
}

In Val, we would write this:

public fun main() {
  let s = "abc"
  var t = StringView(s) // note: 't' is 'StringView<let>'
  &t.remove_first()
  print(t)
  print(s)
}

In a nutshell, the Collection trait describes an index-based API to access the collection's elements. You use first_index and end_index to get the first and "past the end" positions and index(after:) to "advance". Finally, you have a subscript that projects elements at a given position.

In these three methods and subscript roughly describe a forward iterator. Consider the following C++ program:

int main() {
  const string s = "abc";
  auto it = s.begin();
  while (it != s.end()) { std::cout << *it << endl; it++; }
}

In Val, we would write this:

public fun main() {
  let s = "abc"
  var i = s.start_index()
  while i != s.end_index() { print(s[i]); &i = s.index(after: i) }
}

Because StringView<a> (a.k.a. Slice<a, String>) is also a collection, it has the same API.

The problem with this approach is that, as of now, it doesn't let you "store" a string view inside another collection. For example, consider the following C++ program:

int main() {
  const string s = "abc";
  const vector t = { string_view(s), string_view(s) };
  for (auto u : t) { cout << u << endl; }
}

In Val, the same program won't compile:

public fun main() {
  let s = "abc"
  let t = Array([StringView(s), StringView(s)])
    // ^^^ error: type 'StringView<let>' does not conform to 'Sinkable' 
  for let u in t { print(u) }
}

We may find a way to improve on our design to support dynamic collections of projections, but there are many hurdles we need to overcome. I won't delve into the details but feel free to ask if you are interested.

As pairs of indices:
The second approach solves the above storing issue by forgoing the remote part. Instead, you only store a pair of indices in the base collection and use it to project a slice whenever you want.

public typealias StringView = Range<String.Index>

Let's go back over our examples. First we had this C++ program:

int main() {
  const string s = "abc";
  string_view t(s);
  t.remove_prefix(1);
  cout << t << endl;
  cout << s << endl;
}

Now we write this in Val:

public fun main() {
  let s = "abc"
  var t = StringView(s.start_index(), s.end_index())
  &t.lower_bound = s.index(after: t.lower_bound)
  print(s[in: t])
  print(s)
}

The second example was illustrating the use of the index API, which is kind of obvious now that we're using indices to represent string views. Let's instead focus on the third example, which was inexpressible in Val. In C++, we had:

int main() {
  const string s = "abc";
  const vector t = { string_view(s), string_view(s) };
  for (auto u : t) { cout << u << endl; }
}

Now in Val we can write this:

public fun main() {
  let s = "abc"
  let t = Array([
    StringView(s.start_index(), s.end_index()),
    StringView(s.start_index(), s.end_index())
  ])
  for let u in t { print(s[u]) }
}

Now it works, but notice that we always need explicit access to the base collection (here, s) every time we want to read its contents. That's fine in this kind of small examples, but becomes quite inconvenient when want to pass things around in functions.

For example, if you want to refactor the for loop in a different function, it will have to accept the base string as an additional argument. I call this the "context piping problem".

fun print_views(_ slices: Array<StringView>, in base: String) {
  for let slice in slices { print(base[slice]) }
}

The "context piping problem" often occurs when we're trying to work on large data structures without reference semantics. For example, it's a common problem in React.js applications. I'm happy to present examples if you're interested.

A second problem (which David Sankel pointed out) is that nothing statically guarantees that we're using indices in the correct collection. For example, this program compiles:

public fun main() {
  let s1 = "abc"
  let s2 = "def"
  let t = StringView(s1.start_index(), s1.end_index())
  print(s2[t]) // uses indices of 's1' to access 's2'
}

We could solve this problem with path dependent types, as found in Scala, but beleive the complexity cost outweigh the benefit. I'm happy to expand on the details if you are interested.

What Rust can do but Val cannot
Rust can circumvent the storing problem using lifetime annotations. Basically, it has a way to expose the lifetime of a remove part to type system. To understand how that's different from Val, let's look at the first example again:

public fun main() {
  let s = "abc"
  var t = StringView(s) // note: 't' is 'StringView<let>'
  &t.remove_first()
  print(t)
  print(s)
}

In Rust, t would have a type that preserves its relationship to s explicitly. One could think of something like StringView<let s> (rather than just StringView<let>). So now if we put t inside another generic type, the relationship to s is also preserved, as in Array<StringView<let s>> for example.

In Val, the relationship is kept implicit. That works because if t cannot escape, then it's easy for to just track all uses and projections of s in the scope; the compiler "sees" everything. Once we cross function boundaries, we either need whole program analysis or a richer type system.

Other approaches
We have other ideas to work around the storing problem. Dave and Lucian have explored the use of wrapper types that bundle indices together with a remote access to the base collection. This trick essentially allows us to switch between the range and slice approach whenever we want.

Notice that the collection's API with which we've been playing already supports this approach, because Slice<a, T> is essentially a bundle combining a pair of indices in an instance of T with an access to that instance. So when we're writing collection[in: range], we're creating a bundle.

Another idea is to address the "context piping problem" with implicit parameters. In broad strokes, functions that require access to a whole can accept it as an implicit parameter so that it can be omitted at call sites. Here's how that could work in Val:

public fun main() {
  let s = "abc"
  let t = Array([
    Range(s.start_index(), s.end_index()),
    Range(s.start_index(), s.end_index())
  ])
  for let u in t { print_view(u) }
}

fun print_view(_ view: Range<String.Index>, base: implicit String) {
  print(base[view])
}

This approach is (or at least it was a couple of years ago) popular in React.js. AKAIK, it's also common in Scala.

I am personally getting increasingly convinced that implicit parameters are really interesting, but their design is not high on the priority list at the moment.

[mlathan]

Just a few weeks ago I learned about Hylo and find it very interesting. What is the current state of realizing something like a "StringView" in Hylo as of today?

[kyouko-taiga]

You can go a long way if you're willing to use the unsafe API to create a safe abstraction around raw pointers. The main challenge is to preserve lifetimes but that can be done quite easily by leveraging Hylo's subscript mechanism.

[mlathan]

The challenge is to preserve lifetimes; yes.

Now imagine there is a fictional a: Array<String> and b: Array<StringView>. I want to reference some strings of a, but not all in b as efficient as possible, no copy. Then I want to use b in a funciton f to access the some Strings of original a.

As far as I understand subscripts in Hylo, f would require the original a to be able to use a subscript on it. To transfer the indices for the subscript to access the data there would be a second parameter which is a collection of the indices which would be in b (data source + indices)?

This is kind of the Range<> approach from your discussion above. So maybe I thought you were chasing the idea of Scala's implicit parameters or something. In this case a as implicit parameter to f and the indices as explicit parameter?

[dabrahams]

As far as I know a string view would be a simple slice projection out of a string, accessed with a subscript. Did you have something else in mind?