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

Safe Haskell | Safe-Inferred
Language | GHC2021

Futhark.IR.Prop.Scope

Contents

- Extended type environment

Description

The core Futhark AST does not contain type information when we use a variable. Therefore, most transformations expect to be able to access some kind of symbol table that maps names to their types.

This module defines the concept of a type environment as a mapping from variable names to `NameInfo`s. Convenience facilities are also provided to communicate that some monad or applicative functor maintains type information.

A simple example of a monad that maintains such as environment is `Reader`. Indeed, `HasScope` and `LocalScope` instances for this monad are already defined.

Synopsis

- class (Applicative m, RepTypes rep) => HasScope rep m | m -> rep where
  - lookupType :: VName -> m Type
  - lookupInfo :: VName -> m (NameInfo rep)
  - askScope :: m (Scope rep)
  - asksScope :: (Scope rep -> a) -> m a
- data NameInfo rep
  - = LetName (LetDec rep)
  - | FParamName (FParamInfo rep)
  - | LParamName (LParamInfo rep)
  - | IndexName IntType
- class (HasScope rep m, Monad m) => LocalScope rep m where
  - localScope :: Scope rep -> m a -> m a
- type Scope rep = Map VName (NameInfo rep)
- class Scoped rep a | a -> rep where
  - scopeOf :: a -> Scope rep
- inScopeOf :: (Scoped rep a, LocalScope rep m) => a -> m b -> m b
- scopeOfLParams :: LParamInfo rep ~ dec => [Param dec] -> Scope rep
- scopeOfFParams :: FParamInfo rep ~ dec => [Param dec] -> Scope rep
- scopeOfLoopForm :: LoopForm -> Scope rep
- scopeOfPat :: LetDec rep ~ dec => Pat dec -> Scope rep
- scopeOfPatElem :: LetDec rep ~ dec => PatElem dec -> Scope rep
- type SameScope rep1 rep2 = (LetDec rep1 ~ LetDec rep2, FParamInfo rep1 ~ FParamInfo rep2, LParamInfo rep1 ~ LParamInfo rep2)
- castScope :: SameScope fromrep torep => Scope fromrep -> Scope torep
- data ExtendedScope rep m a
- extendedScope :: ExtendedScope rep m a -> Scope rep -> m a

# Documentation

class (Applicative m, RepTypes rep) => HasScope rep m | m -> rep where Source #

The class of applicative functors (or more common in practice: monads) that permit the lookup of variable types. A default method for `lookupType` exists, which is sufficient (if not always maximally efficient, and using `error` to fail) when `askScope` is defined.

Minimal complete definition

askScope

Methods

lookupType :: VName -> m Type Source #

Return the type of the given variable, or fail if it is not in the type environment.

lookupInfo :: VName -> m (NameInfo rep) Source #

Return the info of the given variable, or fail if it is not in the type environment.

askScope :: m (Scope rep) Source #

Return the type environment contained in the applicative functor.

asksScope :: (Scope rep -> a) -> m a Source #

Return the result of applying some function to the type environment.

#### Instances

Instances details

HasScope SOACS ADM Source # |
Instance details Defined in Futhark.AD.Rev.Monad Methods lookupType :: VName -> ADM Type Source # lookupInfo :: VName -> ADM (NameInfo SOACS) Source # askScope :: ADM (Scope SOACS) Source # asksScope :: (Scope SOACS -> a) -> ADM a Source #
HasScope SOACS InternaliseM Source # |
Instance details Defined in Futhark.Internalise.Monad Methods lookupType :: VName -> InternaliseM Type Source # lookupInfo :: VName -> InternaliseM (NameInfo SOACS) Source # askScope :: InternaliseM (Scope SOACS) Source # asksScope :: (Scope SOACS -> a) -> InternaliseM a Source #
ASTRep rep => HasScope rep (RuleM rep) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Rule Methods lookupType :: VName -> RuleM rep Type Source # lookupInfo :: VName -> RuleM rep (NameInfo rep) Source # askScope :: RuleM rep (Scope rep) Source # asksScope :: (Scope rep -> a) -> RuleM rep a Source #
(ASTRep rep, Monad m) => HasScope rep (BuilderT rep m) Source # |
Instance details Defined in Futhark.Builder Methods lookupType :: VName -> BuilderT rep m Type Source # lookupInfo :: VName -> BuilderT rep m (NameInfo rep) Source # askScope :: BuilderT rep m (Scope rep) Source # asksScope :: (Scope rep -> a) -> BuilderT rep m a Source #
(HasScope rep m, Monad m) => HasScope rep (ExtendedScope rep m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods lookupType :: VName -> ExtendedScope rep m Type Source # lookupInfo :: VName -> ExtendedScope rep m (NameInfo rep) Source # askScope :: ExtendedScope rep m (Scope rep) Source # asksScope :: (Scope rep -> a) -> ExtendedScope rep m a Source #
(Monad m, ASTRep rep) => HasScope rep (DistNestT rep m) Source # |
Instance details Defined in Futhark.Pass.ExtractKernels.DistributeNests Methods lookupType :: VName -> DistNestT rep m Type Source # lookupInfo :: VName -> DistNestT rep m (NameInfo rep) Source # askScope :: DistNestT rep m (Scope rep) Source # asksScope :: (Scope rep -> a) -> DistNestT rep m a Source #
(Monad m, HasScope rep m) => HasScope rep (ExceptT e m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods lookupType :: VName -> ExceptT e m Type Source # lookupInfo :: VName -> ExceptT e m (NameInfo rep) Source # askScope :: ExceptT e m (Scope rep) Source # asksScope :: (Scope rep -> a) -> ExceptT e m a Source #
(Monad m, RepTypes rep) => HasScope rep (ReaderT (Scope rep) m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods lookupType :: VName -> ReaderT (Scope rep) m Type Source # lookupInfo :: VName -> ReaderT (Scope rep) m (NameInfo rep) Source # askScope :: ReaderT (Scope rep) m (Scope rep) Source # asksScope :: (Scope rep -> a) -> ReaderT (Scope rep) m a Source #
ASTRep torep => HasScope torep (AllocM fromrep torep) Source # |
Instance details Defined in Futhark.Pass.ExplicitAllocations Methods lookupType :: VName -> AllocM fromrep torep Type Source # lookupInfo :: VName -> AllocM fromrep torep (NameInfo torep) Source # askScope :: AllocM fromrep torep (Scope torep) Source # asksScope :: (Scope torep -> a) -> AllocM fromrep torep a Source #
HasScope SOACS (ImpM rep r op) Source # |
Instance details Defined in Futhark.CodeGen.ImpGen Methods lookupType :: VName -> ImpM rep r op Type Source # lookupInfo :: VName -> ImpM rep r op (NameInfo SOACS) Source # askScope :: ImpM rep r op (Scope SOACS) Source # asksScope :: (Scope SOACS -> a) -> ImpM rep r op a Source #
(Monad m, Monoid w, RepTypes rep) => HasScope rep (RWST (Scope rep) w s m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods lookupType :: VName -> RWST (Scope rep) w s m Type Source # lookupInfo :: VName -> RWST (Scope rep) w s m (NameInfo rep) Source # askScope :: RWST (Scope rep) w s m (Scope rep) Source # asksScope :: (Scope rep -> a) -> RWST (Scope rep) w s m a Source #
(Monad m, Monoid w, RepTypes rep) => HasScope rep (RWST (Scope rep) w s m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods lookupType :: VName -> RWST (Scope rep) w s m Type Source # lookupInfo :: VName -> RWST (Scope rep) w s m (NameInfo rep) Source # askScope :: RWST (Scope rep) w s m (Scope rep) Source # asksScope :: (Scope rep -> a) -> RWST (Scope rep) w s m a Source #
Checkable rep => HasScope (Aliases rep) (TypeM rep) Source # |
Instance details Defined in Futhark.IR.TypeCheck Methods lookupType :: VName -> TypeM rep Type Source # lookupInfo :: VName -> TypeM rep (NameInfo (Aliases rep)) Source # askScope :: TypeM rep (Scope (Aliases rep)) Source # asksScope :: (Scope (Aliases rep) -> a) -> TypeM rep a Source #
SimplifiableRep rep => HasScope (Wise rep) (SimpleM rep) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods lookupType :: VName -> SimpleM rep Type Source # lookupInfo :: VName -> SimpleM rep (NameInfo (Wise rep)) Source # askScope :: SimpleM rep (Scope (Wise rep)) Source # asksScope :: (Scope (Wise rep) -> a) -> SimpleM rep a Source #

data NameInfo rep Source #

How some name in scope was bound.

Constructors

LetName (LetDec rep) |
FParamName (FParamInfo rep) |
LParamName (LParamInfo rep) |
IndexName IntType |

#### Instances

Instances details

(Monad m, RepTypes rep) => HasScope rep (ReaderT (Scope rep) m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods lookupType :: VName -> ReaderT (Scope rep) m Type Source # lookupInfo :: VName -> ReaderT (Scope rep) m (NameInfo rep) Source # askScope :: ReaderT (Scope rep) m (Scope rep) Source # asksScope :: (Scope rep -> a) -> ReaderT (Scope rep) m a Source #
(Monad m, RepTypes rep) => LocalScope rep (ReaderT (Scope rep) m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods localScope :: Scope rep -> ReaderT (Scope rep) m a -> ReaderT (Scope rep) m a Source #
Scoped rep (VName, NameInfo rep) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods scopeOf :: (VName, NameInfo rep) -> Scope rep Source #
(Monad m, Monoid w, RepTypes rep) => HasScope rep (RWST (Scope rep) w s m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods lookupType :: VName -> RWST (Scope rep) w s m Type Source # lookupInfo :: VName -> RWST (Scope rep) w s m (NameInfo rep) Source # askScope :: RWST (Scope rep) w s m (Scope rep) Source # asksScope :: (Scope rep -> a) -> RWST (Scope rep) w s m a Source #
(Monad m, Monoid w, RepTypes rep) => HasScope rep (RWST (Scope rep) w s m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods lookupType :: VName -> RWST (Scope rep) w s m Type Source # lookupInfo :: VName -> RWST (Scope rep) w s m (NameInfo rep) Source # askScope :: RWST (Scope rep) w s m (Scope rep) Source # asksScope :: (Scope rep -> a) -> RWST (Scope rep) w s m a Source #
(Monad m, Monoid w, RepTypes rep) => LocalScope rep (RWST (Scope rep) w s m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods localScope :: Scope rep -> RWST (Scope rep) w s m a -> RWST (Scope rep) w s m a Source #
(Monad m, Monoid w, RepTypes rep) => LocalScope rep (RWST (Scope rep) w s m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods localScope :: Scope rep -> RWST (Scope rep) w s m a -> RWST (Scope rep) w s m a Source #
RepTypes rep => Show (NameInfo rep) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods showsPrec :: Int -> NameInfo rep -> ShowS Source # show :: NameInfo rep -> String Source # showList :: [NameInfo rep] -> ShowS Source #
RepTypes rep => Typed (NameInfo rep) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods typeOf :: NameInfo rep -> Type Source #
Substitutable rep => Substitute (NameInfo rep) Source # |
Instance details Defined in Futhark.Transform.Substitute Methods substituteNames :: Map VName VName -> NameInfo rep -> NameInfo rep Source #
Monad m => MonadReader (Scope rep) (ExtendedScope rep m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods ask :: ExtendedScope rep m (Scope rep) Source # local :: (Scope rep -> Scope rep) -> ExtendedScope rep m a -> ExtendedScope rep m a Source # reader :: (Scope rep -> a) -> ExtendedScope rep m a Source #

class (HasScope rep m, Monad m) => LocalScope rep m where Source #

The class of monads that not only provide a `Scope`, but also the ability to locally extend it. A `Reader` containing a `Scope` is the prototypical example of such a monad.

Methods

localScope :: Scope rep -> m a -> m a Source #

Run a computation with an extended type environment. Note that this is intended to *add* to the current type environment, it does not replace it.

#### Instances

Instances details

LocalScope SOACS ADM Source # |
Instance details Defined in Futhark.AD.Rev.Monad Methods localScope :: Scope SOACS -> ADM a -> ADM a Source #
LocalScope SOACS InternaliseM Source # |
Instance details Defined in Futhark.Internalise.Monad Methods localScope :: Scope SOACS -> InternaliseM a -> InternaliseM a Source #
ASTRep rep => LocalScope rep (RuleM rep) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Rule Methods localScope :: Scope rep -> RuleM rep a -> RuleM rep a Source #
(ASTRep rep, Monad m) => LocalScope rep (BuilderT rep m) Source # |
Instance details Defined in Futhark.Builder Methods localScope :: Scope rep -> BuilderT rep m a -> BuilderT rep m a Source #
(Monad m, ASTRep rep) => LocalScope rep (DistNestT rep m) Source # |
Instance details Defined in Futhark.Pass.ExtractKernels.DistributeNests Methods localScope :: Scope rep -> DistNestT rep m a -> DistNestT rep m a Source #
LocalScope rep m => LocalScope rep (ExceptT e m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods localScope :: Scope rep -> ExceptT e m a -> ExceptT e m a Source #
(Monad m, RepTypes rep) => LocalScope rep (ReaderT (Scope rep) m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods localScope :: Scope rep -> ReaderT (Scope rep) m a -> ReaderT (Scope rep) m a Source #
ASTRep torep => LocalScope torep (AllocM fromrep torep) Source # |
Instance details Defined in Futhark.Pass.ExplicitAllocations Methods localScope :: Scope torep -> AllocM fromrep torep a -> AllocM fromrep torep a Source #
(Monad m, Monoid w, RepTypes rep) => LocalScope rep (RWST (Scope rep) w s m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods localScope :: Scope rep -> RWST (Scope rep) w s m a -> RWST (Scope rep) w s m a Source #
(Monad m, Monoid w, RepTypes rep) => LocalScope rep (RWST (Scope rep) w s m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods localScope :: Scope rep -> RWST (Scope rep) w s m a -> RWST (Scope rep) w s m a Source #
SimplifiableRep rep => LocalScope (Wise rep) (SimpleM rep) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods localScope :: Scope (Wise rep) -> SimpleM rep a -> SimpleM rep a Source #

type Scope rep = Map VName (NameInfo rep) Source #

A scope is a mapping from variable names to information about that name.

class Scoped rep a | a -> rep where Source #

The class of things that can provide a scope. There is no overarching rule for what this means. For a `Stm`, it is the corresponding pattern. For a `Lambda`, is is the parameters.

Methods

scopeOf :: a -> Scope rep Source #

#### Instances

Instances details

Scoped rep (FunDef rep) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods scopeOf :: FunDef rep -> Scope rep Source #
Scoped rep (Lambda rep) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods scopeOf :: Lambda rep -> Scope rep Source #
Scoped rep (Stm rep) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods scopeOf :: Stm rep -> Scope rep Source #
Scoped rep (Stms rep) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods scopeOf :: Stms rep -> Scope rep Source #
Scoped rep a => Scoped rep [a] Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods scopeOf :: [a] -> Scope rep Source #
Scoped rep (VName, NameInfo rep) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods scopeOf :: (VName, NameInfo rep) -> Scope rep Source #

inScopeOf :: (Scoped rep a, LocalScope rep m) => a -> m b -> m b Source #

Extend the monadic scope with the `scopeOf` the given value.

scopeOfLParams :: LParamInfo rep ~ dec => [Param dec] -> Scope rep Source #

The scope of some lambda parameters.

scopeOfFParams :: FParamInfo rep ~ dec => [Param dec] -> Scope rep Source #

The scope of some function or loop parameters.

scopeOfLoopForm :: LoopForm -> Scope rep Source #

The scope of a loop form.

scopeOfPat :: LetDec rep ~ dec => Pat dec -> Scope rep Source #

The scope of a pattern.

scopeOfPatElem :: LetDec rep ~ dec => PatElem dec -> Scope rep Source #

The scope of a pattern element.

type SameScope rep1 rep2 = (LetDec rep1 ~ LetDec rep2, FParamInfo rep1 ~ FParamInfo rep2, LParamInfo rep1 ~ LParamInfo rep2) Source #

A constraint that indicates two representations have the same `NameInfo` representation.

castScope :: SameScope fromrep torep => Scope fromrep -> Scope torep Source #

If two scopes are really the same, then you can convert one to the other.

# Extended type environment

data ExtendedScope rep m a Source #

A monad transformer that carries around an extended `Scope`. Its `lookupType` method will first look in the extended `Scope`, and then use the `lookupType` method of the underlying monad.

#### Instances

Instances details

(HasScope rep m, Monad m) => HasScope rep (ExtendedScope rep m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods lookupType :: VName -> ExtendedScope rep m Type Source # lookupInfo :: VName -> ExtendedScope rep m (NameInfo rep) Source # askScope :: ExtendedScope rep m (Scope rep) Source # asksScope :: (Scope rep -> a) -> ExtendedScope rep m a Source #
Monad m => MonadReader (Scope rep) (ExtendedScope rep m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods ask :: ExtendedScope rep m (Scope rep) Source # local :: (Scope rep -> Scope rep) -> ExtendedScope rep m a -> ExtendedScope rep m a Source # reader :: (Scope rep -> a) -> ExtendedScope rep m a Source #
Applicative m => Applicative (ExtendedScope rep m) Source # |

Instance details

Defined in Futhark.IR.Prop.Scope

Methods

pure :: a -> ExtendedScope rep m a Source #

(<*>) :: ExtendedScope rep m (a -> b) -> ExtendedScope rep m a -> ExtendedScope rep m b Source #

liftA2 :: (a -> b -> c) -> ExtendedScope rep m a -> ExtendedScope rep m b -> ExtendedScope rep m c Source #

(*>) :: ExtendedScope rep m a -> ExtendedScope rep m b -> ExtendedScope rep m b Source #

(<*) :: ExtendedScope rep m a -> ExtendedScope rep m b -> ExtendedScope rep m a Source #

Functor m => Functor (ExtendedScope rep m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods fmap :: (a -> b) -> ExtendedScope rep m a -> ExtendedScope rep m b Source # (<$) :: a -> ExtendedScope rep m b -> ExtendedScope rep m a Source #
Monad m => Monad (ExtendedScope rep m) Source # |
Instance details Defined in Futhark.IR.Prop.Scope Methods (>>=) :: ExtendedScope rep m a -> (a -> ExtendedScope rep m b) -> ExtendedScope rep m b Source # (>>) :: ExtendedScope rep m a -> ExtendedScope rep m b -> ExtendedScope rep m b Source # return :: a -> ExtendedScope rep m a Source #

extendedScope :: ExtendedScope rep m a -> Scope rep -> m a Source #

Run a computation in the extended type environment.