The nature of something predefined. For functions, these can either be monomorphic or overloaded. An overloaded builtin is a list valid types it can be instantiated with, to the parameter and result type, with Nothing representing the overloaded parameter type.

A map of all built-ins.

Find the VName corresponding to a builtin. Crashes if that name cannot be found.

The largest tag used by an intrinsic - this can be used to determine whether a VName refers to an intrinsic or a user-defined name.

Is this the name of an intrinsic?

Names of primitive types to types. This is only valid if no shadowing is going on, but useful for tools.

Create a name with no qualifiers from a name.

Add another qualifier (at the head) to a qualified name.

The type of a basic value.

Given an operator name, return the operator that determines its syntactical properties.

The modules imported by a Futhark program.

The modules imported by a single declaration.

The set of module types used in any exported (non-local) declaration.

Extract a leading ((name, namespace, file), remainder) from a documentation comment string. These are formatted as `name`@namespace[@file]. Let us hope that this pattern does not occur anywhere else.

Given a list of strings representing entries in the stack trace and the index of the frame to highlight, produce a final newline-terminated string for showing to the user. This string should also be preceded by a newline. The most recent stack frame must come first in the list.

Find instances of typed holes in the program.

The name of the default program entry point (main).

The name, if any.

A special expression representing no known size, but encoding an equivalence class (represented by the integer) that can be used to detect unknown-but-equal sizes. This is important so that we do not throw away size equalities just because the names become unknown to us (e.g. see #2326). The type checker should _never_ produce anySizes - they are a (hopefully temporary) thing introduced by defunctorisation and monomorphisation. They represent a flaw in our implementation. When they occur in a return type, they can be replaced with freshly created existential sizes. When they occur in parameter types, they can be replaced with size parameters.

If this is any size, retrieve the key for the equivalence class.

Override the location of an Apply expression.

This is useful because mkApply sets the location to be the span of the function and all arguments, but during many frontend transformations we insert additional arguments for which we do not care about the original source location. Our goal is to maintain a correspondence between the original source code and the generated code.

The type of an Futhark term. The aliasing will refer to itself, if the term is a non-tuple-typed variable.

The type scheme of a value binding, comprising the type parameters and the actual type.

The names that are brought into scope by this value binding (not including its own parameter names, but including any existential sizes).

The type of a function with the given parameters and return type.

Strip semantically irrelevant stuff from the top level of expression. This is used to provide a slightly fuzzy notion of expression equality.

Ideally we'd implement unification on a simpler representation that simply didn't allow us.

All non-trivial subexpressions (as by stripExp) of some expression, not including the expression itself.

If these two expressions are structurally similar at top level as sizes, produce their subexpressions (which are not necessarily similar, but you can check for that!). This is the machinery underlying expresssion unification. We assume that the expressions have the same type.

Are these the same expression as per recursively invoking similarExps?

The set of identifiers bound in a pattern.

The set of names bound in a pattern.

Each name bound in a pattern alongside its type.

The type of values bound by the pattern.

The type matched by the pattern, including shape declarations if present.

When viewed as a function parameter, does this pattern correspond to a named parameter of some type?

patternOrderZero pat is True if all of the types in the given pattern have order 0.

Return the freshness of a type. A composite type is fresh if any of its components are.

fresh t is True if the type of the argument is fresh.

diet t returns a description of how a function parameter of type t consumes its argument.

Return the dimensionality of a type. For non-arrays, this is zero. For a one-dimensional array it is one, for a two-dimensional it is two, and so forth.

Return the shape of a type - for non-arrays, this is mempty.

orderZero t is True if the argument type has order 0, i.e., it is not a function type, does not contain a function type as a subcomponent, and may not be instantiated with a function type.

Extract the parameter types and return type from a type. If the type is not an arrow type, the list of parameter types is empty.

foldFunType ts ret creates a function type (Arrow) that takes ts as parameters and returns ret.

The qualified type names mentioned in a type.

The type names mentioned in a type.

If this type corresponds to the builtin "acc" type, return the type of the underlying array.

peelArray n t returns the type resulting from peeling the first n array dimensions from t. Returns Nothing if t has less than n dimensions.

stripArray n t removes the n outermost layers of the array. Essentially, it is the type of indexing an array of type t with n indexes.

arrayOf o s t constructs an array type. The convenience compared to using the Array constructor directly is that t can itself be an array. If t is an n-dimensional array, and s is a list of length n, the resulting type is of an n+m dimensions.

Like arrayOf, but you can pass in the annotation of the resulting array.

Convert any type to one that has rank information, no alias information, and no embedded names.

Remove the annotation from a type.

Convert to ResType

Uses Observe.

Preserves relation between Diet and Freshness.

Preserves relation between Diet and Freshness.

Convert to ResRetType

Set the annotation of a type - that is, its Diet or Freshness, or nothing at all. If the type is a record or sum type, the annotation of its components will be modified.

Change the shape of a type to be just the rank.

Perform a traversal (possibly including replacement) on sizes that are parameters in a function type, but also including the type immediately passed to the function. Also passes along a set of the parameter names inside the type that have come in scope at the occurrence of the dimension.

Where does this dimension occur?

Create a record type corresponding to a tuple with the given element types.

Does this type corespond to a tuple? If so, return the elements of that tuple.

Does this record map correspond to a tuple?

Construct a record map corresponding to a tuple.

Increasing field names for a tuple (starts at 0).

Sort fields by their name; taking care to sort numeric fields by their numeric value. This ensures that tuples and tuple-like records match.

Sort the constructors of a sum type in some well-defined (but not otherwise significant) manner.

Is this a TypeParamType?

Is this a TypeParamDim?

Match the dimensions of otherwise assumed-equal types. The combining function is also passed the names bound within the type (from named parameters or return types).

A type with no aliasing information but shape annotations.

An unchecked type expression.

An identifier with no type annotations.

An index with no type annotations.

A slice with no type annotations.

An expression with no type annotations.

A module expression with no type annotations.

A module type expression with no type annotations.

A type parameter with no type annotations.

A pattern with no type annotations.

A function declaration with no type annotations.

A type binding with no type annotations.

A module type binding with no type annotations.

A module binding with no type annotations.

A declaration with no type annotations.

A spec with no type annotations.

A Futhark program with no type annotations.

A case (of a match expression) with no type annotations.

An identifier with type- and aliasing information.

An index with type information.

A slice with type information.

An application expression with type information.

An expression with type information.

A pattern with type information.

A type-checked module expression.

A type-checked module parameter.

A type-checked module type expression.

A type-checked module binding.

A type-checked module type binding.

An constant declaration with type information.

A type-checked declaration.

A type-checked specification.

An Futhark program with type information.

A type binding with type information.

A known type arg with shape annotations.

A known scalar type with no shape annotations.

A type-checked type parameter.

A type-checked case (of a match expression).