Compiler & VM Architecture Reference

This document details Tinsel's internal compilation pipeline, 24-byte tagged Value representation, zero-sort structural hashing, in-place prototype dispatch, multi-pass optimizer, and bytecode instruction set.

1. Compilation & Execution Pipeline

+---------------------------------------------------------------+
|                     Tinsel Source (.tin)                      |
+---------------------------------------------------------------+
                                |
                                v
+---------------------------------------------------------------+
|                    Lexer (internal/lexer)                     |
|  - Token stream with line & column span tracking              |
|  - Template pattern strings & f"..." string interpolation     |
+---------------------------------------------------------------+
                                |
                                v
+---------------------------------------------------------------+
|                 Pratt Parser (internal/parser)                |
|  - Top-down operator precedence (binding powers 0..140)       |
|  - Expression & Pattern AST construction                      |
+---------------------------------------------------------------+
                                |
                                v
+---------------------------------------------------------------+
|               Bytecode Compiler (internal/vm)                 |
|  - AST constant folding & comprehension reduction fusion      |
|  - Flat bytecode chunks, lexical locals & closure upvalues    |
+---------------------------------------------------------------+
                                |
                                v
+---------------------------------------------------------------+
|         Multi-Pass Bytecode Optimizer (internal/vm)           |
|  - Jump threading, dead-code & loop-accumulator elision       |
|  - Peephole superinstruction fusion & constant pool pruning   |
+---------------------------------------------------------------+
                                |
                                v
+---------------------------------------------------------------+
|           Stack-Based Virtual Machine (internal/vm)           |
|  - 24-byte tagged Value stack & inline 32-bit Vec2/Range      |
|  - In-place prototype (__proto__) CallFrame method dispatch   |
+---------------------------------------------------------------+

2. The 24-Byte Tagged Value Memory Model

To avoid heap-boxing primitives in Go's any (interface{}) during tight loops and graph searches, every runtime value is represented by a uniform 24-byte struct (internal/value/value.go):

type Value struct {
    Type ValueType // 8-bit discriminator tag (ValInt, ValFloat, ValVec2, ValRange, ...)
    Num  int64     // Inline payload: int64, bool (0/1), rune, IEEE-754 float64 bits, or packed 2x32-bit Vec2/Range
    Obj  any       // Heap pointer only when needed (string, *Array, *Map, *Closure, *big.Int, 64-bit Vec2/Range)
}

Zero-Allocation Inline Packing

1. Scalars (ValInt, ValBool, ValChar, ValFloat): Stored entirely inside Num with Obj == nil. Float values bit-cast their 64-bit IEEE-754 representation into Num via math.Float64bits.
2. Packed 32-bit Vec2 and Range (Obj == nil): Whenever both (X, Y) coordinates of a vec2 or both [start, end) bounds of a range fit within signed 32-bit integers (-2,147,483,648 to 2,147,483,647), they are packed into the high and low 32 bits of Num with Obj == nil. Creating, adding, comparing, and hashing 2D coordinates in bfs/dijkstra runs with zero heap allocations. Coordinates exceeding 32-bit bounds transparently fall back to heap-allocated *Vec2 or *Range structs in Obj.

3. Zero-Sort Structural Hashing & Prototype Dispatch

Comparable Map & Struct Keys (Value.HashKey())

Tinsel allows any composite value (arrays, tuples, vectors, ranges, maps, and user-defined struct instances) to be used as a map or set key:

• Primitives, packed Vec2, and packed Range return fixed-size comparable Go struct keys with zero allocations.
• User-defined struct declarations (struct Name(f1, f2, ...)) record their ordered field names in __proto__.__fields__. When hashing a struct instance with 0 to 4 fields, Value.HashKey() constructs a comparable StructHashKey0..4 struct directly in declaration order—bypassing map key sorting and string serialization entirely.

In-Place Prototype CallFrame Dispatch (__proto__)

Standard library composite types (grid, rangeset, set, deque, Iter) and user-defined struct types are implemented in pure Tinsel (stdlib/*.tin) and attach a __proto__ table. When OP_METHOD_CALL invokes a Tinsel method closure on a struct, prototype-backed map, or built-in type (array, string, int, option), the VM pushes a new CallFrame directly onto vm.frames in-place rather than re-entering a recursive Go interpreter loop.

4. Compiler & Multi-Pass Bytecode Optimizer

When optimization is enabled (the default for tinsel run and tinsel compile), Tinsel applies both AST-level and bytecode-level optimizations (internal/vm/optimizer.go):

1. AST Constant Folding & Immutable let Propagation:
   • Evaluates constant arithmetic, bitwise, string, character, range (1..=10), <-> Manhattan distance, and constant vec2/vec3 expressions at compile time.
   • Propagates immutable let scalar constants into downstream expressions and eliminates untaken if branches when conditions are compile-time constants.
2. Comprehension Reduction Fusion:
   • Fuses (for x in iterable { ... yield expr }).sum() (as well as .count(), .min(), .max(), and .product()) into a single scalar accumulator register without allocating an intermediate array.
   • Elides the hidden OP_BUILD_ARRAY 0 accumulator for for loops that contain no yield statement, and skips element indexing on wildcard loops (for _ in a..b).
3. Peephole Superinstruction Fusion & Jump Threading:
   • Fuses common multi-instruction sequences into single-dispatch superinstructions (OP_INC_LOCAL, OP_LESS_LOCAL_JMP_F, OP_GET_LOCAL_INDEX, etc.).
   • Threads jump-to-jump chains and strips unreachable instructions after return/break/continue.
4. Dead Constant Pool Pruning:
   • Compacts Chunk.Constants after peephole optimization by removing unreferenced constants and remapping surviving constant indices.

5. Bytecode Instruction Set Reference

Inspect compiled bytecode for any file via ./bin/tinsel compile <file.tin> (optimized) or ./bin/tinsel compile --no-opt <file.tin> (unoptimized). All 16-bit operands (u16) use big-endian encoding.

5.1 Constants, Literals & Stack Manipulation

5.2 Local Variables, Globals & Lexical Upvalues

5.3 Arithmetic, Bitwise, Relational & Spatial Operators

5.4 Collections, Structs, Indexing & Fields

5.5 Control Flow, Calls, Closures & Modules

5.6 Fused Peephole Superinstructions