Building a Register VM Interpreter - Part 2: The Value System

When building an interpreter for a dynamically typed language, one of the first basic hurdles is figuring out how to represent variables. In a dynamically typed language, a single variable might hold a numeric value at one moment, a boolean the next, and maybe a string later on.

C, however, is a statically typed language. A C double can only hold a decimal number, and a C pointer points to memory. To bridge this gap, our virtual machine requires a universal, unified data type capable of representing all of the value the language can produce.

In core/value.h, this universal type is defined simply as an unsigned 64-bit integer:

typedef uint64_t Value;

While we could use a C struct containing an enum for type presentation and a union for the type payload (known as a Tagged Union), this approach wastes memory due to alignment padding. Instead, let’s take a look at the implements of a highly optimized, memory-efficient technique known as NaN-Boxing.

NaN-Boxing

To understand how a single 64-bit integer can safely and efficiently represent numbers, booleans, nulls, and even more without losing track of what it actually is, we have to have a sense of how modern hardware represents floating-point numbers.

Under the IEEE 754 standard, a 64-bit double-precision floating-point number is divided into three parts:

• 1 Sign bit: determines positive or negative

• 11 Exponent bits: determines the magnitude

• 52 Mantissa bits: determines the precision/fraction

When all the exponent bits are set to 1, the standard defines the value as “Not a Number” (NaN). This usually happens when you try to divide by zero. However, when a value is NaN, the CPU practically ignores the remaining 52 mantissa bits.

So we can hijack these unused 52 bits, plus the 1 sign bit, to store our own custom data. In core/value.h, we establish the core mask for this exact purpose:

#define QNAN            ((uint64_t)0x7ffc000000000000)
#define SIGN_BIT        ((uint64_t)0x8000000000000000)

The QNAN stands for Quiet NaN, which is the bitmask where all 11 exponent bits are set to 1, along with the highest two bits of the mantissa. The first bit of the mantissa must be set to 1 for the NaN to be “Quiet”. Otherwise the CPU might triggering a CPU exception or signaling an error. The second bit of the mantissa is often set to 1 to prevent Intel hardware from altering the value. Some CPUs canonicalize NaNs, if they encounter a NaN bit pattern they don’t recognize, they may automatically reset the bits to a default NaN value (usually 0x7ff8000000000000). By setting the second to 1, the programmer creates a sturdier NaN pattern that the hardware is less likely to overwrite, preventing “boxed” values from being reset.

The SIGN_BIT represents the very first bit of the 64-bit sequence, which we will reserve for identifying memory pointers.

Numbers

The most elegant part of NaN-boxing is that standard numbers require zero extra work. A valid IEEE 754 number will not have all the QNAN bit set.

To check if a Value is a number, the VM only needs to perform a bitwise AND against the QNAN mask. If the result does not perfectly match the mask, it musk be a number:

#define IS_NUM(value)   (((value) & QNAN) != QNAN)

As C’s strict aliasing rules heavily discourage casting directly between double and uint64_t via pointers, we can safely translate between the two using memcpy:

static inline Value numToValue(double num) {
    Value bits;
    memcpy(&bits, &num, sizeof(double));
    return bits;
}

static inline double valueToNum(Value value) {
    double num;
    memcpy(&num, &value, sizeof(double));
    return num;
}

With these inline functions, whenever the script evaluates a number, it writes the exact binary representation of the double directly into Value typedef.

Null and Booleans

For values that are not numbers like null, true and false, we can activate the mask and use the lowest bits of the mantissa as the own custom type tags.

In core/value.h, it defines the exact integer tags for states:

#define TAG_EMPTY       0
#define TAG_NULL        1
#define TAG_FALSE       2
#define TAG_TRUE        3

To create a null value in VM, we just take the mask and bitwise OR it with the TAG_NULL integer. We simply do the sane with either TAG_TRUE or TAG_FALSE:

#define NULL_VAL        ((Value)(uint64_t)(QNAN | TAG_NULL))
#define BOOL_VAL(bool)  ((Value)(uint64_t)(QNAN | (bool ? TAG_TRUE : TAG_FALSE)))
#define EMPTY_VAL       ((Value)(uint64_t)(QNAN | TAG_EMPTY))

Checking if a Value is a specific type requires checking if its bits exactly match these masks. For null, the checking is straightforward:

#define IS_NULL(value)  ((value) == (QNAN | TAG_NULL))

For booleans, we can use a optimized bitwise trick to check for both true and false:

#define IS_BOOL(value)  (((value) & ~1) == (QNAN | TAG_FALSE))

It is easy to notice that TAG_FALSE is set to10 in binary (decimal 2) and the TAG_TRUE is 11 (decimal 3). They only differ by the last bit. So the ~1 can create a mask that clears the least significant bit. By AND-ing the value with ~1, it wipes out the last bit. Therefore, if the original value was either true or false, the final wiped tag is forced to equal TAG_FALSE. In one single instruction, we are able to check “is this any boolean?”.

To unbox a boolean and convert it back to a native C one, we simply check if it matches the true tag:

#define AS_BOOL(value)  ((value) == (QNAN | TAG_TRUE))

Objects

While a number or a boolean fits perfectly inside 64 bits, complex data structures like strings or lists cannot. These structures must be dynamically allocated on the heap with a pointer holding by VM.

Actually the 64-bit pointer fit inside the 52-bit mantissa, because modern 64-bit hardware only use the lower 48 bits for real virtual memory addresses. This leaves plenty of space inside mantissa to store a raw C pointer.

To differ an Object from other tags, we need the SIGN_BIT defined earlier. If a value is a NaN and its sign bit is set, the VM recognize the remaining bits as a memory address:

#define IS_OBJECT(value) (((value) & (QNAN | SIGN_BIT)) == (QNAN | SIGN_BIT))

When creating an object, the C pointer is cast to a uintptr_t, which is an integer type guaranteed to be large enough to hold a pointer, and it is OR-ed with the QNAN and SIGN_BIT.

#define OBJECT_VAL(obj) ((Value)(QNAN | SIGN_BIT | (uintptr_t)(obj)))

When we need to unbox the data from the object, we reserve the process. By using a bitwise NOT on the mask, we disconstruct the QNAN and SIGN_BIT, leaving only the pure 48-bit C pointer, which we safely cast back to an Object*:

#define AS_OBJECT(value)  ((Object*)(value & ~(QNAN | SIGN_BIT)))

Value Arrays

With the Value system successfully packing any data type into a integer, now the VM needs a way to store and manage multiple values at once. Since the number of elements these lists will need is unknown at compile time, we cannot use a fixed-size C arrays. Instead, we must implement a dynamic, resizable array.

In core/value.h, it defines the ValueArray structure to handle this:

typedef struct{
    Value* values;
    size_t count;
    size_t capacity;
}ValueArray;

The values is a C pointer to the dynamically allocated block of memory which holding the actual Value. And the capacity stands for the total amount of memory currently allocated. This tells us how many elements we can store before we need to request more memory from system.

Init and Growth

Managing a ValueArray begins with putting it into a clean, zeroed-out state:

void initValueArray(ValueArray* array){
    array->values = NULL;
    array->count = 0;
    array->capacity = 0;
}

If the array is already full (or entirely unallocated) while inserting a new value into it, the VM must dynamically grow the underlay memory. This logic is handled inside writeValueArray:

void writeValueArray(VM* vm, ValueArray* array, Value value){
    if(array->count + 1 > array->capacity){
        size_t oldCapacity = array->capacity;
        array->capacity = oldCapacity < 8 ? 8 : oldCapacity * 2;
        array->values = (Value*)reallocate(
            vm,
            array->values,
            sizeof(Value) * oldCapacity,
            sizeof(Value) * array->capacity
        );
    }
    array->values[array->count++] = value;
}

It first checks whether the required size exceeds the current capacity, if a growth is needed, it calculates a new capacity. The growth strategy starts with an initial capacity of 8. If it already has elements, it simply doubles the capacity. reallocate is a core memory management function defined and will be explained later. It passes the old pointer, old size and newly required byte size.

Finally, with sufficient space guaranteed, it writes the new Value to the values array at the current count index, and increments count immediately after using the ++ postfix operator.

Cleanup

Since C does not have a automatic garbage collection for pointers, any dynamically allocated memory must be explicitly freed to avoid memory leaks. The freeValueArray function is responsible for tearing down the array:

void freeValueArray(VM* vm, ValueArray* array){
    reallocate(vm, array->values, sizeof(Value) * array->capacity, 0);
    initValueArray(array);
}