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

# NaN-packed Value

<!--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,
minus the following four bit patterns:

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

Infinity values may also be returned by FP operations, and we want them to also
exist 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 to be encoded.  (51-bit values excluding zero.)

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

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

    sign = 0, quiet = 1 :: Pointers and 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 Value #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 Value #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 istr object

    001   :: Pointer to list values

    010   :: Pointer to heap object

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

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

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.

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

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.

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.

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

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.

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

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

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.

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 istr object as constant

    001   :: Pointer to list values as constant

    010   :: Pointer to heap object as constant

    011   :: Immediate short string as constant

    100   :: Index of a local variable

    101   :: Index of a lexical capture

    110   :: Undefined

    111   :: Pointer to optimized code expression

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

Forbidden Value #4, Positive Infinity, is avoided thanks to the fact that istr
pointers always have non-zero length bits.

### 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, 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 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.

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.




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