PathMap

help edit space_dashboard
Draft — This content has not been approved for publication.

Author: Luke Peterson

Repo: PathMap

Status: Foundational substrate, sibling to MORK. Operational as a low-level trie crate; pathmap-book intro is complete but the database section (2.00.00_database_intro.md) is a GOAT/TODO stub.

What PathMap Is

PathMap is a prefix-compressed triemap (radix tree) for byte-keyed values, with structural sharing and an algebraic operation set. It is functionally a superset of HashMap<Vec<u8>, V> with additional path-prefix composition and grafting, dangling-path handling, structural sharing across keys, and primitives optimized for large data sets and multi-threaded use. It is the low-level data structure that MORK's path algebra and Zipper Abstract Machine sit on top of.

Relationship to MORK

PathMap is declared as a path-relative dependency of MORK at MORK/Cargo.toml:28-32 (../PathMap/ with jemalloc, arena_compact, nightly features). It is a sibling repo, not a bundled crate — the AtomSpace Backend Integration Cluster Pilot Source 3 (2026-04-29) lifted PathMap's wiki classification from "MORK component" to "foundational MORK trie substrate, independent repo" precisely because the MORK Cargo.toml reaches outside the workspace to consume it.

  • What MORK adds on top of PathMap: S-expression encoding (expr/ crate), Zipper Abstract Machine execution (kernel kernel/src/sinks.rs et al.), MM2 dataflow language, MeTTaTron special forms, sources/sinks resource model, server branch HTTP API.
  • What PathMap provides: The prefix-compressed trie, structural sharing, path-algebra primitives (prefix scans, union/intersection of posting lists, anti-join), dangling-path support, and the building blocks the ZAM cursor navigates.

pathmap-book Status

The pathmap-book documentation distinguishes implementation-complete sections from design-stage stubs:

  • Complete: Introduction, structural-sharing description, basic API surface.
  • Stub (TODO/GOAT): The database section at pathmap-book/src/2.00.00_database_intro.md outlines but does not deliver trie segmentation, schemas, indices, permissions, and concurrency. PathMap is "foundational MORK trie substrate", NOT "complete database layer."

Lean / ZAM Formalization Caveat

The MORK family includes Lean formalization work for the Zipper Abstract Machine (notably mork-mm2-pathmap-formalization.tex by Zarathustra Goertzel and Oruži, plus theorem files in the Mettapedia Lean tree). These prove ZAM soundness theorems against a formal model of the path algebra. Lean theorems do not establish Rust production equivalence — the Lean ZAM is not wired into the Rust kernel, and the bridge between formal model and production implementation is not currently verified end-to-end. Citing Lean results as evidence for Rust correctness requires explicit bridge verification.

Independence and Reusability

PathMap is, in principle, usable outside MORK as a generic prefix-compressed triemap library. As of 2026-04-29 there is no documented production user of PathMap independent of MORK; the API surface is shaped around MORK's needs (path algebra, structural sharing for S-expressions, jemalloc-backed arena allocation). A general-purpose triemap library would likely require API stabilization and documentation work that the current pathmap-book does not provide.

Implementation Anchors

  • PathMap (primary) — Rust crate; nightly toolchain required for the same generators/coroutines/SIMD features MORK uses.
  • pathmap-book — Documentation (intro complete; database section stub).
  • Consuming repo: MORK via ../PathMap/ dep in workspace Cargo.toml.

Source

This card was created by the AtomSpace Backend Integration Cluster Pilot (2026-04-29) per Source 3 R3.4 / R3.I4 / R4.K1. Cluster archive at scripts/archive/atomspace_pilot/source3_mork_substrate/.



Discussion