Should `Vector` support a second dimension?

[jonathanhogg]

There are a few places where I am implicitly treating Vector as having a second dimension:

• In multiple-binding for loops (for a;b;c in v)
• In zip(), which takes multiple vectors and produces a vector suitable for multiple-binding
• In functions that take an optional group-size argument, e.g., sum() and accumulate()
• In functions that produce or consume pairs, e.g., polar() and angle()
• Explicitly in the Matrix33 and Matrix44 sub-classes of Vector

Would all of this be neater if I just supported a second dimension to vectors? I hesitate to call this a "matrix" as I feel that ought to be reserved for fixed-size objects rather than the variable length objects the first four of these usages operate on. I'm going to call these "arrayed vectors" for the moment based on the C++ terminology of arrays being fixed-length and vectors being variable-length.

So the array part of an arrayed vector would be a size value that the vector length becomes a multiple of. Mostly no changes to the model would be required except for adding a new attribute that contains this array size and some changes to how indexing works.

Let's say that zip consumes m flat vectors (i.e., vectors with an array size of 1) and returns an arrayed vector with an array size m. Indexing or iterating over this should produce m-vectors. If multiple-binding for loops were redefined such that the names are bound to each element of the vector produced by iterating over the loop source, then the overall behaviour of:

for a;b;c in zip(as, bs, cs)
    ...

stays the same. However, looping with multiple names over a flat vector would always result in binding each element to the first name and setting the other names to null.

Functions that implicitly return arrayed vectors, like polar() could just explicitly do that and therefore could still be iterated over naturally:

let n = 12
    indices = 0..n

for x;y in polar(indices/n)
    ...

However, now one could also naturally index the results:

let n=12
    indices = 0..n
    coords = polar(indices/n)

for i in indices
    let x;y = coords[i]
    ...

which would improve the various places in my code where I have ugly indexing like coords[i*2..(i+1)*2]. Functions like angle() would take 2-arrayed vectors and return flat vectors. hypot() would take an n-arrayed m-item vector and return a flat m-item vector with the n-dimensioned hypotenuse of each item. sum() and acculumate() would lose their second argument and just do The Right Thing with any n-arrayed vector they are given.

Matrix33 and Matrix44 are only used internally, but it would make sense for these to match 3-arrayed and 4-arrayed vectors in terms of their attributes. It might be neat to abstract out operations into Vector that can easily work with any size of matrix – like translate, scale, vmul, mmul and transpose.

[jonathanhogg]

Constructing

Logically, an arrayed vector is a vector of arrays. Arrays are not something that currently exists in the language so I clearly need new syntax, but do I also need new semantics? Semicolon is currently used to concatenate vectors and I don't think it's a good idea to change that. Is an array also a vector? In which case, arrayed vectors are actually vectors of vectors?

The vectors-of-vectors idea kind of makes sense looking at a multiple-binding for loop:

for x;y in polar(0..1|0.01)
    ...

The x;y construction suggests that x and y are elements of a 2-vector, but if I write 0;1;2, how do I know whether that means a 1-vector containing a 3-vector or a 3-vector containing 1-vectors? Brackets alone don't help me – e.g., (0;1;2);(3;4;5) – as they are currently strictly for explicit structuring of evaluation order and changing that feels like a problem.

I could use a different character for constructing arrayed-vectors, like a comma – for example: 0,1,2;3,4,5. This looks like a mistake as I can barely see the difference between a comma and a semi-colon, but we could try a clearer character, like maybe a pipe/bar: 0|1|2;3|4|5. This feels a little clunky. An alternative might be syntax for taking a flat vector and turning it around into an array, perhaps: [0;1;2];[3;4;5]. This might feel a little more natural compared to nested data structures in other languages.

So [v] would mean: take the flat n-vector v and turn it into a 1-vector n-array. As I'm only proposing a second additional dimension, [[v]] would be illegal – either returning null or perhaps flattening [v] before making it into an array.

I'm not a big fan of the square bracket syntax, but if I ditched queries (see #17) then I could re-purpose braces, a la: {0;1;2};{3;4;5};{6;7;8}. Then maybe the correct unpacking-for syntax should actually be:

for {x;y} in polar(0..1|0.01)
    ...

and the old for x;y in ... syntax would continue to mean taking multiple items from the source vector in each iteration.

If I go for vectors-of-vectors – which does appear to be most orthogonal on the face of it – then I should consider that a vector can contain vectors of different length or of non-numeric types. So the following would also be valid?

{:key;1;2}
:key;{1;2}
{0};{1;2;3};{4;5}

Perhaps the smart thing to do under-the-hood is to have vectors of fixed-length numeric sub-vectors be a single array of doubles in .numbers and a .stride attribute (I'm going to call array size stride when referring to numerical vectors now), and then have anything else be actual Vector objects stored in the objects list?

Vector concatenation would consist of quickly checking the strides and types (numeric/other) of the vectors to see if they are compatible and then either writing them into a single .numbers array or putting them into an .objects list. This would only be a small change from the current .concat() logic.

Maths operations will need some re-thinking. What does v + 1 mean if v is a vector-of-vectors? What does v + {1,2,3} mean? Possible answers:

• ({0;1;2};{4;5;6}) + 1 ➡ ({0;1;2};{4;5;6}) + ({1;1;1};{1;1;1}) ➡ ({1;2;3};{5;6;7})
• ({0;1;2};{4;5;6}) + {1;2;3} ➡ ({0;1;2};{4;5;6}) + ({1;2;3};{1;2;3}) ➡ ({1;3;5};{5;7;9})
• ({0;1;2};{4;5;6}) + (1;2) ➡ ({0;1;2};{4;5;6}) + ({1;1;1};{2;2;2}) ➡ ({1;2;3};{6;7;8})

To be consistent with current maths operations, it would probably also need to be the case that:

• ({0;1;2};{4;5;6}) + (1;2;3) ➡ ({0;1;2};{4;5;6};{0;1;2}) + ({1;1;1};{2;2;2};{3;3;3}) ➡ ({1;2;3};{6;7;8});{3;4;5})

I think I'd need to consider all other variants as invalid, including operations on numerical vectors with different strides – repeating elements the same way I do for vectors now sounds viable, but I think it's going to be a mistake. Likewise, I think I'd need to disallow vectors-of-vectors containing numerical vectors of different lengths in the .objects list.

An alternative that keeps this rule sacrosanct is actually to say that a vector-of-vectors always has a single .stride and non-numeric vectors-of-vectors are just a single .objects list that contains all items with the stride applying to that list too…

[jonathanhogg]

Indexing

Going with the vectors-of-vectors thing, indexing should also return a vector-of-vectors to be consistent with current indexing, which returns a vector containing zero or more items from the original vector. So:

let foo = {0;1;2};{3;4;5};{6;7;8}

foo[0] == {0;1;2}
foo[1;2] == ({3;4;5};{6;7;8})

What about foo[3]? It should return null, but should it return a null that is a zero-length vector of 3-vectors? i.e., can a vector have zero .length but a non-zero .stride? Does this even matter? Are there any situations where different flavours of null would have an important meaning? I'm gonna guess no for the moment.

How do I unpack a sub-vector and index into that? Perhaps the obvious thing is a second "argument" to index brackets. So:

foo[0, 1] == 1
foo[1;2, 2] == (5;8)
foo[0, 1;2] == {1;2}
foo[1;2, 1;2] == ({4;5};{7;8})

I am assuming here that a stride of 1 is a normal vector, so that's what the first two expressions evaluate to.

It is likely to be useful to pull out an element from every sub-vector/array without knowing the length of the vector, maybe:

foo[.., 1] == (1;4;7)

I could allow ranges with no start or stop to be valid and have them return a special "infinite" range object that would only be valid for indexing and would equate to "everything". This would be a bit like the special random-source Vector sub-classes. It should therefore be valid to use this on its own. As long as foo is a normal vector and not a random-source:

foo[..] == foo

There is an argument that this might as well be extended to ranges that exclude only the stop value, i.e., 1... Again, this would only be valid for indexing but would mean everything from the start index onwards. I think I would continue to expand all finite ranges out to a literal vector, although this could be seen as a function of the partial-evaluator's eagerness to create literals.

Logically, any indexing operation without a second argument has an implicit .. infinite range as the second argument, i.e.:

foo[0] == foo[0, ..] == {0;1;2}

I think I'm going to say that indexing with a non-unit-stride vector is an error and returns null, so:

foo[{0;1}] == null
foo[.., {0;1}] == null

However, logically {1} is the same thing as 1 – they are both unit-stride vectors of length 1 – and so this would be valid:

foo[{0};{1}] == ({0;1;2};{3;4;5})
foo[.., {0}] == (0;3;6)

Also, continuing on with the current tradition, because every value is a vector it is valid to index multiple times in a row:

foo[1, ..][.., 1] == 3

[jonathanhogg]

On pseudo-random sources

I can foresee a bunch of use cases for being able to generate pseudo-random vectors-of-vectors, like creating random coordinates. I would suggest that it is logically sensible to support:

let starting_positions = uniform(:start)[..10, ..3]

To create a 10-length, 3-stride vector of uniform values. As these values must be repeatable, it'll require a bit of re-jigging of how pseudo-random sources are indexed.

The current algorithms expect a single unsigned long long index. I could perhaps do some bit-shifting and -masking and assign part of the 64-bit space to the primary index and some to the secondary index. On the assumption that the secondary index is likely to be smaller than the first, this could be something like 48-bits and 16-bits.

In fact, if I did:

cdef unsigned long long index = primary ^ ((secondary << 48) & (secondary >> 16))

then this would be identical to the current behaviour where the secondary index is 0, which would need to be the case when a secondary index is not given. Secondary indices larger than 16-bits would also still return a varying result, it would just overlap with another part of the pseudo-random-number space.

Interestingly, this would provide an alternative way to get a new set of numbers instead of changing the key, i.e.:

let hues = uniform(:hue)[..n, beat]

instead of:

let hues = uniform(:hue;beat)[..n]

The former being faster as uniform(hue:) is a literal value.

Infinite ranges would, of course, be invalid for indexing pseudo-random sources.

[jonathanhogg]

Required changes

• model: Add .stride to Vector and update logic around .length and allocating numbers
• model: Update all mathematical operations to do The Right Thing with .stride
• model: Push obvious operations from Matrix33 and Matrix44 sub-classes up into Vector
• functions: Update PRNG classes to reflect new indexing scheme
• functions: Update numerical functions to do The Right Thing with .stride
• parser: Decide on fate of queries and syntax for lifting a flat vector into a vector-of-vector
• parser: Update grammar and AST for constructing and indexing vectors-of-vectors
• parser: Update grammar and AST for unpacking-for loops
• vm: Add new instruction for rotating a flat vector
• vm: Update/replace Index* and Slice* instructions
• vm: Update Next instruction for more complex unpacking

[jonathanhogg]

Something I've not considered so far is how to rotate an array back to a vector – i.e., if {1;2;3} turns the 1-stride 3-vector 1;2;3 into a 3-stride 1-vector, then how do I go the other way? Perhaps I need a "flatten" operator that just sets the stride to 1 for any arrayed vector.

What would this look like? Trying to think of characters I've not already used it could be something like: x!, ^x, &x, |x|, ~x. I sort of like the latter, ~x on the basis that it looks a bit like a { on its side / rotated.

Also, what does {x} do if x is already an n-stride vector? I'd say it either returns null or, on the assumption I have a flatten operation, then the smart thing to do would be to flatten it and then raise it to an array.

Finally, thinking again about let unpacking. Is it OK to mix array and vector unpacking like:

let {x;y};z = ...
let {x1;y1};{x2;y2} = ...

Seems complicated, but also makes sense…