Skip to main content

Writing the game of life in Futhark

Background

Some time ago I found a found a video of someone implementing the Game of life on APL (you should take a look at it, the rest of the post will make more sense afterwards). APL is famous for being both expressive and unreadable for the non initiated. For example this Game of life can be expressed as (code from dyalog.com):

life{                                  ⍝ John Conway's "Game of Life".
    1 .3 4=+/,¯1 0 1∘.¯1 0 1∘.⌽⊂  ⍝ Expression for next generation.
}

The video linked above is quite interesting as it explains what all that symbols mean.

Some time later I was fiddling with the Futhark programming language and found a blog post titled "Futhark as target language for an APL compiler". This made me realize that APL and Futhark operate over (mostly) the same base concepts, and that replicating the same process on Futhark will be a good way to get to learn the basic operations of the language.

As an side note that this Game of life is already implemented as a benchmark sample program for futhark, so if you're interested in a useful implementation you should probably consider that one ;)

What is Futhark?

Futhark website describes the language as a "High-performance purely functional data-parallel array programming on the GPU". You could think it's something like a Haskell (with no recursion) which compiles its programs to something that a GPU can run (or anything OpenCL-enabled).

The implementation

For this I'll follow the steps described for the APL implementation on this video, this will be the last reminder to take a look at it, it'll really help follow the rest of the post.

Also, it'd be much better if you could follow along in your own computer. You can find the instructions to install Futhark here.

References