Forward Track: Bootstrap and Self-Modeling

Forward-looking design document. Architectural commitments about how the language describes its own behavior using its own constructs. Phase 1 commits to constraints that keep the bootstrap paths open; later phases deliver the actual self-modeling work.

1. Framing

The question that triggered this document: will there be a point where certain behaviors need to be modeled natively in the language rather than hardcoded in the compiler?

The short answer is yes, several times, in three distinct senses. The longer answer is that self-modeling — the language describing its own machinery using its own constructs — is the load-bearing mechanism for several Phase 2+ deliverables, especially AD-as-effect-handler. Getting Phase 1's design right means leaving the right doors open without trying to build through them yet.

The three senses of bootstrapping, in order of increasing ambition:

1. Standard library in the language itself — linear, relu, softmax, etc. as user-written functions, not compiler primitives.
2. Compiler transformations expressed as in-language handlers — AD, sharding propagation, tile lowering as constructs in the language rather than passes in OCaml.
3. Compiler self-hosting — the OCaml compiler eventually rewritten in the language itself.

Sense 3 is a long-term maturity milestone (Phase 8+). Senses 1 and 2 are on the critical path. This document spends most of its weight on Sense 2 because it is the most ambitious and the one with the most direct implications for Phase 1's architectural decisions.

2. Sense 1: Standard library in the language

Once Phase 1's compiler can compile programs end-to-end, the natural next deliverable is a small standard library: not compiler primitives but user-written functions composing the primitives. Things like:

• linear : Tensor[F32, [B, S, D]] → Tensor[F32, [D, V]] → Tensor[F32, [V]] → Tensor[F32, [B, S, V]]
• relu, gelu, silu, tanh
• layernorm, rmsnorm
• softmax_stable (with the max-shift trick)
• attention_scores, attention (multi-head, with softmax)
• mlp (linear → activation → linear)
• A few common loss functions (mse, cross_entropy if gather is in)

These should be user-written functions in the language, shipped as a package alongside the compiler, not hardcoded compiler primitives.

2.1 Why this is more than a convenience

The standard library is a direct test of the type system's expressiveness. If layernorm is expressible cleanly in the language, the type system handles compositions of reduce + broadcast + arithmetic correctly. If attention_scores is expressible, the matmul + softmax + transpose pipeline composes. If a stdlib function can't be written without an escape hatch (per Phase 0 §1.3's controlled unsoundness), that's a foundation flaw — and a flaw that needs to be discovered in Phase 1 rather than Phase 5.

This is the same discipline as the real-world examples walkthrough, raised to a deliverable. The walkthrough showed which examples are awkward; the stdlib forces decisions about which ones to fix versus accept.

2.2 Acceptance criterion

A representative stdlib for Phase 1 includes at least:

• linear (handling the broadcast-of-weight pattern from real-world-examples §3.1)
• relu, gelu, silu (elementwise unary)
• rmsnorm (reduce + broadcast + arithmetic)
• softmax_stable (numerically-stable softmax via max-shift)
• attention_scores (the Q @ K^T computation, possibly with the variadic-batch matmul from Section 4 making it less awkward)
• A complete mlp and transformer_block_partial (from real-world-examples §5)

Acceptance: each of these compiles cleanly with zero axiomatic assertions. Reshape volume axioms in real implementations are tolerated but flagged. If a stdlib function can't be written without escape hatches, the foundation needs revision before Phase 2.

2.3 Phase 1 commitment

Add the proto-stdlib to the Phase 1 test fixtures. This is essentially free work — the test fixtures need to exist anyway — and it converts a vague "the type system should be expressive" into a concrete acceptance test.

3. Sense 2: Self-modeling — compiler transformations in the language

The more ambitious and more interesting kind of bootstrap. Compiler transformations are expressed in the language, not in OCaml.

The motivating example, from memo 2 and Phase 0:

Reverse-mode AD is a handler written in the language. The user writes with reverseMode handle f x; the handler intercepts every operation, builds the backward computation, and produces both the forward result and its gradient.

This is not a compiler pass written in OCaml that operates on the IR. It is a language-level construct — a handler — that happens to implement what a compiler pass would do.

Same pattern recurs at multiple later phases:

• Phase 3 / 4: sharding propagation is a typed transformation. GSPMD-style sharding inference is essentially type inference over a sharding-refinement axis, expressed in the language's type system rather than in a separate compiler pass.
• Phase 5: tile IR is a sub-language of the main language. Kernel authoring lives in the same language as algebraic-level model code, with the same type system and the same lowering pipeline.
• Phase 4: typed dataframes (per the Arrow forward track) add a new type constructor and new operations to the language via the library-author extension mechanism.

The unifying observation: what other ML systems implement as compiler internals, this project expresses as language constructs.

3.1 What "self-modeling" means precisely

Concretely: every compiler pass that transforms typed programs (rather than purely lowering them) should be expressible as a function in the language. The function takes a typed program (or part of one) and produces a transformed typed program. The transformation rules are program rules, not OCaml-level rewrites.

Three benefits:

1. Composability. Language-level handlers compose by stacking. AD + sharding compose by composing their handlers; the user picks the order. OCaml-level passes don't compose this way; they're sequential and order-dependent in implementation rather than semantics.

2. Verifiability. A handler in the language has a type. A handler's type captures what it transforms and what it preserves. Verification (Phase 6) can prove handler properties using the same Lean 4 mechanization that verifies type soundness. OCaml-level passes need separate verification machinery.

3. User extensibility. Library authors who want a custom transformation (a new AD variant, a custom sharding strategy, a domain-specific optimization) write a handler. They don't have to fork the compiler.

3.2 The cost

Self-modeling is more constrained than just-write-a-compiler-pass. The handler has to type-check; the language has to be expressive enough to write the handler; effects in the language have to be powerful enough to express the transformation.

For AD specifically: reverse-mode AD requires manipulating computation graphs, allocating fresh adjoint storage, traversing the graph backward. Expressing this as a handler requires the language to support:

• Capturing operations as values (so the handler can record what to differentiate).
• Allocating intermediate tensors (so adjoints can be stored).
• Iterating over recorded operations (so the backward pass can walk them).
• Higher-order programming (so the handler can be parameterized over the function being differentiated).

Phase 2's effect-handler design (memo 2 §5) commits to these capabilities. Whether the implementation actually supports them is the load-bearing risk for self-modeling.

3.3 The minimum viable demonstration

The earliest Phase 2 deliverable should be a proof-of-concept showing that reverse-mode AD over a small program produces correct gradients via a language-level handler. Specifically:

• A program: f(W, b, x) = mse(linear(x, W, b), y_target) for fixed y_target, where mse is mean-squared error.
• An AD handler in the language.
• Run with reverseMode handle (f W b x) and produce both f(W, b, x) (a scalar loss) and ∇_W f, ∇_b f (gradients).
• Verify: gradients match a PyTorch reference within FP tolerance.

If this works, the self-modeling thesis is validated and Phase 2 is on track. If it doesn't — if expressing the AD handler hits language-level limitations or if the resulting gradients are wrong — the framework needs revision before more Phase 2 code is written.

This is the same "discover-the-foundation-is-wrong-cheaply" discipline that Phase 0 used and Phase 1 inherits. The cost of a failed PoC is bounded; the cost of building Phase 2's full AD on a flawed foundation compounds.

4. Sense 3: Compiler self-hosting

The classic meaning. Eventually, the OCaml compiler is rewritten in the language itself. Stage 0 is OCaml; Stage 1 is the compiler-in-the-language compiled by Stage 0; Stage 2 is the Stage 1 compiler recompiling itself.

For this project, self-hosting is deferred to Phase 8 or beyond. The reasons:

1. The language isn't expressive enough yet. A compiler needs string manipulation, file I/O, error handling, recursive data structures, hash maps, and a thousand other general-purpose features. The AI-native scope doesn't include any of these. Self-hosting requires expanding the language well beyond its current ambition.

2. OCaml is the right tool for the job. ML-family languages are built for compilers; pattern matching, ADTs, type inference, garbage collection are exactly what compiler-writing wants. Replacing OCaml with our language would be a downgrade in compiler-writing ergonomics — a vanity exercise rather than a practical improvement.

3. It's not on the critical path. Self-hosting doesn't unlock new capabilities for users. Production AI/ML compilers (PyTorch's compiler, JAX, XLA, Mojo) are all written in C++/Python/etc., not in themselves. Self-hosting is a maturity milestone, not a prerequisite for usefulness.

If the project gets there eventually — if surface syntax (Phase 7) makes the language expressive enough and there's appetite for the project — self-hosting becomes possible. But it's not a goal that should drive earlier-phase decisions, and Phase 1's architecture should not bend to accommodate it.

5. Per-phase bootstrap progression

A roadmap for when each kind of bootstrap becomes relevant:

The progression has a shape: Phase 1 sets up the constraints, Phase 2 validates the load-bearing thesis, Phases 3–5 extend it across new transformations, Phase 6 verifies it, Phase 7 packages it for human users. Self-hosting is the speculative coda.

6. The Phase 2 critical path: AD-as-handler PoC

Worth elevating because of how much depends on it.

The thesis under test: reverse-mode AD over the language is expressible as a handler in the language, with correct semantics, with no compiler-internal AD pass required.

The minimum viable demo (per §3.3):

let mse [B] (pred : Tensor[F32, [B]]) (target : Tensor[F32, [B]]) 
    : Tensor[F32, []] =
  let diff = pred - target in
  let sq = diff * diff in
  let total = reduce[sum] sq in
  scalar_div total B   -- scalar_div is a primitive

let f [B, D] (W : Tensor[F32, [D, 1]]) (b : Tensor[F32, [1]])
    (x : Tensor[F32, [B, D]]) (target : Tensor[F32, [B]])
    : Tensor[F32, []] =
  let pred = squeeze (linear x W b) in
  mse pred target

-- The PoC:
let demo () =
  let W, b, x, target = ... in
  let (loss, grads) = with reverseMode handle (f W b x target) in
  -- grads : (Tensor[F32, [D, 1]], Tensor[F32, [1]])
  let (gradW, gradb) = grads in
  ...

The handler reverseMode is a language-level construct. It does not call into a compiler-internal AD function. The implementation lives in a Phase 2 module, written in the language.

Acceptance criteria:

1. The PoC type-checks.
2. It runs to completion on CPU.
3. The forward result matches an unhandled f W b x target invocation within FP tolerance.
4. The gradients match a PyTorch reference within FP tolerance (1e-3 is reasonable for this scale).
5. The handler implementation is no more than a few hundred lines of language code (sanity check that the language is actually expressive enough; if the handler grows beyond a thousand lines, something is wrong with the design).

If all five pass, Phase 2 is on track. If not — particularly if the handler can't be written within a sensible size, or if the gradients are systematically wrong in ways that suggest a foundational issue — Phase 2's framework needs revision.

This is the earliest possible falsification of the self-modeling design. Doing it as the first Phase 2 deliverable means catching foundational issues at month 7 of the project, not month 18.

7. Phase 1 commitments to keep paths open

Three concrete commitments derived from this track. None require new implementation work in Phase 1; all require small documentation and design hygiene.

7.1 Proto-stdlib in test fixtures

A directory compiler/test/fixtures/stdlib/ containing the representative functions from §2.2: linear, relu, silu, rmsnorm, softmax_stable, attention_scores, mlp. Each function has its own test that asserts it compiles and produces correct output for representative inputs.

Acceptance criterion: every function compiles with zero axiomatic assertions (or, where the controlled-unsoundness escape hatch is genuinely required like in reshape, the assertion is documented and minimal).

7.2 ADR on bootstrap stance

A short architectural decision record at decisions/bootstrap-stance.md committing to:

• Standard library is shipped in the language, not as compiler primitives. Phase 1 includes a proto-stdlib; subsequent phases extend it.
• Compiler transformations from Phase 2 onward are expressed as in-language handlers, not as OCaml-level passes. AD, sharding, custom transformations all live in the language.
• Compiler self-hosting is out of scope until Phase 8 at earliest. Phase 1's OCaml architecture is not constrained by self-hosting concerns.
• Type-system extension points for library authors (per ecosystem-architecture) are the same mechanism used by the language itself for self-modeling. There is one extension surface, not two.

The ADR makes the strategy explicit and prevents accidental drift toward more compiler-internal magic.

7.3 Runtime FFI design discipline

Already committed in Phase 1 Section 2 §8 ("small, orthogonal, stateless entry points"). This track elevates the rationale: handler-friendly consumption is why the FFI must be stateless. Each runtime call is self-contained because Phase 2's effect handlers will intercept and reinterpret them. State accumulating on the runtime side would defeat the handler model.

A test for whether the FFI design is right: can a Phase 2 handler implementation intercept all 15–20 entry points and reinterpret them (e.g., as gradient-recording operations)? If yes, the discipline is correct. If no, there's hidden state that needs to come out into the handler.

8. Connections to other forward tracks

The bootstrap track unifies several other commitments:

• Ecosystem architecture (the library author's guide). The extension mechanism for user-written libraries is the same mechanism used internally by the language for self-modeling. AD-as-handler is, structurally, a library that extends the language with a new transformation. The library author's guide and the bootstrap track describe the same surface from two angles.

• CUDA-native (tile IR as a sub-language). The kernel-authoring story in Phase 5 is self-modeling at the tile level. Custom kernels are written in the language, with the same type system, lowering to PTX rather than LLVM. The same machinery that lets users write matmul as a stdlib function lets kernel authors write flashattention_kernel as a tile-level function.

• Arrow + typed dataframes. A typed-dataframes library is the first non-ML domain library to validate that user-written libraries can extend the type system non-trivially. Schema-as-refinement-type adds a new kind to the language. If the bootstrap framework is real, typed dataframes is its first major test.

These tracks are not independent. They're three views of one underlying commitment: the language is extensible by users (and by itself) in the same way, through the same mechanisms.

9. Open issues

1. Effect handler expressiveness. Whether algebraic effect handlers are actually powerful enough to express the full range of compiler transformations we want is a real research question. Pearlmutter & Siskind's CPS framing for AD (memo 2 §5.2) suggests yes for AD specifically. Sharding propagation is less obviously a fit for the effect framework. May require a different mechanism — type-level handlers or a separate metaprogramming surface. Worth a Phase 3 design memo if the AD-as-handler PoC succeeds.

2. Open compiler vs. closed compiler. Two stances on user-defined libraries that extend the type system: (A) closed compiler with fixed type universe, libraries can use it but not extend it; (B) open compiler with extension hooks for new type constructors, operations, and lowering rules. The bootstrap track implicitly commits to (B) — self-modeling depends on it. Worth flagging that the engineering cost of (B) is real and the API stability story is harder than for (A).

3. Stdlib packaging. When the proto-stdlib grows into a real stdlib, how is it shipped? As source code that compiles alongside user programs? As a pre-compiled artifact loaded at runtime? As a hybrid (some pre-compiled, some source)? Engineering question; matters for compile-time performance. Defer until Phase 5.

4. The bootstrap dependency between proto-stdlib and Phase 2 AD validation. If Phase 1's proto-stdlib accepts the controlled-unsoundness escape hatches (per §2.2), and Phase 2's AD handler is built on the stdlib, then the AD PoC inherits any soundness gaps the stdlib has. The interaction needs care: the AD PoC should validate against the minimal stdlib (the parts that compile cleanly without escape hatches), not the full one.

5. What "in-language" means precisely. A handler written "in the language" might still need foreign-function calls to runtime primitives (matmul on GPU calls into cuBLAS via the FFI). Where does "in-language" stop? The pragmatic answer: the handler's control flow and type-level reasoning are in the language; the runtime calls are FFI. The language is the meta-language; the FFI is the object-language operations. This works but worth documenting carefully when the AD PoC happens.

10. Summary

Three senses of bootstrapping, mapped to the project:

The single load-bearing milestone: AD-as-handler PoC (§6). If it works, the self-modeling thesis is validated and the rest of the architecture follows. If it doesn't, the framework needs revision before Phase 2 builds on it.

Phase 1 commitments to keep paths open: proto-stdlib in fixtures, an ADR on bootstrap stance, runtime FFI design discipline. None are large; all are cheap-now, expensive-later.

The bootstrap track unifies the other forward tracks. The library author's guide (ecosystem-architecture) is the public face of the same extension mechanism that makes self-modeling work. The tile IR (CUDA-native) is self-modeling at the kernel-author tier. Typed dataframes (Arrow forward track) is the first major test of the extension surface.

What this implies operationally: Phase 1 doesn't build any of this, but Phase 1's design has to keep the door open for all of it. Section 1's discipline — gate continuation on whether the foundation feels sturdy enough — applies double here, because Phase 2's success depends on Phase 1 not having accidentally precluded self-modeling.

If the language ever does what it's designed to do, this track is what makes it possible. The language describes its own machinery using its own constructs. The compiler is a runtime; the transformations are programs. That's the ambition.

End of bootstrap and self-modeling forward track.