path: root/doc/0/0-value.md

# NaN-packed Value

<!--TOC-->

Zisp uses *NaN-packing* for a uniform 64-bit *Value* representation that covers
*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:

    { sign: 1 bit, exponent: 11 bits, fraction: 52 bits }

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.

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 ***

    1. Negative cqNaN    :: { sign = 1, exponent = MAX, fraction = 10000... }

    2. Negative Infinity :: { sign = 1, exponent = MAX, fraction = 00000... }

    3. Positive cqNaN    :: { sign = 0, exponent = MAX, fraction = 10000... }

    4. Positive Infinity :: { sign = 0, exponent = MAX, fraction = 00000... }

The abbreviation *cqNaN* stands for canonical quiet NaN.

The MSb of the fraction is also called the `is_quiet` flag, because it marks a
NaN as being *quiet* rather than signaling.  The rest of the fraction being all
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.

Infinity values may also be returned by FP operations, and we want them to also
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 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
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
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, 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   :: List pointer with length tag

    001   :: Heap pointer with type tag

    010   :: Istr pointer with length tag

    011   :: Short string immediate

    100   :: Small rational immediate

    101   :: Undefined

    110   :: Undefined

    111   :: Immediate types further subdivided as follows:

             0....... 0....... 0....... (etc.)  :: Rune

             1.......                           :: 128 40-bit types

             0....... 1.......                  :: 16384 32-bit types

             0....... 0....... 1.......         :: 2097152 24-bit types

             (etc.)

Forbidden Pattern #3, Positive cqNaN, is avoided thanks to the fact that some
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, and the index may have different addressing resolutions,
such as 8-byte units, 16-byte units, and so on.

### List pointers

In Zisp, a list is a contiguous array of a fixed number of Values.  To improve
memory density and cache locality, especially for the interpreter, lists of up
to 255 elements are allocated in tight blocks with little or no padding and no
metadata headers on the heap.  Their length is therefore encoded directly with
an 8-bit metadata field within the NaN-packed pointer itself.

The exact layout of the 48-bit payload is as follows:

The low 32 bits are an index into the list heap, while the higher 16 bits are
divided into 8 high bits for the length, and 8 low bits for internal metadata
such as for garbage collection.

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.

Lists that are longer than 255 elements are represented through regular heap
pointers to Array objects.

### Heap pointers

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 heap
pointer, plus 8 more bits encoding the heap object type.

### String pointers

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 low 32 bits are a heap index, while the higher
16 bits are divided into 8 high bits for a non-zero length, and 8 low bits for
internal metadata such as for garbage collection.

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; 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.

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.

### Small rationals

We use a 48-bit space for small rational numbers, with a 32-bit signed two's
complement integer numerator in the low 32 bits, and a 16-bit unsigned integer
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
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.

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.

We divide this space into increasingly many potential types, with smaller and
smaller payloads, where the highest byte with a non-zero MSb determines which
size category we're in: If the highest byte has its MSb set, then the other
seven bits are a type tag, and each type has a 40-bit payload; if the second
highest byte has its MSb set, then the 14 non-MSb bits of the two high bytes
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; 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
(28-bit type tag) and over 34 Billion 8-bit types (35-bit type tag).


## Code optimization

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.

Before, the meanings are as follows:

    000   :: Quoted list pointer

    001   :: Quoted heap pointer

    010   :: Quoted istr pointer

    011   :: Quoted short string

    ...   :: Undefined

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.

When the optimizer encounters such quoted data, it acknowledges the quoting and
simply flips back one bit; other data forms are optimized as code.

After the optimization pass, the meanings are as follows:

    000   :: Pointer to list code form

    001   :: Pointer to heap code form

    010   :: Local variable reference

    011   :: Lexical capture reference

    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.

### 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, but only into one of the
above listed Value types.

### 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,
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 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
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:
;; fill-column: 80
;; End:
-->