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

# NaN-packed Value

<!--TOC-->

Zisp uses NaN-packing for a uniform 64-bit Zisp Value representation.

When we speak of a 64-bit Value that is either a Zisp double or NaN-packed Zisp
value, we use the term "Value" with a capital 'V'.  In other words, a Value is
either a Zisp double, or the NaN-packed representation of any other Zisp value.

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 non-double packing, the remaining 53 bits are available, giving us `2^53`
values, minus the following four bit patterns which *are* doubles:

    *** 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 in Zisp as doubles.

Infinity values may also be returned by FP operations, and we want them to also
exist as doubles in Zisp, so they also represent themselves.

Beyond those four bit patterns, all values with a maximum exponent (all bits
set) are fair game for representing other Values, so `2^53 - 4` possibilities.

We split those `2^53 - 4` available values into four groups, each allowing for
`2^51 - 1` different values (51-bit values excluding zero) for Value coding:

    sign = 1, quiet = 1 :: Negative Fixnums from -1 to -2^51+1

    sign = 1, quiet = 0 :: Positive Fixnums from 0 to 2^51-2

    sign = 0, quiet = 1 :: Pointers and other immediates

    sign = 0, quiet = 0 :: Tree-VM instructions


## Fixnums

Negative fixnums actually represent themselves, without needing to go through
any transformation.  Only the smallest 52-bit signed negative, `-2^51`, cannot
be represented, as it would step on Forbidden Pattern #1, Negative cqNaN.

Positive fixnums go through a bitsiwe NOT (which can be implemented as an XOR
mask combining it with removal of NaN-related high bits) to avoid the all-zero
payload value, which would step on Forbidden Pattern #2, Negative Infinity.


## Pointers and immediates

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 list (code)

    001   :: Pointer to heap

    010   :: Pointer to istr

    011   :: Immediate short string

    100   :: Immediate small rational  (sign bit 0)

    101   :: Immediate small rational  (sign bit 1)

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

Zisp splits the native program heap provided by the platform into three regions
of virtual memory: The code heap of 32 GiB, addressed in 64-bit (8-byte) units;
the main heap of 32 GiB, also addressed in 64-bit units; and the 4 GiB heap for
`istr` objects (interned strings) which is addressed in bytes.  Each region can
thus be addressed via 32-bit indices instead of larger direct pointers.

### List pointers

In Zisp, a list is a contiguous array of a fixed number of Values.  These may
reside in the main heap or the code heap; this pointer type here is used to
represent lists in the code heap specifically.

These code lists are allocated with no or little padding, and with no metadata
headers, to achieve optimal memory density and cache locality of code.  As such,
we must encode the length of the list directly in the pointer itself.

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

The low 32 bits are an index into the code heap, while the higher 16 bits are
divided into 8 high bits for the length, and 8 low bits for garbage collector
metadata.

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.

The 8-bit length field means we can only encode lists of up to 255 elements
using this Value type.  However, this doesn't mean that source code cannot
contain longer lists:

Lists of arbitrary length can be allocated as regular heap objects of the Array
type; the difference is hidden when using a generic list API.  This means that
*some* parts of source code may actually end up on the main heap, though lists
of greater than 255 elements should be extremely rare, typically only used to
embed static data arrays in source code anyway.

Forbidden Pattern #3, Positive cqNaN, is avoided thanks to the fact that the
high 8 bits of the payload, encoding the list length, cannot be zero.

### Heap pointers

Regular heap objects are represented by this index type, which uses a 32-bit
index into the main heap, in the lower portion of the 48-bit payload.

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 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 main
heap index, plus 8 more bits encoding a specific heap 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 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; 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.

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

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 & 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).


## Internal use Values

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 list as constant

    001   :: Pointer to heap as constant

    010   :: Pointer to istr as constant

    011   :: Short string as constant

    100   :: Pointer to opcodes in code list

    101   :: Pointer to opcodes in heap list

    110   :: Local variable reference index

    111   :: Lexical capture reference index

### Constant Values

The first four categories simply mirror those of the previous 51-bit range, but
mark the Value as being a constant rather than code to evaluate.  This way, we
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 Pattern #4, Positive Infinity, is avoided thanks to the fact that
pointers to lists always have non-zero length bits.

### Opcode array pointers

These types are derived from the regular code list pointers (length <= 255) and
heap list pointers (length > 255) by flipping 2 bits.

A heap list pointer of this kind would result from a list of longer than 255
that represents actual code to execute.  (Had it been a quoted list, it would
have become a "pointer to heap as constant" instead.)  This will be exceedingly
rare, given that regular code expressions almost never have such length, but we
must support it.  It might have resulted, for example, from heavy macro use or
otherwise machine-generated source code.

Either way, what this means is that a list has been analyzed to ensure it's a
well-formed code expression, and transformed 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 into VM instructions, but
only of the above listed Value types.

### 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; another 32 bits are
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; another 32 bits are
reserved for other purposes.


<!--
;; Local Variables:
;; fill-column: 80
;; End:
-->