Value Representation

Read this before Lab 4. It is filed in Section 2 because it is the foundation of the reference interpreter, but Lab 4 is where you implement it and where you write ADR-004 and ADR-005.

Three concepts: the tagged union, the integer/float split, and handles versus pointers.

Concept 1: The Tagged Union

1. Concept

A dynamically-typed value must carry its type at run time. A tagged union is a fixed-size cell holding a tag saying which type it is, and a payload whose interpretation depends on the tag.

   ┌──────────┬───────────────────────────────────┐
   │   tag    │            payload                │
   │  1 byte  │            8 bytes                │
   └──────────┴───────────────────────────────────┘
      Integer   0x000000000000002A                  → 42
      Float     0x4045000000000000                  → 42.0
      Table     0x0000000200000007                  → handle: gen 2, slot 7
      Nil       (payload ignored)

In Rust this is exactly what an enum is. In C it is a struct containing a union and a tag byte, which is precisely what Lua's TValue is.

2. Problem

The VM's stack, every table slot, and every function argument must be able to hold any value. If values were different sizes, none of those could be arrays, and array indexing is the operation the whole runtime is built on. So values must be uniform and small.

"Small" matters more than it sounds. The VM's value stack is touched on every instruction; a 16-byte Value puts four values in a 64-byte cache line, an 8-byte one puts eight.

3. Mental model

A Value is a machine word with a label on it. The label costs you either a separate byte (and the padding that follows), or a clever encoding that hides the label inside bit patterns the payload does not use.

Every value representation in every dynamic language is an answer to "where do I put the label?"

4. Implementation

#![allow(unused)]
fn main() {
// src/value.rs
#[derive(Copy, Clone, Debug)]
pub enum Value {
    Nil,
    Boolean(bool),
    Integer(i64),
    Float(f64),
    Str(GcRef<EmberStr>),
    Table(GcRef<Table>),
    Closure(GcRef<Closure>),
    Native(GcRef<NativeFn>),
    UserData(GcRef<UserData>),
}
const _: () = assert!(std::mem::size_of::<Value>() == 16);
}

Why 16 bytes. The largest payload is 8 bytes (i64, f64, or a handle). The discriminant needs at least one byte. Alignment is 8 (because of i64/f64), so the whole thing rounds to 16.

Why Rust cannot do better here. Rust's niche optimization packs a discriminant into unused bit patterns when a variant has them — Option<&T> is 8 bytes because the null pointer is an unused &T. But i64 and f64 use every bit pattern, so there is no niche. The compiler is not being lazy; the information genuinely does not fit.

Why Copy matters. A Copy value can be read out of the stack, pushed, duplicated, and stored in a table with a memcpy and no bookkeeping. The moment Value contains an Rc, it gains a Drop, loses Copy, and every single stack operation in the dispatch loop becomes a refcount increment or decrement. That is the CPython tax, and avoiding it is most of the reason for the handle design in Concept 3.

GcRef<T> is 8 bytes:

#![allow(unused)]
fn main() {
pub struct GcRef<T> {
    index: u32,
    gen:   u32,
    _t: PhantomData<fn() -> T>,   // `fn() -> T`, not `T`: keeps GcRef Copy and
}                                  // covariant without entangling drop-check.
impl<T> Copy for GcRef<T> {}
impl<T> Clone for GcRef<T> { fn clone(&self) -> Self { *self } }
}

Note: PhantomData<fn() -> T> rather than PhantomData<T> is a small but real Rust idiom. PhantomData<T> would make GcRef<T> behave, for variance and drop-check purposes, as if it owned a T — which it does not; it owns an index. fn() -> T marks it as merely producing T, which is covariant and drop-check-free. Deriving Copy/Clone also has to be manual, because #[derive(Copy)] would demand T: Copy and T here is Table, which is not.

5. Alternatives

B — NaN boxing. IEEE-754 defines a NaN as exponent-all-ones with a nonzero mantissa. That leaves roughly 2^52 bit patterns that no arithmetic ever produces. Hide a 3- or 4-bit type tag and a 48-bit pointer in there, and every value is one 8-byte word — with f64 arithmetic completely free, because a float is its own representation. The costs: it is unsafe in Rust by construction, it assumes pointers fit in 48 bits (true on current x86-64 and aarch64 userspace; not guaranteed, and 5-level paging on x86-64 makes 57-bit addresses possible), and every value operation becomes bit-twiddling that the compiler cannot check.

C — Pointer tagging. Heap objects are aligned, so the low 2–3 bits of a pointer are always zero; steal them for a tag. V8 does this: a Smi ("small integer") is a 31-bit integer stored inline, and anything else is a tagged pointer. The cost is that f64 no longer fits, so V8 heap-allocates doubles as HeapNumber objects — which is why numeric JavaScript benchmarks care so much about whether a value stays a Smi.

D — Everything on the heap. CPython's PyObject*: 1 is a heap-allocated object with a refcount. Beautifully uniform, and it means every arithmetic operation allocates — which is why CPython caches small integers (−5 to 256) as singletons. That cache existing at all is the tell.

6. Decision

ADR-004: Ember uses a Rust enum (option A).

The point is not that A is best. It is that B is not obviously better until you have a benchmark, and Ember will have one. Capstone project 2 implements NaN boxing behind a feature flag, keeps the test suite green, and reports the delta. That is the honest way to make this decision, and it is available only because A came first.

7. Tradeoffs

8. Production concerns

• The size is load-bearing and must not drift. const _: () = assert!(size_of::<Value>() == 16) turns an accidental regression into a compile error. Someone will add a variant carrying a String (24 bytes) and triple the stack's memory traffic; this catches it.
• f64 in a Copy enum brings NaN with it. Value cannot derive PartialEq meaningfully (NaN != NaN) or Eq or Hash at all. Ember writes raw_eq by hand and, in Lab 13, makes NaN-as-a-table-key an explicit error — as Lua does.
• Integer/float normalization for table keys. t[1.0] and t[1] must be the same slot, so the table's key path normalizes a float with an exact integer value to an integer before hashing. Forget it and you get two entries that print identically. This is Lua's behavior and it is §3.4.7 of the manual.

9. References

rg -n 'typedef.*TValue|Value;|tt_' lobject.h        # Lua's tagged union, ~16 bytes
rg -n 'LUA_VNUMINT|LUA_VNUMFLT|ttisinteger' lobject.h

• Lua's lobject.h — TValue is a Value union plus lu_byte tt_, with the type and variant and collectable bit packed into that byte. Read the ttis* macros.
• LuaJIT's lj_obj.h — NaN boxing, with a long comment explaining the bit layout. The best primary source on the technique.
• V8's src/objects/smi.h and the "pointer compression" design docs — option C at scale.
• CPython's Include/object.h and Objects/longobject.c (_PyLong_SMALL_INTS) — option D and its mitigation.

Concept 2: The Integer/Float Split

1–3. Concept, problem, mental model

Lua before 5.3 had one numeric type: double. That is simple and it is wrong for anything that counts, indexes, or identifies. 2^53 + 1 == 2^53 in f64, so an ID that crosses 9 quadrillion silently collides — a real failure mode for anything handling large identifiers.

Lua 5.3 introduced two subtypes of number: integer (i64) and float (f64).

One type to the script (type(1) == type(1.0) == "number"), two subtypes to the implementation (math.type distinguishes them). Operators decide which they produce, by rule.

4. Implementation

The rules, which Lab 3 implements and Lab 4 tests:

5–7. Alternatives, decision, tradeoffs

ADR-005: option B. A policy engine indexes arrays, counts, compares IDs, and interoperates with JSON where integers are common. Silent f64 rounding at 2^53 is exactly the class of bug that shows up in production and cannot be reproduced. Option D is genuinely attractive and is rejected on performance grounds Ember cannot yet measure — record that honestly.

The tradeoff is real and it is not free: you now own a promotion table, a wrapping-overflow decision, and an exact mixed comparison. The last of those is where implementations get it wrong.

8. Production concerns

Exact mixed comparison is the trap.

lua -e 'print(math.maxinteger + 0.0 == math.maxinteger)'   # false

i64::MAX is 2^63 − 1. As an f64 it rounds up to exactly 2^63. So x as f64 == y reports equality between an integer and a float that are not equal. Convert in the other direction: a float equals an integer only when it has no fractional part and lies in i64's range and its as i64 conversion equals the integer. Ordering has the same hazard in four sign/magnitude cases; Lua's LTnum handles them explicitly (rg -n 'LTnum|LEnum' lvm.c).

Other concerns:

• Overflow policy. Lua wraps. Rust's + panics in debug builds and wraps in release — the worst possible combination for an embedded runtime, because it means a script can abort the host in a debug build. Every arithmetic path uses wrapping_* explicitly, and there is a test for it.
• JSON and host marshaling. In Section 5, a host passing serde_json::Value::Number must decide which subtype it becomes. 1.0 from JSON is a float; 1 is an integer; and a policy comparing article.id == 1 will silently fail if the host guessed wrong. Document the mapping.
• Printing. 4 and 4.0 must print differently, or a script author cannot tell which subtype they have. Lua formats floats with "%.14g" and appends .0 when the result looks integral.

9. References

• Lua 5.4 Reference Manual §3.4.1–§3.4.3 and §3.4.4 — the rules, stated normatively.
• Lua's lvm.c: luaV_idiv, luaV_mod, luaV_equalobj, LTnum, luaV_tointegerns.
• The Lua 5.3 "what's new" notes on the integer subtype — the rationale, from the designers.
• Python's PEP 3141 and its numeric tower, for the road not taken.

Concept 3: Handles, Not Pointers

1. Concept

Heap values in Value are handles — {index: u32, generation: u32} into a slot table owned by the heap — not pointers and not Rcs.

2. Problem

Ember needs a tracing garbage collector, because cycles are one line of script away. A tracing collector must be able to free an object while other objects still refer to it (they are garbage too), and it must be able to walk the whole object graph. In Rust, the obvious ways to do that are all bad:

3. Mental model

A handle is a row number in a table you own, plus a version stamp. Dereferencing is heap.slots[index] — a bounds-checked array index, which Rust makes safe by construction. The generation stamp turns "this handle refers to a slot that has since been reused" from silent corruption into a loud, catchable error.

   Value::Table(GcRef { index: 7, gen: 2 })
                          │      │
   heap.slots ────────────┘      │       heap.generations
     [0] Some(EmberStr "name")   │         [0] 1
     [1] Some(Closure ...)       └──────▶  [7] 2   ✔ matches → live
     ...                                   
     [7] Some(Table { ... })

   After a collection frees slot 7 and something else reuses it:
     [7] Some(EmberStr "other")            [7] 3   ✘ 2 != 3 → stale handle, ERROR

4. Implementation

Built in Lab 15; previewed here because Value depends on it.

#![allow(unused)]
fn main() {
pub struct Heap {
    slots: Vec<Option<HeapObject>>,
    generations: Vec<u32>,
    free: Vec<u32>,
    bytes_allocated: usize,
    next_gc: usize,
}

impl Heap {
    pub fn table(&self, r: GcRef<Table>) -> Result<&Table> {
        if self.generations[r.index as usize] != r.gen {
            return Err(internal("stale handle — a GC root was missed"));
        }
        match &self.slots[r.index as usize] { Some(HeapObject::Table(t)) => Ok(t), _ => Err(..) }
    }
}
}

5–7. Alternatives, decision, tradeoffs

ADR-006: handles into a slot table.

The Rust problem this creates, stated plainly, because it is the central Rust lesson of Section 4:

#![allow(unused)]
fn main() {
let t = heap.table(handle)?;          // immutable borrow of heap
heap.set(other_handle, key, value)?;  // ERROR: cannot borrow `heap` as mutable
}

The borrow checker is right — set might reallocate slots and invalidate t. The fixes, in order of preference: (1) narrow the scope so the borrows do not overlap; (2) copy the small thing you needed out of the object (Value is Copy, which is why that works); (3) take the object out of its slot, operate, and put it back. unsafe is not on the list. Section 4 works through all three.

8. Production concerns

• The generation check must not be optional in debug builds. It is the only thing standing between a missed root and silent corruption. Section 7 may compile it out in release after the fuzzer has run clean — and that is a documented decision with a stated risk, not a free win.
• u32 index caps the heap at ~4 billion objects. Fine, and it must be documented; the allocation path must error rather than wrap when the slot table is full.
• Handles are not portable across Engines. A GcRef from one engine used in another is nonsense that the generation check will usually catch and is not guaranteed to. Section 5's API never hands a raw GcRef to the host; it hands a rooted, engine-bound wrapper.

9. References

• piccolo (a Rust Lua implementation) — a different answer to the same problem, using arenas and a Collect derive with GC "branding" lifetimes. Read it after Lab 15 and compare.
• gc-arena, the crate underlying piccolo.
• The "generational indices" pattern, popularized in Rust by the slotmap and generational-arena crates — Ember's GcRef is that pattern with a collector attached.
• Lua's lgc.h/lobject.h: GCObject and the CommonHeader macro. Raw pointers, one linked list of all objects, and a marked byte — the C answer, and worth reading side by side with yours.

Things to Notice

• Every value representation is an answer to "where do I put the type tag?" Once you see that, the four options stop being trivia.
• Copy is not a micro-optimization here; it is an architectural property. It is what lets the stack be a plain Vec<Value> with no bookkeeping on push and pop.
• The integer/float split buys correctness and costs a comparison you will get wrong once. Both halves of that sentence are load-bearing.
• Handles make a tracing GC possible in safe Rust, and they make the borrow checker your adversary in a new way. That trade is the most Rust-specific decision in the whole runtime.
• Rust makes this layer easier than C (exhaustive matching, no accidental tag/payload mismatch) and the next layer harder (an object graph is exactly what ownership is bad at). Both observations belong in docs/learning/05-values.md.

Validation / Self-check

1. Why is Value 16 bytes? What would make it 8, and what are the three costs of doing so?
2. Why can Rust's niche optimization not shrink Value?
3. What breaks in the dispatch loop the moment Value stops being Copy?
4. Give the four value representations, a production runtime for each, and the specific problem each one creates.
5. State the rule for /, ^, //, and + on integer/float mixes, and give the value that breaks naive integer↔float equality.
6. Why does Ember use wrapping_add rather than +? What does + do in a debug build?
7. What is a generation counter for, and what would happen without it if you missed a GC root?
8. Write the three legitimate ways out of "cannot borrow heap as mutable because it is also borrowed as immutable", in order of preference. Why is unsafe not among them?

Next: Scope and Environments.