Real arrays

[lerno]

The "problem" with real arrays have been discussed previously, but I start a new topic here since those discussions are pretty much dead. Instead of arguing for why, let me just write the proposal.

1. All arrays are always passed by reference.

Code: [Select]

func void some_function(int[] x)
{
    x[0] = 1;
}

int[3] x = { 2, 3, 4 };
some_function(x);
assert(x[0] == 1);

2. Passing an array is structurally identical to passing in a struct with length + pointer.

This means that the array some_type[] is exactly equivalent to:

Code: [Select]

type struct
{
   pointer_size length; // <- decide whether this should be platform independent or not.
   some_type *start;
}

BTW, I considered whether we should allow variable bit sizes for the length variable. My conclusion is that it would make the feature too complex. Custom structs are better if that is desired.

3. As a consequence we can define slices on an array, simply by varying the start and length.

Note that the strategy here has to be different if we go with "restrict by default" compared to only using restrict like C does it (aliasing by default). In the latter case, much performance can be gained by having pointer + offset + length instead of pointer + length. If space is an issue for the latter, we can rewrite the struct in this manner:

Code: [Select]

type struct
{
   half_pointer_size offset;
   half_pointer_size length;
   some_type *ptr;
}

This way it's easy to analyse the original pointer, even for slices of that array, and arrays / slices can be used interchangeably.

4. Arrays have manual memory management.

Not much to say about that except for needing an custom allocator function for arrays as it must set the length in the returning data.

5. It should be possible to cast an array to a struct.

Array layout should be fixed with the language, and casting an array to a struct (using whatever fixed layout we decide on) is fine.

6. Undefined behaviour

Changing the value of an underlying pointer, length, offset of an array leads to undefined behaviour.

7. Optional bounds check

Bounds checking is optionally inserted on debug builds.

[lerno]

Discussion

1. Should slices have special syntax?

We could potentially use the bit-slice syntax to pull out parts of an array. However, since they don't really match up we have some freedom to decide whether we have <lower index>:<high index inclusive>, <lower index>:<high index exclusive>, <lower index>:<size>

Since arrays are used as first class objects, it makes sense that creating slices of arrays similarly has special syntax.

Code: [Select]

int[] a = { 1, 2, 3, 4, 5, 6 };
int[] b = a[2:3]; // { 3, 4 }, { 3 } or { 3, 4, 5 } depending on definition.

Note that a slice does not outlive the lifetime of an array.


2. Negative indexing

It is possible to use negative indices as shorthand for length - index. So a[-1] is the same as a[a.length - 1]. It's very convenient but means extra instructions. Basically it means unpacking any a to a.start + (i < 0 ? a.length - i : i). Expensive!

3. Extending array methods

Since arrays are generic-ish, we'd need some more generic way of expressing function on it. But it would be useful. The aforementioned negative indexing could be implemented as a function:

Code: [Select]

func any[].slice(any[] array, i64 index, i64 length) {
    index = index < 0 ? index + array.length;
    length = length < 0 ? length + array.length;
    return array[index:length];
}

(In general, considering generic functions is important!)

4. Growable arrays

This is a topic on its own. But let's just mention that it needs some kind of memory management and as such we should consider memory management a bit in detail (in another topic)