diff options
Diffstat (limited to 'doc/0/0-value.md')
| -rw-r--r-- | doc/0/0-value.md | 209 |
1 files changed, 96 insertions, 113 deletions
diff --git a/doc/0/0-value.md b/doc/0/0-value.md index 61d01d9..2ee424b 100644 --- a/doc/0/0-value.md +++ b/doc/0/0-value.md @@ -3,7 +3,7 @@ <!--TOC--> Zisp uses *NaN-packing* for a uniform 64-bit *Value* representation that covers -*Zisp double Values* and *Zisp non-double Values*. +*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: @@ -14,9 +14,9 @@ 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. +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 +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 *** @@ -37,75 +37,63 @@ 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. +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. +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 +fair game for representing Zisp non-Doubles, giving us `2^53-4` bit patterns. +We split these into four categories of `2^51-1` bit patterns, so we have four +51-bit payload value ranges, **each excluding zero,** to encode non-Doubles. + +To summarize, a 64-bit value representing a Zisp Value is either one of: + + * A Zisp Double, represented directly as: + \ + |- binary64 floating-point finite + | + |- binary64 floating-point infinity + | + \- binary64 floating-point cqNaN + + * A Zisp non-Double, encoded in one of the four NaN-packing domains: + \ + |- Negative non-canon qNaN :: Negative Fixnums from -1 to -2^51+1 + | + |- Negative signaling NaN :: Positive Fixnums from 0 to 2^51-2 + | + |- Positive non-canon qNaN :: Pointers, and other immediates + | + \- Positive signaling NaN :: Optimization tricks ## Fixnums -Negative fixnums actually represent themselves, without needing to go through +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 +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 +## Pointers, etc. 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 + 000 :: List pointer with length tag - 001 :: Pointer to heap + 001 :: Heap pointer with type tag - 010 :: Pointer to istr + 010 :: Istr pointer with length tag - 011 :: Immediate short string + 011 :: Short string immediate - 100 :: Immediate small rational + 100 :: Small rational immediate 101 :: Undefined @@ -128,19 +116,8 @@ bits of a list pointer are always set; see below. Zisp divides platform-provided heap memory into regions that are addressed via 32-bit indexes rather than direct pointers. Different pointer types may refer -to different regions. For instance, a list pointer and a regular heap pointer -may have the same index value, which does not mean that they point to the same -real memory address. They may also be addressing their respective region with -different unit sizes. For instance, `istr` (interned string) pointers may use -byte-addressing, meaning the 32-bit index limits the `istr` heap to 4 GiB only, -while list pointers use 64-bit (8-byte) addressing, allowing for a 32 GiB heap. - -Note: The separation of heaps is a possibility, not a guarantee. In practice, -the various 32-bit indexes may share a single value domain, in which case list -pointers, heap pointers, etc. would never have equal 32-bit index values; they -may or may not, depending on current implementation details. The unit size of -each type of 32-bit index is also not guaranteed, but is at least 8 bytes for -list pointers, since a list must contain at least one 64-bit Zisp Value. +to different regions, and the index may have different addressing resolutions, +such as 8-byte units, 16-byte units, and so on. ### List pointers @@ -160,28 +137,22 @@ 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 a generic list API may hide the difference. +Lists that are longer than 255 elements are represented through regular heap +pointers to Array objects. ### Heap pointers -Regular heap objects are represented by this pointer type, which uses a 32-bit -heap index in the lower portion of the 48-bit payload. +Various heap objects are represented by this pointer type, which uses a 32-bit +index in the lower portion of the 48-bit payload. The interpretation of the +index value is dependent on the heap type. 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 internal metadata such as for garbage collection. 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. - -Different types may reside in different heaps, meaning the 32-bit index values -of different heap types may or may not share value domains. The index value of -two heap pointers, of different types, being equal, is neither a guarantee that -they share a memory location, nor is it ruled out. +24 high bits to a combined constant: the 16 high bits that indicate it's a heap +pointer, plus 8 more bits encoding the heap object type. ### String pointers @@ -213,9 +184,6 @@ 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 48-bit space for small rational numbers, with a 32-bit signed two's @@ -225,7 +193,7 @@ denominator in the high 16 bits of the payload. ### 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 +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. @@ -250,60 +218,66 @@ 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 +## Code optimization -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. +The final 51-bit non-zero range is used for optimization tricks, with two-fold +meaning depending on context: Before and after the full optimization pass. - 000 :: Pointer to list as constant +Before, the meanings are as follows: - 001 :: Pointer to heap as constant + 000 :: Quoted list pointer - 010 :: Pointer to istr as constant + 001 :: Quoted heap pointer - 011 :: Immediate short string as constant + 010 :: Quoted istr pointer - 100 :: Pointer to opcodes in list heap + 011 :: Quoted short string - 101 :: Pointer to opcodes in main heap + ... :: Undefined - 110 :: Local variable reference index +This allows the Zisp Decoder to compress quoted data forms, by simply flipping +one bit on the raw data, so the `(#QUOTE ...)` wrapper can be discarded, which +maximizes the memory density and locality of interpreted code. - 111 :: Lexical capture reference index +When the optimizer encounters such quoted data, it acknowledges the quoting and +simply flips back one bit; other data forms are optimized as code. -Forbidden Pattern #4, Positive Infinity, is avoided thanks to the fact that -pointers to lists always have non-zero length bits. +After the optimization pass, the meanings are as follows: -### Constant Values + 000 :: Pointer to list code form -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. + 001 :: Pointer to heap code form -### Opcode array pointers + 010 :: Local variable reference -These types are derived from the regular list pointers (length <= 255) and main -heap Value Array pointers (length > 255) by flipping 2 bits. + 011 :: Lexical capture reference -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. + 100 :: Module binding reference + + ... :: Undefined + +Forbidden Pattern #4, Positive Infinity, is avoided thanks to the fact that +pointers to lists always have non-zero length bits. -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: +### Code pointers + +These two pointer types are derived from regular length-tagged list pointers, +and heap pointers to Array objects, by flipping one bit. + +This kind of Array pointer can only result from a source code list of over 255 +elements, which represents actual code to execute and not quoted data, which is +exceedingly rare. We must support it nevertheless, as it may result from heavy +macro use, or other such automated source code generation. + +Either way, what these pointers represent is a code expression that has been +analyzed to ensure that it's well-formed, and turned 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. +value. Other elements may also have been transformed, but only into one of the +above listed Value types. -### Local variable index +### Local variables Function arguments, and locally declared variables, reside in a "stack frame" allocated for each call. Since a Value has a uniform 64-bit representation, @@ -312,7 +286,7 @@ stack frames are simply Value arrays. 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 +### Lexical captures 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 @@ -321,6 +295,15 @@ 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. +### Module bindings + +References to public bindings of the containing module or of linked modules are +represented by this type. + +The low 32 bits are the heap index of a "box" object that provides a layer of +indirection, so changes to the binding take effect dynamically. The other 16 +bits are reserved for other purposes. + <!-- ;; Local Variables: |