# Futhark by Example

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

Some of the example programs use directives 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
- Type ascriptions
- Basic parallelism
- Tuples and records
- Size coercions
- Ranges
- Scans and reductions
- Parametric polymorphism
- Gather and scatter
- Pipe operators
- Complex ranges
- Sum types and pattern matching
- Loops

## Programming techniques

- Benchmarking
- Counting elements that satisfy property
- 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
- Computing histograms
- Moving average
- Means
- 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 element
- Holes
- Kahan summation
- Random numbers
- Gaussian blur (with Python integration)
- Three-dimensional vectors
- Faking nominal types
- Triangular matrices
- Binary search
- AD with dual numbers
- Variance
- Matching parentheses

## Automatic differentiation

## Literate Futhark

- Basic use of literate Futhark
- Generating videos with literate Futhark
- Reading and writing files in literate Futhark

## Examples from Dex

The following examples are ported from Dex, a dependently typed functional array language that uses a somewhat different approach to describing loop processing. We've tried to keep the original naming 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 example by calling Futhark.

## Projects using Futhark

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

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

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

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

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

Futswirl is a fractal generator based on iterated function systems.

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

Palathark is a Futhark implementation of the lattice Boltzmann method.

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

Pareas is a compiler implemented in Futhark and C++.