Design changes preparing for interpreter.

2 files changed, 184 insertions, 123 deletions

diff --git a/doc/0/0-value.md b/doc/0/0-value.md
index 3485b00..c2810d8 100644
--- a/doc/0/0-value.md
+++ b/doc/0/0-value.md
@@ -1,12 +1,16 @@
-# NaN-packed Value representation
+# NaN-packed Value
 
-The format of a binary64 floating-point number, in big-endian notation:
+<!--TOC-->
+
+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
+For value packing, the remaining 53 bits are available, giving us `2^53` values,
 minus the following four bit patterns:
 
     *** FORBIDDEN BIT-PATTERNS ***
@@ -42,9 +46,9 @@ 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 various immediates
+    sign = 0, quiet = 1 :: Pointers and immediates
 
-    sign = 0, quiet = 0 :: Internal use by interpreter
+    sign = 0, quiet = 0 :: Tree-VM instructions
 
 
 ## Fixnums
@@ -63,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 heap object  (type-tagged)
+    000   :: Pointer to istr object
 
-    001   :: Pointer to list values  (length-tagged)
+    001   :: Pointer to list values
 
-    010   :: Pointer to istr object
+    010   :: Pointer to heap object
 
     011   :: Immediate short string
 
@@ -89,58 +93,89 @@ bits, providing a payload value of 48 bits for each.
 
              (etc.)
 
-Forbidden Value #3, Positive cqNaN, is avoided by not using 0 as a valid type
-tag value for heap pointers.
+### Interned strings
 
-### Type-tagged heap pointers
+An istr is an interned string of up to 65,535 arbitrary bytes.  These are very
+similar to symbols in Lisp and Scheme.  Of the 48-bit payload value, the lower
+32 bits are an offset into a virtual memory region dedicated to this type, and
+the higher 16 bits encode the length of the string, which cannot be zero.  The
+empty string has a different representation; see immediate short strings.
 
-Regular heap objects are allocated with 16-byte alignment, meaning the lowest
-four bits are naturally zero.  We exploit this by shifting down the address by
-four bits, making room for more tag bits immediately following the 16 high bits
-that mark the value as a heap pointer.
+Using a 32-bit offset value means that interned strings can occupy a total
+maximum of 4 GiB of memory, which should be comfortably sufficient.
 
-Thus, a value can be checked against a specific heap object type by comparing
-the 20 high bits to a combined constant value: the 16 highest bits indicating
-that it's a heap pointer, and the 4 bits after that denoting the heap type.
+Forbidden Value #3, Positive cqNaN, is avoided thanks to the fact that the high
+16 bits of the payload value cannot be zero.
+
+### List pointers
+
+Lists are arrays of Value objects, allocated without any padding, for efficient
+source code representation and traversal by the interpreter.
+
+They are also allocated within a dedicated virtual memory region, but using a
+32-bit index value, treating the region as an array of 64-bit Value slots, so
+they can occupy a total maximum of 32 GiB of memory.
+
+The upper 16 bits of the payload encode the length (element count) meaning that
+a list can contain up to 65,535 elements.
+
+The empty list is canonically represented with a null payload value, i.e., zero
+length, and zero offset.
+
+There is a separate heap object type for arbitrary-length arrays; this type is
+intended only for the representation of lists in source code, and no more; it's
+handled differently by the garbage collector as well and should not be used for
+arbitrary heap storage.
+
+### Heap pointers
 
-### Length-tagged list pointers
+Other heap objects are allocated within their own virtual memory region, using
+the low 32 bits of the payload for an index value as well, meaning that this
+region can also span up to 32 GiB of memory.
 
-Lists are arrays of Value objects, allocated without padding (8-byte alignment)
-for efficient source code representation and traversal.  Since the lowest three
-bits are naturally zero, we use them as a 3-bit length information tag.
+Objects in this main heap may have an alignment of greater than 8 bytes, which
+could be exploited to increase the implicit multiplier of the index value, for
+example to 16, to support a greater maximum heap size, such as 64 GiB.  This is
+not currently implemented, since heaps that large are rarely needed, and modern
+CPUs are optimized for indexing into arrays of up to 8-byte elements.
 
-A length tag value of 1 to 7 means there are exactly that many Value objects
-starting at the address, while 0 means there is an array of at least eight,
-terminated with a special 64-bit sentinel bit-pattern that is not otherwise
-valid as a Zisp value.
+(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.)
 
-### Interned string pointers
+Of the remaining upper 16 bits of the 48-bit payload value, the highest 4 are
+used to immediately encode the type of the heap object, and the remaining 12
+bits are reserved for garbage collector metadata.
 
-Interned string (istr) objects may be unaligned, so the low bits of the pointer
-are not used for any special purpose.  Having a separate category for this type
-of pointer also streamlines the interpreter implementation
+Thus, a value can be checked against a specific heap object type by comparing
+the 20 high bits to a combined constant value: The 16 highest bits indicating
+that it's a heap pointer, and the 4 bits after that denoting the heap type.
 
-### Short strings
+### Immediate short strings
 
 This 48-bit range is used for strings of zero to six bytes.  These are NUL
 terminated unless exactly six bytes, meaning that a literal NUL byte cannot
 appear in them, but otherwise they allow arbitrary byte values.
 
+This type is used to represent the empty string, with a null payload, which
+indicates a length of zero due to the first byte immediately being a NUL.
+
+NOTE: The order of bytes 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 and other small values
+### 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
 byte, as they are NUL-terminated unless exactly six ASCII bytes in length.
 
-NOTE: The order in which the characters of the rune are encoded depends on
-endianness.  On little-endian systems (i.e. most modern architectures) the
-characters will be in "reverse" order, with the first character in lowest
-position, so the terminating NUL has to be searched from low to high.
+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.
@@ -163,27 +198,27 @@ with small payload values here: There is room for over 268 Million 16-bit types
 
 ## Internal use values
 
-The final 51-bit range is used for various internal purposes by the Zisp
-interpreter, mostly related to transparent code optimization.
+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 heap object as constant
+    000   :: Pointer to istr object as constant
 
     001   :: Pointer to list values as constant
 
-    010   :: Pointer to istr object as constant
+    010   :: Pointer to heap object as constant
 
     011   :: Immediate short string as constant
 
-    100   :: Local variable reference by index
+    100   :: Index of a local variable
 
-    101   :: Pointer to constant function-call expression
+    101   :: Index of a lexical capture
 
-    110   :: Pointer to variable function-call expression
+    110   :: Undefined
 
-    111   :: Pointer to special-form or macro-call expression
+    111   :: Pointer to optimized code expression
 
-Forbidden Value #4, Positive Infinity, is avoided thanks to the fact that heap
-pointers always have a non-zero heap-type tag.  (See further above.)
+### 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
@@ -191,37 +226,48 @@ 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.
 
-The remaining four categories could be seen as instructions for a tree-walking
-virtual machine executing Zisp code.
+Forbidden Value #4, Positive Infinity, is avoided thanks to the fact that istr
+pointers always have non-zero length bits.
 
-### Local reference
+### Local variable index
 
-Local variables, regardless of whether they are function parameters, variables
-closed over lexically, or explicit local declarations, all use a single flat
-"locals" array at run-time.  References are then optimized into direct indexes
-into this array.  The actual index value is the lowest 16 bits, with the other
-32 bits being reserved for other purposes.
+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.
+
+### 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, with another 32
+being reserved for other purposes.
 
 ### Expression pointers
 
-The final three pointer types are derivatives of list pointers, using three low
-tag bits indicating the count of elements making up the expression.
+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.
 
-A pointer to a constant function-call expression indicates that the destination
-is an array whose first element is a raw, unpacked, untagged pointer to a Zisp
-function object; the remaining elements need to be evaluated to produce the
-arguments to the function.  As a further optimization trick, the first element
-may actually be an integer up to 255, that indicates dispatch to a built-in VM
-operation acting as a function.
+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.
 
-In a variable function-call expression, the first element needs evaluation to
-produce a function pointer: It could be a local variable reference, one of the
-expression pointer types, or else a raw pointer into a module exports table.
 
-A special-form or macro-call expression is similar to a constant function-call
-except that the arguments are passed as context-wrapped source code objects.
-The first element can be an integer up to 255, dispatching to a VM built-in;
-otherwise, it must be a pointer to a macro function.
 
 
 <!--
diff --git a/doc/0/1-parse.md b/doc/0/1-parse.md
index 32ffa2f..b8f1c2d 100644
--- a/doc/0/1-parse.md
+++ b/doc/0/1-parse.md
@@ -5,11 +5,11 @@
 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     | Nil  |
-    +---------+--------+----------+------+
-    | foobar  | #name  | (X ...)  | ()   |
-    +---------+--------+----------+------+
+    +---------+--------+--------+
+    | String  | Rune   | List   |
+    +---------+--------+--------+
+    | foobar  | #name  | (...)  |
+    +---------+--------+--------+
 
 The parser recognizes various *syntax sugar* which abbreviates verbose syntax,
 and may result in special data structures (typically, a list with a rune in its
@@ -18,6 +18,8 @@ into a rich set of value types.
 
 More details about syntax sugar, and the decoder, are explained later.
 
+For the grammar specification, see [grammar](grammar/).
+
 
 ## Character Encoding
 
@@ -160,44 +162,42 @@ is only a *datum* if it adheres to additional constraints as explained below.
 ### String
 
 Strings can appear *bare* or be quoted in various ways.  A quoted string is in
-fact parsed into a list value with a rune in the first position to identify the
+fact encoded as a list datum with a rune in the first position to identify the
 quotation variant that was parsed, and the string value in the second position;
-or, in case of at-quoted strings, a special construct we will look at later.
-
-    +-----------+-------------------------------+
-    | Syntax    | Parse output                  |
-    +-----------+-------------------------------+
-    | |bytes|   | (#PQSTR <STRING>)             |
-    +-----------+-------------------------------+
-    | "bytes"   | (#DQSTR <STRING>)             |
-    +-----------+-------------------------------+
-    | @_bytes_  | (#ATSTR <SENTINEL> <STRING>)  |
-    +-----------+-------------------------------+
-
-The visual token `<STRING>` denotes the actual string, as a Zisp value, in the
-second position of the list.  The visual token `<SENTINEL>` stands for a Zisp
-integer value between 0 and 254.
-
-These external representations of strings will be explained in more detail
-further below, including backslash escape sequences allowed within, and how
-exactly at-quoted strings work.
+or, in case of at-quoted strings with a sentinel, a special construct we will
+look at later.
+
+Bare strings can only contain a limited set of ASCII characters.  For details,
+see the [grammar](grammar/).
+
+    +---------------+------------------------+
+    | External      | Internal               |
+    +---------------+------------------------+
+    | bytes         | <STRING>               |
+    +---------------+------------------------+
+    | |bytes|       | (#PQSTR <STRING>)      |
+    +---------------+------------------------+
+    | "bytes"       | (#DQSTR <STRING>)      |
+    +---------------+------------------------+
+    | @<N>bytes     | (#ATSTR <STRING>)      |
+    +---------------+------------------------+
+    | @<S>bytes<S>  | (#ATSTR <S> <STRING>)  |
+    +---------------+------------------------+
+
+The visual token `<STRING>` denotes the actual string, as a Zisp value.  The
+meaning of the visual tokens `<N>` and `<S>` will be explained later, in the
+section about at-quoted strings.  Other details, including backslash escapes
+allowed in pipe-quoted and double-quoted strings, are also explained later.
 
 Strings have a fixed length, counted in bytes.  Each byte can have any value,
 including zero (ASCII NUL).  The parser reads bytes, not Unicode characters; a
 string may contain UTF-8 byte sequences, but these are not tested for validity.
 
-A string that is up to 255 bytes long is automatically *interned*, meaning any
-occurrence of the same string -- equal in length and containing the same byte
-values -- ends up being represented by the same bit-pattern; either a memory
-address, or an immediate representation within a CPU word for short strings.
-The quotation method is inconsequential to this process; for example, while
-`|foo bar|` and `"foo bar"` will parse into different list values, the actual
-string they hold a reference to will be the same one in program memory.  This
-behavior is however configurable and can be disabled entirely for cases where
-large numbers of arbitrary binary strings are being parsed.
-
-Strings of length greater than 255 bytes are stored separately in memory, even
-if they are equal in length and content.
+Strings of zero to six bytes are represented as an immediate value within a CPU
+word and are thus always represented by the same bit pattern.  (Except if they
+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.
 
 ### Rune
 
@@ -221,30 +221,47 @@ Runes are always stored directly in a CPU word; never by memory address.
 
 ### List
 
-A list is a contiguous array of one or more values in memory, whose length may
-be encoded directly within the pointer to the head of the array, or else the
-array is terminated with a special sentinel bit-pattern that is not otherwise
-valid as a Zisp value.
+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, and the list as a value
+is then represented by the memory address of the array.
 
-The parser allocates a unique array in program memory for every list, and the
-list as a value is then represented by the memory address of that array, with
-either an exact length tag or a tag indicating that it's sentinel-terminated.
-
-Lists are valid data if one of the following holds true:
+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.
+* All values in the list are a valid datum, or the list 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.
 
-### Nil
+Lists can actually be represented by two distinct value types, depending on how
+the parser is configured:
+
+1. Data lists: Allocated in the regular heap region, with a metadata header
+   allowing for an arbitrary length up to the general heap size constraints;
+   subject to automatic memory reclamation.
+
+2. Code lists: Allocated in a dedicated region of program memory, without any
+   padding or metadata header (maximally memory-dense), using a 16-bit length
+   tag directly within the pointer and thus limited to 65,535 elements; not
+   subject to automatic memory reclamation!
 
-The Zisp nil value is a singleton and a datum.  There is exactly one nil value,
-used in lieu of a list of zero length; it has the external representation `()`.
+
+## String interning
+
+Departing from Lisp tradition, Zisp doesn't use a separate *symbol* data type.
+Instead, when the parser is configured for code input, it enables *interning*
+with a configurable upper limit of up to 65,535 bytes for interned strings.
+
+Interning means that any occurrence of the same string -- equal in length and
+containing the same bytes -- ends up being represented by the same bit-pattern
+by use of a hash-set to identify reoccurring strings.
+
+The quotation method is inconsequential to this process; for example, while
+`|foo bar|` and `"foo bar"` will parse into different list values due to the
+different quotation, the actual string value they refer to will be identical.
 
 
 ## Quoted strings
@@ -261,7 +278,7 @@ the parser to generate a list with the structure:
 
 The decoder, using default settings, would emit this string verbatim as a value.
 Then, during code execution, this would be seen as an identifier.  In this way,
-pipe-quoted strings are equivalent to bare strings in functionality.
+pipe-quoted strings become equivalent to bare strings in functionality.
 
 It is important to understand that the decoder sits between the parser and the
 [interpreter](3-execute.html), and in opposition to Lisp and Scheme tradition,
@@ -323,9 +340,7 @@ Example sequence of bytes, represented as a mixture of ASCII and raw integers:
     '@' 255 0 0 0 0 2 100 <612 bytes>  ->  (#ATSTR <STRING>)
 
 One may ask why the length is not included in the list.  This is unnecessary,
-since strings in Zisp already carry length information in their own metadata
-structure.
-    
+since strings in Zisp carry their own length information anyway.
 
 ### Backslash escapes