struggling with life

[melsman]

I'm trying to get the game of life (written in APL) running with Futhark. Here is the APL code:

⍝ Conway's Game of Life in APL without the use of nested arrays
⍝ Function computing the next generation of a board of life
life ← {
  rowsum ← {
    (¯1⌽⍵) + ⍵ + 1⌽⍵
  }
  neighbor ← {
    (rowsum ¯1⊖⍵) + (rowsum ⍵) + rowsum 1⊖⍵       
  }
  n ← neighbor ⍵
  (n=3) ∨ (n=4) ∧ ⍵
}
nlife ← {
  (life ⍣ ⍺) ⍵
}
glider ← 3 3⍴1 1 1 1 0 0 0 1 0
board ← ⍉ ¯10 ↑ ⍉ ¯10 ↑ glider
square ← { x ← (5 ⊖ ⍵), 3 ⌽ ⍉ ⍵ ⋄ x ⍪ 4 ⊖ x }
board ← square board
board ← square board
a ← 20000 nlife board
b ← life a
s ← ∧/∧/a=b      ⍝ Is it stable?   
⎕ ← s+0

The generated Futhark program is quite big - uggh - it is listed below. It will compile ok, but it wont run:

bash-3.2$ ./fut_life 
Abort trap: 6
bash-3.2$ 

Any ideas?

The generated main function:

fun {int} main() =
  let t_v1 = reshape((3, 3),reshape1_bool((3 * (3 * 1)), reshape(((size(0,
                                    [True,
                                     True,
                                     True,
                                     True,
                                     False,
                                     False,
                                     False,
                                     True,
                                     False]) * 1)),[True,
                                            True,
                                            True,
                                            True,
                                            False,
                                            False,
                                            False,
                                            True,
                                            False]))) in
  let t_v2 = rearrange((1, 0),reshape((if ((-10) <= 0)
                   then (-(-10))
                   else (-10), size(1, rearrange((1,
                                  0),reshape((if ((-10) <= 0)
                                          then (-(-10))
                                          else (-10),
                                          size(1,
                                           t_v1)),take1_bool(((-10) * (size(1,
                                                            t_v1) * 1)),
                                                     reshape(((size(0,
                                                            t_v1) * (size(1,
                                                                  t_v1) * 1))),t_v1)))))),take1_bool(((-10) * (size(1,
                                                                                            rearrange((1,
                                                                                                   0),reshape((if ((-10) <= 0)
                                                                                                       then (-(-10))
                                                                                                       else (-10),
                                                                                                       size(1,
                                                                                                        t_v1)),take1_bool(((-10) * (size(1,
                                                                                                                         t_v1) * 1)),
                                                                                                                  reshape(((size(0,
                                                                                                                         t_v1) * (size(1,
                                                                                                                                   t_v1) * 1))),t_v1))))) * 1)),
                                                                                     reshape(((size(0,
                                                                                            rearrange((1,
                                                                                                   0),reshape((if ((-10) <= 0)
                                                                                                       then (-(-10))
                                                                                                       else (-10),
                                                                                                       size(1,
                                                                                                        t_v1)),take1_bool(((-10) * (size(1,
                                                                                                                         t_v1) * 1)),
                                                                                                                  reshape(((size(0,
                                                                                                                         t_v1) * (size(1,
                                                                                                                                   t_v1) * 1))),t_v1))))) * (size(1,
                                                                                                                                                  rearrange((1,
                                                                                                                                                     0),reshape((if ((-10) <= 0)
                                                                                                                                                             then (-(-10))
                                                                                                                                                             else (-10),
                                                                                                                                                             size(1,
                                                                                                                                                              t_v1)),take1_bool(((-10) * (size(1,
                                                                                                                                                                               t_v1) * 1)),
                                                                                                                                                                        reshape(((size(0,
                                                                                                                                                                               t_v1) * (size(1,
                                                                                                                                                                                     t_v1) * 1))),t_v1))))) * 1))),rearrange((1,
                                                                                                                                                                                                          0),reshape((if ((-10) <= 0)
                                                                                                                                                                                                                  then (-(-10))
                                                                                                                                                                                                                  else (-10),
                                                                                                                                                                                                                  size(1,
                                                                                                                                                                                                                   t_v1)),take1_bool(((-10) * (size(1,
                                                                                                                                                                                                                                    t_v1) * 1)),
                                                                                                                                                                                                                             reshape(((size(0,
                                                                                                                                                                                                                                    t_v1) * (size(1,
                                                                                                                                                                                                                                          t_v1) * 1))),t_v1)))))))) in
  let t_v4 = map(fn [bool] ([bool] x, [bool] y) =>
         concat(x, y),zip(let a = t_v2 in
                  map(fn [bool] (int x) =>
                  a[((x + 5) % size(0, t_v2))],iota(size(0,
                                     t_v2))),
                  rearrange((1, 0),let a = rearrange((1,
                                  0),rearrange((1,
                                        0),t_v2)) in
                    map(fn [bool] (int x) =>
                        a[((x + 3) % size(0,
                                  rearrange((1,
                                     0),rearrange((1,
                                               0),t_v2))))],iota(size(0,
                                                          rearrange((1,
                                                             0),rearrange((1,
                                                                       0),t_v2)))))))) in
  let t_v5 = rearrange((1, 0),map(fn [bool] ([bool] x, [bool] y) =>
                  concat(x, y),zip(rearrange((1, 0),t_v4),
                           rearrange((1,
                              0),let a = t_v4 in
                             map(fn [bool] (int x) =>
                                 a[((x + 4) % size(0,
                                           t_v4))],iota(size(0,
                                                 t_v4))))))) in
  let t_v7 = map(fn [bool] ([bool] x, [bool] y) =>
         concat(x, y),zip(let a = t_v5 in
                  map(fn [bool] (int x) =>
                  a[((x + 5) % size(0, t_v5))],iota(size(0,
                                     t_v5))),
                  rearrange((1, 0),let a = rearrange((1,
                                  0),rearrange((1,
                                        0),t_v5)) in
                    map(fn [bool] (int x) =>
                        a[((x + 3) % size(0,
                                  rearrange((1,
                                     0),rearrange((1,
                                               0),t_v5))))],iota(size(0,
                                                          rearrange((1,
                                                             0),rearrange((1,
                                                                       0),t_v5)))))))) in
  let t_v8 = rearrange((1, 0),map(fn [bool] ([bool] x, [bool] y) =>
                  concat(x, y),zip(rearrange((1, 0),t_v7),
                           rearrange((1,
                              0),let a = t_v7 in
                             map(fn [bool] (int x) =>
                                 a[((x + 4) % size(0,
                                           t_v7))],iota(size(0,
                                                 t_v7))))))) in
  let t_v88 = loop (t_v49 = t_v8) = for i < 20000 do
  let t_v53 = let a = t_v49 in
  map(fn [bool] (int x) =>
  a[((x + 1) % size(0, t_v49))],iota(size(0, t_v49))) in
  let t_v71 = let a = t_v49 in
  map(fn [bool] (int x) =>
  a[((x + (-1)) % size(0, t_v49))],iota(size(0, t_v49))) in
  let t_v81 = map(fn [int] ([int] x, [int] y) =>
          map(+,zip(x, y)),zip(map(fn [int] ([int] x, [int] y) =>
                       map(+,zip(x,
                         y)),zip(map(fn [int] ([bool] x) =>
                                 map(boolToInt,x),rearrange((1,
                                             0),let a = rearrange((1,
                                                           0),t_v71) in
                                            map(fn [bool] (int x) =>
                                                a[((x + (-1)) % size(0,
                                                         rearrange((1,
                                                                0),t_v71)))],iota(size(0,
                                                                           rearrange((1,
                                                                                  0),t_v71)))))),
                             map(fn [int] ([int] x,
                                       [int] y) =>
                                 map(+,zip(x,
                                       y)),zip(map(fn [int] ([bool] x) =>
                                           map(boolToInt,x),t_v71),
                                           map(fn [int] ([bool] x) =>
                                           map(boolToInt,x),rearrange((1,
                                                           0),let a = rearrange((1,
                                                                     0),t_v71) in
                                                          map(fn [bool] (int x) =>
                                                          a[((x + 1) % size(0,
                                                                    rearrange((1,
                                                                           0),t_v71)))],iota(size(0,
                                                                                      rearrange((1,
                                                                                         0),t_v71)))))))))),
                   map(fn [int] ([int] x, [int] y) =>
                       map(+,zip(x,
                         y)),zip(map(fn [int] ([int] x,
                                       [int] y) =>
                                 map(+,zip(x,
                                       y)),zip(map(fn [int] ([bool] x) =>
                                           map(boolToInt,x),rearrange((1,
                                                           0),let a = rearrange((1,
                                                                     0),t_v49) in
                                                          map(fn [bool] (int x) =>
                                                          a[((x + (-1)) % size(0,
                                                                       rearrange((1,
                                                                          0),t_v49)))],iota(size(0,
                                                                                     rearrange((1,
                                                                                            0),t_v49)))))),
                                           map(fn [int] ([int] x,
                                                 [int] y) =>
                                           map(+,zip(x,
                                                 y)),zip(map(fn [int] ([bool] x) =>
                                                     map(boolToInt,x),t_v49),
                                                     map(fn [int] ([bool] x) =>
                                                     map(boolToInt,x),rearrange((1,
                                                                     0),let a = rearrange((1,
                                                                               0),t_v49) in
                                                                    map(fn [bool] (int x) =>
                                                                    a[((x + 1) % size(0,
                                                                              rearrange((1,
                                                                                     0),t_v49)))],iota(size(0,
                                                                                                rearrange((1,
                                                                                                       0),t_v49)))))))))),
                             map(fn [int] ([int] x,
                                       [int] y) =>
                                 map(+,zip(x,
                                       y)),zip(map(fn [int] ([bool] x) =>
                                           map(boolToInt,x),rearrange((1,
                                                           0),let a = rearrange((1,
                                                                     0),t_v53) in
                                                          map(fn [bool] (int x) =>
                                                          a[((x + (-1)) % size(0,
                                                                       rearrange((1,
                                                                          0),t_v53)))],iota(size(0,
                                                                                     rearrange((1,
                                                                                            0),t_v53)))))),
                                           map(fn [int] ([int] x,
                                                 [int] y) =>
                                           map(+,zip(x,
                                                 y)),zip(map(fn [int] ([bool] x) =>
                                                     map(boolToInt,x),t_v53),
                                                     map(fn [int] ([bool] x) =>
                                                     map(boolToInt,x),rearrange((1,
                                                                     0),let a = rearrange((1,
                                                                               0),t_v53) in
                                                                    map(fn [bool] (int x) =>
                                                                    a[((x + 1) % size(0,
                                                                              rearrange((1,
                                                                                     0),t_v53)))],iota(size(0,
                                                                                                rearrange((1,
                                                                                                       0),t_v53)))))))))))))) in
  map(fn [bool] ([bool] x, [bool] y) =>
  map(||,zip(x, y)),zip(map(fn [bool] ([int] x) =>
                map(fn bool (int t_v85) =>
                (t_v85 == 3),x),t_v81),
            map(fn [bool] ([bool] x, [bool] y) =>
                map(&&,zip(x, y)),zip(map(fn [bool] ([int] x) =>
                              map(fn bool (int t_v82) =>
                              (t_v82 == 4),x),t_v81),
                          t_v49)))) in t_v49 in
  let t_v91 = let a = t_v88 in
  map(fn [bool] (int x) =>
  a[((x + 1) % size(0, t_v88))],iota(size(0, t_v88))) in
  let t_v109 = let a = t_v88 in
  map(fn [bool] (int x) =>
  a[((x + (-1)) % size(0, t_v88))],iota(size(0, t_v88))) in
  let t_v119 = map(fn [int] ([int] x, [int] y) =>
           map(+,zip(x, y)),zip(map(fn [int] ([int] x, [int] y) =>
                    map(+,zip(x,
                          y)),zip(map(fn [int] ([bool] x) =>
                                  map(boolToInt,x),rearrange((1,
                                              0),let a = rearrange((1,
                                                        0),t_v109) in
                                             map(fn [bool] (int x) =>
                                                 a[((x + (-1)) % size(0,
                                                          rearrange((1,
                                                                 0),t_v109)))],iota(size(0,
                                                                             rearrange((1,
                                                                                0),t_v109)))))),
                              map(fn [int] ([int] x,
                                    [int] y) =>
                                  map(+,zip(x,
                                    y)),zip(map(fn [int] ([bool] x) =>
                                            map(boolToInt,x),t_v109),
                                        map(fn [int] ([bool] x) =>
                                            map(boolToInt,x),rearrange((1,
                                                        0),let a = rearrange((1,
                                                                      0),t_v109) in
                                                           map(fn [bool] (int x) =>
                                                           a[((x + 1) % size(0,
                                                                     rearrange((1,
                                                                        0),t_v109)))],iota(size(0,
                                                                                    rearrange((1,
                                                                                           0),t_v109)))))))))),
                    map(fn [int] ([int] x, [int] y) =>
                    map(+,zip(x,
                          y)),zip(map(fn [int] ([int] x,
                                    [int] y) =>
                                  map(+,zip(x,
                                    y)),zip(map(fn [int] ([bool] x) =>
                                            map(boolToInt,x),rearrange((1,
                                                        0),let a = rearrange((1,
                                                                      0),t_v88) in
                                                           map(fn [bool] (int x) =>
                                                           a[((x + (-1)) % size(0,
                                                                    rearrange((1,
                                                                           0),t_v88)))],iota(size(0,
                                                                                      rearrange((1,
                                                                                             0),t_v88)))))),
                                        map(fn [int] ([int] x,
                                                  [int] y) =>
                                            map(+,zip(x,
                                                  y)),zip(map(fn [int] ([bool] x) =>
                                                      map(boolToInt,x),t_v88),
                                                      map(fn [int] ([bool] x) =>
                                                      map(boolToInt,x),rearrange((1,
                                                                      0),let a = rearrange((1,
                                                                                0),t_v88) in
                                                                     map(fn [bool] (int x) =>
                                                                     a[((x + 1) % size(0,
                                                                               rearrange((1,
                                                                                      0),t_v88)))],iota(size(0,
                                                                                                 rearrange((1,
                                                                                                    0),t_v88)))))))))),
                              map(fn [int] ([int] x,
                                    [int] y) =>
                                  map(+,zip(x,
                                    y)),zip(map(fn [int] ([bool] x) =>
                                            map(boolToInt,x),rearrange((1,
                                                        0),let a = rearrange((1,
                                                                      0),t_v91) in
                                                           map(fn [bool] (int x) =>
                                                           a[((x + (-1)) % size(0,
                                                                    rearrange((1,
                                                                           0),t_v91)))],iota(size(0,
                                                                                      rearrange((1,
                                                                                             0),t_v91)))))),
                                        map(fn [int] ([int] x,
                                                  [int] y) =>
                                            map(+,zip(x,
                                                  y)),zip(map(fn [int] ([bool] x) =>
                                                      map(boolToInt,x),t_v91),
                                                      map(fn [int] ([bool] x) =>
                                                      map(boolToInt,x),rearrange((1,
                                                                      0),let a = rearrange((1,
                                                                                0),t_v91) in
                                                                     map(fn [bool] (int x) =>
                                                                     a[((x + 1) % size(0,
                                                                               rearrange((1,
                                                                                      0),t_v91)))],iota(size(0,
                                                                                                 rearrange((1,
                                                                                                    0),t_v91)))))))))))))) in
  let t_v126 = map(fn [bool] ([bool] x, [bool] y) =>
           map(||,zip(x, y)),zip(map(fn [bool] ([int] x) =>
                     map(fn bool (int t_v123) =>
                         (t_v123 == 3),x),t_v119),
                     map(fn [bool] ([bool] x, [bool] y) =>
                     map(&&,zip(x,
                            y)),zip(map(fn [bool] ([int] x) =>
                                map(fn bool (int t_v120) =>
                                    (t_v120 == 4),x),t_v119),
                                t_v88)))) in
  let t_v133 = reduce(&&,True,map(fn bool ([bool] x) =>
                  reduce(&&,True,x),map(fn [bool] ([bool] x,
                                   [bool] y) =>
                            map(eqb,zip(x,
                                y)),zip(t_v88,
                                    t_v126)))) in
  {boolToInt(t_v133)}

[athas]

What pretty code. I will take a look at it this evening.

[athas]

I get a better error message:

Assertion False at life.fut:237:410-237:410 failed.

It is interesting that this means the Futhark compiler can determine at run-time that the assertion fails. It comes from a reshape.

[athas]

This is the reshape I think:

reshape((if ((-10) <= 0) then (-(-10)) else (-10), size(1,t_v1)),take1_bool(((-10) * (size(1, t_v1) * 1)), reshape(((size(0, t_v1) * (size(1, t_v1) * 1))),t_v1)))

[athas]

Seems to be an error in the definition of takeBody when left-padding. Fixing it now.

[athas]

Is life.apl supposed to simply produce 0?

[athas]

Tail seems to give the same result, so closing this one.