Futhark by Example

The Futhark Programming Language

High-performance purely functional data-parallel array programming

Overview<br>Examples<br>Docs<br>Publications<br>Gotta Go Fast!<br>Get Involved<br>Blog

Fork me on GitHub

Futhark by Example

The following is a hands-on introduction to Futhark through a<br>collection of commented programs, listed in roughly increasing order<br>of complexity. You can load the programs into the<br>interpreter<br>to experiment with them. For a conventional introduction to the<br>language, Parallel Programming in<br>Futhark may be a better choice.<br>For more examples, you can check our implemented<br>benchmarks. We also<br>maintain a list of projects using Futhark.

Some of the example programs use<br>directives<br>for plotting or rendering graphics.

Basic language features

Basic usage with the factorial function

Primitive values

Converting a value to a different type

Mathematical functions

Functions

Arrays

Minimum and maximum

Type ascriptions

Basic parallelism

Tuples and records

Size coercions

Ranges

Backtick operators

Scans and reductions

Parametric polymorphism

Polymorphic minimum and maximum

Gather and scatter

Exclusive scans

Exclusive prefix sum

Pipe operators

Complex ranges

Sum types and pattern matching

Loops

Flattening and unflattening arrays

In-place updates

Programming techniques

Benchmarking

Counting elements that satisfy<br>property

Index of smallest element (argmin)

Reducing the result of a filter

Scattering the result of a filter

Size parameters

Matrix multiplication

Pairwise L₁ distances

Outer product

Comparing arrays for equality

Searching

Option type

Computing histograms

Moving average

Means

Swapping two elements of an array

Integer logarithm

Radix sort

Radix sort by key

Merge sort

Removing duplicates

Abstract data types

Complex numbers

Testing for associativity

Reducing or scanning without a neutral<br>element

Holes

Kahan summation

Random numbers

Gaussian blur (with Python<br>integration)

Three-dimensional vectors

Faking nominal types

Triangular matrices

Binary search

AD with dual numbers

Variance

Matching parentheses

Evaluating polynomials

Line fitting

Decoding MNIST data files

Automatic differentiation

Forward-mode automatic differentiation

Reverse-mode automatic differentiation

Newton’s Method

Literate Futhark

Basic use of literate Futhark

Generating videos with literate Futhark

Reading and writing files in literate Futhark

Plotting

Literate Futhark allows direct use of<br>gnuplot. These examples show simple and<br>common cases.

Plotting a histogram

Examples from Dex

The following examples are ported from<br>Dex, a dependently typed<br>functional array language that uses a somewhat different approach to<br>describing loop processing. We've tried to keep the original naming<br>scheme and programming style.

Prelude

Mandelbrot set

Multi-step ray tracer

Monte Carlo estimates of pi

Brownian motion

Sierpinski triangle

External examples

OCaml-GPU wordcount<br>example<br>by calling Futhark.

Projects using Futhark

The majority of written Futhark code is probably still Futhark’s own<br>test and benchmark suites. However, there are some programs that have<br>been written in Futhark because it was a good tool for the job, and not<br>just to test the compiler. A possibly incomplete list:

Diving Beet is a falling sand<br>game, which is a kind of simple particle simulator toy. Its main purpose<br>is to produce pretty effects. There is a blog<br>post with details and a video.

Futball is a game about avoiding<br>getting hit by balls. The rendering engine is a ray tracer written in<br>Futhark.

Futcam is an application that applies<br>stacks of interactively configurable filters to a webcam stream. Futhark<br>is used to implement the filters.

Futracer is a fairly slow<br>brute-force ray tracer written in Futhark.

Futswirl is a fractal generator<br>based on iterated function<br>systems.

Neptune is an<br>implementation of the Poseidon hash<br>function tuned for<br>Filecoin, where the GPU<br>parts have been<br>implemented in Futhark.

Palathark is a<br>Futhark implementation of the lattice Boltzmann method.

Ray Tracing in One Weekend in<br>Futhark and<br>Ray Tracing: the Next Week in<br>Futhark are<br>implementations based on Peter Shirley's book series. These are by no<br>means real-time ray tracers, but support advanced effects and make use<br>of acceleration structures like BVH trees.

Pareas is a compiler implemented<br>in Futhark and C++.

Developed<br>at DIKU<br>(copyright, acknowledgements, hedgehogs)