Easy way for multidimensional array capability?

If you want to discuss about Oforth...

Easy way for multidimensional array capability?

Postby joekillian » 31 Aug 2015 17:09

Multidimensional arrays seem to be easily created by just a structure with one field pointing to a vector and the other containing the dimensions like 3,3,3 or 10,10 etc.

The one thing needed for an matrix of any dimension is an "accessor" or "combinator" work that just indexes into the vector by the "offsets" needed to pick the rows, columns, pages etc. from the vector.

Once you have these selector functions then any function can be mapped over the intermediate results.

At stackexchange whenever a question pops up like "why doesn't language x have multidimensional arrays" of "how do I create a data structure for a "chessboard" the answer is frequently "why not just create your own accessor functions or equivalent?". Making these accessor functions part of the language can't be that difficult.

There is listing below. The last one shows the pattern needed to select "columns" from a flat vector. Using this approach a multidimensional array is just a vector with optional record fields for information like dimension and type.

So an "array" language is really nothing more than a bit of extra work to create a few accessor functions to pull row and column data from a flat vector then map other functions over that data. The first innovation was just the idea of mapping over a vector but extending that to higher dimensions is not done. This seems really easy to me. The question is why isn't this done in every language? Writing the naked lopping code every time a multidimensional array needs to be worked on seems like a trillion dollar waste of time.

The code concept below works on simple vectors without needed extra dimension data.


Full "moving window" with no shards
f monad or dyad is applied to data in each (window)
a=.1 2 3 4 5 6 7 8 9 10
mwin 3 3;a;f (1 2 3) (4 5 6) (7 8 9)
mwin 3 1;a;f (1 2 3) (2 3 4) (3 4 5) .....(8 9 10)
mwin 3 5;a;f (1 2 3) (5 6 7)
mwin 1 1;a;f (1 2 3 4 5 6 7 8 9 10)
mwin 1 2;a;f (1) 2 (3) 4 (5) 6 (7) 8 (9) 10

assuming a 2 x 5 matrix in a vector 1 2 3 4 5 6 7 8 9 10 :
mwin 5 5;a;f ((1 2 3 4 5)(6 7 8 9 10)useful for applying functions along rows
mwin 1 6;1;a;f (1 6) (2 7)(3 8)(4 9) (5 10) useful for applying functions along columns
joekillian
 
Posts: 5
Joined: 17 Jul 2015 20:13

Re: Easy way for multidimensional array capability?

Postby Franck » 01 Sep 2015 18:18

Hello,

Yes, I agree with you about multidimensional array capability.
But I was thinking about adding this as an extention (a package), and not as part of the language.

The reason is about memory used at startup : I try to keep it as small as possible and not load features that are not required for a operationnal system.
For instance, next version (V0.9.22), Oforth will allocate 256 Ko at startup and other features will have to be imported as packages.

Btw, tell me if you are interested to write this package for multidimensional array in Oforth :)

Franck
Franck
 
Posts: 140
Joined: 29 Oct 2014 19:01

Re: Easy way for multidimensional array capability?

Postby joekillian » 01 Sep 2015 23:58

Franck wrote:Hello,

Yes, I agree with you about multidimensional array capability.
But I was thinking about adding this as an extention (a package), and not as part of the language.

The reason is about memory used at startup : I try to keep it as small as possible and not load features that are not required for a operationnal system.
For instance, next version (V0.9.22), Oforth will allocate 256 Ko at startup and other features will have to be imported as packages.

Btw, tell me if you are interested to write this package for multidimensional array in Oforth :)

Franck


Maybe one of these days......

My intent was to point out that APL, J, K, Q, Chapel etc etc.the "true" multidimensional languages are really nothing more than just one easy layer above the languages that choose to stay on the vector level with mapping constructs. And why is that anyway?? Anybody can roll their own just accessing a vector with a few accessor combinators to map functions on whatever chunks of the vector the accessor selects. It could the row, column or page equivalents of a 3 dimensional matrix. The frustration is after programming initially in APL then J is that this "power" over multidimensional flat or nested arrays is only unique because literally all other languages don't make those few accessor functions as "builtins" to the language. Like Factor for example. I maybe wrong but Factor has many combinators but not one for accessing the equivalent of matrix columns in a 1D vector.

Why do almost all languages "choose" to stay on the vector level and then tell everybody to roll their own high dimensional unique code or better yet some accessor functions? Excel rules the spreadsheet world simply because it maps relatively well over a 2D matrix. So its not like there is not a lot of 2D programming to be done.

The way I see it code like below would be the minimum needed to create a generic 2D and up... function mapping system. Optionally they could be wrapped in more code to duplicate what J does with its "tagged" arrays where the array is a structure with the usual type, and dimension information.

assuming a 2 x 5 matrix in a vector 1 2 3 4 5 6 7 8 9 10 :
mwin 5 5;a;f ((1 2 3 4 5)(6 7 8 9 10)useful for applying functions along rows
mwin 1 6;1;a;f (1 6) (2 7)(3 8)(4 9) (5 10) useful for applying functions along columns

I am just an occasional user of J that would really like the same capability but using Forth like words instead of alphabet soup in a semi functional environment with a lot of neat features - something like OForth maybe.
joekillian
 
Posts: 5
Joined: 17 Jul 2015 20:13

Re: Easy way for multidimensional array capability?

Postby Franck » 02 Sep 2015 18:28

Yes, it could be interesting to implement this kind of built-in accessors in Oforth.

Can you explain a little bit more about those accessors functions (parameters, return value, ...).

I think I understand the first part :
mwin n p : returns n elements and jump p elements each time.

But this does not match with your 4th example :

Code: Select all
mwin 1 1;a;f (1 2 3 4 5 6 7 8 9 10)


could it be (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) ? If not, can you explain ?

For the second part (columns), I need more explainations :
Code: Select all
mwin 1 6;1;a;f (1 6) (2 7) (3 8) (4 9) (5 10)


How does this work ? What is the effect of the 1 added ? Is it what is added each times to the first indexes ?
Can you give an example of syntax with a three dimensional array ?

I will try to design them for Oforth and add them to a future version (not next one, but just after, I think).

Franck
Franck
 
Posts: 140
Joined: 29 Oct 2014 19:01

Re: Easy way for multidimensional array capability?

Postby joekillian » 03 Sep 2015 00:34

Franck wrote:Yes, it could be interesting to implement this kind of built-in accessors in Oforth.

Can you explain a little bit more about those accessors functions (parameters, return value, ...).

I think I understand the first part :
mwin n p : returns n elements and jump p elements each time.

But this does not match with your 4th example :

Code: Select all
mwin 1 1;a;f (1 2 3 4 5 6 7 8 9 10)


could it be (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) ? If not, can you explain ?

For the second part (columns), I need more explainations :
Code: Select all
mwin 1 6;1;a;f (1 6) (2 7) (3 8) (4 9) (5 10)


How does this work ? What is the effect of the 1 added ? Is it what is added each times to the first indexes ?
Can you give an example of syntax with a three dimensional array ?

I will try to design them for Oforth and add them to a future version (not next one, but just after, I think).

Franck


You are correct for mwin 1 1;a;f (1 2 3 4 5 6 7 8 9 10) being (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) and not (1 2 3 4 5 6 7 8 9 10)
mwin 1 1;a;f 1 1 is length of window and shift amount. a is the vector and f is the function.

for example in the language J f could be "<" which is the enclose function that allows creating a linked list useful for creating an array of different data types or same types and different dimensions.
mwin 1 1;1 2 3 4 5 6 7 8 9 10;< would produce (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)



mwin 1 6;1;a;f (1 6) (2 7) (3 8) (4 9) (5 10)

a = 1 2 3 4 5 6 7 8 9 10

1 6 are the index positions to pick. ;1; is the index amount to shift over for the next 1 6 selection.

If the intention is that the vector a is a 2 x 5 array this "mwin 1 6;1;a;f " allows mapping f over the selections (1 6) (2 7) (3 8) (4 9) (5 10) which are the rows of that 2 x 5 matrix

Note that with a record structure might be (2 5) (1 2 3 4 5 6 7 8 9 10) which tags the vector as a 2x5 matrix. To create an array "type" creates a record with arbitrary data about the array. Creating that "tagged" array is useful but not required for using the accessor functions. However It would be an odd language that crated those accessor functions without creating a multidimensional array type which could be just a vector with the dimension data as part of the record or tuple.

The return value is the function f mapped over (1 6) (2 7) (3 8) (4 9) (5 10)

if f was + and + worked over vectors the result would be 7 9 11 13 15

If f were a reverse array function then the result would be 6 1 7 2 8 3 9 4 10 5


The 3D array

1 2
3 4

5 6
7 8

as a vector is a=1 2 3 4 5 6 7 8

mwin 2 2;a;+ results in 3 7 11 15 adding along rows

mwin 1 3;2;a;+ results in 4 6 12 14 adding along columns

mwin 1 5;1;1;a;+ results in 6 8 10 12 adding along pages



mwin 2 2;a;, results in 1 2 3 4 5 6 7 8 appending along rows

mwin 1 3;2;a;, results in 1 3 2 4 5 7 6 8 appending along columns

mwin 1 5;1;a;, results in 1 5 2 6 3 7 4 8 appending along pages

for larger arrays like


1 2 3
4 5 6
7 8 9

10 11 12
13 14 15
16 17 18

1 2 3 4 5 6 7 8 9 10 11 12 13....18

mwin 1 4 7;2;a;, results in 1 4 7 2 5 8 7 8 9......12 15 18 appending along columns

so obviously a function is needed to create the selection vector 1 4 7 on larger matrices. That should be easy.

It seems very straightforward to treat a vector as nothing more than an N dimensional matrix and using the right access/selector functions "paired" with vector mappable functions like + and , make
mapping functions over N dimensional matrices easy.
joekillian
 
Posts: 5
Joined: 17 Jul 2015 20:13

Re: Easy way for multidimensional array capability?

Postby joekillian » 03 Sep 2015 06:17

Oops:
Should be :
mwin 1 4 7;3;a;, results in 1 4 7 2 5 8 7 8 9......12 15 18 appending along columns

1 2 3
4 5 6
7 8 9

10 11 12
13 14 15
16 17 18

1 2 3 4 5 6 7 8 9 10 11 12 13....18

not mwin 1 4 7;2;a;, results in 1 4 7 2 5 8 7 8 9......12 15 18 appending along columns

Anyway, I realize language design takes years but one thing I do very well is browse many computer languages like an amateur armchair linguist and believe me easy to use multidimensional function mapping is useful but not very well supported. I think what happened was just the choice of individual Greek symbols to represent the array operations in APL and for the next 50 years 2D and larger arrays have been second class citizens. Most programmers just don't like the look of that kind of write only code which is all too common with APL and J.
joekillian
 
Posts: 5
Joined: 17 Jul 2015 20:13


Return to Discussions

Who is online

Users browsing this forum: No registered users and 1 guest