!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                 ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L MNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Safe with an accumulating  instance with  as codomain. show' =  .   [a,b,c] ==> a, b, c2Return success or the accumulation of all failures  Safe<=[ ?The different semantic annotations an STG AST element can have.#Semantic annotations for rendering.JStyle of headlines in the state overview, such as "Heap" and "Frame i".%Style of memory addresses, including 0x prefix.QStyle of memory addresses; applied only to the actual address number, such as ff in 0xff.9Style of the type of a closure, such as BLACKHOLE or FUN.8Style of the stack frame annotation, such as UPD or ARG.Prettyprint a value as #, including styles such as colours.  !"#      !"#None5<=[1$%Constructors of algebraic data types.&eSmallest unit of data. Atoms unify variables and literals, and are what functions take as arguments.) Variable.+Primitive operations., +- -. */ /0 %1 ==2 <3 <=4 >5 >=6 /=7/Literals are the basis of primitive operations.9<If no viable alternative is found in a pattern match, use a 9 as fallback.<As in 1#, 2#, 3#>As in  True | False@The part of a H$ alternative that's not the default.AUsed in 'case'g statements that consist only of a default alternative. These can be useful to force or unpack values.BAlgebraic alternative, like  Cons x xs.CPrimitive alternative, like 1#.D#List of possible alternatives in a H 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.F"An expression in the STG language.GLet expression let(rec) ... in ...HCase expression case ... of ... x -> yIFunction application f x y zJ"Saturated constructor application Just aKPrimitive function application + 1 2#LLiteral expression 1#MDistinguishes let from letrec.N%Bindings have no access to each otherO5Bindings can be given to each other as free variablesPHThe update flag distinguishes updatable from non-updatable lambda forms.QhOverwrite the heap object in-place with its reduced value once available, making recurring access cheapR,Don't touch the heap object after evaluationS(Possible classification of lambda forms.TData constructor (J as body)U.Function (lambda with non-empty argument list)VThunk (everything else)WA 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 |]iLambdaForm [Var "x"] NoUpdate [Var "y",Var "z"] (AppF (Var "expr") [AtomVar (Var "x"),AtomVar (Var "z")])X"Free variables (excluding globals) Update flagBound variablesBodyYABindings are collections of lambda forms, indexed over variables.>They exist at the top level, or as part of a let(rec) binding.[An STG [V is the unit that can be loaded by the STG machine. It consists of a set of bindings.]6Classify the type of a lambda form based on its shape.c Right-biased union. See  [ for further information.eRight-biased union of the contained bindings. This makes for a poor man's module system by appending multiple, potentially partially incomplete, Programs to each other.  <>  <> [ | & actual source & |] Prettyprint a W3, given prettyprinters for the free variable list.Introduced so !; can hijack it to display the free value list differently.g$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdeFree variable list printer>$%&'()*+1,-./023456789:;<=>?@ABCDEFLJGHIKMNOPQRSTUVWXYZ[\]?[\YZWXPQRMNOFGHIJKLDE@ABC>?<=9:;78+,-./0123456)*&'($%]STUV?$%&'()*+ ,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdeNone[,Possible errors when looking up alternatives<Algebraic/primitive alternative in primitive/algebraic caseCSuccessful alternative match, used for finding the right branch in casePossible errors of primopsDivision by zero%Apply a primop to two actual integersLook up an algebraic constructor among the given alternatives, and return the first match. If nothing matches, return the default alternative. for primitive literals. NoneI[#A parser for an STG syntax element.NParse STG source using a user-specified parser. To parse a full program, use  .parse program "id = \\x -> x"YRight (Program (Binds [(Var "id",LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") []))]))PSkip a certain token. Useful to consume, but not otherwise use, certain tokens.;Syntax rules for parsing variable-looking like identifiers.JParse a variable identifier. Variables start with a lower-case letter or _@, followed by a string consisting of alphanumeric characters or ', _.$Skip a reserved variable identifier.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.Parse an STG program.(Parse a collection of bindings, used by let(rec)0 expressions and at the top level of a program.Parse a lambda form, consisting of a list of free variables, and update flag, a list of bound variables, and the function body.Parse an arrow token, ->.!Parse an expression, which can belet, let(rec) ... in ...case, case ... of ...function application, f (...)constructor application, C (...)primitive application, p# (...) literal, 1#"Parse the alternatives given in a case expression. Parse an atomParse a primitive operation. +# Parse an integer literal  1# -123# oParse non-default alternatives. The list of alternatives can be either empty, all algebraic, or all primitive. Nil -> ... Cons x xs -> ... 1# -> ... 2# -> ... %Parse a single algebraic alternative. Cons x xs -> ... .Parse a single primitive alternative, such as 1#.  1# -> ... MParse the default alternative, taken if none of the other alternatives in a case expression match. default -> ...  v -> ... NonesHeuristic quasiquoter for STG language elements. Tries a number of parsers, and will use the first successful one.zTo gain more fine-grained control over what the input should be parsed to, use one of the non-heuristic quoters, such as  stgProgram or  stgLambdaFormR. These will also give you much better error messages than merely "doesn't work".[stg| id = \x -> x |]QProgram (Binds [(Var "id",LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") []))])[stg| \x -> x |]4LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") []) [stg| x |]AppF (Var "x") []Build a quasiquoter from a Parser.Quasiquoter for "s.[program| id = \x -> x |]QProgram (Binds [(Var "id",LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") []))])Quasiquoter for #.[binds| id = \x -> x |]I(Binds [(Var "id",LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") []))])Quasiquoter for $s.[lambdaForm| \x -> x |]4LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") [])Quasiquoter for %essions.[expr| f x y z |]FAppF (Var "f") [AtomVar (Var "x"),AtomVar (Var "y"),AtomVar (Var "z")]Quasiquoter for &.*[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") []))Quasiquoter for '.5[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") [])])Quasiquoter for (s.[algebraicAlt| Just x -> x; |]:AlgebraicAlt (Constr "Just") [Var "x"] (AppF (Var "x") [])Quasiquoter for )s.[primitiveAlt| 1# -> x; |],PrimitiveAlt (Literal 1) (AppF (Var "x") [])Quasiquoter for *s.[defaultAlt| default -> x |]#DefaultNotBound (AppF (Var "x") [])[defaultAlt| x -> x |]*DefaultBound (Var "x") (AppF (Var "x") [])Quasiquoter for +s.[literal| 1# |] Literal 1 Quasiquoter for ,s.[primOp| +# |]Add Quasiquoter for -s. [atom| x |]AtomVar (Var "x")7Name of the parsed syntax element (for error reporting)        None Boolean equality. Binary and. Haskell's (&&). && : Bool -> Bool -> Bool  Binary or. Haskell's (||). || : Bool -> Bool -> Bool Binary negation. not : Bool -> Bool Boolean deconstructor. &bool f _ False = f bool _ t True = t bool : a -> a -> Bool -> a             NoneFinally I can define ./ directly! :-)4Note that this function is less powerful than GHC's ./, 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 seq3 is less powerful than Haskell's, since in Haskell seq (const ()) () = () whereas in the STG :constUnit = (x) -> Unit (); seq (constUnit, Unit) = ERROR Identity function.  id : a -> a Constant function. Const : a -> b -> a Function composition. )compose : (b -> c) -> (a -> b) -> a -> c The fixed point combinator. fix : (a -> a) -> a  NoneNothing as a top-level closure. nothing : Maybe a Deconstructor of the Maybe type. &maybe : b -> (a -> b) -> Maybe a -> b  None Equality of boxed integersLess-than for boxed integers Less-or-equal for boxed integersGreater-than for boxed integers#Greater-or-equal for boxed integersInequality of boxed integers!Binary addition of boxed integersDifference of boxed integers'Binary multiplication of boxed integers Boxed integer division!Boxed integer modulo operator"Minimum of two boxed integers#Maximum of two boxed integers !"#  !"#  !"# !"# None$&The empty list as a top-level closure.  nil : [a] %!Concatenate two lists. Haskell's (++). concat2 : [a] -> [a] -> [a] &OLazy left list fold. Provided mostly for seeing how it causes stack overflows. 'foldl : (b -> a -> b) -> b -> [a] -> b '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 (Right list fold. 'foldr : (a -> b -> b) -> b -> [a] -> b )CBuild 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] *?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] +-Take n elements form the beginning of a list. take 3 [1..] = [1,2,3] take : Int -> [a] -> [a] ,3Keep only the elements for which a predicate holds. #filter even [1..] = [2, 4, 6, ...] #filter : (a -> Bool) -> [a] -> [a] -BSeparate 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]) .reverse a list. reverse [1,2,3] = [3,2,1] reverse : [a] -> [a] /#Repeat a single element infinitely. repeat 1 = [1, 1, 1, ...] repeat : a -> [a] 0*Repeat a single element a number of times. replicate 3 1 = [1, 1, 1] replicate : Int -> a -> [a] 1Haskell'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 2 requires 268082. sort : [Int] -> [Int] 2IThat Haskell sort function often misleadingly referred to as "quicksort". naiveSort : [Int] -> [Int] 3+Apply a function to each element of a list. map : (a -> b) -> [a] -> [b] 4Equality of lists of integers. )equals_List_Int : [Int] -> [Int] -> Bool 5Length of a list. length : [a] -> Int 6\Zip two lists into one. If one list is longer than the other ignore the exceeding elements. Vzip [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)] 7Zip two lists into one using a user-specified combining function. If one list is longer than the other ignore the exceeding elements. WzipWith (+) [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] 8Force the spine of a list. forceSpine :: [a] -> [a] $%&'()*+,-./012345678$%&'()*+,-./012345678$%.&'()*+,-/012345678$%&'()*+,-./012345678 None9*Convert a Haskell value to an STG binding.4Instances 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, ;y, this is hidden from the outside. If you want to write your own instance, have a look at the source for documentation.;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 s  function."Prefix for all generated variablesoThis definition unifies the creation of tuple bindings to reduce code duplication between the tuple instances.<>ppr (toStg "quintuple" ((1,2,3,4,5) :: (Int,Int,Int,Int,Int)))quintuple = \ => let __v = \ -> Int# 1#; __w = \ -> Int# 2#; __x = \ -> Int# 3#; __y = \ -> Int# 4#; __z = \ -> Int# 5#$ in Quintuple __v __w __x __y __z=8ppr (toStg "quadruple" ((1,2,3,4) :: (Int,Int,Int,Int)))quadruple = \ => let __w = \ -> Int# 1#; __x = \ -> Int# 2#; __y = \ -> Int# 3#; __z = \ -> Int# 4# in Quadruple __w __x __y __z>/ppr (toStg "triple" ((1,2,3) :: (Int,Int,Int))) triple = \ => let __x = \ -> Int# 1#; __y = \ -> Int# 2#; __z = \ -> Int# 3# in Triple __x __y __z?'ppr (toStg "pair" ((1,2) :: (Int,Int))) pair = \ => let __fst = \ -> Int# 1#; __snd = \ -> Int# 2# in Pair __fst __snd@ ppr (toStg "list" ([] :: [Int]))list = \ => nil;nil = \ -> Nil#ppr (toStg "list" [1, 2, 3 :: Int]) list = \ =>$ letrec __0_value = \ -> Int# 1#;G __1_cons = \(__1_value __2_cons) -> Cons __1_value __2_cons;$ __1_value = \ -> Int# 2#;9 __2_cons = \(__2_value) -> Cons __2_value nil;# __2_value = \ -> Int# 3# in Cons __0_value __1_cons;nil = \ -> NilA1ppr (toStg "either" (Left 1 :: Either Int [Int])) either = \ => let __leftval = \ -> Int# 1# in Left __leftval2ppr (toStg "either" (Right 2 :: Either [Int] Int)) either = \ =>! let __rightval = \ -> Int# 2# in Right __rightvalB*ppr (toStg "maybe" (Nothing :: Maybe Int))maybe = \ => nothing;nothing = \ -> Nothing)ppr (toStg "maybe" (Just 1 :: Maybe Int)) maybe = \ => let __justVal = \ -> Int# 1# in Just __justValCppr (toStg "bool" True)bool = \ -> TrueD Same as the 1 instance, but makes for shorter type annotationsE ppr (toStg "int" (1 :: Integer))int = \ -> Int# 1#Fppr (toStg "unit" ())unit = \ -> Unit9:;Name of the tuple binding*Name of the tuple constructor, e.g. "Pair"Bindings of the entries<=>?@ABCDEF9:;9:;9:;<=>?@ABCDEF NoneGFirst element of a tuple. fst : (a,b) -> a HSecond element of a tuple. snd : (a,b) -> a I/Convert an uncurried function to a curried one. %curry : ((a, b) -> c) -> a -> b -> c J/Convert a curried function to an uncurried one. 'uncurry : (a -> b -> c) -> (a, b) -> c KSwap the elements of a tuple. swap : (a,b) -> (b,a) L$Equality of pairs of boxed integers.GHIJKLGHIJKLGHIJKLGHIJKLNoneM+Force a value to normal form and return it.nThis function makes heavy use of the fact that the STG is untyped. It currently supports the following types: Unit (Unit)Maybe (Just, Nothing)Bool (True, False) Int (Int#)Either (Left, Right)Tuples (Pair, Triple)List (Nil, Cons)'Everything else will run into an error.M5    !"#$%&'()*+,-./012345678GHIJKLMMMNone9;[NBOverloading class for determining the free variables of an object.XOnly takes into account the explicit free variable list of the lambda. This means that globals, which are not explicitly free, will not be considered free variables.NOPQRSTUVWXYZ[\NONONOPQRSTUVWXYZ[\6NoneDR]The usual stack data structure.`UPush a list of items onto the stack. The first item will be at the top of the stack.a/For each list element, pop one element off the ]+. Fail if not enough elements are present.bLike .0 for lists.]^_`abcdefghij]^_`ab]^_a`b ]^_`abcdefghijNone-59:;<=DIR[\,mgHeap objects are what is stored on the heap. The most common and also most important one are closures.oeWhen an updatable closure is entered, it is overwritten by a black hole. This has two main benefits: dMemory mentioned only in the closure is now ready to be collected, avoiding certain space leaks.Entering a black hole means a thunk depends on itself, allowing the interpreter to catch some non-terminating computations with a useful errorTo 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.p6The heap stores closures addressed by memory location.rKA closure is a lambda form, together with the values of its free variables.tbUsed to store meta-information about state transitions in order to be rendered as a helpful hint.Like , but for invalid transitions.scrutinee arity, pattern arity?Type safety wrapper to report variables that were not in scope.KClassifies which rule has been applied in order to reach the current state.Short machine status info. This field may be used programmatically, in particular it tells the stepper whether the machine has halted.4There is no valid state transition to continue with.<The machine did not halt within a number of steps. Used by 1.DThe machine halted because a user-specified halting predicate held.pThe 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 # state with an empty return stack.CDescription of the state transition that lead to the current state..Used to mark the initial state of the machine.CA garbage collection step, in which no ordinary evaluation is done.;User-facing information about the current state of the STG.bThe global environment consists if the mapping from local definitions to their respective values.fThe global environment consists of the mapping from top-level definitions to their respective values."A single key -> value association.DUsed to make 2-tuples to be inserted into association maps clearer.,The different code states the STG can be in.1Evaluate an expression within a local environment*Load the closure at a certain heap address-Sub-computation terminated with an algebraic $uctor3Sub-computation terminated with a primitive integerA value of the STG machine.A memory address.3Stack frames unify arguments, returns, and updates.Argument frames store values on the argument stack, so that they can later be retrieved when the calling function can be applied to them.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.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.The internal state of an STG.%Operation the STG should perform nextThe 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.8The heap stores values allocated at the top level or in let(rec) expressions.8The environment consisting of the top-level definitions.NA counter, used to generte fresh variable names and for orientation purposes.#Information about the current state?Local re-definition to avoid cyclic import with the Heap modulePrettyprint a ].Prettyprint a ,  key -> value.Prettyprint an arity.Flet ppr = Data.Text.IO.putStrLn . Stg.Language.Prettyprint.renderPlainfor_ [0..5] (ppr . pprArity)nullaryunarybinaryternary4-ary5-ary4Prefix all contained documents with a bullet symbol.mnopqrstuvwxyz{|}~dmnopqrstuvwxyz{|}~drspqmnotuvwxyz{|}~9mnopqrstuvwxyz{|}~ None>0Add a list of bindings to the local environment.?Already existing variables will be shadowed (i.e. overwritten).?3Create a local environment from a list of bindings.@Look up the value of an &5 first in the local, then in the global environment.ALook up the values of many &Vs, and return their values in the input's order, or a list of variables not in scope.B9Look up the value of a variable in the local environment.C:Look up the value of a variable in the global environment.>?@ABC>?@ABC>?@ABC>?@ABCNone9;[DYUpdate all contained addresses in a certain value. Useful for moving garbage collectors.F5Collect all mentioned addresses in a machine element.Note that none of the types in  Stg.LanguageJ 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.GJAll contained addresses in the order they appear, but without duplicates.BAll contained addresses in the order they appear, with duplicates.HTA garbage collection algorithm is a specific way to get rid of unused heap objects.I  Algorithmname ( state -> ( dead addresses,  moved addresses,  newstate)JSplit 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.DEFGHIJKLMNOPQRSTUVWXYZDEFGHIJJHIFGDEDEFGHIJKLMNOPQRSTUVWXYZNone9;lEach closure is in one of three states: in the alive heap, staged for later rescue, or not even staged yet.HHeap of closures known to be alive. Has no overlap with the old heap.MMemory addresses known to be alive, but not yet rescued from the old heap.GThe old heap, containing both dead and not-yet-found alive closures.[7Remove all unused addresses, without moving the others. [[[[None_%Current number of elements in a heap.`Look up a value on the heap.aUpdate a value on the heap.bUpdate many values on the heap.c/Store a value in the heap at an unused address.dSStore many values in the heap at unused addresses, and return them in input order._`abcd_`abcd_`abcd_`abcdNone eaPage 39, 2nd paragraph: "[...] closures with non-empty argument lists are never updatable [...]"fPage 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."geA function was applied to an argument that was neither globally defined nor in the local environmenthhA constructor was applied to an argument that was neither globally defined nor in the local environmentipA primitive operation was applied to an argument that was neither globally defined nor in the local environmentjGAlgebraic constructor return, but primitive alternative on return framek;Primitive return, but algebraic alternative on return framelUA black hole was entered, and the infinite recursion detection triggered as a resultm)Closures are always lifted, not primitivenNon-algebraic scrutinee"For more information on this, see /.o,A primitive division had zero as denominatorpYBad constructor arity: different number of arguments in code segment and in return frame efghijklmnop efghijklmnop efghijklmnop efghijklmnopNoneCSmart constructor to avoid generating info if nothing was discardedqRule 1: Function applicationFPush argument values onto the stack, and enter the function's address.r#Rule 2: Enter non-updatable closurekFetch all arguments from the stack, bind them to the lambda's variables, and continue evaluating the body. Create a r out of a W, given a local environment.sRule 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.tRule 4: Case evaluationWPush 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.uRule 5: Constructor applicationSimply transition into the  state.v4Rule 6: Algebraic constructor return, standard matchContinue with the branch of the matched constructor, extending the local environment with the matched pattern variables' values.w;Rule 7: Algebraic constructor return, unbound default matchTNone of the given alternatives matched, so simply continue with the default branch.x9Rule 8: Algebraic constructor return, bound default matchNone 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.yRule 9: Literal evaluationSimply transition into the  state.zRule 10: Literal applicationSimply transition into the  state.{/Rule 11: Primitive return, standard match foundLike t, but for primitives.|.Rule 12: Primitive return, bound default match Similar to x, 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.}0Rule 13: Primitive return, unbound default matchLike w, but for primitives.~'Rule 14: Primitive function applicationzThis 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 _, which handles primitive application more efficiently, without the need for an intermediate  state. Rule 15: Enter updatable closureDEvaluate the address pointed to, and store its future update in an ."In theory this could just do what r does, plus the update frame. However, since lambda forms that take arguments never form updatable closures, there is no need for  handling in this rule.#Rule 16: Update because of missing A  state requires a  to continue, but there is an  in the way. The latter has to be eliminated by performing an update with the returned constructor before attempting the return once more.Are there enough is on the stack to fill the args parameter? If so, return those frames, along with the rest of the stack.ERule 17: Enter partially applied closure, update because of missing There are not enough ArgFrameXs 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.FRule 17a: Enter partially applied closure, update because of missing This is a better version of rule 17, since it does not neccessitate runtime code generation. All required closures can be precompiled.6Rules 18, 19: Shortcut for evaluating/matching primopsThis 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 t.zWhen reading the source here for educational purposes, you should skip this rule until you've seen the normal case rule (t) and the normal primop rule (~).wThis rule has the slight modification compared to the paper in that it works for both bound and unbound default cases.qrstuvwxyz{|}~qrstuvwxyz{|}~qrstuvwxyz{|}~qrstuvwxyz{|}~None-Perform a single STG machine evaluation step.eTransition rules detailed in the 1992 paper, along with error rules to help if none of them applies.EThis is the place to modify the ruleset of the machine, for example 23T can be removed to yield a less efficient, yet equally correct, STG implementation.KApply a single applicable STG evaluation rule to continue to the next step.,Fallback if none of the known rules applies.None9;I[\#Heap of closures known to be alive.HForward pointers to the new locations of already collected heap objectscHeap objects already evacuated, but not yet scavenged. Contains only objects that are also in the toHeap.6Heap objects known to be alive, but not yet evacuated.UMove all used addresses by moving them to a safe location, and delete the leftovers.Copy a closure from from-space to to-space, if it has not been evacuated previously. Copying to to-space involves a new allocation in to-space, registering the copied address to be scavenged, and creating a forwarding entry so that further evacuations can short-circuit.cFind referenced addresses in a heap object, and overwrite them with their evacuated new addresses.          None9;wApply a garbage collection algorithm to the heap of the current machine state, and return the resulting cleaned state.H[H[NoneQDecide whether garbage collection should be attempted, and with which algorithm.4Predicate to decide whether the machine should halt.4Predicate to decide whether the machine should halt.-Do not terminate based on the number of steps+Create a suitable initial state for an STG.`Evaluate the STG until a predicate holds, aborting if the maximum number of steps are exceeded.  ( ...) "a  5Evaluate the STG, and record all intermediate states.Stop when a predicate holds.1Stop if the maximum number of steps are exceeded.Perform GC on every step.  "H unfoldr  "Check whether a state is terminal.MainMaximum number of steps allowedHalting decision function#Condition under which to perform GC Initial state Final stateMaximum number of steps allowedHalting decision function#Condition under which to perform GC Initial state&Initial state plus intermediate statesH[H[None[[Classifies the different errors that can happen when extracting a value from an STG state.e.g. asking for an Int#" at an address that contains a Cons"Tried retrieving a non-constructorTried retrieving a black holee.g.  Cons x y zAn unsuccessful variable lookup]None of the given alternatives matched the given constructor, e.g. when trying to receive a  as a 'Look up the value of a global variable.4Instances 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).(Retrieve the value of a global variable.%Retrieve the value of a heap address.,Used only for looking up primitive integers.7Look up the global of a variable and handle the result.Slighly bent version of C) to fit the types in this module better.Create a local environment.Slighly bent version of ?) to fit the types in this module better.Look up the value of an &' in a state, given a local environment.TInspect whether a closure at a certain memory address matches the desired criteria.ZLift an errable value into a context where the specific error is not necessarily present.Like  matchCon2, but for nullary $uctors.Like  matchCon2, but for unary $uctors.Match a r for a binary $uctor.eIf the constructor matches, return its arguments, and the local environment stored in the closure.*If the constructor does not match, return M as error, indicating to the caller that the next matcher should be tried.tIf the constructor fails due to a non-recoverable error, such as wrong arity, abort with the corresponding error.Like  matchCon2, but for ternary $uctors. Like  matchCon2, but for 4-ary $uctors.!Like  matchCon2, but for 5-ary $uctors.Works for both boxed (Int# 1#) and unboxed (1# ) integers.!"What to do with the value if found#Name of the global value to inspectHList of possible matches, e.g. Nil and Cons in the list case. See e.g.  matchCon2& in order to implement these matchers. !   !4None 9: 9:NoneA 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 main4 closure, and shows how nested functions result in let allocations. A program that adds two numbers.-A program that measures the length of a list.pNegate a list of booleans, but non-strictly. This program does almost nothing, because nothing forces the list.#Negate a list of booleans strictly."'Program to sum up a list, but with the sum function left undefined.Sum up a list of s using sum = 56 (#) 0 MThis is a good way to sum up a list in Haskell, as it runs in constant space.Sum up a list of s using sum = 56 (#) 0 where 56 is implemented via $ as foldl' f z ys = $ (x xs acc -> xs % f acc x) id ys z which is a standard "56 in terms of $M" definition. This definition is denotationally equivalent to the standard 56,, but has a bit more computational overhead.Sum up a list of s using sum = & (#) 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 &! 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 up a list of s using sum = $ (#) 0  Like the & version demonstrated in , 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.VCompute 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 = ' (#) fibo (( fibo) in 57 ) fibo ]Calculate the n-th Fibonacci number using the computationally (horribly) inefficient formula 1fib n | n <= 1 = n fib n = fib (n-1) + fib (n-2) qThis implementation is stack-only, so enjoy watching it explode. At the time of writing this, the machine takes: fib 0 => 27 stepsfib 1 => 27 stepsfib 2 => 122 stepsfib 3 => 218 stepsfib 4 => 410 stepsfib 5 => 698 stepsfib 6 => 1178 stepsfib 7 => 1946 stepsfib 8 => 3194 stepsfib 9 => 5210 stepsfib 10 => 8474 stepsDCalculate the n-th Fibonacci number using the more efficient formula Vfib = 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.*$List concatenation example with the + definition left out.&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.%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.mSort 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].,Sort a list with a translation of Haskell's 89J, which is an implementation of mergesort with ordered sublist detection.&This is a naive implementation of the - function, - x = x : - 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 H! Also note how long it takes to generate two successive list elements.2The reason for this behaviour is that the call to - 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.&This uses a much better definition of -, -5 x = let repeatX = x : repeatX in repeatX xThis program does only a total of three heap allocations before continuously running without interruption: one for the repeatedH value, one for the self-referencing cons cell, and one because of how 8 works.[Note how much smaller the cycles between the traversal of two neighbouring list cells are!"*"*.:;<:;=:;>?@ABCDEFGHIJKLMNOPQRSMGTUVWXYZ[\]^^-_`aa,bcdefghijkl++*mn))((opqr&&%stuvwxyz{|}~$$##""      !"# $%&'(/)*+, - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > 6 ? @ A B  C D E F 9 G  H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ `abcdefghijklmnopqrstu0vwxyz{|}~!!      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~bcd1G             JF !"#$%&'(5?)5>K*+,-5./E0stgi-1.1-LT0PoB9W7KUFnIHxeV3rhx Stg.LanguageStg.UtilStg.Language.PrettyprintStg.Machine.Evaluate.CommonStg.Parser.ParserStg.Parser.QuasiQuoterStg.Prelude.BoolStg.Prelude.FunctionStg.Prelude.MaybeStg.Prelude.NumberStg.Prelude.ListStg.Marshal.ToStgStg.Prelude.Tuple Stg.PreludeStg.StaticAnalysis Data.StackStg.Machine.TypesStg.Machine.Env$Stg.Machine.GarbageCollection.Common-Stg.Machine.GarbageCollection.TriStateTracingStg.Machine.Heap%Stg.Machine.Evaluate.ErrorTransitions%Stg.Machine.Evaluate.ValidTransitionsStg.Machine.Evaluate-Stg.Machine.GarbageCollection.TwoSpaceCopyingStg.Machine.GarbageCollection Stg.MachineStg.Marshal.FromStgStg.ExampleProgramsmapfilterstgClosureProgramBinds LambdaFormExprAltsAlt AlgebraicAlt PrimitiveAlt DefaultAltLiteralPrimOpAtomPreludeseqspan evalUntilValidrule1819 Stg.Marshal Data.Foldablefoldl' traverse_ Data.Listsort*prettyprinter-1.1.1-6YKgnwXYcz97cHm9ZPxgvY"Data.Text.Prettyprint.Doc.Internal prettyListprettyPrettyValidateFailureSuccessshow'commaSep$fApplicativeValidate$fBifunctorValidate$fFunctorValidateAstAnnKeywordPrimVariable Constructor SemicolonStateAnnHeadlineAddress AddressCore ClosureTypeStackFrameTypeStgiAnn PrettyStgi prettyStgi renderRich renderPlainprettyprintOldAnsi$fPrettyStgi[]$fPrettyStgi(,)$fPrettyStgiInteger$fPrettyStgiInt$fPrettyStgiBoolConstrAtomVarAtomLitVarAddSubMulDivModEqLtLeqGtGeqNeqDefaultNotBound DefaultBoundNonDefaultAltsNoNonDefaultAlts AlgebraicAlts PrimitiveAltsLetCaseAppFAppCAppPLitERec NonRecursive Recursive UpdateFlagUpdateNoUpdate LambdaType LambdaCon LambdaFun LambdaThunkclassify$fIsStringConstr $fIsStringVar$fPrettyStgiLambdaType $fShowBinds$fSemigroupBinds $fMonoidBinds$fSemigroupProgram$fMonoidProgram$fEqLambdaType$fOrdLambdaType$fShowLambdaType$fEqUpdateFlag$fOrdUpdateFlag$fShowUpdateFlag$fGenericUpdateFlag$fEnumUpdateFlag$fBoundedUpdateFlag$fEqRec$fOrdRec $fShowRec $fGenericRec $fEnumRec $fBoundedRec $fEqLiteral $fOrdLiteral $fShowLiteral$fGenericLiteral $fEqPrimOp $fOrdPrimOp $fShowPrimOp$fGenericPrimOp$fBoundedPrimOp $fEnumPrimOp$fEqVar$fOrdVar $fShowVar $fGenericVar$fEqAtom $fOrdAtom $fShowAtom $fGenericAtom $fEqConstr $fOrdConstr $fShowConstr$fGenericConstr$fEqExpr $fOrdExpr $fShowExpr $fGenericExpr$fEqAlts $fOrdAlts $fShowAlts $fGenericAlts$fEqDefaultAlt$fOrdDefaultAlt$fShowDefaultAlt$fGenericDefaultAlt$fEqNonDefaultAlts$fOrdNonDefaultAlts$fShowNonDefaultAlts$fGenericNonDefaultAlts$fEqPrimitiveAlt$fOrdPrimitiveAlt$fShowPrimitiveAlt$fGenericPrimitiveAlt$fEqAlgebraicAlt$fOrdAlgebraicAlt$fShowAlgebraicAlt$fGenericAlgebraicAlt $fEqBinds $fOrdBinds$fGenericBinds$fEqLambdaForm$fOrdLambdaForm$fShowLambdaForm$fGenericLambdaForm $fEqProgram $fOrdProgram $fShowProgram$fGenericProgram prettyLambda$fNFDataConstr $fNFDataAtom $fNFDataVar$fNFDataPrimOp$fNFDataLiteral$fNFDataDefaultAlt$fNFDataPrimitiveAlt$fNFDataAlgebraicAlt$fNFDataNonDefaultAlts $fNFDataAlts $fNFDataExpr $fNFDataRec$fNFDataUpdateFlag$fNFDataLambdaForm $fNFDataBinds$fNFDataProgram$fPrettyStgiConstr$fPrettyStgiAtom$fPrettyStgiVar$fPrettyStgiPrimOp$fPrettyStgiLiteral$fPrettyStgiDefaultAlt$fPrettyStgiPrimitiveAlt$fPrettyStgiAlgebraicAlt$fPrettyStgiAlts$fPrettyStgiExpr$fPrettyStgiRec$fPrettyStgiLambdaForm$fPrettyStgiBinds$fPrettyStgiProgram $fLiftVar $fLiftConstr $fLiftBinds$fLiftNonDefaultAlts $fLiftAtom $fLiftPrimOp$fLiftDefaultAlt$fLiftPrimitiveAlt$fLiftAlgebraicAlt $fLiftAlts $fLiftExpr $fLiftRec$fLiftUpdateFlag$fLiftLambdaForm $fLiftLiteral $fLiftProgramAltErrorBadAltAltMatch AltMatchesDefaultMatches PrimErrorDiv0 applyPrimOplookupAlgebraicAltlookupPrimitiveAlt StgParserparsevarconprogrambinds lambdaFormexpraltsatomprimOpliteralnonDefaultAlts algebraicAlt primitiveAlt defaultAlt$fTokenParsingStgParser$fCharParsingStgParser$fParsingStgParser$fAlternativeStgParser$fApplicativeStgParser$fFunctorStgParser$fMonadStgParsereq_Booland2or2notboolidconstcomposefixnothingmaybeeq_Intlt_Intleq_Intgt_Intgeq_Intneq_Intaddsubmuldivmodminmaxnilconcat2foldlfoldriteratecycletake partitionreverserepeat replicate naiveSortequals_List_IntlengthzipzipWith forceSpineToStgtoStgtoStgWithGlobals $fToStg(,,,,) $fToStg(,,,) $fToStg(,,) $fToStg(,) $fToStg[] $fToStgEither $fToStgMaybe $fToStgBool $fToStgInt$fToStgInteger $fToStg()fstsndcurryuncurryswapequals_Pair_Intforce FreeVariables freeVariables$fFreeVariablesAtom$fFreeVariablesLiteral$fFreeVariablesVar$fFreeVariablesDefaultAlt$fFreeVariablesPrimitiveAlt$fFreeVariablesAlgebraicAlt$fFreeVariablesNonDefaultAlts$fFreeVariablesAlts$fFreeVariablesLambdaForm$fFreeVariablesExpr$fFreeVariablesBinds$fFreeVariablesProgram$fFreeVariablesfStackEmpty:<<>> forEachPop $fNFDataStack $fIsListStack$fSemigroupStack $fMonoidStack$fFoldableStack$fFunctorStack $fPrettyStack $fShowStack $fEqStack $fOrdStack HeapObjectHClosure BlackholeHeap InfoDetailDetail_FunctionApplicationDetail_UnusedLocalVariablesDetail_EnterNonUpdatableDetail_EvalLetDetail_EvalCaseDetail_ReturnCon_MatchDetail_ReturnConDefBoundDetail_ReturnIntDefBoundDetail_EnterUpdatableDetail_ConUpdateDetail_PapUpdateDetail_ReturnIntCannotUpdateDetail_StackNotEmptyDetail_GarbageCollectedDetail_EnterBlackHole!Detail_UpdateClosureWithPrimitiveDetail_BadConArity StateErrorVariablesNotInScopeUpdatableClosureWithArgsReturnIntWithEmptyReturnStackAlgReturnToPrimAltsPrimReturnToAlgAltsInitialStateCreationFailedEnterBlackholeUpdateClosureWithPrimitiveNonAlgPrimScrutineeDivisionByZero BadConArity NotInScopeStateTransitionRule1_Eval_FunctionApplicationRule2_Enter_NonUpdatableClosureRule3_Eval_LetRule4_Eval_CaseRule5_Eval_AppCRule6_ReturnCon_MatchRule7_ReturnCon_DefUnboundRule8_ReturnCon_DefBound Rule9_Lit Rule10_LitAppRule11_ReturnInt_MatchRule12_ReturnInt_DefBoundRule13_ReturnInt_DefUnboundRule14_Eval_AppPRule15_Enter_UpdatableClosureRule16_ReturnCon_Update#Rule17_Enter_PartiallyAppliedUpdate$Rule17a_Enter_PartiallyAppliedUpdate"Rule1819_Eval_Case_Primop_Shortcut InfoShort NoRulesApplyMaxStepsExceededHaltedByPredicate StateInitialGarbageCollectionInfoLocalsGlobalsMappingCodeEvalEnter ReturnCon ReturnIntValueAddrPrimIntMemAddr StackFrame ArgumentFrame ReturnFrame UpdateFrameStgStatestgCodestgStackstgHeap stgGlobalsstgStepsstgInfo$fNFDataHeapObject $fNFDataHeap$fNFDataClosure$fNFDataInfoDetail$fNFDataStateError$fNFDataNotInScope$fNFDataStateTransition$fNFDataInfoShort $fNFDataInfo$fNFDataLocals$fNFDataGlobals$fNFDataMapping $fNFDataCode $fNFDataValue$fNFDataMemAddr$fNFDataStackFrame$fNFDataStgState$fPrettyStgiHeapObject$fPrettyStgiHeap$fPrettyStgiClosure$fPrettyStgiInfoDetail$fPrettyStgiStateError$fPrettyStgiNotInScope$fPrettyStgiStateTransition$fPrettyStgiInfoShort$fPrettyStgiInfo$fPrettyStgiLocals$fPrettyStgiGlobals$fPrettyStgiMapping$fPrettyStgiCode$fPrettyStgiValue$fPrettyStgiMemAddr$fPrettyStgiStackFrame$fPrettyStgiStgState $fEqMemAddr $fOrdMemAddr $fShowMemAddr $fEnumMemAddr$fBoundedMemAddr$fGenericMemAddr $fEqValue $fOrdValue $fShowValue$fGenericValue $fEqMapping $fOrdMapping $fShowMapping$fGenericMapping $fEqGlobals $fOrdGlobals $fShowGlobals$fSemigroupGlobals$fMonoidGlobals$fGenericGlobals $fEqLocals $fOrdLocals $fShowLocals$fSemigroupLocals$fMonoidLocals$fGenericLocals$fEqCode $fOrdCode $fShowCode $fGenericCode$fEqStackFrame$fOrdStackFrame$fShowStackFrame$fGenericStackFrame$fEqStateTransition$fOrdStateTransition$fShowStateTransition$fGenericStateTransition$fEqNotInScope$fOrdNotInScope$fShowNotInScope$fGenericNotInScope$fSemigroupNotInScope$fMonoidNotInScope$fEqStateError$fOrdStateError$fShowStateError$fGenericStateError $fEqInfoShort$fOrdInfoShort$fShowInfoShort$fGenericInfoShort$fEqInfoDetail$fOrdInfoDetail$fShowInfoDetail$fGenericInfoDetail$fEqInfo $fOrdInfo $fShowInfo $fGenericInfo $fEqClosure $fOrdClosure $fShowClosure$fGenericClosure$fEqHeapObject$fOrdHeapObject$fShowHeapObject$fGenericHeapObject$fEqHeap $fOrdHeap $fShowHeap $fGenericHeap$fSemigroupHeap $fMonoidHeap $fEqStgState $fOrdStgState$fShowStgState$fGenericStgState addLocals makeLocalsvalvalslocalVal globalVal UpdateAddrs updateAddrs AddressesaddrsGarbageCollectionAlgorithm splitHeapWith$fUpdateAddrsStackFrame$fUpdateAddrsf$fUpdateAddrsMemAddr$fUpdateAddrsValue$fUpdateAddrsGlobals$fUpdateAddrsLocals$fUpdateAddrsCode$fAddressesValue$fAddressesHeapObject$fAddressesClosure$fAddressesLocals$fAddressesGlobals$fAddressesMemAddr$fAddressesStackFrame$fAddressesCode $fAddressesftriStateTracing $fEqGcState $fOrdGcState $fShowGcStatesizelookupupdate updateManyalloc allocManyupdatableClosureWithArgsreturnWithEmptyReturnStackfunctionArgumentNotInScopeconstructorArgumentNotInScopeprimopArgumentNotInScopealgReturnToPrimAltsprimReturnToAlgAltsenterBlackholeupdateClosureWithPrimitivenonAlgPrimScrutineedivisionByZero badConArityrule1_functionApprule2_enterNonUpdatable rule3_let rule4_caserule5_constructorApprule6_algebraicNormalMatch"rule7_algebraicUnboundDefaultMatch rule8_algebraicBoundDefaultMatchrule9_primitiveLiteralEvalrule10_primitiveLiteralApprule11_primitiveNormalMatch!rule12_primitiveBoundDefaultMatch#rule13_primitiveUnboundDefaultMatch rule14_primoprule15_enterUpdatablerule16_missingReturnUpdaterule17_missingArgUpdaterule17a_missingArgUpdaterule1819_casePrimopShortcutevalSteptwoSpaceCopying $fFunctorGc$fApplicativeGc $fMonadGcgarbageCollect PerformGcHaltIf RunForStepsRunIndefinitelyRunForMaxSteps initialState evalsUntil terminated $fEqAttemptGc$fOrdAttemptGc$fShowAttemptGc FromStgError TypeMismatchIsWrongLambdaType IsBlackholeBadArityNotFound AddrNotOnHeapNoConstructorMatchFromStgfromStg fromStgAddr fromStgPrim $fFromStg[]$fFromStgEither$fFromStgMaybe$fFromStg(,,,,)$fFromStg(,,,) $fFromStg(,,) $fFromStg(,)$fFromStgInteger $fFromStgBool $fFromStg()$fEqFromStgError$fOrdFromStgError$fShowFromStgErrorimplies addTwoNumberscalculateLengthmapNot mapNotForced sum_foldl'sum_foldl'ViaFoldr sum_foldl sum_foldrfibonacciZipWithfibonacciNaivefibonacciImprovedlistConcatRightAssociatedlistConcatLeftAssociated librarySort repeatNaive repeatSharingbase Data.EitherEitherGHC.Base ApplicativeGHC.Showshow#text-1.2.2.2-KC7dWoG09dA1F6jKj5GSqhData.Text.InternalText Data.Textpack layoutOptionsMonoidsemicolonTerminated skipTokenvarIdreservedarrowcommentstgQQ defaultQuoterbinaryOp primToBool primIdInttransformers-0.5.2.0Control.Monad.Trans.Writer.LazyWritertell genPrefix tupleBinds integer-gmpGHC.Integer.TypeInteger tupleEntry-<> bindNamesheapSize prettyStack prettyMapcontainers-0.5.7.1 Data.Map.BaseMappprArity bulletListpluralSaddrs'nubSeqGcState aliveHeapstagedoldHeap insert2ndseqToSeteverythingCollectedgcStepmkDetail_UnusedLocalVariablesliftLambdaToClosurepopArgsUntilUpdate isArgFramerulesstgRule noRulesApplytoHeapforwards toScavenge toEvacuateevacuatescavengeEvacuationStatusNotEvacuatedYetAlreadyEvacuatedToGcaskHeap getGcState putGcStateexecGcevacuateScavengeLoopinitialEvacuation scavengeLoopGHC.Listlast AttemptGc GcPossibleSkipGcLeftJustatomValinspect liftToMatcher matchCon0 matchCon1 matchCon2Nothing matchCon3 matchCon4 matchCon5 sumTemplateGHC.Num+$!tail System.IOprintlistConcatTemplateconcat++