diff options
Diffstat (limited to 'doc/0/1-parse.md')
| -rw-r--r-- | doc/0/1-parse.md | 123 |
1 files changed, 69 insertions, 54 deletions
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 |