futhark-0.25.27: An optimising compiler for a functional, array-oriented language.

Safe Haskell | Safe-Inferred
Language | GHC2021

Language.Futhark.Prop

Contents

- Various
- Queries on expressions
- Queries on patterns and params
- Queries on types
- Operations on types
- Un-typechecked ASTs
- Type-checked ASTs

Description

This module provides various simple ways to query and manipulate fundamental Futhark terms, such as types and values. The intent is to keep Futhark.Language.Syntax simple, and put whatever embellishments we need here.

Synopsis

- data Intrinsic
  - = IntrinsicMonoFun [PrimType] PrimType
  - | IntrinsicOverloadedFun [PrimType] [Maybe PrimType] (Maybe PrimType)
  - | IntrinsicPolyFun [TypeParamBase VName] [ParamType] (RetTypeBase Size Uniqueness)
  - | IntrinsicType Liftedness [TypeParamBase VName] StructType
  - | IntrinsicEquality
- intrinsics :: Map VName Intrinsic
- intrinsicVar :: Name -> VName
- isBuiltin :: FilePath -> Bool
- isBuiltinLoc :: Located a => a -> Bool
- maxIntrinsicTag :: Int
- namesToPrimTypes :: Map Name PrimType
- qualName :: v -> QualName v
- qualify :: v -> QualName v -> QualName v
- primValueType :: PrimValue -> PrimType
- leadingOperator :: Name -> BinOp
- progImports :: ProgBase f vn -> [(String, Loc)]
- decImports :: DecBase f vn -> [(String, Loc)]
- progModuleTypes :: ProgBase Info VName -> Set VName
- identifierReference :: String -> Maybe ((String, String, Maybe FilePath), String)
- prettyStacktrace :: Int -> [Text] -> Text
- progHoles :: ProgBase Info VName -> [(Loc, StructType)]
- defaultEntryPoint :: Name
- paramName :: PName -> Maybe VName
- anySize :: Size
- typeOf :: ExpBase Info VName -> StructType
- valBindTypeScheme :: ValBindBase Info VName -> ([TypeParamBase VName], StructType)
- valBindBound :: ValBindBase Info VName -> [VName]
- funType :: [Pat ParamType] -> ResRetType -> StructType
- stripExp :: Exp -> Maybe Exp
- subExps :: Exp -> [Exp]
- similarExps :: Exp -> Exp -> Maybe [(Exp, Exp)]
- sameExp :: Exp -> Exp -> Bool
- patIdents :: PatBase f vn t -> [IdentBase f vn t]
- patNames :: Pat t -> [VName]
- patternMap :: Pat t -> [(VName, t)]
- patternType :: Pat (TypeBase d u) -> TypeBase d u
- patternStructType :: Pat (TypeBase Size u) -> StructType
- patternParam :: Pat ParamType -> (PName, Diet, StructType)
- patternOrderZero :: Pat (TypeBase d u) -> Bool
- uniqueness :: TypeBase shape Uniqueness -> Uniqueness
- unique :: TypeBase shape Uniqueness -> Bool
- diet :: TypeBase shape Diet -> Diet
- arrayRank :: TypeBase d u -> Int
- arrayShape :: TypeBase dim as -> Shape dim
- orderZero :: TypeBase dim as -> Bool
- unfoldFunType :: TypeBase dim as -> ([TypeBase dim Diet], TypeBase dim NoUniqueness)
- foldFunType :: [ParamType] -> ResRetType -> StructType
- typeVars :: TypeBase dim as -> Set VName
- isAccType :: TypeBase d u -> Maybe (TypeBase d NoUniqueness)
- peelArray :: Int -> TypeBase dim u -> Maybe (TypeBase dim u)
- stripArray :: Int -> TypeBase dim as -> TypeBase dim as
- arrayOf :: Shape dim -> TypeBase dim NoUniqueness -> TypeBase dim NoUniqueness
- arrayOfWithAliases :: u -> Shape dim -> TypeBase dim u' -> TypeBase dim u
- toStructural :: TypeBase dim as -> TypeBase () ()
- toStruct :: TypeBase dim u -> TypeBase dim NoUniqueness
- toRes :: Uniqueness -> TypeBase Size u -> ResType
- toParam :: Diet -> TypeBase Size u -> ParamType
- resToParam :: ResType -> ParamType
- paramToRes :: ParamType -> ResType
- toResRet :: Uniqueness -> RetTypeBase Size u -> ResRetType
- setUniqueness :: TypeBase dim u1 -> u2 -> TypeBase dim u2
- noSizes :: TypeBase Size as -> TypeBase () as
- traverseDims :: forall f fdim tdim als. Applicative f => (Set VName -> DimPos -> fdim -> f tdim) -> TypeBase fdim als -> f (TypeBase tdim als)
- data DimPos
  - = PosImmediate
  - | PosParam
  - | PosReturn
- tupleRecord :: [TypeBase dim as] -> ScalarTypeBase dim as
- isTupleRecord :: TypeBase dim as -> Maybe [TypeBase dim as]
- areTupleFields :: Map Name a -> Maybe [a]
- tupleFields :: [a] -> Map Name a
- tupleFieldNames :: [Name]
- sortFields :: Map Name a -> [(Name, a)]
- sortConstrs :: Map Name a -> [(Name, a)]
- isTypeParam :: TypeParamBase vn -> Bool
- isSizeParam :: TypeParamBase vn -> Bool
- matchDims :: forall as m d1 d2. (Monoid as, Monad m) => ([VName] -> d1 -> d2 -> m d1) -> TypeBase d1 as -> TypeBase d2 as -> m (TypeBase d1 as)
- type UncheckedType = TypeBase (Shape Name) ()
- type UncheckedTypeExp = TypeExp UncheckedExp Name
- type UncheckedIdent = IdentBase NoInfo Name
- type UncheckedDimIndex = DimIndexBase NoInfo Name
- type UncheckedSlice = SliceBase NoInfo Name
- type UncheckedExp = ExpBase NoInfo Name
- type UncheckedModExp = ModExpBase NoInfo Name
- type UncheckedModTypeExp = ModTypeExpBase NoInfo Name
- type UncheckedTypeParam = TypeParamBase Name
- type UncheckedPat = PatBase NoInfo Name
- type UncheckedValBind = ValBindBase NoInfo Name
- type UncheckedTypeBind = TypeBindBase NoInfo Name
- type UncheckedModTypeBind = ModTypeBindBase NoInfo Name
- type UncheckedModBind = ModBindBase NoInfo Name
- type UncheckedDec = DecBase NoInfo Name
- type UncheckedSpec = SpecBase NoInfo Name
- type UncheckedProg = ProgBase NoInfo Name
- type UncheckedCase = CaseBase NoInfo Name
- type Ident = IdentBase Info VName
- type DimIndex = DimIndexBase Info VName
- type Slice = SliceBase Info VName
- type AppExp = AppExpBase Info VName
- type Exp = ExpBase Info VName
- type Pat = PatBase Info VName
- type ModExp = ModExpBase Info VName
- type ModParam = ModParamBase Info VName
- type ModTypeExp = ModTypeExpBase Info VName
- type ModBind = ModBindBase Info VName
- type ModTypeBind = ModTypeBindBase Info VName
- type ValBind = ValBindBase Info VName
- type Dec = DecBase Info VName
- type Spec = SpecBase Info VName
- type Prog = ProgBase Info VName
- type TypeBind = TypeBindBase Info VName
- type StructTypeArg = TypeArg Size
- type ScalarType = ScalarTypeBase ()
- type TypeParam = TypeParamBase VName
- type Case = CaseBase Info VName

# Various

data Intrinsic Source #

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.

Constructors

IntrinsicMonoFun [PrimType] PrimType |
IntrinsicOverloadedFun [PrimType] [Maybe PrimType] (Maybe PrimType) |
IntrinsicPolyFun [TypeParamBase VName] [ParamType] (RetTypeBase Size Uniqueness) |
IntrinsicType Liftedness [TypeParamBase VName] StructType |
IntrinsicEquality |

intrinsics :: Map VName Intrinsic Source #

A map of all built-ins.

intrinsicVar :: Name -> VName Source #

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

isBuiltin :: FilePath -> Bool Source #

Is this include part of the built-in prelude?

isBuiltinLoc :: Located a => a -> Bool Source #

Is the position of this thing builtin as per `isBuiltin`? Things without location are considered not built-in.

maxIntrinsicTag :: Int Source #

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.

namesToPrimTypes :: Map Name PrimType Source #

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

qualName :: v -> QualName v Source #

Create a name with no qualifiers from a name.

qualify :: v -> QualName v -> QualName v Source #

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

primValueType :: PrimValue -> PrimType Source #

The type of a basic value.

leadingOperator :: Name -> BinOp Source #

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

progImports :: ProgBase f vn -> [(String, Loc)] Source #

The modules imported by a Futhark program.

decImports :: DecBase f vn -> [(String, Loc)] Source #

The modules imported by a single declaration.

progModuleTypes :: ProgBase Info VName -> Set VName Source #

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

identifierReference :: String -> Maybe ((String, String, Maybe FilePath), String) Source #

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.

prettyStacktrace :: Int -> [Text] -> Text Source #

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.

progHoles :: ProgBase Info VName -> [(Loc, StructType)] Source #

Find instances of typed holes in the program.

defaultEntryPoint :: Name Source #

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

paramName :: PName -> Maybe VName Source #

The name, if any.

anySize :: Size Source #

A special expression representing no known size. When present in a type, each instance represents a distinct size. The type checker should _never_ produce these - 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.

# Queries on expressions

typeOf :: ExpBase Info VName -> StructType Source #

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

valBindTypeScheme :: ValBindBase Info VName -> ([TypeParamBase VName], StructType) Source #

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

valBindBound :: ValBindBase Info VName -> [VName] Source #

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

funType :: [Pat ParamType] -> ResRetType -> StructType Source #

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

stripExp :: Exp -> Maybe Exp Source #

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.

subExps :: Exp -> [Exp] Source #

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

similarExps :: Exp -> Exp -> Maybe [(Exp, Exp)] Source #

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.

sameExp :: Exp -> Exp -> Bool Source #

Are these the same expression as per recursively invoking `similarExps`?

# Queries on patterns and params

patIdents :: PatBase f vn t -> [IdentBase f vn t] Source #

The set of identifiers bound in a pattern.

patNames :: Pat t -> [VName] Source #

The set of names bound in a pattern.

patternMap :: Pat t -> [(VName, t)] Source #

Each name bound in a pattern alongside its type.

patternType :: Pat (TypeBase d u) -> TypeBase d u Source #

The type of values bound by the pattern.

patternStructType :: Pat (TypeBase Size u) -> StructType Source #

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

patternParam :: Pat ParamType -> (PName, Diet, StructType) Source #

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

patternOrderZero :: Pat (TypeBase d u) -> Bool Source #

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

# Queries on types

uniqueness :: TypeBase shape Uniqueness -> Uniqueness Source #

Return the uniqueness of a type.

unique :: TypeBase shape Uniqueness -> Bool Source #

`unique t` is `True` if the type of the argument is unique.

diet :: TypeBase shape Diet -> Diet Source #

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

arrayRank :: TypeBase d u -> Int Source #

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.

arrayShape :: TypeBase dim as -> Shape dim Source #

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

orderZero :: TypeBase dim as -> Bool Source #

`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.

unfoldFunType :: TypeBase dim as -> ([TypeBase dim Diet], TypeBase dim NoUniqueness) Source #

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 :: [ParamType] -> ResRetType -> StructType Source #

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

typeVars :: TypeBase dim as -> Set VName Source #

The type names mentioned in a type.

isAccType :: TypeBase d u -> Maybe (TypeBase d NoUniqueness) Source #

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

# Operations on types

peelArray :: Int -> TypeBase dim u -> Maybe (TypeBase dim u) Source #

`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 :: Int -> TypeBase dim as -> TypeBase dim as Source #

`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 :: Shape dim -> TypeBase dim NoUniqueness -> TypeBase dim NoUniqueness Source #

`arrayOf u 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.

arrayOfWithAliases :: u -> Shape dim -> TypeBase dim u' -> TypeBase dim u Source #

Like `arrayOf`, but you can pass in uniqueness info of the resulting array.

toStructural :: TypeBase dim as -> TypeBase () () Source #

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

toStruct :: TypeBase dim u -> TypeBase dim NoUniqueness Source #

Remove uniquenss information from a type.

toRes :: Uniqueness -> TypeBase Size u -> ResType Source #

Convert to `ResType`

toParam :: Diet -> TypeBase Size u -> ParamType Source #

Uses `Observe`.

resToParam :: ResType -> ParamType Source #

Preserves relation between `Diet` and `Uniqueness`.

paramToRes :: ParamType -> ResType Source #

Preserves relation between `Diet` and `Uniqueness`.

toResRet :: Uniqueness -> RetTypeBase Size u -> ResRetType Source #

Convert to `ResRetType`

setUniqueness :: TypeBase dim u1 -> u2 -> TypeBase dim u2 Source #

Set the uniqueness attribute of a type. If the type is a record or sum type, the uniqueness of its components will be modified.

noSizes :: TypeBase Size as -> TypeBase () as Source #

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

traverseDims :: forall f fdim tdim als. Applicative f => (Set VName -> DimPos -> fdim -> f tdim) -> TypeBase fdim als -> f (TypeBase tdim als) Source #

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.

data DimPos Source #

Where does this dimension occur?

Constructors

PosImmediate | Immediately in the argument to `traverseDims`.
PosParam | In a function parameter type.
PosReturn | In a function return type.

#### Instances

Instances details

Show DimPos Source # |
Instance details Defined in Language.Futhark.Prop Methods showsPrec :: Int -> DimPos -> ShowS Source # show :: DimPos -> String Source # showList :: [DimPos] -> ShowS Source #
Eq DimPos Source # |
Instance details Defined in Language.Futhark.Prop Methods (==) :: DimPos -> DimPos -> Bool Source # (/=) :: DimPos -> DimPos -> Bool Source #
Ord DimPos Source # |
Instance details Defined in Language.Futhark.Prop Methods compare :: DimPos -> DimPos -> Ordering Source # (<) :: DimPos -> DimPos -> Bool Source # (<=) :: DimPos -> DimPos -> Bool Source # (>) :: DimPos -> DimPos -> Bool Source # (>=) :: DimPos -> DimPos -> Bool Source # max :: DimPos -> DimPos -> DimPos Source # min :: DimPos -> DimPos -> DimPos Source #

tupleRecord :: [TypeBase dim as] -> ScalarTypeBase dim as Source #

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

isTupleRecord :: TypeBase dim as -> Maybe [TypeBase dim as] Source #

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

areTupleFields :: Map Name a -> Maybe [a] Source #

Does this record map correspond to a tuple?

tupleFields :: [a] -> Map Name a Source #

Construct a record map corresponding to a tuple.

tupleFieldNames :: [Name] Source #

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

sortFields :: Map Name a -> [(Name, a)] Source #

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

sortConstrs :: Map Name a -> [(Name, a)] Source #

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

isTypeParam :: TypeParamBase vn -> Bool Source #

Is this a `TypeParamType`?

isSizeParam :: TypeParamBase vn -> Bool Source #

Is this a `TypeParamDim`?

matchDims :: forall as m d1 d2. (Monoid as, Monad m) => ([VName] -> d1 -> d2 -> m d1) -> TypeBase d1 as -> TypeBase d2 as -> m (TypeBase d1 as) Source #

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).

# Un-typechecked ASTs

type UncheckedType = TypeBase (Shape Name) () Source #

A type with no aliasing information but shape annotations.

type UncheckedTypeExp = TypeExp UncheckedExp Name Source #

An unchecked type expression.

type UncheckedIdent = IdentBase NoInfo Name Source #

An identifier with no type annotations.

type UncheckedDimIndex = DimIndexBase NoInfo Name Source #

An index with no type annotations.

type UncheckedSlice = SliceBase NoInfo Name Source #

A slice with no type annotations.

type UncheckedExp = ExpBase NoInfo Name Source #

An expression with no type annotations.

type UncheckedModExp = ModExpBase NoInfo Name Source #

A module expression with no type annotations.

type UncheckedModTypeExp = ModTypeExpBase NoInfo Name Source #

A module type expression with no type annotations.

type UncheckedTypeParam = TypeParamBase Name Source #

A type parameter with no type annotations.

type UncheckedPat = PatBase NoInfo Name Source #

A pattern with no type annotations.

type UncheckedValBind = ValBindBase NoInfo Name Source #

A function declaration with no type annotations.

type UncheckedTypeBind = TypeBindBase NoInfo Name Source #

A type binding with no type annotations.

type UncheckedModTypeBind = ModTypeBindBase NoInfo Name Source #

A module type binding with no type annotations.

type UncheckedModBind = ModBindBase NoInfo Name Source #

A module binding with no type annotations.

type UncheckedDec = DecBase NoInfo Name Source #

A declaration with no type annotations.

type UncheckedSpec = SpecBase NoInfo Name Source #

A spec with no type annotations.

type UncheckedProg = ProgBase NoInfo Name Source #

A Futhark program with no type annotations.

type UncheckedCase = CaseBase NoInfo Name Source #

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

# Type-checked ASTs

type Ident = IdentBase Info VName Source #

An identifier with type- and aliasing information.

type DimIndex = DimIndexBase Info VName Source #

An index with type information.

type Slice = SliceBase Info VName Source #

A slice with type information.

type AppExp = AppExpBase Info VName Source #

An application expression with type information.

type Exp = ExpBase Info VName Source #

An expression with type information.

type Pat = PatBase Info VName Source #

A pattern with type information.

type ModExp = ModExpBase Info VName Source #

A type-checked module expression.

type ModParam = ModParamBase Info VName Source #

A type-checked module parameter.

type ModTypeExp = ModTypeExpBase Info VName Source #

A type-checked module type expression.

type ModBind = ModBindBase Info VName Source #

A type-checked module binding.

type ModTypeBind = ModTypeBindBase Info VName Source #

A type-checked module type binding.

type ValBind = ValBindBase Info VName Source #

An constant declaration with type information.

type Dec = DecBase Info VName Source #

A type-checked declaration.

type Spec = SpecBase Info VName Source #

A type-checked specification.

type Prog = ProgBase Info VName Source #

An Futhark program with type information.

type TypeBind = TypeBindBase Info VName Source #

A type binding with type information.

type StructTypeArg = TypeArg Size Source #

A known type arg with shape annotations.

type ScalarType = ScalarTypeBase () Source #

A known scalar type with no shape annotations.

type TypeParam = TypeParamBase VName Source #

A type-checked type parameter.

type Case = CaseBase Info VName Source #

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