Feature contract: prophecy#
A prophecy ghost variable names, at the start of a computation, the value that
computation will finally produce. Types and proofs written early may mention
it; at run time it does not exist. Conventionally this is a prophecy
variable (Abadi and Lamport, "The existence of refinement mappings", 1991;
Jung et al., "The Future is Ours: Prophecy Variables in Separation Logic",
POPL 2020). The mechanism, and the kernel's name for it, is erased-parametric
result instantiation (Alpha.Core.Trusted.Prophecy).
1. Lexical and grammar rules, including precedence and termination#
(prophecy EFFECTS (GHOST : TYPE) (RESOLVED . RESULT) BODY) binder spelling
(prophecy EFFECTS TYPE RELATION BODY) core spelling
(resolve GHOST VALUE WITNESS) resolution
prophecy and resolve are form heads (draft edition only). The binder
spelling is recognised by its structural prefix ( IDENT : in the second
operand, which no term begins with; anything else is the four-operand core
spelling. GHOST and RESOLVED must differ (ALPHA-PARSE-PROPHECY). Inside a
do, (resolve GHOST VALUE WITNESS) may replace the final (return VALUE).
2. Scope and binding rules, including generated names#
GHOST is bound in RESULT and in BODY; RESOLVED is bound in RESULT
only. resolve names a ghost: it must be the ghost of an enclosing prophecy
(ALPHA-PROPHECY-RESOLVE-UNBOUND, also when a nearer binder shadows it), and
its position must be that prophecy's result — a nested prophecy's body cannot
silently resolve the outer ghost (ALPHA-PROPHECY-RESOLVE-SCOPE). No
source-visible names are generated.
3. Type and quantity requirements#
The core rule, checked by the trusted kernel:
E : effect-row A : Type l A observable
R : (erased p : A) -> (v : A) -> Type k
body : (erased p : A) -> computation E (sigma v : A . R p v)
---------------------------------------------------------------
(prophecy E A R body) : computation E (sigma v : A . R v v)
The binder spelling elaborates RESULT to R = (lambda erased GHOST : TYPE . (lambda unrestricted RESOLVED : TYPE . RESULT)) and BODY to
(lambda erased GHOST : TYPE . BODY), checked at
computation EFFECTS (sigma unrestricted RESOLVED : TYPE . RESULT).
- The ghost is erased: any runtime use is
ALPHA-QUANTITY-VIOLATION. Amust be observable —Nat,Byte,Bytes,Fin n, a pair whose first component is retained and both components observable, or a family every one of whose fields (value and recursive) is retained and observable (ALPHA-PROPHECY-UNOBSERVABLEotherwise, with the reason).- The relation's shape is exact, binder quantities included
(
ALPHA-PROPHECY-RELATION, orALPHA-TYPE-MISMATCHfor a wrong quantity). - Inside the body the ghost is abstract:
equal A GHOST vis not provable there. The idiom is a relation conditioned on the ghost being right,(pi erased correct : (equal A GHOST RESOLVED) . T), whose witness transportsreflalongcorrectand which the caller discharges withreflatR v v.
Why it is sound, and what must be preserved: a run of the form is a run of
the erasure of body (the ghost has no runtime slot), so one run realizes
sigma v . R p v for every ghost p; because A is observable, the run's
first component determines one logical v independent of p; so p := v is
a fixed point and the run realizes R v v. Both premises are load-bearing
(the kernel mutants in the gate remove each one). There is deliberately no
free-standing resolve : equal A p v: two resolutions would derive
0 = 1, and transport would turn that into runtime type confusion, while
Alpha's quantities belong to binders, so a use-once token cannot be made
affine by its type. Resolving exactly once, at the scope's end, by
construction removes the question.
4. Effects, totality, and evaluation-order rules#
The form adds no effect and no partiality: its row is the body's. Evaluation is the body's evaluation, unchanged. Like every computation the form is inert to the normaliser (no reduction rule): two prophecies are definitionally equal exactly when their four operands are.
5. Elaboration into existing core or a specifically versioned new core extension#
A versioned core extension: one constructor, RProphecy effects valueType relation body (interface tag 79, alpha-checked-interface-v8). The binder
spelling and the core spelling elaborate to identical core (the gate compares
them with alpha inspect diff --core). resolve adds no core form: it is the
pair (pair (sigma ...) VALUE WITNESS), or its return in the expected row —
or, with nothing expected (a bind continuation), in the prophecy's own row.
6. Representation and target support, where relevant#
Erasure of a prophecy is the erasure of its body: no runtime node is added and
no backend sees the form. The gate requires each executed prophecy program's
x86-64 artifact to be byte-identical to its ghost-free twin. The direct lane
(AArch64 hosts) lowers the prophecy at a canonical ghost instance, but does
not yet lower its dependent-pair result — the direct lane has no pairs at all
(issue #79), so a prophecy program builds for x86-64 through the
evaluator lane. The self-hosted front end (packages/compiler/src/Compiler)
parses and serializes the form and refuses to lower it
(literalProphecyLoweringFailureCode, 90) until its core gains dependent
pairs (issue #80).
7. Error codes and primary/secondary origins#
| code | condition |
|---|---|
ALPHA-PARSE-PROPHECY | the ghost and the resolved value share a name (its "unterminated" variants need a token stream without its end marker: in a source file a missing operand or ) is ALPHA-PARSE-UNEXPECTED, an unclosed form the module reader's ALPHA-MODULE-DEFINITION-CONTINUATION) |
ALPHA-PROPHECY-UNOBSERVABLE | the value type is not observable (the reason is stated) |
ALPHA-PROPHECY-RELATION | the relation is not a two-argument type family |
ALPHA-PROPHECY-RESOLVE-UNBOUND | resolve names no prophecy ghost in scope, or one shadowed by a nearer binder |
ALPHA-PROPHECY-RESOLVE-SCOPE | resolve stands where another prophecy's result is expected |
The ghost read at run time is the existing ALPHA-QUANTITY-VIOLATION; a
witness that does not prove the relation is ALPHA-TYPE-MISMATCH; under
alpha-2026 the form is ALPHA-EDITION-UNSUPPORTED-FORM.
8. Formatting and migration rules#
Canonical formatting (alpha fmt) puts each operand on its own line when the
form does not fit on one; the binder groups stay as written. Expanded
inspection prints the core spelling — the relation and the ghost-parametric
body written out, each resolution as its pair — and re-checks it; the gate
requires both to keep the program's core. Nothing is migrated automatically:
no existing program uses a ghost that a later value resolves (the survey is
docs/language/PROPHECY-FUTURE-USES.md).
9. Positive, negative, execution, and edge-case tests#
tests/language/prophecy/ with scripts/ci/prophecy.sh (CI shard 4):
positives (Positives.alpha: nesting, an observable record family, a Fin
ghost, an early step typed by the ghost, the core spelling); two executed
programs and their ghost-free twins (byte-identical artifacts; a read exits
with the fixture's length, a write writes its bytes and exits with their
count); eleven negatives, each with its code; three source mutants; the edition
boundary; the self-hosted front end (SelfHostedProphecyParser.alpha) and the
checkpoint codec round trip, with a codec mutant; the kernel suite
(alpha-core ProphecySuite, nineteen checks) and four kernel mutants
(observability off, a repeated family hiding its fields, ghost not erased,
erasure dropping the body). Nested parameter instantiations must inspect
their leaves: Box (Box A) is not a recursive induction hypothesis. The
kernel regression also rejects the pure computation with impossible
postcondition hidden(v) = successor(hidden(v)) admitted by the old shortcut
(issue #108). tests/language/draft/prophecy/ adds the binder and core
spellings side by side and a relation that is not a two-argument family
(ALPHA-PROPHECY-RELATION); tests/language/draft/resolve/ covers the
resolution positions and refusals.
Not proved: erasure parametricity in general (the premise the rule shares with every erased-argument function) is relied on, not established here.
10. Compatibility with the old edition, serialized forms, and cache keys#
alpha-2026 rejects both heads. Both are reserved heads in every edition, as
do is (SPECIFICATION §2): a function or binder named prophecy or resolve
keeps its name but is applied as (app resolve x); an alpha-2026 source that
wrote (resolve x) for such a call must change to that spelling. The
checked-interface schema is alpha-checked-interface-v8 (a v7 reader would
refuse tag 79, so the version says so first); the self-hosted AST checkpoint
codec gives the prophecy tag 34 and the resolution tag 35, after the equality
forms' 31 to 33. Edition and schema identity prevent
cross-version cache reuse.