Kurt Stephens

Abstract

I have been interested in optimal low-bit tag schemes on machine words in latently-typed languages. There are different schools of thought on how to handle the trade-offs between Fixnums (integers smaller than word size) and allocated objects.

Ian Piumarta’s libid object library is a very simple prototype-based object system with unresolved method delegation. It is used in the Pepsi/Coke COLA system (available at http://vpri.org/fonc_wiki/index.php/Sources) as the basis for all object representations and meta-behaviors. libid assumes that a reference to an object’s method table, or “vtable” resides at the word before the object’s address.

Type tags in Ruby VALUE

Internally, values in Ruby are 32-bit (at least for 32-bit processors). Some of the least-significant bits are used to store type information. See the VALUE definition in include/ruby/ruby.h. Using type tag bits avoids allocating additional memory for commonly-used immutable values, like integers.

Ruby uses a single-bit tag of 0x01 as the Fixnum type tag. The remaining bits, are used to store the Fixnum’s signed value. This is an immediate value; it doesn’t require storage for the Fixnum value to be allocated, unlike the heap space that would be required for a String. Other types will use different tag bits.

See /pub/tail_call_interp/tail_call_interp.c

The Scheme programming language requires proper implementation of tail calls, because all looping in Scheme is implemented as function calls — there is a very fundamental relationship between tail-calls and iteration.