diff options
Diffstat (limited to 'doc/0/0-value.md')
| -rw-r--r-- | doc/0/0-value.md | 125 |
1 files changed, 76 insertions, 49 deletions
diff --git a/doc/0/0-value.md b/doc/0/0-value.md index 4dbd44a..2067842 100644 --- a/doc/0/0-value.md +++ b/doc/0/0-value.md @@ -2,20 +2,22 @@ <!--TOC--> -Zisp uses NaN-packing for a uniform 64-bit Zisp Value representation. +Zisp uses *NaN-packing* for a uniform 64-bit *Value* representation that covers +*Zisp double Values* and *Zisp non-double Values*. -When we speak of a 64-bit Value that is either a Zisp double or NaN-packed Zisp -value, we use the term "Value" with a capital 'V'. In other words, a Value is -either a Zisp double, or the NaN-packed representation of any other Zisp value. - -The format of a binary64 floating-point number, in big-endian notation, is: +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 either a NaN or an Infinity. +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. -For non-double packing, the remaining 53 bits are available, giving us `2^53` -values, minus the following four bit patterns which *are* doubles: +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 *** @@ -27,49 +29,73 @@ values, minus the following four bit patterns which *are* doubles: 4. Positive Infinity :: { sign = 0, exponent = MAX, fraction = 00000... } -The abbreviation "cqNaN" stands for canonical quiet NaN. +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 +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 +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 as doubles. +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 doubles in Zisp, so they also represent themselves. +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.) -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. + 2. A binary64 floating-point Infinity. (Exponent max, fraction zero.) -We split those `2^53 - 4` available values into four groups, each allowing for -`2^51 - 1` different values (51-bit values excluding zero) for Value coding: + 3. A binary64 floating-point cqNaN. (Exponent max, only MSb of fraction set.) - sign = 1, quiet = 1 :: Negative Fixnums from -1 to -2^51+1 +2. A Zisp non-double, encoded in one of the four NaN-packing domains, with a + 51-bit non-zero payload in each: - sign = 1, quiet = 0 :: Positive Fixnums from 0 to 2^51-2 + 1. A 51-bit non-zero payload in a negative non-canon qNaN - sign = 0, quiet = 1 :: Pointers and other immediates + 2. A 51-bit non-zero payload in a negative signaling NaN - sign = 0, quiet = 0 :: Tree-VM instructions + 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. Only the smallest 52-bit signed negative, `-2^51`, cannot -be represented, as it would step on Forbidden Pattern #1, Negative cqNaN. +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 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 Pattern #2, Negative Infinity. +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 and immediates +## Pointers & 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. +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 (code) @@ -107,17 +133,17 @@ thus be addressed via 32-bit indices instead of larger direct pointers. In Zisp, a list is a contiguous array of a fixed number of Values. These may reside in the main heap or the code heap; this pointer type here is used to -represent lists in the code heap specifically. +represent lists in the code heap only. -These code lists are allocated with no or little padding, and with no metadata -headers, to achieve optimal memory density and cache locality of code. As such, +These code lists are allocated with little or no padding and no metadata on the +heap, to achieve optimal memory density and cache locality of code. Therefore, we must encode the length of the list directly in the pointer itself. The exact layout of the 48-bit payload is as follows: The low 32 bits are an index into the code heap, while the higher 16 bits are divided into 8 high bits for the length, and 8 low bits for garbage collector -metadata. +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 @@ -219,11 +245,12 @@ 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 +## Tree-VM instructions -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. +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 @@ -260,8 +287,8 @@ A heap list pointer of this kind would result from a list of longer than 255 that 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 might have resulted, for example, from heavy macro use or -otherwise machine-generated source code. +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: @@ -274,20 +301,20 @@ 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 values have a uniform 64-bit representation, -this is simply an array. Values in this range denote indexes into it. +allocated for each call. Since a Value has a uniform 64-bit representation, +the stack frame is simply an array. -Only the lower 16 bits are used for the actual index value; another 32 bits are -reserved for other purposes. +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 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. +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. -Only the lower 16 bits are used for the actual index value; another 32 bits are -reserved for other purposes. +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. <!-- |