Compiling Ocaml Effects to Javascript

18 Jan 2017

I am currently working on the compilation of the algebraic effects and handlers introduced in multicore OCaml for the js_of_ocaml backend.

The bytecode and native backends of the OCaml compiler rely on the fact that in effect handlers the continuation can be called at most once to efficiently implement them. This method requires control over the runtime as it manipulates the stack. Since we do not have control over the stack in JavaScript we need to find a way to implement algebraic effects and handlers using existing primitives. In the setting of the $\lambda$-calculus, the traditional way to introduce control primitives is to use Continuation Passing Style (CPS) to make the control flow of the program explicit. Starting from a program using effect primitives we transform it to an equivalent program in CPS which can be compiled to JavaScript.

The actual process is actually a bit different because for maintenance reasons we do not want to implement this transformation in the OCaml compiler but directly on the bytecode which has a stable representation.

Another concern is that a full CPS transformation can induce a severe performance cost so we

What we have :

• A simple calculus for deep handlers (based on Liberating Effects with Rows and Handlers)
  • Attempts to give it semantics (?) in Ocaml (direct/finally tagless) and Agda
• An untyped CPS transform to $\lambda$-calculus
  • Tested on a few examples but the derivation is not well documented :
    Effects -?> Shift/reset -CPS> $\lambda$
  • Typing the result seems to require recursive types
• Hope that we can type it for shallow handlers (we don’t have a simple type system for that)
  • Following Handlers in Action is a possibility but the continuation which is resumed in perform has to be explicitly provided (Which seems to require a cps translation in itself)
• Some questions and a few answers about making it a selective transform
  • Wrapping functions which may be direct style (pure/primitive functions) Inspired by Daan Leijen
  • This introduces problem with separate compilation -> jsoo backend
    • Maybe talk about the consequences of cps in js? (stack overflow and trampolines)
  • A purity analysis which may be built on top of ecaml

Describe the calculus and type system for deep handlers, cps translations for deep & shallow handlers. Explain the issues with typing the (deep) cps translation and the shallow terms.