Codigo para llevar [blog]

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

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)

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

auxiliary stack

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

auxiliary stack

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

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

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

dimension stack

auxiliary stack

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