Slicing two-dimensional arrays

[Richard Russell]

In another thread I have proposed extending the arraylib.bbc library to support not only slicing of one-dimensional arrays but also slicing all or part of a row of a two-dimensional array. Having experimentally implemented it locally, here's how it could work:

Code: Select all

      INSTALL @lib$ + "arraylib"

      DIM array(3,3), vector(3)

      array() =  1,  2,  3,  4, \
      \          5,  6,  7,  8, \
      \          9, 10, 11, 12, \
      \         13, 14, 15, 16

      vector() = 0, -1, -2, -3

      REM Slice row 2 of the array and modify it:
      PROC_rowslice(array(), temp(), 2, 0, 4)
      temp() = vector()

      FOR row = 0 TO 3
        FOR col = 0 TO 3
          PRINT array(row, col);
        NEXT col
        PRINT
      NEXT row

The output is:

Code: Select all

         1         2         3         4
         5         6         7         8
         0        -1        -2        -3
        13        14        15        16

You can see that row 2 of the array, specified as the third parameter of PROC_rowslice(), has been modified to contain the values in vector().

If you have any comments ahead of me releasing the new version of arraylib please post them here (the Forum, not the Group).

[hellomike]

I personally like the approach.

A user however might in addition also expect a column equivalent added to the library. I.e.:

Code: Select all

PROC_colslice(matrix(), temp(), 2, 0, 4)

Yet, I don't think that can work in the same manner. With the alias.
And then the different approach might be confusing.

I might be mistaken of course.

Regards,

Mike

[Richard Russell]

A user however might in addition also expect a column equivalent added to the library.

It's impossible (without moving data around in memory) - and DeepSeek knows it's impossible too because the way it used slicing in the Matrix Inversion code was limited to what can actually be achieved:

Code: Select all

        aug(i%, 0 TO N%-1) = input(i%,)
        aug(i%, N% TO 2*N%-1) = 0
        aug(i%, i%+N%) = 1

The point is that slicing shouldn't need to move data around, that's what makes it fast, and therefore the elements in the slice must be consecutive in memory - which they are in the case of a row but not in the case of a column.

Of course the arraylib library does also have PROC_transpose() so if you really want to extract a column you can transpose the array first, but that will be comparatively slow.

I should add, if it isn't obvious, that a slice isn't a copy of what's in the source array, it's an alias of it - which is why you can modify the slice and at the same time modify the original array.

[Richard Russell]

This is probably a crazy idea, especially given the risks associated with making changes to BBCSDL in my present condition, but writing the array slicing procedures for arraylib.bbc has made me realise that I could (in principle) incorporate that code in the interpreter itself!

I had previously concluded that built-in array slicing was impossible, because a variable look-up can only return a scalar object (e.g. a number or a string) or an entire array (or structure); there is no way that it can return part of an array.

But the way the routines in the library work is that they return an alias array: an entire array that maps to part of another array (restricted to consecutive elements). By using the same trick in the interpreter, I now believe I could support array slicing after all.

I've looked at where in the code such a feature would have to slot-in and, fortunately, I think it can be added with little risk of breaking the existing code. There's plenty of opportunity for bugs in the slicing code itself, but that's not so important.

Do you think this is something worth pursuing? Array slicing is certainly something that I've always wished BBC BASIC could do, and the fact that DeepSeek wrongly believed that it can has had an impact!

[hellomike]

Even though I myself do not use BBCSDL extensively, I firmly believe that all progress and new functionality is welcome.
I'm glad to see that you found strength in interacting with AI and am eager to see what endeavors it will amount to!

Wish you all the best.

Mike

[Richard Russell]

Even though I myself do not use BBCSDL extensively, I firmly believe that all progress and new functionality is welcome.

As I've explained many times before, I've always valued stability and freedom from bugs over feature bloat, which has afflicted so many other languages (not least Python). This is particularly true of interpreted languages, in which any new feature potentially slows down execution (e.g. because of less efficient cache usage) and increases the size of every 'compiled' application bundle, even if the program doesn't use that feature.

So, long before my deteriorating health became an additional complication and risk factor, I adopted the policy that I would not consider extending the core BBC BASIC language unless (a) the proposed extension couldn't be satisfactorily achieved by means of a library, (b) it would be of sufficiently general value to benefit a significant number of users and (c) it could be achieved safely with minimal bloat and/or performance hit.

It's difficult to argue that array slicing, at least the limited kind that it's practical to implement, meets those criteria. It can be achieved reasonably satisfactorily with a library (I've already added the routines to arraylib) and it's likely that only a tiny number of users would ever make use of it. It would also, inevitably, slightly slow down every program using arrays because of the check for the slicing syntax.

However I've started to question that conclusion for a couple of reasons. Firstly array slicing was identified as one of the major features offered by Python that BBC BASIC doesn't have (albeit that Python's version is much more flexible) and it was clear that one of the benefits was in the clarity offered by having a built-in syntax. Even if a library can provide the functionality, it can't provide the elegant syntax.

Secondly, I was struck by the way DeepSeek came to the false conclusion that BBC BASIC does have array slicing, and used it in its suggested code for Matrix Inversion! How that hallucination arose I have no idea, perhaps it got muddled between BBC BASIC and a similar language, but it does suggest that the absence of that functionality puts BBC BASIC at a disadvantage.

So I'm seriously looking at the possibility of adding it, so long as it can be done easily and safely, and with minimal bloat. To make it as lightweight and fast as possible my current proposal is that there be just one, simple, straightforward syntax (no shortcut syntax for a whole row, for example):

Code: Select all

      array(start TO end) : REM For one-dimensional arrays
      array(row, start TO end) : REM For two-dimensional arrays
      array(row, 0 TO DIM(array(),1)) : REM entire row

In general it would work for multi-dimensional arrays but only the final dimension can be sliced, because the elements in the slice must be consecutive in memory and that's only true in those cases.

It would also, unavoidably, suffer from the same limitation as the library implementation that a slice cannot be used in a dot-product operation. However you would be able to use the other 'whole array' operations on slices (which would for example overcome the current limitation that such operations assume zero-based arrays and include element zero in the calculation):

Code: Select all

      PRINT SUM(array(start TO end))
      PRINT MOD(array(start TO end))
      PRINT MOD(array(1 TO DIM(array(),1) : REM One-based, index zero ignored

And of course you would be able to use array assignment and arithmetic, even to copy data from one region of an array to another:

Code: Select all

      DIM array(9)
      array() = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
      array(6 TO 8) = array(1 TO 3)
      FOR I% = 0 TO 9 : PRINT array(I%) : NEXT

which outputs:

Code: Select all

         1
         2
         3
         4
         5
         6
         2
         3
         4
        10

I'd welcome more views on this.

[Richard Russell]

So I'm seriously looking at the possibility of adding it, so long as it can be done easily and safely, and with minimal bloat.

Unsurprisingly, I'm struggling with the coding. Although it's 'only' translating working BBC BASIC code, it's some time since I've done that, and there is the added complication that I have to translate it both to x86 assembler (for BB4W and the Windows edition of BBCSDL) and to C (for the cross-platform editions of BBCSDL)!

What I'm increasingly finding is that if I don't constantly refresh what skills I have left, I rapidly lose them (or at least I forget them). BBC BASIC code is inherently easier to write than C or assembler, and I'm still regularly doing so to keep my hand in. However I'm not writing assembler code or C code often enough to retain the knowledge.

I'll get there in the end, no doubt. If anybody has any application for array slicing, which could form the basis of a test/demonstration program, I'd be very interested to see it.

[Richard Russell]

If anybody has any application for array slicing, which could form the basis of a test/demonstration program, I'd be very interested to see it.

I asked DeepSeek to suggest one, and after a lot of deliberation (far too much to post here) this was its conclusion: "A concise example demonstrating array slicing's usefulness is rotating an array. Slicing allows elegant and efficient rotation without loops".

So here's exactly that, coded using my proposed syntax. This specific example rotates a 10-element array three positions to the right, but the procedure is general purpose and will rotate any (one-dimensional, numeric) array by any amount:

Code: Select all

      DIM array(9)
      array() = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
      PROC_rotate_right(array(), 3)
      FOR I% = 0 TO 9 : PRINT array(I%); : NEXT
      PRINT
      END

      DEF PROC_rotate_right(arr(),K%) : IF K%=0 ENDPROC
      LOCAL N%,tmp() : DIM tmp(K%-1) : N% = DIM(arr(),1)
      tmp() = arr(N%-K%+1 TO N%)
      arr(K% TO N%) = arr(0 TO N%-K%)
      arr(0 TO K%-1) = tmp()
      ENDPROC

This is the output:

Code: Select all

         7         8         9         0         1         2         3         4
         5         6

It would be messy and a lot slower using a loop.

[hellomike]

You might want to better validate the second parameter (K%) as not larger than N%+1 and not negative.
Or you could just make a PROC_rotate() which rotates left when K% is negative?

Just my two cents.

[Richard Russell]

You might want to better validate the second parameter (K%) as not larger than N%+1 and not negative.

Such an additional check would be relatively expensive in execution time and completely unnecessary in a situation in which the calling code cannot pass such an out-of-range parameter (not an unlikely situation).

Generally, I do not believe in exhaustive parameter checking, so long as should an invalid parameter be passed the result will be the reporting of a trappable error (in this case 'Bad subscript') rather than a crash of some kind.

For example the slicing routines in arraylib.bbc do check the parameters quite carefully, because an out-of-range value could result in memory corruption with the potential for a catastrophic and untrappable crash. But that can't happen with the array-rotation example.

BBC BASIC is relatively fast, but to get the best from it one does have to be careful not to execute code that has no benefit, such as code to check for an out-of-range value when the rest of the program ensures that such a value can never be generated.

This is an important difference between a high-level language, which will often protect you from your own stupidity, and a low-level language, which may crash in an unrecoverable fashion.