Stg.Machine.Evaluate.ValidTransitions

Valid transitions from one state to another. Error conditions are handled separately in ErrorTransitions if possible.

Documentation

rule1_functionApp :: StgState -> Maybe StgState

Rule 1: Function application

Push argument values onto the stack, and enter the function's address.

rule2_enterNonUpdatable :: 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.

rule3_let :: 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.

rule4_case :: 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.

rule5_constructorApp :: StgState -> Maybe StgState

Rule 5: Constructor application

Simply transition into the ReturnCon state.

rule6_algebraicNormalMatch :: 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.

rule7_algebraicUnboundDefaultMatch :: StgState -> Maybe StgState

Rule 7: Algebraic constructor return, unbound default match

None of the given alternatives matched, so simply continue with the default branch.

rule8_algebraicBoundDefaultMatch :: 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.

rule9_primitiveLiteralEval :: StgState -> Maybe StgState

Rule 9: Literal evaluation

Simply transition into the ReturnInt state.

rule10_primitiveLiteralApp :: StgState -> Maybe StgState

Rule 10: Literal application

Simply transition into the ReturnInt state.

rule11_primitiveNormalMatch :: StgState -> Maybe StgState

Rule 11: Primitive return, standard match found

Like rule4_case, but for primitives.

rule12_primitiveBoundDefaultMatch :: 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.

rule13_primitiveUnboundDefaultMatch :: StgState -> Maybe StgState

Rule 13: Primitive return, unbound default match

Like rule7_algebraicUnboundDefaultMatch, but for primitives.

rule14_primop :: 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.

rule15_enterUpdatable :: 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.

rule16_missingReturnUpdate :: 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.

rule17_missingArgUpdate :: 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.

rule17a_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.

rule1819_casePrimopShortcut :: 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.