normativeView source

Alpha-Haskell Language Specification#

Status: normative for the Phase 0 bootstrap language

PRD identity: sha256:255c1b4861512fb715368799a0ab1d63aacb82fae6352a2aff0a2f50bd2f091c

1. Scope and conformance#

Alpha-Haskell is the sovereign, dependently typed source language of the Alpha learning compiler. This document specifies the language that the trusted kernel accepts today. It does not describe planned syntax as if it were implemented.

A conforming implementation MUST:

  1. parse source into a span-carrying surface tree without executing it;
  2. elaborate names to de Bruijn indices before trusted checking;
  3. accept a term only when the trusted kernel infers or checks its type;
  4. enforce runtime quantities in the kernel, not as a lint;
  5. normalize terms before deciding definitional equality;
  6. represent effects explicitly in computation types;
  7. reject unmarked divergence from the total fragment;
  8. preserve proof and runtime identities through typed witnesses;
  9. fail closed when a required proof, target, dataset, checkpoint, or device witness is absent; and
  10. provide no host implementation as a fallback for a target operation.

The trusted source boundary is Alpha.Core.Trusted.*. Surface parsing, diagnostics, elaboration, target lowering, scheduling, package management, and runtime submission are untrusted in the proof-theoretic sense: their products must be checked by a smaller trusted boundary before they gain authority.

2. Lexical grammar#

Source bytes must be canonical UTF-8. Outside quoted literals and comments, characters are ASCII; token separators are space, tab, LF, and CR. A line comment begins with -- and ends at newline or end of input. Non-ASCII whitespace is not a token separator. Other ASCII control bytes are payload only inside literals and comments; raw CR/LF remain forbidden in quoted literals.

Identifiers begin with an ASCII letter or _; subsequent characters may also be decimal digits, ', -, /, or .. let* is one reserved form head; * is not an identifier character. A numeric token begins with a digit, or with - immediately followed by a digit (a signed token): decimal (255), hexadecimal (0xff) or binary (0b1010), with _ allowed only between digits of the radix (1_, 1__0, 0x_1 are ALPHA-LITERAL-BAD-SEPARATOR; an empty digit body such as 0x is ALPHA-LITERAL-MISSING-DIGITS); digits.digits or an e exponent makes it a decimal token (§3.1). Under alpha-2026 an unsigned integer token (in any radix) is accepted only as the level after Type, as the operand of (byte …) and as an element of (bytes …); a numeric token anywhere else is a literal term, which the edition gate refuses (ALPHA-EDITION-UNSUPPORTED-FORM). Punctuation is (, ), :, ., =, and the bind arrow <-.

The bare identifiers zero, Nat, Byte, Bytes and BytesBuilder are always the built-in atoms, and Type followed by a numeric token is a universe. A binder (lambda, pi, sigma, let; a family parameter, index or field) or a definition spelled zero, Nat, Byte, Bytes or BytesBuilder could never be referred to, and is refused (ALPHA-ELAB-RESERVED-NAME).

The identifier after an opening ( is the term's head. A head spelled like a form (lambda, pi, let, succ, do, prophecy, resolve, hole, …) is that form in every edition; the edition gate then refuses a form the selected edition lacks. A definition or binder may still be spelled like a form head (succ, do, prophecy, resolve, hole, …), but it is applied with an explicit (app resolve x), never as (resolve x). The draft sugars record, project, update, match and match-with are forms only when their structural prefix matches, so ordinary calls of functions with those names keep their alpha-2026 meaning.

Every token and surface term carries a half-open source span containing byte offset, one-based line, and one-based column positions. A lexical or parse failure is a structured Diagnostic with a stable code and a parse proof obligation.

3. Surface grammar#

The implemented generation-zero grammar is prefix S-expression syntax:

term ::= identifier
       | "Type" natural
       | "Nat"
       | "zero"
       | "(" "succ" term ")"
       | "(" "Fin" term ")"
       | "(" "fzero" term ")"
       | "(" "fsucc" term term ")"
       | "(" "app" term term+ ")"
       | "(" identifier term+ ")"        -- identifier not a form head
       | "(" "first" term ")"
       | "(" "second" term ")"
       | "(" "pair" term term term ")"
       | "(" "equal" term term term ")"
       | "(" "refl" term term ")"
       | "(" "transport" term term term ")"
       | "(" "pi" quantity identifier ":" term "." term ")"
       | "(" "lambda" quantity identifier ":" term "." term ")"
       | "(" "sigma" quantity identifier ":" term "." term ")"
       | "(" "effects" effect* [ ":" term ] ")"
       | "(" "computation" term term ")"
       | "(" "partial" term ")"

quantity ::= "erased" | "affine" | "linear" | "unrestricted"

effect ::= "State" | "Random" | "Device" | "File" | "Network"
         | "Divergence"

Application arity (reconciled 2026-09-03, LP-102). app is n-ary in the surface language: (app f a₁ a₂ … aₙ) with n ≥ 1 is a left-associated sugar that elaborates to nested binary core applications application (… (application (application f a₁) a₂) …) aₙ. The core (§4) keeps application f x strictly binary. A surface app with fewer than two operands is the hard error ALPHA-PARSE-APP. The earlier text declared app binary while the implemented parser (explicitApplication) has always folded extra operands; the corpus relies on the n-ary form pervasively, so the specification now records the implemented rule. Consequence for authors: an n-ary app supplies every trailing operand to the head — a helper-chain whose links are written as sibling operands instead of nested applications is grammatically valid but semantically over-applied (the "flattened chain" defect class); see debug/scan-flattened-chains.py. The bare spelling (f a₁ … aₙ), whose head is an identifier that is not a form head, is the same sugar in every edition; (f) is also ALPHA-PARSE-APP. Its head must be an identifier: ((lambda …) x) is ALPHA-PARSE-UNEXPECTED, so a non-variable function is applied with (app (lambda …) x).

3.1 Extended surface forms (reconciled 2026-09-03, LP-103)#

The implemented parser accepts the following forms beyond the generation-zero grammar above. They are implemented and accepted; their edition status (stable / experimental) is assigned by the alpha-2026 edition manifest (LP-105), not here. A stable core of 51 alpha-2026 forms is frozen in docs/editions/alpha-2026.stable.json; each has a full contract in docs/language/features/form-*.md, whose tests run via debug/feature-contract-tests.py. The normative per-form table — head, arity, surface constructor, and the core builder it elaborates to — is generated from the sources by debug/form-inventory.py into docs/generated/ALPHA-LIVE-FORM-INVENTORY.json (key reconciliation; the script also writes a Markdown rendering, ALPHA-LIVE-FORM-INVENTORY.md, which is not checked in); this section is a grouped summary of that excerpt and must not be edited by hand where they disagree. A head that appears in the parser but not in that table is a specification defect.

  • Naturals: (nat-eliminate motive zeroCase successorCase scrutinee) (arity 4, core RNatEliminate); (nat-less-than a b) (2, RNatLessThan); (nat-to-byte n) (1, RNatToByte; in every edition; the byte n mod 256, so 256 wraps to (byte 0), in the normalizer, the weak-head evaluator and the runtime alike). Draft edition alpha-2027 only (L9/L10): the compact natural literal, written bare (255, 0xff, 0b1010) or as (nat-literal N) (core RNatLiteral, at most 4096 decimal digits, definitionally equal to its unary form; a bare literal also elaborates at an expected fixed-width word type); see nat-literal. (compile-time value) (1, draft alpha-2027 only) normalizes its closed operand at elaboration and substitutes the first-order normal form; an operand that refers to a local binder is ALPHA-COMPILE-TIME-OPEN, one whose normal form is not first-order data is ALPHA-COMPILE-TIME-STUCK, and a natural past 64 bits is ALPHA-COMPILE-TIME-RANGE. Draft edition alpha-2027 only (L12k, PRD 08 N1): (nat-add a b), (nat-multiply a b), (nat-subtract a b), (nat-divide a b), (nat-modulo a b) (2, core RNatAdd / RNatMultiply / RNatSubtract / RNatDivide / RNatModulo) — natural arithmetic: each folds to a compact literal in O(digits) when both operands are closed naturals; subtraction saturates at zero, x / 0 = 0, x mod 0 = x (total, stated); an open operand leaves the node neutral in the normaliser, and erasure emits a RUNTIME node (RuntimeNatAdd … RuntimeNatModulo, runtime-term tags 0x33–0x37, runtime-graph opcodes 0x32–0x36) that the evaluator lane executes in one machine operation on 64-bit words — add and multiply trap on overflow exactly as succ does (coppelius D21, 2026-09-16; before that erasure refused an unfolded node and no lane executed it).
  • Decimal literals (draft edition alpha-2027, L12b): the token [-]digits.digits / [-]digits[.digits]e[-]digits (E accepted; exponent digits mandatory — 1e is ALPHA-LITERAL-MISSING-DIGITS; 1. is not a decimal) has NO type of its own: at an expected type definitionally Data.Float32Bits.InferenceFloat32 (F32) or Model.Parameter.ModelFloat64Bits (F64) it elaborates to that family's constructor record holding the exact round-to-nearest-even bits (one rounding, rational arithmetic; subnormals and underflow by the same rule; -0.0 keeps its sign); finite overflow is ALPHA-LITERAL-OUT-OF-RANGE; any other expected type, or none, is ALPHA-LITERAL-NEEDS-TYPE. An integer spelling at F32/F64 converts the same way. NaN and the infinities are never literals (Std.Float names them).
  • Bytes and byte: Byte, Bytes (types); (byte n) (core RByteLiteral), whose operand is one unsigned integer token in any radix of §2 ((byte 60), (byte 0x3c), (byte 0b0011_1100)) with value 0 to 255 (ALPHA-TYPE-BYTE-LITERAL otherwise); (bytes e…), whose elements are unsigned integer tokens or arbitrary Byte terms: all tokens elaborate to RBytesLiteral, otherwise the elements elaborate to a bytes-cons chain; (byte-to-nat b) (1); (byte-equal a b), (byte-less-than a b) (2); draft alpha-2027 only (L21): (byte-and a b), (byte-or a b), (byte-xor a b), (byte-shift-left a n), (byte-shift-right a n) (2, core RByteAnd / RByteOr / RByteXor / RByteShiftLeft / RByteShiftRight; Byte -> Byte -> Byte, a shift by eight or more yields zero); (bytes-cons b bs) (2, the constructor of the Bytes view that bytes-eliminate takes apart), (bytes-append x y), (bytes-equal x y), (bytes-set-index bs i), (bytes-index-nonzero bs i) (2); (bytes-set-free-index bs i depth offset) (4); (bytes-length bs), (bytes-head bs), (bytes-tail bs), (bytes-checksum bs) (1); (bytes-packbits-decode count recipe) (2, RBytesPackbitsDecode; Nat -> Bytes -> Bytes: exactly count PackBits commands, a control byte C < 128 copying the next C + 1 bytes and C ≥ 128 emitting C - 127 zeros; a malformed recipe decodes to (bytes), never to a partial result); (bytes-eliminate motive emptyCase consCase scrutinee) (4, RBytesEliminate). The reduction rules of each form are stated in its contract under features (form-bytes-*.md).
  • Binary32 (draft alpha-2027 only, L13c): (f32-add a b), (f32-subtract a b), (f32-multiply a b), (f32-divide a b) (2), (f32-sqrt a) (1), (f32-less-than a b), (f32-equal a b) (2, result a Nat boolean); core RF32Add … RF32Equal. The operands are of a four-byte record family (one constructor, four unrestricted Byte fields, e.g. Std.Float F32; ALPHA-TYPE-F32-RECORD otherwise). The normalizer never computes them; only the x86-64 SSE scalar lowering (profile x86-64-sse-scalar-strict) realizes them, and every other lane refuses them by name.
  • Bytes builder: BytesBuilder (type); (bytes-builder-empty) (0), (bytes-builder-chunk bs) (1), (bytes-builder-append l r) (2), (bytes-builder-build builder) (1), and (runtime-image-v4-build builder) (1, RRuntimeImageV4Build).
  • Compiler-native images: (native-physical-image-build T v) (2, RNativePhysicalImageBuild), with compiler-native-encode a second spelling of the same form (same surface and core node): T : Type l and v : T give Bytes. The checker never runs the encoder (the node is inert to the normalizer), and the type does not restrict T to the families the encoder supports: an unsupported value checks and fails when the compiler's realization machine encodes it. The native evaluator cannot execute it.
  • Computations and effects: (effect-row) (the effect-row type, 0, REffectRowType); (return effects value) (2, RReturn); (bind effects result first continuation) (4, RBind); draft alpha-2027 (do effects result (name <- computation) (computation)... (return value)) lowers to nested RBind/RReturn with the same row. A named step may state its quantity before the name; shorthand is unrestricted. See the do contract; (read-file path) (1, RReadFile); (write-file path contents) (2, RWriteFile).
  • Let: (let quantity name [: annotation] = value in body) (binder form, core RLet). The quantity is mandatory, here and in pi, lambda and sigma: a binder name directly followed by : or = (the usual omission) is ALPHA-PARSE-QUANTITY-MISSING, with a fix-it inserting unrestricted; any other word in the quantity position is ALPHA-PARSE-QUANTITY (the retired restricted is offered its replacement affine). Draft alpha-2027 also accepts (let* (quantity name [: annotation] = value)+ in body), which lowers to nested RLet without substitution. See the let* contract.
  • Families and eliminators (structured forms, own parsers): (family F args…) (RFamilyApplication); (constructor F C args…) (RConstructorApplication); (eliminate F motive scrutinee (branch C binders… . body)…) (REliminate, branches exhaustive and in declaration order); branch is not a top-level form. Draft alpha-2027 additionally accepts named single-constructor record sugar: (record F (field = value)+), (project F field value), and (update F value (field = replacement)+). These elaborate respectively to the existing RConstructorApplication and REliminate core forms; they add no core constructor or serialized format. The normative contract is records. It also accepts readable exhaustive matching: (match F scrutinee (case C fields... [(ih induction)] . body)...) infers a constant motive from the expected result, while (match-with F motive scrutinee cases...) supplies the motive. Both lower to the existing REliminate; constructor order and hidden arities come from the checked family. The normative contract is matching. case is structural only within those forms, and ih is structural only as an induction-hypothesis marker immediately after the corresponding recursive field binder.
  • Prophecy ghost variables (draft edition alpha-2027): (prophecy effects (ghost : A) (resolved . R) body) binds an erased ghost ghost : A in R and body, and resolved in R; it elaborates to core RProphecy (§9.1). The core spelling (prophecy effects A relation body) (arity 4) is the same node operand for operand. (resolve ghost value witness) (arity 3) is the dependent pair that closes ghost's prophecy — or its return where a computation is expected — and may stand in place of a do's final (return value). The normative contract is prophecy.

Indexed-family declarations are module declarations checked by the same trusted inductive-family kernel used by the typed construction API. A family block uses family <name> : Type <level>, followed by ordered parameter, index, constructor, field, recursive, recursive-index, and result records, and terminates with end-family. Families precede value definitions, recursive occurrences are explicit, and only imported families enter a module's scope. Malformed order, missing terminators, duplicate or ambiguous families, a value field whose type mentions the family being declared (§7), incomplete index results, and ill-typed telescope entries are hard errors. Eliminators retain exhaustive ordered branch checking.

Draft alpha-2027 typed holes#

(hole NAME) marks a position not yet written. It never elaborates: checking it reports ALPHA-HOLE-GOAL with the type the position needs and the binders in scope (innermost first, with quantities and types), or ALPHA-HOLE-NEEDS-TYPE where the position has no expected type, so no artifact is ever built with a hole in it. It adds no core constructor. Contract: hole.

Draft alpha-2027 quoted token forms#

The text-literal token "…" denotes validated UTF-8 Text; the byte-string-literal token b"…" denotes exact Bytes. These are atomic tokens, not parenthesized heads, and are unavailable in alpha-2026. Their complete draft contracts are Text and Bytes. Neither extends the core constructors. Whole-source UTF-8 validity and half-open byte spans apply before parsing; human columns count scalars and LSP positions use its negotiated encoding. See the contracts for current qualification limits.

Draft alpha-2027 telescopes, nest, then, pipe and open bodies#

Five spellings parse to terms alpha-2026 already has, so none adds a core or surface constructor. A binder telescope continues a lambda, pi or sigma after its . with QUANTITY NAME : TYPE .: (lambda q x : A . r y : B . body) is (lambda q x : A . (lambda r y : B . body)). (nest HEAD X1 ... Xn Z), n >= 1, is (HEAD X1 (HEAD X2 ... (HEAD Xn Z))), where HEAD is an identifier or a parenthesised prefix spliced before every link. (then L1 ... Ln Z), n >= 1, is (L1 (L2 ... (Ln Z))), where each link is an identifier or a parenthesised prefix spliced into its own form. (pipe X L1 ... Ln), n >= 1, is (Ln ... (L2 (L1 X))) with the term so far as each link's first operand: the term goes right after the link's identifier, so (pipe x (f a) g) is (g (f x a)). Because the parsed terms are the nested ones, the edition gate finds these spellings on the lexemes and refuses them outside alpha-2027 (ALPHA-EDITION-UNSUPPORTED-FORM). Contracts: telescopes, nest, then, pipe, open bodies.

An open-body is a body (after the . of a binder, branch or case, or the in of a let or let*) whose first token is a name followed by more tokens before the enclosing ): it is the form those tokens spell, parenthesised, so (lambda q x : A . f a b) is (lambda q x : A . (f a b)). A body that is one term (Type N included) ends at that term, as in alpha-2026.

3.2 Names in a module#

A name in a module body is resolved in this order; the first rule that applies decides it.

  1. Local binders. A lambda, pi, sigma, let or branch binder shadows every other meaning of its spelling inside its body.
  2. The module's own definitions. A def in the current module shadows any imported definition of the same spelling, including one that would otherwise be ambiguous.
  3. Qualified imports. Module.Path/name names the definition name of a module the current module imports directly. It resolves even when several imported modules define name.
  4. Unqualified imports. A bare name resolves to an imported definition only when exactly one directly imported module defines name. If two or more do, the name is ambiguous and is refused; qualify it.
  5. Families and constructors (draft alpha-2027). A name unbound by the rules above means (family X) for a visible family with no parameters or indices, and (constructor F X) for a constructor with no fields of a visible family with no parameters. A name two of these share is ambiguous and is refused (bare-name contract). Under alpha-2026 the name is unbound.

The atoms zero, Nat, Byte, Bytes and BytesBuilder (§2) are never resolved by these rules: a bare use is always the atom, and a binder or definition with one of those spellings is refused (ALPHA-ELAB-RESERVED-NAME).

Visibility is by direct import only: a definition of a module the current module does not import is unbound, bare or qualified, even when an imported module itself imports it (an imported definition that uses it still works). Matching is by whole name: value never resolves to myvalue, and Missing/value names a module, so it is refused when Missing is not imported. An import must name an earlier module of the closure (ALPHA-MODULE-IMPORT), and a family imported from two modules is ALPHA-MODULE-FAMILY-AMBIGUOUS. Resolution never inserts alias bindings: a name resolved by rule 4 refers to the same global as its qualified form.

The bootstrap and the Alpha-written module checker (ordinary and contextual checking) implement rules 1 to 4 alike; scripts/ci/module-name-resolution.sh holds both to the same 18 cases, emitted bytes and executed results included.

4. Core terms#

The trusted core uses de Bruijn indices and contains exactly these forms:

variable i                 universe l
Nat                        zero
successor n                Fin n
finite-zero n              finite-successor n i
Pi q name A B              lambda q name A body
application f x            Sigma q name A B
pair SigmaType x y         first pair
second pair                equal A x y
reflexive A x              effect-row effects [tail]
transport motive proof x   computation effects A
family F arguments         constructor F C arguments
eliminate F motive branches scrutinee
partial-computation C

Universe levels and variable indices are non-negative. Names are canonical ASCII identifiers. The labels of a written effect row must be in the canonical order of §9 and contain no duplicates (ALPHA-EFFECT-INVALID-ROW otherwise); the optional tail is a term of type (effect-row) (§9).

4.1 Extended core forms (reconciled 2026-09-03, LP-103; recounted 2026-11-06)#

The block above is the generation-zero subset of the trusted core. The normative core is the RawTerm type in bootstrap/haskell/packages/alpha-core/src/Alpha/Core/Trusted/Syntax.hs, which has 80 constructors; every one of the 24 forms listed above has its constructor, and the kernel adds the following 56:

  • Not judged by the kernel: RAnnotated (a term with its source origin; transparent to every judgement, reduction and digest) and RGlobal (a definition named rather than positional, produced and consumed only by the checked-interface codec; every judgement refuses it).
  • Naturals: RNatLiteral, RNatEliminate, RNatLessThan, RNatAdd, RNatMultiply, RNatSubtract, RNatDivide, RNatModulo, RNatToByte.
  • Byte: RByte, RByteLiteral, RByteToNat, RByteEqual, RByteLessThan, RByteAnd, RByteOr, RByteXor, RByteShiftLeft, RByteShiftRight.
  • Binary32: RF32Add, RF32Subtract, RF32Multiply, RF32Divide, RF32SquareRoot, RF32LessThan, RF32Equal.
  • Bytes: RBytes, RBytesLiteral, RBytesCons, RBytesAppend, RBytesEqual, RBytesSetIndex, RBytesSetFreeIndex, RBytesIndexNonzero, RBytesLength, RBytesHead, RBytesTail, RBytesChecksum, RBytesEliminate, RBytesPackbitsDecode.
  • Bytes builder and images: RBytesBuilder, RBytesBuilderEmpty, RBytesBuilderChunk, RBytesBuilderAppend, RBytesBuilderBuild, RRuntimeImageV4Build, RNativePhysicalImageBuild.
  • Prophecy: RProphecy (§9.1).
  • Binding and computation: RLet, REffectRowType, RReturn, RBind, RReadFile, RWriteFile.

Typed holes (§3) have no core constructor.

The authoritative, always-current list is generated at docs/generated/ALPHA-LIVE-FORM-INVENTORY.json (diff.kernel_constructors_beyond_spec_core); a kernel constructor absent from this section is a specification defect, and a section entry absent from the kernel is an unimplemented core form and must carry an explicit status.

5. Universes and dependent types#

Type l : Type (l + 1). Nat : Type 0 and Fin n : Type 0 when n : Nat. The universe of a dependent function or pair is the maximum of its domain and codomain levels. Universes are not cumulative: a type in Type 0 is not also in Type 1.

nat-eliminate motive z s n (with n : Nat) requires motive : Nat -> Type l (checked before the cases), z : motive zero and s : (unrestricted p : Nat) -> (unrestricted ih : motive p) -> motive (succ p) — the step binders are always unrestricted — and has type motive n.

Pi q x : A . B classifies functions whose argument has quantity q. Sigma q x : A . B classifies dependent pairs. Application substitutes the argument into the codomain. The type of second p substitutes first p into the pair codomain.

Equality is intensional in the primitive core. If x : A, then refl A x : equal A x x. Type checking uses definitional equality after normalization; it does not trust surface spelling or pointer identity.

Byte : Type 0 contains exactly the values 0 through 255. Bytes : Type 0 is the finite sequence of bytes. byte-to-nat, byte-equal, and byte-less-than are total; equality and unsigned ordering return the canonical Nat booleans zero and succ zero. nat-to-byte is total by wrapping: the byte of n mod 256. bytes-head and bytes-tail are total by default values: the head of (bytes) is (byte 0) and its tail is (bytes). bytes-eliminate is the dependent, structurally total eliminator for byte sequences. These operations remain in runtime erasure when their operands are not definitionally static.

Type checking normalizes before comparing, and also reduces a type to weak-head form wherever it needs the type's head (for example the function type of an applied term); both evaluators have reduction rules for every byte and bytes operation (the weak-head rules for bytes-set-index, bytes-set-free-index, bytes-index-nonzero and bytes-checksum were added on 2026-11-06; before, a type computed through one of them stayed stuck where its head was needed).

The artifact sealer reduces a closed definition with an explicit nat-add, nat-multiply, nat-subtract, nat-divide, or nat-modulo head before collecting its runtime dependencies. The kernel's normalizer supplies the value; this permits exact arithmetic with large compile-time intermediates when the final constant fits the runtime representation. Runtime Nat values are bounded to an unsigned 64-bit word. A larger literal reaching erasure is rejected as RuntimeNaturalOutOfRange, rather than expanded into successors.

The runtime graph compiler recognizes two complete, closed structural natural folds over byte sequences: repeated bytes-tail, and construction of a prefix builder from successive bytes-head values. Recognition checks the full recurrence and binder indices, independently of names. Their private runtime operations preserve saturated suffixes and zero-padded prefixes; they do not change the source language or kernel reduction rules. Native realizations use bounded byte views and one builder chunk, avoiding a closure per source byte. Other recurrences keep their ordinary lowering.

If p : equal A left right, motive left : Type l, motive right : Type r, and value : motive left, then transport motive p value : motive right. Motive and proof are erased runtime positions. Transport over reflexivity reduces definitionally to value.

6. Quantities#

Quantities are runtime-use contracts:

QuantityRequired runtime use
erasedexactly zero
affinezero or one, never captured
linearexactly one, never captured
unrestrictedany number

Type-only positions do not consume a value. Runtime branches are analyzed as alternatives: their minimum and maximum usage bounds are joined. Capturing an affine or linear value in a nested lambda is rejected.

Uses are scaled by the binder they pass through (as in QTT). The runtime uses of an argument count as often as its parameter's quantity allows, and those of a let value as often as its binder's: through an erased parameter or binder they count zero times; through a linear one, exactly as they occur; through an affine one, at most as they occur and possibly not at all; through an unrestricted one, any number of times, as if captured. Passing a linear variable to an unrestricted parameter is therefore a duplication and passing it to an affine one a possible drop, both ALPHA-QUANTITY-VIOLATION. A non-erased let charges its value's uses even when the body never reaches the binder. A violation states the observed use as "is used N time(s)", "may be used any number of times (captured …)" or "is used between A and B time(s), depending on the path taken".

An elimination (eliminate, nat-eliminate, bytes-eliminate) whose type reduces to an equality or a universe has no runtime value and consumes no runtime uses, its scrutinee included, so induction over an erased value into an equation is allowed. A runtime first of a pair whose sigma binder is erased is refused at check time (ALPHA-QUANTITY-VIOLATION). A non-erased sigma quantity (linear, affine) constrains nothing beyond type identity: it does not limit how often a pair is projected. The binders of a nat-eliminate or bytes-eliminate step are always unrestricted. A constructor's parameters are runtime data unless declared erased.

Constructor recursive fields account for the consumption required by structural recursion. Each retained recursive field reserves one use for recursion, independently of whether its induction hypothesis is demanded; affine and linear fields cannot also be used directly. The resulting hypothesis is unrestricted. An erased recursive field reserves no runtime use and has an erased hypothesis. Both source binders remain available for type checking and erased arguments, but neither may be extracted into runtime data. Runtime laziness and physical slot allocation do not change these source ownership obligations.

For an indexed eliminator, each branch result is specialized before erasure. A proof-valued result contributes no residual branch, although its source branch must still pass coverage and type checking. A retained recursive field always reserves a physical field slot and an IH slot. If that IH's specialized type erases, its slot remains inaccessible and unused; neighboring fields, live hypotheses and outer captures keep their indices. A malformed runtime selection of an omitted branch fails with the missing-branch error.

Quantity checking is part of trusted type checking. A backend is not allowed to weaken it, and a failed quantity proof cannot become a warning.

7. Indexed inductive families#

A family definition contains parameters, indices, a result universe, and an ordered constructor set. A constructor contains ordinary value fields, recursive fields, and result indices. A recursive field is the family being declared, at the family's own parameters and at index arguments of its own; it is the only way a constructor may refer to its family.

The family checker MUST establish:

  1. unique family names, and constructor names unique within their family (two families may declare the same constructor name, since a constructor is always named together with its family);
  2. well-formed parameter, index, value, and recursive telescopes;
  3. constructor result indices with the declared family arity;
  4. positivity, in a form stricter than strict positivity: no value field's type may mention the family being declared anywhere, so even a strictly positive function-typed field such as (pi unrestricted i : Nat . (family Tree)) is refused, and infinitely branching families cannot be declared;
  5. complete, ordered eliminator branches;
  6. exact branch arities (for source, enforced by the elaborator as ALPHA-ELAB-BRANCH-ARITY, with the kernel's ALPHA-TYPE-BRANCH-ARITY as backstop); and
  7. branch result types obtained from the motive.

A family has its declared level whatever its parameters (there is no universe polymorphism), and there are no mutual or nested families.

An eliminator first checks that the scrutinee has the named family, checks every constructor branch, and returns the motive applied to the scrutinee indices and the scrutinee itself. Coverage is by constructor name only: a branch is required for every constructor even when the scrutinee's indices rule it out, branch types are not refined by unifying indices, and there is no absurd elimination.

8. Totality and divergence#

The primitive total fragment has no general fixpoint, exception, foreign call, or bottom constructor. A definition cannot refer to itself or to a later definition, so recursion is expressed only through the eliminators (nat-eliminate, bytes-eliminate, eliminate), whose only recursive calls are the induction hypotheses of recursive fields: structural recursion is total by construction, and needs no separate certificate. A kernel-checked primitive term is total unless it contains partial-computation.

Potential divergence is explicit. (partial C), for a type C, has type C, and is accepted only when C reduces to a computation type whose effect row, normalized, contains Divergence (a Divergence label inside a written tail counts; ALPHA-TOTALITY-EXPECTED-DIVERGENT otherwise). A row variable is not enough: Divergence must be written. Since there is no general fixpoint, partial only names a computation that may diverge; it cannot run one: it erases to an explicit partial node that the runtime graph refuses (PartialRuntimeTerm), so a build whose runtime term still contains it fails.

alpha check and alpha build enforce totality only through these rules: the checker distinguishes a partial definition from a total one only by the Divergence row of the computation it marks, so a definition of type Nat may contain (and discard) a partial computation. Alpha.Core.Totality holds a totality certifier (certifyPrimitiveTotality, which refuses every term containing partial-computation) and a structural-recursion plan check (checkStructuralRecursionPlan: one clause per constructor, no unknown or duplicate clause, calls only on recursive fields). Neither is invoked by the checker or the build; only the alpha-core unit tests call them.

9. Effects#

The effect-label vocabulary is:

State Random Device File Network Divergence

This is also the canonical order: a written row lists its labels in it, without repetition (ALPHA-EFFECT-INVALID-ROW otherwise).

The vocabulary is intentionally small in the bootstrap. Extending it changes the language and trusted checker and therefore requires a versioned specification change, tests, and a bootstrap-identity update.

(effect-row) is the type of effect rows, an ordinary type in Type 0 (not a separate kind). (effects File) is a closed row and (effects File : e) extends the row variable e with File. Row variables are ordinary dependently bound terms whose type is (effect-row). Normalization flattens rows: when the tail of (effects L… : T) normalizes to a row (effects M… [: U]), the result is (effects L∪M… [: U]) with repeated labels removed and the canonical order restored; a row with no labels of its own is its tail, so (effects : e) normalizes to e; over a neutral tail, (effects L… : e) with L non-empty stays open. Consequently functions may quantify over an effect row and preserve or extend it without enumerating the caller's remaining effects. There is no row subsumption or effect subtyping: (effects) is not usable where (effects File) is expected, and every composition must use definitionally the same row. Of the six labels only File (from read-file and write-file) and Divergence (required by partial) have primitives; State, Random, Device and Network can be written in types only.

computation E A is well formed only when E : (effect-row) and A is a type. A term of another type where a row is required (the row of computation, return, bind, prophecy, or a row's tail) is ALPHA-EFFECT-EXPECTED-ROW. Effects are represented in types; no operation may perform an unreported device, file, network, random, state, or divergent interaction. Only (computation (effects File) Nat) and Nat can be the type of a native program's main; other rows check but cannot be built as a program root.

The bootstrap computation terms are:

return E value
bind E result-type first continuation
read-file path
write-file path contents

return E value has type computation E A when value : A. bind requires its first operand to have type computation E A and its continuation to have type A -> computation E B; its result is computation E B. The continuation's codomain cannot depend on the bound value. The continuation binder may use any declared quantity, which the kernel enforces; a continuation whose binder is erased still runs (erasure keeps it a function that ignores the value). Both operands must use definitionally the same effect row, written on the bind, on the first operand's type and on the continuation's codomain. read-file requires a Bytes path and has type computation (effects File) Bytes. write-file requires Bytes path and contents and has type computation (effects File) Nat, where the result is the number of bytes written. A path is never truncated at an embedded NUL byte: the direct (control-flow) lane refuses a NUL in a path it knows at build time (ControlFlowNativePathContainsNul), and on the evaluator lane the program builds and the operation fails at run time (RuntimeMachineFilePathContainsNul in the reference machine; exit 128 measured for a native write-file).

9.1 Prophecies#

RProphecy effects valueType relation body is a computation former. If

E : (effect-row)     A : Type l       A is observable
R : (erased p : A) -> (v : A) -> Type k
body : (erased p : A) -> computation E (sigma v : A . R p v)

then prophecy E A R body : computation E (sigma v : A . R v v). The ghost p is the value the body finally produces; the body is checked parametric in it, and the form instantiates it with that value.

A type is observable when its values are determined by their runtime content: Nat, Byte, Bytes, Fin n, a dependent pair whose first component is retained and both components observable, or an inductive family every one of whose value and recursive fields is retained and of an observable type (parameters instantiated). Every other type — a function, a universe, an equality, an effect row, a computation, a byte builder, a type with an erased field, or one whose head does not reduce — is refused (ProphecyValueUnobservable, ALPHA-PROPHECY-UNOBSERVABLE). The relation is checked against the exact shape above, binder quantities included (ALPHA-PROPHECY-RELATION).

Soundness rests on two premises the kernel checks and that must be preserved: the ghost is erased, so the body cannot read it at run time; and A is observable, so the value one run produces is one logical value whatever the ghost was, and is therefore a fixed point of it. No term of type equal A p v is introduced inside the body; the conventional "learn the ghost after resolution" is expressed by a relation conditioned on equal A p v, discharged by refl at R v v. A prophecy is inert to the normalizer, like every computation; its operational meaning is its erasure (§12.1).

9.2 Native lowering of File computations#

Closed File computations are lowered to project-encoded Linux system calls on two native lanes; they are never interpreted by the bootstrap host, and a computation shape a lane cannot lower is a compiler error.

  • Evaluator lane (Alpha.Compiler.RuntimeNativeEvaluator): read-file opens the path (openat), sizes it with fstat, reads in a loop until that size or end of file, and closes it; write-file writes to a temporary PATH.alpha-tmp in a loop that handles partial writes, fsyncs it, seeks back and reads it to verify the bytes, then renames it onto PATH and fsyncs the directory holding PATH (. for a path without /). A failed system call ends the program with a fixed status (open 129, read 130, write 131, fstat 132, close 133, fsync 145, seek 146, read-back mismatch 147, rename 148, opening, fsyncing or closing the directory 149; a path containing NUL 128).
  • Direct (control-flow) lane (Alpha.Compiler.ControlFlowLowering): read-file reads into a fixed 65,536-byte buffer and fails closed like the evaluator lane: a failed open ends the program with status 129, a failed read 130, and a file longer than the buffer 144 (until 2026-11-06 a failed open or read gave the empty sequence and a longer file was truncated). This lane cannot lower a write to a path computed at run time, nor a bind whose first step writes a file.

As of the initial bootstrap, this section also described a growable mmap/mremap read buffer, a refusal of equal input and output paths, and native lowerings specialized to particular canonical byte folds (a byte filter, a balanced-delimiter scan, adjacent-run compression and a whitespace-normalization fold). None of these is present in the current compiler sources: such folds compile through the general runtime lowering like any other term.

10. Elaboration and diagnostics#

Surface names are elaborated to de Bruijn indices. Elaboration rejects unbound names, duplicate binders where prohibited, invalid universes, and every core construction that the trusted checker rejects. Diagnostics carry:

  1. a stable ASCII code;
  2. the source span;
  3. a human-readable explanation; and
  4. an optional typed proof obligation.

Error recovery may collect independent diagnostics, but it MUST NOT emit an authoritative checked term for an ill-typed subtree.

A diagnostic prints the terms it mentions in source syntax, so they can be pasted back: nullary forms in parentheses ((bytes-builder-empty), (effect-row)), an open row as (effects L… : TAIL), and a local binder by its name in located errors rather than by its de Bruijn position (@N). A reference to a module-level definition may still print positionally.

A module build is an ordered, non-empty sequence of named modules. Imports may resolve only definitions exported by earlier modules in that sequence. The final module must contain exactly one checked main; it alone determines the native program result. Empty builds, unresolved or forward imports, ambiguous names, missing main, and multiple final main definitions are compiler errors. Module composition does not authorize host-language evaluation or a fallback interpreter.

A value definition begins with def <name> [ : <type> ] =. Its body may begin on that line or on a later physical line. Parenthesized terms continue until their delimiter depth returns to zero; an atomic body on the following line is one complete term. Delimiter depth, not indentation or a host-language parser, determines continuation. An unmatched close, end of input with an unfinished body, or a new top-level declaration encountered before closure is a hard module error. The definition source span covers every consumed physical line.

11. Runtime witnesses#

Configuration, target, dataset, and checkpoint facts cross into compiled code only as VerifiedFactPackage values. Each package existentially binds a type-level identity to:

  1. a singleton fact kind;
  2. a canonical non-empty ASCII identity;
  3. a schema version proven to be at least one; and
  4. a non-empty byte payload.

The identity cannot be swapped after verification because the witness, proof, and payload share the same type-level symbol. Runtime facts are evidence, not ambient strings.

12. Target and no-fallback contract#

Target-specific operations require a target witness and must lower to a declared target program. On NVIDIA SM86, the production path is generated machine code submitted through the native runtime. A missing kernel, unsupported shape, failed proof, allocator exhaustion, launch fault, or device mismatch is an error. It is never permission to run a host implementation.

Reference interpreters and scalar models are test or proof oracles only. They must be invoked explicitly, must be labelled as non-production, and cannot be reachable from a production target dispatch.

12.1 Proof erasure artifact#

After kernel checking, eraseChecked lowers a checked term to RuntimeTerm. The runtime data type contains variables, natural constructors and the natural operations, bytes and byte constructors and operations, binary32 operations, byte-builder and image-building nodes, runtime lambdas/applications, retained pair fields, projections, constructors, eliminators, computation return/bind nodes, File read/write nodes, and explicit partial computation (59 constructors of RuntimeTerm in Alpha.Core.Erasure; no let node: a retained let erases to a runtime lambda applied to its value, and a binding nothing at run time reaches erases to nothing). It has no universe, type, equality, reflexivity, motive, effect-row, or proof constructors. Computation effect and result types erase, while effectful operations remain explicit so later stages cannot lose or invent an interaction.

Quantity-zero lambdas and arguments are removed, with one exception: a bind continuation whose binder has no runtime presence is kept a function that ignores its argument, so the continuation still runs. A prophecy erases to the erasure of its body (the ghost binder is quantity zero), so it adds no runtime node and no backend observes it. Equality transport erases to the transported runtime value. Attempting to use an erased de Bruijn slot in a runtime position is a hard ErasedVariableUsedAtRuntime error. Runtime terms have a deterministic length-framed binary encoding; this encoding, not a GHC closure or Show representation, is the artifact presented to later compiler stages.

The bootstrap verifier (bootstrap/verify.sh) rejects Unsafe.Coerce, unsafeCoerce, unsafePerformIO, unsafeDupablePerformIO, and unsafeInterleaveIO in code (outside comments) in the src, tool and app trees of every package in bootstrap/haskell/cabal.project. One reviewed unsafePerformIO use is admitted: a process-global mutable cell (name = unsafePerformIO (newMVar …|newQSem …|newIORef …)) whose line carries -- verify: process-global (<why>) and whose binding is NOINLINE; the verifier prints every admitted cell. Core, proof, and surface packages compile under Safe Haskell with unsafe-module warnings promoted to errors.

13. Bootstrap identity#

The Phase 0 bootstrap is identified by:

  1. this specification;
  2. bootstrap/haskell/cabal.project, and the Cabal package description and the Haskell sources (src, tool, app and test trees) of every package it lists (22 as of 2026-11-06);
  3. bootstrap/toolchain.env and the scripts bootstrap/verify.sh, bootstrap/refresh.sh and bootstrap/prove-native-transport.sh;
  4. GHC 9.10.3 and cabal-install 3.12.1.0 (pinned in bootstrap/toolchain.env); and
  5. an x86_64-linux or aarch64-linux bootstrap host.

The input digests are recorded in bootstrap/bootstrap-manifest.sha256. bootstrap/verify.sh checks that identity without network access. Any byte change to an identified input invalidates the bootstrap manifest and requires a deliberate regeneration (bootstrap/refresh.sh) with new evidence. The PRD named by the identity at the head of this document is not among the hashed inputs (no file in the repository has that digest).

14. Versioning rule#

This document is normative only for the manifest that hashes it. Language extensions require a new manifest. Backward compatibility must be explicit; unknown syntax, effects, proof forms, runtime schemas, and target operations fail closed.