November 7, 2018
Jane and the Compiler
Most of the time, our relationship to programming languages is somewhat remote; we depend on the arcane details of the languages we use, but we don't usually have much of a say in how those languages evolve.
At Jane Street, we started out in that mode, as a mere user of the language. But over the last 15 years, we've moved to a more active stance, where today, we have a team of compiler devs who actively contribute to OCaml, and where we're more deeply involved in figuring out the future direction of the language.
In this talk, I'll discuss that history, touching on how upstream changes impacted us along the way, how we came to start making changes ourselves, and what ongoing projects we're excited about.
Yaron Minsky joined Jane Street back in 2002, and claims the dubious honor of having convinced the firm to start using OCaml. He also spends way too much time teaching his kids how to program.
Thank you all for coming. We’ve now been doing the Jane Street Tech Talk series for long enough that I’ve lost count of how many we’ve done and which number we’re at now. So, we like to give a mix of talks. Some of these are talks that we get external people that we’re interested in hearing from to come and talk about all sorts of different aspects of technology, and some of them are talks from us about our own experience, and in this talk, I want to talk in a focused way about our experience with the OCaml compiler, which is, one of the things we’re well-known for is our, let’s call it eccentric taste in programming languages. We many years ago did this weird thing of adopting an almost comically obscure programming language as the thing that we build almost everything in, and that’s a kind of interesting story on its own of how we got to the point of doing that.
But I want to talk about a different aspect of that experience, which is what it has been like having jumped into this programming language community, starting off as a fairly small fish, a mere user of the language, and evolving over time into a serious contributor and an organization that really engages in a first-class way in development of the programming language itself, and helping figure out what direction that language is going to go in the future. And I think that will tell you some things about the OCaml compiler and language itself, and just some things about what it’s like working with a language ecosystem like this one.
And Jane Street’s experience here is a little unusual, because first of all, you don’t find a lot of companies that have made deeply idiosyncratic choices about programming language technologies. On the whole, companies tend to be fairly conservative in the programming languages they pick. And even when companies have weird programming languages they use, they’re often the weird programming languages they wrote themselves, right? So you have like, Google has Go, and Apple has Swift and things like that. And in those kinds of circumstances, the company has a much more direct control, end to end, often, from conception all the way through to the last day of execution of how that language works and how it’s defined.
The experience here is different. Here, we came into OCaml kind of as … Oh, no way. That’s not really a good property, is it? Well, let’s hope that doesn’t keep on happening. So we came into OCaml not as deep experts in the language, we came as people who just were mere users. Like, as a background matter, I actually don’t know how any of this stuff works, on some level. Like I have the kind of knowledge of OCaml that you get from being a serious user over many years, but my background is in distributed systems. I’ve basically never implemented a compiler I’m my life, and I don’t really know how the internals of these systems work. And so we really started very much from an outside perspective, and kind of moved over the years to be more on the inside, and I think that’s a kind of interesting experience on its own.
So, let me start with a little bit of history of how we move through this process. So I inflicted OCaml on this organization many years ago, like as many good decisions, by mistake. So I started working at Jane Street about 15, 16 years ago, not intending to stay. I was here working part-time while doing a postdoc, intending to go off and be a professor somewhere. And about six months through my time working here part-time, I realized I was having a lot more fun working on the problems Jane Street had than I had working on my own research where I got to do whatever I wanted, and I had a pretty good guess where the pay was better, so I jumped ship.
And in that first period, before I knew that I was going to stay, I was doing research, quantitative research on trading strategies, and I ended up using OCaml on the theory that the code I was writing didn’t matter. Like I started writing stuff in Python doing some data analytics, at some point I got sad about how slow Python was and I switched to using OCaml because I had learned that in grad school, and the switch to OCaml was done on the theory that the results mattered and the code didn’t matter that much, and maybe at the end before I left I would figure out what the core bits were and rewrite them in something more accessible.
And of course, 80,000 lines of code later, it turns out I wasn’t going to be a professor anywhere, and I had all this code that I’d written of this useful code base that had been built up over time, and that became the fore of the OCaml code base that we had as an organization. It is, by the way, terrible code. Like if you want to go and see the absolute worst code at Jane Street, like just find anything that dates back. There’s a horrible library called Qbase, which I’m looking at people who are on the research team here. I don’t know if any of that still exists, but it should be burned out root and stem, like it’s all terrible.
But anyway, so I started off doing this research work and we hired a few people to work in OCaml, and at that point, we were very much on the … In fact, the decision wasn’t really intentional. In some sense it really was a mistake, like I had not intended to in any way marry this language to the organization, it was meant to be a kind of temporary tactical decision.
So we made, a few years later, a more thoughtful choice about it, where we stood back and looked at the OCaml ecosystem, and thought about whether or not we wanted to dive in and start building actual production trading systems in it. And at that point, there were reasons we were looking to redo our own internal infrastructure, which up until then, I kid you not, was mostly VBA in the back of a spreadsheet. It was really good VBA, I should say, like very carefully written, thuddingly concrete, first-order but really easy to understand, lots of array operations carefully code reviewed, people took it seriously. And it was, I think, very well done, and Excel made a lot of things easier, but no one was confused that this was a good long-term strategy, we knew we needed to do something better, and after trying various other things, we’re like, “Well, this OCaml thing is kind of working for us. Maybe we should see if that would make sense to bill our production systems out of.”
And that’s when we made a real kind of fateful step into integrating OCaml into our permanent infrastructure. And that was like in 2005, we started doing this 2006, we had about 10 people who were programming in OCaml, and from then it just kind of took off, like the initial experiments went well, we built systems that were successful and that people liked how they worked and liked how easy they were to read, which was very important to us. And we started pushing towards doing it for all of our automated trading systems and really redoing all of our infrastructure in OCaml.
By 2009 we had about 30 people programming in OCaml. 2010 we started teaching the traders to program in OCaml, which I think is really, that’s in some sense a really fateful change, right? Because it’s worth saying, I think people who don’t know Jane Street may have the wrong sense about, like when I say, “And then the traders had to learn it,” it’s almost like, “Oh, the knuckle-dragging traders have to,” it’s like, no, no, no, the traders are extremely sophisticated, technical people in their own right. Some of them have computer science backgrounds, a lot of people with scientific and technical backgrounds.
But, you are then going from a set of people who are willing to dive into an infrastructure fully and spend all their time in it to with the traders, people who are doing it part-time on the side, that puts different pressures on the language, you need different things once you do that.
And more recently, around 2015, the organization had grown enough … Jane Street when I started was like 30 people? It’s now about 800, so the organization has grown a lot in that time, and in 2015 we actually set up an organization that was devoted to working on development tools and on the compiler itself. And that’s another important stage in the development of our interaction with [inaudible 00:08:17], because suddenly now we’re taking … We worked in some ways on development tools and on the OCaml compiler itself in some small ways throughout, but now it’s become a real formal part of our development process as we have enough scale where it makes sense to invest directly in that kind of stuff.
Okay, that’s like a real capsule summary of the role OCaml’s had in the organization. Let’s step back and think about, why does any of this actually matter? What is important about the programming language that you pick, and how does that language and the compiler and the tools around it impact how the organization works? So there’s a bunch of different ways in which the aspects of the language you pick are going to affect the code that you end up with and the systems that you build. There are obvious ones, performance is a clear one. There’s a big difference between building a lot of systems where you’re writing them all in Python and when you’re writing them all in C, right, there’s the terrifying interpreter loop that you go through which has somewhere between a factor of 60 and 200 slowdown on whatever you’re going to do, and the kind of big differences in how memory layouts work in different kinds of languages. It can really affect the performance of the programs you write, and also, I think an important thing that people often don’t realize, the predictability of the performance of the programs that you write.
I think that when you think about the semantics of your code, the meaning of the programs that you write, there’s the meaning in the sense of what values does it produce, what things does it do, what actions does it take, but there’s also the performance semantics, right? What does it make the machine do, how much time do different kinds of actions take? And different programming languages and different compiler systems lead to quite big differences in how predictable that performance is.
If you want to take kind of an extreme example, think about SQL. You write some statement in SQL in some nice, high-level declarative language, and then a miracle happens, and then the query optimizer comes and creates some completely different program which really is going to have very, very different performance characteristics than the naïve program you write, and the choice that the optimizer makes, of whether it uses a hash data structure or a comparison-based data structure, those kind of choices can be worth several orders of magnitude in the performance of the end algorithm.
And not only can you not look at the code on its own, like not only is it hard to understand how it does that optimization, the code on its own is not enough information to even know, because in a database system, it actually gathers statistics about the data to make the choices about how to do the representation, so that’s an example of a language where there’s … Like a miracle happens or the miracle doesn’t happen, and how that presence or absence of an optimization miracle makes enormous differences to how well your program is going to run, and it makes it hard to reason in a simple way in advance about how things are going to work and what the performance is going to be like. How much predictability your language gives you matters a lot, certainly if you care about performance engineering in the work that you do. Not everyone does, but we certainly do.
Another thing, and maybe the first thing I should always say when I talk about how languages matter is safety. This whole thing of writing programs that connect to markets and to your wallet at the same time is terrifying, and if you’re not afraid of it, you’re not thinking about it carefully. We’re all terrible programmers, humans are bad programmers, we all make mistakes, and you want as much as you can get in the way of tools that help you catch mistakes, and there are tools in the form of testing tools, which are incredible important, but there’s also language-level tools, and type systems are one very effective language-level tool for allowing you to engineer better correctness properties out of your program. It’s not enough to have a type system, you have to know how to use it, but languages that provide rich and expressive type systems really make a difference to how likely you are to just one day vanish in a puff of smoke because you did something outrageously stupid, but also, help you move faster.
One of the things that is important for moving quickly and making changes quickly in a high stakes situation is having tools that let you make changes with high confidence that the result is going to be correct, and the language [inaudible 00:12:33] makes a lot of difference to that kind of thing.
Another thing is productivity, how easy it is to make changes, how easy it is to dive into a code base and understand it. And a subtle variant on this, which I think has become more important just over time is the learnability of the resulting language. How easy is it for someone who comes in for the first time to understand the language and understand the environment and understand the tools? And I think the language and the tools around the language make a big difference there, and I think different users have very different experiences and different needs.
I mentioned this kind of sea change of how it became different is we had traders come in who were operating the system in a much more part-time way, I think this thing that’s happened to the organization is we’ve gotten bigger, where we have a much wider scale, a much wider spread of investment and programming sophistication among the different users puts all sorts of different pressures on the language and the tools around it. It makes various forms of discoverability and interactivity in the system much more important, and that’s a thing that didn’t seem that important to us at first, but really, we came to realize how valuable it was over time.
So for the rest of the talk, I kind of want to focus on two streams of things that we’ve learned along the way. We’ve now talked about the history and why all of this matters to us and to the business that we run, but the other interesting thing about this experience is what we learned over time from the features that came into existence over the period, and some of them are features that arrived independently of us, we didn’t ask for them and only discovered their importance as they landed, and some of them are things that we ourselves pushed for and added to the language, and I think they’re both interesting experiences, and quite different in their texture and involve different ways of engaging with a larger programming language, larger development world around OCaml.
So first, let’s talk about some of the features that we didn’t know we wanted, things that arrived in the language without us asking for them. One early interesting one is first-class modules. I’m going to try and explain this in a way that doesn’t require too much understanding of OCaml as a language, but I have to tell you a little bit about how the language works. So one interesting aspect of OCaml is it has an extremely powerful, what’s called a module language, a language for manipulating what you ordinarily think about modules in other languages, like big units of code and functionality, OCaml has all sorts of powerful tools for expressing what the shapes of these are, the signatures of them, and then tools for transforming them, things like, there’s a tool called a functor, which is essentially a function from a module to a module. You can create new modules from old modules in programmatic ways. It sounds a little bit like macros, but instead of being macro-oriented in the way that, say, templates in C++ are, it’s all highly integrated and kind of safe in the type system in a way that things like C++ templates are not.
But this very expressive module language is a kind of totally separate thing from the ordinary value-oriented language. So if you want to transform ordinary value, you have functions, and you have this completely separate thing called functors for transforming modules, and functions can’t take modules as argument and functors can’t take ordinary values as arguments, and this is fairly sharp striation between the two, but they’re both useful and powerful parts of the language.
First-class modules were a feature that arrived at a point where I had imagined this was like a really hard thing to do. If you’ve used a classic ML-like language for a while, you think of this break between the two parts of the language as a kind of fundamental part of the granite that you walk on. It’s like, oh, of course, there’s the module language and the regular language, and they’re separated probably for good reason that those programming language people understand, but I didn’t understand.
And then one day a guy named Alain Frisch proposed some changes to OCaml to add first-class modules, which is just the ability to take a module and kind of package it up and stick it into the ordinary value language. And the thing that this allows, it allows you to use the same kinds of very powerful abstractions you have for manipulating modules to use them in a more dynamic way. So one of the properties of the traditional module language is it’s very static. You kind of have to know in advance at compile time exactly which module’s being packed in … You can’t just dynamically look something up and decide which module to grab and choose it.
And with first-class modules, suddenly you could do that. And a whole bunch of idioms that we had done in awkward ways before suddenly became much easier. In fact, various things that you might think of as kind of traditionally more object-oriented idioms, where you have some kind of complex system with lots of different components that you want to be able to freely plug in together in an easy way, suddenly, we had awkward means of encoding in the past, suddenly became much simpler to encode, and this allowed us to rewrite big systems that had real modularity problems, and make it so that they were suddenly much easier to extend and expand.
Like there was a experience we had after first-class modules landed of a trading system that we had built which had a bunch of different components that were all feeding in together to build a big computation graph to compute some fair value of some security, and the original design had a bunch of, basically had a bunch of manual, wiring work you had to do. There’s like a little horrible runtime in the middle where you had to kind of express how everything got wired together, and it started out pretty simple, as these things often do, and as the system grew and got more complicated and we added more different kinds of things, that part where everything got hooked together got darker and nastier and more complicated to the point where we were afraid to extend the system anymore.
And we did a big rewrite of it with first-class modules, which gave a really elegant set of abstractions for having a kind of form that you could fill out that said what were the responsibilities of the thing that wanted to be a component in the system, and made it really easy to snap everything together. And I think we could have done this without first-class modules, there was enough power in the language to do it without, but it was a feature that made it much easier to do than it had been previously.
So I haven’t heard of this before. Is this like an orchestration thing or a visibility thing? I don’t really understand what this is.
So the question is, just for the purpose of the recording, to repeat the question, the question, what is this whole first-class module thing actually about? Is some kind of orchestrating large systems or some component-based something? So one way of thinking about it is, in an ML module, what you normally have is a collection of types that are exposed, and then a collection of values associated with those types. And that is not normally an object that you can pick up and, say, stuff into a hash table. That’s a kind of structural piece of your code that you can refer to, but you can’t completely freely manipulate.
First-class modules give you a way of handling these completely dynamically. So you could have a bunch of different modules that all match the same signature, and you can dump them into a lookup table, and then dynamically at run time decide which one you want and pull it out and smash them together and combine them. So again, I think this gives you only a partial understanding, but maybe gives you a little bit more of a flavor of the kind of freedom that this kind of system gives you.
Actually, there are ways of simulating this without first-class modules, but the first-class module’s a really elegant way of doing it, and reflected just a thing that we didn’t even know was possible to add to the language.
So, let’s talk about another one. Generalized algebraic data types, GADTs. So this is a generalization of a feature called algebraic datatypes that languages like OCaml and Haskell and Scala and F# have as kind of part of the ordinary, easy to use part of the language. An algebraic data type is a type that allows you to express a collection of different possibilities. In almost every language that you encounter, there are nice ways of saying, “I have a datatype that has a bunch of things together,” like a record, or a class. I have this and that and the other all combined together, it’s easy to construct values that have that shape.
What’s less common is to have, in languages, the ability to say, “I have this or that or the other,” the ability to express disjunction instead of conjunction. GADTs add to that some extra precision at the type level, which is to say, the way you interact with ordinary algebraic data types is you do what’s called a pattern match. You say, “I have this value that’s a bunch of different possibilities, I’m going to write down a case analysis that breaks down and sees which of the different possibilities there are, and then depending on the possibility, I will dispatch different logic for the different cases.”
In a GADT, what it lets you do is it lets you, when you get down to that case, you’re allowed to learn extra type information. You get to learn some more specific things about the type than you knew at the top level. And there’s a bunch of technical reasons, which I don’t want to get too much into, why GADTs behave the way they do and why ordinary variants don’t, but I mostly want to point out a couple of different superpowers that we got from it that, again, we didn’t expect.
So when you look at GADTs in the usual programming language literature, it sounds like the kind of nonsense that gets added to your language when you allow people who write compilers to design your programming language, which is to say it sounds really useful for designing little domain-specific languages. This extra precision at the type level lets you do clever things like encode extra, some of the invariant … You build a little domain-specific language, you write down a little abstract syntax tree in your language that represents the expressions, and then if you want to have some type system for it, you have to write that as some extra level, ordinarily, and GADTs let you pack some extra type information into these little domain-specific languages.
And when I first heard about this being added to the language I was like, “Great.” Like, we have a finite complexity budget, here is this thing being added that seems useful for stuff that I don’t do. Here I am, a poor systems programmer, I do not spend most of my time designing programming languages, what are these going to be good for? And it turns out, a lot. They’re good for a lot, and they’re good for a lot in systems programming, which is a thing that we totally didn’t expect.
There are really two different kinds of things that came out of GADTs in our code base. One of them is it turns out they’re really good for expressing code where you have very precise control over memory layout, but can have a discipline at the type level that feels like the ordinary way you operate in a language like OCaml. A really nice thing about OCaml is, I mentioned you have these or types, where I have this or that or the other, and the and types, we have a bunch of things together. A really rich way of expressing structure is to have layered combinations of ors and ands.
It turns out that’s a very powerful way of expressing all sorts of invariance about the structure of your data. And you often want that structure, but you don’t always want the memory representation it implies. In a language like OCaml, there’s a very particular garbage collection intensive heap memory model of how all these things are built, which is not what you want if you want to write really fast code. If you want to write a really fast packet processor, in whatever language you like, I can tell you how your program’s going to work. You’re going to have a region of memory. You’re going to DMA into that region of memory. You are going to read some bytes off of that region, you are going to mutate some things off the side, maybe you’ll send another packet, and then you’re going to do it again. And if you want to handle a few million packets a second, your program will look like that.
And the thing that GADTs it turned out gave us was a way of building a kind of type safe face around that representation, that let the thing behave mechanically like it needed to to be fast enough, but gave you control at the type level that made it feel more like the ordinary programming you want to do in language like ML and get the ordinary safety benefits that you get from that kind of operation.
The other thing which I’m not going to go to as much is GADTs give you a nice way of providing what are called existentially quantified types, which is a really pointy-headed PL way of saying it. But the kind of very short capsule summary of it is, most of the time in a language like ML and like OCaml, you talk about type variables, generic code that operates, you say, “This operates over any type. This function can modify lists no matter what type they are.” And that’s very useful, but sometimes you want to say, “I want to operate over a message of an unknown type, but there’s just one unknown type. I don’t know what it is, but there’s only one thing.” So sometimes it’s universally quantified, sometimes it’s existentially quantified. And that existential quantification turns out to be really important for, again, these kind of high performance message-oriented systems as a way of modeling what’s going on there. And these were outcomes that, again, we just totally didn’t know would be useful, and it was missing expressivity in the language that we just didn’t expect.
I feel like those were some intense type-oriented, maybe nonsense-sounding examples. Here’s a really simple one. Merlin is a system that provides IDE-like features. What does that mean? It means when you’re working on your program, you want to look at a particular value and say, “Oh, what is the type of that?” Or, “Where was that value defined?” Or being able to look at a value and say, “Oh, pull up the documentation for that value.”
And when I started here, and for a long time I sort of thought, “Oh, we don’t have that stuff. Eh, it doesn’t really matter that much. The language is nice enough and easy enough to use, it kind of makes up for the lack of all these fancy Visual Studio, Eclipse garbage, IDE-like things. We just don’t need it.” And I think that was just the Stockholm syndrome talking. I think a thing that you get used to is whatever it is you have. I think one thing that I find surprisingly, makes it hard to reason about what the right way to operate in a programming language is, is that your mental model of how to build programs is constructed out of your experience building programs in the environment that you’re in, and it’s easy to get used to missing a tool.
And I really think there are two issues. Part of it was just straight up Stockholm syndrome, and part of it is that IDE functionality was less important early on, when there were not that many people, and the code base was relatively small, and things were relatively simple. But as we’ve grown, and there are more code bases to get into, the ability to quickly navigate some new code base that you’ve never seen before is enormously valuable, and automated tools to do that help a lot. And it also helps the people who are spending a smaller fraction of their time programming, or people who are just starting up, the ability to interactively explore and get the system to explain to you what it’s doing turns out to be a really big deal, and a bigger deal as the organization gets bigger.
Here’s another thing we didn’t ask for: PPX, which doesn’t really sound like anything, so I should explain what’s going on. This is really all about how you do metaprogramming, and not everyone does metaprogramming, but on some level we all should. Metaprogramming is an incredibly powerful technique. Metaprogramming is just, in its simplest form, where you write code to generate code. And you don’t want to be doing that all the time. It is harder to reason about programs that write programs, but it is a really good superpower. If you step back for a second and look at the various streams of academic programming languages and practical programming languages, like the whole ML family in which F# and Scala and Haskell and all those guys I think live in, their secret sauce is type systems, and it’s a very powerful one.
And then if you look over to the other functional programming, the Lisp/Scheme/Racket world, their magic power is metaprogramming. And if you look at the type systems made by the Lispy people, or you look at the metaprogramming systems built by the ML people, both of them are kind of embarrassing to the other side. There aren’t really any systems that do a really great job of integrating them both together. And OCaml had a metaprogramming system. It was extremely valuable for us, but it wasn’t great. It was called Camlp4, and it, in some sense, sounds awesome when you first hear about it. Camlp4 came with a separate implementation of the OCaml parser, but an extensible parser. So if you say, “I want to extend OCaml with new syntactic constructs, and I can make whatever syntactic constructs I want,” and just change the language in arbitrary ways with this nicely designed extensible parser, and that’s kind of cool.
And we use that, so we use that, for example, to add little annotations to the syntax. So we could define a type and say, “With sexp,” where sexp is short for S-expression, and the idea was I would declare a type and say, “You know what? Write for me automatically the serializer and de-serializer into this S-expression form, which is a particular serialization format. Think like JSON, but better and from the ’50s. So simpler, indeed, and from the ’50s.
That was an incredibly powerful tool for us, because it meant all sorts of cases where we would otherwise need to do a bunch of boring and error-prone hand-coding of these serializers and de-serializers, we could replace with a system where we just once carefully wrote out a thing that automatically generates those for us. So it’s great, what is there to complain about? We have a metaprogramming facility, we can extend the language in whatever way we want.
So it turns out, this is really at odds with a desire to have good tools for your language. Because if everybody can write their own extension to the syntax, there’s no shared agreement as to what the hell the syntax is. So if you go back a slide and look at Merlin, how does Merlin, like Merlin’s this thing that’s supposed to look at your code and infer types and figure out what’s going on and be able to give you feedback, how does it even know what the hell is going on?
It turns out what Merlin did is it had its own weird extended parser where it had just implemented the popular Camlp4 extensions, and it just kind of knew enough about them to fake out the types just far enough to get the feedback that you needed. Let’s say you want to write an auto-indenter or an auto-formatter, it’s like, yes, but for which syntax, right? There is no syntax, so you can’t write a lot of the tools. Even a syntax highlighter, it’s not clear what to do.
So PPX was a move that in some sense took the OCaml syntax extensions story and took it one step closer to the good story that Lisp systems have. I should say, if there are any Lisp people in the world … in the room, I know there’s some in the world. I don’t mean to say the OCaml metaprogramming story is, at this point, good, I just mean to say it’s a little better, and the way it’s been made better is it’s more Lisp-like in the sense that in Lisp, and all of its descendants, these kind of syntactic transformations, these macros, operate as functions from the abstract syntax tree to the abstract syntax tree, right? There’s a well-defined syntax that everyone agrees on, and you don’t have this thing of a weird parser where you get to write any concrete syntax you want for the vast majority of these kind of macro expansion rules.
And then in the PPX world, what we basically did was the same thing, where we said, “You know what? Everything is just going to be a function from OCaml’s abstract syntax tree to OCaml’s abstract syntax tree,” but that’s not expressive enough on its own, because I might want to put in a little annotation that says, “Right here, please write for me the S-expression serialization/de-serialization code,” so I need more space in the shared syntax to do things like that.
So a bunch of new annotations were added, what are called extension points. So the syntax was grown to add a bunch of different things that you could say in the syntax that had no meaning. The compiler did not know what any of these annotations meant, but it was just extra space in the syntax that could then be used by the system for doing syntactic transformations to guide the transformations that you would in the end do.
So again, this was, I think people elsewhere in the OCaml community realized that this was important, and that it was specifically important to rationalize the tooling story and to get rid of a lot of the technical depth that had built up on top of Camlp4. And I think one of the reasons that we were nowhere near realizing this was important is our own engagement with the tooling at that point was still fairly limited, right? We were still much more in the user stance.
Okay, so that’s a bunch of the stuff about things that happened to us along the way. I should point out, most of them good. One nice thing about OCaml actually is a development group as a culture is that the language has grown conservatively. It mostly doesn’t get stupid features added onto it that you then later regret. It did early on, like I’m still kind of sad about the object system, which I wish had never been added, and there’s a few other corners I could complain about, but especially after the first few years, early on, there are grad students with PhDs to do, and they all need to write papers, and every paper has to extend the language in some way, and at some point you have to have the realization that just because they got their PhD, it doesn’t mean you have to merge their feature. And eventually the OCaml universe figured this out, and the development has gotten much saner from then. So there aren’t a lot of features that have landed that I’m sad about, and that continues to be the case today.
Okay, so since then we’ve, as I said, changed our stance that we’re much more active in developing OCaml ourselves. For a long time we did almost nothing, and then we spent time talking to the OCaml development team, and then after a while we spent time actually working on it, hiring more people who had been on the inside of that process and having them work on changing the compiler. And so one of the things that we built in this time is a thing called Spacetime, and this was a thing that was intended to fill a hole in OCaml’s tooling.
So Spacetime is a, this was, I think, done by people at OCaml Labs, just as a kind of … we made a fun tee shirt out of this. But the point of Spacetime is to give you a precise memory debugger. Basically, the ability to run a program and look at a snapshot of the heap and know from which place in the program every single thing on the heap was allocated. And it’s one thing, when you ask the question of like, “From which point in the program?” You might wonder what that means. Like, you could just say, “Oh, I want to know which source code location.”
But that’s a terrible answer to the question, it turns out. Because, for example, you might discover, “Oh, there’s this point in the code where elements of lists are allocated, and we have a lot of list elements, so that point in the source code allocated all the list elements,” but that didn’t tell you anything, just because all you know is you have a lot of list elements. A more useful piece of information is to have stack trace, to be able to see which stack trace is allocated which pieces of code. So you can get the moral equivalent of flame graphs that give you a breakdown of where and from which path of, through the kind of call tree, was a given piece of allocation arrived at.
But stack traces are kind of big, so the idea of, if you’re going to actually attach a stack trace to every single thing on the heap, that program is not going to run fast at all. So Spacetime is all about having a fairly clever data structure, a kind of stack trace tree, that keeps track of all the different possible stack traces and gives them unique integer identifiers, so you can just put those individual identifiers on the individual spots in the heap. It turns out in most programs you don’t explore that many different stack traces. You have to do a little careful stuff around infinite loops, like if you have a tail recursive loop, you don’t want to just have a unboundedly long stack trace at which the allocation happens, so there’s some careful tracking of that looping behavior.
It’s a very powerful tool, and it’s a thing … In fact, memory allocation’s something that’s gotten a lot better over time, although there’s still significant ways to go. Spacetime is one tool along a spectrum of different possible tools that you want. Spacetime is the good hammer if what you want is to know exactly the heap and understand every single thing that’s been allocated. But it’s still, even with all the optimization, they’re still kind of expensive, and the analysis can be expensive. We actually have special boxes with extra RAM just for doing analysis on a Spacetime run, because that itself can eat up a huge amount of RAM.
There are cheap things that you can do if you’re willing to do statistical sampling. So one thing we’re now working with other people on is trying to kind of extend this to have a richer family of different choices of how you do memory profiling. But I guess one thing, this reflects, is as we’ve grown and needed to do bigger and more complicated programs, we’ve had more need for being able to analyze these programs in an effective way, and tools like this help a lot.
Another related project is this work to make OCaml debugging, I guess make it awesome, or to make it not suck, depending on your perspective. So right now, you can debut an OCaml program with GDB, which there’s a whole, the question of like, is GDB a decent user interface for debugging, which is maybe a separate part of the question. But OCaml is a relatively reasonable Unix citizen, it sort of behaves in a fairly ordinary way. You can look at GDB and see and understand the stack traces. So that part isn’t problematic, but if you want to look at the values and inspect them, or you want to go and, you stop some piece of code, now you want to run a function from your program, none of that works.
So we’ve been doing a lot of work and actually hoping to get a bunch of this work into the upcoming 4.08 release of OCaml to try and basically put into OCaml more support for integrating with GDB, and in fact there’s a kind of dual, part of this project is extending OCaml itself, so it can generate binaries that are more debuggable, and also extensions for GDB itself, and in fact a generalized extension that can be plugged into GDB or LDB or any kind of debugger to give you both ends of this, both the instrumentation at the compiler level and the hooks at the tool level so you can have a really full debugger experience with a language. Which at the moment, is just not possible, and we basically tell ourselves it’s okay to do printf debugging. And I still kind of believe that in my heart, but I think it’s just the Stockholm syndrome talking.
Here’s another one that we’ve spent a lot of time on, which is we added this thing to OCaml called Flamda, which is a new IR, a new intermediate representation in the compiler. Here’s a thing you may not know about compilers: compilers are built as stacks of little languages. So the idea is you have a bunch of different representations of the same program, and then you have different phases, which either bring you from one stage to the next stage, or sometimes loop around in the same phase. Optimization Is often done in this way, where you kind of churn on the same level in the IR.
And Flamda is an IR that was designed to do better optimization, and particularly better inlining in OCaml. I think when you come from a language like C, I think people often underestimate how valuable inlining might be, because there are limits to how much transformation you can do in a C program, but even with inlining, and … You get more benefits than this, but a kind of gross first approximation is that a lot of the benefits you get from inlining a function in C are from not having to do the function call.
And in a language like OCaml, or really lots of different safe and managed languages, doing inlining does something else, which it gives you a larger scope which to analyze your program, and so your compiler can do various other kinds of optimizations, like getting rid of allocations. Actually, that’s one of the most important ones, is there are lots of cases where OCaml needs to allocate values, where really it seems kind of ridiculous that it has to do so. There’s like one function that produces a tuple, and another function that wants to analyze the data in that tuple and do something with the data, and the tuple itself is in existence for only a very short period of time.
In OCaml as it existed prior to Flamda, almost always, that allocation just kind of sticks around, because it’s not very aggressive in terms of inlining, and in order to figure out that the allocation’s unnecessary, you have to kind of expand the scope of what’s visible to the compiler enough for it to see that, “Oh, we allocated this thing and then we deconstructed it and we never used it for anything else, so I can just get rid of that allocation.” And the goal of Flamda was to make it possible to do much more aggressive inlining and to do it in a more principled way than the heuristic used by the compiler as it stands, to be able to do a lot more of that optimization.
And one of the important goals for us in Flamda, and I think we’ve made a lot of progress with Flamda, but we think we haven’t gotten all the way, like we haven’t quite grabbed the brass ring, which is, one of the goals that we really have is to try and make the performance of OCaml more predictable in this way. So inlining as it previously existed was very hit and miss, it was hard to predict when the inliner would and wouldn’t successfully inline a function, so it’s hard to predict when an allocation would or wouldn’t be successfully gotten rid of. And the place we want to get to with Flamda is to be able to kind of expand the scope of the kind of programs that we can write that don’t do any allocation, because we need to write lots of absolutely zero allocation programs, especially for our most performance-sensitive systems, by just expanding the set of things that you can reliably count on not being allocated.
And Flamda’s a real deep investment for the firm. It’s a multi-year project. We spent a few years on the first version. There’s a second, significantly more sophisticated version that we hope to get into the compiler by the end of next year that we think will … Like the current version, we run it on lots of our programs, and a pretty common outcome is the program is, without any extra work, 10 to 20% faster. That’s pretty good.
But the thing we really want to do is to make the kinds of coding disciplines that you need to make your program 100 times faster much easier to write, and we have real hopes that Flamda 2.0 will bring us a lot closer to that goal. Sure.
Can I ask a really stupid question? Is there a degree of coupling between Flamda and Spacetime?
It’s actually funny. So I think mostly no, which is to say I think they mostly interoperate fine, but there are some stupid technical reasons where if you try and use Flamda and Spacetime together, the compilation process is incredibly slow. Because Flamda makes things slower, and Spacetime makes things slower because of a really annoying lack of easy cross-compilation, so that when you compile something under Spacetime, you use a compiler that itself is running Spacetime, which is really stupid, because you don’t actually want to memory profile your compiler when you’re doing this. And then Flamda makes things slower because it’s just a more expensive pass. So it gets like extra double stupid slow when you do this together, but this is just some piece of nonsense that we’ll eventually just fix, and there’s no fundamental conflict between the systems.
All right, here’s another thing. So I want to talk about GADTs again. I’m not going to confuse you again about the type level stuff, but just sort of an interesting fact about the engineering of the compiler. Like if you step back and look at the OCaml compiler, in fact, look at OCaml the language. OCaml as a language is kind of beautiful. It’s a simple, fairly minimal language, very powerful. And then you look at its implementation, you’re like, “Oh, parts of this are like shockingly bad.” And one of the reasons for this is the language was written before people knew how to use the language properly. Which is maybe not surprising, right? It was a long time ago. OCaml was written in the mid-‘90s, and they were all still fairly new to using this language, and things that we think of as obvious best practices that of course you would use weren’t obvious to them, for obvious reasons.
There’s lots of engineering problems in various parts of the system, and one of the things that we discovered with GADTs as we started using them more is that they were a little creaky. Like you pick up some piece of the core, most well-honed part of language, and think this is like a beautiful, well-balanced thing, it is beautiful, works great in every possible way, and all the pieces are smoothly oiled. And you pick up some parts of the language, you’re like, “Oh my God, has anyone ever used this thing before, and why does it make that terrifying noise when I turn it,” right?
And the module system actually feels a little this way. It’s clear that people use the core value system a ton and the module system much less. Indeed, when people early on, when they designed the language, they’re like, “Huh, I wonder how useful this module system will be.” It was sort of kind of conjectural. And GADTs also had some issues. It turns out there’s some nice features in OCaml, where without going into the details, there’s some places where if the type inferencing engine can figure things out, you can write things a little more concisely. You can drop some qualifiers, you don’t have to say exactly where a value came from, as long as the type system knows what the value is.
And this worked great with ordinary algebraic data types, and it didn’t work with generalized algebraic data types. And I, again, thought, “Oh, there must be some deep reason,” you know, “Type inference for GADTs is harder, and there’s lots of theoretical problems.” And it turns out, no, no, no, the reason it didn’t work is because there are two implementations of the pattern-matching logic in the compiler. There’s the good one, and the one that supports GADTs. And the one that supports GADTs can do some more things, but it has some scary bugs, and its performance wasn’t great, so people didn’t want to use it for everything. So they flip over to the bad implementation when they need to, and the rest of the time they use the good implementation. And so we just engage with this like, “Oh, this is just an engineering problem,” and we went in and carefully went through and figured out what the bugs were, and took the bad implementation that supported GADTs and made it a good implementation, and then made it the only implementation.
And then, all the features that didn’t always work in all the places now work in all the places. And I think just one of the lessons here is sometimes the things you do are about fancy, clever, new ideas, and sometimes the things you need to do in a language like this are just apply some elbow grease. There’s a big community of people working on this, they all have other day jobs, they’re publishing papers, a lot of the people who wrote this, and maybe they don’t want to spend all their time engineering various bits of the compiler to make them lovely and work for everyone’s purposes, and so sometimes the thing that an organization like ours can do is just bring the engineering discipline and the willingness to commit serious engineer time to fixing the problems that aren’t foundational problems, but are just issues of having the resources to apply them.
So some problems are about fancy new things. This is one of the features that we are involved with and lots of people are excited about for the language. And I don’t want to talk about it a lot, but it’s just sort of an interesting example. So modular implicits, it sounds fancy. If you know what typeclasses are in Haskell, it is in some sense OCaml’s answer to typeclasses. I like to think it is a somewhat cleaner and better-engineered thing that made a few fundamental better decisions than the typeclass system in Haskell. You can count on OCaml to have a more disciplined answer 20 years later. Take your trade-off as you will.
In any case, the key thing that this lets you do is it’s, similar to a feature that I was alluding to before, it’s a way that you can leverage type information to make various kinds of implicit decisions, to basically allow you to write code that is less explicit, and in some sense more general, more polymorphic, in a lighter weight way. Essentially, you can have cases where you want some functionality and you don’t know which type it is and you don’t have to say it explicitly, just the type system will infer what type you’re talking about and it will search to see if there’s a satisfying implementation, and just implicitly grab it for you and use it. And this is, again, an example of a multi-year project, multiple people have been thinking about this for a while, there’s some theoretical work that’s been going on, and everyone in the OCaml community wants it, and it’s not clear how many years it will take to get, because there are lots of things that everyone wants, and there’s a lot of engineering work that’s needed to be done to get it done in an acceptable way.
Another super fancy thing that everyone wants is typed algebraic effects. This is a way of tracking effects. What are effects? So in a language like Haskell, you use these things called monads, I’m not going to talk about this for too long, these things called monads for keeping track of where you’re doing side-effecting things, like sending network packets or mutating state and things like that, and you can have a clean way of separating out the effectful part of your code from the non-effectful part of your code.
Algebraic effects are another way of treating effects in the context of a functional programming language, and typed algebraic effects are a type system on top of that to allow you to track where these effects are used, and it can be used for, the sort of newfangled algebraic effect idea is there to allow us to do cool things like have a big, concurrent, multicore system, with a scheduler that’s not baked into the system, but anyone can just write their own scheduler. So special kinds of effects are used for some of those tricks.
But the type level control allows us to track types the whole way through, so it allows us to retrofit OCaml as a language where you can actually separate pure code from imperative code all the way down, and do it in a, shockingly, in a backwards compatible way. So this is, I think, a really interesting language feature. I feel like this is one of these features where we’re working on some, we’re mostly working on because some of the people who work in our chosen compilers group are among the people who helped develop the initial proposals for doing this, not because it’s an internal firm priority.
And I feel like I sit kind of halfway on these kinds of features. Like, I can see that they’re useful, and I don’t know how I’m going to come out the other side of the Stockholm syndrome. It’s a cool idea, it theoretically makes a lot of sense, I can see some advantages, it eats up some of the complexity budget. Is it going to be worth it? Don’t know yet. I think part of the thing you learn here is that you don’t really know how things are going to turn out, and you really have to, in some ways, trust the judgment of the people who are thinking hard about this and see the last six things they suggested, did they turn out well? And think how that suggests to you the next ones are going to turn out.
So, a few kind of quick big picture thoughts of what are our actual priorities in terms of things that we want to do, ways in which we want to push the tool stack and the compiler. So one thing is, pushing for better usability throughout the entire stack. So we’ve had a pretty good tool story internally, and the OCaml world tool story more generally has, in various ways, lagged behind historically. There are a bunch of ways in which it’s easier to be an OCaml developer inside of Jane Street than outside of Jane Street. We experience this a lot, where interns would come in having taken a class at Princeton or Cornell or various other places where they teach OCaml, and then they come in and use OCaml and suddenly it’s like, “Oh, it’s much better here. Why can’t it be this good outside?”
And there’s been the reverse thing of sometimes people have developed really useful stuff externally, like Merlin, which again, was created not for us, or another thing, OCaml Format, which if you know the Go ecosystem, OCaml format is like a Go format like opinionated formatting tool. That was created by Facebook, not by us. And over time we’ve, I think, really come to value the ways in which we can make the ecosystem better by merging more the internal and external systems. So one of the things that we’ve had for a long time that’s been really good is we have a really good build system story. Like, I have various complaints I can make about our internal build system, but overall, it’s kind of great. It solves a lot of problems, it’s very well engineered, and we ended up making a kind of open source version of … The internal system’s called [Jenga 00:54:40], we made an open source version of Jenga called Dune. Like many good things, we made it kind of by mistake. We sort of tripped and wrote another build system.
What happened was, there’s this open source release process that we had, because we release a lot of open source code, like a half a million lines of the stuff we have internally is out on GitHub, and pushing that out constantly with every release can be painful, because the external build tools were kind of terrible, and in any case, different. So we had to, with everything we open sourced, rewrite the build rules.
So internally, this tool Jenga had little files called J build files, which were the specifications for the build that end users wrote, and we thought, “Well,” or in fact, a guy named Jeremy Dimino in our London office thought, “Well, maybe what I can do is I can write a J build interpreter. Not a real build system, just a little build system that doesn’t have to do incremental builds or anything, it just has to do builds portably and fast. And then we could release our packages and people could build them and use them and it would be great, and then we won’t have to do this horrible thing of rewriting all our build rules all the time.”
And he made the terrible mistake of making that system really fast. Like you took a thing that was using ocamlbuild, and you ran it under what was then called J Builder, until Borland objected, or rather the ashes of Borland, I don’t know who acquired them, but anyway, also J Builder sounds like a Java ID. It’s not a great name. But you can see why we called it J Builder, things were building from J build files. Anyway, so you switch to J Builder, and suddenly the builds became five times faster. And I don’t mean the overhead of the system, no, the end to end build was five times faster on a lot of different projects, so people suddenly wanted to use it, and we started making it a little better. And now it’s evolved into a full-featured build system, which is now the most popular build system for OCaml, certainly the fastest growing one, and we are shortly, in the next few months, going to replace Jenga with Dune, and kind of swap out the core engine, and that’s going to be our one and only build system and it will serve both the internal and external purposes.
And just in general we feel like this is a useful direction, of finding key shareable pieces, and making real collaborations with people on the outside in Dune, which it’s now called, now that we had to rename it, is, I think, a really nice example of a real collaboration where there are people inside of Jane Street who contribute to it seriously, and there are people outside of Jane Street who contribute to it seriously. It’s a really active project. On GitHub you’ll see lots of different people contributing, and I don’t think that’s a model that we can use with everything, there are lots of things where we get a lot of value out of the tight integration within our own internal systems and tools, but for some key pieces we think it’s really valuable and it’s, I think, good both in that it gets other talented people involved in helping build the ecosystem, and it helps grow the overall OCaml ecosystem, on which we are abjectly dependent.
Like, one thing that we worry about is, it’s not just a question of, “Will OCaml continue to be a useful tool?” Another thing we worry about is are people just going to hate it? Will OCaml one day be COBOL, like a language that people actively avoid? And that motivates us a lot to not just contribute to our own OCaml experience, but to contribute to the larger language ecosystem, because we need to keep on hiring great, talented people to come work on it, and it has to be a vibrant ecosystem for people to view the programming language as something that attracts them rather than something that makes them feel like they don’t want to join in.
Again, I talked about this some before, but another thing we really care about is making the compiler itself cleaner. Both the compiler and the language, finding places where we can simplify and improve and make the implementation easier to engineer, and make the language itself smoother and more uniform and easier to understand. We have a long-term investment. We’re going to be using this in 20 years, and we want it to continue to be an excellent piece of technology, and we need to kind of give a lot of effort to the core engineering work as well for that.
Another thing that we care about a lot is performance engineering, and doing more work to, again, to have support at the optimizer level for generating better code, and at the language level for providing good idioms to make it easy to write performant code. Those are our big focuses, and we have lots of ongoing projects to improve that in a number of different ways.
Anyway, I think the big picture story about this is, this is not something we’re stopping. Whether it was a good idea or a bad idea to introduce OCaml into this company, oh my God are we dependent on it now. We have like 12 million lines of OCaml, it is our primary development language for almost everything that we do, we have hundreds of people who know it and use it, and we are really incentivized to help grow and extend the language and make it as useful as we can, because it’s just part of the air we breathe at this point. And I think it’s an interesting endpoint that you get to when you decide to take on a minority technology. This is a kind of you break it you bought it phenomenon. You used some weird piece of technology and you were successful, it’s like, well, you’re kind of responsible for it to some degree. Jane Street does not own OCaml in any way, just try to get something past Xavier Leroy that he doesn’t like, and you will discover that Jane Street does not own OCaml. There are other people who are in charge of the overall development of the language, and they make the decisions. And we try and help in various ways, but we are in no way the final arbiter.
But we are nonetheless deeply invested and want to do all that we can to support it and grow it. We think it’s been a good experience both for the overall language ecosystem, and for the firm itself. And that, I think, is all I got. Thank you very much. I’d be happy to take a few questions, if anyone has.
I can’t remember when polymorphic variants came into OCaml, but did Jane Street adopt those right at the beginning, or is that a feature you guys started picking up and using more?
Ah, so the question is when did polymorphic variants get added to the language, and how did Jane Street go about adopting them? So they are old, they came in around the time the object system came in, which is I think around ‘95. When O got added to OCaml. It was previously Caml Light and then, hilariously, Caml Special Light. The joke Caml reference is apparently no longer funny. And then it became OCaml when it got, I believe, the object system, and I think at the same time polymorphic variants. We used them fairly early on, and I think actually as the language has grown in other ways, we now use them less and less. Because some of the benefits they provided were about concision, and there are now other ways of getting that concision with some of these more type-directed inference techniques. I think we think of that as, again, if I could go back in time and get rid of that feature, I might. Along with the object system, I’m not sure it’s worth it to wait, and there are other ways of achieving some of those goals.
What was the history on the compiling to native machine code for certain CPUs, was that you guys that built most of that, or was that-
… [crosstalk 01:01:57] was there from-
So yeah, OCaml, I mean, the backend stuff was all there and all very good from the beginning. OCaml had a native code compiler from the first time I ever laid eyes on it, and a good native code compiler, actually. It’s interesting, it’s called OCaml Op, which is a little bit of a lie, because it’s not really an optimizing compiler. OCaml has a really simple, straight ahead compilation strategy, it doesn’t do a lot of optimization. But it does still, if you write your code in a pretty simple and straight ahead way, it generates very good code and very efficient code, and that was there from the beginning.
[inaudible 01:03:07] materials to learn more [inaudible 01:03:07] the compiler of OCaml? [crosstalk 01:03:12] any books or pieces that you can read to better understand the internal-
So I think OCaml itself, I don’t think there are any really good available guides for understanding the compiler. I think if you want to understand compilers in general there’s Benjamin Pierce’s Types and Programming Languages, TAPL, and that’s a great book. But I don’t think I have a good recommendation for a great source for learning OCaml itself, which is not a great fact. It would be nice if there were such resources out, but I think there’s nothing really good for that that I know of.