-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Educational implementation of the STG (Spineless Tagless -- G-machine) -- -- STGi is a visual STG implementation to help understand Haskell's -- execution model. -- -- It does this by guiding through the running of a program, showing -- stack and heap, and giving explanations of the applied transition -- rules. -- -- Here is what an intermediate state looks like: -- -- -- For further information, see README.md. @package stgi @version 1.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 -- | Either with an accumulating Applicative instance data Validate err a Failure :: err -> Validate err a Success :: a -> Validate err a -- | 
--   [a,b,c]  ==>  a, b, c
--
commaSep :: [Doc ann] -> Doc ann 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 class PrettyStgi a prettyStgi :: PrettyStgi a => a -> Doc StgiAnn data StgiAnn StateAnn :: StateAnn -> StgiAnn AstAnn :: AstAnn -> StgiAnn -- | Semantic annotations for rendering. data StateAnn -- | Style of headlines in the state overview, such as "Heap" and "Frame -- i". Headline :: StateAnn -- | Style of memory addresses, including 0x prefix. Address :: StateAnn -- | Style of memory addresses; applied only to the actual address number, -- such as ff in 0xff. AddressCore :: StateAnn -- | Style of the type of a closure, such as BLACKHOLE or FUN. ClosureType :: StateAnn -- | Style of the stack frame annotation, such as UPD or ARG. StackFrameType :: StateAnn -- | The different semantic annotations an STG AST element can have. data AstAnn Keyword :: AstAnn Prim :: AstAnn Variable :: AstAnn Constructor :: AstAnn Semicolon :: AstAnn renderRich :: Doc StgiAnn -> Text renderPlain :: Doc ann -> Text -- | Prettyprint a value as Text, including styles such as colours. prettyprintOldAnsi :: Doc -> Text instance Stg.Language.Prettyprint.PrettyStgi GHC.Types.Bool instance Stg.Language.Prettyprint.PrettyStgi GHC.Types.Int instance Stg.Language.Prettyprint.PrettyStgi GHC.Integer.Type.Integer instance (Stg.Language.Prettyprint.PrettyStgi a, Stg.Language.Prettyprint.PrettyStgi b) => Stg.Language.Prettyprint.PrettyStgi (a, b) instance Stg.Language.Prettyprint.PrettyStgi a => Stg.Language.Prettyprint.PrettyStgi [a] -- | 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 is the unit that can be loaded by the STG -- machine. It consists of a set 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 StgiAnn) -> LambdaForm -> Doc StgiAnn -- | The update flag distinguishes updatable from non-updatable lambda -- forms. data UpdateFlag -- | Overwrite the heap object in-place with its reduced value once -- available, making recurring access cheap Update :: UpdateFlag -- | Don't touch the heap object after evaluation NoUpdate :: UpdateFlag -- | Distinguishes let from letrec. data Rec -- | Bindings have no access to each other NonRecursive :: Rec -- | Bindings can be given to each other as free variables 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# LitE :: !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 -- | Overloaded conversion to Doc. -- -- Laws: -- --
    --
  1. output should be pretty. :-)
    2. --
class Pretty a -- | 
--   >>> pretty 1 <+> pretty "hello" <+> pretty 1.234
--   1 hello 1.234
--
pretty :: Pretty a => a -> Doc ann -- | prettyList is only used to define the instance -- Pretty a => Pretty [a]. In normal circumstances -- only the pretty function is used. -- -- 
--   >>> prettyList [1, 23, 456]
--   [1, 23, 456]
--
prettyList :: Pretty a => [a] -> Doc ann -- | 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 Stg.Language.Prettyprint.PrettyStgi Stg.Language.Program instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.Binds instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.LambdaForm instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.Rec instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.Expr instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.Alts instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.AlgebraicAlt instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.PrimitiveAlt instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.DefaultAlt instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.Literal instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.PrimOp instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.Var instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.Atom instance Stg.Language.Prettyprint.PrettyStgi 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.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 Data.Semigroup.Semigroup Stg.Language.Program instance GHC.Base.Monoid Stg.Language.Binds instance Data.Semigroup.Semigroup Stg.Language.Binds instance GHC.Show.Show Stg.Language.Binds instance Stg.Language.Prettyprint.PrettyStgi Stg.Language.LambdaType instance Data.String.IsString Stg.Language.Var instance Data.String.IsString Stg.Language.Constr -- | Definitions useful for all state transition modules. module Stg.Machine.Evaluate.Common -- | Possible errors of primops data PrimError -- | Division by zero Div0 :: PrimError -- | Apply a primop to two actual integers applyPrimOp :: PrimOp -> Integer -> Integer -> Validate PrimError Integer -- | Successful alternative match, used for finding the right branch in -- case data AltMatch alt AltMatches :: alt -> AltMatch alt DefaultMatches :: DefaultAlt -> AltMatch alt -- | Possible errors when looking up alternatives data AltError -- | Algebraic/primitive alternative in primitive/algebraic case BadAlt :: AltError -- | Look up an algebraic constructor among the given alternatives, and -- return the first match. If nothing matches, return the default -- alternative. lookupAlgebraicAlt :: Alts -> Constr -> Validate AltError (AltMatch AlgebraicAlt) -- | lookupAlgebraicAlt for primitive literals. lookupPrimitiveAlt :: Alts -> Literal -> Validate AltError (AltMatch PrimitiveAlt) -- | 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 :: StgParser Program -- | Parse a collection of bindings, used by let(rec) expressions -- and at the top level of a program. binds :: StgParser 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 :: StgParser LambdaForm -- | Parse an expression, which can be -- -- expr :: StgParser Expr -- | Parse the alternatives given in a case expression. alts :: StgParser 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 :: StgParser NonDefaultAlts -- | Parse a single algebraic alternative. -- -- 
--   Cons x xs -> ...
--
algebraicAlt :: StgParser AlgebraicAlt -- | Parse a single primitive alternative, such as 1#. -- -- 
--   1# -> ...
--
primitiveAlt :: StgParser PrimitiveAlt -- | Parse the default alternative, taken if none of the other alternatives -- in a case expression match. -- -- 
--   default -> ...
--
-- -- 
--   v -> ...
--
defaultAlt :: StgParser DefaultAlt -- | Parse an integer literal -- -- 
--   1#
--   -123#
--
literal :: StgParser Literal -- | Parse a primitive operation. -- -- 
--   +#
--
primOp :: StgParser PrimOp -- | Parse an atom atom :: StgParser Atom -- | Parse a variable identifier. Variables start with a lower-case letter -- or _, followed by a string consisting of alphanumeric -- characters or ', _. var :: StgParser 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 :: StgParser 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 -- | Boolean functions, like in Data.Bool. -- -- This module should be imported qualified to avoid clashes with -- standard Haskell definitions. 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 -- | Definitions found in Haskell's Data.Function. -- -- This module should be imported qualified to avoid clashes with -- standard Haskell definitions. 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 -- | Functions as found in Haskell's Data.Maybe module. -- -- This module should be imported qualified to avoid clashes with -- standard Haskell definitions. 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 -- | Operations on boxed integers. -- -- This module should be imported qualified to avoid clashes with -- standard Haskell definitions. module Stg.Prelude.Number -- | Binary addition of boxed integers add :: Program -- | Difference of boxed integers sub :: Program -- | Binary multiplication of boxed integers mul :: Program -- | Boxed integer division div :: Program -- | Boxed integer modulo operator mod :: Program -- | Equality of boxed integers eq_Int :: Program -- | Less-than for boxed integers lt_Int :: Program -- | Less-or-equal for boxed integers leq_Int :: Program -- | Greater-than for boxed integers gt_Int :: Program -- | Greater-or-equal for boxed integers geq_Int :: Program -- | Inequality of boxed integers neq_Int :: Program -- | Minimum of two boxed integers min :: Program -- | Maximum of two boxed integers max :: Program -- | Definitions found in Haskell's Data.List. -- -- This module should be imported qualified to avoid clashes with -- standard Haskell definitions. 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 -- | Separate a list into parts that do and do not satisfy a predicate. -- -- 
--   partition even [1..6] = ([2,4,6], [1,3,5])
--
-- -- 
--   partition : (a -> Bool) -> [a] -> ([a], [a])
--
partition :: 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) -- | Definitions found in Haskell's Data.Tuple. -- -- This module should be imported qualified to avoid clashes with -- standard Haskell definitions. 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 -- | Equality of pairs of boxed integers. 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 to avoid clashes with -- standard Haskell definitions. module Stg.Prelude -- | 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 -- | Extract Haskell values from running STG programs. module Stg.StaticAnalysis -- | Overloading class for determining the free variables of an object. class FreeVariables ast freeVariables :: FreeVariables ast => ast -> Set Var instance (Data.Foldable.Foldable f, Stg.StaticAnalysis.FreeVariables a) => Stg.StaticAnalysis.FreeVariables (f a) instance Stg.StaticAnalysis.FreeVariables Stg.Language.Program instance Stg.StaticAnalysis.FreeVariables Stg.Language.Binds instance Stg.StaticAnalysis.FreeVariables Stg.Language.Expr instance Stg.StaticAnalysis.FreeVariables Stg.Language.LambdaForm instance Stg.StaticAnalysis.FreeVariables Stg.Language.Alts instance Stg.StaticAnalysis.FreeVariables Stg.Language.NonDefaultAlts instance Stg.StaticAnalysis.FreeVariables Stg.Language.AlgebraicAlt instance Stg.StaticAnalysis.FreeVariables Stg.Language.PrimitiveAlt instance Stg.StaticAnalysis.FreeVariables Stg.Language.DefaultAlt instance Stg.StaticAnalysis.FreeVariables Stg.Language.Var instance Stg.StaticAnalysis.FreeVariables Stg.Language.Literal instance Stg.StaticAnalysis.FreeVariables Stg.Language.Atom -- | 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 present. 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.Internal.Pretty a => Text.PrettyPrint.ANSI.Leijen.Internal.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 Data.Semigroup.Semigroup (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 and for orientation -- purposes. [stgSteps] :: StgState -> !Integer -- | Information about the current state [stgInfo] :: StgState -> Info data StgiAnn StateAnn :: StateAnn -> StgiAnn AstAnn :: AstAnn -> StgiAnn -- | Stack frames unify arguments, returns, and updates. 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 an algebraic Constructor ReturnCon :: Constr -> [Value] -> Code -- | Sub-computation terminated with a primitive integer ReturnInt :: Integer -> Code -- | A single key -> value association. -- -- Used to make 2-tuples to be inserted into association maps clearer. 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 -- | Heap objects are what is stored on the heap. The most common and also -- most important one are closures. 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 -- | Used to store meta-information about state transitions in order to be -- rendered as a helpful hint. 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 -- | Classifies which rule has been applied in order to reach the current -- state. data StateTransition Rule1_Eval_FunctionApplication :: StateTransition Rule2_Enter_NonUpdatableClosure :: StateTransition Rule3_Eval_Let :: Rec -> StateTransition Rule4_Eval_Case :: StateTransition Rule5_Eval_AppC :: StateTransition Rule6_ReturnCon_Match :: StateTransition Rule7_ReturnCon_DefUnbound :: StateTransition Rule8_ReturnCon_DefBound :: StateTransition Rule9_Lit :: StateTransition Rule10_LitApp :: StateTransition Rule11_ReturnInt_Match :: StateTransition Rule12_ReturnInt_DefBound :: StateTransition Rule13_ReturnInt_DefUnbound :: StateTransition Rule14_Eval_AppP :: StateTransition Rule15_Enter_UpdatableClosure :: StateTransition Rule16_ReturnCon_Update :: StateTransition Rule17_Enter_PartiallyAppliedUpdate :: StateTransition Rule17a_Enter_PartiallyAppliedUpdate :: StateTransition Rule1819_Eval_Case_Primop_Shortcut :: StateTransition -- | Like StateTransition, but for invalid transitions. data StateError VariablesNotInScope :: NotInScope -> StateError UpdatableClosureWithArgs :: StateError ReturnIntWithEmptyReturnStack :: StateError AlgReturnToPrimAlts :: StateError PrimReturnToAlgAlts :: StateError InitialStateCreationFailed :: StateError EnterBlackhole :: StateError UpdateClosureWithPrimitive :: StateError NonAlgPrimScrutinee :: StateError DivisionByZero :: StateError -- | scrutinee arity, pattern arity BadConArity :: Int -> Int -> StateError -- | Type safety wrapper to report variables that were not in scope. newtype NotInScope NotInScope :: [Var] -> NotInScope 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 Data.Semigroup.Semigroup 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 Data.Semigroup.Semigroup 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 Data.Semigroup.Semigroup 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 Data.Semigroup.Semigroup 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 v, GHC.Show.Show k) => GHC.Show.Show (Stg.Machine.Types.Mapping k v) instance (GHC.Classes.Ord v, GHC.Classes.Ord k) => GHC.Classes.Ord (Stg.Machine.Types.Mapping k v) instance (GHC.Classes.Eq v, GHC.Classes.Eq k) => 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 Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.StgState instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.StackFrame instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.MemAddr instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.Value instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.Code instance (Stg.Language.Prettyprint.PrettyStgi k, Stg.Language.Prettyprint.PrettyStgi v) => Stg.Language.Prettyprint.PrettyStgi (Stg.Machine.Types.Mapping k v) instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.Globals instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.Locals instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.Info instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.InfoShort instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.StateTransition instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.NotInScope instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.StateError instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.InfoDetail instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.Closure instance Stg.Language.Prettyprint.PrettyStgi Stg.Machine.Types.Heap instance Stg.Language.Prettyprint.PrettyStgi 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 to report variables that were not in scope. newtype NotInScope NotInScope :: [Var] -> NotInScope -- | Look up the value of a variable in the global environment. globalVal :: Globals -> Atom -> Validate NotInScope Value -- | Definitions used by various garbage collection algorithms. module Stg.Machine.GarbageCollection.Common -- | Split the heap contained in a machine state in three parts: the dead -- objects that can safely be discarded, a maping from old to new -- addresses if definitions were moved, and the final state with a -- cleaned up heap. splitHeapWith :: GarbageCollectionAlgorithm -> StgState -> (Set MemAddr, Map MemAddr MemAddr, StgState) -- | A garbage collection algorithm is a specific way to get rid of unused -- heap objects. data GarbageCollectionAlgorithm -- | 
--   name (state -> (addresses, addresses, 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 -- | 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 :: Mapping MemAddr HeapObject -> Heap -> Heap -- | Update many values on the heap. updateMany :: [Mapping 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) -- | STG error transitions, in order to provide useful information to the -- user. module Stg.Machine.Evaluate.ErrorTransitions -- | Page 39, 2nd paragraph: "[...] closures with non-empty argument lists -- are never updatable [...]" updatableClosureWithArgs :: StgState -> Maybe StgState -- | Page 39, 4th paragraph: "It is not possible for the ReturnInt state to -- see an empty return stack, because that would imply that a closure -- should be updated with a primitive value; but no closure has a -- primitive type." returnWithEmptyReturnStack :: StgState -> Maybe StgState -- | A function was applied to an argument that was neither globally -- defined nor in the local environment functionArgumentNotInScope :: StgState -> Maybe StgState -- | A constructor was applied to an argument that was neither globally -- defined nor in the local environment constructorArgumentNotInScope :: StgState -> Maybe StgState -- | A primitive operation was applied to an argument that was neither -- globally defined nor in the local environment primopArgumentNotInScope :: StgState -> Maybe StgState -- | Algebraic constructor return, but primitive alternative on return -- frame algReturnToPrimAlts :: StgState -> Maybe StgState -- | Primitive return, but algebraic alternative on return frame primReturnToAlgAlts :: StgState -> Maybe StgState -- | A black hole was entered, and the infinite recursion detection -- triggered as a result enterBlackhole :: StgState -> Maybe StgState -- | Closures are always lifted, not primitive updateClosureWithPrimitive :: StgState -> Maybe StgState -- | Non-algebraic scrutinee -- -- For more information on this, see seq. nonAlgPrimScrutinee :: StgState -> Maybe StgState -- | A primitive division had zero as denominator divisionByZero :: StgState -> Maybe StgState -- | Bad constructor arity: different number of arguments in code segment -- and in return frame badConArity :: StgState -> Maybe StgState -- | Valid transitions from one state to another. Error conditions are -- handled separately in ErrorTransitions if possible. module Stg.Machine.Evaluate.ValidTransitions -- | Rule 1: Function application -- -- Push argument values onto the stack, and enter the function's address. rule1_functionApp :: StgState -> Maybe StgState -- | Rule 2: Enter non-updatable closure -- -- Fetch all arguments from the stack, bind them to the lambda's -- variables, and continue evaluating the body. rule2_enterNonUpdatable :: StgState -> Maybe StgState -- | Rule 3: let(rec) -- -- Allocate closures for each definition on the heap, making sure -- references to existing (or recursive) definitions are correct, and add -- the bindings to the local environment. Proceed by evaluating the -- in part of the let. rule3_let :: StgState -> Maybe StgState -- | Rule 4: Case evaluation -- -- Push a return frame with the possible branches, and continue -- evaluating the scrutinee. -- -- Compared to the paper, this rule was improved by removing local -- bindings that are not used at all in the alternatives, which would -- unnecessarily prolong the garbage collection lifetime of unused -- bindings. rule4_case :: StgState -> Maybe StgState -- | Rule 5: Constructor application -- -- Simply transition into the ReturnCon state. rule5_constructorApp :: StgState -> Maybe StgState -- | Rule 6: Algebraic constructor return, standard match -- -- Continue with the branch of the matched constructor, extending the -- local environment with the matched pattern variables' values. rule6_algebraicNormalMatch :: StgState -> Maybe StgState -- | Rule 7: Algebraic constructor return, unbound default match -- -- None of the given alternatives matched, so simply continue with the -- default branch. rule7_algebraicUnboundDefaultMatch :: StgState -> Maybe StgState -- | Rule 8: Algebraic constructor return, bound default match -- -- None of the given alternatives matched, so continue with the default -- branch. Also allocate the default-matched value on the heap and extend -- the local environment with its binding to retain a reference to the -- scrutinized value. rule8_algebraicBoundDefaultMatch :: StgState -> Maybe StgState -- | Rule 9: Literal evaluation -- -- Simply transition into the ReturnInt state. rule9_primitiveLiteralEval :: StgState -> Maybe StgState -- | Rule 10: Literal application -- -- Simply transition into the ReturnInt state. rule10_primitiveLiteralApp :: StgState -> Maybe StgState -- | Rule 11: Primitive return, standard match found -- -- Like rule4_case, but for primitives. rule11_primitiveNormalMatch :: StgState -> Maybe StgState -- | Rule 12: Primitive return, bound default match -- -- Similar to rule8_algebraicBoundDefaultMatch, but for primtives. -- Since the bound variable is primitive, this rule is a bit sompler -- since we can store the value directly in its binding, instead of -- allocating it on the heap and storing the address. rule12_primitiveBoundDefaultMatch :: StgState -> Maybe StgState -- | Rule 13: Primitive return, unbound default match -- -- Like rule7_algebraicUnboundDefaultMatch, but for primitives. rule13_primitiveUnboundDefaultMatch :: StgState -> Maybe StgState -- | Rule 14: Primitive function application -- -- This rule has been modified to take not only primitive-valued -- variables, but also primitive values directly as arguments. -- -- Without this modification, you cannot evaluate +# 1# 2#, you -- have to write -- -- 
--   case 1# of one -> case 2# of two -> case +# one two of ...
--
-- -- which is a bit silly. I think this might be an oversight in the 1992 -- paper. The fast curry paper does not seem to impose this restriction. -- -- This rule is shadowed by rule1819_casePrimopShortcut, which -- handles primitive application more efficiently, without the need for -- an intermediate ReturnInt state. rule14_primop :: StgState -> Maybe StgState -- | Rule 15: Enter updatable closure -- -- Evaluate the address pointed to, and store its future update in an -- UpdateFrame. -- -- In theory this could just do what rule2_enterNonUpdatable does, -- plus the update frame. However, since lambda forms that take arguments -- never form updatable closures, there is no need for -- ArgumentFrame handling in this rule. rule15_enterUpdatable :: StgState -> Maybe StgState -- | Rule 16: Update because of missing ReturnFrame -- -- A ReturnCon state requires a ReturnFrame to continue, -- but there is an UpdateFrame in the way. The latter has to be -- eliminated by performing an update with the returned constructor -- before attempting the return once more. rule16_missingReturnUpdate :: StgState -> Maybe StgState -- | Rule 17: Enter partially applied closure, update because of missing -- ArgumentFrame -- -- There are not enough ArgFrames on the stack for a lambda's -- arguments, because an update frame blocks access to more. -- -- Although this rule is a bit simpler to understand compared to rule -- 17a, it is hard to implement in a real STG compiler, since a new -- closure has to be made up during runtime, which means runtime code -- generation. Rule 17a remedies this problem. This rule (17) is included -- for comparison anyway. rule17_missingArgUpdate :: StgState -> Maybe StgState -- | Rule 17a: Enter partially applied closure, update because of missing -- ArgumentFrame -- -- This is a better version of rule 17, since it does not neccessitate -- runtime code generation. All required closures can be precompiled. rule17a_missingArgUpdate :: StgState -> Maybe StgState -- | Rules 18, 19: Shortcut for evaluating/matching primops -- -- This rule allows evaluating primops without the overhead of allocating -- an intermediate return stack frame. In order to trigger, it must be -- applied with higher precedence than rule4_case. -- -- When reading the source here for educational purposes, you should skip -- this rule until you've seen the normal case rule (rule4_case) -- and the normal primop rule (rule14_primop). -- -- This rule has the slight modification compared to the paper in that it -- works for both bound and unbound default cases. rule1819_casePrimopShortcut :: StgState -> Maybe StgState -- | Evaluate STG Programs. module Stg.Machine.Evaluate -- | Perform a single STG machine evaluation step. evalStep :: StgState -> StgState -- | Two space stop-and-copy garbage collector. -- -- module Stg.Machine.GarbageCollection.TwoSpaceCopying -- | Move all used addresses by moving them to a safe location, and delete -- the leftovers. 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 -- | Apply a garbage collection algorithm to the heap of the current -- machine state, and return the resulting cleaned state. garbageCollect :: GarbageCollectionAlgorithm -> StgState -> StgState -- | A garbage collection algorithm is a specific way to get rid of unused -- heap objects. data GarbageCollectionAlgorithm -- | Remove all unused addresses, without moving the others. triStateTracing :: GarbageCollectionAlgorithm -- | Move all used addresses by moving them to a safe location, and delete -- the leftovers. 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 -- | Apply a garbage collection algorithm to the heap of the current -- machine state, and return the resulting cleaned state. garbageCollect :: GarbageCollectionAlgorithm -> StgState -> StgState -- | Decide whether garbage collection should be attempted, and with which -- algorithm. newtype PerformGc PerformGc :: (StgState -> Maybe GarbageCollectionAlgorithm) -> PerformGc -- | A garbage collection algorithm is a specific way to get rid of unused -- heap objects. data GarbageCollectionAlgorithm -- | Remove all unused addresses, without moving the others. triStateTracing :: GarbageCollectionAlgorithm -- | Move all used addresses by moving them to a safe location, and delete -- the leftovers. twoSpaceCopying :: GarbageCollectionAlgorithm instance GHC.Show.Show Stg.Machine.AttemptGc instance GHC.Classes.Ord Stg.Machine.AttemptGc instance GHC.Classes.Eq Stg.Machine.AttemptGc -- | 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 -- | Classifies the different errors that can happen when extracting a -- value from an STG state. 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 -- | Classifies the different errors that can happen when extracting a -- value from an STG state. 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 calculates x and not y. This is probably the -- simplest example program worth showing. It demonstrates how functions -- are evaluated, has an update for the main closure, and shows -- how nested functions result in let allocations. implies :: Bool -> Bool -> Program -- | A program that adds two numbers. addTwoNumbers :: Integer -> Integer -> Program -- | A program that measures the length of a list. calculateLength :: ToStg a => [a] -> Program -- | Negate a list of booleans, but non-strictly. This program does almost -- nothing, because nothing forces the list. mapNot :: [Bool] -> Program -- | Negate a list of booleans strictly. mapNotForced :: [Bool] -> 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 efficient 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 example, calculating the 10th Fibonacci number -- (55) takes only 490 steps, compared to the many thousands 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 :: ToStg a => [[a]] -> 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 :: ToStg a => [[a]] -> 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 -- continuously running without interruption: one for the -- repeated value, one for the self-referencing cons cell, and -- one because of how forceSpine works. -- -- Note how much smaller the cycles between the traversal of two -- neighbouring list cells are! repeatSharing :: Program