# NaN-packed Value Zisp uses *NaN-packing* for a uniform 64-bit *Value* representation that covers *Zisp double Values* and *Zisp non-double Values*. Let's start by looking at the IEEE 754 binary64 floating-point number format, using big-endian notation: { sign: 1 bit, exponent: 11 bits, fraction: 52 bits } When the 11 exponent bits are all set, it's a NaN or Infinity. Otherwise, it's a finite, which covers normals, subnormals, and positive and negative zero. All binary64 floating-point finite numbers (those *not* having all 11 exponent bits set) map directly to themselves as a Zisp double in our Value domain. To represent a Zisp non-double, we must set all 11 exponent bits, leaving us with `2^53` possible bit patterns, minus four: *** FORBIDDEN BIT-PATTERNS *** 1. Negative cqNaN :: { sign = 1, exponent = MAX, fraction = 10000... } 2. Negative Infinity :: { sign = 1, exponent = MAX, fraction = 00000... } 3. Positive cqNaN :: { sign = 0, exponent = MAX, fraction = 10000... } 4. Positive Infinity :: { sign = 0, exponent = MAX, fraction = 00000... } The abbreviation *cqNaN* stands for canonical quiet NaN. The MSb of the fraction is also called the `is_quiet` flag, because it marks a NaN as being *quiet* rather than signaling. The rest of the fraction being all zero makes it the *canonical* quiet NaN for the given sign value. The positive and negative cqNaN are the only NaN values that can actually be returned by FP operations. This is convenient, because it means we can simply use them to represent themselves as Zisp doubles. Infinity values may also be returned by FP operations, and we want them to also exist as Zisp doubles, so they also represent themselves. Beyond those four, all bit patterns with a maximum exponent (11 bits set) are fair game for representing Zisp non-doubles, giving us `2^53-4` bit patterns. We split those into four categories of `2^51-1` bit patterns, so we have four 51-bit value ranges, each excluding zero, to encode Zisp non-doubles. To summarize, a 64-bit value representing a Zisp Value is one of: 1. A Zisp double, represented directly as: 1. A binary64 floating-point finite. (Exponent sub-maximum.) 2. A binary64 floating-point Infinity. (Exponent max, fraction zero.) 3. A binary64 floating-point cqNaN. (Exponent max, only MSb of fraction set.) 2. A Zisp non-double, encoded in one of the four NaN-packing domains, with a 51-bit non-zero payload in each: 1. A 51-bit non-zero payload in a negative non-canon qNaN 2. A 51-bit non-zero payload in a negative signaling NaN 3. A 51-bit non-zero payload in a positive non-canon qNaN 4. A 51-bit non-zero payload in a positive signaling NaN Those four NaN-packing domains are used as follows: sign = 1, exp = MAX, quiet = 1 :: Negative Fixnums from -1 to -2^51+1 sign = 1, exp = MAX, quiet = 0 :: Positive Fixnums from 0 to 2^51-2 sign = 0, exp = MAX, quiet = 1 :: Pointers and other immediates sign = 0, exp = MAX, quiet = 0 :: Tree-VM instructions ## Fixnums Negative fixnums actually represent themselves, without needing to go through any transformation, since the highest 13 bits are all set anyway. Only the smallest 52-bit negative, `-2^51`, cannot be represented, as it steps on Forbidden Pattern #1, Negative cqNaN. Positive fixnums go through a bitwise NOT (which can be implemented as an XOR mask combining it with removal of NaN-related high bits) to avoid the zero payload, which would step on Forbidden Pattern #2, Negative Infinity. ## Pointers & immediates This region of 51-bit non-zero values is divided as follows, based on the three highest bits, providing a payload value of 48 bits for each. 000 :: Pointer to list 001 :: Pointer to heap 010 :: Pointer to istr 011 :: Immediate short string 100 :: Immediate small rational (sign bit 0) 101 :: Immediate small rational (sign bit 1) 110 :: Undefined 111 :: Immediate types further subdivided as follows: 0....... 0....... 0....... (etc.) :: Rune 1....... :: 128 40-bit types 0....... 1....... :: 16384 32-bit types 0....... 0....... 1....... :: 2097152 24-bit types (etc.) Forbidden Pattern #3, Positive cqNaN, is avoided thanks to the fact that some bits of a list pointer are always set; see below. Zisp splits the native program heap provided by the platform into three regions of virtual memory: The list heap of 32 GiB, addressed in 64-bit (8-byte) units; the main heap of 32 GiB, also addressed in 64-bit units; and the 4 GiB heap for `istr` objects (interned strings) which is addressed in bytes. Each region can thus be addressed via 32-bit indices instead of larger direct pointers. ### List pointers In Zisp, a list is a contiguous array of a fixed number of Values. To improve memory density and cache locality, especially for the interpreter, lists of up to 255 elements are allocated in tight blocks with little or no padding and no metadata headers on the heap. Their length is therefore encoded directly with an 8-bit metadata field within the NaN-packed pointer. The exact layout of the 48-bit payload is as follows: The low 32 bits are an index into the list heap, while the higher 16 bits are divided into 8 high bits for the length, and 8 low bits for garbage collector or other internal metadata. The length bits cannot be zero. The empty list is represented by a different bit pattern to provide a minor benefit during garbage collection: Zero-length lists can't needlessly trigger the code branch that handles list pointers. Note that "list pointer" and "list heap" are slightly misleading terms, since arbitrary-length lists can be allocated on the main heap as Array objects with element type Value. In this case, they are represented by a main heap pointer, and the generic list API hides the difference. ### Heap pointers Regular heap objects are represented by this index type, which uses a 32-bit index into the main heap, in the lower portion of the 48-bit payload. Of the 16 high bits of the payload, the upper 8 are used to immediately encode the type of the heap object, and the remaining 8 are used for garbage collector metadata. This means our 64-bit Values can be checked against heap types by comparing the 24 high bits to a combined constant: the 16 high bits that indicate it's a main heap index, plus 8 more bits encoding a specific heap type. ### String pointers An `istr` is a string of up to 255 arbitrary bytes, that is typically interned, fulfilling a similar purpose to symbols in Lisp and Scheme. If uninterned, we could consider the 'i' to mean *intermediate* length string instead. Of the 48-bit payload value, the lower 32 bits are an offset into a dedicated virtual memory region for this type only, bounding total memory use to 4 GiB, which should be more than enough. The higher 16 bits of the payload are divided in two halves. The upper 8 bits directly encode the length, which cannot be zero; the lower 8 bits are used for garbage collection metadata. The empty string is represented as a *short string* instead; see below. ### Short strings This 48-bit range is used for strings of zero to six bytes in length. They are NUL-terminated unless exactly six bytes, meaning that a literal NUL byte cannot appear in them, but otherwise they allow arbitrary byte values. When a NUL-terminator appears, the remaining bytes *must* be NUL as well; this ensures that short strings can be tested for equality by using a simple 64-bit value comparison. One could say that short strings are therefore *implicitly interned*. The empty string is represented with an all-NUL payload. If a string of six or fewer bytes is encountered that happens to contain a NUL, we fall back to the `istr` representation, making the limitation invisible to application code. NOTE: The order of bytes in the 48-bit payload of a short string immediate 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 & others A rune is a marker of up to 6 ASCII characters in length, used to implement extensible reader syntax. (See Zisp decoder.) Runes cannot contain the NUL byte, as they are NUL-terminated unless exactly six ASCII bytes in length. NOTE: The order of bytes may depend on the endianness of the platform. 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. We divide this space into increasingly many potential types, with smaller and smaller payloads, where the highest byte with a non-zero MSb determines which size category we're in: If the highest byte has its MSb set, then the other seven bits are a type tag, and each type has a 40-bit payload; if the second highest byte has its MSb set, then the 14 non-MSb bits of the two high bytes define the type, and each has a 32-bit payload; and so on. Unicode code points need 21 bits, so we use a 24-bit type for the Character type. Miscellaneous Values like True, False, EOF, etc. are placed in an 8-bit type, since there will never be that many of them; this is also where the empty list bit pattern is located. A virtually unlimited number of user-defined enum types can fit into the types with small payload values here: There is room for over 268 Million 16-bit types (28-bit type tag) and over 34 Billion 8-bit types (35-bit type tag). ## Tree-VM instructions The final 51-bit non-zero range is used to represent something similar to a VM instruction set for what is still essentially a tree-walking interpreter. This strategy allows source code to be transformed into this optimized form through almost purely in-place mutations of the original source code tree. 000 :: Pointer to list as constant 001 :: Pointer to heap as constant 010 :: Pointer to istr as constant 011 :: Short string as constant 100 :: Pointer to opcodes in list heap 101 :: Pointer to opcodes in main heap 110 :: Local variable reference index 111 :: Lexical capture reference index Forbidden Pattern #4, Positive Infinity, is avoided thanks to the fact that pointers to lists always have non-zero length bits. ### Constant Values The first four categories simply mirror those of the previous 51-bit range, but mark the Value as being a constant rather than code to evaluate. This way, we can inject constant data into the AST without needing to worry about it being confused for code to evaluate, and without needing the `(quote ...)` wrapper. ### Opcode array pointers These types are derived from the regular list pointers (length <= 255) and main heap Value Array pointers (length > 255) by flipping 2 bits. A main heap pointer of this kind can only result from a list of more than 255 elements which represents actual code to execute. (Had it been a quoted list, it would have become a "pointer to heap as constant" instead.) This will be exceedingly rare, given that regular code expressions almost never have such length, but we must support it; it may result, for instance, from heavy macro use or otherwise machine-generated source code. Either way, what this means is that a list has been analyzed to ensure it's a well-formed code expression, and transformed into an optimized form: The first element is transformed into something other than a Value: It is now a 64-bit structure whose low 8 bits are an opcode, and the high 56 bits a payload value. Other elements may also have been transformed into VM instructions, but only of the above listed Value types. ### Local variable index Function arguments, and locally declared variables, reside in a "stack frame" allocated for each call. Since a Value has a uniform 64-bit representation, the stack frame is simply an array. The low 16 bits of the payload are an index into the stack array; the other 32 bits are reserved for other purposes. ### Lexical capture index Variables that are closed over by a lambda expression have their Value at the point of lambda creation copied into an array. References to them are turned into indexes into this array, which is provided to the closure when called. The low 16 bits of the payload are an index into the array of lexical captures; the other 32 bits are reserved for other purposes.