diff options
| author | Taylan Kammer <taylan.kammer@gmail.com> | 2026-06-27 09:41:01 +0200 |
|---|---|---|
| committer | Taylan Kammer <taylan.kammer@gmail.com> | 2026-06-27 09:41:01 +0200 |
| commit | 831ff8ddfbc1d22c051c15940afd4c0eb7eb92fc (patch) | |
| tree | e7078fb0b9e2ef681d5ffa0747f69a18e163ebcb /doc/0 | |
| parent | 15a03f90ae86f1dc75224405904c1f2ba4f57176 (diff) | |
Improvements to latest design changes.
Diffstat (limited to 'doc/0')
| -rw-r--r-- | doc/0/0-value.md | 78 | ||||
| -rw-r--r-- | doc/0/1-parse.md | 28 |
2 files changed, 53 insertions, 53 deletions
diff --git a/doc/0/0-value.md b/doc/0/0-value.md index c2810d8..2b9a858 100644 --- a/doc/0/0-value.md +++ b/doc/0/0-value.md @@ -95,70 +95,78 @@ bits, providing a payload value of 48 bits for each. ### Interned strings -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. +An `istr` is an interned string of up to 255 arbitrary bytes, fulfilling a +similar purpose to symbols in Lisp and Scheme. -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. +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 -16 bits of the payload value cannot be zero. +8 bits of the payload, encoding the length, 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 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. -The upper 16 bits of the payload encode the length (element count) meaning that -a list can contain up to 65,535 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. The empty list is canonically represented with a null payload value, i.e., zero -length, and zero offset. +length, cleared GC metadata bits, and zero index value. -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. +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 explicitly +heap-allocated Value, a *pair* type of exactly two Values, and a variety of +*struct* types of fixed Value counts could be implemented by this type. ### Heap 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. +the low 32 bits of the payload as an index value as well, meaning this region +can occupy another 32 GiB of memory. -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. +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. (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.) -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. +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. -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. +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 -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 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. -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. +The empty string is represented with an all-NUL payload. NOTE: The order of bytes may depend on the endianness of the platform. diff --git a/doc/0/1-parse.md b/doc/0/1-parse.md index b8f1c2d..54b1dd4 100644 --- a/doc/0/1-parse.md +++ b/doc/0/1-parse.md @@ -221,43 +221,35 @@ 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, and the list as a value -is then represented by the memory address of the array. +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 the list is empty. +* 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. -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! - ## 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. +for all strings up to 255 bytes in length. 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. +by use of a hash-set to identify reoccurring strings; the same strategy used +with symbols, but applied to all 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 |
