Engineering behind OCaml's Effect handlers

Specifically, stack management in OCaml.

Hi, I'm Manas.

prometheansacrifice

Reason and OCaml devtools

Maintaining esy

Worked with Ligo team

I helped them build a package manager and ship multi-platform builds

Briefly worked on Tezos core

Again devtools and a core economic protocol proposal

Currently helping setup an OCaml devteam

And hopefully develop an open source template for other companies to follow.

What is OCaml?

Statically typed

with Hindley Milner type system

Functional programming language

Like Haskell, but closer to metal.

Example

open Angstrom

let parens p = char '(' *> p <* char ')'
let add = char '+' *> return (+)
let sub = char '-' *> return (-)
let mul = char '*' *> return ( * )
let div = char '/' *> return (/)
let integer =
  take_while1 (function '0' .. '9' -> true | _ -> false) >>| int_of_string

Eager and imperative.

Like Javascript and Lisps. Unlike Haskell.

Example

let addProjectToGCRoot = (proj: Project.t) => {
  let prefixPath =
    switch (proj.projcfg.prefixPath) {
    | Some(prefixPath) => prefixPath
    | None => EsyBuildPackage.Config.storePrefixDefault
    };
  let currentProjectPath = Path.show(proj.projcfg.path);
  EsyFetch.ProjectList.sync(prefixPath, currentProjectPath);
};

Has classes too!

Example

  class stack_of_ints = {
  as self;
  val mutable theList: list(int) = []; /* instance variable */
  pub push = x =>
    /* push method */
    theList = [x, ...theList];
  pub pop =
    {
      let result = List.hd(theList);
      theList = List.tl(theList);
      result;
    } /* pop method */;
  pub peek =
    List.hd(theList) /* peek method */;
  pub size =
    List.length(theList) /* size method */;
};

Learn more about OCaml at our virtual meetups

reason-ocaml.in

Why this topic?

I was studying OCaml's DWARF output

Effects

try/catch from Javascript

try {
  // validation, processing, lot of code
  // oops
  throw new Error("Ignoring rest of code and jumping to the handler")
  // What?! You're saying, with effects, the code can resume here?
} catch(e) {
  // handle the error
}

Effects in OCaml

type _ Effect.t += Hello : unit Effect.t

let main () =
  Effect.perform Hello

let () =
  let retc = Fun.id in
  let exnc = raise in
  let effc : type c. c Effect.t -> ((c, 'a) Effect.Deep.continuation -> 'a) option
  = function
    | Hello -> Some (fun k -> print_endline "Hello"; Effect.Deep.continue k ())
    | _ -> None
  in
  Effect.Deep.match_with main () { retc; exnc; effc }

This snippet will be obsolete with the 5.3 release

So how can a compiler implement effect handlers

Continuation Passing Style

Delimited Continuations

OCaml compiler internals

Exceptions visualised


let () =
  let failing_fn () =
    failwith "This function failed"
  in
  let fn_c () = 
    failing_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () with | e -> raise e

(empty_stack)


let () =
  let failing_fn () =
    failwith "This function failed"
  in
  let fn_c () = 
    failing_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () with | e -> raise e

fn_a


let () =
  let failing_fn () =
    failwith "This function failed"
  in
  let fn_c () = 
    failing_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () with | e -> raise e

fn_a

fn_b


let () =
  let failing_fn () =
    failwith "This function failed"
  in
  let fn_c () = 
    failing_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () with | e -> raise e

fn_a

fn_b

fn_c


let () =
  let failing_fn () =
    failwith "This function failed"
  in
  let fn_c () = 
    failing_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () with | e -> raise e

fn_a

fn_b

fn_c

failing_fn


let () =
  let failing_fn () =
    failwith "This function failed"
  in
  let fn_c () = 
    failing_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () with | e -> raise e

(empty_stack)

Restoring stack statement problem



let () =
  let effectful_fn () =
    let effect_result = perform Some_effect in
     // some work with effect_result
  in
  let fn_c () = 
    effectful_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () ; fn_c () with
  | effect e, k -> continue k

(empty_stack)


let () =
  let effectful_fn () =
    let effect_result = perform Some_effect in
     // some work with effect_result
  in
  let fn_c () = 
    effectful_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () ; fn_c () with
  | effect e, k -> continue k

fn_a


let () =
  let effectful_fn () =
    let effect_result = perform Some_effect in
     // some work with effect_result
  in
  let fn_c () = 
    effectful_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () ; fn_c () with
  | effect e, k -> continue k

fn_a

fn_b


let () =
  let effectful_fn () =
    let effect_result = perform Some_effect in
     // some work with effect_result
  in
  let fn_c () = 
    effectful_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () ; fn_c () with
  | effect e, k -> continue k

fn_a

fn_b

fn_c


let () =
  let effectful_fn () =
    let effect_result = perform Some_effect in
     // some work with effect_result
  in
  let fn_c () = 
    effectful_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () ; fn_c () with
  | effect e, k -> continue k

fn_a

fn_b

fn_c

effectful_fn


let () =
  let effectful_fn () =
    let effect_result = perform Some_effect in
     // some work with effect_result
  in
  let fn_c () = 
    effectful_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () ; fn_c () with
  | effect e, k -> continue k

fn_a

fn_b

fn_c

effectful_fn


let () =
  let effectful_fn () =
    let effect_result = perform Some_effect in
     // some work with effect_result
  in
  let fn_c () = 
    effectful_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () ; fn_c () with
  | effect e, k -> continue k

(empty_stack)


let () =
  let effectful_fn () =
    let effect_result = perform Some_effect in
     // some work with effect_result
  in
  let fn_c () = 
    effectful_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () ; fn_c () with
  | effect e, k -> continue k

fn_a

fn_b

fn_c

effectful_fn


let () =
  let effectful_fn () =
    let effect_result = perform Some_effect in
     // some work with effect_result
  in
  let fn_c () = 
    effectful_fn ()
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  try fn_a () ; fn_c () with
  | effect e, k -> continue k

fn_a

fn_b

fn_c

effectful_fn

We need new program stacks for easy book-keeping

Fiber layout and stack layout

struct stack_handler

caml_start_program

frame 1

frame 2

red zone

struct stack_info


let () =
  let effectful_fn_2 () =
    let effect_result = perform Some_effect in
    // some work with effect_result
  in
  let effectful_fn_1 () =
    effectfule_fn_2 ()
  in
  let fn_c () = 
    try effectful_fn () with
    | effect e, k -> continue k
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  fn_a()

struct stack_handler

caml_start_program

(empty_stack)

red zone

struct stack_info


let () =
  let effectful_fn_2 () =
    let effect_result = perform Some_effect in
    // some work with effect_result
  in
  let effectful_fn_1 () =
    effectfule_fn_2 ()
  in
  let fn_c () = 
    try effectful_fn () with
    | effect e, k -> continue k
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  fn_a()

struct stack_handler

caml_start_program

fn_a

red zone

struct stack_info


let () =
  let effectful_fn_2 () =
    let effect_result = perform Some_effect in
    // some work with effect_result
  in
  let effectful_fn_1 () =
    effectfule_fn_2 ()
  in
  let fn_c () = 
    try effectful_fn () with
    | effect e, k -> continue k
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  fn_a()

struct stack_handler

caml_start_program

fn_a

fn_b

red zone

struct stack_info


let () =
  let effectful_fn_2 () =
    let effect_result = perform Some_effect in
    // some work with effect_result
  in
  let effectful_fn_1 () =
    effectfule_fn_2 ()
  in
  let fn_c () = 
    try effectful_fn () with
    | effect e, k -> continue k
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  fn_a()

struct stack_handler

caml_start_program

fn_a

fn_b

fn_c

red zone

struct stack_info


let () =
  let effectful_fn_2 () =
    let effect_result = perform Some_effect in
    // some work with effect_result
  in
  let effectful_fn_1 () =
    effectfule_fn_2 ()
  in
  let fn_c () = 
    try effectful_fn_1 () with
    | effect e, k -> continue k
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  fn_a()

struct stack_handler

caml_start_program

fn_a

fn_b

fn_c

red zone

struct stack_info

struct stack_handler

caml_start_program

(empty_stack)

red zone

struct stack_info


let () =
  let effectful_fn_2 () =
    let effect_result = perform Some_effect in
    // some work with effect_result
  in
  let effectful_fn_1 () =
    effectfule_fn_2 ()
  in
  let fn_c () = 
    try effectful_fn_1 () with
    | effect e, k -> continue k
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  fn_a()

struct stack_handler

caml_start_program

fn_a

fn_b

fn_c

red zone

struct stack_info

struct stack_handler

caml_start_program

effectful_fn_1

red zone

struct stack_info


let () =
  let effectful_fn_2 () =
    let effect_result = perform Some_effect in
    // some work with effect_result
  in
  let effectful_fn_1 () =
    effectfule_fn_2 ()
  in
  let fn_c () = 
    try effectful_fn_1 () with
    | effect e, k -> continue k
  in
  let fn_b () = 
    fn_c ()
  in
  let fn_a () =
    fn_b ()
  in
  fn_a()

struct stack_handler

caml_start_program

fn_a

fn_b

fn_c

red zone

struct stack_info

struct stack_handler

caml_start_program

effectful_fn_1

effectful_fn_2

red zone

struct stack_info

Closing thoughts

More notes on ocaml-internals.dining-philosophers.dev

Compiler overview
Passes and how various backends differ
Generated assembly explanations
Running notes…

Thank you

I'm @ManasJayanth on x.com.

You can email me at hello [at] manas-jayanth [dot] com

These slides can be found at slides.manas-jayanth.com