Crate pertaro 

PERTARO

Pruned Expert Regrounding Trie via Answer-set Reduct Optimization.

A #![no_std], zero-heap neuro-symbolic micro-expert primitive that packs a 5-tier ternary decision trie (3^5 = 243 leaves) plus a 13-state in-band control envelope (243..=255) into one exact 256-byte cache-aligned word.

Byte contract

One byte has 256 states: 0..243 are 5-trit coordinates, 243..=255 are the 13 Sentinel control states. A Word256 is header-first:

offset	field	meaning
0..8	hash: u64	xorshift64 seed of the default leaf field
8..12	parent: u32	lineage link to the parent horizon word
12..255	trits[0..243]	243 leaf deltas or in-band sentinels
255	trits[243]	root sentinel: the active horizon phase

Default field

The seed’s xorshift64 stream is turned into 243 uniform Z_243 digits by radix-243 extraction: 243^8 < 2^64, so every state below 243^8 holds eight exact, independent digits; states at or above it are rejected, not reduced. No % 243 bias anywhere.

pertaro

Pruned Expert Regrounding Trie via Answer-set Reduct Optimization.

pertaro is a #![no_std], zero-dependency, zero-heap Rust primitive for cache-resident neuro-symbolic inference and bounded-horizon state planning. It packs an entire 5-tier ternary decision trie (3^5 = 243 leaves), an 8-byte deterministic PRNG seed, a 4-byte lineage link, and a 13-state in-band control envelope (243..=255) into an exact 256-byte cache-aligned word (Word256).

---

Core Architecture: The 243 + 13 = 256 Isomorphism

A single byte (u8) has 256 possible states (0..=255). pertaro partitions both the value space of a byte and the structural layout of a 256-byte cache block along the exact same boundary:

1. Coordinate Space (0..243): A 1-in, 3-out ternary trie expanded across 5 tiers yields 3^5 = 243 leaves (MAX_PACKED = 243). Values 0..243 represent packed 5-trit coordinates or modular residual deltas in Z_243.
2. In-Band Control Envelope (243..=255): The remaining 13 byte values (SENTINEL_COUNT = 13) act as in-band non-monotonic control sentinels directly inside the payload:
   • 243 (Sentinel::NullNode): Terminal Answer Set leaf. The deterministic xorshift64(seed) default prior holds at zero delta cost.
   • 244 (Sentinel::MersenneOverflow): Out-of-band arithmetic overflow marker.
   • 245 (Sentinel::Tombstone): Branch defeated by integrity constraints under the Gelfond-Lifschitz reduct.
   • 246 (Sentinel::BusIndirect): Horizon boundary trigger signalling a Tier-5 reground jump.
   • 247..=255 (Sentinel::Phase5 .. Sentinel::Phase13): Horizon / phase anchors.

---

Exact 256-Byte Header-First Memory Layout

Every Word256 / PertaroExpert243 instance is aligned to 256 bytes (#[repr(C, align(256))], four 64-byte CPU cache lines) with compile-time verified field offsets:

Byte Offset	Size	Field	Description
0..8	8 B	hash: u64	Deterministic xorshift64 seed and FNV-1a content signature
8..12	4 B	parent: u32	Lineage link to the parent 5-tier horizon word
12..255	243 B	trits[0..243]	3^5 = 243 ternary trie leaf deltas (0..243) or in-band Sentinels (243..=255)
255	1 B	trits[243]	Active root_sentinel / horizon phase byte (243..=255)
Total	256 B	Word256	128 complete 5-tier trees fit inside a single 32 KB L1 data cache

---

Quick Start

This example ships as examples/quick_start.rs and is compiled by cargo check --examples.

use pertaro::{PertaroExpert243, Sentinel, Word256, MAX_PACKED, ROOT_SENTINEL};

fn main() {
    // 1. A 256-byte word with a seed, a parent link, and in-band sentinels.
    let mut raw = Word256 {
        hash: 0xcbf2_9ce4_8422_2325,
        parent: 0,
        trits: [0u8; 244],
    };

    // Address leaf [1, 0, 2, 1, 2] in the 5-tier ternary trie (each tier in 0..3).
    let target_leaf = PertaroExpert243::trie_index([1, 0, 2, 1, 2]);
    raw.trits[target_leaf] = 42; // residual override: +42 mod 243

    // Stamp a defeated branch with an in-band Tombstone (245).
    let defeated_leaf = PertaroExpert243::trie_index([2, 2, 0, 1, 0]);
    raw.trits[defeated_leaf] = Sentinel::Tombstone as u8;

    // Mark the root horizon sentinel at trits[243].
    raw.trits[ROOT_SENTINEL] = Sentinel::NullNode as u8;

    // 2. Wrap in the zero-cost view and materialize.
    let expert = PertaroExpert243(raw);
    let materialized: Word256 = expert.materialize();

    assert!(materialized.trits[target_leaf] < MAX_PACKED);
    assert_eq!(materialized.trits[defeated_leaf], Sentinel::Tombstone as u8);

    // 3. Reground the winning Tier-5 leaf (0..243) into a fresh seed.
    let next_seed = expert.reground_seed(target_leaf as u8, Sentinel::BusIndirect);
    assert_ne!(next_seed, expert.seed());
}

---

Key Guarantees

• Unbiased radix-243 extraction. Because 243^8 = 3^40 = 12,157,665,459,056,928,801 < 2^64, materialize() extracts 8 independent, strictly unbiased base-243 coordinates (0..243) per xorshift64 word by rejection sampling below 243^8, avoiding u8 % 243 modulo bias entirely.
• Strict const bounds. trie_index enforces tier digits in 0..3 and reground_seed enforces winning leaves in 0..243, so a sentinel is never folded as a leaf.
• Zero unsafe, zero heap. #![no_std] and #![forbid(unsafe_code)], with no dynamic memory allocation anywhere.

---

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Structs

AnswerSetMask

A 256-bit set over atoms 0..=255: a candidate or derived answer set S over the 243 leaves. Four u64 words, no heap.

PertaroArena121

The complete 4-tier L1-resident ternary trie arena: 121 words, 30,976 bytes.

PertaroExpert243

Zero-cost view over Word256: the payload as a 5-tier micro-expert.

Word256

Sealed 256-byte header-first word, aligned to 256 bytes (four cache lines).

Enums

Sentinel

The 13 in-band control states, bytes 243..=255.

Constants

ARENA_BYTES

Exact byte footprint of the arena: 121 * 256 = 30,976 bytes.

ARENA_NODES

Nodes in a complete 4-tier ternary routing arena: 1 + 3 + 9 + 27 + 81 = 121.

ARENA_TIERS

Tiers resident in the arena: 0..=4.

DIGITS_PER_WORD

Digits one accepted xorshift64 state yields.

FNV1A64_BASIS

Canonical FNV-1a 64-bit offset basis.

FNV1A64_PRIME

Canonical FNV-1a 64-bit prime.

FRONTIER_NODES

Frontier nodes: 3^4 = 81.

FRONTIER_START

Index of the first Tier-4 frontier node: 1 + 3 + 9 + 27 = 40.

L1_BUDGET_BYTES

The L1 data cache size the arena is sized against.

LEAVES

Trie leaves: 3^5 = 243, one byte each.

MAX_PACKED

Count of 5-trit coordinate values in one byte: 3^5 = 243.

PAYLOAD_BYTES

Payload width: 243 leaves + 1 root sentinel.

RADIX_243_POW_8

243^8: the rejection threshold for unbiased radix-243 extraction.

ROOT_SENTINEL

Payload index of the root sentinel byte, the one byte past the leaves.

SENTINEL_COUNT

Count of in-band control states: 256 - 243 = 13.

TIERS

Trie depth: five ternary tiers address one leaf.

Functions

fnv1a64_fold

FNV-1a 64-bit fold of bytes onto a running hash. Start from FNV1A64_BASIS. The single FNV home in this crate.

xorshift64

One xorshift64 step (13, 7, 17). 0 is a fixed point.