Type Erasure

Type erasure is the removal of an object's typing information from the runtime system/image of a computer program (more accurately, it is the decision not to put it there in the first place).

When a compiler (etc) types a program (in other words, it solves the CompileTimeTypingProblem for a program), it has a collection of terms with associated types. How to encode this stuff in the runtime image? There are several different choices to be made, depending on the language and its semantics.

Is TypeErasure important? Generally, for large objects, it matters little - the runtime memory cost of the type information is one structure (of some small size) per type that the system knows about, and one pointer per object. For an object consisting of dozens or hundreds of bytes (or more), one additional pointer isn't noticeable.

For small objects, such as numeric types, booleans, ConsCells, characters, enums/units, etc. - the overhead is tremendous. A boolean needs only a single bit to encode; compared to 32 or 64 bits for the size of a pointer (on a modern machine). In many cases, it is desirable to have objects of this sort occupy a single machine register (an important optimization), if they have to lug around a type pointer it is a huge problem. Many runtimes for languages that never perform type erasure use various "hacks" like reserving one bit for an "object/intrinsic" flag, redefining ints to be 31 bits rather than 32; and insisting that pointers be word-aligned (a limitation present on most CPUs regardless). One of the distinguishing features of the LispMachine (the hardware, that is) is extra "tag" bits which allow the type information to be economically stored. Many like to flame JavaLanguage for excluding intrinsic types from the family of objects; it is precisely this sort of hassle that lead the designers of Java to make that decision (the semantics of Java are such that the intrinsic types may always be subject to type erasure). That said, the BoxingConversions of C# might be a more elegant solution.


TypeTheory

EditText of this page (last edited December 17, 2004) or FindPage with title or text search