Specification

1.

Lexical elements

The tokenizer produces a flat list of string tokens from source text.

• Whitespace: Spaces, tabs, and newlines delimit tokens and are otherwise ignored.
• Parentheses: ( and ) are standalone tokens that delimit list expressions.
• Quote token: ' is emitted as a standalone token.
• Integer literals: Decimal integers such as 1, 255, and -128 parse to Expr("int", …).
• Float literals: Values such as 3.14 and -2.5 parse to Expr("fp64", …).
• String literals: Double-quoted text such as "hello world" parses to Expr("str", …).
• Hex bytes: 0x1f and 0Xab parse to Expr("bytes", …).
• Symbols: Any other contiguous non-whitespace, non-parenthesis string. Examples: sum, def, math.sum.
• Line comments: ; starts a comment that runs to end-of-line.
• Block comments: #; skips the next complete expression, including nested lists.

2.

Expression data model

Every value is an Expr with a base slot ("link", "symbol", or "bytes") and a value slot that holds the inline payload for scalar types (int, str, floats) or None for pair links. The _tag, _value, _head, and _tail properties expose the same read interface for backward compatibility. The type tag is the terminal symbol of the value's canonical linked form — the type is structurally embedded in the value itself.

Type system tiers

• Open — any symbol passed to init introduces a new type at runtime; no declaration or registry required.
• Dynamic — tags are runtime symbols, introspected via type and dispatched by tag equality; no static checking.
• Nominal — type identity is tag-symbol equality, not structural shape.
• Structurally embedded — the tag is the terminal of the value's canonical linked form (link(args…, symbol("tag"))), making the type part of its content-addressed encoding.

Base types

Three terminal types with direct wire encoding. All other types decompose into these for hashing and serialization.

• link (wire 0x00) — a pair (head, tail). link(None, None) is NIL. Can also carry unresolved hash pointers for lazy DAG traversal.
• symbol (wire 0x01) — a named identifier, stored as UTF-8.
• bytes (wire 0x02) — raw byte data.

Builtin types

All eleven natively supported types. Includes the three base types (italicised) plus eight composed types that serialize as link(bytes(payload), symbol(tag)):

• int — tag "int", variable-length signed LE encoding (composed)
• e4m3 — tag "e4m3", 1-byte (4-bit exponent, 3-bit mantissa) (composed)
• e5m2 — tag "e5m2", 1-byte (5-bit exponent, 2-bit mantissa) (composed)
• fp16 — tag "fp16", 2-byte IEEE 754 LE (composed, half precision)
• bf16 — tag "bf16", 2-byte brain float (composed)
• fp32 — tag "fp32", 4-byte IEEE 754 LE (composed, single precision)
• fp64 — tag "fp64", 8-byte IEEE 754 LE; the default float literal type (composed)
• str — tag "str", UTF-8 encoding (composed)
• symbol — tag "symbol", UTF-8 (base, wire 0x01)
• bytes — tag "bytes", raw (base, wire 0x02)
• link — tag "link" (base, wire 0x00)

Float precision hierarchy

lib-py supports six float types at different precision levels. All float arithmetic is same-type; mixed float types raise an error. Arithmetic results promote to the next wider type: e4m3/e5m2 → fp16; fp16/bf16 → fp32; fp32 → fp64.

• e4m3 — 8-bit (4-bit exponent, 3-bit mantissa)
• e5m2 — 8-bit (5-bit exponent, 2-bit mantissa)
• fp16 — 16-bit IEEE 754 half-precision
• bf16 — 16-bit brain float
• fp32 — 32-bit IEEE 754 single-precision
• fp64 — 64-bit IEEE 754 double-precision (base — decimal literals parse as fp64)

User types

Any other tag string. User types are entirely open — passing any symbol to init creates a new type on the spot. Constructed via init and introspected via type:

(3 5 link 'point init)   → Expr("point", value=link(3, 5))
(point_val type)            → Symbol("point")

Type-name-as-constructor

Built-in type names (int, bytes, fp64, str, symbol, link) are polymorphic coercion operators. User types follow the same pattern — the type name is bound as a function that calls init with its quoted tag:

'( (x y link 'point init) (x y) closure ) 'point def
'( (expr) expr head closure ) 'point.x def
'( (expr) expr tail head closure ) 'point.y def

(3 5 point apply) constructs a point. init is idempotent (re-tagging a value that already bears the target tag is a no-op). type returns the tag as a Symbol, following the tag-last canonical form — the type symbol is the terminal of the link chain. The explicit apply is required because closure values are tagged link pairs.

Content-addressed hashing

• Every Expr has a cached 32-byte Blake3 hash computed lazily.
• Serialization uses a compact binary format: base types use a wire tag byte (0x00/0x01/0x02) followed by payload; composed types serialize as link(bytes(payload), symbol(tag)); user types serialize as link(value, symbol(tag)).
• The encoding module provides encode_expr_to_bytes for serialization and decode_expr_from_bytes for deserialization.

3.

Parsing

• tokenize(source: str) -> List[str] produces tokens.
• parse(tokens: List[str]) -> (Expr, List[str]) consumes one expression and returns it with the remaining tokens.
• ( opens a nil-terminated list. Items are parsed recursively until ). Empty list () produces link(None, None) (NIL). Non-empty lists are nil-terminated: (a b c) parses to link(a, link(b, link(c, NIL))).
• Decimal integers parse to Expr("int", …).
• Float tokens parse to Expr("fp64", …).
• Double-quoted strings parse to Expr("str", …).
• 0x or 0X prefixed hex tokens parse to Expr("bytes", …).
• All other tokens become Expr("symbol", …).
• ParseError is raised on unexpected end-of-input or unmatched ).

4.

Evaluation model

evaluation(machine, expr, stack, env) -> List[Expr] is the core recursive evaluator.

Symbol dispatch

• Operator: If the symbol is in OPERATOR_LIST, the handler is called. The operator pops arguments from the stack and pushes results.
• Variable: Otherwise, the symbol is looked up via env.get(value). If bound, the value is pushed. If unbound, NIL is pushed.
• Meter charges: bound lookups cost symbol_size + value_size; unbound lookups cost symbol_size + 1.

Atom evaluation

• bytes, int, fp64, and str values push themselves onto the stack.
• Charges are size-based and depend on the concrete value.

Link evaluation

• Quote: If the list head is quote or ', the tail is pushed unevaluated. (quote) with no tail pushes NIL.
• Normal: Evaluate head, then evaluate tail recursively. This is how postfix dispatch works.

Result

• Machine.run(expr, env) calls evaluation and returns the top of stack, or NIL if the stack is empty.
• Operators that wrap their result via the ? suffix push tagged results in the form (value . ok) or (msg . err) — see section 9.

5.

Operators

Stack notation below uses (before -> after).

5.1 Arithmetic

• + - (b a -- sum). Int + Int returns Int. fp64 + fp64 returns fp64. Mixed Int/fp64 promotes to fp64.
• - - (b a -- diff). Same type rules as +.
• * - (b a -- product). Same type rules as +.
• / - (b a -- quotient). Int / Int uses integer division. fp64 / fp64 uses float division. Mixed Int/fp64 promotes to fp64.
• % - (b a -- remainder). Int only.
• sqrt - (a -- sqrt(a)). fp64 only.
• abs - (a -- abs(a)). Int or fp64. Raises OpError on non-numeric.

Example: (1 2 +) -> 3. (1.5 2.5 +) -> 4.0.

5.2 Comparison

• < - (b a -- 0|1). Less than (Int/Int or fp64/fp64). Pushes Bytes(b"\x01") if true, else Bytes(b"\x00"). Raises OpError on type mismatch.
• > - (b a -- 0|1). Greater than. Same type rules as <.
• <= - (b a -- 0|1). Less than or equal. Same type rules as <.
• >= - (b a -- 0|1). Greater than or equal. Same type rules as <.

5.3 Bitwise

• & - (b a -- a & b). Bytes only.
• | - (b a -- a | b). Bytes only.
• ^ - (b a -- a ^ b). Bytes only.
• ~ - (a -- ~a). Bytes only.

5.4 Shifts and rotates

• << — shift: value (Bytes or Int) left by shifts (Int > 0) or right by shifts (Int < 0). For Bytes the shift is logical (zero-fill); for Int it is arithmetic (sign-extend). No-op on 0.
• <<< — rotate: value (Bytes or Int) left by shifts (Int > 0) or right by shifts (Int < 0). Rotation width is byte-rounded for Int. No-op on 0.

5.5 Stack operations

• dip - temporarily removes one value, evaluates the next expression, then restores the saved value.
• drop - discard the top stack value.
• dup - duplicate the top stack value.
• swap - swap the top two stack values.
• rot - (a b c -- b c a). Rotate the top three stack values left.

5.6 Expression construction

• link - (head tail -- link(head, tail)).
• head - (link -- head). Pushes NIL if the head is missing.
• tail - (link -- tail). Pushes NIL if the tail is missing.
• is_eq - (b a -- 0|1). Structural equality. Different types are never equal. Pushes Bytes(b"\x01") if equal, Bytes(b"\x00") otherwise.
• eval - (expr -- evaluated). Re-enters the evaluator on the value. Not blocked in deterministic mode.
• quote - (a -- (' a)). Stack operator that wraps a value in a quotation.
• id - (expr -- bytes). Pushes the 32-byte BLAKE3 hash of any expression.
• parse - (str -- expr). Tokenizes and parses a string as an Astreum S-expression. Raises OpError on parse failure.

5.7 Definition & control flow

• def - (name value -- ). Stores value under name in the current lexical scope. Write-once: redefinition raises OpError (caught and pushes NIL in bare form).
• if - (cond then else -- result). The condition is evaluated first. Truthiness is non-zero Bytes, non-zero Int, non-zero fp64, or a non-NIL Link whose head is not Symbol("err").
• rec - (pred then_branch rec1 rec2 -- result). Evaluates pred; if truthy evaluates then_branch, otherwise evaluates rec1, recurses, then evaluates rec2 on return.

5.8 Sequence operations

All sequence operators are polymorphic over Bytes, str, and link.

• concat - (a b -- concatenation). Concatenates two sequences. Raises OpError on type mismatch.
• split - (value index -- link(left, right)). Splits a sequence at index (Int). Raises OpError on out-of-bounds.
• index - (value index -- element). Returns the nth element. Raises OpError on out-of-bounds.
• count - (seq -- int). Returns the length of a sequence. Replaces the removed bytes-only size.
• reverse - (seq -- seq). Reverses a sequence.
• map - (seq cl -- seq). Applies closure cl to each element and collects results.
• filter - (seq cl -- seq). Keeps elements where closure pushes truthy.
• each - (seq cl -- seq). Applies closure cl to each element for effects; returns the original sequence.
• fold - (seq init cl -- result). Left fold over the sequence.
• zip - (seq1 seq2 -- seq). Pairwise zips two sequences into a link list.
• find - (seq cl -- elem|nil). Returns the first element matching the predicate closure.

5.9 Conversion

• symbol - (a -- symbol|NIL). Converts Bytes, String, Int, or fp64 to Symbol.
• str - (a -- string|NIL). Converts any atom to String.
• int - (a -- int|NIL). Converts Bytes, String, Symbol, or fp64 to Int.
• bytes - (a -- bytes|NIL). Converts Int, fp64, String, or Symbol to Bytes.
• e4m3 - (a -- e4m3|NIL). Converts Bytes (1 byte) or String to 8-bit float (4-bit exponent, 3-bit mantissa).
• e5m2 - (a -- e5m2|NIL). Converts Bytes (1 byte) or String to 8-bit float (5-bit exponent, 2-bit mantissa).
• fp16 - (a -- fp16|NIL). Converts Bytes (2 bytes) or String to IEEE 754 half-precision.
• bf16 - (a -- bf16|NIL). Converts Bytes (2 bytes) or String to brain float.
• fp32 - (a -- fp32|NIL). Converts Bytes (4 bytes) or String to IEEE 754 single-precision.
• fp64 - (a -- fp64|NIL). Converts Bytes (8 bytes) or String to IEEE 754 double-precision.

5.10 Type, tag & monadic operators

• init - (value 'tag -- expr). Wrap value in a typed Expr with tag tag. Idempotent for matching tags.
• type - (expr -- symbol). Return the tag of expr as a Symbol.
• ok - (val -- (val . ok)). Wrap a value with the ok tag in the tail (terminal) position.
• err - (msg -- (msg . err)). Wrap a message with the err tag in the tail position.
• result - (val|(val . tag) [cont] -- ...). Inspect a tagged result: if err leave it; if ok extract the head.
• match - (val tag_sym succ_cl fail_cl -- ...). If val's terminal tag equals tag_sym, push head and evaluate succ_cl; otherwise push val and evaluate fail_cl.
• is - (val tag_sym -- bytes). Pushes Bytes(b"\x01") if the value's type tag (or terminal tag for links) equals tag_sym, else Bytes(b"\x00").
• is_atom - (expr -- 0|1). Pushes Bytes(b"\x01") if the value is not a link, else Bytes(b"\x00").

5.11 Closures

• closure - (params body -- tagged). Pop params (Symbol chain) and body. Snapshot the current environment and push a tagged link pair (((env_uuid . body) . params) . 'lex). The 'lex tag indicates a captured parent environment.
• apply - (argN … arg1 tagged -- result). Applies a function value. If the terminal tag is 'lex, restores the captured environment from machine.library by UUID; if 'dyn, uses the current call-site lexical environment; if 'pure, uses no parent environment (closed scope).

'dyn and 'pure are tag symbols recognised by apply but have no dedicated operator — they are constructed manually with link.

5.12 Storage / code

• ref - (hash -- expr|NIL). Resolves a 32-byte hash to a stored expression. Blocked in deterministic mode.
• load - (hash -- full_expr|NIL). Deep-resolves a 32-byte hash recursively. Blocked in deterministic mode.

5.13 Console I/O

• print - (expr -- ). Writes repr(expr) to stdout. Void (no stack push). Blocked in deterministic mode.
• println - (expr -- ). Writes repr(expr) + "\n" to stdout; if stack is empty prints just \n. Void. Blocked in deterministic mode.

5.14 Actor model

• spawn - (body name -- name|NIL). Spawns a new actor thread running body in a child environment. name must be a Symbol. Blocked in deterministic mode.
• send - (target msg -- ). Sends msg to the mailbox of actor target. Void. Blocked in deterministic mode.
• receive - (target -- msg|NIL). Blocks until a message arrives in the mailbox of actor target. Blocked in deterministic mode.

5.15 Consensus / context operators

• acc.balance - (-- balance). Push the expression account's (tx.recipient) balance as Int.
• acc.get - (key -- value|NIL). Look up key (Bytes) in the expression account's data store. Pushes NIL if absent.
• acc.put - (key value -- ). Store value (Bytes) under key (Bytes) in the expression account's data. Sender pays a storage fee. Void.
• acc.pay - (recipient amount -- ). Pay amount (Int) from the expression account (tx.recipient) to recipient (Bytes). Creates recipient account if missing; sender pays storage fee for new accounts. Void.
• block.chain_id - (-- chain_id). Push the current block's chain_id as Int.
• block.height - (-- height). Push the current block's height as Int.
• block.previous_block_hash - (-- hash). Push the current block's previous_block_hash as Bytes (32 bytes).
• block.timestamp - (-- timestamp). Push the current block's timestamp as Int.
• block.bloom.insert - (value -- ). Record value.hash() as a bloom search key. Charges 8 storage bytes per non-dedup call. Deduped per-tx and per-block. Void.
• tx.amount - (-- amount). Push the current transaction's amount as Int.
• tx.recipient - (-- recipient). Push the current transaction's recipient public key as Bytes (32 bytes).
• tx.sender - (-- sender). Push the current transaction's sender public key as Bytes (32 bytes).
• tx.new - (code recipient amount data -- 1|NIL). Construct an internal (unsigned) transaction and apply its effects inline. The contract appears as the nested tx's sender; the value transferred debits the contract's balance; execution + storage fees debit the outer tx sender. On success pushes 1; on failure pushes NIL and reverts effects.
• tx.log - (expr -- ). Append an expression as a log entry in the current transaction's log. Dedup-aware, charges to storage meter. Void.

6.

Environment and scoping

• Env(data, parent) stores local bindings and an optional lexical parent environment.
• get(key) checks local data first, then walks parent environments.
• put(key, value) binds in the local environment.
• def writes to the current lexical scope only (no global def_target mechanism). Machine.run() creates a fresh Env per call — there is no shared mutable global environment. Redefining an existing name raises OpError (caught and pushes NIL in bare form).
• closure captures the current environment via machine.snapshot_env(env); apply restores it from machine.library by UUID for 'lex-tagged values.

7.

Machine and metering

Machine class

• Machine(node, mode="dynamic", meter_limit=None) orchestrates evaluation.
• In "dynamic" mode, all operators execute normally.
• In "deterministic" mode, spawn, send, receive, ref, load, print, and println (and their ? variants) push NIL instead of executing. eval, closure, and apply execute normally.
• run(expr, env=None) evaluates an expression and returns the top of the stack or NIL.

Meter (gas)

• Meter(limit=None) tracks byte-level computation cost split into two pools: eval and storage. limit=None means unlimited.
• charge(n, kind="eval"|"storage") credits the appropriate pool. If total would exceed the limit, it raises MeterExceededError.
• total returns eval + storage. remaining() returns the budget before the limit is hit.
• charge_bytes(n, is_storage=False) is the legacy API; equivalent to charge(n, kind="storage" if is_storage else "eval").
• Operators that touch storage (acc.put, tx.log, block.bloom.insert, etc.) charge to the storage pool.
• Per-operator cost formulas and fixed costs are listed in the Language Reference operator tables.

8.

Module system

The module system is implemented by the loader in machine/loader.py. It processes .aex files into environments at load time.

Module file structure

• A module file is a sequence of top-level S-expressions, each parsed independently.
• Each expression must be a 3-element form: (value name_or_prefix terminator).
• The terminator must be def or import.

Definitions

• (value name def) stores value under name with no runtime evaluation at load time.
• Names are UTF-8 symbols. Example: (1 version def).

Path imports

• (prefix "path/to/module.aex" import) or (prefix path/to/module.aex import) loads another module file.
• Paths may be absolute or relative to the importing module's directory.
• All definitions in the loaded module are prefixed with prefix..

Reference imports

• (prefix (0x... ref) import) loads a module expression stored in expression storage by content hash.

Symbol rewriting

• When a module is loaded under a prefix, all symbol references within its definitions are rewritten to fully qualified names. Example: sum -> math.sum.

Circular import protection

• The loader maintains an active_stack set. If a module is encountered while already on the stack, ValueError is raised.

Loader API

assemble_env(node, script, target) resolves a definition from a .aex file and returns an Env with only the definitions transitively referenced by the target (tree-shaking). This replaces the old compile function.

• node — an Astreum Node instance, or None when only file-based imports are used.
• script — path to the root .aex script (absolute or relative).
• target — name of the definition to resolve. May include dots for imported modules (e.g. "math.calc_sum").
• Returns an Env with the resolved definitions. Use env.get(name) to retrieve a definition, then evaluate it with Machine.run().
• Modules are parsed lazily — only those reached via symbol references from the target are ever loaded.

from astreum.machine import Machine, assemble_env

env = assemble_env(node=None, script="./hello.aex", target="main")
result = Machine(node=None).run(env.get("main"), env)
# result = Int(42)

9.

Error handling

Operator errors

• Operators raise OpError on type mismatches, stack underflow, out-of-bounds access, or other semantic errors.
• Bare form — the error is caught and NIL is pushed. Execution continues with NIL on the stack.
• Tagged form — appending ? to any operator name wraps the result as a tagged pair. The tag is in the tail (terminal) position:
  • Success: (value . ok) — or (NIL . ok) for void operators (drop?, print?, etc.)
  • Error: (msg . err) — the string describes what went wrong.

Meter errors

• MeterExceededError is never caught and always propagates, halting evaluation.