# NaN-packed Value 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, minus the following four bit patterns: *** 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 in Zisp. Infinity values may also be returned by FP operations, and we want them to also exist in Zisp, so they also represent themselves. Beyond those four bit patterns, all values with a maximum exponent (all bits set) are fair game for representing other values, so `2^53 - 4` possibilities. We split those `2^53 - 4` available values into four groups, each allowing for `2^51 - 1` different values to be encoded. (51-bit values excluding zero.) sign = 1, quiet = 1 :: Negative Fixnum from -1 to -2^51+1 sign = 1, quiet = 0 :: Positive Fixnum from 0 to 2^51-2 sign = 0, quiet = 1 :: Pointers and other immediates sign = 0, quiet = 0 :: Tree-VM instructions ## Fixnums Negative fixnums actually represent themselves, without needing to go through any transformation. Only the smallest 52-bit signed negative, `-2^51`, cannot be represented, as it would step on Forbidden Value #1, Negative cqNaN. Positive fixnums go through a bitsiwe NOT (which can be implemented as an XOR mask combining it with removal of NaN-related high bits) to avoid the all-zero payload value, which would step on Forbidden Value #2, Negative Infinity. ## Pointers and immediates 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 list values 001 :: Pointer to heap object 010 :: Pointer to istr object 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.) Pointers are actually indexes into one of two regions of virtual memory: The main heap of 32 GiB, which is addressed in 64-bit (8-byte) units; and another region of 4 GiB for `istr` objects which are byte-addressed. Both regions can thus be addressed via 32-bit index/offset values. ### List pointers In Zisp, a list is a contiguous array of a fixed number of Value elements. For a maximally dense representation of code, lists of up to 255 Value elements are allocated in blocks without any padding or metadata headers, using some of the bits of the NaN-packed pointer to immediately encode the length. The lower 32 bits of the payload are an index into the main heap region, while the higher 16 bits are divided into 8 high bits for the length and 8 low bits for garbage collector 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 don't needlessly trigger the code branch that handles list pointers. Lists of arbitrary length can be allocated as regular heap objects of the array type; the difference is invisible when using the generic list API. Forbidden Value #3, Positive cqNaN, is avoided thanks to the fact that the high 8 bits of the payload, encoding the length, cannot be zero. ### Heap pointers Regular heap objects are represented by this pointer type, which also 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 that a full 64-bit NaN-packed value can be checked against a heap type by comparing the highest 24 bits to a combined constant: the highest 16 bits indicating that it's a regular heap pointer, and 8 bits encoding the specific heap type being checked against. ### Interned strings 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 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. ### 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. 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). ## Internal use values 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 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 values 101 :: Pointer to opcodes in heap object 110 :: Local variable reference index 111 :: Lexical capture reference index ### 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 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. Forbidden Value #4, Positive Infinity, is avoided thanks to the fact that list pointers always have non-zero length bits. ### Opcode array pointers These pointer types are derived from regular list pointers and heap pointers by flipping 2 bits. In the case of a heap pointer, the heap type will be an array of values, i.e., a list of length greater than 255; this should be exceedingly rare, given that code expressions almost never have such length, but we support it just in case. Either way, what this means is that the list has been pre-evaluated to ensure it's a well-formed code expression, and the first element has been transformed into something other than a Value: Its new layout as a 64-bit structure is that the low 8 bits are an opcode, and the high 56 bits a payload value. For example, a `CALL` opcode may use 48 bits for the direct memory address of a function to call. An opcode like `CALL_LOCAL` may indicate that a heap index should be read from the local variables array (see below) to locate a function or closure in the main heap. A `CALL_EVAL` opcode may indicate that the payload contains a 32-bit heap index to another expression to evaluate to generate the address of a function to call; this might result from a code form such as: `((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 help during iterative development of macro code. ### Local variable index 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; another 32 bits are 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; another 32 bits are reserved for other purposes.