CPS & assembly
x86 machine code is inherently in continuation passing style, where the
continuation is passed as an address on the stack (pushed by
call
and jumped to by ret
). This is a useful
perspective, because it makes multi-continuation setups quite natural.
In particular, escape continuations, while hard to do in normal C, are quite natural in assembly. Something like this in a pseudo-Javascript
function div(x, y; then, escape) {if (y ==0 ) escape(0 );else then(x / y); } div(10 ,0 ; res => res +1 , res => res -1 );
(where then
and escape
are the continuations)
becomes something like this in x64 assembly
main :mov rdi,10 xor rsi, rsilea rax, [.escape ]push raxlea rax, [.then ]push raxjmp div.escape :dec raxret .then :inc raxret div :push rbpmov rbp, rspcmp rsi,0 jne .ok .err :xor rax, raxleave add rsp,16 mov rbx, [rsp-8 ]jmp [rbx].ok :mov rax, rdiidiv rsileave add rsp,16 mov rbx, [rsp-16 ]jmp [rbx]
The important pattern is this:
lea rax, [.cont ]push raxjmp target
This is a stand-in for
call target
1,
but with the return pointer explicit. A call to div
should
therefore make the stack look something like this:
| ... | +------------+ <-- rbp | prev rbp | +------------+ | then | +------------+ | escape | +------------+ | ... |
A more natural implementation of escape continuations would use the
normal call
and ret
instructions, which would
leave non-escaping code looking largely the same. This gives the caller
the responsbility of cleaning up the escape pointer, meaning a typical
escapable call might look something like
lea rax, [.escape ]push raxcall func pop
Notes
-
^ x64 is not able to encode a
push
instruction with a 64-bit immediate operand, which is why thelea
is necessary here. On 32-bit systems,push .cont
can be used instead.