Visiting OCaml Labs -- Day #1

Computer Laboratory entrance, Cambridge Entrance to the Computer Laboratory, Cambridge.

Today I arrived in Cambridge, where I am staying for next two weeks, while I work on a native backend for Links with effect handlers. My plan is to target either the surface syntax of OCaml or the OCaml IR directly. I have been invited by KC Sivaramakrishnan, whom is working on adding multicore support to OCaml using handlers. I plan to do something similar with Links, albeit my focus at the moment is on concurrency and not on parallelism. However, I might obtain multicore support for free.

KC gave me an overview of the OCaml compiler and the multicore project today. I will give a brief overview/summary of our discussion.

Overview of OCaml Lambda IRs

The OCaml backend consists of a number of intermediate representations (IRs) based on variants of the Lambda calculus. Below is a rough sketch of how the IRs are connected:

lambda IR
  |-> flambda IR -> clambda IR
  |                   |-> byte code
  |                   |-> native code
  |-> JavaScript

The backend entry point is the lambda IR, which can be translated either directly to JavaScript or to flambda IR. The flambda IR is an optimisation framework for inlining, simplification, dead code elimination and so forth. Notably, the terms of flambda are in A-normal form (ANF) -- or at least a relaxed form of ANF. The Links IR are a variant of ANF aswell. The clambda IR introduces closures. After clambda IR comes low-level optimisations, instruction selection, instruction scheduling and register allocation. There are two possible targets which are interpretable byte code or executable native code.

The lambda IR is fairly simple. Targetting the lambda IR directly seems like a good, flexible choice as I will get the possibility to compile both to native code and JavaScript. The JavaScript option is interesting, because Links client-side code is compiled to JavaScript already. It might be interesting to see whether the JavaScript code generated by the OCaml backend performs better than code currently generated by Links.

Concurrency and parallelism

The OCaml multicore project clearly separates the notions of concurrency and parallelism. Concurrency is concerned with structuring interactions. The OCaml effects project provide concurrency via algebraic effects and handlers. The unit of concurrency is a so-called fiber, which is essentially a co-operative routine. Fibers are scheduled by a handler, they run in a single thread, thus fibers on their own do not provide any parallelism.

Parallelism is concerned with performance, i.e. speeding up computations. The OCaml multicore project adds support for parallelism by providing primitives that let handlers map fibers onto processing cores.

Currently, the effects project has a native backend. The multicore project only compiles to byte code at the moment. I will start by targetting the backend of the effects project. Later, when a native backend becomes available for the multicore project, I should be able to seamlessly switch to it as they share the same lambda IR. Thus, I ought to get multicore support for free!