Decision D028 · proposed; no 32-bit targets accepted (D042)
Value representation
A record of the language's design, as it stood on 2026-11-18: written for the people who build Diaspar, and kept as it was written. Its code is a sketch, not a program of the site, and an older record may show syntax that a later one changed. It names files of the language's source, which is not public yet.
Status: proposed (2026-11-16)
Research: reports/Runtime and C backend design.md and its notes, mainly value_representation.md (cited below as "notes §N"). D026 already accepted the outline: a 64-bit word with low-bit tags, an 8-byte header with a 32-bit count and a 32-bit type id, a type id per type version, UTF-8 strings with an ASCII flag, flat vectors. This decision fills in the exact layouts. Where it restates D026, D026 governs.
Summary
- A value is one 64-bit word,
dsp_val. A set low bit is a 63-bit integer. Low bits000are a pointer to an object. Low bits010are a constant:nil, booleans,(), and variants without fields.100and110are reserved. - Every object starts with an 8-byte header: a signed 32-bit count and a 32-bit word holding a 28-bit type id and 4 flags.
- A type id names one version of one type. It indexes a table of descriptors that only grows. The descriptor says how to read, print, compare, and free the object. All versions of a type share one lineage, which holds the protocol implementations.
- Built-in kinds have fixed small ids. Records and variants are a header plus one value word per field.
- Objects never move. Immortal objects (count 0) are never written, so literals can live in read-only memory.
1. The value word
typedef uint64_t dsp_val;. Targets are 64-bit and little-endian, the assumption D026's seed already makes; there are no 32-bit targets, and the browser's build uses 64-bit WebAssembly memory (D042).
| Low 3 bits | Meaning | Payload |
|---|---|---|
xx1 |
integer (fixnum) | bits 63–1: a signed 63-bit integer n; the word is (n << 1) | 1 |
000, word ≠ 0 |
pointer | the 8-aligned address of an object header |
010 |
constant | bits 7–3: a subtag; bits 63–8: a payload |
100 |
reserved | immediate floats (open question 1) |
110 |
reserved | small strings or another immediate (open question 2) |
the word 0 |
not a value | the runtime's "empty" (empty tree branches, unset slots); never visible to programs |
Constants under 010:
| Subtag | Value | Word |
|---|---|---|
| 0 | nil |
0x02 |
| 1 | false |
0x0A |
| 2 | true |
0x12 |
| 3 | the empty list () |
0x1A |
| 4 | a type with no fields: a variant such as Red, or (deftype Empty []) |
(tid << 8) | 0x22 |
| 5 | runtime markers ("field absent", "cell not yet defined"); never visible to programs | (n << 8) | 0x2A |
| 6–31 | reserved |
Consequences:
- Truthiness is one OR and one compare. Only
nilandfalseare false, and they differ in one bit:truthy(v) = (v | 0x08) != 0x0A. - Counting skips immediates.
dupanddropfirst test(v & 7) == 0. Integers and constants are never counted and never touch memory. - Representations are canonical. An integer in the fixnum range is always a fixnum, never a box; a type without fields is always the immediate. So two equal words are always
=, and two different immediate words are never=unless both are numbers (1and an immediate1.0, if floats become immediates). 0is not a value. Debug builds assert that nodsp_valpassed to user code is0.
Integers
The fixnum range is −2⁶² to 2⁶²−1 (notes §2: Lean and OCaml also use 63 bits; Koka uses 62). D013 makes overflow an error only beyond 64 bits, so integers from 2⁶² to 2⁶³ are boxed as an Int64 object (as Koka's KK_TAG_INT64). There are no bignums: D013 decided that overflow beyond 64 bits is an error. A big-integer type can come later as a library type; it would not join the numeric tower silently.
The fast paths, with one tag test and one hardware overflow check (notes §2, Koka integer.h):
#define DSP_FIX(n) (((uint64_t)(n) << 1) | 1)
#define DSP_FIX_VAL(v) ((int64_t)(v) >> 1) /* arithmetic shift */
/* a + b: 2x+1 + 2y = 2(x+y)+1; overflows exactly when x+y leaves 63 bits */
if (DSP_LIKELY(a & b & 1) && !__builtin_add_overflow((int64_t)a, (int64_t)(b - 1), &r))
result = (dsp_val)r;
else
result = dsp_add_slow(ctx, a, b);
Subtraction is a - (b - 1). Multiplication is (a >> 1) * (b - 1) + 1 with the overflow check on the product. The slow path widens both sides to int64_t (fixnum or box) or double, computes with an overflow check, and returns a fixnum, a box, a float, or performs Fail with "integer overflow". Anything that is not a number goes to the protocol method (D022: + also concatenates strings and dispatches to user types). The seed's portable profile replaces __builtin_add_overflow with plain C (D026).
Floats
Floats are boxed in the first version, as D026 accepted: a Float object with one double, 16 bytes. Where inference knows a local is a float, the C backend keeps it as a raw double and boxes only at polymorphic boundaries (from B2, when inference exists). Float literals are static immortal objects.
D013's rules do not depend on the layout, but they constrain it:
(= 1 1.0)is true and(= 9007199254740993 9007199254740992.0)is false: an exact integer–float comparison, which the bootstrap already has (cmp_int_floatin bootstrap/src/value/mod.rs).NaNequals itself, so any twoNaNpayloads are equal; the printer prints anyNaNasstd.math.nan.- Equal values hash equally: an integral float hashes as its integer.
- Printing must match the bootstrap byte for byte for differential testing (D003). The bootstrap prints with Rust's
{:?}(shortest round-trip). B1 can reproduce it by trying%.{p}gfor p = 1…17 until the text reads back to the same double, then adjusting the format to Rust's; a shortest-digits algorithm (Ryū, Schubfach) can replace it later.
2. The object header
typedef struct dsp_hdr {
int32_t rc; /* offset 0: the count */
uint32_t tidw; /* offset 4: bits 0–27 the type id, bits 28–31 flags */
} dsp_hdr;
A pointer value points at the header, as in Koka and Lean. Every object is 8-aligned. A header is written with one 64-bit store, ((uint64_t)tidw << 32) | 1, which is also how reuse rewrites the type id (notes §5).
The count
Lean's encoding, as D026 accepted (notes §1, §6, §7):
rc |
State | dup |
drop |
|---|---|---|---|
| 1 | unique: one reference, one owner | rc++ |
free |
| 2 … 2³¹−2 | owned by one task, several references; non-atomic | rc++ |
rc-- |
| 2³¹−1 | about to overflow | becomes 0 (immortal) | rc-- |
| 0 | immortal: literals, static data, interned keywords and symbols, descriptors | nothing | nothing |
| −1 … −(2³¹ − 2²⁸) | shared between tasks that may run in parallel; the count is −rc; atomic |
atomic rc-- |
atomic rc++; free at −1 |
| below that | sticky: a shared count that overflowed; never changes, never freed | nothing | nothing |
The fast paths cost one compare each:
/* dup: 1 ≤ rc ≤ 2³¹−2, with one unsigned compare */
if (DSP_LIKELY((uint32_t)h->rc - 1u < 0x7FFFFFFEu)) h->rc++; else dsp_dup_slow(h);
/* drop: the slow path handles 1 (free), 0 (immortal), negative (atomic) */
if (DSP_LIKELY(h->rc > 1)) h->rc--; else dsp_drop_slow(ctx, h);
A positive count that overflows becomes immortal: the owner is the only writer, so there is no race, and reaching 2³¹ references needs 16 GiB of pointers. A shared count needs the sticky band instead, because concurrent atomic updates may run while one thread notices the overflow; the band is wide enough that they stay inside it (Lean's LEAN_RC_STICKY).
Shared means reachable from two tasks that may run in parallel, not "seen by two OS threads". With M:N fibers (D006) a fiber moves between threads, and the move itself synchronizes, so a value reachable from one task keeps non-atomic counts wherever that task runs. A value graph is marked shared once, recursively, at a hand-off point: values captured by spawn and the inherited context, actor messages, values stored into an atom visible to several tasks, and globals in a multi-threaded program. Marking stops at objects already shared or immortal. A single-threaded scheduler may skip marking entirely. This is the Lean and Koka scheme, preferred to biased counting because fibers have no stable owner thread (notes §6).
The flags
| Bit | Name | Meaning |
|---|---|---|
| 28 | RELEASED |
release already ran (D023 rule 3); automatic release skips it, and using it is an error |
| 29 | HAS_SIDE |
the side table has an entry for this object: defaults of fields added after it was created (D010 §5), or a resource's creation position for D023's messages |
| 30, 31 | reserved |
Rare per-object data lives in the side table, a hash table keyed by address, so ordinary objects pay nothing for it. Freeing an object with HAS_SIDE removes its entry.
There is no cycle-collector bit. D004 limits candidates to atoms (and later actors); an atom has its own link field (section 4), and the collector keeps colours and trial counts in a table that exists only during a collection (report, "The cycle collector can wait").
Freeing
When drop sees rc == 1:
- If the type may release (a lineage flag, section 3) and
RELEASEDis clear, callreleasewith a borrowed reference and setRELEASED. A failure raises at the drop (D023 rule 5, D026). Ifreleasestored the value somewhere, the count is now above 1: the value is resurrected and not freed, as CPython does since PEP 442. - If
HAS_SIDE, remove the side entry. - Drop the counted fields and free the memory.
Deep structures are freed without recursion: children whose count reaches zero go on an explicit stack in the context, and the last child is handled in a loop, so a long list spine uses no stack (Koka frees by tail-calling into the child; notes §1). Lean instead threads the to-do list through the header, which needs the header's bits and is incompatible with ARM MTE (notes §1).
Built-in kinds without counted fields (section 4, ids 1–15) are freed without loading their descriptor: the drop path checks tid < 16 first.
3. Type descriptors
Ids and the table
- A type id (tid) is 28 bits: 268 million ids. It names one version of one type, or one variant of one version of an enum. Ids are never reused.
- Ids 1–63 are fixed built-in kinds (section 4). User types start at 64.
dsp_types[tid]gives the descriptor. The table is two-level, in chunks of 4,096 entries that never move, so readers need no lock and the table only grows. Descriptors are never freed (D026; an interactive image can afford it).- Modules register their types and intern their keywords at initialization, and generated code refers to them through module-level slots:
Point_v1_tid,KW_x. A type id is not a C constant, because the object cache compiles modules separately (D026 [17]) and ids depend on load order. The extra load hits a hot global. - Immediates have pseudo-ids for dispatch: fixnums share the
Intlineage with theInt64box;nil, booleans, and()have their own; a field-less type's id is its payload.
What a descriptor holds
A descriptor is itself an immortal object (tid Type), so a type is a value: Point passed to a function, or (json.Codec.from-json Config data) (D010 §5a), is a pointer to the current version's descriptor.
typedef struct dsp_field {
dsp_val key; /* interned keyword, compared by pointer */
uint32_t offset; /* byte offset in the object */
uint32_t flags; /* has a default; the default is a thunk */
dsp_val dflt; /* constant, or a function of no arguments */
} dsp_field;
typedef struct dsp_type {
dsp_hdr h; /* rc 0, tid = Type */
uint32_t tid; /* its own id */
uint16_t kind; /* string, vector, record, variant, field-less, enum, … */
uint16_t flags; /* opaque, effect, has :where */
dsp_val name; /* the qualified name as a symbol: user.Point */
struct dsp_lineage* lineage; /* shared by all versions */
uint32_t version; /* 1, 2, … */
uint32_t ordinal; /* a variant's position in its enum (this version) */
struct dsp_type* family; /* a variant's enum descriptor, same version */
uint32_t size; /* object size in bytes; 0 if it varies */
uint32_t nfields; /* value fields, all counted */
const dsp_field* fields; /* in declaration order, for printing */
dsp_val where; /* the :where check, or nil */
} dsp_type;
typedef struct dsp_lineage {
dsp_val id; /* user.Point: the identity across versions */
_Atomic(dsp_type*) current; /* the newest version */
uint32_t flags; /* may release: some version implements Release */
_Atomic(struct dsp_impls*) impls; /* protocol → method table */
} dsp_lineage;
- Printing,
=, ordering, and hashing of records and variants are generic runtime functions driven by the descriptor.=cannot be overridden (D022), so these are the only implementations of equality and hashing;Show,Ord, and the others are protocols. - Freeing uses
nfieldsfor records and variants, and code per kind for built-ins. - Built-in kinds have descriptors too, with
kindset and no fields. Their lineages hold protocol implementations for built-in types (Int,String, and kinds such asNumber).
Field access and match
Compiled p.x where inference says p is a Point:
if (DSP_LIKELY(DSP_IS_PTR(p) && DSP_TID(p) == Point_v1_tid))
x = DSP_SLOT(p, 8); /* offset from the layout */
else
x = dsp_field_slow(ctx, p, KW_x, &site_7); /* by name, through p's own descriptor */
The slow path finds the field by keyword in the value's own descriptor (D010 §5) and caches (tid, offset) at the call site. A field the value's version lacks is read from the side table, or computed from the current version's default and stored there, or is an error ("this Point was created before :z was added"). Release builds where types cannot change (--sealed) drop the compare.
match on an enum compares the tid with the variant ids its code was compiled against. A value from another version falls back to the variant's name through family, never its ordinal, since redefinition may reorder variants. A field-less variant is matched by comparing the word.
Protocol dispatch
A protocol method call reads the first argument's tid. The call site keeps a one-entry cache of (tid, pointer to the lineage's implementation slot). It caches the slot, not the method, so replacing an implementation needs no cache invalidation: D010's "redefinition replaces the whole block" is one atomic pointer store of a new method table. On a miss the slow path goes tid → descriptor → lineage → its table, then the built-in kind's table, then the protocol's default, then the error.
Implementations belong to the lineage, not to one version (open question 3): after a type is redefined in the REPL, extend-type blocks written for it still apply to new and old values.
A redefinition makes a new version
When deftype or defenum runs for a lineage that exists:
- If the definition is the same as the current version's (fields, defaults,
:where,:opaque, variants), nothing changes. Reloading an unchanged file keeps every value=to new ones and keeps compiled guards fast (open question 4). - Otherwise a new descriptor gets a fresh tid and
version + 1; for an enum, every variant gets a new tid.lineage->currentand the type's global cell point to it. Derivers rerun (D010 §7) and replace their protocol blocks. - Old values keep their tid and stay readable by name. A value of one version is never
=to a value of another (D010 §5), because equality compares tids first.
D018's later migrations fit the same layout: a migration rewrites an old value into the current version, in place when unique.
4. The built-in kinds
| tid | Kind | Layout after the header | Bytes | Notes |
|---|---|---|---|---|
| 1 | Int64 box |
int64_t v |
16 | only for integers outside the fixnum range; canonical |
| 2 | Float |
double v |
16 | |
| 3 | String |
uint64_t len; uint32_t spare; uint32_t info; char bytes[len+1] |
24 + len + 1 | below |
| 4 | Bytes |
uint64_t len; uint64_t cap; uint8_t data[cap] |
24 + cap | later: I/O and FFI buffers |
| 5 | Keyword |
uint64_t hash; dsp_val name |
24 | interned, immortal |
| 6 | Symbol |
uint64_t hash; dsp_val name |
24 | interned, immortal |
| 7 | foreign pointer | void* ptr; uint32_t ctype; uint32_t flags |
24 | D021 |
| 8–15 | reserved: kinds without counted fields | |||
| 16 | cons | dsp_val head, tail |
24 | () is the constant 0x1A |
| 17 | vector | uint64_t len; uint64_t cap; dsp_val items[cap] |
24 + 8·cap | flat; in place when unique |
| 18 | small map | uint32_t len; uint32_t cap; dsp_val kv[2·cap], sorted by key |
16 + 16·cap | up to 8 entries |
| 19 | map node | dsp_val key, val, left, right; uint64_t size |
48 | a weight-balanced tree; 0 is an empty branch |
| 20 | small set | uint32_t len; uint32_t cap; dsp_val keys[cap] |
16 + 8·cap | |
| 21 | set node | dsp_val key, left, right; uint64_t size |
40 | |
| 22 | closure | dsp_entry code; uint32_t arity; uint32_t nfree; dsp_val free[nfree] |
24 + 8·n | |
| 23 | atom | _Atomic(dsp_val) value; uint64_t id; struct dsp_atom* cc_next |
32 | D027 |
| 24 | type descriptor | section 3 | immortal | |
| 25, 26 | protocol, method | immortal | ||
| 27 | position | dsp_val source; uint32_t line; uint32_t col |
24 | Failure :trace |
| 28 | resume |
uint64_t perform_id; uint64_t state |
24 | stage 1, one-shot |
| 29–63 | reserved | |||
| ≥ 64 | record, variant | dsp_val fields[n] |
8 + 8·n | a two-field record is 24 bytes |
Empty collections are static immortal objects: "", #[] (cap 0), #{}, and #set[]. Global cells are not values; they are the C structs of D026.
Strings
- UTF-8, always valid.
lenis the byte count, sobyte-countis O(1). A NUL follows the bytes, so a string can be passed to C without copying (D021); C must still reject strings that contain U+0000. info: bit 31 isASCII, set at construction. Bits 0–30 cache the grapheme count,0x7FFFFFFFmeaning unknown. For ASCII textcountislen(D026). For other textcountwalks the string once (UAX #29) and stores the result with a relaxed atomic store, which is safe because every writer stores the same number. Literals get the count from the compiler. Nothing ever writes into an immortal object, so literals can live in read-only memory.spare: free bytes after the NUL, so+andstron a unique string append in place (Lean has a capacity field; notes §3).- No small-string optimization and no shared slices, as D026 decided; slices copy. Equality, ordering, and hashing compare bytes (D013), and every string is one canonical form, so comparison never has to look at the representation.
- There is no character type (D013): a grapheme is a one-grapheme string.
Keywords and symbols
Both are interned and immortal: one object per name, so equality is a pointer compare, and the hash is precomputed. name is an immortal string holding the full name, json.name. Ordering compares names. The intern table is global and grows only. That is acceptable because D010 never turns external data (JSON keys) into keywords silently.
A compiled symbol carries no hygiene context. The expander in compiler/ keeps scopes in its own syntax objects (stage-b.md), and D013 already excludes the context from equality. The bootstrap's Sym with a SymCtx is the interpreter's own arrangement.
Lists, vectors, maps, sets
- Lists are cons cells, so
restis O(1) and the RC pass can reuse cells, as in Perceus'mapexample.counton a list is O(n): no cached length (Clojure keeps one; open question 7). - Vectors follow D026: flat, updated in place when unique (Lean's
Array, notes §4). A vector reachable from a global is never unique, soconjon it copies; a 32-way trie with a tail can arrive later under a new tid of the same kind, if profiling finds the pattern. - Maps and sets follow D026's recommendation [5], to be decided for B2: sorted by the built-in total order, so printing matches the bootstrap's
BTreeMap. Up to 8 entries they are a sorted array updated in place when unique; above that, a persistent weight-balanced tree whose nodes are reused when unique. The weight in every node makescountO(1) without a wrapper and gives O(log n) split and union for set operations (open question 5). If [5] chooses hash order instead, the node kinds become CHAMP nodes and nothing else in this decision changes.
Records and variants
- A header and one value word per field. Fields are dynamically typed (D010 declares no field types), so a field cannot be an unboxed
double; raw scalar fields exist only in FFI structs and runtime objects. - Every field is counted, so "counted fields first" (Lean, Koka; notes §5) holds trivially. B1 stores fields in declaration order; D010 lets the compiler reorder them later.
- A variant with fields is a record with its own tid. A variant or record without fields is the constant
(tid << 8) | 0x22: no allocation, no counting, matched by comparing words (Koka encodes enumerations the same way; notes §2). - Effects (
defeffect) andFailureare records.
Closures
codeis the uniform entry of D026 [9]:dsp_val (*)(dsp_ctx*, dsp_val self, uint32_t argc, dsp_val a0, a1, a2, a3), extra arguments in the context's spill area. Calling borrowsself. A multi-arityfnswitches onargcinside its entry.arity: bits 0–15 the minimum, bit 16 variadic, bit 17 several arities; for error messages and reflection.- Captured values are owned fields, moved in at their last use (notes §5, the bootstrap's model).
- A global function used as a value is a static immortal closure with no captures that calls that version's code. Like the bootstrap's
Value::Fn, it is the function as it was when taken, while calls by name go through the cell. - A recursive local closure takes itself as a parameter rather than capturing itself, so it forms no cycle (report, pass order table).
Atoms
valueholds the current value; the atom owns one reference to it.idis a creation counter, as in the bootstrap: atoms are equal only to themselves, and the id gives them a stable order in sorted sets and a printed name.cc_nextlinks a candidate atom into the cycle collector's buffer; non-null means buffered.- An unshared atom is updated with plain loads and stores. A shared atom (negative count) needs reading and
duping the value to be one step, or a concurrentreset!can free the value between them (notes §5, Koka's double CAS). Open question 6 proposes a per-atom lock used only for shared atoms. - D027's in-place
swap!moves the value out and back when the compiler has proved nobody can see the gap; the layout needs nothing extra for it.
Effect continuations
In stage 1 a resume is valid only while its handler runs (D005): the object holds the id of the perform it returns to and a state (live, used, expired). In stage 2 the same kind holds a fiber. Dropping a continuation that was never resumed unwinds its fiber with cleanup (D005, "Abandoned computations"), so this kind has its own drop code, like atoms.
Foreign pointers
A raw C pointer is boxed with an id for its C type. It releases nothing itself: release belongs to the record that wraps it, as in (deftype Db [handle] :opaque :release sqlite3-close) (D023). Objects never move (D004), so a pointer to a string's bytes or a Bytes buffer stays valid while the count is above zero.
5. What reuse and in-place update need
| Need | How the layout provides it |
|---|---|
| A uniqueness test | rc == 1: one load and compare. Immortal (0) and shared (negative) objects are never unique, so static data and rodata are never written. |
| Reuse by size | Records and variants are 8 + 8n bytes, known from the tid at compile time. Drop-guided reuse (D026 [15]) may reuse any object of the same size: a cons for a two-field record. |
| Rewriting the type | One 64-bit store writes rc = 1 and the new tid with the flags cleared. Reuse requires the flags to be clear: an object with HAS_SIDE is freed normally, and values that may release are never reused (D026). |
| Functional update in place | assoc on a unique record keeps its tid and replaces a field. conj on a unique vector writes into cap; strings append into spare. |
| Trees | Map and set nodes are fixed-size, so an insert on a unique path rebuilds nodes in place, the Perceus red-black case (notes §4). |
| Freeing without descriptors | Leaf kinds have ids below 16; records free nfields words. |
Tail recursion modulo context (Koka's _field_idx) has no header space reserved. If it comes, it can keep its index in the count word while an object is under construction and still unique.
6. What B1 needs
| Part | B1 | Later |
|---|---|---|
| Value word | fixnums, nil, booleans, (), pointers |
immediate floats (measured), small strings |
| Integers | fixnum fast paths, the Int64 box, the overflow error |
unboxed int64_t locals with inference (B2) |
| Floats | the box, printing identical to the bootstrap (/ returns a float, D013) |
unboxed double locals |
| Header | positive counts, 0 immortal, the single-store initializer | shared counts and marking (stage D, with threads); the side table (B2 for resources, D for late fields) |
| Freeing | the explicit stack, nfields, leaf ids |
release at drops (B2, D026 [8]) |
| Descriptors | the chunked table, one version per type, field access with the tid compare | redefinition, lineage tables swapped live (stage D) |
| Strings | literals, len, ASCII, concatenation, print |
grapheme segmentation and the count cache (B2), spare for appends |
| Keywords | interned at module init | (keyword s) at run time |
| Records | construction by name, p.x, printing, = |
:where, defaults, opaque types (B2) |
Variants and match |
field-less constants, variants with fields | |
| Closures | the uniform entry, captures | |
Failure and resume |
Failure as a record, stage-1 resume |
stage-2 continuations |
| Lists, vectors, maps, sets, atoms | cons and () for rest arguments |
vectors, maps, sets, atoms (B2); the cycle collector (D) |
B1's programs (hello world, factorial, a loop, a closure, a record, a caught error) need only the B1 column. The C header that stage-b.md task 4 calls for contains only what the C compiler must see: dsp_val, the tag macros, dsp_hdr, the built-in tids, the inline dup/drop and fixnum fast paths, and DSP_FIELD. The runtime written in Diaspar reads the same layouts through std.unsafe intrinsics; a test checks its offset constants against the header's offsetof.
Comparison with prior art
| Choice | Diaspar | Prior art |
|---|---|---|
| Integer tag | low bit set, 63 bits | Lean and OCaml 63 bits, Koka 62 (notes §2); Chez Scheme 61-bit fixnums with 3 tag bits, Erlang 60-bit small integers (background, not checked in the research) |
| Floats | boxed; a tag reserved for immediates | Koka keeps most doubles immediate; LuaJIT and JSC NaN-box (notes §2) |
| Header | 8 bytes: count + type id | Koka and Lean 8 bytes with a constructor tag; Swift and CPython 16 bytes with a type pointer (notes §1) |
| Shared counts | negative, marked at hand-off | Lean's lean_mark_mt, Koka's tshare; Swift atomic by default; CPython biased (notes §6) |
| Immortal | count 0 | Lean 0; Koka INT32_MIN; CPython ≥ 2³¹ (PEP 683); Swift a bit pattern (notes §7) |
| Type identity | a 28-bit index per version | Swift and CPython a pointer per object; Chez and Racket CS records keep a record-type descriptor pointer in their first word (background); Lean, Koka, and OCaml only a constructor tag (notes §8) |
| Strings | UTF-8, ASCII flag, grapheme count cache | Swift ASCII and NFC bits; Lean caches the code-point count; Koka and Roc small strings (notes §3) |
| Keywords | interned immortal objects | Erlang atoms are immediate indices into a table that is never collected (background) |
| Vectors | flat, in place when unique | Lean Array; Clojure and Lean's PersistentArray tries (notes §4) |
| Closures | flat, code pointer + captures | Lean's closure object (notes §5) |
Rejected alternatives
| Alternative | Why not |
|---|---|
| NaN-boxing (LuaJIT, JSC) | immediate integers of 32 or 47 bits instead of 63, more boxing under D013's 64-bit rule; pointers limited to 48 bits, against ARM top-byte tagging and MTE (notes §2) |
| A 16-byte header with a descriptor pointer (Swift, CPython) | 8 more bytes per object; the 28-bit id cannot run out and costs one load on slow paths only (D026) |
| A descriptor pointer as the first field of records only | two ways to find a type, and records pay a word anyway |
| Koka's count, 0 = unique | equally cheap; D026 chose Lean's, which reads naturally in a debugger and matches D004's "count is 1" |
| Biased counting (CPython free-threaded) | needs an owner thread, which M:N fibers do not have, plus an 8-byte field (notes §6) |
| Kind tags in the pointer bits (Chez's typed pointers) | Chez spends them to drop headers from pairs; with reference counting every object needs a header for its count anyway, and the low bits are worth more for immediates |
| Multi-word values (Swift existentials, Roc's 24-byte strings) | every container slot and argument would grow; Diaspar's values are uniformly dynamic |
Automatic bignums (Python, Clojure's +') |
D013 makes overflow beyond 64 bits an error |
| A character type | D013: a grapheme is a one-grapheme string |
| Keywords as immediate indices (Erlang atoms) | every name lookup and ordering goes through the table, and literal indices are no more constant in separately compiled C than pointers; an immortal object's count check hits a hot cache line |
| Unboxed scalar fields in records | fields have no declared types; the compiler cannot know a field always holds a float |
| Positional field order as the layout contract | D010 gives the layout to the compiler |
| A header bit for the cycle collector | D004 limits candidates to atoms, which have their own link field |
| Lean's free list threaded through the header | needs header bits Diaspar uses for the type id, and breaks under ARM MTE (notes §1) |
Variant ordinals as the fallback in match |
ordinals change when variants are reordered; names do not |
Open questions
| # | Question | Recommendation |
|---|---|---|
| 1 | Immediate floats under 100, Koka's trick of keeping doubles whose exponent fits in 10 bits |
Keep the tag reserved. Measure after B2 on a float benchmark (a ray tracer, an n-body simulation). Inferred unboxed locals may make it unnecessary. |
| 2 | Small strings under 110 (7 bytes) |
No, until a measurement shows allocation of short strings matters. If adopted, every string of up to 7 bytes must be immediate, so the bytes stay canonical. |
| 3 | Protocol implementations per lineage or per version | Per lineage: hand-written extend-type blocks then keep working after a deftype is re-evaluated alone. Generic printing and equality read the value's own descriptor, so old values stay correct. |
| 4 | Whether re-evaluating an identical deftype makes a new version |
No new version. Otherwise reloading an unchanged file makes old values unequal to new ones. The bootstrap needs a fix either way: cmp_records compares records by qualified name and then fields, so values of two versions with the same fields are equal there, against D010 §5. Differential testing will catch it. |
| 5 | The tree for large maps and sets | A weight-balanced tree first: O(1) count, split and union for set operations, simple reuse. Benchmark it against a red-black tree (Perceus' best case) and a B-tree with wide nodes when maps become hot. Depends on D026 [5]. |
| 6 | Reading shared atoms safely | A per-atom spin lock, taken only when the atom is shared, around read-and-dup and around the compare-and-swap commit. Contention on atoms is low, and unshared atoms pay nothing. Decide with fibers (stage D); where values become shared: design/concurrency.md §4.4. |
| 7 | A cached length in cons cells | No: cells stay 24 bytes, like Lean, Koka, and OCaml. Add a lint if count on lists shows up in profiles. |
| 8 | Whether a shared value whose count reached −1 counts as unique for reuse | Not at first; copy. Revisit when shared data is measured. It needs an acquire fence before writing. The contents of a cown and the result of join are not marked shared, so they stay unique (design/concurrency.md §4.4). |
| 9 | Keyword literals across modules: module slots or link-time deduplication (weak symbols, COMDAT) | Module slots filled at init: portable, and they work for code loaded live (stage D). Weak symbols can be a sealed-build optimization. |