diff options
Diffstat (limited to 'doc/0/0-value.md')
| -rw-r--r-- | doc/0/0-value.md | 184 |
1 files changed, 115 insertions, 69 deletions
diff --git a/doc/0/0-value.md b/doc/0/0-value.md index 3485b00..c2810d8 100644 --- a/doc/0/0-value.md +++ b/doc/0/0-value.md @@ -1,12 +1,16 @@ -# NaN-packed Value representation +# NaN-packed Value -The format of a binary64 floating-point number, in big-endian notation: +<!--TOC--> + +Zisp uses NaN-packing for a uniform 64-bit Value representation. + +The format of a binary64 floating-point number, in big-endian notation, is: { sign: 1 bit, exponent: 11 bits, fraction: 52 bits } When the 11 exponent bits are all set, it's either a NaN or an Infinity. -For value packing, the remaining 53 bits are available, giving us `2^53` values +For value packing, the remaining 53 bits are available, giving us `2^53` values, minus the following four bit patterns: *** FORBIDDEN BIT-PATTERNS *** @@ -42,9 +46,9 @@ We split those `2^53 - 4` available values into four groups, each allowing for sign = 1, quiet = 0 :: Positive Fixnum from 0 to 2^51-2 - sign = 0, quiet = 1 :: Pointers and various immediates + sign = 0, quiet = 1 :: Pointers and immediates - sign = 0, quiet = 0 :: Internal use by interpreter + sign = 0, quiet = 0 :: Tree-VM instructions ## Fixnums @@ -63,11 +67,11 @@ payload value, which would step on Forbidden Value #2, Negative Infinity. This region of 51-bit values is divided as follows, based on the three highest bits, providing a payload value of 48 bits for each. - 000 :: Pointer to heap object (type-tagged) + 000 :: Pointer to istr object - 001 :: Pointer to list values (length-tagged) + 001 :: Pointer to list values - 010 :: Pointer to istr object + 010 :: Pointer to heap object 011 :: Immediate short string @@ -89,58 +93,89 @@ bits, providing a payload value of 48 bits for each. (etc.) -Forbidden Value #3, Positive cqNaN, is avoided by not using 0 as a valid type -tag value for heap pointers. +### Interned strings -### Type-tagged heap pointers +An istr is an interned string of up to 65,535 arbitrary bytes. These are very +similar to symbols in Lisp and Scheme. Of the 48-bit payload value, the lower +32 bits are an offset into a virtual memory region dedicated to this type, and +the higher 16 bits encode the length of the string, which cannot be zero. The +empty string has a different representation; see immediate short strings. -Regular heap objects are allocated with 16-byte alignment, meaning the lowest -four bits are naturally zero. We exploit this by shifting down the address by -four bits, making room for more tag bits immediately following the 16 high bits -that mark the value as a heap pointer. +Using a 32-bit offset value means that interned strings can occupy a total +maximum of 4 GiB of memory, which should be comfortably sufficient. -Thus, a value can be checked against a specific heap object type by comparing -the 20 high bits to a combined constant value: the 16 highest bits indicating -that it's a heap pointer, and the 4 bits after that denoting the heap type. +Forbidden Value #3, Positive cqNaN, is avoided thanks to the fact that the high +16 bits of the payload value cannot be zero. + +### List pointers + +Lists are arrays of Value objects, allocated without any padding, for efficient +source code representation and traversal by the interpreter. + +They are also allocated within a dedicated virtual memory region, but using a +32-bit index value, treating the region as an array of 64-bit Value slots, so +they can occupy a total maximum of 32 GiB of memory. + +The upper 16 bits of the payload encode the length (element count) meaning that +a list can contain up to 65,535 elements. + +The empty list is canonically represented with a null payload value, i.e., zero +length, and zero offset. + +There is a separate heap object type for arbitrary-length arrays; this type is +intended only for the representation of lists in source code, and no more; it's +handled differently by the garbage collector as well and should not be used for +arbitrary heap storage. + +### Heap pointers -### Length-tagged list pointers +Other heap objects are allocated within their own virtual memory region, using +the low 32 bits of the payload for an index value as well, meaning that this +region can also span up to 32 GiB of memory. -Lists are arrays of Value objects, allocated without padding (8-byte alignment) -for efficient source code representation and traversal. Since the lowest three -bits are naturally zero, we use them as a 3-bit length information tag. +Objects in this main heap may have an alignment of greater than 8 bytes, which +could be exploited to increase the implicit multiplier of the index value, for +example to 16, to support a greater maximum heap size, such as 64 GiB. This is +not currently implemented, since heaps that large are rarely needed, and modern +CPUs are optimized for indexing into arrays of up to 8-byte elements. -A length tag value of 1 to 7 means there are exactly that many Value objects -starting at the address, while 0 means there is an array of at least eight, -terminated with a special 64-bit sentinel bit-pattern that is not otherwise -valid as a Zisp value. +(Both the x86-64 and AArch64 architectures can directly use a value as an index +into an array of 64-bit values, making the multiplication by 8 implicit, while +greater multipliers need an explicit transform of the index.) -### Interned string pointers +Of the remaining upper 16 bits of the 48-bit payload value, the highest 4 are +used to immediately encode the type of the heap object, and the remaining 12 +bits are reserved for garbage collector metadata. -Interned string (istr) objects may be unaligned, so the low bits of the pointer -are not used for any special purpose. Having a separate category for this type -of pointer also streamlines the interpreter implementation +Thus, a value can be checked against a specific heap object type by comparing +the 20 high bits to a combined constant value: The 16 highest bits indicating +that it's a heap pointer, and the 4 bits after that denoting the heap type. -### Short strings +### Immediate short strings This 48-bit range is used for strings of zero to six bytes. These are NUL terminated unless exactly six bytes, meaning that a literal NUL byte cannot appear in them, but otherwise they allow arbitrary byte values. +This type is used to represent the empty string, with a null payload, which +indicates a length of zero due to the first byte immediately being a NUL. + +NOTE: The order of bytes may depend on the endianness of the platform. + ### Small rationals We use a 49-bit space for small rational numbers, with a signed 25-bit two's complement integer numerator, and 24-bit unsigned integer denominator. -### Runes and other small values +### Runes Runes are symbols of up to 6 ASCII characters in length, used to implement extensible reader syntax. (See Zisp decoder.) They cannot contain the NUL byte, as they are NUL-terminated unless exactly six ASCII bytes in length. -NOTE: The order in which the characters of the rune are encoded depends on -endianness. On little-endian systems (i.e. most modern architectures) the -characters will be in "reverse" order, with the first character in lowest -position, so the terminating NUL has to be searched from low to high. +NOTE: The order of bytes may depend on the endianness of the platform. + +### Other small immediates The fact that runes are limited to ASCII bytes, whose MSb is unset, opens up some space for other small values to co-inhabit the same 48-bit value range. @@ -163,27 +198,27 @@ with small payload values here: There is room for over 268 Million 16-bit types ## Internal use values -The final 51-bit range is used for various internal purposes by the Zisp -interpreter, mostly related to transparent code optimization. +The final 51-bit range is used for various internal purposes by the interpreter, +mostly related to transparent code optimization. These could also be viewed as +a sort of instruction set for a tree-walking virtual machine. - 000 :: Pointer to heap object as constant + 000 :: Pointer to istr object as constant 001 :: Pointer to list values as constant - 010 :: Pointer to istr object as constant + 010 :: Pointer to heap object as constant 011 :: Immediate short string as constant - 100 :: Local variable reference by index + 100 :: Index of a local variable - 101 :: Pointer to constant function-call expression + 101 :: Index of a lexical capture - 110 :: Pointer to variable function-call expression + 110 :: Undefined - 111 :: Pointer to special-form or macro-call expression + 111 :: Pointer to optimized code expression -Forbidden Value #4, Positive Infinity, is avoided thanks to the fact that heap -pointers always have a non-zero heap-type tag. (See further above.) +### Constant values The first four categories simply mirror those of the previous 51-bit range, but mark the values as being constants rather than code to evaluate. This way, we @@ -191,37 +226,48 @@ can inject direct data pointers into the AST without needing to worry about the data being confused for code to evaluate, and without needing the `(quote ...)` wrapper anymore. -The remaining four categories could be seen as instructions for a tree-walking -virtual machine executing Zisp code. +Forbidden Value #4, Positive Infinity, is avoided thanks to the fact that istr +pointers always have non-zero length bits. -### Local reference +### Local variable index -Local variables, regardless of whether they are function parameters, variables -closed over lexically, or explicit local declarations, all use a single flat -"locals" array at run-time. References are then optimized into direct indexes -into this array. The actual index value is the lowest 16 bits, with the other -32 bits being reserved for other purposes. +Function arguments, and locally declared variables, reside in a "stack frame" +allocated for each call. Since values have a uniform 64-bit representation, +this is simply an array. Values in this range denote indexes into it. + +Only the lower 16 bits are used for the actual index value, with another 32 +being reserved for other purposes. + +### Lexical capture index + +Variables that are closed over by a lambda expression are copied into an array, +and references to them turned into indexes into this array which is provided to +the closure code when called. Values in this range denote these indexes. + +Only the lower 16 bits are used for the actual index value, with another 32 +being reserved for other purposes. ### Expression pointers -The final three pointer types are derivatives of list pointers, using three low -tag bits indicating the count of elements making up the expression. +The final pointer type is derived from the "pointer to list values" type; it +encodes a 16-bit length and 32-bit index into the list values memory region. + +The difference is that it indicates that the destination list has been altered +into an optimized form: The first element is not a Value at all anymore, but +rather a custom structure whose low 8 bits are an opcode, and high 56 bits a +payload value. -A pointer to a constant function-call expression indicates that the destination -is an array whose first element is a raw, unpacked, untagged pointer to a Zisp -function object; the remaining elements need to be evaluated to produce the -arguments to the function. As a further optimization trick, the first element -may actually be an integer up to 255, that indicates dispatch to a built-in VM -operation acting as a function. +For example, a `CALL` opcode may use 48 bits for the address of the function to +call. An opcode like `CALL_LOCAL` may indicate that the address should be read +from the local variables array instead, using an index payload. A `CALL_EVAL` +opcode may indicate that there is a 48-bit payload which is the address of yet +another code expression to evaluate to generate the address, which would result +from a code form like `((if x fn1 fn2) arg1 arg2)`. Various special forms like +if, let, lambda, etc. can have their own opcode, and one for user-defined macro +calls in case macros should be expanded on every evaluation to aid in iterative +development of macro code. -In a variable function-call expression, the first element needs evaluation to -produce a function pointer: It could be a local variable reference, one of the -expression pointer types, or else a raw pointer into a module exports table. -A special-form or macro-call expression is similar to a constant function-call -except that the arguments are passed as context-wrapped source code objects. -The first element can be an integer up to 255, dispatching to a VM built-in; -otherwise, it must be a pointer to a macro function. <!-- |