w&F      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnop q r s t u v w x y z { | } ~        !"#$%&'()*+,-./0123456789:;<=>?@ABCDESafeThe validation version of F.G with H as codomain. show' = I . G  [a,b,c] ==> a, b, c4Prefix all contained documents with a bullet symbol. #Add an 's' for non-singleton lists.J2Return success or the accumulation of all failures  KJL   KJLSafeU Prettyprint a value as H#, including styles such as colours. Prettyprint a value as H6, stripped off all style information such as colours. M   MNone0U3 %Constructors of algebraic data types.eSmallest unit of data. Atoms unify variables and literals, and are what functions take as arguments. Variable.Primitive operations. + - * / % == < <= > >= /=/Literals are the basis of primitive operations.!<If no viable alternative is found in a pattern match, use a ! as fallback.$As in 1#, 2#, 3#&As in  True | False(The part of a 0$ alternative that's not the default.)Used in 'case'g statements that consist only of a default alternative. These can be useful to force or unpack values.*Algebraic alternative, like  Cons x xs.+Primitive alternative, like 1#.,#List of possible alternatives in a 0 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.."An expression in the STG language./Let expression let(rec) ... in ...0Case expression case ... of ... x -> y1Function application f x y z2"Saturated constructor application Just a3Primitive function application + 1 2#4Literal expression 1#5Distinguishes let from letrec.8JThe update flag distinguishes updateable from non-updateable lambda forms.The former will be overwritten in-place when it is evaluated, allowing the calculation of a thunk to be shared among multiple uses of the same value.;(Possible classification of lambda forms.<Data constructor (2 as body)=.Function (lambda with non-empty argument list)>Thunk (everything else)?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 |]iLambdaForm [Var "x"] NoUpdate [Var "y",Var "z"] (AppF (Var "expr") [AtomVar (Var "x"),AtomVar (Var "z")])AABindings are collections of lambda forms, indexed over variables.>They exist at the top level, or as part of a let(rec) binding.C$An STG program consists of bindings.NAPackage of style definitions used for prettyprinting the STG AST.O Keyword styleP+Primitive style, for literals and functionsQVariable styleRConstructor styleS8Semicolons separating lists of bindings and alternativesT'Colour definitions used by the STG AST.E6Classify the type of a lambda form based on its shape.U Right-biased union of binds. This makes it easier to overwrite modify definitions from other programs. For example, if you have one program that has a certain definition of V, you can write )program' = program <> [stg| map = ... |]  to make it use your own version.W,Left-biased union of the contained bindings.FPrettyprint a ?3, given prettyprinters for the free variable list.Introduced so ; can hijack it to display the free value list differently.m  !"#$%&'()*+,-./0123456789:;<=>?@ABCDNXOPQRSTEYZ[\UW]FFree variable list printer^_`abcdefghijklmnopqrstuvwxyz{|}~>  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEF>CDAB?@F89:567./01234,-()*+&'$%!"#  E;<=>?    !"#$%&'()*+,-./0123456789:;<=>?@ABCDNXOPQRSTEYZ[\UW]F^_`abcdefghijklmnopqrstuvwxyz{|}~NoneCUG#A parser for an STG syntax element.HNParse STG source using a user-specified parser. To parse a full program, use H K.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.IJParse 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.JParse 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.KParse an STG program.L(Parse a collection of bindings, used by let(rec)0 expressions and at the top level of a program.MParse 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, ->.N!Parse an expression, which can belet, let(rec) ... in ...case, case ... of ...function application, f (...)constructor application, C (...)primitive application, p# (...) literal, 1#O"Parse the alternatives given in a case expression.QParse a primitive operation. +# SoParse non-default alternatives. The list of alternatives can be either empty, all algebraic, or all primitive. Nil -> ... Cons x xs -> ... 1# -> ... 2# -> ... T%Parse a single algebraic alternative. Cons x xs -> ... U.Parse a single primitive alternative, such as 1#.  1# -> ... VMParse the default alternative, taken if none of the other alternatives in a case expression match. default -> ...  v -> ... GHIJKLMNOPQRSTUVGHIJKLMNOPQRSTUVHGKLMNOSTUVRQPIJGHIJKLMNOPQRSTUVNoneWsHeuristic 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.XQuasiquoter for s.[program| id = \x -> x |]QProgram (Binds [(Var "id",LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") []))])YQuasiquoter for .[binds| id = \x -> x |]I(Binds [(Var "id",LambdaForm [] NoUpdate [Var "x"] (AppF (Var "x") []))])ZQuasiquoter 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") [])aQuasiquoter for $s.[literal| 1# |] Literal 1bQuasiquoter for %s.[primOp| +# |]AddcQuasiquoter for &s. [atom| x |]AtomVar (Var "x")W7Name of the parsed syntax element (for error reporting)XYZ[\]^_`abc WXYZ[\]^_`abc WXYZ[\]^_`abcWXYZ[\]^_`abcNonedNothing as a top-level closure. nothing : Maybe a eDeconstructor of the Maybe type. &maybe : b -> (a -> b) -> Maybe a -> b dedededeNonefBoolean equality.gBinary and. Haskell's (&&). && : Bool -> Bool -> Bool hBinary or. Haskell's (||). || : Bool -> Bool -> Bool iBinary negation. not : Bool -> Bool jBoolean deconstructor. &bool f _ False = f bool _ t True = t bool : a -> a -> Bool -> a fghijfghijghijffghijNonekFinally 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 lIdentity function.  id : a -> a mConstant function. Const : a -> b -> a nFunction composition. )compose : (b -> c) -> (a -> b) -> a -> c oThe fixed point combinator. fix : (a -> a) -> a klmnoklmnoklmnoklmno Nonepqrstuvwxyz{| pqrstuvwxyz{| vwxyzpqrstu{|pqrstuvwxyz{| 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] 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] *Repeat a single element a number of times. replicate 3 1 = [1, 1, 1] replicate : Int -> a -> [a] 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  requires 268082. sort : [Int] -> [Int] IThat Haskell sort function often misleadingly referred to as "quicksort". naiveSort : [Int] -> [Int] +Apply a function to each element of a list. map : (a -> b) -> [a] -> [b] Equality of lists of integers. )equals_List_Int : [Int] -> [Int] -> Bool Length of a list. length : [a] -> Int \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)] Zip 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] Force the spine of a list. forceSpine :: [a] -> [a] }~}~}~}~ NoneU*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 __z8ppr (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 = \ -> Nil1ppr (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 __rightval*ppr (toStg "maybe" (Nothing :: Maybe Int))maybe = \ => nothing;nothing = \ -> Nothing)ppr (toStg "maybe" (Just 1 :: Maybe Int)) maybe = \ => let __justVal = \ -> Int# 1# in Just __justValppr (toStg "bool" True)bool = \ -> True Same as the 1 instance, but makes for shorter type annotations ppr (toStg "int" (1 :: Integer))int = \ -> Int# 1#ppr (toStg "unit" ())unit = \ -> UnitName of the bindingName of the binding,Log: globals; value: value definition itselfName of the tuple binding*Name of the tuple constructor, e.g. "Pair"Bindings of the entries NoneFirst element of a tuple. fst : (a,b) -> a Second element of a tuple. snd : (a,b) -> a /Convert an uncurried function to a curried one. %curry : ((a, b) -> c) -> a -> b -> c /Convert a curried function to an uncurried one. 'uncurry : (a -> b -> c) -> (a, b) -> c Swap the elements of a tuple. swap : (a,b) -> (b,a)  None+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.4defghijklmnopqrstuvwxyz{|}~4ed}~ghijfvwxyzpqrstu{|klmnoNone>LThe usual stack data structure.UPush a list of items onto the stack. The first item will be at the top of the stack.dFor each list element, pop one element off the stack. Fail if not enough elements are on the stack.Like ') for lists.  None 0>CLUV*eWhen 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.6The heap stores closures addressed by memory location.KA closure is a lambda form, together with the values of its free variables.Type safety wrapper.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 *.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.,The different code states the STG can be in.1Evaluate an expression within a local environment*Load the closure at a certain heap address5Sub-computation terminated with algebraic constructor3Sub-computation terminated with a primitive integerA value of the STG machine.A memory address.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.1Package of style definitions used in this module.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.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.5A counter, used to generte fresh variable names from.#Information about the current state'Colour definitions used in this module.RA stack frame of the unified stack that includes arguments, returns, and updates.Prettyprint a .Prettyprint a ,  key -> value.hh9 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. Look up the values of many Vs, and return their values in the input's order, or a list of variables not in scope. 9Look up the value of a variable in the local environment.:Look up the value of a variable in the global environment.                    None%Current number of elements in a heap.Look up a value on the heap.Update a value on the heap.Update many values on the heap./Store a value in the heap at an unused address.SStore many values in the heap at unused addresses, and return them in input order.NoneUCSmart constructor to avoid generating info if nothing was discardedLook up an algebraic constructor among the given alternatives, and return the first match. If nothing matches, return the default alternative. for primitive literals.-Perform a single STG machine evaluation step.CApply a single STG evaluation rule, as specified in the 1992 paper.When there are no rules, the machine halts. But there are many different ways this state can be reached, so it's helpful to the user to distinguish them from each other.  None35UYUpdate all contained addresses in a certain value. Useful for moving garbage collectors.5Collect 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.JAll contained addresses in the order they appear, but without duplicates.BAll contained addresses in the order they appear, with duplicates.*Dead addresses, moved addresses, new stateSplit the heap contained in a machine state in two parts: the dead objects that can safely be discarded, and the alive ones that are still needed by the program.None35UlEach 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. None35CUV#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 .6Heap objects known to be alive, but not yet evacuated.>Remove all unused addresses by moving them to a safe location.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.None35UNoneU QDecide 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.  !"#$%&'Main(Maximum number of steps allowedHalting decision function#Condition under which to perform GC Initial state Final state)Maximum number of steps allowedHalting decision function#Condition under which to perform GC Initial state&Initial state plus intermediate states* !"#$%&'()*'()*"#$%& ! !"#$%&'()*NoneU,e.g. asking for an Int#" at an address that contains a Cons-"Tried retrieving a non-constructor.Tried retrieving a black hole/e.g.  Cons x y z0An unsuccessful variable lookup2]None of the given alternatives matched the given constructor, e.g. when trying to receive a   as a  3'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).4(Retrieve the value of a global variable.5%Retrieve the value of a heap address.6,Used only for looking up primitive integers. 7Look up the global of a variable and handle the result.Slighly bent version of ) 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 , but for nullary  uctors.Like , but for unary  uctors.Match a  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 , but for ternary  uctors.Like , but for 4-ary  uctors.Like , but for 5-ary  uctors.Boxed (Int# 1#) or unboxed (1#)!+,-./01234Name of the global, e.g. main56 "What to do with the value if found#Name of the global value to inspect  HList of possible matches, e.g. Nil and Cons in the list case. See e.g. & in order to implement these matchers. +,-./0123456 3456+,-./012+,-./0123456    +None +,-./01234 34+,-./012NoneU7 A program that adds two numbers.8-A program that measures the length of a list.!'Program to sum up a list, but with the sum function left undefined.9Sum up a list of s using sum = ,- (") 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 = ,- (") 0 where ,- is implemented via # as foldl' f z ys = # (x xs acc -> xs $ f acc x) id ys z which is a standard ",- in terms of #M" definition. This definition is denotationally equivalent to the standard ,-,, 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 ,. ( 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 steps?DCalculate the n-th Fibonacci number using the more effective 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 examle, calculating the 10th Fibonacci number (55) takes only 490 steps, compared to the many thousand 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.A%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.BmSort 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].C,Sort a list with a translation of Haskell's /0J, which is an implementation of mergesort with ordered sublist detection.D&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 EH! 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.E&This uses a much better definition of ,, ,5 x = let repeatX = x : repeatX in repeatX wThis program does only a total of three heap allocations before continously running without interruption: one for the repeatedH value, one for the self-referencing cons cell, and one beacuse of how  works.ZNote how much smaller the cycles between the traversal of two neighbouring list cells is!78!9:;<=>?)@ABCDE789:;<=>?@ABCDE789:;<>?=@ABCDE78!9:;<=>?)@ABCDE-1231241256789:;<=>??&@ABB%CDEFGHIJKLM$$#NO""!!PQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvjklmnrstuqpowxyz{|}(~ - 0  )      !!""#$%&*'()*+,-./0123456789:;<=>?@ABCDECFGHIJHKLMNOPQRSTUVWXCYZQ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~f                 W  C CD CY    CY C!"C,CY#C,CC$C%&'C,(CY)C*stgi_8bE3gn1720lADEl7ZXTWI0Stg.Language.PrettyprintStg.Util Stg.LanguageStg.Parser.ParserStg.Parser.QuasiQuoterStg.Prelude.MaybeStg.Prelude.BoolStg.Prelude.FunctionStg.Prelude.NumberStg.Prelude.ListStg.Marshal.ToStgStg.Prelude.Tuple Stg.Prelude Data.StackStg.Machine.TypesStg.Machine.EnvStg.Machine.HeapStg.Machine.Evaluate$Stg.Machine.GarbageCollection.Common-Stg.Machine.GarbageCollection.TriStateTracing-Stg.Machine.GarbageCollection.TwoSpaceCopyingStg.Machine.GarbageCollection Stg.MachineStg.Marshal.FromStgStg.ExampleProgramsClosureProgramBinds LambdaFormExprAltsAlt AlgebraicAlt PrimitiveAlt DefaultAltLiteralPrimOpAtomPreludeseqspan evalUntil Stg.Marshal Data.Foldablefoldl' traverse_ Data.Listsortansiw_KTAhiPa3RNI09mbeoAwSSXText.PrettyPrint.ANSI.Leijen prettyListprettyPrettyValidateFailureSuccessshow'commaSep bulletListpluralS prettyprintprettyprintPlainConstrAtomVarAtomLitVarAddSubMulDivModEqLtLeqGtGeqNeqDefaultNotBound DefaultBoundNonDefaultAltsNoNonDefaultAlts AlgebraicAlts PrimitiveAltsLetCaseAppFAppCAppPLitRec NonRecursive Recursive UpdateFlagUpdateNoUpdate LambdaType LambdaCon LambdaFun LambdaThunkclassify prettyLambda StgParserparsevarconprogrambinds lambdaFormexpraltsatomprimOpliteralnonDefaultAlts algebraicAlt primitiveAlt defaultAltstgnothingmaybeeq_Booland2or2notboolidconstcomposefixeq_Intlt_Intleq_Intgt_Intgeq_Intneq_Intaddsubmuldivmodminmaxnilconcat2foldlfoldriteratecycletakefilterreverserepeat replicate naiveSortmapequals_List_IntlengthzipzipWith forceSpineToStgtoStgtoStgWithGlobalsfstsndcurryuncurryswapequals_Pair_IntforceStackEmpty:<<>> forEachPop HeapObjectHClosure BlackholeHeap InfoDetailDetail_FunctionApplicationDetail_UnusedLocalVariablesDetail_EnterNonUpdatableDetail_EvalLetDetail_EvalCaseDetail_ReturnCon_MatchDetail_ReturnConDefBoundDetail_ReturnIntDefBoundDetail_EnterUpdatableDetail_ConUpdateDetail_PapUpdateDetail_ReturnIntCannotUpdateDetail_StackNotEmptyDetail_GarbageCollectedDetail_EnterBlackHole!Detail_UpdateClosureWithPrimitiveDetail_BadConArity StateErrorVariablesNotInScopeUpdatableClosureWithArgsReturnIntWithEmptyReturnStackAlgReturnToPrimAltsPrimReturnToAlgAltsInitialStateCreationFailedEnterBlackholeUpdateClosureWithPrimitiveNonAlgPrimScrutineeDivisionByZero BadConArity NotInScopeStateTransitionEnter_NonUpdatableClosureEnter_PartiallyAppliedUpdateEnter_UpdatableClosure Eval_AppC Eval_AppP Eval_CaseEval_Case_Primop_NormalEval_Case_Primop_DefaultBoundEval_FunctionApplicationEval_LetEval_Lit Eval_LitAppReturnCon_DefBoundReturnCon_DefUnboundReturnCon_MatchReturnCon_UpdateReturnInt_DefBoundReturnInt_DefUnboundReturnInt_Match InfoShort NoRulesApplyMaxStepsExceededHaltedByPredicate StateInitialGarbageCollectionInfoLocalsGlobalsMappingCodeEvalEnter ReturnCon ReturnIntValueAddrPrimIntMemAddr StackFrame ArgumentFrame ReturnFrame UpdateFrame StgStateStyleheadlineaddress addressCore closureTypestackFrameTypeStgStatestgCodestgStackstgHeap stgGlobalsstgStepsstgInfo addLocals makeLocalsvalvalslocalVal globalValsizelookupupdate updateManyalloc allocManyevalStep UpdateAddrs updateAddrs AddressesaddrsGarbageCollectionAlgorithm splitHeapWithtriStateTracingtwoSpaceCopyinggarbageCollect PerformGcHaltIf RunForStepsRunIndefinitelyRunForMaxSteps initialState evalsUntil terminated FromStgError TypeMismatchIsWrongLambdaType IsBlackholeBadArityNotFound AddrNotOnHeapNoConstructorMatchFromStgfromStg fromStgAddr fromStgPrim addTwoNumberscalculateLength sum_foldl'sum_foldl'ViaFoldr sum_foldl sum_foldrfibonacciZipWithfibonacciNaivefibonacciImprovedlistConcatRightAssociatedlistConcatLeftAssociated librarySort repeatNaive repeatSharingbase Data.EitherEitherGHC.Showshowtext_HmqVQnZSpjaC156ABqPhneData.Text.InternalText Data.Textpack$fBifunctorValidate$fApplicativeValidate$fFunctorValidateprettyprintModified StgAstStylekeywordprimvariable constructor semicolonstyle $fMonoidBindsGHC.Base$fMonoidProgram$fIsStringConstr $fIsStringVar$fPrettyLambdaType $fShowBindssemicolonTerminated$fNFDataConstr $fNFDataAtom $fNFDataVar$fNFDataPrimOp$fNFDataLiteral$fNFDataDefaultAlt$fNFDataPrimitiveAlt$fNFDataAlgebraicAlt$fNFDataNonDefaultAlts $fNFDataAlts $fNFDataExpr $fNFDataRec$fNFDataUpdateFlag$fNFDataLambdaForm $fNFDataBinds$fNFDataProgram$fPrettyConstr $fPrettyAtom $fPrettyVar$fPrettyPrimOp$fPrettyLiteral$fPrettyDefaultAlt$fPrettyPrimitiveAlt$fPrettyAlgebraicAlt $fPrettyAlts $fPrettyExpr $fPrettyRec$fPrettyLambdaForm $fPrettyBinds$fPrettyProgram $fLiftVar $fLiftConstr $fLiftBinds$fLiftNonDefaultAlts $fLiftAtom skipTokenvarIdreservedarrowcomment$fTokenParsingStgParserstgQQ defaultQuoterbinaryOp primToBool primIdInttrans_GZTjP9K5WFq01xC9BAGQpFControl.Monad.Trans.Writer.LazyWritertell genPrefix tupleBinds $fToStg(,,,,) $fToStg(,,,) $fToStg(,,) $fToStg(,) $fToStg[] $fToStgEither $fToStgMaybe $fToStgBool $fToStgInt integer-gmpGHC.Integer.TypeInteger$fToStgInteger $fToStg() tupleEntry $fNFDataStack $fIsListStack $fMonoidStack$fFoldableStack$fFunctorStack $fPrettyStack $fShowStack prettyStack prettyMapconta_2C3ZI8RgPO2LBMidXKTvIU Data.Map.BaseMapheapSizepprArity$fNFDataHeapObject $fNFDataHeap$fNFDataClosure$fNFDataInfoDetail$fNFDataStateError$fNFDataNotInScope$fNFDataStateTransition$fNFDataInfoShort $fNFDataInfo$fNFDataLocals$fNFDataGlobals$fNFDataMapping $fNFDataCode $fNFDataValue$fNFDataMemAddr$fNFDataStackFrame$fNFDataStgState$fPrettyHeapObject $fPrettyHeap$fPrettyClosure$fPrettyInfoDetail$fPrettyStateError$fPrettyNotInScope$fPrettyStateTransition$fPrettyInfoShort $fPrettyInfo$fPrettyLocals$fPrettyGlobals$fPrettyMapping $fPrettyCode $fPrettyValue$fPrettyMemAddr$fPrettyStackFrame$fPrettyStgStatemkDetail_UnusedLocalVariableslookupAlgebraicAltlookupPrimitiveAltstgRule noRuleApplies PrimErrorDiv0liftLambdaToClosure applyPrimOp isArgFrameaddrs'nubSeq$fUpdateAddrsStackFrame$fUpdateAddrsf$fUpdateAddrsMemAddr$fUpdateAddrsValue$fUpdateAddrsGlobals$fUpdateAddrsLocals$fUpdateAddrsCode$fAddressesValue$fAddressesHeapObject$fAddressesClosure$fAddressesLocals$fAddressesGlobals$fAddressesMemAddr$fAddressesStackFrame$fAddressesCode $fAddressesfGcState aliveHeapstagedoldHeap insert2ndseqToSeteverythingCollectedgcSteptoHeapforwards toScavenge toEvacuateevacuatescavengeEvacuationStatusNotEvacuatedYetAlreadyEvacuatedToGcaskHeap getGcState putGcStateexecGcevacuateScavengeLoopinitialEvacuation scavengeLoopGHC.ListlastLeftJustatomValinspect liftToMatcher matchCon0 matchCon2 matchCon1Nothing matchCon3 matchCon4 matchCon5$fFromStgInteger $fFromStg[]$fFromStgEither$fFromStgMaybe$fFromStg(,,,,)$fFromStg(,,,) $fFromStg(,,) $fFromStg(,) $fFromStgBool $fFromStg() sumTemplateGHC.Num+$!tail System.IOprintlistConcatTemplateconcat++