[ML'26] Self-Tagging Numbers

Self-Tagging Numbers (Video, ML 2026) John Reppy, Ben Wakefield, and Byron Zhong (University of Chicago; University of Chicago; University of Chicago) Abstract: ML implementations generally require values in polymorphic contexts to use a uniform representation. To implement garbage collection, this representation must distinguish pointers from other values. For numeric values, most systems heap-allocate floating-point numbers and encode an integer $n$ as the tagged value $2n + 1$. But boxing incurs allocation and memory traffic, and tagging sacrifices one bit of precision and adds overhead to arithmetic. Recently, Malençon et al. proposed “self tagging” as a technique for representing floating-point values in a Scheme compiler that eliminates most heap allocation for floats. Inspired by this work, we have extended the idea of self tagging to replace the tagged representation of integers currently used in the Standard ML of New Jersey compiler. In our context, we can take advantage of static types to keep numeric values in their native representation most of the time (especially for arithmetic). When a value enters a polymorphic context, however, the compiler applies a reversible bit transformation that makes most values distinguishable from pointers and other bit patterns reserved by the runtime system. Uncommon values that conflict with those patterns fall back to heap-allocation. Self-tagging preserves the full native range of integers, removes tag manipulation from ordinary integer arithmetic, and avoids heap-allocation for most values. In our preliminary experiment, where we make the 64-bit integers as the default, across the benchmark suite every integer observed crossing a polymorphic boundary can be represented without heap allocation. Presentation at the ML 2026 workshop, August 28, 2026, https://icfp26.sigplan.org/home/mlfamilyworkshop-2026 Sponsored by ACM SIGPLAN.