# Matrix operators as stack languages

On the last post we explored how some program written on APL can be translated to Futhark.

Both Futhark and APL can be considered array programming languages.

A difference between them is that APL can express inner or outer operations when handling a multidimensional array, meaning that having an array `3×3×5×7` we can sum the values when only the first dimension is different, converting it into a `3×5×7` matrix (see the operation demonstrated here). By the way, the sizes come from the example on last post and don't have any special meaning.

For the same operation to be performed on Futhark we have to do move that dimension to the last "place", and then apply a reduce. Let's call the matrix `mat`, name each dimension, and see how it plays out.

#### Initial state:

`mat`

Dimension Name Size
1 Outer column 3
2 Outer row 3
3 Inner row 5
4 Inner column 7

#### Swap the outer row into the 4th dimension

We then apply `transpose()` operations. When we `transpose()` an array, it swaps the two topmost dimensions.

`transpose(mat)`

Dimension Name Size
1 (from 2) Outer row 3
2 (from 1) Outer colum 3
3 Inner row 5
4 Inner column 7

Ok, that makes sense, but how can we move it further? The idea is that some operations over this matrix are analogous to operations on stack langauges if we consider that operations done over the dimensions of the matrix. For example, `transpose(mat)` is like applying SWAP over the dimensions on a language like Forth.

Cool, but we have to go "deeper" on the stack, what can we do?

The second operation is map, (the usual one from functional languages). This operation does a POP on our dimensions and PUSHES it into an auxiliary stack. Let's see how that might work.

`map (\next -> *follow here* transpose(mat))`

Dimension Name Size
1 Outer column 3
2 Inner row 5
3 Inner column 7

`auxiliary stack`

Dimension Name Size
1 Outer row 3

In a moment we'll se how we can POP from the auxiliary back into the dimensions one. After that the next operations will be applied over the `map` iterator until we close the `map`. For now we can apply the transposition and see how that would work

`map (\next -> *CURSOR* transpose(next) ) (transpose(mat))`

Dimension Name Size
1 (from 3) Inner row 5
2 (from 1) Outer column 3
3 (from 4) Inner column 7

`auxiliary stack`

Dimension Name Size
1 Outer row 3

I didn't identify a clear operation to move from the auxiliary stack onto the dimensions one, but "finishing" the operation does that for every element on the auxiliary stack.

`map (\next -> transpose(next)) (transpose(mat))`

Dimension Name Size
1 (from 2) Outer row 3
2 (from 3) Inner row 5
3 (from 1) Outer column 3
4 Inner column 7
``````-- Prepare the example, you can ignore this
[0]> let are_accepted (arr: []i32, accepted: []i32): []bool = map(\item -> any(\ok -> item == ok)(accepted)) arr
[1]> let bool_to_num (v: bool): i32 = match v case false -> 0 case true -> 1
[2]> let r = unflatten(3)(3)(map bool_to_num (are_accepted (iota(9), [1, 2, 3, 4, 7])))
[3]> let extend1 [n]'a (x: i32, arr: [n]a, item: a): []a = arr ++ (replicate(x - n)(item))
[4]> let extend2 'a (y: i32, x: i32, arr: [][]a, item: a): [][]a = extend1 (y, map(\row -> extend1 (x, row, item))(arr), replicate(x)(item))
[5]> let rotate2 'a (r: i32) (xs: [][]a) = map (\row -> rotate(r)(row))(xs)
[6]> let R = rotate(-1)(rotate2(-2)(extend2 (5, 7, r, 0)))
[7]> let mat = map(\yrot -> (map (\xrot -> rotate(yrot)(rotate2(xrot)(R)))) ([1, 0, -1]))([1, 0, -1])

-- Say that mat is our 3×3×5×7 matrix
[8]> let dim (x: [][][][]i32): []i32 = [length(x), length(x[0]), length((x[0])[0]), length(((x[0])[0])[0])]
[9]> dim(mat)
[3i32, 3i32, 5i32, 7i32]
[10]> dim( map (\next -> transpose(next)) (transpose(mat)) )
[3i32, 5i32, 3i32, 7i32]
``````

So up until that point it looks like it works. The goal is twofold, moving the Outer column into the innermost dimension

Dimension Name Size
1 (from 2) Outer row 3
2 (from 3) Inner row 5
3 (from 4) Inner column 7
4 (from 1) Outer column 3

and at the same time expose it so we can operate over it. The goal state we want is thus:

`dimension stack`

Dimension Name Size
1 Outer column 3

`auxiliary stack`

Dimension Name Size
1 Outer row 3
2 Inner row 5
3 Inner column 7

For this we would do

``````SWAP
MAP SWAP -- At this point the matrix is the 3x5x3x7 we know
MAP SWAP -- One dimension to the aux. stack and swap again and it's 3x5x7x3

-- Here we would operate over the innermost DIMENSION
``````

If we translate this back to Futhark, line by line

``````transpose(mat) -- SWAP

map( \next -> *CURSOR* transpose(next) ) (transpose(mat)) -- SWAP MAP SWAP

map( \next -> map( \next -> *CURSOR* (transpose(next)) ) (transpose(next)) ) (transpose(mat)) -- SWAP MAP SWAP MAP SWAP
``````

The results look alright:

``````[11]> dim(  map( \next -> map( \next -> (transpose(next)) ) (transpose(next)) ) (transpose(mat))  )
[3i32, 5i32, 7i32, 3i32]
``````

We can even add the operation we want inside the first element we have on the dimension stack, we just have to add a `map` and that's it

``````[12]> let dim3 (x: [][][]i32): []i32 = [length(x), length(x[0]), length((x[0])[0])]
[13]> let add_elements (arr: []i32): i32 = reduce (\x -> \y -> x + y) 0 arr -- i32.sum would be OK too
-- SWAP MAP SWAP MAP SWAP ← the one before || add_elements ← operation
[14]> dim3( map( \next -> map( \next ->
map add_elements  -- New operation
(transpose(next)) ) (transpose(next)) ) (transpose(mat)))
[3i32, 5i32, 7i32]
``````

This shows the same result as the same operation on the previous post

``````-- This code
[15]> let X = map( \next -> map( \next -> map add_elements (transpose(next)) ) (transpose(next)) ) (transpose(mat))
-- Previous code
[16]> let pushed = map(\xrd -> map(\row -> transpose(row))(xrd)) (map(\xrd -> transpose xrd) (transpose(mat)))
[17]> let Y = map(\xrd -> map(\row -> map(i32.sum) row )  xrd) pushed
[18]> X == Y
true
``````

In summary, the rules are:

• To do a swap add a `transpose(mat)` and continue on the left of it.
• To move from dimension stack to the auxiliary one, open a `map(` (don't close it) and continue on inside the map.
• New operations can be performed inside the `map` as long as they are done over the `map` lambda parameter.

### The code

The following script can be used to convert stack code to Futhark. The valid operations are `SWAP`, `MAP`, and anything preceded with `:` will be called as a Futhark function on all the array (no parameters allowed). Line comments start with `--`:

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33``` ``````import re def compose(commands, target): text = [] cursor = 0 # for command in commands: if command.upper() == 'SWAP': target = f"transpose({target})" elif command.upper() == 'MAP': text.insert(cursor, r'map (\next -> ') text.insert(cursor + 1, f') ({target})') cursor += 1 target = "next" else: if not command.startswith(':'): raise Exception(f"Found “{command}”, expected “SWAP”, “MAP” or something starting with ‘:’") function = command[1:] target = f'map ({function}) ({target})' text.insert(cursor, target) return ' '.join(text) + ' -- ' + ' '.join(commands) # This is a proof of concept, and it's not tested *at all* def convert(stack_code, target_matrix): lines = stack_code.split('\n') no_comments = [] for line in lines: if '--' in line: line = line[:line.index("--")] no_comments.append(line.strip()) # commands = re.split(r'\s+', " ".join(no_comments).strip()) return compose(commands, target_matrix) ``````

And some examples:

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24``` ``````def test(): print(convert(""" SWAP MAP SWAP -- At this point the matrix is the 3x5x3x7 we know MAP SWAP -- One dimension to the aux. stack and swap again and it's 3x5x7x3 :add_elements """, "mat")) # The example above # Result: map (\next -> map (\next -> map (add_elements) (transpose(next)) ) (transpose(next)) ) (transpose(mat)) print(convert(""" -- Single operation :i32.sum """, "[[1, 2], [3, 4]]")) # Result: map (i32.sum) ([[1, 2], [3, 4]]) # If applied: [3, 7] # print(convert(""" -- Starting with a MAP MAP :i32.sum """, "[[[1, 2], [3, 4]]" ",[[5, 6], [7, 8]]]")) # Result: map (\next -> map (i32.sum) (next) ) ([[[1, 2], [3, 4]],[[5, 6], [7, 8]]]) # If applied: [[3, 7], [11, 15]] test() ``````

The result of this execution is

``````>>> test()
map (\next ->  map (\next ->  map (add_elements) (transpose(next)) ) (transpose(next)) ) (transpose(mat)) -- SWAP MAP SWAP MAP SWAP :add_elements
map (i32.sum) ([[1, 2], [3, 4]]) -- :i32.sum
map (\next ->  map (i32.sum) (next) ) ([[[1, 2], [3, 4]],[[5, 6], [7, 8]]]) -- MAP :i32.sum
``````

Anyway, that's it, there's points to polish and probably doesn't have much application but I found it interesting anyway :)