Rambles around computer science
Diverting trains of thought, wasting precious time
Wed, 30 Sep 2015
Project suggestion: an observable OCaml, using liballocs
It's the season to suggest student projects, and this post is about one which follows up a series of blog posts (1, 2, 3, 4). Feel free to see also my suggestions from last year, another from last year and other standing suggestions
This post is about a suggested project which will produce a working implementation of the OCaml programming language, using an existing front-end but a very different back-end.
Unlike the mainstream implementation, this implementation will be optimized for debuggability, or more generally “observability”. The compilation strategy will be to translate to C, hence obtaining the debuggability (and, to some as-yet-unknown extent, the performance) of the C compilation toolchain.
This means at least three key differences. Firstly, all locally-bound names will map to C local variables. Secondly, OCaml's lexical closures will be implemented in a highly compatible way, perhaps using the technique of Breuel (which is already implemented in the GNU C compiler, but with stack allocation, whose lifetime semantics are not appropriate for OCaml). Thirdly, all allocations will have associated type metadata at run time, using liballocs This will allow parametric polymorphism to be “seen through” by a debugger—so it can tell you, for example, that some stack frame of a function whose type is 'a -> 'a is actually activated with 'a as int, say. (This may or may not be the right formulation of “seeing through”—stronger and weaker versions are possible; ask me!)
Key ingredients are the following:
- designing an efficiently observable object representation for OCaml values (including variants, tuples, etc., noting that there's no compulsion to stick to the central tagged-pointer decision of mainline OCaml, and many reasons not to—see “interoperability”, below);
- writing a translator from OCaml's typed AST to C, or an abstraction of C such as CIL, initially targeting the most-used features of OCaml (e.g. no objects, no polymorphic variants);
- write a minimalist runtime necessary to execute programs—actually, no runtime is necessary, but one or both of two features would be advisable: a garbage collector and dynamic closure creation (the latter can be implemented using libffi initially);
- basic observability including teaching liballocs about OCaml layouts (easy if they map via C) and how to get a dynamically-created closure's type (easy enough);
- finding a way to model OCaml's polymorphic types using liballocs's uniqtype abstraction (ask me; this is mostly worked out already, but putting it into practice might reveal some interesting cases);
- enabling observability in the presence of polymorphic allocation sites, such as heap instantiations of polymorphic record types or polymorphic function closures, and stack activation of polymorphic functions; this is subtle but not actually as hard as it seems (I've thought about it quite a bit);
- creating a simple OCaml library (not complete) sufficient to run some demo/benchmark programs.
Optional “extension”-style challenges might include the following:
- improving the closure implementation for which I have plenty of ideas, so ask me—it's likely that we'll want a special closure allocator that is fast, maintains the link with liballocs efficiently, and avoids simultaneously writable and executable mappings (for security);
- improve the GC—ideally a simple generational collector whose new-space liballocs can understand, and that can pin/promote objects conveniently during interop;
- improve the library to support a bigger subset of the OCaml library;
- experiment with interoperability (e.g. with C and C++)—since interoperability is potentially an additional win of this approach (key idea: don't use header files; use liballocs! also there are interactions with the GC).
Evaluation of the system is mostly via performance—the goal would be to get within a reasonable factor of the OCaml native-code compiler. We can also do some experiments to measure observability of our system. One simple experiment might interrupt both versions of a program at randomly chosen call sites and count how much of the local state we could recover (number of frames in the backtrace, number of locals in those frames; perhaps even doing a diff on their values). Call sites are a good choice because all but one frame of the stack is always stopped at one, and instrumenting the native code so that we can do lock-step breakpointing, by counting call invocations, should not be too difficult (though it might mean disabling inlining, which does affect what is being measured). Usually there'll be no contest, since the original OCaml native compiler doesn't let you observe locally bound values at all. There is, however, a development branch which does, and comparing with the bytecode debugger (ocamldebug) is also a good bet.
[/research] permanent link contact
