Types & Value Representation

How we represent values in memory is one of the most consequential design decisions for a language implementation. It affects performance, memory usage, and what operations the GC must handle.

Tagged Unions

The most common approach is a tagged union — a type tag plus a union of possible values:

Value {
    type: enum { NUMBER, BOOLEAN, NIL, OBJ }
    as: union {
        number:  double
        boolean: bool
        obj:     Object*    // pointer to heap object
    }
}

Numbers, booleans, and nil are stored inline (no heap allocation). Strings, functions, and classes are heap objects accessed through a pointer.

NaN Boxing

An advanced technique: since IEEE 754 doubles have many NaN representations, we can encode non-number values inside NaN bit patterns:

Regular double:   [sign][11-bit exponent][52-bit mantissa]
NaN:              [sign][11111111111][non-zero mantissa]

The mantissa of a NaN has 52 bits of space. We use some bits for the type tag and the rest for a pointer or small value. This way, every Value is exactly 8 bytes — no tag overhead.

V8 uses a similar technique called Smi (Small Integer) tagging: pointers are tagged in their least-significant bit.

Heap Objects

Complex values live on the heap. All heap objects share a common header:

Object {
    type:  ObjType    // STRING, FUNCTION, CLOSURE, CLASS, INSTANCE
    next:  Object*    // linked list for GC to traverse all objects
}

ObjString : Object {
    length: int
    chars:  char[]
    hash:   uint32    // cached hash for interning
}

The next pointer forms an intrusive linked list of all heap objects — the GC walks this list during the sweep phase.

Strings as Objects

Strings are the first heap-allocated type we implement. Key decisions:

• Immutable: strings cannot be changed after creation (like Python, Java, Lua)
• Interned: each unique string exists once in a global table
• Hash cached: the hash is computed once at creation and stored

Immutability and interning together enable O(1) string equality: just compare pointers.

How Lua Represents Values

Lua uses a tagged union where the tag is a byte and the value is a C union. Small strings (under 40 bytes) are interned; long strings are not. Lua 5.4 added an integer subtype alongside floats, controlled by a compile-time option.

Your Task

Implement a tagged union Value type with number, boolean, nil, and string. Make strings heap-allocated, immutable, and interned. Add string concatenation with OP_CONCAT.