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:
- parse source into a span-carrying surface tree without executing it;
- elaborate names to de Bruijn indices before trusted checking;
- accept a term only when the trusted kernel infers or checks its type;
- enforce runtime quantities in the kernel, not as a lint;
- normalize terms before deciding definitional equality;
- represent effects explicitly in computation types;
- reject unmarked divergence from the total fragment;
- preserve proof and runtime identities through typed witnesses;
- fail closed when a required proof, target, dataset, checkpoint, or device witness is absent; and
- 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, coreRNatEliminate);(nat-less-than a b)(2,RNatLessThan);(nat-to-byte n)(1,RNatToByte; in every edition; the byten mod 256, so 256 wraps to(byte 0), in the normalizer, the weak-head evaluator and the runtime alike). Draft editionalpha-2027only (L9/L10): the compact natural literal, written bare (255,0xff,0b1010) or as(nat-literal N)(coreRNatLiteral, 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, draftalpha-2027only) normalizes its closed operand at elaboration and substitutes the first-order normal form; an operand that refers to a local binder isALPHA-COMPILE-TIME-OPEN, one whose normal form is not first-order data isALPHA-COMPILE-TIME-STUCK, and a natural past 64 bits isALPHA-COMPILE-TIME-RANGE. Draft editionalpha-2027only (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, coreRNatAdd/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 assuccdoes (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(Eaccepted; exponent digits mandatory —1eisALPHA-LITERAL-MISSING-DIGITS;1.is not a decimal) has NO type of its own: at an expected type definitionallyData.Float32Bits.InferenceFloat32(F32) orModel.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.0keeps its sign); finite overflow isALPHA-LITERAL-OUT-OF-RANGE; any other expected type, or none, isALPHA-LITERAL-NEEDS-TYPE. An integer spelling atF32/F64converts the same way. NaN and the infinities are never literals (Std.Floatnames them). - Bytes and byte:
Byte,Bytes(types);(byte n)(coreRByteLiteral), 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-LITERALotherwise);(bytes e…), whose elements are unsigned integer tokens or arbitraryByteterms: all tokens elaborate toRBytesLiteral, otherwise the elements elaborate to abytes-conschain;(byte-to-nat b)(1);(byte-equal a b),(byte-less-than a b)(2); draftalpha-2027only (L21):(byte-and a b),(byte-or a b),(byte-xor a b),(byte-shift-left a n),(byte-shift-right a n)(2, coreRByteAnd/RByteOr/RByteXor/RByteShiftLeft/RByteShiftRight;Byte -> Byte -> Byte, a shift by eight or more yields zero);(bytes-cons b bs)(2, the constructor of theBytesview thatbytes-eliminatetakes 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: exactlycountPackBits commands, a control byteC < 128copying the nextC + 1bytes andC ≥ 128emittingC - 127zeros; 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-2027only, 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 aNatboolean); coreRF32Add…RF32Equal. The operands are of a four-byte record family (one constructor, four unrestrictedBytefields, e.g.Std.FloatF32;ALPHA-TYPE-F32-RECORDotherwise). The normalizer never computes them; only the x86-64 SSE scalar lowering (profilex86-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), withcompiler-native-encodea second spelling of the same form (same surface and core node):T : Type landv : TgiveBytes. The checker never runs the encoder (the node is inert to the normalizer), and the type does not restrictTto 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); draftalpha-2027(do effects result (name <- computation) (computation)... (return value))lowers to nestedRBind/RReturnwith 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, coreRLet). The quantity is mandatory, here and inpi,lambdaandsigma: a binder name directly followed by:or=(the usual omission) isALPHA-PARSE-QUANTITY-MISSING, with a fix-it insertingunrestricted; any other word in the quantity position isALPHA-PARSE-QUANTITY(the retiredrestrictedis offered its replacementaffine). Draftalpha-2027also accepts(let* (quantity name [: annotation] = value)+ in body), which lowers to nestedRLetwithout 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);branchis not a top-level form. Draftalpha-2027additionally 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 existingRConstructorApplicationandREliminatecore 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 existingREliminate; constructor order and hidden arities come from the checked family. The normative contract is matching.caseis structural only within those forms, andihis 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 ghostghost : AinRandbody, andresolvedinR; it elaborates to coreRProphecy(§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 closesghost's prophecy — or itsreturnwhere a computation is expected — and may stand in place of ado'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.
- Local binders. A
lambda,pi,sigma,letor branch binder shadows every other meaning of its spelling inside its body. - The module's own definitions. A
defin the current module shadows any imported definition of the same spelling, including one that would otherwise be ambiguous. - Qualified imports.
Module.Path/namenames the definitionnameof a module the current module imports directly. It resolves even when several imported modules definename. - Unqualified imports. A bare
nameresolves to an imported definition only when exactly one directly imported module definesname. If two or more do, the name is ambiguous and is refused; qualify it. - 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-namecontract). 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) andRGlobal(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:
| Quantity | Required runtime use |
|---|---|
erased | exactly zero |
affine | zero or one, never captured |
linear | exactly one, never captured |
unrestricted | any 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:
- 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);
- well-formed parameter, index, value, and recursive telescopes;
- constructor result indices with the declared family arity;
- 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; - complete, ordered eliminator branches;
- exact branch arities (for source, enforced by the elaborator as
ALPHA-ELAB-BRANCH-ARITY, with the kernel'sALPHA-TYPE-BRANCH-ARITYas backstop); and - 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-fileopens the path (openat), sizes it withfstat, reads in a loop until that size or end of file, and closes it;write-filewrites to a temporaryPATH.alpha-tmpin a loop that handles partial writes,fsyncs it, seeks back and reads it to verify the bytes, then renames it ontoPATHandfsyncs the directory holdingPATH(.for a path without/). A failed system call ends the program with a fixed status (open 129, read 130, write 131,fstat132, close 133,fsync145, 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-filereads 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 abindwhose 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:
- a stable ASCII code;
- the source span;
- a human-readable explanation; and
- 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:
- a singleton fact kind;
- a canonical non-empty ASCII identity;
- a schema version proven to be at least one; and
- 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:
- this specification;
bootstrap/haskell/cabal.project, and the Cabal package description and the Haskell sources (src,tool,appandtesttrees) of every package it lists (22 as of 2026-11-06);bootstrap/toolchain.envand the scriptsbootstrap/verify.sh,bootstrap/refresh.shandbootstrap/prove-native-transport.sh;- GHC
9.10.3and cabal-install3.12.1.0(pinned inbootstrap/toolchain.env); and - an
x86_64-linuxoraarch64-linuxbootstrap 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.