Representing Type Lattices Compactly

With co-author Brett Simmers! The Cinder JIT compiler does some cool stuff with how they represent types so I’m going to share it with you here. The core of it is thinking about types as sets (lattices, even), and picking a compact representation. Compilers will create and manipulate types with abandon, so all operations have to be fast. We’ll start from first principles, assuming we’re analyzing a language like Python, and build our way up to roughly what Cinder has (and we could go further from there). Types as sets Types, as a concept, name sets of objects—sets of instances. Some types (say, int8 ) have finite members. There are only ever 256 potential values for an 8-bit integer. Some times, (say, list ) are infinite. Given enough storage, one could keep generating bigger and bigger instances. Since it’s not possible to store all elements of a set, we refer to types by a name. This reduces precision. Maybe there is some bizarre case where you know that an object could be one o ... Read full article.