4. Language Reference

This reference seeks to describe every construct in the Futhark language. It is not presented in a tutorial fashion, but rather intended for quick lookup and documentation of subtleties. For this reason, it is not written in a bottom-up manner, and some concepts may be used before they are fully defined. It is a good idea to have a basic grasp of Futhark (or some other functional programming language) before reading this reference. An ambiguous grammar is given for the full language. The text describes how ambiguities are resolved in practice (things like operator precedence).

4.1. Identifiers and Keywords

id        ::=  letter (letter | "_" | "'")* | "_" id
quals     ::=  (id ".")+
qualid    ::=  id | quals id
binop     ::=  symbol+
qualbinop ::=  binop | quals binop
fieldid   ::=  decimal | id
symbol    ::=  "+" | "-" | "*" | "/" | "%" | "=" | "!" | ">" | "<" | "|" | "&" | "^"

Many things in Futhark are named. When we are defining something, we give it an unqualified name (id). When referencing something inside a module, we use a qualified name (qualid). The fields of a record are named with fieldid`s. Note that a `fieldid can be decimal numbers.

4.2. Primitive Types and Values

literal ::=  intnumber | floatnumber | "true" | "false"

Boolean literals are written true and false. The primitive types in Futhark are the signed integer types i8, i16, i32, i64, the unsigned integer types u8, u16, u32, u64, the floating-point types f32, f64, as well as bool. An f32 is always a single-precision float and a f64 is a double-precision float.

int_type   ::=  "i8" | "i16" | "i32" | "i64" | "u8" | "u16" | "u32" | "u64"
float_type ::=  "f8" | "f16" | "f32" | "f64"

Numeric literals can be suffixed with their intended type. For example 42i8 is of type i8, and 1337e2f64 is of type f64. If no suffix is given, integer literals are of type i32, and decimal literals are of type f64. Hexadecimal literals are supported by prefixing with 0x, and binary literals by prefixing with 0b.

intnumber   ::=  (decimal | hexadecimal | binary) [int_type]
decimal     ::=  decdigit+
hexadecimal ::=  0 ("x" | "X") hexdigit+
binary      ::=  0 ("b" | "B") bindigit+
floatnumber   ::=  (pointfloat | exponentfloat) [float_type]
pointfloat    ::=  [intpart] fraction | intpart "."
exponentfloat ::=  (intpart | pointfloat) exponent
intpart       ::=  decdigit+
fraction      ::=  "." decdigit+
exponent      ::=  ("e" | "E") ["+" | "-"] decdigit+
decdigit ::=  "0"..."9"
hexdigit ::=  decdigit | "a"..."f" | "A"..."F"
bindigit ::=  "0" | "1"

Numeric values can be converted between different types by using the desired type name as a function. E.g., i32(1.0f32) would convert the floating-point number 1.0 to a 32-bit signed integer. Conversion from floating-point to integers is done by truncation.

These can also be converted to numbers (1 for true, 0 for false) by using the desired numeric type as a function.

4.2.1. Compound Types and Values

All primitive values can be combined in tuples and arrays. A tuple value or type is written as a sequence of comma-separated values or types enclosed in parentheses. For example, (0, 1) is a tuple value of type (i32,i32). The elements of a tuple need not have the same type – the value (false, 1, 2.0) is of type (bool, i32, f64). A tuple element can also be another tuple, as in ((1,2),(3,4)), which is of type ((i32,i32),(i32,i32)). A tuple cannot have just one element, but empty tuples are permitted, although they are not very useful-these are written () and are of type ().

type        ::=  qualid | array_type | tuple_type | record_type
array_type  ::=  "[" [dim] "]" type
tuple_type  ::=  "(" ")" | "(" type ("[" "," type "]")* ")"
record_type ::=  "{" "}" | "{" fieldid ":" type ("," fieldid ":" type)* "}"
dim         ::=  qualid | decimal

An array value is written as a nonempty sequence of comma-separated values enclosed in square brackets: [1,2,3]. An array type is written as [d]t, where t is the element type of the array, and d is an integer indicating the size. We typically elide d, in which case the size will be inferred. As an example, an array of three integers could be written as [1,2,3], and has type [3]i32. An empty array is written as empty(t), where t is the element type.

Multi-dimensional arrays are supported in Futhark, but they must be regular, meaning that all inner arrays must have the same shape. For example, [[1,2], [3,4], [5,6]] is a valid array of type [3][2]i32, but [[1,2], [3,4,5], [6,7]] is not, because there we cannot come up with integers m and n such that [m][n]i32 describes the array. The restriction to regular arrays is rooted in low-level concerns about efficient compilation. However, we can understand it in language terms by the inability to write a type with consistent dimension sizes for an irregular array value. In a Futhark program, all array values, including intermediate (unnamed) arrays, must be typeable.

Records are mappings from field names to values, with the field names known statically. A tuple behaves in all respects like a record with numeric field names, and vice versa. It is an error for a record type to name the same field twice.

String literals are supported, but only as syntactic sugar for arrays of i32 values. There is no char type in Futhark.

stringlit  ::=  '"' stringchar '"'
stringchar ::=  <any source character except "\" or newline or quotes>

4.3. Expressions

Expressions are the basic construct of any Futhark program. An expression has a statically determined type, and produces a value at runtime. Futhark is an eager/strict language (“call by value”).

The basic elements of expressions are called atoms, for example literals and variables, but also more complicated forms.

atom     ::=    literal
              | qualid
              | stringlit
              | "empty" "(" type ")"
              | "(" ")"
              | "(" exp ")"
              | "(" exp ("," exp)* ")"
              | "{" "}"
              | "{" field ("," field)* "}"
              | qualid "[" index ("," index)* "]"
              | "(" exp ")" "[" index ("," index)* "]"
              | "[" exp ("," exp)* "]"
              | "#" fieldid exp
exp      ::=    atom
              | exp qualbinop exp
              | exp exp
              | exp ":" type
              | "if" exp "then" exp "else" exp
              | "let" pat "=" exp "in" exp
              | "let" id "[" index ("," index)* "]" "=" exp "in" exp
              | "let" id pat+ [":" ty_exp] "=" exp "in" exp
              | "loop" "(" pat [("=" exp)] ")" "=" loopform "do" exp in exp
              | "iota" exp
              | "shape" exp
              | "replicate" exp exp
              | "reshape" exp exp
              | "rearrange" "(" nat_int+ ")" exp
              | "transpose" exp
              | "rotate" ["@" nat_int] exp exp
              | "split" ["@" nat_int] exp exp
              | "concat" ["@" nat_int] exp+
              | "zip" ["@" nat_int] exp+
              | "unzip" exp
              | "unsafe" exp
              | "copy" exp
              | exp "with" "[" index ("," index)* "]" "<-" exp
              | "map" fun exp+
              | "reduce" fun exp exp
              | "reduce_comm" fun exp exp
              | "reduce" fun exp exp
              | "scan" fun exp exp
              | "filter" fun exp
              | "partition" "(" fun+ ")" exp
              | "write" exp exp exp
              | "stream_map" fun exp
              | "stream_map_per" fun exp
              | "stream_red" fun exp exp
              | "stream_map_per" fun exp exp
              | "stream_seq" fun exp exp
field    ::=    fieldid "=" exp
              | exp
pat      ::=    id
              |  "_"
              | "(" ")"
              | "(" pat ")"
              | "(" pat ("," pat)+ ")"
              | "{" "}"
              | "{" fieldid "=" pat ["," fieldid "=" pat] "}"
              | pat ":" type
loopform ::=  "for" id "<" exp
              | "for" atom "<=" id "<" exp
              | "for" atom ">" id ">=" exp
              | "for" atom ">" id
              | "while" exp

Some of the built-in expression forms have parallel semantics, but it is not guaranteed that the the parallel constructs in Futhark are evaluated in parallel, especially if they are nested in complicated ways. Their purpose is to give the compiler as much freedom and information is possible, in order to enable it to maximise the efficiency of the generated code.

4.3.1. Resolving Ambiguities

The above grammar contains some ambiguities, which in the concrete implementation is resolved via a combination of lexer and grammar transformations. For ease of understanding, they are presented here in natural text.

  • A type ascription (exp : type) cannot appear as an array index, as it collides with the syntax for slicing.

  • In f [x], there is am ambiguity between indexing the array f at position x, or calling the function f with the singleton array x. We resolve this the following way:

    • If there is a space between f and the opening bracket, it is treated as a function application.
    • Otherwise, it is an array index operation.
  • The following table describes the precedence and associativity of infix operators. All operators in the same row have the same precedence. The rows are listed in increasing order of precedence. Note that not all operators listed here are used in expressions; nevertheless, they are still used for resolving ambiguities.

    Associativity Operators
    left ,
    left :
    left ||
    left &&
    left <= >= > < == !=
    left & ^ |
    left << >> >>>
    left + -
    left * / % // %%
    right ->

4.3.2. Semantics

4.3.2.1. literal

Evaluates to itself.

4.3.2.2. qualid

A variable name; evaluates to its value in the current environment.

4.3.2.3. stringlit

Evaluates to an array of type []i32 that contains the string characters as integers.

4.3.2.4. empty(t)

Create an empty array whose row type is t. For example, empty(i32) creates a value of type []i32. The row type can contain shape declarations, e.g., empty([2]i32). Any dimension without an annotation will be of size 0, as will the outermost dimension.

4.3.2.5. ()

Evaluates to an empty tuple.

4.3.2.6. ( e )

Evaluates to the result of e.

4.3.2.7. (e1, e2, ..., eN)

Evaluates to a tuple containing N values. Equivalent to (1=e1, 2=e2, ..., N=eN).

4.3.2.8. {f1, f2, ..., fN}

A record expression consists of a comma-separated sequence of field expressions. A record expression is evaluated by creating an empty record, then processing the field expressions from left to right. Each field expression adds fields to the record being constructed. A field expression can take one of two forms:

f = e: adds a field with the name f and the value resulting from evaluating e.

e: the expression e must evaluate to a record, whose fields are added to the record being constructed.

If a field expression attempts to add a field that already exists in the record being constructed, the new value for the field supercedes the old one.

4.3.2.9. a[i]

Return the element at the given position in the array. The index may be a comma-separated list of indexes instead of just a single index. If the number of indices given is less than the rank of the array, an array is returned.

The array a must be a variable name or a parenthesized expression. Futhermore, there may not be a space between a and the opening bracket. This disambiguates the array indexing a[i], from a [i], which is a function call with a literal array.

4.3.2.10. a[i:j:s]

Return a slice of the array a from index i to j, the latter inclusive and the latter exclusive, taking every s-th element. The s parameter may not be zero. If s is negative, it means to start at i and descend by steps of size s to j (not inclusive).

It is generally a bad idea for s to be non-constant. Slicing of multiple dimensions can be done by separating with commas, and may be intermixed freely with indexing.

If s is elided it defaults to 1. If i or j is elided, their value depends on the sign of s. If s is positive, i become 0 and j become the length of the array. If s is negative, i becomes the length of the array minus one, and j becomes minus one. This means that a[::-1] is the reverse of the array a.

4.3.2.11. [x, y, z]

Create an array containing the indicated elements. Each element must have the same type and shape. At least one element must be provided - empty arrays must be constructed with the empty construct. This restriction is due to limited type inference in the Futhark compiler, and will hopefully be fixed in the future.

4.3.2.12. #f e

Access field f of the expression e, which must be a record or tuple.

4.3.2.13. x binop y

Apply an operator to x and y. Operators are functions like any other, and can be user-defined. Futhark pre-defines certain “magical” overloaded operators that work on many different types. Overloaded functions cannot be defined by the user. Both operands must have the same type. The predefined operators and their semantics are:

**

Power operator, defined for all numeric types.

//, %%

Division and remainder on integers, with rounding towards zero.

*, /, %, +, -

The usual arithmetic operators, defined for all numeric types. Note that / and % rounds towards negative infinity when used on integers - this is different from in C.

^, &, |, >>, <<, >>>

Bitwise operators, respectively bitwise xor, and, or, arithmetic shift right and left, and logical shift right. Shift amounts must be non-negative and the operands must be integers. Note that, unlike in C, bitwise operators have higher priority than arithmetic operators. This means that x & y == z is understood as (x & y) == z, rather than x & (y == z) as it would in C. Note that the latter is a type error in Futhark anyhow.

==, !=

Compare any two values of builtin or compound type for equality.

<, <=. >, >=

Company any two values of numeric type for equality.

4.3.2.14. x && y

Short-circuiting logical conjunction; both operands must be of type bool.

4.3.2.15. x || y

Short-circuiting logical disjunction; both operands must be of type bool.

4.3.2.16. f x y z

Apply the function f to the arguments x, y and z. Any number of arguments can be passed.

4.3.2.17. e : t

Annotate that e is expected to be of type t, failing with a type error if it is not. If t is an array with shape declarations, the correctness of the shape declarations is checked at run-time.

Due to ambiguities, this syntactic form cannot appear as an array index expression unless it is first enclosed in parentheses.

4.3.2.18. ! x

Logical negation of x, which must be of type bool.

4.3.2.19. - x

Numerical negation of x, which must be of numeric type.

4.3.2.20. . x

Bitwise negation of x, which must be of integral type.

4.3.2.21. if c then a else b

If c evaluates to True, evaluate a, else evaluate b.

4.3.2.22. let pat = e in body

Evaluate e and bind the result to the pattern pat while evaluating body. The in keyword is optional if body is a let or loop expression.

4.3.2.23. let a[i] = v in body

Write v to a[i] and evaluate body. The given index need not be complete and can also be a slice, but in these cases, the value of v must be an array of the proper size. Syntactic sugar for let a = a with [i] <- v in a.

4.3.2.24. let f params... = e in body

Bind f to a function with the given parameters and definition (e) and evaluate body. The function will be treated as aliasing any free variables in e. The function is not in scope of itself, and hence cannot be recursive.

4.3.2.25. loop (pat = initial) = for i < bound do loopbody in body

The name i is bound here and initialised to zero.

  1. Bind pat to the initial values given in initial.
  2. While i < bound, evaluate loopbody, rebinding pat to be the value returned by the body, increasing i by one after each iteration.
  3. Evaluate body with pat bound to its final value.

The = initial can be left out, in which case initial values for the pattern are taken from equivalently named variables in the environment. I.e., loop (x) = ... is equivalent to loop (x = x) = ....

4.3.2.26. loop (pat = initial) = while cond do loopbody in body

  1. Bind pat to the initial values given in initial.
  2. While cond evaluates to true, evaluate loopbody, rebinding pat to be the value returned by the body.
  3. Evaluate body with pat bound to its final value.

4.3.2.27. iota n

An array of the integers from 0 to n-1. The n argument can be any integral type. The elements of the array will have the same type as n.

4.3.2.28. shape a

The shape of array a as an integer array. It is often more readable to use shape declaration names instead of shape.

4.3.2.29. replicate n x

An array consisting of n copies of a. The n argument can be of any integral type.

4.3.2.30. reshape (d_1, ..., d_n) a

Reshape the elements of a into an n-dimensional array of the specified shape. The number of elements in a must be equal to the product of the new dimensions.

4.3.2.31. rearrange (d_1, ..., d_n) a

Permute the dimensions in the array, returning a new array. The d_i must be static integers, and constitute a proper length-n permutation.

For example, if b==rearrange((2,0,1),a), then b[x,y,z] = a[y,z,x].

4.3.2.32. transpose a

Return the transpose of a, which must be a two-dimensional array.

4.3.2.33. rotate@d i a

Rotate dimension d of the array a left by i elements. Intuitively, you can think of it as subtracting i from every index (modulo the size of the array).

For example, if b=rotate(1, i, a), then b[x,y+1] = a[x,y].

4.3.2.34. split (i_1, ..., i_n) a

Partitions the given array a into n+1 disjoint arrays (a[0...i_1-1], a[i_1...i_2-1], ..., a[i_n...]), returned as a tuple. The split indices must be weakly ascending, ie i_1 <= i_2 <= ... <= i_n.

Example: split((1,1,3), [5,6,7,8]) == ([5],[],[6,7],[8])

4.3.2.35. split@i (i_1, ..., i_n) a

Splits an array across dimension i, with the outermost dimension being 0. The i must be a compile-time integer constant, i.e. i cannot be a variable.

4.3.2.36. concat a_1 ..., a_n

Concatenate the rows/elements of several arrays. The shape of the arrays must be identical in all but the first dimension. This is equivalent to concat@0 (see below).

4.3.2.37. concat@i a_1 ... a_n

Concatenate arrays across dimension i, with the outermost dimension being 0. The i must be a compile-time integer constant, i.e. i cannot be a variable.

4.3.2.38. zip x y z

Zips together the elements of the outer dimensions of arrays x, y, and z. Static or runtime check is performed to check that the sizes of the outermost dimension of the arrays are the same. If this property is not true, program execution stops with an error. Any number of arrays may be passed to unzip. If n arrays are given, the result will be a single-dimensional array of n-tuples (where the the tuple components may themselves be arrays).

4.3.2.39. zip@i x y z

Like zip, but operates within i+1 dimensions. Thus, zip@0 is equivalent to unadorned zip. This form is useful when zipping multidimensional arrays along the innermost dimensions.

4.3.2.40. unzip a

If the type of a is [(t_1, ..., t_n)], the result is a tuple of n arrays, i.e., ([t_1], ..., [t_n]), and otherwise a type error.

4.3.2.41. unsafe e

Elide safety checks (such as bounds checking) for operations lexically with e. This is useful if the compiler is otherwise unable to avoid bounds checks (e.g. when using indirect indexes), but you really do not want them here.

4.3.2.42. copy a

Return a deep copy of the argument. Semantically, this is just the identity function, but it has special semantics related to uniqueness types as described in Uniqueness Types.

4.3.2.43. a with [i] <- e

Return a, but with the element at position i changed to contain the result of evaluating e. Consumes a.

4.3.2.44. map f a_1 ... a_n

Apply f to every element of a_1 ... a_n and return the resulting array. Differs from map f (zip a_1 ... a_n) in that f is called with n arguments, where in the latter case it is called with a single n-tuple argument. In other languages, this form of map is often called zipWith.

4.3.2.45. reduce f x a

Left-reduction with f across the elements of a, with x as the neutral element for f. The function f must be associative. If it is not, the return value is unspecified.

4.3.2.46. reduce_comm f x a

Like reduce, but with the added guarantee that the function f is commutative. This lets the compiler generate more efficient code. If f is not commutative, the return value is unspecified. You do not need to explicitly use reduce_comm with built-in operators like + - the compiler already knows that these are commutative.

4.3.2.47. scan f x a

Inclusive prefix scan. Has the same caveats with respect to associativity as reduce.

4.3.2.48. filter f a

Remove all those elements of a that do not satisfy the predicate f.

4.3.2.49. partition (f_1, ..., f_n) a

Divide the array a into disjoint partitions based on the given predicates. Each element of a is called with the predicates f_1 to f_n in sequence, and as soon as one as one of them returns True, the element is added to the corresponding partition. If none of the functions return True, the element is added to a catch-all partition that is returned last. Always returns a tuple with n+1 components. The partitioning is stable, meaning that elements of the partitions retain their original relative positions.

4.3.2.50. write is vs as

The write expression calculates the equivalent of this imperative code:

for index in 0..shape(is)[0]-1:
  i = is[index]
  v = vs[index]
  as[i] = v

The is and vs arrays must have the same outer size. write acts in-place and consumes the as array, returning a new array that has the same type and elements as as, except for the indices in is. If is contains duplicates (i.e. several writes are performed to the same location), the result is unspecified. It is not guaranteed that one of the duplicate writes will complete atomically - they may be interleaved.

4.4. Declarations

dec ::=    fun_bind | val_bind | ty_bind | mod_bind | mod_ty_bind
         | "open" mod_exp+
         | default_dec
         | "import" stringlit

4.4.1. Declaring Functions and Values

fun_bind ::=    ("let" | "entry") id pat+ [":" ty_exp] "=" exp
              | ("let" | "entry") pat binop pat [":" ty_exp] "=" exp
val_bind ::=  "let" id [":" ty_exp] "=" exp

Functions and values must be defined before they are used. A function declaration must specify the name, parameters, return type, and body of the function:

let name params...: rettype = body

Type inference is not supported, and functions are fully monomorphic. A parameter is written as (name: type). Functions may not be recursive. Optionally, the programmer may put shape declarations in the return type and parameter types. These can be used to express invariants about the shapes of arrays that are accepted or produced by the function, e.g:

let f (a: [n]i32) (b: [n]i32): [n]i32 =
  map (+) a b

In general, shape declarations in parameters are fresh names, whilst shape declarations in return types must refer to a name of type i32 in scope. A shape declaration can also be an integer constant (with no suffix). The dimension names bound in a parameter shape declaration can be used as ordinary variables within the scope of the parameter. If a function is called with arguments that do not fulfill the shape constraints, the program will fail with a runtime error.

4.4.2. User-Defined Operators

Infix operators are defined much like functions:

let (p1: t1) op (p2: t2): rt = ...

For example:

let (a:i32,b:i32) +^ (c:i32,d:i32) = (a+c, b+d)

A valid operator name is a non-empty sequence of characters chosen from the string "+-*/%=!><&^". The fixity of an operator is determined by its first characters, which must correspond to a built-in operator. Thus, +^ binds like +, whilst *^ binds like *. The longest such prefix is used to determine fixity, so >>= binds like >>, not like >.

It is not permitted to define operators with the names && or || (although these as prefixes are accepted). This is because a user-defined version of these operators would not be short-circuiting. User-defined operators behave exactly like functions, except for syntactically.

A built-in operator can be shadowed (i.e. a new + can be defined). This will result in the built-in polymorphic operator becoming inaccessible, except through the Intrinsics module.

4.4.2.1. Entry Points

Apart from declaring a function with the keyword fun, it can also be declared with entry. When the Futhark program is compiled any function declared with entry will be exposed as an entry point. If the Futhark program has been compiled as a library, these are the functions that will be exposed. If compiled as an executable, you can use the --entry-point command line option of the generated executable to select the entry point you wish to run.

Any function named main will always be considered an entry point, whether it is declared with entry or not.

4.4.2.2. Value Declarations

A named value/constant can be declared as follows:

let name: type = definition

The definition can be an arbitrary expression, including function calls and other values, although they must be in scope before the value is defined. The type annotation can be elided if the value is defined before it is used.

Values can be used in shape declarations, except in the return value of entry points.

4.4.3. Type Abbreviations

ty_bind ::=  "type" id "=" type

Futhark supports simple type abbreviations to improve code readability. Examples:

type person_id                = i32
type int_pair                 = (i32, i32)
type position, velocity, vec3 = (f32, f32, f32)

type pilot      = person_id
type passengers = []person_id
type mass       = f32

type airplane = (pilot, passengers, position, velocity, mass)

The abbreviations are merely a syntactic convenience. With respect to type checking the position and velocity types are identical. It is currently not possible to put shape declarations in type abbreviations. When using uniqueness attributes with type abbreviations, inner uniqueness attributes are overrided by outer ones:

type uniqueInts = *[]i32
type nonuniqueIntLists = []intlist
type uniqueIntLists = *nonuniqueIntLists

-- Error: using non-unique value for a unique return value.
let uniqueIntLists (nonuniqueIntLists p) = p

4.5. Module System

mod_bind    ::=  "module" id mod_param+ "=" [":" mod_type_exp] "=" mod_exp
mod_param   ::=  "(" id ":" mod_type_exp ")"
mod_ty_bind ::=  "module" "type" id "=" mod_type_exp

Futhark supports an ML-style higher-order module system. Modules can contain types, functions, and other modules. Module types are used to classify the contents of modules, and parametric modules are used to abstract over modules (essentially module-level functions). In Standard ML, modules, module types and parametric modules are called structs, signatures, and functors, respectively.

Named modules are declared as:

module name = module expression

A named module type is defined as:

module type name = module type expression

Where a module expression can be the name of another module, an application of a parametric module, or a sequence of declarations enclosed in curly braces:

module Vec3 = {
  type t = ( f32 , f32 , f32 )
  let add(a: t) (b: t): t =
    let (a1, a2, a3) = a in
    let (b1, b2, b3) = b in
    (a1 + b1, a2 + b2 , a3 + b3)
}

module AlsoVec3 = Vec3

Functions and types within modules can be accessed using dot notation:

type vector = Vec3.t
let double(v: vector): vector = Vec3.add v v

We can also use open Vec3 to bring the names defined by Vec3 into the current scope. Multiple modules can be opened simultaneously by separating their names with spaces. In case several modules define the same names, the ones mentioned last take precedence. The first argument to open may be a full module expression.

Named module types are defined as:

module type ModuleTypeName = module type expression

A module type expression can be the name of another module type, or a sequence of specifications, or specs, enclosed in curly braces. A spec can be a value spec, indicating the presence of a function or value, an abstract type spec, or a type abbreviation spec. For example:

module type Addable = {
  type t                 -- abstract type spec
  type two_ts = (t,t)    -- type abbreviation spec
  val add: t -> t -> t   -- value spec
}

This module type specifies the presence of an abstract type t, as well as a function operating on values of type t. We can use module type ascription to restrict a module to what is exposed by some module type:

module AbstractVec = Vec3 : Addable

The definition of AbstractVec.t is now hidden. In fact, with this module type, we can neither construct values of type AbstractVec.T or convert them to anything else, making this a rather useless use of abstraction. As a derived form, we can write module M: S = e to mean module M = e : S.

Parametric modules allow us to write definitions that abstract over modules. For example:

module Times(M: Addable) = {
  let times (x: M.t) (k: int): M.t =
    loop (x' = x) = for i < k do
      T.add x' x
    in x'
}

We can instantiate Times with any module that fulfills the module type Addable and get back a module that defines a function times:

module Vec3Times = Times(Vec3)

Now Vec3Times.times is a function of type Vec3.t -> int -> Vec3.t.

4.5.1. Module Expressions

mod_exp ::=    qualid
             | mod_exp ":" mod_type_exp
             | "\" "(" id ":" mod_type_exp ")" [":" mod_type_exp] "=" mod_exp
             | mod_exp mod_exp
             | "(" mod_exp ")"
             | "{" dec* "}"
             | "import" stringlit

4.5.2. Module Type Expressions

mod_type_exp ::=    qualid
                  | "{" spec* "}"
                  | mod_type_exp "with" qualid "=" ty_exp
                  | "(" mod_type_exp ")"
                  | "(" id ":" mod_type_exp ")" "->" mod_type_exp
                  | mod_type_exp "->" mod_type_exp
spec      ::=    "val" id ":" spec_type
               | "val" binop ":" spec_type
               | "type" id "=" type
               | "type id
               | "module" id ":" mod_type_exp
               | "include" mod_type_exp
spec_type ::=  type | type "->" spec_type

4.6. Referring to Other Files

You can refer to external files in a Futhark file like this:

import "module"

The above will include all top-level definitions from module.fut is and make them available in the current Futhark program. The .fut extension is implied.

You can also include files from subdirectories:

include "path/to/a/file"

The above will include the file path/to/a/file.fut.

Qualified imports are also possible, where a module is created for the file:

module M = import "module"

4.7. Literal Defaults

default_dec ::=    "default" (int_type)
                 | "default" (float_type)
                 | "default" (int_type, float_type)

By default, Futhark interprets integer literals as i32 values, and decimal literals (integer literals containing a decimal point) as f64 values. These defaults can be changed using the Haskell-inspired default keyword.

To change the i32 default to e.g. i64, type the following at the top of your file:

default(i64)

To change the f64 default to f32, type the following at the top of your file:

default(f32)

To change both, type:

default(i64,f32)