OCaml

What I have been doing

Most of my work has been replacing calls into the C programming language with native machine instructions.

Every chip speaks its own language, a set of "instructions" telling it what to do. OCaml, for a number of operations, does not say them directly. It asks C to say them on its behalf, which is a bit like everyone in a ten euro hostel in rural Poland speaking English at each other and hoping for the best.

Now, I hear you asking, "what's wrong with C?" Nothing. C is wonderful and will exist until the heat death of the universe, or until someone asks an AI to build Skynet and adds "make no mistakes". But it is not the language the chip speaks either, so you end up translating one language into another into a third, and every hop costs you something.

A chip only has a handful of places to hold what it is working on. Call it bench space in your kitchen, and there might be sixteen or thirty-two spots on it. Everything else goes in a drawer, which is slower to get at. Part of the compiler called the register allocator decides what stays on the bench and what goes in a drawer, and it is very good at this.

Then a call into C turns up. C has its own rules about how much of the bench has to be clear before it will start, which is called the calling convention. So the allocator stops, puts most of what it was holding away, makes the call, waits, and gets it all back out afterwards. Which is how there's now a spatula in with the utensils and my tupperware drawer is even more of a mess. Putting things down like that is called spilling.

Or it's like being passed out in barracks and having your bed, your chair and your trusty Moro bar spilled all over you, and not in the place they definitely should be.

Burnham Military Camp, Christchurch.

That is a register allocator spilling.

So something the chip could have done in one instruction turns into tidy up, introduce yourself, wait, unpack again. Put that inside a loop running a million times and it adds up.

With atomics it is worse than just slow. They are the instructions that let several parts of a program touch the same piece of memory without treading on each other, and the whole point of them is saying precisely when everyone else is allowed to see what you have done. The chip has exact words for that. Going through C means saying it in the intermediary's vocabulary and hoping your intent survives the trip.

Emitting the instructions natively means OCaml just says the thing.

The button nobody presses

Fun fact. Almost every microwave with a number pad, built in the last thirty-five years, is also a stopwatch. Not a cooking timer, an actual countdown that beeps and cooks nothing. You could time your planks with a microwave at the gym and only get slightly more stares than usual and almost nobody has ever pressed the button.

Chips are like this too, and square root is one of those buttons. POWER, RISC-V and s390x, which is the mainframe, all have an instruction for it. You hand the chip a number, you get a square root back, and that is the whole transaction. OCaml was not pressing it. It was stopping what it was doing, calling out to a C library, and waiting for the answer to come back.

Fused multiply-add is stranger. It multiplies two numbers and adds a third in one go without rounding in between, which gets you a closer answer than doing it in two steps. Four of the five chips already emit it when you write a *. b +. c. They spot the shape and fuse it for you, unasked, and that changes the answer you get rather than just the speed. But when you asked for it by name, with Float.fma, OCaml went off to C. So we fuse when nobody asked and call out to the C maths library when someone does.

Then there is the kind where something is simply broken. A shared library on the mainframe, what is called a segmentation fault, and nothing to go on. When a program calls a function for the first time, the system has a little helper that goes off and finds where that function actually lives. That helper tucks its working values away in what it assumes is scratch space, like a little notepad for the chip, on the stack. OCaml's stack is not laid out where it expects. So the helper wrote positive infinity and a very small number straight over the middle of a live data structure, and some time later the program followed a pointer that was, by then, the number infinity.

I recognised the shape of that one because I spend my spare time staring at mainframe code, which I promise is fun. On z/OS this bug has a name. It is a storage overlay, and the system hands you a structured error message and a dump to work through. On Linux all you get is sweet nothings and a wall of text (maybe).

The five machines

OCaml targets five architectures and they do not agree about much. The mainframe has been backwards compatible with punch cards, x86 has been backwards compatible with a chip from 1978, Arm is in every phone on earth, RISC-V is off on its own bender and POWER sits in the corner being left out. As mentioned, different chips speak different languages, and if you write in that language incorrectly it throws up its hands, says it doesn't understand you and hey-ho you've got a crash. That, or even worse, it understood the wrong thing and is now spitting nonsense.

Which raises a reasonable question about how someone in Auckland tests anything on an IBM mainframe and like four other computers.

Now lucky for everyone I haven't had Auckland's latest data centre in my apartment the whole time. The machines come from cfarm, the GCC Compile Farm, a set of machines that companies and universities donate so people like me can test on things. The rounding work was tested on an Applied Micro X-Gene, an Intel Xeon, a POWER10, an IBM z15 and a SpacemiT X60, which is a RISC-V board. I do not own any of them.

Real hardware, too, rather than emulation. An emulator will happily tell you your instructions are valid and your logic is right. It will tell you nothing about whether the ordering guarantees hold, because it never reorders anything.

Now turning up to a place going "hey bro I totally tested on 5 machines bro trust me" is a bad idea generally, so I keep the output. Every investigation goes into a repository called bits and bobs along with the assembly, the disassembly, the logs and the notes I made at the time. If you want to check that a POWER10 really did emit the instruction I say it did, it is in there.

Now you may ask "hey isn't a raw dump of what the machine is doing like...a lot?" and well, yes, it is. GitHub having trouble and crashing every couple of weeks or so is totally unrelated.

By overloading GitHub's servers with yet another machine code dump.

Why OCaml

Well the reason is how I got into programming in the first place. A few years ago I began reading, collecting and eventually resurrecting historical software and emulating hardware. I've got a 50GB documents folder that has everything from the Voyager spacecraft that's currently in interstellar space to Soviet computers controlling nuclear reactors. Konrad Zuse's handwritten notes, Grace Hopper's original compiler specification, and British and American defence code. That's to name a few. The trouble I've hit is "what happens if the scanned paper documents aren't enough"? What happens if something is completely undocumented and only referred to? What happens if the only thing that remains is the software, and not the understanding of how it worked in the first place.

When resurrecting HALMAT, the intermediate language used in the Space Shuttle by NASA, I hit this wall. The manuals have been lost to time and all that remains are their echoes in other historical communities. When trying to look for something that could help and hitting a wall each time, I eventually found my way to OCaml. I could describe the grammar of HALMAT, and OCaml, with Menhir, could tell me where I had got it wrong. You write down what you think the rules are, feed it the real files, and when your description is wrong it stops on the exact line that broke it rather than quietly carrying on with a wrong answer. Feeling your way around a dark room only works if something tells you when you have walked into a wall. Enough walls and you have the shape of the room. This led to me being one of the few people outside of the original engineers who knew what the language that helped build the International Space Station and the Hubble Telescope looked like.

My work has been used to assist the Virtual Apollo Guidance Computer project and you can find out more information here and here.

The rationale for working in the OCaml compiler is rather simple. It's a way of giving back and contributing to something that enables my passion projects. It's because of the fantastic work of OCaml developers that I was able to achieve any of this in the first place, and honestly without it I would probably still be running around in the dark bumping into a suspiciously space shuttle shaped object.

Where next

Me and my closest friend have this inside joke where we both look at each other and go "so, what now?" Well currently I'm looking at making OCaml emit more native instructions and get it to run on GPUs with my own compiler, which is on GitHub as Booth. I have had an OCaml kernel running on my own card all week. I've also been making some tooling for the language like a plugin for a code editor called Notepad++.

The logo for my GPU compiler, Booth.

But even better, that's to say nothing of the historical work underway. I've managed to find documentation for the Coral-66 language which is still being run in British defence to this day. So currently I'm looking at writing a compiler for it in OCaml. The best surviving compiler was written for a Ferranti Argus 500, a British machine from the sixties that doesn't really exist anymore. Because of my work on z390 I've learned more and more about how you can build a compiler out of nothing but assembler macros. Which in non-technical terms means that to get around the fact I can't break into a British nuclear reactor to use their last remaining Argus computer, I'll have to make my own computer wear a wig and pretend it is one.

It has been a privilege to contribute to so many Open Source projects like OCaml and work with many brilliant people every day and I hope to continue to do so. The Open source movement is fundamentally the reason why someone like me, someone from the arse end of the Pacific, with no compiler industry, with limited opportunities within tech is able to continue to do this at all. It's because of that radical idea, started by people like Sister Mary Kenneth Keller (the first woman in the United States to earn a doctorate in computer science, who worked with Thomas Kurtz on BASIC and spent twenty years running a computer science department she founded) and Arnold Casinghino (creator of the CBT Tape), that knowledge should be freely shared and given. That everyone should be given the ability to learn how computers work if they want it. And most importantly, that some random Kiwi dude can build that emulator for a computer a solar system away.

Thanks

Thanks to Miod Vallat, Xavier Leroy, Nicolás Ojeda Bär, Olivier Nicole and KC Sivaramakrishnan and the OCaml team who have reviewed my work. Thank you to Gabriel Scherer and the OCSF team for your support as well.

Music I was listening to while writing this: this, and also this.

Want to learn OCaml? Here's a great place to start, and this wonderful book translated from French.

Don't want to make the leap into programming because its a bit scary? Thats fine. Being afraid of the unknown is what makes us, well, us. I left the Army knowing sweet nothing and I always run into things I don't know. But figuring it out is where the fun is in the first place! A piece I'd recommend is So you want to be a Wizard by Julia Evans.