Binary Format

AXON Binary AST Format Specification

Version 0.1.0 — Phase 2 (Draft)

---

Table of Contents

1. Overview
2. Rationale
3. File Structure
4. Header
5. String Table Section
6. Type Table Section
7. Function Table Section
8. Node Encoding
9. Variable Encoding (De Bruijn Indices)
10. Integer Encoding (LEB128)
11. Example: Fibonacci in Binary
12. Round-Trip Guarantee
13. Tooling

---

1. Overview

The AXON Binary AST format (.axb) is a compact binary encoding of the abstract syntax tree. It is designed as the primary output format for AI models generating AXON code. Instead of emitting text that must be lexed and parsed, the AI emits a byte stream that the compiler loads directly into its internal representation.

File extension: .axb
MIME type: application/x-axon-binary
Byte order: Little-endian

---

2. Rationale

Why binary format is better for AI

1. No parsing errors. Text formats introduce failure modes: unbalanced parentheses, typos in keywords, encoding issues. Binary format eliminates the entire class of syntax errors — if the structural invariants hold, the AST is valid.

2. Smaller output. AI token budgets are expensive. A binary AST is 3-5× smaller than the equivalent S-expression text, meaning the AI can express more complex programs within the same token limit.

3. Faster compilation. The compiler skips lexing and parsing entirely — the binary is memory-mapped directly into the AST representation. This makes the compile-code-test loop faster for AI-in-the-loop development.

4. Structural constraints. The binary format encodes the AST structure directly. An AI model generating binary can be constrained at the token level to only produce well-formed trees (e.g., via a constrained decoding grammar over the opcode vocabulary).

5. De Bruijn indices. Variables are referenced by structural position (how many binders away), not by name. This eliminates name shadowing bugs and variable capture — the AI never needs to invent unique names.

---

3. File Structure

An .axb file consists of a fixed-size header followed by four sections:

┌──────────────────────────────┐
│         Header (32 bytes)    │
├──────────────────────────────┤
│      String Table Section    │
├──────────────────────────────┤
│       Type Table Section     │
├──────────────────────────────┤
│     Function Table Section   │
├──────────────────────────────┤
│      AST Nodes Section       │
└──────────────────────────────┘

---

4. Header

The header is exactly 32 bytes:

Offset	Size	Field	Description
0	4	magic	Magic bytes: AXN\0 (0x41 0x58 0x4E 0x00)
4	2	version_major	Format version major (currently 0)
6	2	version_minor	Format version minor (currently 1)
8	4	flags	Bitfield flags (see below)
12	4	str_table_offset	Byte offset to string table section
16	4	type_table_offset	Byte offset to type table section
20	4	func_table_offset	Byte offset to function table section
24	4	node_offset	Byte offset to AST nodes section
28	4	checksum	CRC-32 of all sections (header excluded)

Flags

Bit	Name	Description
0	F_DEBUG	Contains debug info (source locations)
1	F_OPTIMIZED	Pre-optimized AST (constant folding applied)
2-31	—	Reserved (must be 0)

---

5. String Table Section

The string table stores all string literals and identifiers. Each string is referenced by a 0-based index (StrId). Index 0 is reserved for “no string”.

Layout

┌─────────────────────────────┐
│  count: u32                 │   Number of strings (including slot 0)
├─────────────────────────────┤
│  offsets: u32[count]        │   Byte offset of each string from start of data
├─────────────────────────────┤
│  data: u8[]                 │   Concatenated null-terminated strings
└─────────────────────────────┘

• String 0 is always the empty string "" (1 byte: 0x00).
• Strings are null-terminated in the data section.
• offsets[i] gives the byte offset from the start of data to string i.

Example

Strings: ["", "main", "fib", "n"]

count:   04 00 00 00
offsets: 00 00 00 00   01 00 00 00   06 00 00 00   0A 00 00 00
data:    00            6D 61 69 6E 00   66 69 62 00   6E 00
         ""            "main\0"         "fib\0"       "n\0"

---

6. Type Table Section

The type table stores all types used in the module. Types are referenced by 0-based index (TypeId). Index 0 is reserved for TYPE_INVALID.

Layout

┌─────────────────────────────┐
│  count: u32                 │   Number of types
├─────────────────────────────┤
│  types: TypeEntry[count]    │   Type entries
└─────────────────────────────┘

Type Entry Encoding

Each type entry begins with a 1-byte kind tag, followed by kind-specific data:

Kind	Tag	Extra Data
TY_VOID	0x00	—
TY_BOOL	0x01	—
TY_NEVER	0x02	—
TY_I8	0x03	—
TY_I16	0x04	—
TY_I32	0x05	—
TY_I64	0x06	—
TY_U8	0x07	—
TY_U16	0x08	—
TY_U32	0x09	—
TY_U64	0x0A	—
TY_F32	0x0B	—
TY_F64	0x0C	—
TY_PTR	0x0D	pointee: uleb128 (TypeId)
TY_ARRAY	0x0E	elem: uleb128 (TypeId), count: uleb128
TY_SLICE	0x0F	elem: uleb128 (TypeId)
TY_STRUCT	0x10	name: uleb128 (StrId), field_count: uleb128, then for each field: name: uleb128 (StrId), type: uleb128 (TypeId)
TY_FUNC	0x11	ret: uleb128 (TypeId), param_count: uleb128, is_variadic: u8, then for each param: type: uleb128 (TypeId)

---

7. Function Table Section

The function table provides metadata for each function in the module. The actual function bodies are encoded in the AST nodes section.

Layout

┌─────────────────────────────┐
│  count: u32                 │   Number of functions
├─────────────────────────────┤
│  entries: FuncEntry[count]  │   Function entries
└─────────────────────────────┘

Function Entry

Field	Encoding	Description
name	uleb128 (StrId)	Function name
func_type	uleb128 (TypeId)	Function type from type table
param_count	uleb128	Number of parameters
params	(uleb128, uleb128)[param_count]	For each param: (name StrId, type TypeId)
is_extern	u8	1 if extern (no body), 0 otherwise
body_offset	u32	Byte offset to body node in AST nodes section (0 if extern)
attrs	u32	Attribute bitmask (ATTR_PURE, ATTR_INLINE, etc.)

---

8. Node Encoding

AST nodes are encoded as a depth-first pre-order traversal of the tree. Each node starts with a 1-byte opcode, followed by opcode-specific data.

Node Opcodes

Opcode	Tag	Operands
ND_INT_LIT	0x01	type: uleb128, value: sleb128
ND_FLOAT_LIT	0x02	type: uleb128, value: f64 (8 bytes, IEEE 754)
ND_BOOL_LIT	0x03	value: u8 (0 or 1)
ND_STR_LIT	0x04	str_id: uleb128
ND_VAR	0x05	debruijn_index: uleb128
ND_BINOP	0x06	op: u8, then lhs: node, rhs: node
ND_UNOP	0x07	op: u8, then operand: node
ND_CALL	0x08	callee: uleb128 (StrId), nargs: uleb128, then args: node[nargs]
ND_IF	0x09	has_else: u8, then cond: node, then: node, optionally else: node
ND_WHILE	0x0A	cond: node, body: node
ND_LET	0x0B	has_type: u8, optionally type: uleb128, then init: node, body: node
ND_SET	0x0C	debruijn_index: uleb128, value: node
ND_BLOCK	0x0D	count: uleb128, then stmts: node[count]
ND_RET	0x0E	has_value: u8, optionally value: node
ND_CAST	0x0F	target_type: uleb128, then expr: node
ND_INDEX	0x10	array: node, index: node
ND_FIELD	0x11	field_name: uleb128 (StrId), then object: node
ND_DEREF	0x12	ptr: node
ND_ADDR	0x13	debruijn_index: uleb128
ND_ARRAY_LIT	0x14	elem_type: uleb128, count: uleb128, then elems: node[count]
ND_STRUCT_LIT	0x15	struct_name: uleb128, field_count: uleb128, then for each: name: uleb128, value: node

Binary Operator Tags

Op	Tag
ADD	0x00
SUB	0x01
MUL	0x02
DIV	0x03
MOD	0x04
EQ	0x05
NE	0x06
LT	0x07
LE	0x08
GT	0x09
GE	0x0A
BAND	0x0B
BOR	0x0C
BXOR	0x0D
SHL	0x0E
SHR	0x0F
LAND	0x10
LOR	0x11

Unary Operator Tags

Op	Tag
NEG	0x00
NOT	0x01
BNOT	0x02

---

9. Variable Encoding (De Bruijn Indices)

In the binary format, variables are not referenced by name. Instead, they use De Bruijn indices — a variable reference is a non-negative integer that counts how many binders (lambda abstractions / let bindings) outward the binding site is.

Example

In the text format:

(fn add ((a i64) (b i64)) i64
  (add a b))

Here, a is the parameter at index 0, b at index 1. In the binary format, a is referenced as De Bruijn index 1 (1 binder away) and b as De Bruijn index 0 (0 binders away — the closest one).

More precisely, De Bruijn indices count from the innermost binding outward:

(fn f ((x i64)) i64            ;; x is at depth 0
  (let (y (i64 1))             ;; y is at depth 0, x is now at depth 1
    (add y x)))                ;; y = debruijn(0), x = debruijn(1)

Function Parameters

Function parameters are numbered from right to left (last param = index 0):

(fn f ((a i64) (b i64) (c i64)) i64
  ;; c = debruijn(0), b = debruijn(1), a = debruijn(2)
  (add a c))
  ;; a = debruijn(2), c = debruijn(0)

Benefits for AI

1. No name invention. The AI never needs to generate unique variable names.
2. No shadowing bugs. De Bruijn indices are structurally unambiguous.
3. Smaller output. A single integer replaces a multi-character identifier.
4. Easier verification. Index validity is a simple bound check.

---

10. Integer Encoding (LEB128)

All variable-length integers in the binary format use LEB128 (Little-Endian Base 128) encoding:

Unsigned LEB128 (uleb128)

Each byte encodes 7 bits of data. The high bit (bit 7) is set if more bytes follow.

Value: 624485
Binary: 100110 0001000 1100101
Encoding: 0xE5 0x8E 0x26

Byte 0:  1_1100101  (0xE5) — more bytes follow
Byte 1:  1_0001000  (0x8E) — more bytes follow
Byte 2:  0_0100110  (0x26) — last byte

Signed LEB128 (sleb128)

Same as unsigned, but the sign bit is the highest bit of the last byte.

Value: -123456
Encoding: 0xC0 0xBB 0x78

Common Values

Value	uleb128
0	0x00
1	0x01
127	0x7F
128	0x80 0x01
255	0xFF 0x01
300	0xAC 0x02

---

11. Example: Fibonacci in Binary

The following AXON program:

(module
  (fn fib ((n i64)) i64
    (if (lt n (i64 2))
      n
      (add (call fib (sub n (i64 1)))
           (call fib (sub n (i64 2)))))))

Hex Dump

;; === Header (32 bytes) ===
41 58 4E 00              ;; magic: "AXN\0"
00 00                    ;; version_major: 0
01 00                    ;; version_minor: 1
00 00 00 00              ;; flags: none
20 00 00 00              ;; str_table_offset: 32
3F 00 00 00              ;; type_table_offset: 63
4C 00 00 00              ;; func_table_offset: 76
62 00 00 00              ;; node_offset: 98
A7 B3 C1 D2              ;; checksum: CRC-32

;; === String Table ===
03 00 00 00              ;; count: 3 (including slot 0)
00 00 00 00              ;; offsets[0]: 0 → ""
01 00 00 00              ;; offsets[1]: 1 → "fib"
05 00 00 00              ;; offsets[2]: 5 → "n"
00                       ;; data[0]: "" (null)
66 69 62 00              ;; data[1]: "fib\0"
6E 00                    ;; data[2]: "n\0"

;; === Type Table ===
03 00 00 00              ;; count: 3
00                       ;; types[0]: TY_VOID (placeholder for TYPE_INVALID)
06                       ;; types[1]: TY_I64
01                       ;; types[2]: TY_BOOL
;; (plus function type entry — elided for brevity)

;; === Function Table ===
01 00 00 00              ;; count: 1
01                       ;; name: StrId 1 ("fib")
03                       ;; func_type: TypeId 3 (i64 → i64)
01                       ;; param_count: 1
02 01                    ;; param[0]: name=StrId 2 ("n"), type=TypeId 1 (i64)
00                       ;; is_extern: false
00 00 00 00              ;; body_offset: 0 (start of nodes section)
00 00 00 00              ;; attrs: ATTR_NONE

;; === AST Nodes (body of fib) ===
;; (if (lt n (i64 2)) n (add (call fib (sub n (i64 1))) (call fib (sub n (i64 2)))))

09                       ;; ND_IF
01                       ;; has_else: true
  06                     ;; ND_BINOP
  07                     ;; op: LT
    05                   ;; ND_VAR
    00                   ;; debruijn_index: 0 (n)
    01                   ;; ND_INT_LIT
    01                   ;; type: TypeId 1 (i64)
    02                   ;; value: sleb128(2)
  05                     ;; ND_VAR (then branch: n)
  00                     ;; debruijn_index: 0
  06                     ;; ND_BINOP (else branch: add)
  00                     ;; op: ADD
    08                   ;; ND_CALL
    01                   ;; callee: StrId 1 ("fib")
    01                   ;; nargs: 1
      06                 ;; ND_BINOP
      01                 ;; op: SUB
        05               ;; ND_VAR
        00               ;; debruijn_index: 0 (n)
        01               ;; ND_INT_LIT
        01               ;; type: TypeId 1 (i64)
        01               ;; value: sleb128(1)
    08                   ;; ND_CALL
    01                   ;; callee: StrId 1 ("fib")
    01                   ;; nargs: 1
      06                 ;; ND_BINOP
      01                 ;; op: SUB
        05               ;; ND_VAR
        00               ;; debruijn_index: 0 (n)
        01               ;; ND_INT_LIT
        01               ;; type: TypeId 1 (i64)
        02               ;; value: sleb128(2)

Total size: ~98 bytes for the nodes section, compared to ~170 characters of S-expression text.

---

12. Round-Trip Guarantee

The binary format provides a semantic round-trip guarantee:

decode(encode(ast)) ≡ ast

Specifically:

1. Structural equivalence: The decoded AST has the same tree structure as the original.
2. Type preservation: All type annotations are preserved exactly.
3. Value preservation: All literal values are preserved exactly (including floating-point bit patterns).
4. Variable binding: De Bruijn indices are resolved back to the same binding sites.

Note: The round-trip does not preserve:

• Variable names (De Bruijn indices replace names)
• Source locations (unless F_DEBUG flag is set)
• Comments (not representable in binary)
• Whitespace or formatting

Verification

The compiler includes a verification mode:

# Encode text to binary
axonc encode input.axs -o output.axb

# Decode binary back to text
axonc decode output.axb -o roundtrip.axs

# Verify structural equivalence (ignoring names)
axonc verify input.axs output.axb

---

13. Tooling

Planned Tools

Tool	Description
axonc encode	Compile .axs text to .axb binary
axonc decode	Decompile .axb binary to .axs text
axonc dump	Hex dump with annotations
axonc verify	Verify round-trip equivalence
axonc inspect	Pretty-print type table, string table, function table

Library API

For AI agent integration, a C library API will be provided:

// Write binary AST
AxbWriter *axb_writer_new(Arena *a);
void axb_write_header(AxbWriter *w, uint32_t flags);
void axb_write_string(AxbWriter *w, const char *s, size_t len);
uint32_t axb_write_type(AxbWriter *w, Type *t);
void axb_write_node(AxbWriter *w, uint8_t opcode, ...);
void axb_finish(AxbWriter *w, FILE *out);

// Read binary AST
AxbReader *axb_reader_new(const uint8_t *data, size_t len, Arena *a);
bool axb_read_header(AxbReader *r, AxbHeader *hdr);
Node *axb_read_module(AxbReader *r, TypeTable *types, StrTable *strings);