Dense storage.
Stable indices.
No GC.

#Why No GC

U has no garbage collector. Ownership is a DAG — strong references point from parent to child, never upward or cyclically. When an owner's refcount hits zero, its entire subtree dies. No tracing, no mark-sweep, no pause. The cost of deallocation is proportional to what was allocated by that owner, not to total heap size.

Back-references use +R(parent) annotations. The compiler treats them as weak: they don't contribute to the reference count and resolve to none when the referent dies. The linter enforces the DAG structure using Tarjan's SCC algorithm on the type-reference graph — any cycle must have at least one +R(parent) edge, or the program is rejected.

#Slab Chain Allocator

Every owner has a slab chain. Allocations bump a pointer within the current slab. When a slab fills, a new slab twice the size is linked in.

Owner
 └─ slab_ptrs: [ptr0, ptr1, ptr2, ...]
                  │      │      │
                  ▼      ▼      ▼
                4KB    8KB   16KB   ...

The chain for n total bytes has at most ⌈log₂(n/initial)⌉ slabs. Each slab is a power-of-two allocation, which system allocators can service efficiently through size-class free lists.

Allocation is a bump pointer: increment, compare to end. No per-object free-list traversal and no general-purpose allocation metadata is required for individual owner-scoped objects.

Deallocation walks the chain and frees each slab. For ordinary request-sized allocations this is only a handful of frees. Cost is O(log n) slab releases for n total bytes and effectively constant for typical scopes.

#NaN-Boxed Tagged Values

Dynamic values in Lists, Maps, and Trees can use a single 8-byte tagged representation via NaN-boxing.

real double      → raw IEEE representation, with NaNs canonicalized
small integer    → tagged integer payload
pointer          → tagged pointer payload
bool true        → reserved tagged pattern
bool false       → reserved tagged pattern
none             → reserved tagged pattern
tombstone        → reserved tagged pattern

The exact tag layout is an ABI detail. Floating-point NaNs must be canonicalized so tagged payloads cannot be confused with numeric NaNs.

A dynamic U value is one machine word whenever its value fits the tagged representation.

Leaf values therefore require no separate heap allocation. Tags and payloads are extracted with masks, shifts, and comparisons.

#Lists

Lists use stable power-of-two slabs. Elements do not move merely because the List grows.

slab 0: 4 elements
slab 1: 8 elements
slab 2: 16 elements
slab 3: 32 elements
...

Once an element receives a logical index, appending later elements does not change that index or relocate the existing element.

O(1) Random Access

For index k, the slab can be determined using the highest significant bit, clz, shifts, and arithmetic.

slab_index = 31 - clz((k >> 2) + 1)
base       = (4 << slab_index) - 4
pointer    = slab_ptrs[slab_index]
address    = pointer + (k - base) * element_size

The slab-pointer header is small and normally cache-resident.

Iteration

Iteration holds the current slab pointer, current element pointer, and remaining elements in the slab. It walks contiguous memory until the slab ends, then advances to the next slab. Sequential iteration therefore approaches ordinary contiguous-memory bandwidth and works naturally with hardware prefetching.

O(1) Append

Appending within the current slab is a bump. When that slab fills, allocate the next power-of-two slab and continue there. Existing elements are never copied merely because capacity grows. Append is therefore worst-case O(1) with respect to existing List length rather than merely amortized O(1).

#Maps: Stable Ordered Storage

A U Map is fundamentally ordered dense storage, not a hash table. Its authoritative representation is two parallel stable Lists:

Map<K,V>

index       1      2      3      4      5
            │      │      │      │      │
keys       [K1]   [K2]   [K3]   [K4]   [K5]
values     [V1]   [V2]   [V3]   [V4]   [V5]

The defining invariant is insertion index i ↔ keys[i] ↔ values[i]. Indices increase sequentially. Existing live entries never move merely because later entries are inserted.

The authoritative direction is index → (key, value). The reverse direction key → index is derived acceleration data.

#First Rule of Map Optimization: Avoid Reverse Lookup

A conventional hash table assumes key → hash → storage location is fundamental. U does not.

Many important PHP, JavaScript, JSON, routing, configuration and application patterns already reveal the relevant stable index through iteration, insertion, compiler-constant keys, shared shapes, previous resolution, or compiler dataflow.

Before optimizing key → index, determine whether the operation is necessary at all.

The general dynamic resolver handles only the residual case.

#Iterator Provenance

foreach ($a as $b => $c) {
    use($a[$b]);
}

The iterator already knows b, c, and the current stable index bi. Therefore $a[$b] becomes a.values[bi]. There is no reverse lookup.

Nested iteration follows the same rule:

foreach ($a as $b => $c) {
    foreach ($c as $d => $e) {
        use($a[$b][$d]);
    }
}

The compiler retains the outer stable index bi and inner stable index di, so $a[$b][$d] can compile approximately as a.values[bi].values[di].

The same principle applies to JavaScript. Iteration-derived keys carry hidden stable-index provenance. If the key is used only to return to its originating Map, the compiler may not need to materialize it at all.

#Compiler-Constant Keys and Symbols

Literal and compiler-constant keys should not repeatedly execute their key semantics at runtime.

$user["id"]
$user["name"]
$user["email"]

"id"    → Symbol A
"name"  → Symbol B
"email" → Symbol C

A symbol is not a universal Map index.

Map A: Symbol("foo") → index 7
Map B: Symbol("foo") → index 19
Map C: Symbol("foo") → absent

The pipeline is constant K → canonical Symbol(K) → per-Map/per-shape resolution → stable index i → cache i.

Once a Map or shared shape establishes (Map/shape, Symbol("email")) → 2, subsequent accesses can use a guarded cached index. Unrelated appends do not invalidate index 2.

#Object Key Semantics

Arbitrary objects may be Map keys by defining:

__hash__()         → deterministic intermediate H
__equals__(other)  → bool

Both are -E-D by default, like ordinary U functions. A key implementation requiring effects or nondeterminism is not eligible for ordinary deterministic Map resolution.

K
↓
K.__hash__()
↓
H
↓
resolver generation(s)
↓
candidate stable index i
↓
keys[i].__equals__(K)
↓
match / collision

Two unequal objects may legally produce the same H. Resolver algorithms must preserve enough collision information to examine every relevant candidate until __equals__ establishes the result.

__hash__ selects candidates; __equals__ establishes key identity.

Constant Objects

Compiler-constant objects can be canonicalized through the same semantics. Because ordinary U functions are -E-D, these methods may execute during compile/JIT time when their inputs are compiler constants. The resulting symbol still maps independently to a stable index in each Map or shape. Dynamic objects use the same semantics at runtime.

#Shared Shapes

Maps with the same insertion history can share symbol-to-index metadata.

Shape #174

Symbol("id")    → 0
Symbol("name")  → 1
Symbol("email") → 2

Individual Maps can share the shape rather than maintaining equivalent reverse metadata separately. Shape transitions can themselves be shared.

Insertion history is a Map shape.

This is especially useful for records, JSON objects, database rows, headers, configuration structures and API payloads.

#Tombstones and Reinsertion

Deletion does not move later entries. It writes TOMBSTONE into the key position and iteration skips it.

before: 0 A | 1 B         | 2 C
after:  0 A | 1 TOMBSTONE | 2 C

Append-on-Reinsert

For PHP-compatible semantics, reinserting B appends it, e.g. B → 3. Historical resolver entries remain harmless because the old position is a tombstone. When multiple historical candidates exist, the newest live insertion wins; because insertion indices increase monotonically, this is the greatest live candidate index.

Revive-on-Reinsert

Other collection semantics may revive the old position. Tombstoning is storage mechanism; reinsertion ordering is language/collection policy.

#Stable-Index Invalidation

A stable index belongs to a Map storage generation. Append, value update, new storage slabs, tombstones, resolver growth/sealing/replacement/compaction, membership-filter rebuilds, SwissTable resizing inside an unsealed resolver generation, and switching algorithms for later generations do not renumber unaffected entries.

Deleting the cached key makes that key's cached position absent/stale, but does not invalidate unrelated indices. Append-on-reinsert gives the reinserted key a new stable index.

Storage Compaction

Storage compaction that packs away tombstones renumbers entries and therefore creates a new Map storage generation. Caches capable of surviving arbitrary code must be guarded by storage generation or equivalent shape identity.

Mutation invalidates a stable index only when it changes the relevant index → entry mapping.

#Resolver Compaction Is Not Storage Compaction

Map storage compaction renumbers keys[]/values[], changes the storage generation, and invalidates moved stable indices.

Resolver compaction reorganizes reverse-index metadata while leaving keys[]/values[] untouched, so stable indices remain valid.

#Dynamic Resolution

After eliminating iterator provenance, compiler-constant work, shape specialization and cached resolution, the residual problem is dynamic K → stable index i.

Maps expose an abstract resolver: Resolver<K>.probe(K) → candidate stable index(es). Exact key equality remains authoritative. The resolver is acceleration metadata, not Map storage.

#Two-Stage Dynamic Resolution

K
↓
deterministic key function
↓
H
↓
per-Map reverse resolver
↓
stable index i
↓
keys[i] exact validation
↓
values[i]

F(K) depends on key type: strings use a deterministic hash of UTF-8 bytes; integers use identity/mixing; symbols use canonical IDs; objects use __hash__; tuples use a composed deterministic hash.

The intermediate H does not determine where the actual value lives. It exists only to accelerate discovery of the stable insertion index. Hash collisions are allowed and candidates are validated against keys[i].

#String Keys

String resolvers operate directly on U's underlying canonical UTF-8 byte representation. ASCII is simply the UTF-8 subset 0x00..0x7F.

"foo" → 66 6f 6f
"猫"  → e7 8c ab

Both are ordinary byte sequences over a radix-256 logical alphabet. No ASCII→Unicode tree transition is required. Physical radix nodes remain adaptive and compact rather than allocating 256 child pointers universally.

#Generational Reverse Resolver

Do not migrate historical resolver entries merely because the Map grows.

The reverse index consists of generations: G0 | G1 | G2 | G3 | ... | current.

ResolverGeneration {
    min_index
    max_index
    algorithm
    membership_summary
    data
}

Only the current generation accepts new entries. When it reaches its target size: seal it; optionally freeze/compact its resolver representation; construct its immutable membership summary; choose the appropriate algorithm for the next generation; then begin appending resolver entries to that new generation.

Sealed generations never need to be rewritten merely because later generations exist.

#Geometric Resolver Generations

G0       8
G1      32
G2     128
G3     512
G4    2K
G5    8K
G6   32K
G7  128K
...

The precise multiplier is benchmark-tunable; 4× is a useful starting hypothesis because it keeps the number of historical generations small while giving each generation enough lifetime to justify specialization. Storage slabs and resolver generations need not have identical boundaries.

#Resolver Algorithms by Generation Size

These thresholds are hypotheses and should be benchmark-tuned per architecture.

Tiny: ~1–8

Use direct unrolled/SIMD comparison. No separate hash table is justified.

Small: ~9–64

Use SIMD fingerprints plus exact candidate validation, or a tiny SwissTable-style group. A separate Bloom filter is unnecessary.

Medium: ~65–4K

Default to a SwissTable-style resolver. Sparse storage contains only resolver metadata and stable indices; authoritative keys and values remain dense.

Large: ~4K–64K

For arbitrary hashable keys, continue Swiss-style generations if benchmarks favor them. For string-heavy generations, consider compressed/adaptive radix resolution when reduced footprint and prefix sharing win.

Very Large: ~64K+

For string-keyed generations, benchmark compact ART/Patricia against SwissTable. For arbitrary non-string keys, compact hash-derived resolvers may remain preferable. The invariant is the resolver interface, not its implementation.

#Adaptive Radix / Patricia Resolver

String generations can use a byte-oriented compressed radix structure over UTF-8.

"content-"
    ├─ "length"   → 17
    ├─ "type"     → 31
    └─ "encoding" → 46

Unary paths are compressed. Nodes adapt to observed fan-out: Node4 → Node16 → Node48 → Node256. A logical radix of 256 does not imply a physical array of 256 pointers at every node.

Sealed/read-mostly generations can compile these structures into packed arrays such as nodes[], edges[], prefixes[], and terminal_indices[], with relative offsets where practical.

#Why SwissTable Rehashing Is Acceptable Here

Rehashing was undesirable when imagining a hash table as the Map itself. It is much less problematic when hashing is merely reverse-index acceleration.

A mutable resolver generation may rehash H → stable-index records without moving keys[] or values[], and without invalidating iterator indices, shape caches, literal/symbol caches, or previous stable indices. Once a generation is sealed, it need never resize again.

#Bloom and Negative Membership Filters

Bloom-like structures are not authoritative Map indexes. They are optional compact negative filters in front of resolver generations.

                     H
                     │
          compact generation filters
             /       |       \
           no       maybe     no
                     │
                     ↓
              actual resolver
             Swiss / ART / ...
                     │
                     ↓
               stable index

A negative filter result means definitely not in this generation. A positive result means only possibly in this generation, requiring an actual resolver probe followed by exact key equality.

This is particularly valuable when resolver generations are large and cold. A few compact membership summaries may remain in cache while the actual SwissTable or ART structures do not.

Dynamic Read

If all generation summaries are negative, the key is definitely absent. Otherwise probe only candidate generations.

Dynamic Write

If all historical summaries and the current resolver prove absence, append immediately at the next sequential stable index. No physical insertion-bucket search is needed in authoritative storage.

Filter Selection

Small generations normally need no separate Bloom filter. Larger sealed generations may choose no filter, Bloom, blocked Bloom, XOR, quotient, or fingerprint structures. False positives are acceptable; false negatives are forbidden.

Membership filters eliminate resolver probes; they never establish Map membership.

#Parallel / Pipelined Generation Lookup

Resolver generations are independent. Their probes have no sequential dependency, so implementations can issue independent loads concurrently rather than waiting for one generation to miss before touching the next.

G0.probe(K) ─┐
G1.probe(K) ─┤
G2.probe(K) ─┼→ live candidates → newest applicable index
G3.probe(K) ─┘

For loops containing several dynamic lookups, U can pipeline across both dimensions: multiple keys × multiple candidate generations. The useful hot-loop metric becomes resolved keys per cycle, not only isolated cold-lookup latency.

#Historical Candidates and Reinsertion

Sealed generations can retain historical resolver entries. If G2 says "foo" → 173 and index 173 is later tombstoned, validation rejects it. If PHP-style reinsertion later creates G7: "foo" → 9182, both generations may return candidates, but the greatest live matching stable index is authoritative.

Old resolver generations therefore do not need deletion updates merely because authoritative storage changes.

#Optional Resolver Consolidation

Generational stability does not forbid consolidation. If profiling shows too many generations hurt throughput, U may construct a consolidated resolver in the background.

Consolidation rewrites resolver metadata, never stable Map storage.

Old readers may continue using the previous immutable resolver view until reclamation is safe.

#Resolver Independence from Storage Slabs

Storage slabs optimize allocation, append, iteration, stable random access and bulk deallocation. Resolver generations optimize dynamic key → stable index. Their boundaries need not coincide.

A resolver generation may cover several storage slabs, and a large storage slab may contain indices covered by different resolver generations.

#Power-of-Two Slab Arithmetic

Stable indices map naturally onto power-of-two storage slabs. Operations that might otherwise require division or modulo can often use masks, shifts, clz, and ctz. A stable index cheaply determines slab and offset, while sequential iteration simply walks slab memory directly.

#NaN Boxing and Batched Lookup

Because dynamic U values have uniform machine-word representations, multiple keys can be classified and processed together.

K1 K2 K3 K4 K5 K6 K7 K8
 ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓
 S  I  S  O  I  S  Y  S

Different classes use specialized paths: integer → arithmetic/hash resolver; symbol → canonical-ID resolver/cache; string → UTF-8 hash or radix resolver; object → __hash__/__equals__. Arbitrary keys therefore do not require one universal expensive algorithm.

#Map Access Hierarchy

1. Iterator provenance: index already known → direct access.
2. Compiler-constant key: Symbol(K) known → check cached Map/shape mapping.
3. Cached symbol: guard → direct stable index.
4. Uncached symbol: resolve once → cache stable index.
5. Previously resolved dynamic key: guarded cached stable index.
6. Novel dynamic key: compute H → membership summaries → candidate generations → pipelined probes → exact equality → stable index.
7. Definitely absent write: append at next stable index.

The goal is to make real programs execute the fully dynamic path only when they genuinely lack enough information to do something cheaper.

#Insertion-Order Iteration

Insertion-order iteration is native to storage. Key/value iteration walks key and value slabs sequentially. Value-only iteration need not touch keys at all. Iteration does not operate through the reverse resolver, so hash-table sparsity has no effect on ordinary Map iteration.

#PHP and JavaScript Transpilation

foreach ($users as $id => $user) {
    $users[$id]["active"] = true;
}

The compiler does not rediscover $id. Nested loops similarly retain outer and inner stable indices.

Literal accesses such as $user["name"] and $user["email"] use compiler symbols plus per-Map/per-shape stable-index caches.

A cross-Map pattern such as $foo[$c] where $c came from iterating another Map requires genuine dynamic resolution. Even then, membership metadata can prove absence and allow immediate append.

Do not optimize a general-purpose operation when program structure makes the operation unnecessary.

#Trees

A dynamic Tree can be represented recursively using Maps whose values may point to other Maps/Trees. The same principles apply: stable insertion indices, sequential iteration, compiler-constant specialization, derived reverse resolution, and owner-scoped allocation.

Path Copy

tree.set(key, val) may construct a new root by copying only changed paths while sharing unchanged subtrees. Leaf values are copied inline where possible; subtrees can be shared by reference.

MVCC

Shared mutable state uses +M(MVCC). Reads acquire the current root/version; writes construct a new immutable version and CAS the root. Lock-free reads require safe reclamation through epochs, RCU-like reclamation, hazard references, ownership acquisition, or an equivalent mechanism.

#Ownership, Capabilities, Determinism and Containment

Assignment Determines Lifetime

Where a value is assigned determines which owner controls its lifetime. No explicit arena-selection API is required in ordinary U code. c expr copies a value; the assignment target determines the destination lifetime. The compiler may implement this using owner slab chains.

-E-D by Default

U functions are deterministic and effect-free by default. f foo(...) means f-E-D foo(...) unless explicitly widened. -E means no undeclared effects; -D means deterministic. Functions explicitly declare +E and/or +D when required.

This makes ordinary functions easier to execute, memoize, fold and specialize. Compiler-constant __hash__ and __equals__ operations that remain -E-D can participate in compile/JIT-time symbol canonicalization.

Capabilities Through Parameters

Effectful operations require capabilities explicitly reachable through parameters. Filesystem, network, crypto, database and similar authority are capabilities rather than ambient globals.

# +E Capabilities and Events

+E on a reference is a compile-time capability view. Assignment may narrow capabilities but never widen them.

server: Server +E(.read)
server: Server +E([.read, .write, .stat])

parent: TreeManager +E(RemoveEvent)

Capability sets flatten. Absence is denial.

#Back-References: +R(parent)

Back-references do not participate in strong ownership and cannot mutate through the back-reference. They may carry event capabilities.

d TreeNode
    children: [TreeNode +R]
    parent: TreeManager +R(parent) +E(RemoveEvent)

Runtime weak-reference resolution must use a mechanism that cannot dereference reclaimed memory.

#Event System

e(obj) accesses the object's event emitter. Handlers match by event type.

e(t).on(RemoveEvent => t.children.remove(ev.node))

Handlers are owned by their registrants. Emitter references to handlers are weak/back references so registration does not create ownership cycles.

#Request Scoping

f+E handle(req: Request +M, server: ServerState) -> Response

Request-local allocations are owned by req. Data that must outlive the request explicitly crosses into a longer-lived owner, for example through <<. When the request dies, its slab chain is released in a small number of slab operations.

#PHP Transpilation

$_GET/$_POST/$_SERVER/$_COOKIE
    → req.query / req.body / req.headers / req.cookies

global $var
    → explicit parameter

apcu_store/apcu_fetch
    → server.cache operations

file_get_contents
    → server.fs.read

$_SESSION
    → request session view + explicit persistence

PHP array semantics can be preserved while U chooses radically different physical storage and access paths.

#Vectorization (+V)

+V operations compile bulk transforms into SIMD loops over contiguous slab regions with scalar tails where necessary. Map-heavy loops may batch dynamic resolver operations across both keys and resolver generations, optimizing streams of operations rather than merely isolated latency.

#GPU (+R(GPU))

c+R(GPU) list can linearize a slab chain into a contiguous device representation. Maps can transfer as structure-of-arrays: keys[], values[], and resolver metadata where useful. GPU resolver representation need not match CPU resolver representation.

#Deallocation Summary

#Design Principles

1. Assignment determines lifetime. Where a value is assigned determines which owner controls its storage.
2. Ownership determines deallocation. Owner-scoped allocation makes bulk release possible without tracing GC.
3. Determinism and absence of effects are defaults. Functions are -E-D unless explicitly widened.
4. Lists are stable. Power-of-two slabs grow without relocating existing elements.
5. Maps are ordered dense storage first. Parallel key/value Lists are authoritative.
6. Stable indices are semantic handles. Sequential insertion creates positions reusable by iteration, shapes, caches and resolvers.
7. Symbols identify keys; indices identify positions.
8. Object identity is separate from hashing. __hash__ selects candidates; __equals__ establishes equality.
9. Avoid reverse lookup before optimizing it.
10. Dynamic resolution is a separate subsystem.
11. Resolver generations are backward-stable.
12. Resolver algorithms may evolve with scale.
13. Historical resolvers may remain immutable.
14. Bloom/XOR structures are filters, not indexes.
15. Dynamic reads and writes exploit negative membership information.
16. Resolver compaction is not Map compaction.
17. Map storage compaction is exceptional.
18. Hashing is a tool, not the Map.
19. UTF-8 bytes are the natural string resolver alphabet.
20. Optimize streams, not merely operations.
21. Dense application data beats sparse application data.
22. Hardware structure matters.
23. Capabilities are contained.
24. Do not reach for the blunt instrument by default.

                         U Map
                           │
          ┌────────────────┴────────────────┐
          │                                 │
 authoritative storage              reverse acceleration
          │                                 │
 dense stable slabs              generational Resolver<K>
 keys[i], values[i]                        │
          │                    ┌────────────┼────────────┐
          │                  SIMD         Swiss       ART/Patricia
          │                    │            │             │
          │                    └──────┬─────┴─────────────┘
          │                           │
          │                    stable index i
          │                           │
          └───────────────────────────┘

            optional generation filters
                 Bloom / XOR / etc.
                        │
              eliminate cold probes

The storage representation is optimized for append, iteration, locality, ownership and stable positions. The reverse resolver is free to use whatever algorithm best fits each stage of the Map's lifetime without forcing historical data to migrate.

Whenever the compiler already knows the position, the fastest resolver is no resolver at all.