# [gclist] Formal semantics of stack maps

**Daniel Wang**
danwang@CS.Princeton.EDU

*02 Dec 1999 17:29:21 -0500*

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