-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Educational implementation of the STG (Spineless Tagless -- G-machine) -- -- See README.md @package stgi @version 1 -- | Useful utilities that don't really fit in a specific location. module Stg.Util -- | show with Text as codomain. -- -- 
--   show' = pack . show
--
show' :: Show a => a -> Text -- | The validation version of Either. data Validate err a Failure :: err -> Validate err a Success :: a -> Validate err a -- | 
--   [a,b,c]  ==>  a, b, c
--
commaSep :: [Doc] -> Doc -- | Prefix all contained documents with a bullet symbol. bulletList :: [Doc] -> Doc -- | Add an 's' for non-singleton lists. pluralS :: [a] -> Doc instance GHC.Base.Functor (Stg.Util.Validate a) instance Data.Bifunctor.Bifunctor Stg.Util.Validate instance GHC.Base.Monoid a => GHC.Base.Applicative (Stg.Util.Validate a) -- | Prettyprinting STG elements in various formats. module Stg.Language.Prettyprint -- | The member prettyList is only used to define the instance -- Pretty a => Pretty [a]. In normal circumstances only the -- pretty function is used. class Pretty a pretty :: Pretty a => a -> Doc prettyList :: Pretty a => [a] -> Doc -- | Prettyprint a value as Text, including styles such as colours. prettyprint :: Pretty a => a -> Text -- | Prettyprint a value as Text, stripped off all style information -- such as colours. prettyprintPlain :: Pretty a => a -> Text -- | The STG language syntax tree, modeled after the description in the -- 1992 paper (link). -- -- A Program is typically created using functionality provided by -- the Stg.Parser module, as opposed to manually combining the -- data types given in this module. -- -- For plenty of comparisons of STG language source and generated parse -- trees, have a look at the Stg.Parser.QuasiQuoter module. module Stg.Language -- | An STG program consists of bindings. newtype Program Program :: Binds -> Program -- | Bindings are collections of lambda forms, indexed over variables. -- -- They exist at the top level, or as part of a let(rec) binding. newtype Binds Binds :: (Map Var LambdaForm) -> Binds -- | A lambda form unifies free and bound variables associated with a -- function body. The lambda body must not be of primitive type, as this -- would imply the value is both boxed and unboxed. -- -- 
--   >>> [stg| \(x) y z -> expr x z |]
--   LambdaForm [Var "x"] NoUpdate [Var "y",Var "z"] (AppF (Var "expr") [AtomVar (Var "x"),AtomVar (Var "z")])
--
data LambdaForm LambdaForm :: ![Var] -> !UpdateFlag -> ![Var] -> !Expr -> LambdaForm -- | Prettyprint a LambdaForm, given prettyprinters for the free -- variable list. -- -- Introduced so Closure can hijack it to display the free value -- list differently. prettyLambda :: ([Var] -> Doc) -> LambdaForm -> Doc -- | The update flag distinguishes updateable from non-updateable lambda -- forms. -- -- The former will be overwritten in-place when it is evaluated, allowing -- the calculation of a thunk to be shared among multiple uses of the -- same value. data UpdateFlag Update :: UpdateFlag NoUpdate :: UpdateFlag -- | Distinguishes let from letrec. data Rec NonRecursive :: Rec Recursive :: Rec -- | An expression in the STG language. data Expr -- | Let expression let(rec) ... in ... Let :: !Rec -> !Binds -> !Expr -> Expr -- | Case expression case ... of ... x -> y Case :: !Expr -> !Alts -> Expr -- | Function application f x y z AppF :: !Var -> ![Atom] -> Expr -- | Saturated constructor application Just a AppC :: !Constr -> ![Atom] -> Expr -- | Primitive function application + 2# AppP :: !PrimOp -> !Atom -> !Atom -> Expr -- | Literal expression 1# Lit :: !Literal -> Expr -- | List of possible alternatives in a Case expression. -- -- The list of alts has to be homogeneous. This is not ensured by the -- type system, and should be handled by the parser instead. data Alts Alts :: !NonDefaultAlts -> !DefaultAlt -> Alts -- | The part of a Case alternative that's not the default. data NonDefaultAlts -- | Used in 'case' statements that consist only of a default alternative. -- These can be useful to force or unpack values. NoNonDefaultAlts :: NonDefaultAlts -- | Algebraic alternative, like Cons x xs. AlgebraicAlts :: !(NonEmpty AlgebraicAlt) -> NonDefaultAlts -- | Primitive alternative, like 1#. PrimitiveAlts :: !(NonEmpty PrimitiveAlt) -> NonDefaultAlts -- | As in True | False data AlgebraicAlt AlgebraicAlt :: !Constr -> ![Var] -> !Expr -> AlgebraicAlt -- | As in 1#, 2#, 3# data PrimitiveAlt PrimitiveAlt :: !Literal -> !Expr -> PrimitiveAlt -- | If no viable alternative is found in a pattern match, use a -- DefaultAlt as fallback. data DefaultAlt DefaultNotBound :: !Expr -> DefaultAlt DefaultBound :: !Var -> !Expr -> DefaultAlt -- | Literals are the basis of primitive operations. newtype Literal Literal :: Integer -> Literal -- | Primitive operations. data PrimOp -- | 
--   +
--
Add :: PrimOp -- | 
--   -
--
Sub :: PrimOp -- | 
--   *
--
Mul :: PrimOp -- | 
--   /
--
Div :: PrimOp -- | 
--   %
--
Mod :: PrimOp -- | 
--   ==
--
Eq :: PrimOp -- | 
--   <
--
Lt :: PrimOp -- | 
--   <=
--
Leq :: PrimOp -- | 
--   >
--
Gt :: PrimOp -- | 
--   >=
--
Geq :: PrimOp -- | 
--   /=
--
Neq :: PrimOp -- | Variable. newtype Var Var :: Text -> Var -- | Smallest unit of data. Atoms unify variables and literals, and are -- what functions take as arguments. data Atom AtomVar :: !Var -> Atom AtomLit :: !Literal -> Atom -- | Constructors of algebraic data types. newtype Constr Constr :: Text -> Constr -- | The member prettyList is only used to define the instance -- Pretty a => Pretty [a]. In normal circumstances only the -- pretty function is used. class Pretty a pretty :: Pretty a => a -> Doc prettyList :: Pretty a => [a] -> Doc -- | Classify the type of a lambda form based on its shape. classify :: LambdaForm -> LambdaType -- | Possible classification of lambda forms. data LambdaType -- | Data constructor (AppC as body) LambdaCon :: LambdaType -- | Function (lambda with non-empty argument list) LambdaFun :: LambdaType -- | Thunk (everything else) LambdaThunk :: LambdaType instance Language.Haskell.TH.Syntax.Lift Stg.Language.Program instance Language.Haskell.TH.Syntax.Lift Stg.Language.Literal instance Language.Haskell.TH.Syntax.Lift Stg.Language.LambdaForm instance Language.Haskell.TH.Syntax.Lift Stg.Language.UpdateFlag instance Language.Haskell.TH.Syntax.Lift Stg.Language.Rec instance Language.Haskell.TH.Syntax.Lift Stg.Language.Expr instance Language.Haskell.TH.Syntax.Lift Stg.Language.Alts instance Language.Haskell.TH.Syntax.Lift Stg.Language.AlgebraicAlt instance Language.Haskell.TH.Syntax.Lift Stg.Language.PrimitiveAlt instance Language.Haskell.TH.Syntax.Lift Stg.Language.DefaultAlt instance Language.Haskell.TH.Syntax.Lift Stg.Language.PrimOp instance Language.Haskell.TH.Syntax.Lift Stg.Language.Atom instance Language.Haskell.TH.Syntax.Lift Stg.Language.NonDefaultAlts instance Language.Haskell.TH.Syntax.Lift Stg.Language.Binds instance Language.Haskell.TH.Syntax.Lift Stg.Language.Constr instance Language.Haskell.TH.Syntax.Lift Stg.Language.Var instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.Program instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.Binds instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.LambdaForm instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.Rec instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.Expr instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.Alts instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.AlgebraicAlt instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.PrimitiveAlt instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.DefaultAlt instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.Literal instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.PrimOp instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.Var instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.Atom instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.Constr instance Control.DeepSeq.NFData Stg.Language.Program instance Control.DeepSeq.NFData Stg.Language.Binds instance Control.DeepSeq.NFData Stg.Language.LambdaForm instance Control.DeepSeq.NFData Stg.Language.UpdateFlag instance Control.DeepSeq.NFData Stg.Language.Rec instance Control.DeepSeq.NFData Stg.Language.Expr instance Control.DeepSeq.NFData Stg.Language.Alts instance Control.DeepSeq.NFData Stg.Language.NonDefaultAlts instance Control.DeepSeq.NFData Stg.Language.AlgebraicAlt instance Control.DeepSeq.NFData Stg.Language.PrimitiveAlt instance Control.DeepSeq.NFData Stg.Language.DefaultAlt instance Control.DeepSeq.NFData Stg.Language.Literal instance Control.DeepSeq.NFData Stg.Language.PrimOp instance Control.DeepSeq.NFData Stg.Language.Var instance Control.DeepSeq.NFData Stg.Language.Atom instance Control.DeepSeq.NFData Stg.Language.Constr instance GHC.Generics.Constructor Stg.Language.C1_0Program instance GHC.Generics.Datatype Stg.Language.D1Program instance GHC.Generics.Constructor Stg.Language.C1_0LambdaForm instance GHC.Generics.Datatype Stg.Language.D1LambdaForm instance GHC.Generics.Constructor Stg.Language.C1_0Binds instance GHC.Generics.Datatype Stg.Language.D1Binds instance GHC.Generics.Constructor Stg.Language.C1_0AlgebraicAlt instance GHC.Generics.Datatype Stg.Language.D1AlgebraicAlt instance GHC.Generics.Constructor Stg.Language.C1_0PrimitiveAlt instance GHC.Generics.Datatype Stg.Language.D1PrimitiveAlt instance GHC.Generics.Constructor Stg.Language.C1_2NonDefaultAlts instance GHC.Generics.Constructor Stg.Language.C1_1NonDefaultAlts instance GHC.Generics.Constructor Stg.Language.C1_0NonDefaultAlts instance GHC.Generics.Datatype Stg.Language.D1NonDefaultAlts instance GHC.Generics.Constructor Stg.Language.C1_1DefaultAlt instance GHC.Generics.Constructor Stg.Language.C1_0DefaultAlt instance GHC.Generics.Datatype Stg.Language.D1DefaultAlt instance GHC.Generics.Constructor Stg.Language.C1_0Alts instance GHC.Generics.Datatype Stg.Language.D1Alts instance GHC.Generics.Constructor Stg.Language.C1_5Expr instance GHC.Generics.Constructor Stg.Language.C1_4Expr instance GHC.Generics.Constructor Stg.Language.C1_3Expr instance GHC.Generics.Constructor Stg.Language.C1_2Expr instance GHC.Generics.Constructor Stg.Language.C1_1Expr instance GHC.Generics.Constructor Stg.Language.C1_0Expr instance GHC.Generics.Datatype Stg.Language.D1Expr instance GHC.Generics.Constructor Stg.Language.C1_0Constr instance GHC.Generics.Datatype Stg.Language.D1Constr instance GHC.Generics.Constructor Stg.Language.C1_1Atom instance GHC.Generics.Constructor Stg.Language.C1_0Atom instance GHC.Generics.Datatype Stg.Language.D1Atom instance GHC.Generics.Constructor Stg.Language.C1_0Var instance GHC.Generics.Datatype Stg.Language.D1Var instance GHC.Generics.Constructor Stg.Language.C1_10PrimOp instance GHC.Generics.Constructor Stg.Language.C1_9PrimOp instance GHC.Generics.Constructor Stg.Language.C1_8PrimOp instance GHC.Generics.Constructor Stg.Language.C1_7PrimOp instance GHC.Generics.Constructor Stg.Language.C1_6PrimOp instance GHC.Generics.Constructor Stg.Language.C1_5PrimOp instance GHC.Generics.Constructor Stg.Language.C1_4PrimOp instance GHC.Generics.Constructor Stg.Language.C1_3PrimOp instance GHC.Generics.Constructor Stg.Language.C1_2PrimOp instance GHC.Generics.Constructor Stg.Language.C1_1PrimOp instance GHC.Generics.Constructor Stg.Language.C1_0PrimOp instance GHC.Generics.Datatype Stg.Language.D1PrimOp instance GHC.Generics.Constructor Stg.Language.C1_0Literal instance GHC.Generics.Datatype Stg.Language.D1Literal instance GHC.Generics.Constructor Stg.Language.C1_1Rec instance GHC.Generics.Constructor Stg.Language.C1_0Rec instance GHC.Generics.Datatype Stg.Language.D1Rec instance GHC.Generics.Constructor Stg.Language.C1_1UpdateFlag instance GHC.Generics.Constructor Stg.Language.C1_0UpdateFlag instance GHC.Generics.Datatype Stg.Language.D1UpdateFlag instance GHC.Generics.Generic Stg.Language.Program instance GHC.Show.Show Stg.Language.Program instance GHC.Classes.Ord Stg.Language.Program instance GHC.Classes.Eq Stg.Language.Program instance GHC.Generics.Generic Stg.Language.LambdaForm instance GHC.Show.Show Stg.Language.LambdaForm instance GHC.Classes.Ord Stg.Language.LambdaForm instance GHC.Classes.Eq Stg.Language.LambdaForm instance GHC.Generics.Generic Stg.Language.Binds instance GHC.Classes.Ord Stg.Language.Binds instance GHC.Classes.Eq Stg.Language.Binds instance GHC.Generics.Generic Stg.Language.AlgebraicAlt instance GHC.Show.Show Stg.Language.AlgebraicAlt instance GHC.Classes.Ord Stg.Language.AlgebraicAlt instance GHC.Classes.Eq Stg.Language.AlgebraicAlt instance GHC.Generics.Generic Stg.Language.PrimitiveAlt instance GHC.Show.Show Stg.Language.PrimitiveAlt instance GHC.Classes.Ord Stg.Language.PrimitiveAlt instance GHC.Classes.Eq Stg.Language.PrimitiveAlt instance GHC.Generics.Generic Stg.Language.NonDefaultAlts instance GHC.Show.Show Stg.Language.NonDefaultAlts instance GHC.Classes.Ord Stg.Language.NonDefaultAlts instance GHC.Classes.Eq Stg.Language.NonDefaultAlts instance GHC.Generics.Generic Stg.Language.DefaultAlt instance GHC.Show.Show Stg.Language.DefaultAlt instance GHC.Classes.Ord Stg.Language.DefaultAlt instance GHC.Classes.Eq Stg.Language.DefaultAlt instance GHC.Generics.Generic Stg.Language.Alts instance GHC.Show.Show Stg.Language.Alts instance GHC.Classes.Ord Stg.Language.Alts instance GHC.Classes.Eq Stg.Language.Alts instance GHC.Generics.Generic Stg.Language.Expr instance GHC.Show.Show Stg.Language.Expr instance GHC.Classes.Ord Stg.Language.Expr instance GHC.Classes.Eq Stg.Language.Expr instance GHC.Generics.Generic Stg.Language.Constr instance GHC.Show.Show Stg.Language.Constr instance GHC.Classes.Ord Stg.Language.Constr instance GHC.Classes.Eq Stg.Language.Constr instance GHC.Generics.Generic Stg.Language.Atom instance GHC.Show.Show Stg.Language.Atom instance GHC.Classes.Ord Stg.Language.Atom instance GHC.Classes.Eq Stg.Language.Atom instance GHC.Generics.Generic Stg.Language.Var instance GHC.Show.Show Stg.Language.Var instance GHC.Classes.Ord Stg.Language.Var instance GHC.Classes.Eq Stg.Language.Var instance GHC.Enum.Enum Stg.Language.PrimOp instance GHC.Enum.Bounded Stg.Language.PrimOp instance GHC.Generics.Generic Stg.Language.PrimOp instance GHC.Show.Show Stg.Language.PrimOp instance GHC.Classes.Ord Stg.Language.PrimOp instance GHC.Classes.Eq Stg.Language.PrimOp instance GHC.Generics.Generic Stg.Language.Literal instance GHC.Show.Show Stg.Language.Literal instance GHC.Classes.Ord Stg.Language.Literal instance GHC.Classes.Eq Stg.Language.Literal instance GHC.Enum.Bounded Stg.Language.Rec instance GHC.Enum.Enum Stg.Language.Rec instance GHC.Generics.Generic Stg.Language.Rec instance GHC.Show.Show Stg.Language.Rec instance GHC.Classes.Ord Stg.Language.Rec instance GHC.Classes.Eq Stg.Language.Rec instance GHC.Enum.Bounded Stg.Language.UpdateFlag instance GHC.Enum.Enum Stg.Language.UpdateFlag instance GHC.Generics.Generic Stg.Language.UpdateFlag instance GHC.Show.Show Stg.Language.UpdateFlag instance GHC.Classes.Ord Stg.Language.UpdateFlag instance GHC.Classes.Eq Stg.Language.UpdateFlag instance GHC.Show.Show Stg.Language.LambdaType instance GHC.Classes.Ord Stg.Language.LambdaType instance GHC.Classes.Eq Stg.Language.LambdaType instance GHC.Base.Monoid Stg.Language.Program instance GHC.Base.Monoid Stg.Language.Binds instance GHC.Show.Show Stg.Language.Binds instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Language.LambdaType instance Data.String.IsString Stg.Language.Var instance Data.String.IsString Stg.Language.Constr -- | A parser for the STG language, modeled after the grammar given in the -- description in the 1992 paper (link) with a couple of -- differences to enhance usability: -- -- module Stg.Parser.Parser -- | Parse STG source using a user-specified parser. To parse a full -- program, use parse program. -- -- 
--   >>> parse program "id = \\x -> x"
--   Right (Program (Binds [(Var "id",LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") []))]))
--
parse :: StgParser ast -> Text -> Either Doc ast -- | A parser for an STG syntax element. data StgParser ast -- | Parse an STG program. program :: (Monad parser, TokenParsing parser) => parser Program -- | Parse a collection of bindings, used by let(rec) expressions -- and at the top level of a program. binds :: (Monad parser, TokenParsing parser) => parser Binds -- | Parse a lambda form, consisting of a list of free variables, and -- update flag, a list of bound variables, and the function body. lambdaForm :: (Monad parser, TokenParsing parser) => parser LambdaForm -- | Parse an expression, which can be -- -- expr :: (Monad parser, TokenParsing parser) => parser Expr -- | Parse the alternatives given in a case expression. alts :: (Monad parser, TokenParsing parser) => parser Alts -- | Parse non-default alternatives. The list of alternatives can be either -- empty, all algebraic, or all primitive. -- -- 
--   Nil -> ...
--   Cons x xs -> ...
--
-- -- 
--   1# -> ...
--   2# -> ...
--
nonDefaultAlts :: (Monad parser, TokenParsing parser) => parser NonDefaultAlts -- | Parse a single algebraic alternative. -- -- 
--   Cons x xs -> ...
--
algebraicAlt :: (Monad parser, TokenParsing parser) => parser AlgebraicAlt -- | Parse a single primitive alternative, such as 1#. -- -- 
--   1# -> ...
--
primitiveAlt :: (Monad parser, TokenParsing parser) => parser PrimitiveAlt -- | Parse the default alternative, taken if none of the other alternatives -- in a case expression match. -- -- 
--   default -> ...
--
-- -- 
--   v -> ...
--
defaultAlt :: (Monad parser, TokenParsing parser) => parser DefaultAlt literal :: TokenParsing parser => parser Literal -- | Parse a primitive operation. -- -- 
--   +#
--
primOp :: TokenParsing parser => parser PrimOp atom :: (Monad parser, TokenParsing parser) => parser Atom -- | Parse a variable identifier. Variables start with a lower-case letter -- or _, followed by a string consisting of alphanumeric -- characters or ', _. var :: (Monad parser, TokenParsing parser) => parser Var -- | Parse a constructor identifier. Constructors follow the same naming -- conventions as variables, but start with an upper-case character -- instead, and may end with a # symbol. con :: (Monad parser, TokenParsing parser) => parser Constr instance GHC.Base.Monad Stg.Parser.Parser.StgParser instance GHC.Base.Functor Stg.Parser.Parser.StgParser instance GHC.Base.Applicative Stg.Parser.Parser.StgParser instance GHC.Base.Alternative Stg.Parser.Parser.StgParser instance Text.Parser.Combinators.Parsing Stg.Parser.Parser.StgParser instance Text.Parser.Char.CharParsing Stg.Parser.Parser.StgParser instance Text.Parser.Token.TokenParsing Stg.Parser.Parser.StgParser -- | Quasiquoters for easier generation of STG syntax trees. The stg -- quoter is most convenient, I suggest you use it unless you have a -- reason not to. module Stg.Parser.QuasiQuoter -- | Heuristic quasiquoter for STG language elements. Tries a number of -- parsers, and will use the first successful one. -- -- To gain more fine-grained control over what the input should be parsed -- to, use one of the non-heuristic quoters, such as stgProgram -- or stgLambdaForm. These will also give you much better error -- messages than merely "doesn't work". -- -- 
--   >>> [stg| id = \x -> x |]
--   Program (Binds [(Var "id",LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") []))])
--
-- -- 
--   >>> [stg| \x -> x |]
--   LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") [])
--
-- -- 
--   >>> [stg| x |]
--   AppF (Var "x") []
--
stg :: QuasiQuoter -- | Quasiquoter for Programs. -- -- 
--   >>> [program| id = \x -> x |]
--   Program (Binds [(Var "id",LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") []))])
--
program :: QuasiQuoter -- | Quasiquoter for Binds. -- -- 
--   >>> [binds| id = \x -> x |]
--   (Binds [(Var "id",LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") []))])
--
binds :: QuasiQuoter -- | Quasiquoter for LambdaForms. -- -- 
--   >>> [lambdaForm| \x -> x |]
--   LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") [])
--
lambdaForm :: QuasiQuoter -- | Quasiquoter for Expressions. -- -- 
--   >>> [expr| f x y z |]
--   AppF (Var "f") [AtomVar (Var "x"),AtomVar (Var "y"),AtomVar (Var "z")]
--
expr :: QuasiQuoter -- | Quasiquoter for Alts. -- -- 
--   >>> [alts| Just x -> True; default -> False |]
--   Alts (AlgebraicAlts (AlgebraicAlt (Constr "Just") [Var "x"] (AppC (Constr "True") []) :| [])) (DefaultNotBound (AppC (Constr "False") []))
--
-- -- 
--   >>> [alts| 0# -> True; default -> False |]
--   Alts (PrimitiveAlts (PrimitiveAlt (Literal 0) (AppC (Constr "True") []) :| [])) (DefaultNotBound (AppC (Constr "False") []))
--
alts :: QuasiQuoter -- | Quasiquoter for Alt. -- -- 
--   >>> [nonDefaultAlts| Just x -> True; Nothing -> False; |]
--   AlgebraicAlts (AlgebraicAlt (Constr "Just") [Var "x"] (AppC (Constr "True") []) :| [AlgebraicAlt (Constr "Nothing") [] (AppC (Constr "False") [])])
--
-- -- 
--   >>> [nonDefaultAlts| 0# -> False; 1# -> True; |]
--   PrimitiveAlts (PrimitiveAlt (Literal 0) (AppC (Constr "False") []) :| [PrimitiveAlt (Literal 1) (AppC (Constr "True") [])])
--
nonDefaultAlts :: QuasiQuoter -- | Quasiquoter for AlgebraicAlts. -- -- 
--   >>> [algebraicAlt| Just x -> x; |]
--   AlgebraicAlt (Constr "Just") [Var "x"] (AppF (Var "x") [])
--
algebraicAlt :: QuasiQuoter -- | Quasiquoter for PrimitiveAlts. -- -- 
--   >>> [primitiveAlt| 1# -> x; |]
--   PrimitiveAlt (Literal 1) (AppF (Var "x") [])
--
primitiveAlt :: QuasiQuoter -- | Quasiquoter for DefaultAlts. -- -- 
--   >>> [defaultAlt| default -> x |]
--   DefaultNotBound (AppF (Var "x") [])
--
-- -- 
--   >>> [defaultAlt| x -> x |]
--   DefaultBound (Var "x") (AppF (Var "x") [])
--
defaultAlt :: QuasiQuoter -- | Quasiquoter for Literals. -- -- 
--   >>> [literal| 1# |]
--   Literal 1
--
literal :: QuasiQuoter -- | Quasiquoter for PrimOps. -- -- 
--   >>> [primOp| +# |]
--   Add
--
primOp :: QuasiQuoter -- | Quasiquoter for Atoms. -- -- 
--   >>> [atom| x |]
--   AtomVar (Var "x")
--
atom :: QuasiQuoter module Stg.Prelude.Maybe -- | Nothing as a top-level closure. -- -- 
--   nothing : Maybe a
--
nothing :: Program -- | Deconstructor of the Maybe type. -- -- 
--   maybe : b -> (a -> b) -> Maybe a -> b
--
maybe :: Program -- | Boolean functions, like in Data.Bool. module Stg.Prelude.Bool -- | Binary and. Haskell's (&&). -- -- 
--   && : Bool -> Bool -> Bool
--
and2 :: Program -- | Binary or. Haskell's (||). -- -- 
--   || : Bool -> Bool -> Bool
--
or2 :: Program -- | Binary negation. -- -- 
--   not : Bool -> Bool
--
not :: Program -- | Boolean deconstructor. -- -- 
--   bool f _ False = f
--   bool _ t True  = t
--
-- -- 
--   bool : a -> a -> Bool -> a
--
bool :: Program -- | Boolean equality. eq_Bool :: Program module Stg.Prelude.Function -- | Finally I can define seq directly! :-) -- -- Note that this function is less powerful than GHC's seq, since -- STG does not have a rule to force functions, only expressions that -- reduce to an algebraic or primitive value. This leads to the fact that -- STG's seq is less powerful than Haskell's, since in Haskell -- -- 
--   seq (const ()) () = ()
--
-- -- whereas in the STG -- -- 
--   constUnit = (x) -> Unit ();
--   seq (constUnit, Unit) = ERROR
--
seq :: Program -- | Identity function. -- -- 
--   id : a -> a
--
id :: Program -- | Constant function. -- -- 
--   Const : a -> b -> a
--
const :: Program -- | Function composition. -- -- 
--   compose : (b -> c) -> (a -> b) -> a -> c
--
compose :: Program -- | The fixed point combinator. -- -- 
--   fix : (a -> a) -> a
--
fix :: Program module Stg.Prelude.Number add :: Program sub :: Program mul :: Program div :: Program mod :: Program eq_Int :: Program lt_Int :: Program leq_Int :: Program gt_Int :: Program geq_Int :: Program neq_Int :: Program min :: Program max :: Program module Stg.Prelude.List -- | The empty list as a top-level closure. -- -- 
--   nil : [a]
--
nil :: Program -- | Concatenate two lists. Haskell's (++). -- -- 
--   concat2 : [a] -> [a] -> [a]
--
concat2 :: Program -- | reverse a list. -- -- 
--   reverse [1,2,3] = [3,2,1]
--
-- -- 
--   reverse : [a] -> [a]
--
reverse :: Program -- | Lazy left list fold. Provided mostly for seeing how it causes stack -- overflows. -- -- 
--   foldl : (b -> a -> b) -> b -> [a] -> b
--
foldl :: Program -- | Strict left list fold. -- -- Careful: the STG only supports primitive and algebraic case -- scrutinees. As a result, you can only hand primitive or algebraic -- b values to this function or it will fail! -- -- 
--   foldl' : (b -> a -> b) -> b -> [a] -> b
--
foldl' :: Program -- | Right list fold. -- -- 
--   foldr : (a -> b -> b) -> b -> [a] -> b
--
foldr :: Program -- | Build a list by repeatedly applying a function to an initial value. -- -- 
--   iterate f x = [x, f x, f (f x), ...]
--
-- -- 
--   iterate : (a -> a) -> a -> [a]
--
iterate :: Program -- | Infinite list created by repeating an initial (non-empty) list. -- -- 
--   cycle [x,y,z] = [x,y,z, x,y,z, x,y,z, ...]
--
-- -- 
--   cycle : [a] -> [a]
--
cycle :: Program -- | Take n elements form the beginning of a list. -- -- 
--   take 3 [1..] = [1,2,3]
--
-- -- 
--   take : Int -> [a] -> [a]
--
take :: Program -- | Keep only the elements for which a predicate holds. -- -- 
--   filter even [1..] = [2, 4, 6, ...]
--
-- -- 
--   filter : (a -> Bool) -> [a] -> [a]
--
filter :: Program -- | Repeat a single element infinitely. -- -- 
--   repeat 1 = [1, 1, 1, ...]
--
-- -- 
--   repeat : a -> [a]
--
repeat :: Program -- | Repeat a single element a number of times. -- -- 
--   replicate 3 1 = [1, 1, 1]
--
-- -- 
--   replicate : Int -> a -> [a]
--
replicate :: Program -- | Haskell's Prelude sort function at the time of implementing this. Not -- quite as pretty as the Haskell version, but functionally equivalent. -- :-) -- -- This implementation is particularly efficient when the input contains -- runs of already sorted elements. For comparison, sorting [1..100] -- takes 6496 steps, whereas naiveSort requires 268082. -- -- 
--   sort : [Int] -> [Int]
--
sort :: Program -- | That Haskell sort function often misleadingly referred to as -- "quicksort". -- -- 
--   naiveSort : [Int] -> [Int]
--
naiveSort :: Program -- | Apply a function to each element of a list. -- -- 
--   map : (a -> b) -> [a] -> [b]
--
map :: Program -- | Equality of lists of integers. -- -- 
--   equals_List_Int : [Int] -> [Int] -> Bool
--
equals_List_Int :: Program -- | Length of a list. -- -- 
--   length : [a] -> Int
--
length :: Program -- | Zip two lists into one. If one list is longer than the other ignore -- the exceeding elements. -- -- 
--   zip [1,2,3,4,5] [10,20,30] ==> [(1,10),(2,20),(3,30)]
--   
--   zip xs ys = zipWith Pair xs ys
--
-- -- 
--   zip : [a] -> [b] -> [(a,b)]
--
zip :: Program -- | Zip two lists into one using a user-specified combining function. If -- one list is longer than the other ignore the exceeding elements. -- -- 
--   zipWith (+) [1,2,3,4,5] [10,20,30] ==> [11,22,33]
--   
--   zipWith f xs ys = map f (zip xs ys)
--
-- -- 
--   zipWith : (a -> b -> c) -> [a] -> [b] -> [c]
--
zipWith :: Program -- | Force the spine of a list. -- -- 
--   forceSpine :: [a] -> [a]
--
forceSpine :: Program -- | Convert Haskell values to STG values. module Stg.Marshal.ToStg -- | Convert a Haskell value to an STG binding. -- -- Instances of this class should have a corresponding FromStg -- instance to retrieve a value fom the program, with the two being -- inverse to each other (up to forcing the generated thunks). -- -- This class contains a helper function, toStgWithGlobals, this -- is hidden from the outside. If you want to write your own instance, -- have a look at the source for documentation. class ToStg value where toStg var val = let (globals, actualDef) = runWriter (toStgWithGlobals var val) in globals <> actualDef toStgWithGlobals var val = pure (toStg var val) toStg :: ToStg value => Var -> value -> Program -- | Some definitions, such as the one for lists, require certain global -- values to be present (such as nil). In order to avoid duplicate -- definitions, this function allows defining top-level elements using -- Writers tell function. toStgWithGlobals :: ToStg value => Var -> value -> Writer Program Program instance Stg.Marshal.ToStg.ToStg () instance Stg.Marshal.ToStg.ToStg GHC.Integer.Type.Integer instance Stg.Marshal.ToStg.ToStg GHC.Types.Int instance Stg.Marshal.ToStg.ToStg GHC.Types.Bool instance Stg.Marshal.ToStg.ToStg a => Stg.Marshal.ToStg.ToStg (GHC.Base.Maybe a) instance (Stg.Marshal.ToStg.ToStg a, Stg.Marshal.ToStg.ToStg b) => Stg.Marshal.ToStg.ToStg (Data.Either.Either a b) instance Stg.Marshal.ToStg.ToStg a => Stg.Marshal.ToStg.ToStg [a] instance (Stg.Marshal.ToStg.ToStg a, Stg.Marshal.ToStg.ToStg b) => Stg.Marshal.ToStg.ToStg (a, b) instance (Stg.Marshal.ToStg.ToStg a, Stg.Marshal.ToStg.ToStg b, Stg.Marshal.ToStg.ToStg c) => Stg.Marshal.ToStg.ToStg (a, b, c) instance (Stg.Marshal.ToStg.ToStg a, Stg.Marshal.ToStg.ToStg b, Stg.Marshal.ToStg.ToStg c, Stg.Marshal.ToStg.ToStg d) => Stg.Marshal.ToStg.ToStg (a, b, c, d) instance (Stg.Marshal.ToStg.ToStg a, Stg.Marshal.ToStg.ToStg b, Stg.Marshal.ToStg.ToStg c, Stg.Marshal.ToStg.ToStg d, Stg.Marshal.ToStg.ToStg e) => Stg.Marshal.ToStg.ToStg (a, b, c, d, e) module Stg.Prelude.Tuple -- | First element of a tuple. -- -- 
--   fst : (a,b) -> a
--
fst :: Program -- | Second element of a tuple. -- -- 
--   snd : (a,b) -> a
--
snd :: Program -- | Convert an uncurried function to a curried one. -- -- 
--   curry : ((a, b) -> c) -> a -> b -> c
--
curry :: Program -- | Convert a curried function to an uncurried one. -- -- 
--   uncurry : (a -> b -> c) -> (a, b) -> c
--
uncurry :: Program -- | Swap the elements of a tuple. -- -- 
--   swap : (a,b) -> (b,a)
--
swap :: Program equals_Pair_Int :: Program -- | Common Haskell functions, translated to STG. Use the Monoid -- instance for Program to mix them. -- -- This module should be imported qualified, since it heavily conflicts -- with the standard Haskell Prelude. module Stg.Prelude -- | Deconstructor of the Maybe type. -- -- 
--   maybe : b -> (a -> b) -> Maybe a -> b
--
maybe :: Program -- | Nothing as a top-level closure. -- -- 
--   nothing : Maybe a
--
nothing :: Program -- | The empty list as a top-level closure. -- -- 
--   nil : [a]
--
nil :: Program -- | Concatenate two lists. Haskell's (++). -- -- 
--   concat2 : [a] -> [a] -> [a]
--
concat2 :: Program -- | reverse a list. -- -- 
--   reverse [1,2,3] = [3,2,1]
--
-- -- 
--   reverse : [a] -> [a]
--
reverse :: Program -- | Lazy left list fold. Provided mostly for seeing how it causes stack -- overflows. -- -- 
--   foldl : (b -> a -> b) -> b -> [a] -> b
--
foldl :: Program -- | Strict left list fold. -- -- Careful: the STG only supports primitive and algebraic case -- scrutinees. As a result, you can only hand primitive or algebraic -- b values to this function or it will fail! -- -- 
--   foldl' : (b -> a -> b) -> b -> [a] -> b
--
foldl' :: Program -- | Right list fold. -- -- 
--   foldr : (a -> b -> b) -> b -> [a] -> b
--
foldr :: Program -- | Build a list by repeatedly applying a function to an initial value. -- -- 
--   iterate f x = [x, f x, f (f x), ...]
--
-- -- 
--   iterate : (a -> a) -> a -> [a]
--
iterate :: Program -- | Infinite list created by repeating an initial (non-empty) list. -- -- 
--   cycle [x,y,z] = [x,y,z, x,y,z, x,y,z, ...]
--
-- -- 
--   cycle : [a] -> [a]
--
cycle :: Program -- | Take n elements form the beginning of a list. -- -- 
--   take 3 [1..] = [1,2,3]
--
-- -- 
--   take : Int -> [a] -> [a]
--
take :: Program -- | Keep only the elements for which a predicate holds. -- -- 
--   filter even [1..] = [2, 4, 6, ...]
--
-- -- 
--   filter : (a -> Bool) -> [a] -> [a]
--
filter :: Program -- | Repeat a single element infinitely. -- -- 
--   repeat 1 = [1, 1, 1, ...]
--
-- -- 
--   repeat : a -> [a]
--
repeat :: Program -- | Repeat a single element a number of times. -- -- 
--   replicate 3 1 = [1, 1, 1]
--
-- -- 
--   replicate : Int -> a -> [a]
--
replicate :: Program -- | Haskell's Prelude sort function at the time of implementing this. Not -- quite as pretty as the Haskell version, but functionally equivalent. -- :-) -- -- This implementation is particularly efficient when the input contains -- runs of already sorted elements. For comparison, sorting [1..100] -- takes 6496 steps, whereas naiveSort requires 268082. -- -- 
--   sort : [Int] -> [Int]
--
sort :: Program -- | That Haskell sort function often misleadingly referred to as -- "quicksort". -- -- 
--   naiveSort : [Int] -> [Int]
--
naiveSort :: Program -- | Apply a function to each element of a list. -- -- 
--   map : (a -> b) -> [a] -> [b]
--
map :: Program -- | Length of a list. -- -- 
--   length : [a] -> Int
--
length :: Program -- | Zip two lists into one. If one list is longer than the other ignore -- the exceeding elements. -- -- 
--   zip [1,2,3,4,5] [10,20,30] ==> [(1,10),(2,20),(3,30)]
--   
--   zip xs ys = zipWith Pair xs ys
--
-- -- 
--   zip : [a] -> [b] -> [(a,b)]
--
zip :: Program -- | Zip two lists into one using a user-specified combining function. If -- one list is longer than the other ignore the exceeding elements. -- -- 
--   zipWith (+) [1,2,3,4,5] [10,20,30] ==> [11,22,33]
--   
--   zipWith f xs ys = map f (zip xs ys)
--
-- -- 
--   zipWith : (a -> b -> c) -> [a] -> [b] -> [c]
--
zipWith :: Program -- | Force the spine of a list. -- -- 
--   forceSpine :: [a] -> [a]
--
forceSpine :: Program -- | Equality of lists of integers. -- -- 
--   equals_List_Int : [Int] -> [Int] -> Bool
--
equals_List_Int :: Program -- | First element of a tuple. -- -- 
--   fst : (a,b) -> a
--
fst :: Program -- | Second element of a tuple. -- -- 
--   snd : (a,b) -> a
--
snd :: Program -- | Convert an uncurried function to a curried one. -- -- 
--   curry : ((a, b) -> c) -> a -> b -> c
--
curry :: Program -- | Convert a curried function to an uncurried one. -- -- 
--   uncurry : (a -> b -> c) -> (a, b) -> c
--
uncurry :: Program -- | Swap the elements of a tuple. -- -- 
--   swap : (a,b) -> (b,a)
--
swap :: Program equals_Pair_Int :: Program -- | Binary and. Haskell's (&&). -- -- 
--   && : Bool -> Bool -> Bool
--
and2 :: Program -- | Binary or. Haskell's (||). -- -- 
--   || : Bool -> Bool -> Bool
--
or2 :: Program -- | Binary negation. -- -- 
--   not : Bool -> Bool
--
not :: Program -- | Boolean deconstructor. -- -- 
--   bool f _ False = f
--   bool _ t True  = t
--
-- -- 
--   bool : a -> a -> Bool -> a
--
bool :: Program -- | Boolean equality. eq_Bool :: Program add :: Program sub :: Program mul :: Program div :: Program mod :: Program eq_Int :: Program lt_Int :: Program leq_Int :: Program gt_Int :: Program geq_Int :: Program neq_Int :: Program min :: Program max :: Program -- | Finally I can define seq directly! :-) -- -- Note that this function is less powerful than GHC's seq, since -- STG does not have a rule to force functions, only expressions that -- reduce to an algebraic or primitive value. This leads to the fact that -- STG's seq is less powerful than Haskell's, since in Haskell -- -- 
--   seq (const ()) () = ()
--
-- -- whereas in the STG -- -- 
--   constUnit = (x) -> Unit ();
--   seq (constUnit, Unit) = ERROR
--
seq :: Program -- | Identity function. -- -- 
--   id : a -> a
--
id :: Program -- | Constant function. -- -- 
--   Const : a -> b -> a
--
const :: Program -- | Function composition. -- -- 
--   compose : (b -> c) -> (a -> b) -> a -> c
--
compose :: Program -- | The fixed point combinator. -- -- 
--   fix : (a -> a) -> a
--
fix :: Program -- | Force a value to normal form and return it. -- -- This function makes heavy use of the fact that the STG is untyped. It -- currently supports the following types: -- -- -- -- Everything else will run into an error. force :: Program -- | A simple stack type. Very similar to an ordinary list, but with a more -- specialized API. module Data.Stack -- | The usual stack data structure. data Stack a Empty :: Stack a (:<) :: a -> Stack a -> Stack a -- | For each list element, pop one element off the stack. Fail if not -- enough elements are on the stack. forEachPop :: [x] -> Stack a -> Maybe ([a], Stack a) -- | Push a list of items onto the stack. The first item will be at the top -- of the stack. (<>>) :: [a] -> Stack a -> Stack a -- | Like span for lists. span :: (a -> Bool) -> Stack a -> (Stack a, Stack a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Stack.Stack a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Stack.Stack a) instance GHC.Show.Show a => GHC.Show.Show (Data.Stack.Stack a) instance Text.PrettyPrint.ANSI.Leijen.Pretty a => Text.PrettyPrint.ANSI.Leijen.Pretty (Data.Stack.Stack a) instance GHC.Base.Functor Data.Stack.Stack instance Data.Foldable.Foldable Data.Stack.Stack instance GHC.Base.Monoid (Data.Stack.Stack a) instance GHC.Exts.IsList (Data.Stack.Stack a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Stack.Stack a) -- | Types used in the execution of the STG machine. module Stg.Machine.Types -- | The internal state of an STG. data StgState StgState :: Code -> Stack StackFrame -> Heap -> Globals -> !Integer -> Info -> StgState -- | Operation the STG should perform next [stgCode] :: StgState -> Code -- | The stack stores not-yet-used arguments (argument stack part), -- computations to return to once case evaluation has finished (return -- stack part), and instructions to update heap entries once computation -- of a certain value is done. [stgStack] :: StgState -> Stack StackFrame -- | The heap stores values allocated at the top level or in -- let(rec) expressions. [stgHeap] :: StgState -> Heap -- | The environment consisting of the top-level definitions. [stgGlobals] :: StgState -> Globals -- | A counter, used to generte fresh variable names from. [stgSteps] :: StgState -> !Integer -- | Information about the current state [stgInfo] :: StgState -> Info -- | Package of style definitions used in this module. data StgStateStyle StgStateStyle :: (Doc -> Doc) -> (Doc -> Doc) -> (Doc -> Doc) -> (Doc -> Doc) -> (Doc -> Doc) -> StgStateStyle -- | Style of headlines in the state overview, such as "Heap" and "Frame -- i". [headline] :: StgStateStyle -> Doc -> Doc -- | Style of memory addresses, including 0x prefix. [address] :: StgStateStyle -> Doc -> Doc -- | Style of memory addresses; applied only to the actual address number, -- such as ff in 0xff. [addressCore] :: StgStateStyle -> Doc -> Doc -- | Style of the type of a closure, such as BLACKHOLE or FUN. [closureType] :: StgStateStyle -> Doc -> Doc -- | Style of the stack frame annotation, such as UPD or ARG. [stackFrameType] :: StgStateStyle -> Doc -> Doc data StackFrame -- | Argument frames store values on the argument stack, so that they can -- later be retrieved when the calling function can be applied to them. ArgumentFrame :: Value -> StackFrame -- | Return frames are used when the scrutinee of a case expression is done -- being evaluated, and the branch to continue on has to be decided. ReturnFrame :: Alts -> Locals -> StackFrame -- | When an updatable closure is entered, an update frame with its heap -- address is created. Once its computation finishes, its heap entry is -- updated with the computed value. UpdateFrame :: MemAddr -> StackFrame -- | A memory address. newtype MemAddr MemAddr :: Int -> MemAddr -- | A value of the STG machine. data Value Addr :: MemAddr -> Value PrimInt :: Integer -> Value -- | The different code states the STG can be in. data Code -- | Evaluate an expression within a local environment Eval :: Expr -> Locals -> Code -- | Load the closure at a certain heap address Enter :: MemAddr -> Code -- | Sub-computation terminated with algebraic constructor ReturnCon :: Constr -> [Value] -> Code -- | Sub-computation terminated with a primitive integer ReturnInt :: Integer -> Code -- | A single key -> value association. data Mapping k v Mapping :: k -> v -> Mapping k v -- | The global environment consists of the mapping from top-level -- definitions to their respective values. newtype Globals Globals :: (Map Var Value) -> Globals -- | The global environment consists if the mapping from local definitions -- to their respective values. newtype Locals Locals :: (Map Var Value) -> Locals -- | A closure is a lambda form, together with the values of its free -- variables. data Closure Closure :: LambdaForm -> [Value] -> Closure -- | The heap stores closures addressed by memory location. newtype Heap Heap :: (Map MemAddr HeapObject) -> Heap data HeapObject HClosure :: Closure -> HeapObject -- | When an updatable closure is entered, it is overwritten by a black -- hole. This has two main benefits: -- --
    --
  1. Memory mentioned only in the closure is now ready to be collected, -- avoiding certain space leaks.
    2. --
  2. Entering a black hole means a thunk depends on itself, allowing -- the interpreter to catch some non-terminating computations with a -- useful error
    3. --
-- -- To make the black hole a bit more transparent, it is tagged with the -- STG tick in which it was introduced. This tag is used only for display -- purposes. Blackhole :: Integer -> HeapObject -- | User-facing information about the current state of the STG. data Info Info :: InfoShort -> [InfoDetail] -> Info -- | Short machine status info. This field may be used programmatically, in -- particular it tells the stepper whether the machine has halted. data InfoShort -- | There is no valid state transition to continue with. NoRulesApply :: InfoShort -- | The machine did not halt within a number of steps. Used by -- evalUntil. MaxStepsExceeded :: InfoShort -- | The machine halted because a user-specified halting predicate held. HaltedByPredicate :: InfoShort -- | The machine halted in a state that is known to be invalid, there is no -- valid state transition to continue with. -- -- An example of this would be a ReturnCon state with an empty -- return stack. StateError :: StateError -> InfoShort -- | Description of the state transition that lead to the current state. StateTransition :: StateTransition -> InfoShort -- | Used to mark the initial state of the machine. StateInitial :: InfoShort -- | A garbage collection step, in which no ordinary evaluation is done. GarbageCollection :: InfoShort data InfoDetail Detail_FunctionApplication :: Var -> [Atom] -> InfoDetail Detail_UnusedLocalVariables :: [Var] -> Locals -> InfoDetail Detail_EnterNonUpdatable :: MemAddr -> [Mapping Var Value] -> InfoDetail Detail_EvalLet :: [Var] -> [MemAddr] -> InfoDetail Detail_EvalCase :: InfoDetail Detail_ReturnCon_Match :: Constr -> [Var] -> InfoDetail Detail_ReturnConDefBound :: Var -> MemAddr -> InfoDetail Detail_ReturnIntDefBound :: Var -> Integer -> InfoDetail Detail_EnterUpdatable :: MemAddr -> InfoDetail Detail_ConUpdate :: Constr -> MemAddr -> InfoDetail Detail_PapUpdate :: MemAddr -> InfoDetail Detail_ReturnIntCannotUpdate :: InfoDetail Detail_StackNotEmpty :: InfoDetail Detail_GarbageCollected :: Text -> (Set MemAddr) -> (Map MemAddr MemAddr) -> InfoDetail Detail_EnterBlackHole :: MemAddr -> Integer -> InfoDetail Detail_UpdateClosureWithPrimitive :: InfoDetail Detail_BadConArity :: InfoDetail data StateTransition Enter_NonUpdatableClosure :: StateTransition Enter_PartiallyAppliedUpdate :: StateTransition Enter_UpdatableClosure :: StateTransition Eval_AppC :: StateTransition Eval_AppP :: StateTransition Eval_Case :: StateTransition Eval_Case_Primop_Normal :: StateTransition Eval_Case_Primop_DefaultBound :: StateTransition Eval_FunctionApplication :: StateTransition Eval_Let :: Rec -> StateTransition Eval_Lit :: StateTransition Eval_LitApp :: StateTransition ReturnCon_DefBound :: StateTransition ReturnCon_DefUnbound :: StateTransition ReturnCon_Match :: StateTransition ReturnCon_Update :: StateTransition ReturnInt_DefBound :: StateTransition ReturnInt_DefUnbound :: StateTransition ReturnInt_Match :: StateTransition data StateError VariablesNotInScope :: NotInScope -> StateError UpdatableClosureWithArgs :: StateError ReturnIntWithEmptyReturnStack :: StateError AlgReturnToPrimAlts :: StateError PrimReturnToAlgAlts :: StateError InitialStateCreationFailed :: StateError EnterBlackhole :: StateError UpdateClosureWithPrimitive :: StateError NonAlgPrimScrutinee :: StateError DivisionByZero :: StateError BadConArity :: Int -> Int -> StateError -- | Type safety wrapper. newtype NotInScope NotInScope :: [Var] -> NotInScope instance GHC.Generics.Selector Stg.Machine.Types.S1_0_5StgState instance GHC.Generics.Selector Stg.Machine.Types.S1_0_4StgState instance GHC.Generics.Selector Stg.Machine.Types.S1_0_3StgState instance GHC.Generics.Selector Stg.Machine.Types.S1_0_2StgState instance GHC.Generics.Selector Stg.Machine.Types.S1_0_1StgState instance GHC.Generics.Selector Stg.Machine.Types.S1_0_0StgState instance GHC.Generics.Constructor Stg.Machine.Types.C1_0StgState instance GHC.Generics.Datatype Stg.Machine.Types.D1StgState instance GHC.Generics.Constructor Stg.Machine.Types.C1_0Heap instance GHC.Generics.Datatype Stg.Machine.Types.D1Heap instance GHC.Generics.Constructor Stg.Machine.Types.C1_1HeapObject instance GHC.Generics.Constructor Stg.Machine.Types.C1_0HeapObject instance GHC.Generics.Datatype Stg.Machine.Types.D1HeapObject instance GHC.Generics.Constructor Stg.Machine.Types.C1_0Closure instance GHC.Generics.Datatype Stg.Machine.Types.D1Closure instance GHC.Generics.Constructor Stg.Machine.Types.C1_0Info instance GHC.Generics.Datatype Stg.Machine.Types.D1Info instance GHC.Generics.Constructor Stg.Machine.Types.C1_16InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_15InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_14InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_13InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_12InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_11InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_10InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_9InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_8InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_7InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_6InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_5InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_4InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_3InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_2InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_1InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_0InfoDetail instance GHC.Generics.Datatype Stg.Machine.Types.D1InfoDetail instance GHC.Generics.Constructor Stg.Machine.Types.C1_6InfoShort instance GHC.Generics.Constructor Stg.Machine.Types.C1_5InfoShort instance GHC.Generics.Constructor Stg.Machine.Types.C1_4InfoShort instance GHC.Generics.Constructor Stg.Machine.Types.C1_3InfoShort instance GHC.Generics.Constructor Stg.Machine.Types.C1_2InfoShort instance GHC.Generics.Constructor Stg.Machine.Types.C1_1InfoShort instance GHC.Generics.Constructor Stg.Machine.Types.C1_0InfoShort instance GHC.Generics.Datatype Stg.Machine.Types.D1InfoShort instance GHC.Generics.Constructor Stg.Machine.Types.C1_10StateError instance GHC.Generics.Constructor Stg.Machine.Types.C1_9StateError instance GHC.Generics.Constructor Stg.Machine.Types.C1_8StateError instance GHC.Generics.Constructor Stg.Machine.Types.C1_7StateError instance GHC.Generics.Constructor Stg.Machine.Types.C1_6StateError instance GHC.Generics.Constructor Stg.Machine.Types.C1_5StateError instance GHC.Generics.Constructor Stg.Machine.Types.C1_4StateError instance GHC.Generics.Constructor Stg.Machine.Types.C1_3StateError instance GHC.Generics.Constructor Stg.Machine.Types.C1_2StateError instance GHC.Generics.Constructor Stg.Machine.Types.C1_1StateError instance GHC.Generics.Constructor Stg.Machine.Types.C1_0StateError instance GHC.Generics.Datatype Stg.Machine.Types.D1StateError instance GHC.Generics.Constructor Stg.Machine.Types.C1_0NotInScope instance GHC.Generics.Datatype Stg.Machine.Types.D1NotInScope instance GHC.Generics.Constructor Stg.Machine.Types.C1_18StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_17StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_16StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_15StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_14StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_13StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_12StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_11StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_10StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_9StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_8StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_7StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_6StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_5StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_4StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_3StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_2StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_1StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_0StateTransition instance GHC.Generics.Datatype Stg.Machine.Types.D1StateTransition instance GHC.Generics.Constructor Stg.Machine.Types.C1_2StackFrame instance GHC.Generics.Constructor Stg.Machine.Types.C1_1StackFrame instance GHC.Generics.Constructor Stg.Machine.Types.C1_0StackFrame instance GHC.Generics.Datatype Stg.Machine.Types.D1StackFrame instance GHC.Generics.Constructor Stg.Machine.Types.C1_3Code instance GHC.Generics.Constructor Stg.Machine.Types.C1_2Code instance GHC.Generics.Constructor Stg.Machine.Types.C1_1Code instance GHC.Generics.Constructor Stg.Machine.Types.C1_0Code instance GHC.Generics.Datatype Stg.Machine.Types.D1Code instance GHC.Generics.Constructor Stg.Machine.Types.C1_0Locals instance GHC.Generics.Datatype Stg.Machine.Types.D1Locals instance GHC.Generics.Constructor Stg.Machine.Types.C1_0Globals instance GHC.Generics.Datatype Stg.Machine.Types.D1Globals instance GHC.Generics.Constructor Stg.Machine.Types.C1_0Mapping instance GHC.Generics.Datatype Stg.Machine.Types.D1Mapping instance GHC.Generics.Constructor Stg.Machine.Types.C1_1Value instance GHC.Generics.Constructor Stg.Machine.Types.C1_0Value instance GHC.Generics.Datatype Stg.Machine.Types.D1Value instance GHC.Generics.Constructor Stg.Machine.Types.C1_0MemAddr instance GHC.Generics.Datatype Stg.Machine.Types.D1MemAddr instance GHC.Generics.Generic Stg.Machine.Types.StgState instance GHC.Show.Show Stg.Machine.Types.StgState instance GHC.Classes.Ord Stg.Machine.Types.StgState instance GHC.Classes.Eq Stg.Machine.Types.StgState instance GHC.Base.Monoid Stg.Machine.Types.Heap instance GHC.Generics.Generic Stg.Machine.Types.Heap instance GHC.Show.Show Stg.Machine.Types.Heap instance GHC.Classes.Ord Stg.Machine.Types.Heap instance GHC.Classes.Eq Stg.Machine.Types.Heap instance GHC.Generics.Generic Stg.Machine.Types.HeapObject instance GHC.Show.Show Stg.Machine.Types.HeapObject instance GHC.Classes.Ord Stg.Machine.Types.HeapObject instance GHC.Classes.Eq Stg.Machine.Types.HeapObject instance GHC.Generics.Generic Stg.Machine.Types.Closure instance GHC.Show.Show Stg.Machine.Types.Closure instance GHC.Classes.Ord Stg.Machine.Types.Closure instance GHC.Classes.Eq Stg.Machine.Types.Closure instance GHC.Generics.Generic Stg.Machine.Types.Info instance GHC.Show.Show Stg.Machine.Types.Info instance GHC.Classes.Ord Stg.Machine.Types.Info instance GHC.Classes.Eq Stg.Machine.Types.Info instance GHC.Generics.Generic Stg.Machine.Types.InfoDetail instance GHC.Show.Show Stg.Machine.Types.InfoDetail instance GHC.Classes.Ord Stg.Machine.Types.InfoDetail instance GHC.Classes.Eq Stg.Machine.Types.InfoDetail instance GHC.Generics.Generic Stg.Machine.Types.InfoShort instance GHC.Show.Show Stg.Machine.Types.InfoShort instance GHC.Classes.Ord Stg.Machine.Types.InfoShort instance GHC.Classes.Eq Stg.Machine.Types.InfoShort instance GHC.Generics.Generic Stg.Machine.Types.StateError instance GHC.Show.Show Stg.Machine.Types.StateError instance GHC.Classes.Ord Stg.Machine.Types.StateError instance GHC.Classes.Eq Stg.Machine.Types.StateError instance GHC.Base.Monoid Stg.Machine.Types.NotInScope instance GHC.Generics.Generic Stg.Machine.Types.NotInScope instance GHC.Show.Show Stg.Machine.Types.NotInScope instance GHC.Classes.Ord Stg.Machine.Types.NotInScope instance GHC.Classes.Eq Stg.Machine.Types.NotInScope instance GHC.Generics.Generic Stg.Machine.Types.StateTransition instance GHC.Show.Show Stg.Machine.Types.StateTransition instance GHC.Classes.Ord Stg.Machine.Types.StateTransition instance GHC.Classes.Eq Stg.Machine.Types.StateTransition instance GHC.Generics.Generic Stg.Machine.Types.StackFrame instance GHC.Show.Show Stg.Machine.Types.StackFrame instance GHC.Classes.Ord Stg.Machine.Types.StackFrame instance GHC.Classes.Eq Stg.Machine.Types.StackFrame instance GHC.Generics.Generic Stg.Machine.Types.Code instance GHC.Show.Show Stg.Machine.Types.Code instance GHC.Classes.Ord Stg.Machine.Types.Code instance GHC.Classes.Eq Stg.Machine.Types.Code instance GHC.Generics.Generic Stg.Machine.Types.Locals instance GHC.Base.Monoid Stg.Machine.Types.Locals instance GHC.Show.Show Stg.Machine.Types.Locals instance GHC.Classes.Ord Stg.Machine.Types.Locals instance GHC.Classes.Eq Stg.Machine.Types.Locals instance GHC.Generics.Generic Stg.Machine.Types.Globals instance GHC.Base.Monoid Stg.Machine.Types.Globals instance GHC.Show.Show Stg.Machine.Types.Globals instance GHC.Classes.Ord Stg.Machine.Types.Globals instance GHC.Classes.Eq Stg.Machine.Types.Globals instance GHC.Generics.Generic (Stg.Machine.Types.Mapping k v) instance (GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Stg.Machine.Types.Mapping k v) instance (GHC.Classes.Ord k, GHC.Classes.Ord v) => GHC.Classes.Ord (Stg.Machine.Types.Mapping k v) instance (GHC.Classes.Eq k, GHC.Classes.Eq v) => GHC.Classes.Eq (Stg.Machine.Types.Mapping k v) instance GHC.Generics.Generic Stg.Machine.Types.Value instance GHC.Show.Show Stg.Machine.Types.Value instance GHC.Classes.Ord Stg.Machine.Types.Value instance GHC.Classes.Eq Stg.Machine.Types.Value instance GHC.Generics.Generic Stg.Machine.Types.MemAddr instance GHC.Enum.Bounded Stg.Machine.Types.MemAddr instance GHC.Enum.Enum Stg.Machine.Types.MemAddr instance GHC.Show.Show Stg.Machine.Types.MemAddr instance GHC.Classes.Ord Stg.Machine.Types.MemAddr instance GHC.Classes.Eq Stg.Machine.Types.MemAddr instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.StgState instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.StackFrame instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.MemAddr instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.Value instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.Code instance (Text.PrettyPrint.ANSI.Leijen.Pretty k, Text.PrettyPrint.ANSI.Leijen.Pretty v) => Text.PrettyPrint.ANSI.Leijen.Pretty (Stg.Machine.Types.Mapping k v) instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.Globals instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.Locals instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.Info instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.InfoShort instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.StateTransition instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.NotInScope instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.StateError instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.InfoDetail instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.Closure instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.Heap instance Text.PrettyPrint.ANSI.Leijen.Pretty Stg.Machine.Types.HeapObject instance Control.DeepSeq.NFData Stg.Machine.Types.StgState instance Control.DeepSeq.NFData Stg.Machine.Types.StackFrame instance Control.DeepSeq.NFData Stg.Machine.Types.MemAddr instance Control.DeepSeq.NFData Stg.Machine.Types.Value instance Control.DeepSeq.NFData Stg.Machine.Types.Code instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData v) => Control.DeepSeq.NFData (Stg.Machine.Types.Mapping k v) instance Control.DeepSeq.NFData Stg.Machine.Types.Globals instance Control.DeepSeq.NFData Stg.Machine.Types.Locals instance Control.DeepSeq.NFData Stg.Machine.Types.Info instance Control.DeepSeq.NFData Stg.Machine.Types.InfoShort instance Control.DeepSeq.NFData Stg.Machine.Types.StateTransition instance Control.DeepSeq.NFData Stg.Machine.Types.NotInScope instance Control.DeepSeq.NFData Stg.Machine.Types.StateError instance Control.DeepSeq.NFData Stg.Machine.Types.InfoDetail instance Control.DeepSeq.NFData Stg.Machine.Types.Closure instance Control.DeepSeq.NFData Stg.Machine.Types.Heap instance Control.DeepSeq.NFData Stg.Machine.Types.HeapObject -- | Defines operations on local and global variable environments. module Stg.Machine.Env -- | Add a list of bindings to the local environment. -- -- Already existing variables will be shadowed (i.e. overwritten). addLocals :: [Mapping Var Value] -> Locals -> Locals -- | Create a local environment from a list of bindings. makeLocals :: [Mapping Var Value] -> Locals -- | Look up the value of an Atom first in the local, then in the -- global environment. val :: Locals -> Globals -> Atom -> Validate NotInScope Value -- | Look up the values of many Atoms, and return their values in -- the input's order, or a list of variables not in scope. vals :: Locals -> Globals -> [Atom] -> Validate NotInScope [Value] -- | Look up the value of a variable in the local environment. localVal :: Locals -> Atom -> Validate NotInScope Value -- | Type safety wrapper. newtype NotInScope NotInScope :: [Var] -> NotInScope -- | Look up the value of a variable in the global environment. globalVal :: Globals -> Atom -> Validate NotInScope Value -- | The STG heap maps memory addresses to closures. module Stg.Machine.Heap -- | Current number of elements in a heap. size :: Heap -> Int -- | Look up a value on the heap. lookup :: MemAddr -> Heap -> Maybe HeapObject -- | Update a value on the heap. update :: MemAddr -> HeapObject -> Heap -> Heap -- | Update many values on the heap. updateMany :: [MemAddr] -> [HeapObject] -> Heap -> Heap -- | Store a value in the heap at an unused address. alloc :: HeapObject -> Heap -> (MemAddr, Heap) -- | Store many values in the heap at unused addresses, and return them in -- input order. allocMany :: [HeapObject] -> Heap -> ([MemAddr], Heap) -- | Evaluate STG Programs. module Stg.Machine.Evaluate -- | Perform a single STG machine evaluation step. evalStep :: StgState -> StgState -- | Definitions used by various garbage collection algorithms. module Stg.Machine.GarbageCollection.Common -- | Split the heap contained in a machine state in two parts: the dead -- objects that can safely be discarded, and the alive ones that are -- still needed by the program. splitHeapWith :: GarbageCollectionAlgorithm -> StgState -> (Set MemAddr, Map MemAddr MemAddr, StgState) data GarbageCollectionAlgorithm -- | Dead addresses, moved addresses, new state GarbageCollectionAlgorithm :: Text -> (StgState -> (Set MemAddr, Map MemAddr MemAddr, StgState)) -> GarbageCollectionAlgorithm -- | Collect all mentioned addresses in a machine element. -- -- Note that none of the types in Stg.Language contain addresses, -- since an address is not something present in the STG _language_, only -- in the execution contest the language is put in in the -- Stg.Machine modules. class Addresses a where addrs = nubSeq . addrs' -- | All contained addresses in the order they appear, but without -- duplicates. addrs :: Addresses a => a -> Seq MemAddr -- | Update all contained addresses in a certain value. Useful for moving -- garbage collectors. class UpdateAddrs a updateAddrs :: UpdateAddrs a => (MemAddr -> MemAddr) -> a -> a instance (Data.Foldable.Foldable f, Stg.Machine.GarbageCollection.Common.Addresses a) => Stg.Machine.GarbageCollection.Common.Addresses (f a) instance Stg.Machine.GarbageCollection.Common.Addresses Stg.Machine.Types.Code instance Stg.Machine.GarbageCollection.Common.Addresses Stg.Machine.Types.StackFrame instance Stg.Machine.GarbageCollection.Common.Addresses Stg.Machine.Types.MemAddr instance Stg.Machine.GarbageCollection.Common.Addresses Stg.Machine.Types.Globals instance Stg.Machine.GarbageCollection.Common.Addresses Stg.Machine.Types.Locals instance Stg.Machine.GarbageCollection.Common.Addresses Stg.Machine.Types.Closure instance Stg.Machine.GarbageCollection.Common.Addresses Stg.Machine.Types.HeapObject instance Stg.Machine.GarbageCollection.Common.Addresses Stg.Machine.Types.Value instance Stg.Machine.GarbageCollection.Common.UpdateAddrs Stg.Machine.Types.Code instance Stg.Machine.GarbageCollection.Common.UpdateAddrs Stg.Machine.Types.Locals instance Stg.Machine.GarbageCollection.Common.UpdateAddrs Stg.Machine.Types.Globals instance Stg.Machine.GarbageCollection.Common.UpdateAddrs Stg.Machine.Types.Value instance Stg.Machine.GarbageCollection.Common.UpdateAddrs Stg.Machine.Types.MemAddr instance (GHC.Base.Functor f, Stg.Machine.GarbageCollection.Common.UpdateAddrs a) => Stg.Machine.GarbageCollection.Common.UpdateAddrs (f a) instance Stg.Machine.GarbageCollection.Common.UpdateAddrs Stg.Machine.Types.StackFrame -- | Tri-state ("tri-colour") garbage collector. -- -- module Stg.Machine.GarbageCollection.TriStateTracing -- | Remove all unused addresses, without moving the others. triStateTracing :: GarbageCollectionAlgorithm instance GHC.Show.Show Stg.Machine.GarbageCollection.TriStateTracing.GcState instance GHC.Classes.Ord Stg.Machine.GarbageCollection.TriStateTracing.GcState instance GHC.Classes.Eq Stg.Machine.GarbageCollection.TriStateTracing.GcState -- | Two space stop-and-copy garbage collector. -- -- module Stg.Machine.GarbageCollection.TwoSpaceCopying -- | Remove all unused addresses by moving them to a safe location. twoSpaceCopying :: GarbageCollectionAlgorithm instance GHC.Base.Monad Stg.Machine.GarbageCollection.TwoSpaceCopying.Gc instance GHC.Base.Applicative Stg.Machine.GarbageCollection.TwoSpaceCopying.Gc instance GHC.Base.Functor Stg.Machine.GarbageCollection.TwoSpaceCopying.Gc instance GHC.Show.Show Stg.Machine.GarbageCollection.TwoSpaceCopying.GcState instance GHC.Classes.Ord Stg.Machine.GarbageCollection.TwoSpaceCopying.GcState instance GHC.Classes.Eq Stg.Machine.GarbageCollection.TwoSpaceCopying.GcState -- | Remove unused heap objects. module Stg.Machine.GarbageCollection garbageCollect :: GarbageCollectionAlgorithm -> StgState -> StgState data GarbageCollectionAlgorithm -- | Remove all unused addresses, without moving the others. triStateTracing :: GarbageCollectionAlgorithm -- | Remove all unused addresses by moving them to a safe location. twoSpaceCopying :: GarbageCollectionAlgorithm -- | User-facing API to work with STG programs. module Stg.Machine -- | Create a suitable initial state for an STG. initialState :: Var -> Program -> StgState -- | Perform a single STG machine evaluation step. evalStep :: StgState -> StgState -- | Evaluate the STG until a predicate holds, aborting if the maximum -- number of steps are exceeded. -- -- 
--   last (evalsUntil ...) ≡ evalUntil
--
evalUntil :: RunForSteps -> HaltIf -> PerformGc -> StgState -> StgState -- | Evaluate the STG, and record all intermediate states. -- -- -- -- 
--   evalsUntil ≈ unfoldr evalUntil
--
evalsUntil :: RunForSteps -> HaltIf -> PerformGc -> StgState -> NonEmpty StgState -- | Check whether a state is terminal. terminated :: StgState -> Bool -- | Predicate to decide whether the machine should halt. newtype HaltIf HaltIf :: (StgState -> Bool) -> HaltIf -- | Predicate to decide whether the machine should halt. data RunForSteps -- | Do not terminate based on the number of steps RunIndefinitely :: RunForSteps RunForMaxSteps :: Integer -> RunForSteps garbageCollect :: GarbageCollectionAlgorithm -> StgState -> StgState -- | Decide whether garbage collection should be attempted, and with which -- algorithm. newtype PerformGc PerformGc :: (StgState -> Maybe GarbageCollectionAlgorithm) -> PerformGc data GarbageCollectionAlgorithm -- | Remove all unused addresses, without moving the others. triStateTracing :: GarbageCollectionAlgorithm -- | Remove all unused addresses by moving them to a safe location. twoSpaceCopying :: GarbageCollectionAlgorithm -- | Extract Haskell values from running STG programs. module Stg.Marshal.FromStg -- | Look up the value of a global variable. -- -- Instances of this class should have a corresponding ToStg -- instance to inject a value into the program, with the two being -- inverse to each other (up to forcing the generated thunks). class FromStg value where fromStg stgState = globalVal stgState (\case { PrimInt {} -> Left TypeMismatch Addr addr -> fromStgAddr stgState addr }) fromStgPrim _ = Left TypeMismatch -- | Retrieve the value of a global variable. fromStg :: FromStg value => StgState -> Var -> Either FromStgError value -- | Retrieve the value of a heap address. fromStgAddr :: FromStg value => StgState -> MemAddr -> Either FromStgError value -- | Used only for looking up primitive integers. fromStgPrim :: FromStg value => Integer -> Either FromStgError value data FromStgError -- | e.g. asking for an Int# at an address that contains a -- Cons TypeMismatch :: FromStgError -- | Tried retrieving a non-constructor IsWrongLambdaType :: LambdaType -> FromStgError -- | Tried retrieving a black hole IsBlackhole :: FromStgError -- | e.g. Cons x y z BadArity :: FromStgError -- | An unsuccessful variable lookup NotFound :: NotInScope -> FromStgError AddrNotOnHeap :: FromStgError -- | None of the given alternatives matched the given constructor, e.g. -- when trying to receive a Left as a Just NoConstructorMatch :: FromStgError instance GHC.Show.Show Stg.Marshal.FromStg.FromStgError instance GHC.Classes.Ord Stg.Marshal.FromStg.FromStgError instance GHC.Classes.Eq Stg.Marshal.FromStg.FromStgError instance Stg.Marshal.FromStg.FromStg () instance Stg.Marshal.FromStg.FromStg GHC.Types.Bool instance Stg.Marshal.FromStg.FromStg GHC.Integer.Type.Integer instance (Stg.Marshal.FromStg.FromStg a, Stg.Marshal.FromStg.FromStg b) => Stg.Marshal.FromStg.FromStg (a, b) instance (Stg.Marshal.FromStg.FromStg a, Stg.Marshal.FromStg.FromStg b, Stg.Marshal.FromStg.FromStg c) => Stg.Marshal.FromStg.FromStg (a, b, c) instance (Stg.Marshal.FromStg.FromStg a, Stg.Marshal.FromStg.FromStg b, Stg.Marshal.FromStg.FromStg c, Stg.Marshal.FromStg.FromStg d) => Stg.Marshal.FromStg.FromStg (a, b, c, d) instance (Stg.Marshal.FromStg.FromStg a, Stg.Marshal.FromStg.FromStg b, Stg.Marshal.FromStg.FromStg c, Stg.Marshal.FromStg.FromStg d, Stg.Marshal.FromStg.FromStg e) => Stg.Marshal.FromStg.FromStg (a, b, c, d, e) instance Stg.Marshal.FromStg.FromStg a => Stg.Marshal.FromStg.FromStg (GHC.Base.Maybe a) instance (Stg.Marshal.FromStg.FromStg a, Stg.Marshal.FromStg.FromStg b) => Stg.Marshal.FromStg.FromStg (Data.Either.Either a b) instance Stg.Marshal.FromStg.FromStg a => Stg.Marshal.FromStg.FromStg [a] -- | Convert Haskell values to STG values and back. -- -- This module is what users should be using - it reexports only the safe -- classes. module Stg.Marshal -- | Convert a Haskell value to an STG binding. -- -- Instances of this class should have a corresponding FromStg -- instance to retrieve a value fom the program, with the two being -- inverse to each other (up to forcing the generated thunks). -- -- This class contains a helper function, toStgWithGlobals, this -- is hidden from the outside. If you want to write your own instance, -- have a look at the source for documentation. class ToStg value where toStg var val = let (globals, actualDef) = runWriter (toStgWithGlobals var val) in globals <> actualDef toStgWithGlobals var val = pure (toStg var val) toStg :: ToStg value => Var -> value -> Program -- | Look up the value of a global variable. -- -- Instances of this class should have a corresponding ToStg -- instance to inject a value into the program, with the two being -- inverse to each other (up to forcing the generated thunks). class FromStg value where fromStg stgState = globalVal stgState (\case { PrimInt {} -> Left TypeMismatch Addr addr -> fromStgAddr stgState addr }) fromStgPrim _ = Left TypeMismatch -- | Retrieve the value of a global variable. fromStg :: FromStg value => StgState -> Var -> Either FromStgError value data FromStgError -- | e.g. asking for an Int# at an address that contains a -- Cons TypeMismatch :: FromStgError -- | Tried retrieving a non-constructor IsWrongLambdaType :: LambdaType -> FromStgError -- | Tried retrieving a black hole IsBlackhole :: FromStgError -- | e.g. Cons x y z BadArity :: FromStgError -- | An unsuccessful variable lookup NotFound :: NotInScope -> FromStgError AddrNotOnHeap :: FromStgError -- | None of the given alternatives matched the given constructor, e.g. -- when trying to receive a Left as a Just NoConstructorMatch :: FromStgError -- | A collection of example programs that might be interesting to look at -- during execution. module Stg.ExamplePrograms -- | A program that adds two numbers. addTwoNumbers :: Integer -> Integer -> Program -- | A program that measures the length of a list. calculateLength :: [Integer] -> Program -- | Sum up a list of Integers using -- -- 
--   sum = foldl' (+) 0
--
-- -- This is a good way to sum up a list in Haskell, as it runs in constant -- space. sum_foldl' :: [Integer] -> Program -- | Sum up a list of Integers using -- -- 
--   sum = foldl' (+) 0
--
-- -- where foldl' is implemented via foldr as -- -- 
--   foldl' f z ys = foldr (x xs acc -> xs $! f acc x) id ys z
--
-- -- which is a standard "foldl' in terms of foldr" -- definition. This definition is denotationally equivalent to the -- standard foldl', but has a bit more computational overhead. sum_foldl'ViaFoldr :: [Integer] -> Program -- | Sum up a list of Integers using -- -- 
--   sum = foldl (+) 0
--
-- -- This is the canonical space leak in Haskell: note how the accumulator -- is lazy, resulting in a large thunk buildup of suspended additions, -- that is only collapsed to a final value after foldl has -- terminated. The thunks are stored on the heap, so it grows linearly -- with the length of the list. When that thunk is forced, it will push -- lots of additions on the stack; in summary, this produces a heap -- overflow, and if the heap is not exhausted, it will try to overflow -- the stack. sum_foldl :: [Integer] -> Program -- | Sum up a list of Integers using -- -- 
--   sum = foldr (+) 0
--
-- -- Like the foldl version demonstrated in sum_foldl, this -- is a space-leaking implementation of the sum of a list. In this case -- however, the leak spills to the stack and the heap alike: the stack -- contains the continuations for the additions, while the heap contains -- thunks for the recursive call to foldr. sum_foldr :: [Integer] -> Program -- | Calculate the n-th Fibonacci number using the computationally -- (horribly) inefficient formula -- -- 
--   fib n | n <= 1 = n
--   fib n = fib (n-1) + fib (n-2)
--
-- -- This implementation is stack-only, so enjoy watching it explode. At -- the time of writing this, the machine takes: -- -- fibonacciNaive :: Integer -> Program -- | Calculate the n-th Fibonacci number using the more effective formula -- -- 
--   fib = fib' 0 1
--     where
--       fib' x _ | n <= 0 = x
--       fib' x !y n = fib' y (x+y) (n-1)
--
-- -- This implementation is a lot faster than the naive exponential -- implementation. For examle, calculating the 10th Fibonacci number (55) -- takes only 490 steps, compared to the many thousand of the exponential -- version. fibonacciImproved :: Integer -> Program -- | Compute the list of Fibonacci numbers eagerly in the contents, but -- lazy in the spine. -- -- This means that the program will successively generate all the -- Fibonacci numbers, allocating new cells of the infinite list and -- calculating their new values, and garbage collecting previous values. -- -- You can picture this as what happens to fibo in the Haskell -- program -- -- 
--   main = let fibo = zipWith (+) fibo (tail fibo)
--          in traverse_ print fibo
--
fibonacciZipWith :: Program -- | Force a right-associated concatenation -- -- 
--   [0] ++ ([1] ++ ([2] ++ ([3])))
--
-- -- and store it in the main closure. -- -- This computation is linear in the number of elements of the -- sublists. listConcatRightAssociated :: [[Integer]] -> Program -- | Force a left-associated concatenation -- -- 
--   (([0] ++ [1]) ++ [2]) ++ [3]
--
-- -- and store it in the main closure. -- -- This computation is quadratic in the number of elements of the -- sublists. listConcatLeftAssociated :: [[Integer]] -> Program -- | Sort a list with the canonical Quicksort-inspired algorithm often -- found in introductory texts about Haskell. -- -- Note that this is not Quicksort itself, as one key feature of it is -- sorting in-place. In particular, this algorithm is not all that quick, -- as it takes almost a thousand steps to reach the final state when -- sorting [5,4,3,2,1]. naiveSort :: [Integer] -> Program -- | Sort a list with a translation of Haskell's sort, which is an -- implementation of mergesort with ordered sublist detection. librarySort :: [Integer] -> Program -- | This is a naive implementation of the repeat function, -- -- 
--   repeat x = x : repeat x
--
-- -- and it is used to compute the infinite repetition of a number. Run -- this program for a couple hundred steps and observe the heap and the -- garbage collector. Count the GC invocations, and compare it to the -- behaviour of repeatSharing! Also note how long it takes to -- generate two successive list elements. -- -- The reason for this behaviour is that the call to repeat -- x is not shared, but done again for each cons cell, requiring one -- heap allocation every time. Cleaning up after this keeps the GC quite -- busy. repeatNaive :: Program -- | This uses a much better definition of repeat, -- -- 
--   repeat x = let repeatX = x : repeatX
--              in repeatX
--
-- -- This program does only a total of three heap allocations before -- continously running without interruption: one for the -- repeated value, one for the self-referencing cons cell, and -- one beacuse of how forceSpine works. -- -- Note how much smaller the cycles between the traversal of two -- neighbouring list cells is! repeatSharing :: Program