bitrings.md

As a first hardware layer abstraction level, and to make addressing arithmetic between types as easy as possible, I propose this simple bitring-based type system, to which runtime values of the above kind are specialized:

• bit is the only atomic type and represents a value of either 0 or 1.
• A ring of n bit size is described with a simple integer constant n and has degree 1. 32 for example describes a bitring of size 32 that can hold one of 2**32 bit patterns and distinguishes between 32 different keys of degree 1 (0..31). The elements of a bitring can be indexed with bitrings, whose value will be modulated by the ring size.
• A bit is also a ring of size 1, which only accepts the value 0 as key, and has degree 1.
• 0 describes a zero-element bitring of depth 1 that accepts no keys and has degree 0.
• K * T describes an multidimensional bitring of element type T, size K and degree degree(T)+1, or the product of two rings. 2 * 3 * 5 defines a 2-element ring of a 3-element ring of a 5-element ring of bits, or a ring of degree 3 and size 30. The ring types 30 and 2 * 3 * 5 have the same size.
• * is a non-commutative operator. T * K != K * T, as keys need to be specified in order.
• * is an irreducible operator. (64 * 64) * 32 describes a bitarray of degree 2 with its top key being of degree 2 as well.
• N ** T describes a map of size pow(sizeof(N),sizeof(T)). The final type depends on the degree of provided arguments. 2 ** 32 is equivalent to 4294967296.
• All rings of same size are isomorphic to each other and can therefore be cast to each other without cost.
• T @ K describes indexing a bitarray T by key of type K. A key must have the same degree as the top ring type of the product. (2 * 3 * 5) @ 32 evaluates to 3 * 5. (2 * 3 * 5) @ 32 @ 32 @ 32 evaluates to 1. (64 * 64) * 32 @ (6 * 6) evaluates to 32.
• inf is a bitarray of degree 1 and infinite length.
• a..b describes a bitarray with a variable length between the two constant integers provided, both included.
• ... describes a bitarray of unknown degree.
• ... * ... abstractly describes a polymorphic associative map permitting arbitrary keys.
• A | B | ... describes a union of two or more bitarrays. The min/max size is min(sizeof(A),sizeof(B)) and max(sizeof(A),sizeof(B)).
• A + B + ... describes a tuple of two or more bitarrays.

Let's look at some LLVM or SPIR-V types and how they're equivalently described in this system. The alignment rules are vastly different, of course.

• {} or void are equivalent to 0
• iN is simply N; so booleans use 1, integers commonly use 8,16,32,64.
• Floats and doubles use 32 and 64.
• [T x N] and <T x N> are the same as N * T. We do not distinguish between array or vector type.
• {A B C} is the same as A + B + C.
• 64-bit pointers are perfectly described by 64. Untyped main memory is of type 2 ** 64 * 8.
• String constants are typically of type N * 8.
• A RGBA8 layered image would use the type L * H * W * 4 * 8.