| Copyright | (c) 2020 James Koppel |
|---|---|
| License | BSD3 |
| Safe Haskell | None |
| Language | Haskell2010 |
Cubix.Essentials
Description
This is a beginner-friendly package containing the most common functions and types needed by Cubix programs. It is built as a companion to the Cubix tutorial, though we explain many things in both places.
Guide to using this file * Strongly recommend: Click "Collapse All Instances" in the top-right corner * For newcomers: Look at the examples given, not at the types * This file is not the authoritative source for any of its exports. Some typeclasses have methods hidden here. Some functions are exported with more-specific type signatures that are easier to understand.
Synopsis
- deriveAll :: [Name] -> Q [Dec]
- data Sum (fs :: [(Type -> Type) -> Type -> Type]) (h :: Type -> Type) e
- type Term fs = HFix (Sum fs)
- inject :: g :-<: fs => g (Term fs) l -> Term fs l
- class f :<: Sum fs => (f :: (Type -> Type) -> Type -> Type) :-<: (fs :: [(Type -> Type) -> Type -> Type])
- class All (c :: k -> Constraint) (fs :: [k])
- caseCxt :: All cxt fs => Proxy cxt -> (forall f. cxt f => f a e -> b) -> Sum fs a e -> b
- class All HFunctor fs => InjF fs l l' where
- data Label
- type TermLab f = AnnTerm Label f
- class HFunctor (h :: (Type -> Type) -> Type -> Type)
- class HFunctor h => HFoldable (h :: (Type -> Type) -> Type -> Type)
- class HFoldable t => HTraversable (t :: (Type -> Type) -> Type -> Type)
- class EqHF (f :: (Type -> Type) -> Type -> Type)
- class EqHF f => OrdHF (f :: (Type -> Type) -> Type -> Type)
- class ShowHF (f :: (Type -> Type) -> Type -> Type)
- project :: g :<: f => Cxt h f a l -> Maybe (g (Cxt h f a) l)
- project' :: (RemA f f', s :<: f') => HFix f i -> Maybe (s (HFix f) i)
- class Functor f => InsertF f e where
- class ExtractF f e where
- extractF :: e (f l) -> f (e l)
- query :: (All HFoldable fs, All HFunctor fs) => (forall i. Term fs i -> r) -> (r -> r -> r) -> Term fs l -> r
- transform :: All HFunctor fs => (forall i. Term fs i -> Term fs i) -> Term fs l -> Term fs l
- type RewriteM (m :: Type -> Type) (f :: Type -> Type) l = f l -> m (f l)
- (>+>) :: forall (m :: Type -> Type) (f :: Type -> Type). MonadPlus m => GRewriteM m f -> GRewriteM m f -> GRewriteM m f
- addFail :: Monad m => TranslateM m f l t -> TranslateM (MaybeT m) f l t
- promoteRF :: forall f l (m :: Type -> Type). (DynCase f l, Monad m) => RewriteM (MaybeT m) f l -> GRewriteM (MaybeT m) f
- promoteR :: forall f l (m :: Type -> Type). (DynCase f l, Monad m) => RewriteM (MaybeT m) f l -> GRewriteM m f
- alltdR :: forall (m :: Type -> Type) (f :: (Type -> Type) -> Type -> Type) h (a :: Type -> Type). (Monad m, HTraversable f) => GRewriteM m (Cxt h f a) -> GRewriteM m (Cxt h f a)
- prunetdR :: forall (m :: Type -> Type) (f :: (Type -> Type) -> Type -> Type) h (a :: Type -> Type). (Monad m, HTraversable f) => GRewriteM (MaybeT m) (Cxt h f a) -> GRewriteM m (Cxt h f a)
- type MCSig = MCSig
- type MJavaSig = MJavaSig
- type MJSSig = MJSSig
- type MLuaSig = MLuaSig
- type MPythonSig = MPythonSig
- type MCTerm = Term MCSig
- type MJavaTerm = Term MJavaSig
- type MJSTerm = Term MJSSig
- type MLuaTerm = Term MLuaSig
- type MPythonTerm = Term MPythonSig
- type MCTermLab = TermLab MCSig
- type MJavaTermLab = TermLab MJavaSig
- type MJSTermLab = TermLab MJSSig
- type MLuaTermLab = TermLab MLuaSig
- type MPythonTermLab = TermLab MPythonSig
- class ParseFile fs where
- class Pretty fs where
- data Cfg fs
- data CfgNode fs
- safeLookupCfg :: Cfg fs -> Label -> Maybe (CfgNode fs)
- lookupCfg :: Cfg fs -> Label -> CfgNode fs
- cfgNodeForTerm :: Cfg fs -> CfgNodeType -> TermLab fs l -> Maybe (CfgNode fs)
- makeCfg :: forall fs l. CfgBuilder fs => TermLab fs l -> Cfg fs
- class Monad m => MonadCfgInsertion m fs l where
- dominatingPrependFirst :: TermLab fs i -> TermLab fs l -> m ()
- type CfgInserterT fs l m = WriterT [Action fs l] m
- performCfgInsertions :: (MonadAnnotater Label m, InsertAt fs l, All HTraversable fs, All HFunctor fs, All HFoldable fs) => Proxy l -> ProgInfo fs -> RewriteM (CfgInserterT fs l m) (TermLab fs) i -> RewriteM m (TermLab fs) i
Core representation
Language fragments
The first concept is that of a language fragment and signature. Language fragments in Cubix look like this:
data ExpL data StatementL data Statement e l where Assign :: String -> e ExpL -> Statement e StatementL Seq :: e StatementL -> e StatementL -> Statement e StatementL
This definition of Statement is called a *language fragment*. It defines
the nodes Assign and Seq without any reference to the larger language
they are embedded in. The *labels* StatementL and ExpL are *sorts*, categories of terms.
Popular languages commonly have a sort for top-level definitions, a sort for lvalues, a sort for
import statements, etc. Specifying the sort separately from the language fragment makes it possible
to modularly add new statements and expressions to a language definition, which we will demonstrate shortly.
Expect to see the kind (* -> *) -> * -> * a lot, the kind of language fragments.
When you define a normal datatype (kind *) in Haskell, you might suffix it with
deriving (Eq, Ord, Show). The equivalent for these higher-kinded language fragments is
to derive their higher-kinded equivalents using the deriveAll Template Haskell function, e.g.:
deriveAll [''Statement]
deriveAll :: [Name] -> Q [Dec] Source #
Derives instances of the following for each type in the list:
HFunctor,HTraversable,HFoldable,EqHF,ShowHF,OrdHF,DynCase
Additonally, it will create smart constructors for the data type
Signatures: Combining fragments
Language fragments let one define nodes independent of a larger language. We shall soon
show how to combine them into a **signature**. But first, let us define two more
language fragments, Conditional and Exp.
data Conditional e l where If :: e ExpL -> e StatementL -> e StatementL -> Conditional e StatementL data Exp e l where VarExp :: String -> Exp e ExpL Add :: e ExpL -> e ExpL -> Exp e ExpL -- other cases omitted
As a preview, note how Conditional defines a new node If of sort Statement. When these fragments are
combined into a language, the If node will be able to be included under a Seq node, just as easily
as if was defined in the Statement fragment.
A *signature* is a collection of language fragments. They take the form of a type-level list.
Here is a signature for a language containing all the nodes in the Statement, Conditional, and Exp
fragments.
type LangSig = '[Statement, Conditional, Exp]
Signatures have the kind [(* -> *) -> * -> *], another kind you'll encounter frequently.
Signatures are used by passing them to the Sum constructor, e.g.:
Sum LangSig
Sum LangSig has kind (* -> *) -> * -> *, the same kind as language fragments. It is
conceptually a single language fragment consisting of the combined nodes of Statement, Conditional,
and Exp. It could even be placed in another language signature, and nested within another Sum,
although this use case is not supported.
The Sum constructor is important to Cubix, but you may not use it directly.
More often, you'll use something like Term LangSig --- but note that Term is defined using
Sum.
data Sum (fs :: [(Type -> Type) -> Type -> Type]) (h :: Type -> Type) e #
Data type defining a sum of signatures.
It is inspired by modular reifiable matching, as described in
- Oliveira, Bruno C. D. S., Shin-Cheng Mu, and Shu-Hung You. "Modular reifiable matching: a list-of-functors approach to two-level types." In Haskell Symposium, 2015.
except that this definition uses value-level integers (in the Elem datatype) in place
of type-level naturals. It hence uses unsafeCoerce under the hood, but is type-safe if used
through the public API. The result is that values of this type take constant memory with respect to the number
of summands (unlike vanilla datatypes à la carte), and constant time to dereference
(unlike modular reifiable matching). The representation is the bare minimum: an int representing the alternative,
and pointer to the value.
Instances
Terms
Terms are how we put stuff together
Dealing with sums
class f :<: Sum fs => (f :: (Type -> Type) -> Type -> Type) :-<: (fs :: [(Type -> Type) -> Type -> Type]) #
Instances
| f :<: Sum fs => f :-<: fs | |
Defined in Data.Comp.Multi.Ops | |
class All (c :: k -> Constraint) (fs :: [k]) #
An instance of All c fs holds if c f holds for all f in fs.
Example: All holds if there are HFunctor '[Add, Mul]HFunctor instances for signatures
Add and Mul.
The primary way to consume an All instance is with the caseCxt function. E.g.:
class Pretty f where pretty :: f e l -> String instance (All Pretty fs) => Pretty (Sum fs) where pretty x = caseCxt (Proxy @Pretty) pretty x
Minimal complete definition
dicts
Instances
| All (c :: k -> Constraint) ('[] :: [k]) | |
Defined in Data.Comp.Dict | |
| (All c fs, c f) => All (c :: a -> Constraint) (f ': fs :: [a]) | |
Defined in Data.Comp.Dict | |
caseCxt :: All cxt fs => Proxy cxt -> (forall f. cxt f => f a e -> b) -> Sum fs a e -> b Source #
For full documentaton, see original declaration: caseCxt
Higher topics involving sums/tems
Sort injections
class All HFunctor fs => InjF fs l l' where Source #
InjF allows us to create "sort injections," stating that one sort can be considered a coercive subsort of another..
For example, if we wanted to parameterize whether a given syntax allows arbitrary expressions to be used as function arguments, we could have the function terms have arguments of sort FunArg and create an ExpressionIsFunArg . Defining an instance
instance (ExpressionIsFunArg :-<: f) => InjF fs ExpL FunArgL
would then allow us to use expression as function arguments freely.
Instances
Labeled nodes
Provides unique labels for AST nodes
Instances
| Eq Label Source # | |
| Data Label Source # | |
Defined in Cubix.Language.Info Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Label -> c Label # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Label # dataTypeOf :: Label -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c Label) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Label) # gmapT :: (forall b. Data b => b -> b) -> Label -> Label # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Label -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Label -> r # gmapQ :: (forall d. Data d => d -> u) -> Label -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Label -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Label -> m Label # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Label -> m Label # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Label -> m Label # | |
| Ord Label Source # | |
| Read Label Source # | |
| Show Label Source # | |
| Generic Label Source # | |
| NFData Label Source # | |
Defined in Cubix.Language.Info | |
| HasLabel Label Source # | |
| (Monad m, MonadLabeler s m) => MonadAnnotater Label m Source # | |
| type Rep Label Source # | |
Defined in Cubix.Language.Info | |
Common typeclassess
These are analogues of standard typeclasses, but for sorted unfixed datatypes.
You are unlikely to use methods in these classes directly, but
you may frequently invoke functions that require them. You may
wind up writing many constraints that use these, likely combined with the All
constructor.
class HFunctor (h :: (Type -> Type) -> Type -> Type) #
This class represents higher-order functors (Johann, Ghani, POPL '08) which are endofunctors on the category of endofunctors.
Minimal complete definition
Instances
class HFunctor h => HFoldable (h :: (Type -> Type) -> Type -> Type) #
Instances
class HFoldable t => HTraversable (t :: (Type -> Type) -> Type -> Type) #
Instances
class EqHF (f :: (Type -> Type) -> Type -> Type) #
Signature equality. An instance EqHF f gives rise to an instance
KEq (HTerm f).
Minimal complete definition
Instances
class EqHF f => OrdHF (f :: (Type -> Type) -> Type -> Type) #
Signature ordering. An instance OrdHF f gives rise to an instance
Ord (Term f).
Minimal complete definition
Instances
class ShowHF (f :: (Type -> Type) -> Type -> Type) #
Signature printing. An instance ShowHF f gives rise to an instance
KShow (HTerm f).
Instances
Manipulating terms
Dealing with annotations
Dealing with containers
class Functor f => InsertF f e where Source #
Methods
insertF :: Typeable l => f (e l) -> e (f l) Source #
Inverse of extractF. Pushes a functor into a label.
Example:
insertF:: [JavaProjSourceFileL] ->JavaProj[SourceFileL]
Note that this cannot be used on a labeled tree, as the insertion operation will require generating additional labels.
This is an instance of a distributive law, and can probably be replaced with such.
class ExtractF f e where Source #
Methods
extractF :: e (f l) -> f (e l) Source #
Pulls a functor out of a label.
Example:
extractF::JavaProj[SourceFileL] -> [JavaProjSourceFileL]
Beware that this function unsafely assumes that e.g.: a term of sort
[l] is a ListF node (and similar for Maybe, etc).
If you define a custom node that has sort [l] for any l, and
do not define a corresponding ExtractF instance, then extractF
may give an error.
Traversals
Without strategy combinators
Cubix inherits from compdata two elementary traversal functions.
query :: (All HFoldable fs, All HFunctor fs) => (forall i. Term fs i -> r) -> (r -> r -> r) -> Term fs l -> r Source #
transform :: All HFunctor fs => (forall i. Term fs i -> Term fs i) -> Term fs l -> Term fs l Source #
For full documentation, see original declaration: transform
With strategy combinators
type RewriteM (m :: Type -> Type) (f :: Type -> Type) l = f l -> m (f l) #
The basic type of rewrites. A RewriteM m f l rewrites a term
of signature f, sort l, to another such term, with effects in monad m
Rewrite m f l is equivalent to TranslateM m f l (f l)
(>+>) :: forall (m :: Type -> Type) (f :: Type -> Type). MonadPlus m => GRewriteM m f -> GRewriteM m f -> GRewriteM m f #
Applies two rewrites in suceesion, succeeding if one or both succeed
addFail :: Monad m => TranslateM m f l t -> TranslateM (MaybeT m) f l t #
Lifts a translation into the Maybe monad, allowing it to fail
promoteRF :: forall f l (m :: Type -> Type). (DynCase f l, Monad m) => RewriteM (MaybeT m) f l -> GRewriteM (MaybeT m) f #
Turns a rewrite that runs on a single sort to one that runs on any sort,
failing for all other sorts. Equivalent to dynamicR
promoteR :: forall f l (m :: Type -> Type). (DynCase f l, Monad m) => RewriteM (MaybeT m) f l -> GRewriteM m f #
alltdR :: forall (m :: Type -> Type) (f :: (Type -> Type) -> Type -> Type) h (a :: Type -> Type). (Monad m, HTraversable f) => GRewriteM m (Cxt h f a) -> GRewriteM m (Cxt h f a) #
Runs a rewrite in a top-down traversal Defined:
alltdR f = f >=> allR (alltdR f)
prunetdR :: forall (m :: Type -> Type) (f :: (Type -> Type) -> Type -> Type) h (a :: Type -> Type). (Monad m, HTraversable f) => GRewriteM (MaybeT m) (Cxt h f a) -> GRewriteM m (Cxt h f a) #
Languages
Signatures
The primary language signatures in Cubix are MCSig, MJavaSig, MJSSig, MLuaSig, and MPythonSig.
The M stands for "modular."
These are all long, auto-generated definitions consisting of every language fragment in the language (often over 80). We re-export them here, but with their definitions hidden.
type MPythonSig = MPythonSig Source #
Terms
type MPythonTerm = Term MPythonSig Source #
Labeled terms
type MJavaTermLab = TermLab MJavaSig Source #
type MJSTermLab = TermLab MJSSig Source #
type MLuaTermLab = TermLab MLuaSig Source #
type MPythonTermLab = TermLab MPythonSig Source #
Parsing / pretty-printing
class ParseFile fs where Source #
Methods
parseFile :: FilePath -> IO (Maybe (Term fs (RootSort fs))) Source #
Parses a file with the appropriate parser for the language with signature fs.
Recommended to use with the TypeApplications extension,
e.g.: parseFile @MCSig "my_file.c".
class Pretty fs where Source #
Methods
pretty :: Term fs (RootSort fs) -> String Source #
Pretty-prints a term, using the appropriate pretty-printer for the language with
signature fs.
Control-flow graphs
Representation
Instances
| All EqHF fs => Eq (Cfg fs) Source # | |
| (All HFunctor fs, All OrdHF fs, All EqHF fs) => Ord (Cfg fs) Source # | |
| (All ShowHF fs, All HFunctor fs) => Show (Cfg fs) Source # | |
| Generic (Cfg fs) Source # | |
| HasCurCfg (Cfg fs) fs Source # | |
| type Rep (Cfg fs) Source # | |
Defined in Cubix.Language.Parametric.Semantics.Cfg.Graph type Rep (Cfg fs) = D1 ('MetaData "Cfg" "Cubix.Language.Parametric.Semantics.Cfg.Graph" "cubix-0.1.0.0-GE3qzSJT6A0CUj1veI8jGO" 'False) (C1 ('MetaCons "Cfg" 'PrefixI 'True) (S1 ('MetaSel ('Just "_cfg_nodes") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map Label (CfgNode fs))) :*: S1 ('MetaSel ('Just "_cfg_ast_nodes") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map Label (Map CfgNodeType Label))))) | |
Instances
cfgNodeForTerm :: Cfg fs -> CfgNodeType -> TermLab fs l -> Maybe (CfgNode fs) Source #
Construction
makeCfg :: forall fs l. CfgBuilder fs => TermLab fs l -> Cfg fs Source #
Constructs a CFG for the given labelled term
class Monad m => MonadCfgInsertion m fs l where Source #
Minimal complete definition
dominatingPrependFirstOpts, dominatingPrependLastOpts, dominatingAppendFirstOpts, dominatingAppendLastOpts, firstPredPrependLastOpts, restPredPrependLastOpts
Methods
dominatingPrependFirst :: TermLab fs i -> TermLab fs l -> m () Source #
Instances
type CfgInserterT fs l m = WriterT [Action fs l] m Source #
performCfgInsertions :: (MonadAnnotater Label m, InsertAt fs l, All HTraversable fs, All HFunctor fs, All HFoldable fs) => Proxy l -> ProgInfo fs -> RewriteM (CfgInserterT fs l m) (TermLab fs) i -> RewriteM m (TermLab fs) i Source #