CPS & assembly

ASM

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, rsi
  
  lea rax, [.escape]
  push rax
  lea rax, [.then]
  push rax

  jmp div

.escape:
  dec rax
  ret

.then:
  inc rax
  ret


div:
  push rbp
  mov rbp, rsp

  cmp rsi, 0
  jne .ok

.err:
  xor rax, rax

  leave
  add rsp, 16
  mov rbx, [rsp-8]
  jmp [rbx]

.ok:
  mov rax, rdi
  idiv rsi

  leave
  add rsp, 16
  mov rbx, [rsp-16]
  jmp [rbx]

The important pattern is this:

  lea rax, [.cont]
  push rax
  jmp target

This is a stand-in for call target1, 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 rax
  call func
  pop

Notes

  1. ^ x64 is not able to encode a push instruction with a 64-bit immediate operand, which is why the lea is necessary here. On 32-bit systems, push .cont can be used instead.