Yet another NaN-packing design change.

2 files changed, 123 insertions, 118 deletions

diff --git a/doc/0/0-value.md b/doc/0/0-value.md
index 57e593d..b5a702e 100644
--- a/doc/0/0-value.md
+++ b/doc/0/0-value.md
@@ -46,7 +46,7 @@ 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 immediates
+    sign = 0, quiet = 1 :: Pointers and other immediates
 
     sign = 0, quiet = 0 :: Tree-VM instructions
 
@@ -67,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 istr object
+    000   :: Pointer to list values
 
-    001   :: Pointer to list values
+    001   :: Pointer to heap object
 
-    010   :: Pointer to heap object
+    010   :: Pointer to istr object
 
     011   :: Immediate short string
 
@@ -93,82 +93,83 @@ bits, providing a payload value of 48 bits for each.
 
              (etc.)
 
-### Interned strings
-
-An `istr` is an interned string of up to 255 arbitrary bytes, fulfilling a
-similar purpose to symbols in Lisp and Scheme.
-
-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 is more than enough for interned strings.
-
-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 an immediate short string; see below.
-
-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.
+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
 
-Lists are arrays of Value objects, allocated without any padding, for efficient
-source code representation and traversal by the interpreter.
-
-They are allocated within a dedicated virtual memory region as well, but use a
-32-bit index value that treats the region as an array of 64-bit slots, meaning
-they can occupy a total maximum of 32 GiB of memory.
+In Zisp, a list is a contiguous array of a fixed number of Value elements.
 
-The higher 16 bits of the 48-bit payload are once again divided into length and
-garbage collector metadata.  This limits element count to 255, but a fall-back
-heap type is used to make this limitation invisible to programs.
+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 empty list is canonically represented with a null payload value, i.e., zero
-length, cleared GC metadata bits, and zero index value.
+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.
 
-Lists of this type can double as generic *tuple* types since they are packed in
-a maximally efficient way.  For instance, a *box* type of a single shared and
-mutable Value, a *pair* type of exactly two Values, and a variety of *struct*
-types of fixed Value counts could be implemented simply by this type.
+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.
 
-### Heap 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.
 
-Various objects are allocated within a generic heap region of virtual memory,
-using the low 32 bits of the payload as an index value as well, meaning this
-region can occupy another 32 GiB of memory.
+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.
 
-Objects in the main heap may have an alignment greater than 8 bytes.  We could
-exploit this to support larger heaps, treating the heap as, for instance, slots
-of 16 bytes (128 bits) or more.  However, this is not implemented, since heaps
-that large are rarely needed, and modern CPUs are optimized for indexing 64-bit
-array elements.
+### Heap pointers
 
-(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.)
+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 remaining upper 16 bits of the 48-bit payload, the upper 8 are used to
-immediately encode the type of the heap object, and the remaining 8 bits are
-once again used for garbage collector metadata.
+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.
 
-### Immediate short strings
+### 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;
-otherwise the strings could not be tested for equality as easily.
+
+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.
 
-NOTE: The order of bytes may depend on the endianness of the platform.
+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
 
@@ -177,8 +178,8 @@ complement integer numerator, and 24-bit unsigned integer denominator.
 
 ### 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
+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.
@@ -197,7 +198,8 @@ 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.
+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
@@ -210,41 +212,66 @@ 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 istr object as constant
+    000   :: Pointer to list as constant
 
-    001   :: Pointer to list values as constant
+    001   :: Pointer to heap as constant
 
-    010   :: Pointer to heap object as constant
+    010   :: Pointer to istr as constant
 
-    011   :: Immediate short string as constant
+    011   :: Short string as constant
 
-    100   :: Index of a local variable
+    100   :: Pointer to opcodes in list values
 
-    101   :: Index of a lexical capture
+    101   :: Pointer to opcodes in heap object
 
-    110   :: Undefined
+    110   :: Local variable reference index
 
-    111   :: Pointer to optimized code expression
+    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 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.
+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 istr
+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, with another 32
-being reserved for other purposes.
+Only the lower 16 bits are used for the actual index value; another 32 bits are
+reserved for other purposes.
 
 ### Lexical capture index
 
@@ -252,30 +279,8 @@ 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 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.
-
-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.
-
-
+Only the lower 16 bits are used for the actual index value; another 32 bits are
+reserved for other purposes.
 
 
 <!--
diff --git a/doc/0/1-parse.md b/doc/0/1-parse.md
index 54b1dd4..91407da 100644
--- a/doc/0/1-parse.md
+++ b/doc/0/1-parse.md
@@ -6,9 +6,9 @@ Zisp s-expressions represent an extremely minimal set of data types; only that
 which is necessary to strategically construct more complex values:
 
     +---------+--------+--------+
-    | String  | Rune   | List   |
+    | String  | List   | Rune   |
     +---------+--------+--------+
-    | foobar  | #name  | (...)  |
+    | foobar  | (...)  | #name  |
     +---------+--------+--------+
 
 The parser recognizes various *syntax sugar* which abbreviates verbose syntax,
@@ -199,6 +199,26 @@ contain NUL bytes, in which case this optimization isn't used.)  Longer strings
 may be *interned* which is a feature explained further below.  Otherwise, each
 string is allocated separately, and represented by its unique memory address.
 
+### List
+
+A list is a sequence of values with a fixed length.
+
+A unique, contiguous array of values is allocated in program memory for each
+list of non-zero length, and the list as a value is then represented by the
+memory address of the array.  The empty list is represented by a distinct
+canonical bit pattern.
+
+Lists are valid as a datum if one of the following holds true:
+
+* The list encodes a quoted string, datum label, or shebang line.
+
+* All values in the list are a valid datum, or it is empty.
+
+Further, a structure of nested list values may not contain cyclic references
+back up in the structure (which would make the above definition diverge into
+infinity).  Such cycles must be broken up with datum labels, or else the list
+cannot be considered a datum, since it cannot be printed or parsed.
+
 ### Rune
 
 A rune is represented by an ASCII character sequence of 1 to 6 bytes, that must
@@ -219,26 +239,6 @@ default decoder settings and documented explicitly as such.
 
 Runes are always stored directly in a CPU word; never by memory address.
 
-### List
-
-A list is a sequence of values with a fixed length.
-
-A unique, contiguous array of values is allocated in program memory for each
-list of non-zero length, and the list as a value is then represented by the
-memory address of the array.  The empty list is represented by a specific
-canonical bit pattern.
-
-Lists are valid as a datum if one of the following holds true:
-
-* The list encodes a quoted string, datum label, or shebang line.
-
-* All values in the list are a valid datum, or it is empty.
-
-Further, a structure of nested list values may not contain cyclic references
-back up in the structure (which would make the above definition diverge into
-infinity).  Such cycles must be broken up with datum labels, or else the list
-cannot be considered a datum, since it cannot be printed or parsed.
-
 
 ## String interning