[gclist] Formal semantics of stack maps

[Daniel Wang]

I'm not so sure, anyones made the observation before, but I know several
precise collectors emit a mapping from the current return address of 
stack frame to a map that describes the types and roots of the stack.

After playing with some standard transformations used in compilers, I've
"discovered" that the stack map is something that comes for free if you CPS
convert your program and then convert your CPS program into a first order
(i.e. programs with out function pointers) language which uses a switch
statement on tagged values to simulate jumps/computed gotos. 

Anyway, has anyone else made this or a similar observation before? 

Here's a worked out example in ML. I'm assuming those of you who can decode
CPS have a good chance of reading ML code too... :) Also with a sufficiently
cute tagging scheme and representation tricks you end up with machine code
that you'd normally expect. 

structure ANF = (* a-normal form *)
  struct
    fun f () = 1
    fun g () = 1.0 
    fun h () = let
      val t = f()
    in t + 2
    end

    val x = f()
    val y = g()
    val z = h()
    val ans = (x,y,z)
  end

structure CPS =
  struct
    exception HALT of (int * real * int)
    fun halt x = raise (HALT x)

    fun f (k,()) = k 1
    fun g (k,()) = k 1.0
    fun h (k,()) = let 
      fun ret_t (t) = k (t + 2)
    in f(ret_t,())
    end

    fun ret_x (x) = let
      fun ret_y (y) = let
	fun ret_z (z) = (halt (x,y,z))
      in h(ret_z,()) end
    in g(ret_y,()) end
   val ans = f(ret_x,()) handle (HALT x) => x
  end

structure FOL_CPS =
  struct
    exception HALT of (int * real * int)
    fun halt x = raise (HALT x)

   (* a stack map for free... *)
    datatype int_cont  = Ret_X  | Ret_T of int_cont | Ret_Z of int * real
    and real_cont = Ret_Y of int

    fun app_int (Ret_X,x) = g (Ret_Y x,())
      | app_int (Ret_T k,t) = app_int (k,t + 2)
      | app_int (Ret_Z(x,y),z) = halt(x,y,z)
    and app_real (Ret_Y x,y)  = h (Ret_Z(x,y),())
    and f (k,()) = app_int  (k,1)
    and g (k,()) = app_real (k,1.0)
    and h (k,()) = f(Ret_T k,())
    val ans = f(Ret_X,()) handle (HALT x) => x
  end