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 themap
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 

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 

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 :)