Skip to content

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.name

An 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.

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:

  1. Equal types, source Never, or target Term succeed without solving.
  2. A bare unsolved variable unifies with the other type exactly.
  3. Matching constructors recurse by variance (invariant positions unify).
  4. A source union must fit the target member by member.
  5. 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.
  6. 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.

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.

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.

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.

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.

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.

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.