Type system
This reference specifies the Gale type system precisely; the compiler and its tests take precedence when they disagree. Static compatibility never converts a native value, and a proof is separate from a successful typecheck.
Built in:
| Type | Meaning |
|---|---|
Integer, Float |
Separate numerics; operators never mix them |
Range |
Native integer range struct, with Integer first, last, and step fields |
String |
UTF-8 text (a Binary) |
Binary |
Byte-aligned bits (a Bitstring) |
Bitstring |
Any immutable bit length |
Atom, :ready |
Any atom, or one unquoted Elixir atom |
Boolean |
true | false |
Term |
Any BEAM value; decode or refine before use |
Never |
No possible value |
List<A>, Map<K, V> |
Linked list, dictionary |
{A, B}, {} |
Tuples, empty tuple |
%{name: String} |
Exact record with fixed atom keys |
fn(A) -> B, fn() receives M -> A |
Function value, with optional mailbox |
AnyPid |
Untyped process reference |
Reference |
Raw BEAM reference; no monitor or timer provenance |
ChildSpec<A> |
Opaque native child specification for supervisors |
Nilable<A>, Timeout |
A | nil, Integer | :infinity |
Order |
Less | Equal | Greater |
Option<A> |
Some(A) | None |
Result<A, E> |
Ok(A) | Error(E) |
Pid<M> in the rules below denotes gale_std.process.Pid<M>; unlike
AnyPid, it requires that module qualification or a local type alias. Other
OTP handles likewise come from gale_std, not the builtin type namespace.
Join alternatives with | (:open | :closed). Generic parameters use angle
brackets. nil is the atom :nil; absence is Option, failure is Result.
@ may appear in an unquoted atom after the first character (:foo@bar).
A name cannot start with @. Quoted atoms are unsupported.
Algebraic data types declare a closed set of constructors:
pub type UserId = Integer
pub type Tree<A> = | Leaf | Node(A, Tree<A>, Tree<A>)Fieldless constructors (Leaf) are values; constructors with fields are
constructed directly (Node(1, Leaf, Leaf)). Payload constructors are not
function values: write fn(value) -> Some(value) for a callback. Constructors
are namespaced by their ADT. Named declarations require labels (Cancelled(reason: r))
and defaults (C3(f: T, g: U = default); defaulted fields come last).
Labeled constructor calls can be nested inside other expressions. Constructors
may fix their result instance for reply-indexed protocols:
pub type Request<Reply> = | Count : Request<Integer> | Rename(name: String) : Request<:ok>Matching a Request<R> refines R per branch. Indexed types are invariant;
incompatible constructors are unreachable for a concrete index. Constructor
indices are first-order types (including tuples and injective nominal type
applications), not applications of abstract type constructors. Every field
type parameter must occur as a whole result index. Closed compound indices are
allowed; nonuniform forms such as Pack(A): Family<List<A>> are excluded. The
matched value must have a known type.
Transparent aliases cannot contain recursive alias cycles; ADTs and structs can be recursive. A constructor’s defaults must be trailing and effect-free; they cannot refer to other fields. Omitted defaults are evaluated at the call site after supplied expressions, once in declaration order; explicitly supplied fields skip their defaults. Defaults must terminate. Pattern omission means wildcard and never evaluates a default. Labels do not create ordinary function keyword arguments. The default expression is part of the constructor’s proof interface. Proofs retain its checked computation and obligations; a public function called by that expression still exposes only its own declared contract.
Records are structural and exact: extra fields make a different type:
user = %{name: "Ada", age: 36}older = %{user | age: user.age + 1}name = user.nameAn exact record fits Map<K, V> when its fields fit. Maps with runtime keys
use %{key => value}.
Structs declare an explicit type name and are owned by their module; they emit real Elixir structs:
mod shop.user
struct User { name: String, active: Boolean = true}
pub fn new(name: String) -> User { %User{name: name}}A module can declare at most one struct Name { ... } or exception Name { ... }.
The type name conventionally matches the module’s final segment in UpperPascalCase,
but may differ: mod shop.storage with struct Entry { ... } exports
shop.storage.Entry in Gale and emits %Shop.Storage{...} in Elixir. The
Gale type name never introduces a nested BEAM module. Declarations require a
name; unnamed struct blocks are unsupported. Module-owned structs and exceptions
are public.
A generic struct writes struct Box<A> { value: A } and is used as Box<A>.
Omitted fields use their declared defaults.
Exceptions are named, module-owned structs with native Elixir exception
behaviour. Construction, field access, updates and patterns use the same syntax
as ordinary structs. Creating an exception or returning it inside Error never
raises it or captures a stack trace:
mod shop.errors
exception EncodingError { issues: List<String>}
pub fn message(error: EncodingError) -> String { "Encoding failed"}
pub fn reject(issue: String) -> Result<Integer, EncodingError> { Error(%EncodingError{issues: [issue]})}
pub fn issues(result: Result<Integer, EncodingError>) -> List<String> { case result { Ok(_) -> [] Error(%EncodingError{issues: issues}) -> issues }}This emits Shop.Errors with defexception; reject("invalid") returns
{:error, %Shop.Errors{issues: ["invalid"]}}. Other modules refer to the Gale
type as errors.EncodingError after alias shop.errors.
Exceptions can declare defaults but cannot have type parameters. Provide either
message: String (with an optional default), which generates the native message
callback, or pub fn message(error: EncodingError) -> String. A custom callback
takes precedence over a message field, has no type parameters or mailbox
requirement, and is checked as ordinary Gale code. __struct__ and
__exception__ are compiler-owned fields and cannot be declared or updated.
Exception types remain distinct nominal types in error unions; matching their
structs and fields follows the ordinary exhaustiveness rules. Result accepts
ordinary structs and variants as well as exceptions. Raising remains an explicit
foreign operation; an exception declaration adds no implicit control flow.
Opaque types hide their representation outside the defining module:
pub opaque type AccountId = Integer. Inside its module, functions can use
and construct the representation. Outside, callers must use the public API;
an Integer cannot be passed as an AccountId. An opaque type may declare
an invariant(value) { ... } that verification requires construction and
updates to establish. opaque type Marker without a representation is
uninhabited. Invariants require a representation.
Type system
Section titled “Type system”Inference and annotations. Named functions annotate results and parameters
in an inline definition or one shared signature header; implementation
heads contain patterns. Local bindings and lambdas are inferred or checked
against their expected type. Declare generic parameters explicitly (fn identity<A>(value: A) -> A).
Each call instantiates a named generic function afresh. Local bindings are not
implicitly generalized into generic functions. A type parameter means the
function must work for every permitted instantiation; it is not dynamic Term.
Compatibility. Subtyping passes the same BEAM value without conversion:
| Rule | Consequence |
|---|---|
Never fits every type; every type fits Term |
Never has no values; Term needs narrowing before use |
:ready fits Atom; String <: Binary <: Bitstring |
Subtyping views the same native value |
Integer does not fit Float |
Convert explicitly; arithmetic never widens numbers |
| A member fits its union | Integer fits Integer | :infinity |
| Records require the same field set | A record with extra fields does not fit a smaller record |
| Aliases are transparent; ADTs, structs, opaques, and extern types are nominal | Similar representations do not make distinct declarations interchangeable |
Record fields and tuple components may widen without changing shape. An exact
record also fits Map<K, V> if all its keys and values fit. A struct does not
implicitly become a record; construct the record explicitly.
Generic compatibility (variance). List<A>, Option<A>, and both Result
parameters can widen with their contents (covariance). Map<K, V> requires
the same key type, while values may widen. Function results may widen, but a
replacement function must accept at least the original parameter types
(contravariance). Gale infers variance for transparent data declarations.
Opaque and extern parameters, behaviour arguments, typed PIDs, server handles,
and mailbox types require the same type arguments (invariance). In particular,
Pid<Integer> cannot become Pid<Term>.
Narrowing and coverage. case and receive narrow values with patterns
and guard type tests. is_binary proves Binary, not valid UTF-8 String;
use a decoder for that. Every possible case input must be covered;
selective receive may handle only part of its mailbox. Pins and guards
can fail and generally need fallbacks. Bindings and <- need patterns that
cannot fail. Result<A, Never> needs only an Ok arm.
Unions and representation. A union adds no runtime tag. Gale flattens
unions, removes redundant members, and rejects ambiguous constructor tags.
Use {:value, Integer | String}, not two tuple members sharing the same tag
and arity. Two ADTs with the same lowered constructor tag and arity cannot be
joined into a union. These checks matter because fieldless ADT constructors
emit snake-case atoms and constructors with fields emit tagged tuples:
None is :none, Some(1) is {:some, 1}, and Ok(1) is {:ok, 1}.
Capabilities. mod B<...> exposes a declared behaviour’s callbacks;
a module must implement it to be passed. receives M is a function capability
checked at call sites, not just documentation. Functions without a mailbox
requirement may run in any mailbox context. Indexed constructors such as
Count: Request<Integer> refine the reply type when matched. Behaviour
parameters may abstract over a type constructor (Call: Type -> Type), as
in gale_std.gen_server.Server; this is not unrestricted higher-rank typing.
Kinds and equality. Ordinary parameters have kind Type. A parameter
F: Type -> Type takes one type argument; more arrows set a fixed arity.
For example, type Box<F: Type -> Type, A> = Box(F<A>) accepts List as
F. Generic declarations are rank one: functions cannot take a polymorphic
function parameter. Strict equality compares complete runtime values of related
types, including Term and a single generic parameter. There is no Eq bound
or custom equality implementation; use explicit comparators for ordering.
Inference procedure. Expected types flow into function/lambda bodies,
annotated bindings, call arguments, collection components, and branch results.
A call’s expected result can help instantiate its generic parameters. There
is no explicit call-site type application. The checker collects subtype
bounds from all arguments before choosing an inferred parameter: an
established operand type, a finite union of literals from one scalar family,
or a structural combination through covariant components. Invariant
components must agree; the checker does not invent a mixed-family union,
widen literals to a primitive type, or guess Term to reconcile arguments.
A chosen candidate must satisfy every collected bound. Rigid declared
parameters accept only their own type. Union unification requires equivalent
unions; it does not search their members.
Context resolves empty values first. Infer Never only for justified empty
covariant payload positions. Otherwise unresolved types are inference errors;
they cannot justify unreachable branches or omitted mailbox checks.
Without an expected type, branch and collection types are joined from left
to right: equal types stay equal; an unsolved variable unifies with the other
side; matching type constructors join covariant components and unify invariant
or contravariant components. If the component merge fails, its tentative
solutions are rolled back and a normalized union is attempted. An invalid
union is an error. Written List<A> | List<B> remains distinct from
List<A | B>; joining two inferred lists may produce the latter.
Compatibility with unsolved variables uses the first applicable rule:
- Equal types, source
Never, or targetTermsucceed without solving. - A bare unsolved variable unifies with the other type exactly.
- Matching constructors recurse by variance (invariant positions unify).
- A source union must fit the target member by member.
- For a target union, first accept an already compatible member without solving. Otherwise exactly one member must match the source’s outer type constructor or be a bare variable; check against it. Ambiguity is an error.
- Otherwise apply the closed subtyping rules above.
Annotations resolve ambiguities; the checker does not search for alternative instantiations. Transparent parameters used only positively are covariant; used only negatively, in both, or in neither position they are invariant. Contravariance arises only structurally, in function argument positions. Function subtyping also requires equal arity and compatible mailbox capability: a mailbox-free function fits one requiring a mailbox, but not conversely; two present mailbox types must be identical.
Union normalization flattens nested unions, drops Never, duplicates, and
members already covered by another member (Term covers all). It does not
distribute unions through containers. Besides ADT tag/arity collisions,
ambiguous unions include an ADT and an atom/tuple alternative accepting its
tag, distinct foreign exceptions for the same native module, and an opaque
value overlapping its exposed runtime shape. Structural unions can overlap;
pattern matching narrows all compatible members without inventing nominal
identity. Struct identity and distinct outer tags can distinguish alternatives.
Boundary of the guarantee. Extern signatures are trusted. Decode external
Term values rather than claiming a type through an unchecked extern.
--runtime-typechecks (or the Mix option) adds checks at supported function
boundaries; it does not validate all foreign process messages or prove
contracts. Typing does not establish termination, delivery, liveness, or
absence of native exceptions. Contracts require a separate verification run.
Function identity and inference
Section titled “Function identity and inference”One module/name/arity has one typed interface and contract. A contiguous bodyless header owns visibility, named whole arguments, generics, return type, mailbox and requires/ensures/decreases. Ordered implementation clauses supply patterns/guards/ bodies. The family must cover the declared input domain. An inline typed single body is the concise alternative; different arities are separate functions. Same-arity distinct signatures and anonymous multi-clause functions are excluded.
Explicit named generics instantiate afresh per call; a local reference is monomorphic. Context flows through annotated bindings, expected callback/results and call arguments. There is no explicit call-site type application, higher-rank callback or polymorphic lambda. Expression joins retain heterogeneous values with unions. Generic unification need not discover every common union: supply an annotation when context is needed.
<N: Integer | Float> is a finite-choice constraint: N is exactly one listed closed
concrete type at an instantiation. It cannot be the union itself. All choices must
satisfy the body and proof obligations. This general constraint supports type-preserving
numeric APIs without compiler-recognized function names. It introduces no typeclass
lookup, predicate parameter or arbitrary subtype-constraint solver.
Ordering values of the same parameter is accepted when every choice supports
ordering. Negation preserves a parameter restricted to Integer and Float.
Two independent parameters do not become interchangeable just because their
choice sets coincide.
Closed compound alternatives are retained separately: List<Integer> and
List<String> do not admit List<Integer | String> as their instantiation.
A single alternative fixes the type in the body. Callback implementations may
accept a wider set of choices than the interface, including an unconstrained
parameter; they must accept every interface choice.
Fixed-arity higher kinds (F: Type -> Type, etc.) remain; type-level computation,
abstract higher-kinded indices and general dependent/existential types are excluded.
String <: Binary <: Bitstring preserves native identity. Binary is byte-aligned;
Bitstring admits any bit length. is_bitstring tests the native shape and bit_size
observes bit length. Alignment alone does not establish UTF-8 validity.
Constructor and field rules
Section titled “Constructor and field rules”A named declaration requires named arguments; positional declarations use positions.
For Retry(delay_ms: Integer, attempts: Integer = 3), construct
Retry(delay_ms: 100). Retry(100) is an error. Supplied expressions evaluate once
in written order before slot reordering, followed by omitted defaults in declaration
order. Defaults are pure and cannot reference sibling fields. Pattern omission
is wildcard, not equality to a default. Bare payload constructors are not callbacks;
use fn(value) -> Some(value).
Records are exact atom-keyed maps; subset patterns are native required-key matching.
%{} as a pattern matches a map, not only the empty record. Same-shape records widen
field types; record-to-dictionary compatibility checks every field. No width subtyping,
open rows or dictionary-to-record assignment. Dynamic-map K is invariant and V covariant.
No library put/delete/merge function transforms a record type through special typing.
map.new() is generic in its key domain, supplied by ordinary type context.
For example, empty: Map<Integer, String> = map.new() retains invariant integer
keys. %{} is available when no key domain has been established.
Expected result unions supply context through a unique tuple alternative with the same literal tag and arity. Repeated tags do not choose a specialization; the completed result is checked against the whole expected union.
Direct union updates require the updated fields to have the same declared type in every alternative; otherwise match before updating. Field access requires the field in every union alternative. Existing-field updates preserve each alternative and its correlations: a tag and another variant’s payload cannot be combined. Widening a value then updating it does not mutate a narrower alias. Owned and foreign structs retain their native nominal identity. A raw foreign struct’s field types do not establish semantic validity or an opaque invariant.
Indexed ADTs retain uniform generic and closed indexed payloads. Matching establishes branch-local first-order index equations, shared by related arguments/replies, without leaking them into other branches. Reject nonuniform generic payloads needing existential models, payload parameters absent from indices, arithmetic indices and subjects without a known indexed type. Runtime tags alone cannot certify erased index/payload validity.
Patterns, binding identities and coverage
Section titled “Patterns, binding identities and coverage”Rebinding creates a fresh immutable binding version. Captures, pins, contracts and proof facts refer to their resolved version. Repeated names in a simultaneous pattern compare strictly with its first binding; pins use only the outer environment. Aliases bind the whole subject as well as its components.
Case/cond and valid typed function calls are total over their admitted inputs. Plain bindings/lambda parameters and required successful with payloads must be irrefutable. Use supported structural constructor/nested coverage, with explicit fallbacks for pins, literal-content, prefix and size constraints. A known missing witness differs from conservative inability to establish coverage. Unresolved types cannot justify unreachable arms. Empty case is justified only for an established uninhabited domain.
Native partial guard failure rejects the arm. Guards cannot call arbitrary functions. is_binary gives byte alignment, not UTF-8; is_list on Term does not certify a proper typed list; function arity does not give a signature, mailbox or contract. Preserve only facts actually observed by nominal/type/structural tests.
Receive is partial native selective receive. The mailbox includes standard and custom messages; unhandled messages remain queued. Wildcards consume. after 0 polls; dynamic timeouts need validation/proved domain obligations. The timeout alias alone does not encode the native 0..4,294,967,295 bound. Typed Pid is invariant, erases to AnyPid, and cannot be recovered through a runtime PID-shape test.
Text and bits
Section titled “Text and bits”String <: Binary <: Bitstring, with UTF-8, byte alignment and arbitrary bit length respectively. Subtyping views the same immutable native value. Validation distinguishes UTF-8 from alignment. Byte/string identity is strict, with no Unicode normalization. Native grapheme semantics do not imply additive byte/grapheme equations.
Selected <<…>> syntax constructs fixed literal-width integer segments and complete binary/bitstring payloads. Defaults are unsigned big endian 8 bits; low-bit encoding follows Elixir. Integer widths include zero/nonbyte values. Payload patterns can use constants/previous bindings, byte units for binary and bit units for bitstring; only a trailing payload may omit size. Sole unconstrained remainder patterns are total for their representation. Float/UTF/native endian/custom units/runtime integer widths, computed sizes and sized-payload construction are excluded.
Function interfaces, behaviours and logical use
Section titled “Function interfaces, behaviours and logical use”A named function alias may bind invocation parameters and declare requires/ensures; result scopes over ensures. Compatibility combines argument contravariance/result covariance/mailbox requirements with weaker required domains and stronger guarantees. Erasing a function to a plain fn cannot erase an unmet precondition. Known passed, returned and stored values retain justified interface facts; unknown broad interfaces provide only their declared guarantees.
Proof-only call_requires(callback, arguments...) observes invocation admission;
call_ensures(callback, arguments..., output) observes the normal-return relation.
Arguments are separate and in declared order, including zero-argument callbacks.
The callback must have a statically known mailbox-free function interface, and
each input/output must match its declared type. These Boolean formulas are erased
and rejected in runtime code and guards. They do not invoke callbacks, prove that
a call occurred, or establish termination/purity. Actual invocations publish their
postcondition relation. Checked construction and interface conversions preserve
justified stronger facts, including through returned/stored function values and
argument/result variance. An unconstrained callback gains no exact output.
Captures are immutable; no mutable callback-state model is introduced.
Purity checking follows callback invocation through ordinary source helpers, including recursive helpers. A pure caller must provide pure callbacks wherever the helper invokes them; ordinary callers can still provide effectful callbacks. This conditional purity does not establish termination.
Pure fn callback interfaces and extern pure declarations support deterministic, effect-free, terminating logical calls on their valid domain. Ordinary named Gale helpers establish eligibility through checked bodies/dependencies. Ensures alone is neither purity nor termination. Ordinary recursion may diverge with normal-return contracts; logical/default/lemma recursion needs a proved decreasing measure including mutual cycles. An optional named pure declaration requests the same logical-call capability; effects and termination remain separate checked duties. Public total qualifiers are excluded. Known source helpers require no qualifier for logical use.
Explicit mod capabilities use declares/implements, not global search. Overlapping same-name/arity callbacks are permitted only if one function satisfies each independently. Optional callbacks without a body can be absent and are not abstractly callable. A provided default emits a real function on omission; override/default prove the same contract in the declaration’s lexical scope. Conflicting defaults need an explicit implementation. Native framework fallback is not proof of an exported method.
Trusted typed interfaces
Section titled “Trusted typed interfaces”Extern signatures and contracts are explicit trusted boundaries. Pure extern eligibility is separately declared and reported. Native models require versioned provenance and conformance evidence; a matching name cannot create an axiom. Standard/user libraries share general type and proof facilities. Foreign structs remain their original native values, with direct construction/matching/field operations; functions require separate extern declarations.
Optional runtime typechecks raise on supported representation mismatch: UTF-8, proper lists, exact records, constructor/struct fields and callback arity. They do not prove contracts, hidden invariants, phantoms, typed service identity, termination or mailbox conformance. Mandatory checked native adapters validate their stronger promises in every build. Dynamic/untrusted values use explicit Result-returning decoders instead.
Expected checked failures are values; selected direct native exceptional boundaries remain declared. Never means no inhabitant/no normal return, not a runtime kill. No try/rescue/catch syntax, hot reload/code_change, protocols/macros or ownership system.
Proof validity and scope
Section titled “Proof validity and scope”Contracts typecheck during compile/check; verify must account for every required goal and implementation dependency. Assertions/predicates/lemmas/ghost/forall are pure and well-defined, and erased when runtime checks are disabled; no assume/admit, source exists or SMT triggers. Full success requires complete Valid results under reported assumptions. Unknown/timeouts/unsupported/ incomplete/no-goal outcomes remain distinct. Cached callers never excuse verification of a changed callee; unfolded bodies invalidate dependents.
Integer arithmetic and nonnegative powers/division are exact. Numerical Float proof models are excluded from v1; identity, transport and stable comparison observations remain available without numerical ordering or arithmetic laws. Runtime signed-zero identity must match native strict equality. Collection/bit models preserve native identity/order/alignment; full Unicode/calendar/Decimal/crypto/external-world/liveness models are excluded.
Decoder refinement facts follow ordinary quantified pure callback contracts. They survive value-preserving composition and contracted factories, not forged metadata, arbitrary schema type arguments or property-destroying transforms. Server invariant proofs cover initialization and completed state transitions while the loop may run forever. They establish no survival, delivery, fairness or recovery.