In this post, I’ll explain how I compiled an OCaml program to run on a TI-84+ CE calculator. 🐪

A 3D cube rotating on a TI-84+ CE calculator

Background

OCaml is a somewhat niche functional language that I’ve enjoyed learning over the last couple of years. I’ve also been a calculator enthusiast since high school, working on projects like PineappleCAS. At the time, the calculator toolchain only supported C and (e)z80 assembly. Now, talented folks have set up a toolchain that leverages LLVM so you can program in C, C++, Rust, Zig, and others. OCaml is notably missing from this list. Let’s fix that!

Compiling OCaml

There are native OCaml compilers for x86, ARM, and PowerPC. There is also a bytecode compiler, though it’s largely undocumented (see interp.c). All of these backends need a runtime that includes a garbage collector and native functions to do useful things like print to stdout and read files. Unfortunately, these artifacts tend to be large due to the OCaml compiler’s lack of dead code elimination.

I really like the idea of compiling an entire OCaml program into a single highly portable ANSI C file that we could compile with the calculator toolchain (or any C toolchain!).

This idea isn’t new: ocamlcc compiles OCaml bytecode to C. OMicroB compiles OCaml to small devices by optimizing the OCaml bytecode and using a lightweight virtual machine.

For my approach, I wanted something that is:

  1. Highly portable
  2. Interacts well with the OCaml build system
  3. Small – The generated code and runtime should fit in the 256k RAM on the TI-84+ CE

Note that “efficient” and “practical” are missing from this list :)

Enter Js_of_ocaml. Js_of_ocaml powers nearly all of the OCaml website frontends that are written in OCaml. (Yes, that’s a real thing!). First, the OCaml is compiled to bytecode, then Js_of_ocaml optimizes that bytecode and lifts that bytecode into javascript.

The high level idea is as follows: we’ll write a new backend for Js_of_ocaml to emit C instead of javascript. Then we’ll just need to add a couple native functions and a garbage collector. The great thing about this approach is that Js_of_ocaml is well maintained, so we can expect it to keep up with OCaml as the language and bytecode changes. Js_of_ocaml also has a strong dead code elimination pass, and it is first-class supported by dune, OCaml’s build system.

New C Backend

Because most javascript constructs map trivially to C, we can mostly just use the real Js_of_ocaml backend as a reference and hack out our C backend. We can take some shortcuts, like using goto statements instead of reimplementing complex logic to map things into if/else blocks. The only catch is that we have to write a garbage collector.

Garbage Collection

In order to write a garbage collector, we need to know which objects are alive at the time of garbage collection. The native compilers can do this by scanning the stack and CPU registers for pointers to OCaml heap objects. We can’t do this because we want our C file to be as portable as possible. Instead, we’ll replace all local variables with explicit reads and writes into a global stack. That way, we can scan the global stack to find all of our live objects when it comes time to GC. Here’s a conceptual example of what I mean:

value global_stack[1024];
value *bp = global_stack;
value *sp = global_stack;

void transmogrify(value string) {
  bp = sp;
  sp += 2; // Allocate space for 2 local variables

  bp[0] = caml_copy_string(string);
  bp[1] = caml_reverse_string(string);

  // Do something with these local vars

  sp = bp; // Deallocate the two local variables
}

void gc() {
  // Scan through global_stack from 0 up to sp
  // and mark those values as "alive"
}

We’ll consider garbage collecting any time we want to allocate a new OCaml object. We’ll garbage collect if either:

  1. The allocation would put us over the max memory limit
  2. The allocation would put us over 2x the memory that we were at after the last collection

When we garbage collect, we’ll do a simple mark and sweep. First, we’ll scan the global stack. When we encounter an OCaml pointer, we’ll follow that pointer and every pointer that object has recursively, marking them all as alive. When we’re done, we’ll free every other object that wasn’t marked.

Runtime

In order for the OCaml code to do useful things, we can use the extern keyword in OCaml to call any C functions that we write. We can then write the C functions to support a minimal standard library and a small TI-84+ CE library that can do things like drawing to the screen.

Build system

Because Js_of_ocaml is first-class supported in OCaml’s build system, so also is our C_of_ocaml. We can ergonomically write a spinning cube OCaml program for the calculator with LSP support and dune build commands working out of the box.

Conclusion

Feel free to check out the generated C code for a simple OCaml fibonacci program here. You can compile it with gcc! The first half of the C file is the runtime, and the second half is the generated code.

Many OCaml features (floats, exceptions, etc) aren’t supported. In fact, the spinny cube demo uses fixed point numbers (with 24 bit registers!). Maybe in the future I’ll try to use this project with wee to get OCaml running ~anywhere. I hope you found the post interesting! Thanks for reading. All the source code can be found here.