Suppose I have a ubyte and a void* and a list of types for a tagged reference, I use 0 to mean void itself, 1 for int etc. then N+1 I use to mean slices of my sumtype and there will be an int that the length of the slice at index 0. Then N+M is a slice of slice of... of my sumtype, till you fill up the ubyte.
Length‑Prefixed Generic Slice with Type Tags and 255‑Byte Limit
The user is describing a tagged reference / tagged union / sum type encoding scheme. They have:
- A
ubyte(8 bits) for the tag - A
void*for the data pointer - A list of types for a tagged reference/sum type
Encoding scheme:
- Tag 0 means
voiditself - Tag 1 means
int(and presumably other primitive types follow) - Tag N+1 means "slice of my sumtype" (where N is the number of primitive types?)
- At index 0 of the slice, there's an
intthat is the length of the slice - Then N+M is a "slice of slice of... of my sumtype" (nested slices)
- This continues until you fill up the ubyte (256 possible tags)
This is a fairly technical systems programming / type system design question. The user seems to be describing a design and likely wants feedback, validation, or help reasoning about it. They haven't asked a specific question yet - they've just stated the design.
I should:
- Acknowledge and restate the design to make sure I understand it correctly
- Identify potential issues or considerations
- Ask what specific aspect they want help with (implementation, encoding efficiency, alignment, memory layout, type safety, etc.)
Let me break down what I understand:
- 8-bit tag gives 256 possible variants
- Tag 0 = void (unit/empty type)
- Tags 1..N = primitive types (int, float, etc.)
- Tag N+1 = slice of the sumtype (fat pointer: ptr + len, where len is stored at index 0?)
- Tag N+2 = slice of slice of sumtype? Or N+M where M is nesting depth?
- Wait, "N+M is a slice of slice of... of my sumtype, till you fill up the ubyte"
Actually, re-reading: "N+1 I use to mean slices of my sumtype and there will be an int that the length of the slice at index 0. Then N+M is a slice of slice of... of my sumtype, till you fill up the ubyte."
So:
- Tags 1..N: primitive types
- Tag N+1:
[]T(slice of sumtype) - Tag N+2:
[][]T(slice of slice of sumtype) - ...
- Tag N+M:
[][][]...T(M-dimensional slice) - Until tag 255
Wait, but they said "there will be an int that the length of the slice at index 0". This suggests the slice representation stores the length at the first element? Or perhaps the void* points to a struct where index 0 is the length?
This sounds like it could be related to:
- Zig's tagged unions
- A custom dynamic type system
- A serialization format
- An interpreter/VM value representation
I should ask clarifying questions about:
- What language they're working in (C? Zig? Custom?)
- Whether the slice length is stored inline with the data or alongside the pointer
- What specific problem they're trying to solve (memory layout, tag allocation, recursive type representation?)
- Whether they need help with the math of how many nesting levels fit in a ubyte
Actually, looking at the phrasing again, this might be a "is this a good design?" or "how do I implement this?" or "what are the edge cases?" type of question. Since they haven't explicitly asked anything, I should provide a thoughtful analysis of the design and ask what they need.
Key observations to share:
- With only 256 tags, if you have many primitives, you limit nesting depth
- Slice-as-tag means the type system encodes dimensionality in the tag, which is unusual but valid
- Storing length at index 0 means the pointer points to a length-prefixed array (Pascal-style string but for generic slices)
void*loses type safety; the tag carries the type info- Nested slices with lengths at index 0: for
[][]T, each sub-slice also has its length at its own index 0 - Filling up the ubyte: if N primitives + M nesting levels = 255 max, that's the constraint
Let me provide a concise but thorough response that analyzes this design and asks what they need help with specifically.
I think I understand the scheme you're describing. Let me restate it to check:
- Tag 0:
void(the empty/unit type) - Tags 1..N: Primitive types (
int,float,bool, etc.) - Tag N+1:
[]T— a slice of the sumtype itself, where the pointed-to memory has its length at index 0 - Tag N+2:
[][]T— a slice of slices - ...
- Tag N+M: M-dimensional nested slices
- Tags N+M+1..255: Unused (or reserved)
So your tag byte is doing double duty: it identifies both the primitive type and the array nesting depth of the value behind the
void*.A few things worth thinking through:
1. Tag budget math
If you have, say, 16 primitive types (N=16), you get M = 255 − 16 = 239 dimensions of nesting. That's plenty. But if your primitive list grows, your max nesting depth shrinks. If you ever need more than ~200 primitives, you collide with your slice tags.
2. The "length at index 0" layout
For
[]T, the void* points to a block where [0] is an int length and [1..len] are the elements. That works, but it means every slice access pays a pointer indirection just to read the length. A more common fat-pointer layout keeps (ptr, len) together in the value struct rather than in the heap block. Is there a reason you want the length inline with the data?3. Nested slices
For
[][]T, each inner slice is itself a void* with its own tag. Does the outer slice's memory contain (tag, void*) pairs? Or do all inner slices share the same tag (N+1) and the outer tag (N+2) just means "array of arrays"? If the latter, you lose the ability for a [][]T to hold rows of different types.4. Homogeneity vs. heterogeneity
If
[]T means "slice of the sumtype," then each element can independently be any variant (int, void, another slice, etc.). That's powerful but means your slice of 1000 ints carries 1000 tag bytes. If you instead want []int to be homogeneous, you'd need separate tags for []int, []float, etc., which explodes your tag space.5. The void + tag model*
This is essentially a manual vtable or tagged union. It's flexible, but every operation needs a switch on the tag. Have you considered whether you want inline storage for small primitives (e.g., fitting an
int directly in the pointer word) to avoid heap allocations for simple values?What aspect are you looking to nail down — the bit-level encoding, the allocator strategy for the slices, or whether this is a sound type-system design?
is there a classical name
Searching for Classical Name of Array‑Nesting Tag Encoding
The user is asking if there's a classical name for the data structure / type system scheme they described. Let me think about what they're describing:
- A ubyte tag + void* pointer
- 0 = void, 1-N = primitive types, N+1 = slice of sumtype, N+2 = slice of slice, etc.
- Length stored at index 0 of the slice data
This sounds like:
- A tagged union / discriminated union / sum type - but with the specific encoding of nesting depth in the tag
- A fat pointer or tagged pointer scheme
- The slice-with-length-at-index-0 sounds like a flexible array member or variable-length array in C
- The whole thing with void* + tag is essentially a boxed value or tagged reference
But the specific scheme where:
- Tag encodes both the base type AND the array nesting depth
- Pointer points to data where length is inline
This is very reminiscent of:
- Tagged pointers in dynamic languages (Lisp, Smalltalk, etc.)
- Boxed values in language runtimes
- Fat pointers with tag bits
Actually, the specific encoding where higher tag values mean "array of the lower type" is somewhat like:
- Type descriptors or type tags in some dynamic language implementations
- Array type encoding where you have a base type and dimensionality
Wait, the specific thing about N+1 being slice, N+2 being slice of slice... this is essentially encoding array rank or dimensionality in the tag byte.
Classical names for this kind of thing:
- Tagged pointer / tagged reference
- Boxed value (when primitive values are heap-allocated with a tag)
- Fat pointer (when pointer carries extra metadata, though usually that's width, not type)
- Type tag / tag word
- Header word (in garbage collectors / runtime systems)
- Self-describing value
But I think what they're really asking about is whether this specific scheme of encoding dimensionality in the tag has a classical name. Let me think...
In array theory / type theory:
- Rank-polymorphic arrays (APL, J)
- Nested arrays (APL)
In language implementation:
- This is essentially how Java arrays work at the JVM level -
Object[]is an array of references, and multi-dimensional arrays areObject[][]which is an array ofObject[] - In .NET, SZ arrays vs multi-dimensional arrays
But the specific tag encoding... I don't think there's a single classical name for this exact scheme. The closest would be:
- Tagged union / discriminated union - for the sum type aspect
- Fat pointer - for the pointer+metadata aspect
- Boxed value - for the heap-allocated representation
- Self-describing data / tagged data structure - for the runtime type information
Actually, looking more carefully at the description: "N+1 I use to mean slices of my sumtype and there will be an int that the length of the slice at index 0. Then N+M is a slice of slice of... of my sumtype"
This sounds very much like:
- Cons cells or S-expressions in Lisp (where lists are built from pairs)
- But more specifically, this is how dynamic arrays or vectors are represented in many language implementations
Wait - I think the user might be describing something very close to how Perl's SV (Scalar Value) or Python's PyObject works, but simplified. Or perhaps Lua's TValue.
But the specific encoding of array nesting in the tag... I don't know of a classical name for that exact encoding. Let me search to see if there's something specific.
Buscar en la Web
tagged pointer encoding array dimensionality in type tag classical name discriminated union tag byte encodes array rank nesting depth void pointer with ubyte tag sum type slice encoding name 22 resultados
Identify Classical Component Names and Note Dimensionality Encoding Choice
The search results give me some useful context about tagged pointers and tagged objects, but they don't directly answer whether there's a classical name for the specific scheme the user described (where tag values N+1, N+2, etc. encode array nesting depth/dimensionality).
Let me think about this more carefully. The user's scheme is:
- ubyte tag + void* pointer
- Tag 0 = void
- Tags 1..N = primitive types
- Tag N+1 = slice of sumtype (1D array)
- Tag N+2 = slice of slice (2D array)
- etc.
This is essentially:
- A tagged pointer / tagged reference - the general concept of pairing a type tag with a pointer
- A discriminated union / sum type - the type system aspect
- The specific encoding of array dimensionality in the tag is...
I don't think there's a single classical name for this exact scheme. But there are related concepts:
- Array rank polymorphism (APL, J) - where operators work on arrays of any rank
- Nested arrays (APL)
- Boxed arrays (APL J) - where arrays can contain other arrays
- Fat pointers - pointers with extra metadata
- Tagged objects - in dynamic language runtimes
Actually, let me think about whether there's something closer. The scheme where you have a base type and then higher tag values mean "array of base type", "array of array of base type", etc. - this is somewhat like:
- Type descriptors in some systems
- Array type encoding in bytecode/JVM where array types are encoded as
[I,[[I, etc. - Type tags with dimensionality - not a standard term
In the JVM, array types have descriptors like
[I for int[], [[I for int[][]. This is similar in spirit but not the same encoding.I think the most accurate answer is that there isn't a single classical name for this exact scheme, but it's a combination of:
- Tagged pointer / tagged reference - for the tag+pointer pair
- Discriminated union / sum type - for the type system
- Boxed value - for heap-allocated representation
- The array nesting encoding is similar to rank polymorphism or nested array representations
Let me also consider if this is related to Cons cells in Lisp. In Lisp, lists are built from cons cells (pairs), and nested lists are just lists of lists. But that's not quite the same.
Another thought: in some Forth systems and in some array languages, there's the concept of shape which encodes dimensionality separately from the data.
I think the honest answer is: there isn't one classical name for this exact scheme. It's a tagged pointer / tagged reference representation with a specific encoding convention for array nesting. The closest classical concepts are tagged pointers (from Lisp, Smalltalk, etc.) and discriminated unions (from type theory).
Let me provide a clear, helpful answer that identifies the classical names for the components and notes that the specific dimensionality encoding is a design choice rather than a named classical pattern.
There isn't one classical name for the exact scheme you described, but it combines several well-known concepts:
Tagged pointer / tagged reference — the
ubyte + void* pair itself. This goes back to Lisp (1960s) and Smalltalk, where low bits of a pointer word encode the type, letting the runtime dispatch without dereferencing memory. Your version uses a separate byte rather than stealing pointer bits, which is the same idea just less compressed. Discriminated union (or sum type, tagged union, variant) — the type system where a tag tells you which constructor/primitive is active. This is the classical name for "void or int or float or ...".
Boxed value — when a primitive like
int is heap-allocated behind a pointer with a tag, rather than stored inline in the pointer word.Fat pointer — usually means
(ptr, len) or (ptr, len, cap) stored together, but the term is sometimes stretched to any pointer carrying metadata.Where your scheme diverges from the classical literature is the specific convention that
N+1 means "1D slice of sumtype", N+2 means "2D slice", etc. That encoding doesn't have a standard name — it's a rank-encoded tag or dimensionality-encoded tag, but those are descriptive, not classical terms.The closest classical analog to that nesting convention is probably nested arrays in APL/J, or the way the JVM encodes array types as
[I, [[I, [[[I — where each [ prefix adds one dimension. Your tag byte is doing the same job as those bracket prefixes, just in integer form.So if you need a name for the whole thing: it's a tagged-pointer representation of a sum type with rank-polymorphic array nesting.