You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Self-hosting: the bootstrap fixed point (stage 1, stage 2, byte-identical) and removal of the Rust compiler #273
Child of #92 (stage 8 of #27): its "Self-hosting acceptance". Part of v0.4's objective: LexLean compiles itself.
Scope
Once every compiler part is certified LexLean source (the sibling issues, BS-01..BS-08, and #91's runtime):
Stage 1: stage 0 (today's Rust compiler) compiles the .lex.tex compiler to a certified Rust package whose provenance binds the source, certificates A, B, E and the runtime.
Stage 2: stage 1 compiles the same source.
Fixed point: stage 2's package is byte-identical to stage 1's, and stage 1 equals stage 0 on every committed project, corpus, fixture, golden and the Atlas verification records.
The trusted base is stated exactly: Lean kernel, leanchecker, rustc and the host; every part of the compiler's own logic is certified.
Each part follows the standing R3 discipline of #15: register rows in model/ids.toml and SPEC §31, one scenario and one conformance_<id> test per row, positive and negative fixtures, a planted defect recorded in VERIFICATION.md, and the Rust module kept as the stage-0 oracle (differential to the byte) until the fixed point of #92 removes it.
changed the title [-][v0.4] Self-hosting: the bootstrap fixed point (stage 1, stage 2, byte-identical) and removal of the Rust compiler[/-][+]Self-hosting: the bootstrap fixed point (stage 1, stage 2, byte-identical) and removal of the Rust compiler[/+]on Oct 22, 2026
Proposal for #273: modular certification and the shape of stage 1
A proposal for the owner and maintainer to decide, posted here as the 2026-10-22 ruling asks. No milestone, label or title is changed, and nothing is built or pushed. It came out of a read-only survey of what stands between release/v0.4 and stage 1. That survey found that porting is not the binding constraint: certifying a compiler-sized command root is.
Base: release/v0.4 at aaf845507. Counted means measured on that tree. Estimated means extrapolated, and each estimate names its source.
Decision asked
Lower one program per project and target instead of one per root. Each function's certificate rows are then generated once, in shard modules cut along the call graph. Each root keeps a small certificate A, B and E of its own that cites the shards.
The calculus, RustSemantics, and the library's sound, simulate and compose do not change. Every theorem a root has today keeps its statement except one thing: the entry is e_r instead of 0. This is the smallest change that lets a compiler-sized command root be certified. It also cuts the bootstrap's certificates about in half today.
Three smaller decisions make stage 1 buildable:
The compiler's embedded language/ tree reaches the step through a new embedded host request, and the certified step checks its digest.
rust_renderer stays the recorded digest of the Rust renderer files until the removal.
Certificates of the self-compile are verified in CI and not committed as bytes.
1. The problem, measured
A root's certificates restate its whole closure. Certificate A's statement is RunConv P 0 … over the program P lowered for that root alone (§17.17, Statement). Its rows are __prog, the encoders, and __fits_k and __rel_k for each function of the closure. Certificate B has one fun<n> derivation per function of the same program. So a function that two roots call is lowered, related and derived twice.
Counted on the 62 committed bootstrap roots (the program records bootstrap/expected/verify/preserve/program/R*.json and preservation.json; the script at the end, which identifies functions structurally up to renumbering):
5,320,581 bytes (lowerBodies, A), against max_file_bytes 6,291,456
Certificate bytes per program byte
about 17
Projection to stage 1. This is estimated: it scales the bootstrap's distinct program, about 4.7 MB for about 14,900 Rust lines ported, to the compiler's about 150,000 lines.
Today's scheme
One project program, sharded
Program
about 47 MB
about 47 MB
Certificates in total
about 800 MB, all in one root's A and B
about 800 MB, spread over shards
Largest file
about 340 MB (A) and 440 MB (B); refused by the 6 MB cap
the largest call-graph cycle's rows; today about 5.3 MB
Bootstrap export (62 roots)
157 MB
about 80 MB (the 1.95 ratio)
2. Options
Option
What changes
Verdict
Status quo with raised limits
max_file_bytes to about 512 MB
Rejected. One Lean process would check a 340 MB module. Today a 9.2 GB Lean child on Atlas is already more than the 16 GB WSL host can hold.
S: one program per project and target, sharded certificates
lowering numbering; how certificates are cut into modules; package layout
Recommended. It keeps every proof of the hand-written library.
L: linked programs, true separate compilation
the calculus gains cross-program calls; run, RustSemantics, sound and simulate gain an environment and a frame lemma
Later, if S's Lean time is too high. It changes the trusted library's proofs, so it is a larger review.
3. Design S
3.1 Lowering (§17.14, production/lower.rs)
The program. One program per project and target: the union of the eligibility closures of every production root that declares that target. Instances are deduplicated by definition and type arguments, as within a root today.
Numbering. Roots go in report order, and functions in discovery order from each root in turn. An instance already numbered keeps its number. The layout gains an entry table, root to function.
Invariants. "The program is exactly the closure" becomes two checks: the program is exactly the union of the closures, and each root's closure is exactly the set reachable from its entry. Both remain LLI9001.
Limits.max_ir_nodes is charged per program, as now.
one function constant __fn_k per function of the shard
the shard
…P
__prog, the program as a lookup over the __fn_k constants (see risk R1)
the number of functions
…A.<s> (one per shard)
__fits_k, __rel_k, the encoders first used there
the shard
…B.<target>.<s>
fun<n> for each function of the shard
the shard
…B.<target>
krate, flags, crate_ok, root (simulate)
the number of functions
…R<i> (one per root)
denote, root : RunConv __prog e_i …
the root's boundary
…R<i>.Compose.<target>
compose applied to R<i>.root and B.<target>.root at fnIdent e_i
the root's boundary
Shards. A shard is a set of strongly connected components of the call graph, cut in topological order and filled up to a byte budget. A component is never split, because a mutual group's relation is one recursor. Each shard imports the shards of its callees.
Content. The rows are those of today's modules, unchanged. Today's rows are already independent of the root: __rel_k relates function k of P to its source definition, and fun<n> derives function n of the crate. Only P, the numbering and the module boundaries move.
The library. No proof of the library changes. The one statement that moves is certificate A's root, from function 0 to function e_i. E's boundary form already takes fnIdent e. To confirm in M1: whether compose assumes entry 0 anywhere.
Limits. The size limit (§17.17, Limits) applies per shard and per root module, so max_file_bytes bounds every file Lean opens. The early lower bounds are computed per component.
Records.preservation.json lists the shards, each with its module, byte length and SHA-256, and per root its entry, its A and E modules, and the target's B root module. This is a schema change (schemas/preservation.schema.json), so the language-1.2 compiler-semantics ID moves. Languages 1.0 and 1.1 are untouched, since production is 1.2 only.
The request.lexlean/production-request/1 is unchanged: one package per requested root.
A root's package.src/lib.rs is the project crate for the target (the one certificate B is about) plus that root's export wrapper. Cargo.toml and provenance.json are as now; the provenance also binds the crate digest that B states.
Trade-off. A consumer that ships one small root out of a large project now ships the whole project crate. A project that wants small packages splits into projects. For the downstream projects that use production today, this is no change in practice. Their projects are small; that is a reading of the corpora, not a measurement.
rustc. One crate per project instead of one per root. The conformance harnesses build it once per run and link the wrappers. Risk R2 covers the size of the compiler's crate.
3.4 Verification (§22, verify/)
The shards form a directed acyclic graph of imports. Verification stages and compiles them in that order through the existing pool (verify/pool.rs, whose output is width-independent by contract). This is also the parallel certificate stage the gate-speed hand-over asked for. Today 1,397 of the export's 1,966 s are certificates checked one at a time.
3.5 What does not change
The trusted base and the kernel.
The statements a consumer relies on, apart from the entry index.
The 49 Corr rules.
The token audit and the axiom pins.
4. The shape of stage 1
Question
Proposal
Why
Where is the command root?
LexLeanBoot.Compiler.step in bootstrap/, with a committed production request for it alone
Under S, the bootstrap project's program already is the compiler. A separate selfhost/ project would import bootstrap as a source package and certify every function a second time.
How does stage 1 get its 36,119,142 bytes of language/ (counted; 32,670,965 of it the preservation library)?
A 15th request, embedded (path : String), answered by Event.read. RB-24's printed driver serves it from an include_bytes! table, and the package gains an assets/ tree. The certified step computes the §11.5 tree digest of what it reads and refuses anything but its compiled-in compiler-semantics ID. It needs no effect.
A literal costs about 27 bytes of certificate A per digit (§17.17 cost table), which is impossible here. Reading files beside the executable would change the release from one binary to a binary plus a data tree. With the digest check, the driver's table is trusted only to be there, not to be right.
What is rust_renderer in provenance?
Unchanged until the removal: the recorded digest of the nine Rust RENDERER_FILES. Stage 1 reads it from language/ as data, and it moves once, at FP-06.
Stage 1 must write what stage 0 writes. If it framed bootstrap/src now, every slice landing would move the compiler-semantics ID. This is the maintainer's 2026-10-22 decision 4 ("at the fixed point").
Are certificates committed?
The self-compile's certificates are not committed. CI regenerates and verifies them, and preservation.json with its digests is committed. The bootstrap export as it is today stays committed until the maintainer decides otherwise.
About 800 MB per regeneration (estimated) is not a git workload. bootstrap/expected is already 258,401,428 bytes for 62 packages (counted).
Stack
The RB-24 driver runs the step on a thread sized from PD-08's rows
the PD-08 bounds and the Windows default stack (#164)
5. Risks, and the measurement that decides them (M1)
#
Risk
What M1 measures
Fallback if it fails
R1
The kernel evaluates program and crate lookups in every side condition. A list of about 22,000 functions (estimated: 2,221 distinct functions per 14,900 lines, scaled) makes each lookup about 22,000 reduction steps.
B's check time on the bootstrap with __prog as a list and as a balanced tree
Represent __prog and krate as a tree. A library lemma, proved once, equates the tree lookup with today's list lookup.
R2
rustc on a crate of the whole compiler: about 36 MB of Rust (estimated from the bootstrap's crates, 7,036,588 bytes summed and ratio 1.95, scaled)
the debug and release build time and peak memory of the bootstrap's project crate, and of a synthetic crate ten times its size
Split the crate into files by shard (an RB-07 layout change)
R3
A single call-graph cycle exceeds max_file_bytes
the largest component's rows on the bootstrap
Split the source definition. The rows of a cycle cannot be split.
R4
Lean time for about 800 MB of shards
the bootstrap export at width 1 and width 4, before and after S
Option L
M1 decision gate. M1 is a spike on a branch, never landed, run on CI rather than the laptop. It prototypes 3.1 and 3.2 on the bootstrap and reports:
the total certificate bytes (prediction: about 80 MB, against 157 MB);
the largest shard;
the export time at widths 1 and 4;
the time per side condition for R1;
the crate build for R2.
S proceeds if the total is below today's, every shard is under the cap, and the export is no slower at width 4.
6. Plan
Every step follows R3: register rows and SPEC first, a failing case, plants, a VERIFICATION entry. All changes are in stage 0 (Rust and SPEC); the .lex.tex twins of the changed generator are track C's.
PR
Content
Rows touched (to be confirmed against model/ids.toml)
M1
The spike and its measurements, posted on #92 and #273 for the decision
Project program and entry table (production/lower.rs, layout)
SP rows of lowering
M4
Certificate A shards and root modules (certificate/data_a, certificate.rs)
SP-15
M5
Certificate B shards, crate_ok, root per target (certificate/data_b)
SP-16
M6
Certificate E per root; package equals project crate plus wrapper (package.rs, provenance)
SP-14, RB-07
M7
Shard staging through the pool (verify/mod.rs)
VR rows of staging
M8
The regeneration: every language-1.2 export, golden and record, with Atlas, through regenerate.yml. One identity move, landed with M3-M7 as one batch, as #480 landed BS-25..34.
counts
M9
The embedded request: PD-10 row, RB-24 driver arm, assets/ in the package layout
PD-10, RB-24
M10
The step root's first slice (track X) on top of M9
new BS row
Size (estimated, from no measurement of this work). M2-M7 are 6 Rust PRs of about 500 to 2,000 changed lines each, plus one regeneration. With reviews, that is 2 to 4 weeks elapsed. M1 is 2 to 3 days.
Effect on the writing tracks.
The BS cases' export comparison changes from per-root packages to a shared crate with wrappers. Every case's comparison step needs one mechanical edit at M6, done by M6 itself.
A slice written before M8 lands regenerates once more, as it would for any identity move.
Track C should port the kernel DAG and certificate B's derivations first. S leaves those per-function pieces intact, and moves only module boundaries and __prog.
7. Questions for the maintainer
S rather than L, subject to M1's gate?
Program per project and target (recommended), or per production request? Per request gives smaller packages to consumers, but verify and production build would then certify different programs.
The embedded request (one binary), or a data tree beside the binary?
Keep rust_renderer as the recorded constant until FP-06?
The self-compile's certificates verified in CI and not committed?
Counted figures: the script below over the 62 program records and preservation.json of bootstrap/expected/verify/preserve/ at aaf845507, and the repository tree through the GitHub API.
The measurement script (Python 3, standard library; run as python dedupe.py <dir>, with the 62 R*.json and preservation.json in that directory)
"""How much of the bootstrap's lowered programs is the same function restated by several roots.Functions and ADTs are numbered per program, so identity is structural: a label is refinedover rounds from the body with every callee and ADT reference replaced by that callee's orADT's label of the previous round (Weisfeiler-Lehman style), until the partition is stable."""importglob, hashlib, json, os, sysd=sys.argv[1]
progs= {}
forfinsorted(glob.glob(os.path.join(d, "R*.json")), key=lambdap: int(os.path.basename(p)[1:-5])):
progs[os.path.basename(f)[:-5]] =json.load(open(f, encoding="utf-8"))
defh(s):
returnhashlib.sha256(s.encode()).hexdigest()[:24]
defsubst(x, fl, al):
ifisinstance(x, dict):
k=x.get("kind")
out= {}
forkk, vinx.items():
ifkin ("call", "closure") andkk=="function":
out[kk] ="F:"+fl[v]
elifk=="adt"andkk=="index":
out[kk] ="A:"+al[v]
else:
out[kk] =subst(v, fl, al)
returnoutifisinstance(x, list):
return [subst(v, fl, al) forvinx]
returnxlabels= {}
forname, pinprogs.items():
labels[name] = (["f"] *len(p["functions"]), ["a"] *len(p["adts"]))
prev_classes=-1forrndinrange(40):
new= {}
forname, pinprogs.items():
fl, al=labels[name]
nf= [h(json.dumps(subst(fn, fl, al), sort_keys=True)) forfninp["functions"]]
na= [h(json.dumps(subst(a, fl, al), sort_keys=True)) forainp["adts"]]
new[name] = (nf, na)
labels=newclasses=len({lforfl, _inlabels.values() forlinfl}) +len({lfor_, alinlabels.values() forlinal})
ifclasses==prev_classes:
breakprev_classes=classessum_f=sum(len(p["functions"]) forpinprogs.values())
sum_bytes=0uniq= {}
forname, pinprogs.items():
fl, _=labels[name]
forfn, linzip(p["functions"], fl):
b=len(json.dumps(fn, separators=(",", ":")))
sum_bytes+=buniq.setdefault(l, b)
print(f"rounds={rnd+1} roots={len(progs)} functions summed={sum_f} distinct={len(uniq)}")
print(f"function JSON bytes summed={sum_bytes:,} distinct={sum(uniq.values()):,} ratio={sum_bytes/sum(uniq.values()):.2f}")
# how many roots restate each distinct function, weighted by bytescount= {}
forname, pinprogs.items():
fl, _=labels[name]
forlinset(fl):
count[l] =count.get(l, 0) +1top=sorted(uniq, key=lambdal: -uniq[l] *count[l])[:5]
forlintop:
print(f" shared function {l}: {uniq[l]:,} B in {count[l]} roots")
pres=json.load(open(os.path.join(d, "preservation.json"), encoding="utf-8"))
a=sum(r["byte_length"] forrinpres["roots"])
b=sum(x["byte_length"] forrinpres["roots"] forxinr["renderings"])
e=sum(x["composed"]["byte_length"] forrinpres["roots"] forxinr["renderings"])
largest=max(max([r["byte_length"]] + [x["byte_length"] forxinr["renderings"]]) forrinpres["roots"])
print(f"certificates: A={a:,} B={b:,} E={e:,} total={a+b+e:,} largest part={largest:,} roots={len(pres['roots'])}")
Maintainer design readback of 6823454237: the smallest next decision is per-root certificate-sharding feasibility, separated from project-wide program union. A compiler-sized single root still needs its A/B certificates split even if no functions are shared across roots. Project union adds numbering, package-content and closure-policy changes; its deduplication benefit is a separate question.
Two evidence boundaries matter before choosing a spike:
The supplied refinement script groups recursive unfolding labels; it does not establish a bijective renumbering or source-instance equivalence for merging functions. Its 40-round cap and class-count stopping rule do not supply that proof. Keep 2,221 distinct / 1.95× as candidate grouping estimates, not verified deduplication or predicted certificate savings. Reuse the existing census; no repeat measurement is requested.
At the cited aaf base, Compose.lex.tex accepts an arbitrary function index f, while rows.rs currently generates entry 0. That supports investigating nonzero entries without changing that library theorem, but it is not proof that every generated A/B/E premise, lookup and wrapper correspondence already generalizes.
Existing implementing owner: first separate the minimal sharding contract and its concrete remaining proof obstacle from the project-union/package redesign. This can be a concise source/design delta using the existing records. It should identify whether current per-root statements and package behavior can remain intact, and what prevents splitting the oversized certificate. That is the next reviewable decision before choosing the smallest necessary hosted experiment.
The existing R25 group-union admission/STOP remains in force; this static proposal does not authorize that experiment, the M1 runs, an identity wave, raised limits, or M2–M10. #387's isolated-context proposal is distinct and remains unaccepted. The embedded request, renderer transition, certificate storage and lane allocation also remain proposed decisions. No build, probe, census, export or gate was repeated for this readback.
The prior owner ruling also remains unchanged: #267–#277 are unscheduled, and this is not acceptance of a new v0.4 objective or a milestone change. The recommendation above narrows the proposal for a decision; it does not schedule its implementation.
#273: the minimal per-root sharding contract, separated from project union
This answers the readback of 2026-11-12 (afflom): separate the minimal sharding contract and its concrete remaining obstacle from the project-union and package redesign, using existing records. Nothing was built, verified, exported or run under Lean. The figures come from a static read of the committed records at maina74b1f99b, by the script at the end. release/v0.5 has the same certificate generator under another semantic ID; its R30 A is the same size, its R34 A is 5,324,482 bytes and its R30 B is 5,217,111 bytes, which changes no conclusion. Counted means read from those bytes. Estimated means extrapolated, and each estimate names its basis.
Answer
A root's certificates can be split into modules without changing any root's statement or package.
The entry stays function 0.
The numbering stays per root.
Each root keeps one package with the same crate and provenance.
No lemma of the preservation library changes. Neither does compose's use of fnIdent 0, so this contract does not depend on Compose generalising to a nonzero entry.
Three generated rows grow with the whole program and cannot simply move to another module:
__prog in certificate A,
program and krate in certificate B,
crate_ok in certificate B.
Two of them already have a split that needs no new proof. The remaining question is one kernel-cost measurement, not a proof (§4).
1. What is being separated
Concern
Per-root sharding (this contract)
Project union (deferred, unchanged proposal)
Lowering, numbering, entry
unchanged: one program per root, root is function 0
one program per project and target, entry table
Statements of A, B, E
unchanged text: they cite __prog, program, krate, crate_ok by name
A's root moves to e_r
Packages
unchanged: one per root, same crate
project crate plus wrapper
Certificate files
one root's A or B becomes several modules
shards shared across roots
Deduplication across roots
none
the candidate 1.95× grouping estimate, unverified
Sharding is what a compiler-sized root needs. Union is a separate saving that can be decided later or never.
2. Where the bytes are (counted)
These are the two largest roots of the bootstrap export, measured against the bootstrap's own max_file_bytes of 6,291,456. The project already raised that limit from the default of 4,194,304.
So the bootstrap is already near its limit without any stage 1. The next slice that grows either closure is refused.
Row anatomy of R30. Bytes are node-table text; records add row headers and node prefixes, about 1.2× more.
Certificate A
Certificate B
Rows
476
255
Literal rows
__prog 184,965
program 205,513, krate 495,085
Literal nodes other rows restate
158,872 of 184,965 (86%)
612,035 of 686,834 (89%)
Largest row
__rel_89 988,419
fun23 297,600
Largest unit that must not be split
the 5 __rel rows of one mutual group (23, 71, 75, 77, 89) sharing one packed core, 989,409
one row, fun23
crate_ok (outside the literals)
92,240, one Nat.casesOn level per function
root, denote
801, 453
509
Cut greedily along the row graph (callees first, no unit split), at two byte budgets per shard:
Budget per shard
A: shards, largest, total vs today
B: shards, largest, total vs today
2 MiB
3, 2.10 MB, +9.7%
3, 2.09 MB, +21.7%
4 MiB
2, 4.18 MB, +4.7%
2, 4.18 MB, +14.8%
The overhead is the literal nodes each shard restates: a __rel_k or fun<n> row states the body it relates. B pays more because its rows restate more of krate.
3. What prevents the split today
#
Obstacle
Where
Kind
Fix within this contract
O1
__prog, program and krate are one row each, so they grow with the whole program
rows.rs (__prog), data_b.rs (program, krate)
size
Emit one constant per function (and per ADT) and define the literal as Program.mk over the list of those constants. Statements cite the constant by name, so their text does not change. A and B build the same program with the same builder, so the literal could live in one module that both import.
O2
crate_ok is one row: a chain of countNat.casesOn levels
data_b.rscrate_ok_value
size
Each level is already the closed statement ∀ x fn h, FunOK (x + d). Name the level at each shard boundary as a row of that shard; the level above cites it. The kernel checks the same succ m + d against m + (d+1) it checks between levels today. No new lemma.
O3
A mutual group's relation theorems share one packed core as an anonymous node, not a row
data_a recursion plan
layout
Cut by the group (the source knows it), never by row. Optionally emit the core as a named row so one module holds it.
O4
The contract is per-root, single-module throughout
SPEC §17.17 Statement, Limits, Verification; preservation.json schema; certificate.rs; verify/ staging and the audit
contract
Module names R<i>.S<k> and R<i>.RustStd.S<k> beside the unchanged R<i> and R<i>.RustStd. Weigh each module against max_file_bytes, and move the early refusal's lower bound from the root to a unit. Stage modules in import order through the existing pool. preservation.json lists each module's path, length and SHA-256.
O5
Axiom pins are printed per module, and the order of that printing is not a property of one constant (#227)
audit
audit
Keep each mutual group in one module, as O3 already requires. The existing group-union rule then applies unchanged. Recompute every pin once.
O4 changes the schema of preservation.json and every record, so the language-1.2 compiler-semantics ID moves once. That is one identity wave, the same cost as any record change.
4. The one open question
O1 is the only change that alters what the kernel evaluates.
Side conditions are Eq.refl at a lookup into the program, and every rule's statement mentions the program. Today the kernel reduces a lookup through one literal list. After O1 it unfolds the per-function constant at the index found. The number of list steps per lookup is the same for the same program, because sharding a root changes no index, so this contract makes no lookup longer.
What is unknown is whether the kernel's sharing of the unfolded literal behaves the same when the literal is assembled from constants, both within a module and across the modules a shard imports. That is the measurement to make first:
B's check time on R30, with the literal as today and with the literal assembled.
Replay time and peak memory of the same.
It is a single root, run once each way. It is not M1, and it repeats no census. It needs your authorisation as a hosted run.
The program's length is a separate question that only scale raises, and it is project union's R1 as well: at compiler size the list may be long enough that each lookup is slow. That is already true of an unsharded root of the same size, so it is not an obstacle sharding creates.
5. When the literal rows outgrow the limit (estimated)
These rates come from R30 alone (250 functions). One root does not represent the compiler's mix of functions.
Row
Bytes per function on R30
Functions at which the row alone reaches 6,291,456 bytes
krate
about 1,980
about 3,200
program
about 820
about 7,700
__prog
about 740
about 8,500
crate_ok
about 370
about 17,000
By the bootstrap's existing count, a compiler-sized root passes the first of these thresholds even if that count is several times too high. So O1 and O2 are required for stage 1 whether or not project union is chosen. The bootstrap counted 4,698 functions summed over its 62 roots, for about 15,000 lines of ported Rust; the compiler is 158,583 lines (counted on main).
6. Evidence boundaries
These are static reads of committed records. No Lean time or memory was measured, and §4 is the measurement that would supply it.
The shard simulation sizes modules by node-text bytes and assumes a row's closure is restated wherever the row goes. It does not model a decoder's fixed cost per module.
O2's split rests on reading crate_ok_value and on the existing between-level defeq. A generated level row checked under Lean would confirm it.
The per-function rates in §5 come from one root.
The measurement script (Python 3, standard library; python -I cert_rows.py <record.lex.tex> [budget ...])
"""Row anatomy of one committed certificate record (lexlean/core-module/2, authoring notation).Static read only: no build, no Lean. For each row it takes the closure of its type and valuenodes in the module's shared node table; node bytes are the record's own lines. It reports whatthe literal rows hold, how much of them other rows restate, the largest row and mutual-groupclosures, and a greedy cut of the rows into shards of a byte budget along the row graph, calleesfirst, a mutual group (`all:`) or a set of rows sharing one packed core never split.usage: python -I cert_rows.py <record.lex.tex> [budget-bytes ...]"""importcollections, re, systext=open(sys.argv[1], encoding="utf-8").read()
budgets= [int(x) forxinsys.argv[2:]] or [2*1024*1024, 4*1024*1024]
row_re=re.compile(r"^(definition|theorem|abbreviation) (\S+) : @(\d+)(?: := @(\d+))? \{")
node_re=re.compile(r"^@(\d+) := (.*)$")
rows, nodes, cur= [], {}, Noneforlnintext.split("\n"):
m=row_re.match(ln)
ifm:
rows.append((m[2], [int(m[3])] + ([int(m[4])] ifm[4] else []))); cur=None; continuem=node_re.match(ln)
ifm:
cur=int(m[1]); nodes[cur] = [m[2]]; continueifcurisnotNoneandln[:1] in (" ", "("):
nodes[cur].append(ln)
elifln.startswith("\\end"):
cur=Nonenames= {nforn, _inrows}
size= {k: sum(len(s) +1forsinv) fork, vinnodes.items()}
kids= {k: [int(x) forxinre.findall(r"@(\d+)", " ".join(v))] fork, vinnodes.items()}
cites= {k: {cforcinre.findall(r"[A-Za-z_][\w.]*", " ".join(v)) ifcinnames} fork, vinnodes.items()}
short=lambdan: n.rsplit(".", 1)[-1]
defclosure(start):
seen, todo=set(), list(start)
whiletodo:
n=todo.pop()
ifnnotinseen:
seen.add(n); todo.extend(kids.get(n, []))
returnseenB=lambdas: sum(size[n] fornins)
cl= {n: closure(r) forn, rinrows}
total=B(nodes)
lit= [nforn, _inrowsifshort(n) in ("__prog", "program", "krate")]
L=set().union(*(cl[n] forninlit)) iflitelseset()
other= [nforn, _inrowsifnnotinlit]
print(f"record {len(text):,} B; rows {len(rows)}; nodes {len(nodes):,} ({total:,} B)")
forninlit:
print(f"literal row {short(n)}: closure {B(cl[n]):,} B")
print(f"literal nodes restated by other rows: {B(set().union(*(cl[n] &Lforninother))):,} of {B(L):,} B")
forninsorted(other, key=lambdan: -B(cl[n]))[:3]:
print(f"row {short(n)}: closure {B(cl[n]):,} B")
forninother:
ifshort(n) in ("crate_ok", "root", "denote"):
print(f"row {short(n)}: closure {B(cl[n] -L):,} B outside the literals")
# units: rows of one mutual group, and rows whose closures share a core of over 64 KiB, stay togetherparent= {n: nforninother}
deffind(x):
whileparent[x] !=x:
parent[x] =parent[parent[x]]; x=parent[x]
returnxforminre.finditer(r"^(?:definition|theorem|abbreviation) (\S+) .*?\n all: \[([^\]]*)\]", text, re.M):
group= [g.strip() forginm[2].split(",") ifg.strip() inparent]
forgingroup[1:]:
parent[find(g)] =find(group[0])
owner= {}
forninother:
forkincl[n] -L:
ifsize[k] >0:
owner.setdefault(k, []).append(n)
heavy=collections.Counter()
fork, nsinowner.items():
iflen(ns) >1:
forainns[1:]:
heavy[(find(ns[0]), find(a))] +=size[k]
for (a, b), vinheavy.items():
ifv>64*1024andfind(a) !=find(b):
parent[find(b)] =find(a)
units=collections.defaultdict(list)
forninother:
units[find(n)].append(n)
deps=collections.defaultdict(set)
forninother:
forkincl[n]:
forcincites.get(k, ()):
ifcinparentandfind(c) !=find(n):
deps[find(n)].add(find(c))
order, done= [], set()
defvisit(u, stack=()):
ifuindoneoruinstack:
returnfordinsorted(deps[u]):
visit(d, stack+ (u,))
done.add(u); order.append(u)
foruinsorted(units):
visit(u)
ucl= {u: set().union(*(cl[n] forninunits[u])) foruinunits}
big=max(units, key=lambdau: B(ucl[u]))
print(f"units {len(units)}; largest unit {len(units[big])} rows, {B(ucl[big]):,} B ({', '.join(short(n) forninunits[big][:6])})")
forbudgetinbudgets:
shards, cur, cn= [], [], set()
foruinorder:
ifcurandB(cn|ucl[u]) >budget:
shards.append(cn); cur, cn= [], set()
cur.append(u); cn|=ucl[u]
ifcur:
shards.append(cn)
sizes= [B(s-L) +B(s&L) forsinshards]
whole=sum(sizes) +B(L)
print(f"budget {budget:,}: {len(shards)} shards, largest {max(sizes):,} B, total with the literal module {whole:,} B ({100* (whole-total) /total:+.1f}%)")
The per-root contract answers the earlier request to separate sharding from project union: entry0, numbering and packages stay fixed. That narrows the next decision usefully. The reported sizes remain static evidence; I have not repeated the census or run the simulation.
Two limits should remain explicit before calling kernel cost the only open question. The posted cut simulation tolerates dependency cycles and admits an oversized first unit; its figures therefore do not establish an acyclic layout within actual serialized-module limits. Naming crate_ok boundary levels also retains a generated-term correspondence obligation even if no library lemma changes. These are contract/qualification gaps, not demonstrated impossibility.
Please make the requested R30 comparison concrete: pin the exact baseline/candidate delta, distinguish literal factoring from imported-shard behavior, and specify runner/cache controls, resource and stopping bounds, and retained source/output/measurement custody. Budgets remain planning assumptions until observed, and one pair gives exploratory evidence only. Reuse existing records; no repeat census is requested. This design review does not admit a hosted run or identity wave. Existing #431/oldTC03 and R25 STOPs remain intact, and #443/#559's targeted owner repairs remain the delivery priority.
#273: the two qualification gaps, and the R30 comparison as a concrete plan
This replies to the review of 2026-11-16 (afflom). Nothing was built, verified or run under Lean. The figures are static reads of committed records at maina74b1f99bba637e51d19fb4efc508316aafa6664 (tree 0af41e384c9df2d6b6d9873accbaa8e91038d264), and of the existing telemetry of two CI runs. No census was repeated. This asks for no admission; it is the plan the review requested.
1. The layout gap, corrected
The review is right that the first script tolerated cycles and admitted an oversized first unit. Version 2 (at the end) changes four things:
It merges units that cite each other in a cycle into one unit, and reports every merge.
It refuses a layout in which any single unit, or the literal module, exceeds the limit. Such a unit is never placed.
It weighs modules as serialized: node lines with their @N := prefix, row headers, and the import block.
After placement it checks that no module imports a later one and that every module is within the limit. It stops if either check fails.
Planted defects, on synthetic records:
Plant
Result
Two rows citing each other
reported as one merged cycle of 2 rows, placed together
A unit of 3,138 B against a limit of 2,500
INFEASIBLE, 1 unit(s) exceed it alone
The same records without a defect
one shard, 0 backward edges
Results on the four largest records (counted; serialized bytes):
Record
Cycles merged
Largest unit as a module
1 MiB
2 MiB
4 MiB
R30 A (5,420,777)
0
1,140,442 (the 5-row __rel group)
infeasible
3 shards, largest 2,005,347, total +11.7%
2 shards, +8.5%
R30 B (5,212,396)
0
376,777 (fun23)
6 shards, +35.4%
3 shards, largest 2,074,842, +28.1%
2 shards, +22.1%
R34 A (5,320,145)
0
430,442 (__rel_8)
7 shards, +20.5%
3 shards, +13.3%
2 shards, +9.8%
R34 B (4,220,225)
0
535,727 (fun8)
5 shards, +34.9%
3 shards, +27.3%
1 shard, +18.8%
Every total includes the literal module that all the shards import: 296,708 B for R30 A and 990,826 B for R30 B.
So an acyclic layout exists for all four within serialized limits of 2 MiB and above, but not at 1 MiB for R30 A. Certificate B costs about 22 to 35% more bytes, because its rows restate most of krate. These remain planning figures until a module is staged.
2. The generated-term obligation, stated as a check
Naming crate_ok's boundary levels (and, for O1, the per-function constants of the literal) changes no lemma. It still leaves the obligation the review names: the named rows must be exactly the terms they replace. The candidate discharges this by a comparison rather than an argument.
Expansion equality. δ-expand every new row (__fn_k, __adt_j, crate_ok_from_d) in the candidate's data and compare the result, node for node, with the baseline's __prog, program, krate and crate_ok. They must be equal after the canonical renumbering the core module already performs.
Statements. The type of every row the baseline has is equal in both. Only the new rows are added.
Axioms. The audit prints, for every baseline row, exactly the pin it has today. Each new row pins [], because it is a definition with no proof content; crate_ok_from_d pins what crate_ok pins.
Any inequality fails the arm before Lean runs. The kernel's acceptance of the candidate is then the remaining check, and that is what §3 measures.
3. The R30 comparison
The baseline (pinned). R30 LexLeanBoot.RuntimeValidate.validateRuntime at a74b1f99b, semantic ID prefix Ce734249a01f6588cb76caa0d10039d36:
The arms. Each arm differs from the one before by one change, so each effect is attributed by itself:
Arm
Change from the previous arm
What it isolates
A0
none: the committed records
the baseline, rerun under the same controls
A1
the literal factored into __fn_k and __adt_j constants in the same module; __prog and program defined from them
the kernel's cost of unfolding constants, with no new import
A2
A1's literal rows moved to one module R30.P, which A and B both import
the cost of the import alone
A3
the rest cut by the version-2 layout at 2 MiB (A: 3 shards; B: 3 shards with crate_ok named at the shard boundaries)
shard imports and the crate_ok split
E is unchanged in every arm, apart from what it imports. It is checked in every arm, because it imports A and B.
Construction. The construction is a record-to-record transform of the pinned data, never a change to the generator. It uses the conformance crate's existing path, as the plants of SP-14, SP-15 and SP-16 already do: read the record back to CoreModule data, transform it, render with backend::core::lean_text_legacy, stage it with preservation::staged, then compile and check with preservation::compile_text and check. It lives on a branch that is never landed. Nothing is committed to main, no record or export changes, and no identity moves.
The exact delta is pinned by three things:
the transform's source and its SHA-256,
the SHA-256 and length of every module each arm produces,
the expansion-equality report of §2.
What is measured, per arm and per module. For each module:
lean: wall time and peak RSS;
leanchecker: wall time and peak RSS;
the audit's printed axioms, compared with A0;
the module's bytes.
These are the fields of the verifier's existing telemetry (§22.12), so the same parser reads A0 and the candidates.
Runner and cache controls.
One job on the standard ubuntu-24.04 runner, as the gate uses (§9.4), from a clean checkout of the pinned commit.
The pinned lean-toolchain and rust-toolchain.toml.
No actions/cache and no restored Lake or build directory.
Width 1: no two proof processes run at once.
Arms run interleaved in three rounds (A0 A1 A2 A3, then A1 A2 A3 A0, then A2 A3 A0 A1), so runner drift falls on every arm.
Before each process, record the load average and available memory, as the telemetry already does.
The bootstrap's generated modules are elaborated once per job, before the first round, and are not timed.
Why rounds: in the existing records, the same modules at the same commit differ by 1.4 to 1.65 times between two runs at width 2:
Module
Run 43871322239
Run 43898718803
R30 A, lean
15.3 s
22.5 s
R30 B, lean
22.9 s
33.1 s
R30 B, leanchecker
16.4 s
27.1 s
Peak RSS agrees within about 2% (2.04 to 2.09 GB for lean, 1.59 to 1.69 GB for leanchecker). A single pair could not separate a real time difference under about 2×; memory it could.
Resource and stopping bounds.
Bound
Value
Basis
Per process time
10 min
about 18× the slowest baseline process (33 s)
Per process memory
6 GiB, enforced by the process's cgroup
about 3× the baseline peak of 2.09 GB
Job
120 min, rounds included
estimated; the elaboration of the bootstrap's generated modules is not measured separately
On a kernel rejection, timeout or memory kill
stop that arm, record it, continue the other arms
the rejection is itself the finding
Retries
none, except a runner infrastructure failure, which is reported as such
Every arm's expansion equality (§2) passes before any Lean process starts. A failure there stops the job.
Custody. One artifact per run, retained for 90 days, holding:
the run and attempt; the commit and its tree;
the SHA-256 of rust-toolchain.toml, lean-toolchain and Cargo.lock;
what rustc -vV and lean --version report;
the SHA-256 of the lean, leanchecker and lake executables (the fields of lexlean/ci-bootstrap-export/2);
the transform's SHA-256 and the input records' SHA-256 (above);
every generated module's text with its SHA-256 and length;
the expansion-equality report, the audit output, and the raw telemetry JSONL.
The result is reported here with the run ID. None of it is an input to any recipe or committed output.
How it would be read. Exploratory, as the review says: one job of three rounds.
Reported: the median and every raw value per arm, and the ratio of each arm to A0 per module.
No sign of a blocker: each arm's summed lean plus leanchecker time within 2× of A0, and its peak RSS within 25%.
What is not claimed: anything about compiler scale. That is the program's length (§4 of the earlier comment), which R30 cannot show.
4. Not requested here
No hosted run, no identity wave, no generator change and no M1. The STOPs on #431/oldTC03 and R25 stand, and #443/#559 keep priority. If the plan is acceptable, the next step is your admission of the single job above. Its harness would be reviewed before it runs.
The layout checker, version 2 (Python 3, standard library; python -I cert_rows.py <record.lex.tex> [limit ...])
"""Row anatomy of one committed certificate record (lexlean/core-module/2, authoring notation),and whether an acyclic layout of its rows into modules exists under a byte limit.Static read only: no build, no Lean. A row's closure is the nodes its type and value reach inthe module's shared node table. Sizes are serialized bytes: a node's full lines including its`@N := ` prefix, a row's own header block, and each module's import block.Layout rules (version 2, answering the review of 2026-11-16):- A unit is a set of rows that must share a module: one mutual group (`all:`), or rows sharing a packed core of over 64 KiB that no row names.- Units that cite each other in a cycle are merged into one unit, and every merge is reported: modules cannot import in a cycle.- A unit larger than the module limit makes the layout infeasible at that limit. It is reported and never placed, so no figure below comes from an oversized module.- Units are placed callees first; a module imports only modules placed before it, which is checked after placement, and every module's serialized size is checked against the limit.- The literal rows (`__prog`; `program` and `krate`) form one module every shard imports. A shard restates the literal nodes its rows reach, as rows do today.usage: python -I cert_rows.py <record.lex.tex> [limit-bytes ...]"""importcollections, re, systext=open(sys.argv[1], encoding="utf-8").read()
limits= [int(x) forxinsys.argv[2:]] or [2*1024*1024, 4*1024*1024, 6291456]
row_re=re.compile(r"^(definition|theorem|abbreviation) (\S+) : @(\d+)(?: := @(\d+))? \{")
node_re=re.compile(r"^@(\d+) := ")
lines=text.split("\n")
rows, header, nodes, cur, kind= [], {}, {}, None, Noneimports_end=next(ifori, linenumerate(lines) ifl.startswith("imports [") andl.endswith("]")
orl.startswith("]")) +1import_bytes=sum(len(l) +1forlinlines[:imports_end])
forlninlines[imports_end:]:
m=row_re.match(ln)
ifm:
cur=m[2]; kind="row"rows.append((cur, [int(m[3])] + ([int(m[4])] ifm[4] else []))); header[cur] =len(ln) +1continuem=node_re.match(ln)
ifm:
cur=int(m[1]); kind="node"; nodes[cur] = [ln]
continueifln.startswith("\\end"):
cur=None; kind=Noneelifkind=="row":
header[cur] +=len(ln) +1elifkind=="node":
nodes[cur].append(ln)
names= {nforn, _inrows}
size= {k: sum(len(s) +1forsinv) fork, vinnodes.items()}
body= {k: " ".join(v)[len(f"@{k} := "):] fork, vinnodes.items()}
kids= {k: [int(x) forxinre.findall(r"@(\d+)", t)] fork, tinbody.items()}
cites= {k: {cforcinre.findall(r"[A-Za-z_][\w.]*", t) ifcinnames} fork, tinbody.items()}
short=lambdan: n.rsplit(".", 1)[-1]
defclosure(start):
seen, todo=set(), list(start)
whiletodo:
n=todo.pop()
ifnnotinseen:
seen.add(n); todo.extend(kids.get(n, []))
returnseenNB=lambdas: sum(size[n] fornins)
cl= {n: closure(r) forn, rinrows}
lit= [nforn, _inrowsifshort(n) in ("__prog", "program", "krate")]
L=set().union(*(cl[n] forninlit)) iflitelseset()
other= [nforn, _inrowsifnnotinlit]
print(f"record {len(text):,} B; rows {len(rows)}; nodes {len(nodes):,} ({NB(nodes):,} B); imports {import_bytes:,} B")
forninlit:
print(f"literal row {short(n)}: closure {NB(cl[n]):,} B")
print(f"literal nodes restated by other rows: {NB(set().union(*(cl[n] &Lforninother))):,} of {NB(L):,} B")
forninsorted(other, key=lambdan: -NB(cl[n]))[:3]:
print(f"row {short(n)}: closure {NB(cl[n]):,} B")
forninother:
ifshort(n) in ("crate_ok", "root", "denote"):
print(f"row {short(n)}: closure {NB(cl[n] -L):,} B outside the literals")
# unitsparent= {n: nforninother}
deffind(x):
whileparent[x] !=x:
parent[x] =parent[parent[x]]; x=parent[x]
returnxdefunion(a, b):
a, b=find(a), find(b)
ifa!=b:
parent[b] =aforminre.finditer(r"^(?:definition|theorem|abbreviation) (\S+) .*?\n all: \[([^\]]*)\]", text, re.M):
group= [g.strip() forginm[2].split(",") ifg.strip() inparent]
forgingroup[1:]:
union(group[0], g)
owners=collections.defaultdict(list)
forninother:
forkincl[n] -L:
owners[k].append(n)
shared=collections.Counter()
fork, nsinowners.items():
forainns[1:]:
shared[(ns[0], a)] +=size[k]
for (a, b), vinshared.items():
ifv>64*1024:
union(a, b)
defunit_graph():
units=collections.defaultdict(list)
forninother:
units[find(n)].append(n)
deps= {u: set() foruinunits}
forninother:
forkincl[n]:
forcincites.get(k, ()):
ifcinparentandfind(c) !=find(n):
deps[find(n)].add(find(c))
returnunits, deps# merge cycles until the unit graph is acyclic (Tarjan, iterative)merged_cycles= []
whileTrue:
units, deps=unit_graph()
index, low, stack, on, sccs, counter= {}, {}, [], set(), [], [0]
forrootinsorted(units):
ifrootinindex:
continuework= [(root, iter(sorted(deps[root])))]
index[root] =low[root] =counter[0]; counter[0] +=1; stack.append(root); on.add(root)
whilework:
v, it=work[-1]
w=next(it, None)
ifwisnotNone:
ifwnotinindex:
index[w] =low[w] =counter[0]; counter[0] +=1; stack.append(w); on.add(w)
work.append((w, iter(sorted(deps[w]))))
elifwinon:
low[v] =min(low[v], index[w])
continuework.pop()
ifwork:
low[work[-1][0]] =min(low[work[-1][0]], low[v])
iflow[v] ==index[v]:
comp= []
whileTrue:
x=stack.pop(); on.discard(x); comp.append(x)
ifx==v:
breaksccs.append(comp)
cycles= [cforcinsccsiflen(c) >1]
ifnotcycles:
order= [c[0] forcinsccs] # Tarjan emits callees firstbreakforcincycles:
merged_cycles.append(sum(len(units[u]) foruinc))
foruinc[1:]:
union(c[0], u)
print(f"units {len(units)}; cycles merged: {len(merged_cycles)} (rows in each: {merged_cyclesor'none'})")
ucl= {u: set().union(*(cl[n] forninunits[u])) foruinunits}
uhdr= {u: sum(header[n] forninunits[u]) foruinunits}
big=max(units, key=lambdau: NB(ucl[u]) +uhdr[u])
print(f"largest unit: {len(units[big])} rows, {NB(ucl[big]) +uhdr[big] +import_bytes:,} B as a module "f"({', '.join(short(n) forninunits[big][:6])})")
lit_module=import_bytes+NB(L) +sum(header[n] forninlit)
forlimitinlimits:
over= [uforuinorderifimport_bytes+NB(ucl[u]) +uhdr[u] >limit]
ifover:
print(f"limit {limit:,}: INFEASIBLE, {len(over)} unit(s) exceed it alone, largest "f"{max(import_bytes+NB(ucl[u]) +uhdr[u] foruinover):,} B")
continueiflit_module>limit:
print(f"limit {limit:,}: INFEASIBLE, the literal module alone is {lit_module:,} B")
continueshards, place, cur, cn, ch= [], {}, [], set(), 0foruinorder:
size_with=import_bytes+NB(cn|ucl[u]) +ch+uhdr[u]
ifcurandsize_with>limit:
shards.append((cur, cn, ch)); cur, cn, ch= [], set(), 0cur.append(u); cn|=ucl[u]; ch+=uhdr[u]; place[u] =len(shards)
shards.append((cur, cn, ch))
backward=sum(1foruinunitsfordindeps[u] ifplace[d] >place[u])
sizes= [import_bytes+NB(s) +hfor_, s, hinshards]
worst=max(sizes)
whole=sum(sizes) +lit_moduleassertbackward==0andworst<=limitprint(f"limit {limit:,}: {len(shards)} shards + literal module ({lit_module:,} B); largest shard {worst:,} B; "f"imports acyclic (0 backward edges); total {whole:,} B vs record {len(text):,} B "f"({100* (whole-len(text)) /len(text):+.1f}%)")
Activity
[-][v0.4] Self-hosting: the bootstrap fixed point (stage 1, stage 2, byte-identical) and removal of the Rust compiler[/-][+]Self-hosting: the bootstrap fixed point (stage 1, stage 2, byte-identical) and removal of the Rust compiler[/+]humuhumu33 commentedon Nov 12, 2026
Proposal for #273: modular certification and the shape of stage 1
A proposal for the owner and maintainer to decide, posted here as the 2026-10-22 ruling asks. No milestone, label or title is changed, and nothing is built or pushed. It came out of a read-only survey of what stands between
release/v0.4and stage 1. That survey found that porting is not the binding constraint: certifying a compiler-sized command root is.Base:
release/v0.4ataaf845507. Counted means measured on that tree. Estimated means extrapolated, and each estimate names its source.Decision asked
Lower one program per project and target instead of one per root. Each function's certificate rows are then generated once, in shard modules cut along the call graph. Each root keeps a small certificate A, B and E of its own that cites the shards.
The calculus,
RustSemantics, and the library'ssound,simulateandcomposedo not change. Every theorem a root has today keeps its statement except one thing: the entry ise_rinstead of0. This is the smallest change that lets a compiler-sized command root be certified. It also cuts the bootstrap's certificates about in half today.Three smaller decisions make stage 1 buildable:
language/tree reaches the step through a newembeddedhost request, and the certified step checks its digest.rust_rendererstays the recorded digest of the Rust renderer files until the removal.1. The problem, measured
A root's certificates restate its whole closure. Certificate A's statement is
RunConv P 0 …over the programPlowered for that root alone (§17.17, Statement). Its rows are__prog, the encoders, and__fits_kand__rel_kfor each function of the closure. Certificate B has onefun<n>derivation per function of the same program. So a function that two roots call is lowered, related and derived twice.Counted on the 62 committed bootstrap roots (the program records
bootstrap/expected/verify/preserve/program/R*.jsonandpreservation.json; the script at the end, which identifies functions structurally up to renumbering):lowerBodies, A), againstmax_file_bytes6,291,456Projection to stage 1. This is estimated: it scales the bootstrap's distinct program, about 4.7 MB for about 14,900 Rust lines ported, to the compiler's about 150,000 lines.
2. Options
max_file_bytesto about 512 MBrun,RustSemantics,soundandsimulategain an environment and a frame lemma3. Design S
3.1 Lowering (§17.14,
production/lower.rs)LLI9001.max_ir_nodesis charged per program, as now.3.2 Certificates (§17.17,
production/certificate*)…P.Fn<s>(one per shard)__fn_kper function of the shard…P__prog, the program as a lookup over the__fn_kconstants (see risk R1)…A.<s>(one per shard)__fits_k,__rel_k, the encoders first used there…B.<target>.<s>fun<n>for each function of the shard…B.<target>krate,flags,crate_ok,root(simulate)…R<i>(one per root)denote,root : RunConv __prog e_i ……R<i>.Compose.<target>composeapplied toR<i>.rootandB.<target>.rootatfnIdent e_i__rel_krelates functionkofPto its source definition, andfun<n>derives functionnof the crate. OnlyP, the numbering and the module boundaries move.0to functione_i. E's boundary form already takesfnIdent e. To confirm in M1: whethercomposeassumes entry 0 anywhere.max_file_bytesbounds every file Lean opens. The early lower bounds are computed per component.preservation.jsonlists the shards, each with its module, byte length and SHA-256, and per root its entry, its A and E modules, and the target's B root module. This is a schema change (schemas/preservation.schema.json), so the language-1.2 compiler-semantics ID moves. Languages 1.0 and 1.1 are untouched, since production is 1.2 only.3.3 Packages (§17.16, §24.7,
calculus/rust/package.rs)lexlean/production-request/1is unchanged: one package per requested root.src/lib.rsis the project crate for the target (the one certificate B is about) plus that root's export wrapper.Cargo.tomlandprovenance.jsonare as now; the provenance also binds the crate digest that B states.3.4 Verification (§22,
verify/)The shards form a directed acyclic graph of imports. Verification stages and compiles them in that order through the existing pool (
verify/pool.rs, whose output is width-independent by contract). This is also the parallel certificate stage the gate-speed hand-over asked for. Today 1,397 of the export's 1,966 s are certificates checked one at a time.3.5 What does not change
Corrrules.4. The shape of stage 1
LexLeanBoot.Compiler.stepinbootstrap/, with a committed production request for it aloneselfhost/project would importbootstrapas a source package and certify every function a second time.language/(counted; 32,670,965 of it the preservation library)?embedded (path : String), answered byEvent.read. RB-24's printed driver serves it from aninclude_bytes!table, and the package gains anassets/tree. The certified step computes the §11.5 tree digest of what it reads and refuses anything but its compiled-in compiler-semantics ID. It needs no effect.rust_rendererin provenance?RENDERER_FILES. Stage 1 reads it fromlanguage/as data, and it moves once, at FP-06.bootstrap/srcnow, every slice landing would move the compiler-semantics ID. This is the maintainer's 2026-10-22 decision 4 ("at the fixed point").preservation.jsonwith its digests is committed. The bootstrap export as it is today stays committed until the maintainer decides otherwise.bootstrap/expectedis already 258,401,428 bytes for 62 packages (counted).5. Risks, and the measurement that decides them (M1)
__progas a list and as a balanced tree__progandkrateas a tree. A library lemma, proved once, equates the tree lookup with today's list lookup.max_file_bytesM1 decision gate. M1 is a spike on a branch, never landed, run on CI rather than the laptop. It prototypes 3.1 and 3.2 on the bootstrap and reports:
S proceeds if the total is below today's, every shard is under the cap, and the export is no slower at width 4.
6. Plan
Every step follows R3: register rows and SPEC first, a failing case, plants, a VERIFICATION entry. All changes are in stage 0 (Rust and SPEC); the
.lex.textwins of the changed generator are track C's.model/ids.toml)production/lower.rs, layout)certificate/data_a,certificate.rs)crate_ok,rootper target (certificate/data_b)package.rs, provenance)verify/mod.rs)regenerate.yml. One identity move, landed with M3-M7 as one batch, as #480 landed BS-25..34.embeddedrequest: PD-10 row, RB-24 driver arm,assets/in the package layoutSize (estimated, from no measurement of this work). M2-M7 are 6 Rust PRs of about 500 to 2,000 changed lines each, plus one regeneration. With reviews, that is 2 to 4 weeks elapsed. M1 is 2 to 3 days.
Effect on the writing tracks.
BScases' export comparison changes from per-root packages to a shared crate with wrappers. Every case's comparison step needs one mechanical edit at M6, done by M6 itself.__prog.7. Questions for the maintainer
embeddedrequest (one binary), or a data tree beside the binary?rust_rendereras the recorded constant until FP-06?Sources
preservation.jsonofbootstrap/expected/verify/preserve/ataaf845507, and the repository tree through the GitHub API.The measurement script (Python 3, standard library; run as
python dedupe.py <dir>, with the 62R*.jsonandpreservation.jsonin that directory)🤖 Generated with Claude Code
afflom commentedon Nov 12, 2026
Maintainer design readback of 6823454237: the smallest next decision is per-root certificate-sharding feasibility, separated from project-wide program union. A compiler-sized single root still needs its A/B certificates split even if no functions are shared across roots. Project union adds numbering, package-content and closure-policy changes; its deduplication benefit is a separate question.
Two evidence boundaries matter before choosing a spike:
Existing implementing owner: first separate the minimal sharding contract and its concrete remaining proof obstacle from the project-union/package redesign. This can be a concise source/design delta using the existing records. It should identify whether current per-root statements and package behavior can remain intact, and what prevents splitting the oversized certificate. That is the next reviewable decision before choosing the smallest necessary hosted experiment.
The existing R25 group-union admission/STOP remains in force; this static proposal does not authorize that experiment, the M1 runs, an identity wave, raised limits, or M2–M10. #387's isolated-context proposal is distinct and remains unaccepted. The embedded request, renderer transition, certificate storage and lane allocation also remain proposed decisions. No build, probe, census, export or gate was repeated for this readback.
The prior owner ruling also remains unchanged: #267–#277 are unscheduled, and this is not acceptance of a new v0.4 objective or a milestone change. The recommendation above narrows the proposal for a decision; it does not schedule its implementation.
humuhumu33 commentedon Nov 16, 2026
#273: the minimal per-root sharding contract, separated from project union
This answers the readback of 2026-11-12 (afflom): separate the minimal sharding contract and its concrete remaining obstacle from the project-union and package redesign, using existing records. Nothing was built, verified, exported or run under Lean. The figures come from a static read of the committed records at
maina74b1f99b, by the script at the end.release/v0.5has the same certificate generator under another semantic ID; its R30 A is the same size, its R34 A is 5,324,482 bytes and its R30 B is 5,217,111 bytes, which changes no conclusion. Counted means read from those bytes. Estimated means extrapolated, and each estimate names its basis.Answer
A root's certificates can be split into modules without changing any root's statement or package.
compose's use offnIdent 0, so this contract does not depend onComposegeneralising to a nonzero entry.Three generated rows grow with the whole program and cannot simply move to another module:
__progin certificate A,programandkratein certificate B,crate_okin certificate B.Two of them already have a split that needs no new proof. The remaining question is one kernel-cost measurement, not a proof (§4).
1. What is being separated
__prog,program,krate,crate_okby namee_rSharding is what a compiler-sized root needs. Union is a separate saving that can be decided later or never.
2. Where the bytes are (counted)
These are the two largest roots of the bootstrap export, measured against the bootstrap's own
max_file_bytesof 6,291,456. The project already raised that limit from the default of 4,194,304.RuntimeValidate.validateRuntime, 250 functionsRustStd)RustBodies.lowerBodiesSo the bootstrap is already near its limit without any stage 1. The next slice that grows either closure is refused.
Row anatomy of R30. Bytes are node-table text; records add row headers and node prefixes, about 1.2× more.
__prog184,965program205,513,krate495,085__rel_89988,419fun23297,600__relrows of one mutual group (23, 71, 75, 77, 89) sharing one packed core, 989,409fun23crate_ok(outside the literals)Nat.casesOnlevel per functionroot,denoteCut greedily along the row graph (callees first, no unit split), at two byte budgets per shard:
The overhead is the literal nodes each shard restates: a
__rel_korfun<n>row states the body it relates. B pays more because its rows restate more ofkrate.3. What prevents the split today
__prog,programandkrateare one row each, so they grow with the whole programrows.rs(__prog),data_b.rs(program,krate)Program.mkover the list of those constants. Statements cite the constant by name, so their text does not change. A and B build the same program with the same builder, so the literal could live in one module that both import.crate_okis one row: a chain ofcountNat.casesOnlevelsdata_b.rscrate_ok_value∀ x fn h, FunOK (x + d). Name the level at each shard boundary as a row of that shard; the level above cites it. The kernel checks the samesucc m + dagainstm + (d+1)it checks between levels today. No new lemma.data_arecursion planpreservation.jsonschema;certificate.rs;verify/staging and the auditR<i>.S<k>andR<i>.RustStd.S<k>beside the unchangedR<i>andR<i>.RustStd. Weigh each module againstmax_file_bytes, and move the early refusal's lower bound from the root to a unit. Stage modules in import order through the existing pool.preservation.jsonlists each module's path, length and SHA-256.O4 changes the schema of
preservation.jsonand every record, so the language-1.2 compiler-semantics ID moves once. That is one identity wave, the same cost as any record change.4. The one open question
O1 is the only change that alters what the kernel evaluates.
Side conditions are
Eq.reflat a lookup into the program, and every rule's statement mentions the program. Today the kernel reduces a lookup through one literal list. After O1 it unfolds the per-function constant at the index found. The number of list steps per lookup is the same for the same program, because sharding a root changes no index, so this contract makes no lookup longer.What is unknown is whether the kernel's sharing of the unfolded literal behaves the same when the literal is assembled from constants, both within a module and across the modules a shard imports. That is the measurement to make first:
It is a single root, run once each way. It is not M1, and it repeats no census. It needs your authorisation as a hosted run.
The program's length is a separate question that only scale raises, and it is project union's R1 as well: at compiler size the list may be long enough that each lookup is slow. That is already true of an unsharded root of the same size, so it is not an obstacle sharding creates.
5. When the literal rows outgrow the limit (estimated)
These rates come from R30 alone (250 functions). One root does not represent the compiler's mix of functions.
krateprogram__progcrate_okBy the bootstrap's existing count, a compiler-sized root passes the first of these thresholds even if that count is several times too high. So O1 and O2 are required for stage 1 whether or not project union is chosen. The bootstrap counted 4,698 functions summed over its 62 roots, for about 15,000 lines of ported Rust; the compiler is 158,583 lines (counted on
main).6. Evidence boundaries
crate_ok_valueand on the existing between-level defeq. A generated level row checked under Lean would confirm it.The measurement script (Python 3, standard library;
python -I cert_rows.py <record.lex.tex> [budget ...])🤖 Generated with Claude Code
afflom commentedon Nov 16, 2026
The per-root contract answers the earlier request to separate sharding from project union: entry0, numbering and packages stay fixed. That narrows the next decision usefully. The reported sizes remain static evidence; I have not repeated the census or run the simulation.
Two limits should remain explicit before calling kernel cost the only open question. The posted cut simulation tolerates dependency cycles and admits an oversized first unit; its figures therefore do not establish an acyclic layout within actual serialized-module limits. Naming crate_ok boundary levels also retains a generated-term correspondence obligation even if no library lemma changes. These are contract/qualification gaps, not demonstrated impossibility.
Please make the requested R30 comparison concrete: pin the exact baseline/candidate delta, distinguish literal factoring from imported-shard behavior, and specify runner/cache controls, resource and stopping bounds, and retained source/output/measurement custody. Budgets remain planning assumptions until observed, and one pair gives exploratory evidence only. Reuse existing records; no repeat census is requested. This design review does not admit a hosted run or identity wave. Existing #431/oldTC03 and R25 STOPs remain intact, and #443/#559's targeted owner repairs remain the delivery priority.
Bounded review: issue273-sharding-contract-review-20261116.json, SHA256982549507f2c6bde908fdf911fe12633ae3ba4b5dc5b2fd66e53f50a2432d4f9.
humuhumu33 commentedon Nov 16, 2026
#273: the two qualification gaps, and the R30 comparison as a concrete plan
This replies to the review of 2026-11-16 (afflom). Nothing was built, verified or run under Lean. The figures are static reads of committed records at
maina74b1f99bba637e51d19fb4efc508316aafa6664(tree0af41e384c9df2d6b6d9873accbaa8e91038d264), and of the existing telemetry of two CI runs. No census was repeated. This asks for no admission; it is the plan the review requested.1. The layout gap, corrected
The review is right that the first script tolerated cycles and admitted an oversized first unit. Version 2 (at the end) changes four things:
@N :=prefix, row headers, and the import block.Planted defects, on synthetic records:
INFEASIBLE, 1 unit(s) exceed it aloneResults on the four largest records (counted; serialized bytes):
__relgroup)fun23)__rel_8)fun8)Every total includes the literal module that all the shards import: 296,708 B for R30 A and 990,826 B for R30 B.
So an acyclic layout exists for all four within serialized limits of 2 MiB and above, but not at 1 MiB for R30 A. Certificate B costs about 22 to 35% more bytes, because its rows restate most of
krate. These remain planning figures until a module is staged.2. The generated-term obligation, stated as a check
Naming
crate_ok's boundary levels (and, for O1, the per-function constants of the literal) changes no lemma. It still leaves the obligation the review names: the named rows must be exactly the terms they replace. The candidate discharges this by a comparison rather than an argument.__fn_k,__adt_j,crate_ok_from_d) in the candidate's data and compare the result, node for node, with the baseline's__prog,program,krateandcrate_ok. They must be equal after the canonical renumbering the core module already performs.[], because it is a definition with no proof content;crate_ok_from_dpins whatcrate_okpins.Any inequality fails the arm before Lean runs. The kernel's acceptance of the candidate is then the remaining check, and that is what §3 measures.
3. The R30 comparison
The baseline (pinned). R30
LexLeanBoot.RuntimeValidate.validateRuntimeata74b1f99b, semantic ID prefixCe734249a01f6588cb76caa0d10039d36:R30.lex.tex(A)4b2287f7546c879e76e8e112ccb2b2384f9dbac3700741fe218877c1334d3ce4R30/RustStd.lex.tex(B)c4cef2676da20187fa6ebac4114d00e01ab5be04246179c6620598f3cb802fa3R30/Compose/RustStd.lex.tex(E)24f9cfb7aff3992e2835ab6be618cca32ab7878113730fc4ecbff29d2d78ea17The arms. Each arm differs from the one before by one change, so each effect is attributed by itself:
__fn_kand__adt_jconstants in the same module;__progandprogramdefined from themR30.P, which A and B both importcrate_oknamed at the shard boundaries)crate_oksplitE is unchanged in every arm, apart from what it imports. It is checked in every arm, because it imports A and B.
Construction. The construction is a record-to-record transform of the pinned data, never a change to the generator. It uses the conformance crate's existing path, as the plants of
SP-14,SP-15andSP-16already do: read the record back toCoreModuledata, transform it, render withbackend::core::lean_text_legacy, stage it withpreservation::staged, then compile and check withpreservation::compile_textandcheck. It lives on a branch that is never landed. Nothing is committed tomain, no record or export changes, and no identity moves.The exact delta is pinned by three things:
What is measured, per arm and per module. For each module:
lean: wall time and peak RSS;leanchecker: wall time and peak RSS;These are the fields of the verifier's existing telemetry (§22.12), so the same parser reads A0 and the candidates.
Runner and cache controls.
ubuntu-24.04runner, as the gate uses (§9.4), from a clean checkout of the pinned commit.lean-toolchainandrust-toolchain.toml.actions/cacheand no restored Lake or build directory.Why rounds: in the existing records, the same modules at the same commit differ by 1.4 to 1.65 times between two runs at width 2:
leanleanleancheckerPeak RSS agrees within about 2% (2.04 to 2.09 GB for
lean, 1.59 to 1.69 GB forleanchecker). A single pair could not separate a real time difference under about 2×; memory it could.Resource and stopping bounds.
Every arm's expansion equality (§2) passes before any Lean process starts. A failure there stops the job.
Custody. One artifact per run, retained for 90 days, holding:
rust-toolchain.toml,lean-toolchainandCargo.lock;rustc -vVandlean --versionreport;lean,leancheckerandlakeexecutables (the fields oflexlean/ci-bootstrap-export/2);The result is reported here with the run ID. None of it is an input to any recipe or committed output.
How it would be read. Exploratory, as the review says: one job of three rounds.
leanplusleancheckertime within 2× of A0, and its peak RSS within 25%.4. Not requested here
No hosted run, no identity wave, no generator change and no M1. The STOPs on #431/oldTC03 and R25 stand, and #443/#559 keep priority. If the plan is acceptable, the next step is your admission of the single job above. Its harness would be reviewed before it runs.
The layout checker, version 2 (Python 3, standard library;
python -I cert_rows.py <record.lex.tex> [limit ...])🤖 Generated with Claude Code