STG case compilation

Learn
1

I’m trying to make my way through Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-machine. I’m stuck at compilation of case expressions.

Suppose I need to generate native code for such STG expression:

case <x> of
Cons y ys -> <z>

Simply speaking I would need to

  1. Push continuation on the stack.
  2. Evaluate subexpression x. It will eventually jump to the continuation.
  3. In the continuation save local environment (y and ys)
  4. Evaluate subexpression z.

What I can’t figure out is how local environment should be saved. In 9.4.1 the paper suggests that it can be pushed onto the stack. But then it must be cleaned after step 4 and it’s not obvious how. One way I came up with is to push another intermediate continuation before step 4 with sole purpose of cleaning stack of values pushed at step 3 after step 4 and then it would jump to the next “real” continuation. But that seems rather inefficient.

In 9.2.2 the paper explains that the code for applications is supposed to clean the stack before pushing new arguments onto the stack. If <z> is an application then it could clean the stack not only from the arguments but from case-binded variables too. But what if <z> is not an application? Does it mean that all other types of expressions such as literal, constructor application, primitive operation need to clean stack too?

I tried to see what the real compiler does and it seems to be something different from what this paper describes. If I understood C-- correctly it calls functions normally instead of going through continuation mechanism (“tiny interpreter” 6.2.2). The usual stack is used to preserve local environment and it’s cleaned when function returns so there’s no need for manual bookkeeping in this case.

2

I think the confusion comes from what composes the local environment. y and ys aren’t in the local environment.

Suppose you have the following code instead, with a and b local variables:

case <x> of
  Cons y ys -> z a b y ys
  Nil -> nil

The local environment is composed of: a, b. You have to generate code like:

  push a
  push b
  evaluate x -> returns to cont

cont:
  local_b <- pop b
  local_a <- pop a
  ; scrutinize x that is now evaluated
  case x of
    Cons y ys -> call z (local_a, local_b, y, ys) ; whatever the calling convention is
    Nil -> call nil

There can be many variations around this. E.g. in this paper, for ADTs they directly pass several continuations in an array. Each continuation is independent so you start with something like:

  push a
  push b
  evaluate x -> returns to cont

cont:
  ; scrutinize x that is now evaluated
  case x of
    Cons y ys -> do
      local_b <- pop b
      local_a <- pop a
      call z (local_a, local_b, y, ys)
    Nil -> do
      _ <- pop b ; cleanup the stack
      _ <- pop a
      call nil

But then you mix evaluation and scrutinization:

  push a
  push b
  evaluate and scrutinize x -> returns to &cont_array[tag]

cont_array:
  .ptr cont_cons
  .ptr cont_nil

cont_cons:
  local_y <- pop y
  local_ys <- pop ys
  local_b <- pop b
  local_a <- pop a
  call z (local_a, local_b, local_y, local_ys)

cont_nil:
  _ <- pop b ; cleanup the stack
  _ <- pop a
  call nil

GHC doesn’t use continuation vectors like this anymore.