Array Manifesto

[mark-koch]

Here are some of my thoughts on how to move forwards with arrays.

Compile-time unknown sizes

We should allow a variant of arrays where the size is not tracked by the type system. In Guppy itself, I think it would make most sense for users by overloading the array type to support both of these variants:

• array[int] is an array of integers whose size cannot change but is not known by the compiler
• array[int, 42] is an array of exactly 42 integers

This way, we can frame the size as an optional annotation to users instead of a totally separate type.

Conversion

array[T, n] should implicitly coerce to array[T], i.e. whereever an unsized array is required, it's also fine to pass a sized one. The other way around requires intervention from the user. Concretely, I propose the following methods on array:

• try_as_sized to return sized array or nothing if the size doesn't match. We can provide two overloads:

  def try_as_sized[T, n](self: array[T]) -> Option[array[T, n]]: ...
  
  def try_as_sized[T](self: array[T], n: nat @comptime) -> Option[array[T, n]]: ...

• as_sized, the panicking version of the above

Inference

Type inference should infer the size wherever possible:

xs = array(1, 2, 3)  # Inferred type: array[int, 3]
ys = array(i for i in range(3))  # Inferred type: array[int, 3]
zs = array(i for i in xs)  # Inferred type: array[int, 3]

Slicing

We should also introduce Pythonic slicing of arrays. Luckily for us, slicing a list Python returns a new list, so we don't run into our usual Python semantics problem of having multiple references to the same object:

# In Python:
xs = list(range(3))
ys = xs[1:-1]
ys[0] = -1
print(xs)  # [0, 1, 2], not mutated!

In Guppy, we can follow the usual runtime borrow checking logic we already used for array indexing: We implicitly use option-arrays and swap each sliced linear element with None. Our inout mechanism can will write values back afterwards. Therefore, simliar to indexing, we should allow slicing on linear elemts in inout positions:

qs = array(qubit() for _ in range(10))
rs = qs[:5]  # error: slices are only allowed to be borrowed, not moved

The runtime borrow checking also means that we can't have overlapping slices of linear data:

qs = array(qubit() for _ in range(10))
foo(qs[:-1], qs[1:])  # Runtime error: linear element already borrowed!

Finally, we can even infer the size of slices if all slice parameters (start, step, stop) are known.

Renaming to List

Finally, we can start resuing the builtin list syntax to talk about arrays. This would make the syntax more concise and easier to pick up for people coming from Python.

[GBoydQ]

Could you get around the restriction of compile-time unknown array sizes if you only allow comptime variables in the slicing? (I imagine in almost all cases the slices wouldn't be dependent on measurement results)
If so it would be possible (although I don't know how difficult) for the compiler to infer the size of the slices

[mark-koch]

Yes it's possible, as long as the array size is also known exactly (i.e. not generic). If you slice qs[start:step:stop] on an array of size n, your output will be of length (roughly) (min(stop, n) - start) // step. The problem is that we can't express this as soon as one of these values is a variable instead of a known constant.

I imagine in almost all cases the slices wouldn't be dependent on measurement results

Probably not on measurement results, but possibly on function inputs or other expressions depending on unknowns at checking time. For example, to slice a generic array of length n in half, you'd do qs[:n//2], but you would get an array of length n//2 which we can't express in the type system. An alternative to compile-time unknown array sizes would be to make the type system stronger to express arbitrary expressions as array lengths (see #785 for some thoughts on that).

Do you think having slices would be useful, even if so heavily restricted (i.e. every number involved must be a literal)?

[GBoydQ]

The case I originally came across this was just needing something along the lines of foo(qs[1:], qs[0]), so even a restricted version of #785 just allowing addition/subtraction would help for that, although perhaps it is not a common enough scenario to be worth the time.