Futhark Programming Language

Expressions are the fundamental building blocks of Futhark programs. Every expression has a statically determined type and produces a value at runtime. Futhark uses an eager/strict evaluation strategy (call-by-value).

Basic elements of expressions are called atoms, which include literals, variables, strings, characters, and parenthesized expressions. Expressions can be composed using operators, constructors, type ascriptions, and control flow constructs like if, let, loop, and match.

Futhark uses a system of size-dependent types to statically check that array sizes are compatible.

• Size Parameters: Represented as [n], these quantify array sizes. They are not passed explicitly during function calls; instead, their values are implicitly deduced from the arguments.
• Anonymous Sizes: Represented as [], these allow the type checker to invent fresh size parameters to ensure all arrays have a size.
• Existential Sizes: On the right-hand side of a function arrow (return types), a size might be unknown until the function is applied, denoted by ?[k].[k]t.
• Size-dependent Types: You can use size parameters in return types. For example, replicate 10 0 results in type [10]i32.
• Constraints: Sizes must be expressions of type i64 that do not consume free variables.

def f [n] (a: [n]i32) (b: [n]i32): [n]i32 =
  map2 (+) a b

Futhark provides powerful abstraction capabilities through its module system:

• Module: A mapping from names to definitions of types, values, or nested modules.
• Parametric Module: A function from modules to modules, providing the highest level of abstraction.
• Module Type: A description of a module's interface, used for hiding contents via Module Ascription (m : mt) or requiring implementations in parametric modules.
• Defunctorisation: A compiler transformation that compiles away modules (similar to defunctionalisation) to make using parametric modules free at run-time.

The benchmarking tool uses a two-phase technique to ensure statistical robustness:

1. Warmup: A single run is performed and discarded.
2. Initial Phase: Performs a set number of runs (default 10, configurable with -r) or runs for at least half a second, whichever is longer. If measurements are statistically robust (based on standard deviation and autocorrelation), the process finishes.
3. Convergence Phase: If the initial phase is not robust, the tool enters a convergence phase, continuing runs until sufficient statistical quality is reached.

Customizing Control:

• To disable the convergence phase and use a fixed number of runs, use --no-convergence-phase combined with -r <count>.
• To limit the time spent in the convergence phase, use --convergence-max-seconds=NUM (defaults to 300 seconds).

The futhark literate command compiles a Futhark program and generates a Markdown file (e.g., foo.md for foo.fut) containing a prettyprinted version of the code. This is useful for demonstrating programming techniques.

Key behaviors:

• Top-level comments starting with -- (dash-dash-space) are converted to ordinary text.
• Top-level definitions are enclosed in Markdown code blocks.
• Directives (lines starting with -- >) are executed and replaced with their output.
• Generated assets (images, etc.) are placed in a directory named <program_name>-img/.

Warning: Do not run untrusted programs as directives can execute arbitrary shell commands or file operations.

futhark literate [options...] program

C code often simulates multidimensional arrays using a single-dimensional array and manual index calculation, such as a[i * M + j] = foo; (where M is the inner dimension).

In Futhark, you can represent this directly as a multidimensional array. For example, a C allocation of malloc(N * M * sizeof(int)) corresponds to a Futhark type of [N][M]i32. The update expression a[i * M + j] = foo translates to:

let a[i,j] = foo in
...

Initialization: Since you cannot allocate and then loop to initialize in Futhark, use replicate, iota, or map to create arrays with initial values. In the worst case, use replicate followed by a do-loop with in-place updates.

If you do not want to compile your code, you can use the interpreter to run Futhark code directly. Note that the interpreter is significantly slower than compiled code.

• futhark run: Runs a Futhark file.
• futhark repl: Opens an interactive prompt for experimenting with Futhark expressions.