Compiler architecture

The portable compiler is a tricu program. It receives source characters and already-resolved external trees, then produces executable trees and diagnostics. The Haskell host supplies reduction, file IO, hashing, verified transport, and bundle packing.

Language defines source semantics; Modules defines acquisition and publication; Compiler rebuilding explains how to change and verify the compiler.

Pipeline

Stage	Implementation
Finite-stream replies and combinators	lib/parser.tri
Scanning, positions, and spans	lib/lexer.tri
Located source tokens	lib/source/lexer.tri
Surface syntax	lib/source/ast.tri
Expressions and definitions	lib/source/parser.tri, program.tri
Pattern parsing and equation grouping	lib/source/equations.tri
Free names and dependency ordering	lib/graph.tri, lib/source/order.tri
Scoped core and de Bruijn resolution	lib/source/core.tri, resolve.tri
Equation lowering	lib/source/pattern.tri
Optimized and stable abstraction	lib/source/compile.tri, stable.tri
Unit entrypoints	lib/source/unit.tri
Modules, locks, builds, and maps	lib/source/{module,lock,build,map}.tri
Object and bundle publication	lib/source/{object,bundle}.tri

Each stage preserves locations needed by later diagnostics. Grouping retains its outer span. Pipes become applications, do uses its supplied operator, lists become canonical Fork cells, and local bindings become scoped applications. A singleton all-name function head takes the ordinary lambda path; other equation groups retain located patterns until resolution.

The parser protocol defines consumption, commitment, rollback, and repetition. Binary and HTTP consumers share those primitives with the compiler.

Name lookup

Stable module compilation shares a compiler-private persistent index between name analysis and external-name resolution. lib/source/index.tri indexes the Leaf/Stem/Fork preorder of finite tree keys; it does not hash identifiers or inspect stored executable values. Construction preserves first-binding precedence, and insertion of a compiled local creates a new index version. Index callers supply proper binding lists and finite keys.

Association-list lookup remains available. Both paths share pattern/scope resolution, diagnostic sequencing and ordered compilation; the index does not replace duplicate/shadow checks, reorder dependency edges, or change cycle selection. Compiler helper function trees are representation-sensitive and may change when this wiring is refactored, even when compiled application trees agree. See the name-index controls.

Unit interfaces

lib/source/unit.tri exports:

compileSource environment sourceCharacters
  : Result (pair selectedRoot compiledDefinitions) Diagnostic

environment = association list of (qualifiedName, rawTree)

Definitions are returned in stable dependency order. Selection prefers local main, then the optional final expression. Missing both produces diagnostic 32. Every definition is checked for missing names and cycles; normalization of unused bodies is demand-driven. Unit definitions can shadow supplied externals. Native module staging adds the stricter import/local-name collision checks.

compileGateProgram projects the selected root. compileGateProgramOutput returns the root and definitions. compileModuleDefinitions and compileStableModuleDefinitions select optimized and stable definition compilation, respectively. The public compileSource interface retains its existing unit backend; application authoring selects the stable graph entrypoint through build-stable.arboricx.

Successful compileSource replies have a Leaf remainder; failures preserve the gate output's diagnostic and remainder. Source input at these APIs is a character list. Native headers are processed by the module layer before the body reaches the unit compiler. Native modules publish their declared interface; the unit parser also supports bare expressions.

Stable and optimized lowering

Stable lowering preserves normal-form construction while abstracting binders. Potentially executing applications stay residual until abstraction completes. Direct top-level function self-recursion and explicit local recursion use a delayed fixed point with lexical captures.

The stable backend prunes a binder-independent application only when it is certified constructor-only: its function is a known Leaf or Stem and its argument is a represented value or another certified construction. Opaque variables may be stored but are not known callable shapes. Fork applications, unknown calls, and constructors containing unproved computations remain residual. There is no general independent-expression or eta shortcut. Constructor shape and the minimum free index are cached on private residual nodes and updated during abstraction/shifting; they do not enter output trees or diagnostic locations. Inspectable function representations can differ from older stable compilers even when application results agree.

The retained optimized backend prunes binder-independent subtrees into constant functions and provides named abstraction strategies for comparison. Its recursive programs use explicit fixed points. Work that normalizes while building a closed export may need to stay beneath an argument-dependent branch; consumed-data-first recursion and lazy handlers can matter on this backend. These are representation and demand choices to test with a selected artifact, rather than general source style rules.

Canonical numbers, strings, Booleans, and lists have shared encodings. Function trees are backend-sensitive, including functions embedded in data. For a fixed compiler and identical inputs, complete outputs and diagnostics must agree structurally. Comparing backends requires explicit expectations for intensional observations as well as application results.

Compilation includes normalization. A timeout, cancellation, or resource limit is a host outcome; frontend errors are structured diagnostics. Use bounded probes for abstract-input function construction as well as concrete application.

Pattern lowering

sourceLowerEquations equations consumes compiler-built patterns and resolved core bodies, returning Result Core Diagnostic. It validates positive consistent arity, unique captures, supported pattern tags, and final irrefutable coverage.

A body's indices address captures in reverse introduction order, followed by surrounding lexical binders. Pins resolve in the surrounding scope. Lowering aliases captures to argument and structural-handler binders and rewrites indices beneath nested lambdas and lists. The optimized lowerer delays constructor branches; stable lowering uses direct dispatch for eligible outer splits only. A miss shares a lazy continuation to the next equation. The executable contains ordinary tree operations rather than a runtime pattern interpreter.

Capture and pin-collision checks precede free-name analysis. Sequential local groups become nested bindings; recursive groups add their self binder explicitly. Preserve opaque external trees, capture order, spans, and unselected-branch demand when changing these passes.

Outer-constructor factoring

The source.pattern lowerer factors one outer-constructor test per equation group. The first row must reach that test: every preceding column in every row must contain only a wildcard or plain capture. At the selected column, only constructor, wildcard, and plain-capture patterns qualify. Literal, pin, and whole patterns at that column retain sequential lowering. No independent argument or child tests are moved ahead of earlier tests.

Each constructor branch retains compatible rows in source order, reuses the already available children, and preserves the original subject for fallback captures. Child expressions shift through failure binders alongside the ordinary capture context. A row guaranteed to match within that branch needs no failure continuation; sequential lowering likewise omits the final irrefutable row's unused continuation. Nested refutable patterns keep their existing left-to-right matching and saved-sibling protocol. Validation still checks all authored rows.

The stable definition compiler selects resolveStableGateAst and sourceLowerStableEquations. For the factored outer split it emits ordinary triage with a value for Leaf and child-binding lambdas for Stem/Fork, rather than a selected unit continuation. Stable abstraction keeps applications residual under the original argument binders during complete function construction. The Leaf body gains no binder and therefore needs no extra shift. Nested refutable tests, sequential fallbacks and failure continuations retain their delayed protocol. resolveGateAst and sourceLowerEquations retain optimized-backend lowering, including its branch-construction safeguards.

Factoring can change compiled function representations; intensional tree observations remain compiler-dependent. It does not change evaluator rules, data encodings, or the equality implementation. The comparison probe checks results, diagnostics, demand, code-generation targets, and costs using explicit compiler identities. Source-level checks do not substitute for compiler artifact acceptance.

Located representations

Lexer token kinds:

1 t       2 identifier  3 (      4 )       5 :       6 newline
7 number  8 string      9 [     10 ]      11 =      12 let
13 in    14 where      15 <|    16 |>     17 do     18 <-
19 @     20 ,          21 |     22 {      23 }      24 ^
25 case  26 of         27 rec

Identifier payloads are character lists; t carries its spelling. Number and string tokens carry decoded canonical values. Punctuation payloads are Leaf. Tokens retain half-open spans with character offsets and line/column positions.

Surface AST kinds are 1 leaf, 2 name, 3 application, 4 lambda, 5 grouping, 6 number, 7 string, 8 list, 9 local binding, 10 pipe, 11 do block, 12 equation group, 13 pattern, 14 expression match, and 15 recursive local binding. A match pairs its subject with a unary equation group. Recursive locals retain the local-binding payload. Patterns use lowerer tags 0..7; pins carry located names until resolution. Constructors and accessors beside the source are the interface to these encodings.

Diagnostics contain code, expected, found, location, and contexts. Important codes include 20 unresolved name, 30 duplicate definition, 31 dependency cycle, 32 missing root, 40 layout/missing-body errors, and 48 pattern or recursive-function validation. Cycle diagnostics identify an actual cycle member. Missing-name diagnostics retain the original occurrence's span.

Native application boundary

The CLI loads a pinned sourceBuildGraph export. The selected tree owns header staging, dependency resolution, compilation, receipts, and cache policy. The host frames its IO action and supplies the packaged bundle digest as compiler identity. Explicit toolchain overrides retain their verified export-object identity. The host grants reads to the source directory/store and writes to the application store. Application IO receives its own grants.

Indexed tool objects preserve sharing through loading. Their object hashes differ from flat tree-term hashes, so changing transport representation also changes the explicit compiler identity used in receipts. Native module publication uses indexed objects with the same name-neutral format as CLI import. See Storage for these identities and the complete-interface cache rules.

Haskell evaluation boundary

The production host imports Runtime, whose implementation is split into Runtime.Tree (trees/reduction), Runtime.Value (canonical values), Runtime.Presentation (display), and Runtime.Merkle (native DAG helpers). The historical Haskell frontend and its recovery syntax have been removed. Executables, tests and benchmarks all use this source-free host API. Source test programs compile through retained authenticated portable compiler artifacts; library tests may instead apply published trees directly. The ast display format renders tree constructors directly, without constructing source ASTs.

ContentStore.Executable shares authenticated flat/indexed loading across host entrypoints. Object loading checks kind, identity and encoding; named export loading additionally authenticates the manifest and checks the export ABI. Whole-interface and selected-export loads authenticate the manifest once. The streaming flat-bundle packer remains separate: it must not reconstruct expanded trees just to reuse the executable loader.

PortableCompiler supervises tool selection, loading, deadlines, restricted IO and publication verification for file compilation and interactive sessions. It owns no source semantics. Its failures are IO errors; CLI and REPL boundaries choose how to report them rather than library code terminating the process. REPL startup authenticates the selected worker under the compiler deadline, without applying it. Explicit toolchains never fall back to packaged data.

Runtime.Tree.T has lazy constructor fields, and Runtime.Tree.apply implements the kernel rules without an explicit application/thunk node. Pending reductions live in Haskell thunks. Constructor application returns an outer Stem/Fork without forcing its children; constant application ignores its discarded argument; triage inspects the discriminator only as needed. This is demand-driven, call-by-need execution, not a separate full-normalization pass on every call.

Indexed loading reconstructs shared inert subtrees. Distribution reuses its argument, but sharing a function tree does not establish a global application cache or an exact once-per-source-expression cost model. Compiler abstraction and host optimization affect allocation and sharing.

Observation supplies further demand. toList validates the entire finite spine before returning success, without forcing its elements; toString additionally decodes all characters. Full tree rendering, flat serialization, and indexed publication traverse complete tree structure. Indexed publication can reuse physical sharing but cannot serialize unevaluated Haskell computations or infinite trees. Stored --profile follows normal rendering demand; the explicit --profile-full-result option additionally forces the complete result using a traversal-local physical-node memo (TreeObservation.forceTreeShared). Nodes are marked complete only after their children, so a cycle is not accepted as a finite normal form. Infinite inputs still require external resource limits.

The Evaluation demand boundaries tests in test/Spec.hs use poisoned host subtrees for positive/negative demand controls, check distribution sharing, and apply fully constructed stable function trees to partial inputs or an infinite producer. Existing local-control/parser controls check ignored subjects, siblings, and handlers; transport tests check physical sharing after decoding. These are focused implementation/behavior checks, not a proof of normalization, a complete sharing specification, or an eager-evaluator compatibility claim.

Checks

The test suite has independent token/span, AST/core, scope, diagnostic, pattern, and recursion expectations. Demand controls check opaque or divergent unused fields. Integrity checks cover module, receipt, object, and bundle publication. Testing separates retained-reference tests from candidate execution and fresh-generation acceptance.

Investigating optimized construction

For the retained optimized backend, test whether a complete function tree can be published while its runtime inputs are still abstract. A concrete application alone may hide construction-time work. Useful experiments include:

• Inspect consumed data before known counters, bounds, prefixes, or state.
• Keep fixed points beneath public argument-taking wrappers, and delay branches containing recursive work with the appropriate library continuation protocol.
• Destructure fixed-format records finitely rather than using a recursive slice driven by a known count over an unknown input.
• Advance through the consumed structure, with small recursive calls and constant-time state construction. Repeated append or restarting from the original input can add both normalization and traversal costs.
• Reuse established invariants, such as backward-only node references, to search an already-built prefix instead of rebuilding from the entire input.

A generated unused lambda binder alone may still reduce closed work under a constant abstraction. When publication stalls, isolate reachable dependencies with small constant replacements, then restore them one at a time. The first export to stall need not contain the root cause. These are diagnostic techniques for a selected compiler, not requirements imposed on stable source style.

Experimental staging profiles

The three lib/source/*experiment.tri modules are opt-in compiler research, separate from canonical syntax and the production compiler map. Their contracts below describe the experiments; ordinary programs use the stable language. Testing documents bounded Haskell-only checks using explicitly prepared artifacts.

Trusted compiler IR

staging-experiment.tri accepts compiler-built Branch(condition, yes, no) and Recur(nextState) nodes. Branch lowering inserts lazyBool continuations and makes each delayed application's function depend on the continuation's force argument:

f x  ->  (triage f t t token) x

The supplied Leaf token selects f. Operands, lambda bodies, and lists are transformed recursively; external tree payloads stay opaque. Conditions remain ordinary evaluation unless enclosed by another delayed branch. Private kind 98 marks already-protected continuations: shifting treats it as a binder, outer guard passes leave it opaque, and final syntax lowering replaces it with a lambda. Repeatedly guarding generated continuations can greatly expand the output.

The IR stageList(done, step) constructs input state -> result. Leaf or non-cons input calls done; a Fork supplies its head and state to step. Recur advances on the original tail. Step indices are state 0, head 1, then outer binders; inserted self/tail bindings use binder-aware remapping. done can read state 0 but has no other free outer binders. Recur is meaningful only inside a step. These are trusted-IR conventions, not validation of arbitrary user trees.

Authored conditional and list forms

staged-conditional-experiment.tri recognizes stageIf condition yes no after lexical resolution. Leaf selects no; Stem/Fork select yes. Only the selected branch's applications are released by the force token. Work outside the branch expressions remains ordinary evaluation. A fourth argument applies to the selected result. Bare or partial uses of the compiler binding produce arity errors.

Local bindings may shadow construct names. Top-level definitions must be distinct from imports and these compiler bindings. Private External marker trees identify the constructs; their exact values are reserved in supplied environments and compiled definitions. Wrapping a construct in an ordinary function does not give that function control over its caller's argument syntax.

staged-list-experiment.tri supports:

main input = (stageList input []
  (state : state)
  (head state : pair head (stageNext state)))

The done callback is an inline state lambda, and the step callback is an inline head/state lambda. Leaf and non-cons input finish; Fork selects the step. stageNext nextState recurs on the original tail. Returning another value stops; non-tail result construction is permitted. This is distinct from the library's listContinue/listStop suffix-retaining protocol.

Generated callbacks depend on a Leaf token derived from the current input constructor, without inspecting an unused head or tail. Initial state and conditions remain outside callback staging. Remapping preserves outer captures and nested result lambdas. The profile requires inline callbacks, excludes nested stageList inside them, and rejects stageNext outside a step, in a condition, in its own next-state expression, or escaping as a value.

demos/staged-newlines/app.tri is a second consumer: CR emits LF, immediately following LF is skipped, and other characters pass through. Its application contract is finite Unicode text; the underlying list form also terminates on non-cons tails. Formatter replacement fragments remain test inputs, separate from the production formatter.

Checks must force complete compiled trees before application, then independently publish and execute them. Finite application agreement does not establish equal function representations. Timeouts bound observations, not termination proofs.

Preserve non-strict arguments

An ordinary-lambda staging experiment derived a force token from every argument's constructor. It was rejected because it made discarded arguments strict:

main input = (ignored : succ 22) (loop [1])

With a divergent loop and suitable supplied helpers, canonical execution could return 23 while the staged version demanded the ignored argument. Any future staging design must retain this negative control, lexical capture behavior, complete-tree construction checks, and intentional intensional observations.

Native source decoding boundary

readSourceFile returns both exact file octets and strictly decoded Unicode scalar characters. sourceBuildReadTriPath stages characters and retains octets for source fingerprints and receipts. Mapped staging validates/transforms the scalar source. Native overlays use the captured original octets directly; encodeSourceText produces UTF-8 octets for transformed overlay hashes and atomic writes. Legacy header rewrites retain their existing line handling. General readFile remains binary.

Malformed UTF-8 and an initial BOM are rejected. No Unicode normalization occurs; positions count scalars, not bytes or display cells. Existing explicit-scalar lexer fixtures check character handling, not file decoding; the opt-in test/native_source_utf8.py checks the file boundary with current consumers. The included compiler has not yet been republished with this candidate boundary. See source characters.