Type descriptions
Why types are passed and inspected as they are, how a match on a Type value is checked, and what it compiles to
A match on a Type(a) inspects the type it stands for, as Inspecting a type
describes. This page gives the design behind type arguments and descriptions, and says how the compiler checks a match
on one and what it compiles to. What is still planned is on
Type members and reflection in Work in progress.
Design
Three problems led here. Code that follows a type’s structure (serialisation, equality, hashing, printing) had to be
written by hand or built into the compiler. A decoder, def deserialise: [Decode(a)] string -> a, mentions its type
only in its output, so the call site had no good way to say which a it wants, as Haskell’s read and Rust’s parse
have none, and where nothing fixed a the user got an ambiguity error that is hard to read. And a constraint over
collections had to carry the element type everywhere, [Iter(c, a)], though it follows from the container. Associated
types (Contexts) answer the last; type arguments answer the other two. Both are
the same thing: a record member whose value is a type.
- A type is passed as an argument,
type aorinto: type, of typeType(a), always written at the call. It is the same idea as Haskell’sProxy a, Scala’sClassTagand Kotlin’sKClass<T>. The named form makes a type parameter the same kind of member as an associated type, gives the argument a name at the call site, and matches the constraint syntax;type ais its positional counterpart. A named type member is passed by name like any named field: lettingdeserialise(text, type Point)skip that rule would make type arguments the one exception to a rule that holds for every call and every record construction, and an author who wants positional calls declarestype a. - Generic code is checked once, not per instantiation. Inspection is type-checked when the generic function is
defined, as all generic code is. Nanyx does not adopt compile-time templates, at least for now: in Zig’s
comptimeand C++ templates, generic code is checked separately for each type it is used at, and errors appear inside library code. - Narrowing on a
Typematch only, not full GADTs, and abuildthe compiler provides for decoding, not rank-2 functions in the language. - A nominal type is read-only to reflection outside its home module: there its description is
#nominal, with its name and module but no structure and nobuild. Its encoding comes from its attached definitions or a context its module provides. - A description contains field and case names and types, the type’s name and module, its type parameters, attributes on fields and doc comments.
- Customising an encoding: a type that provides the library’s context itself wins over walking its description, as an explicit instance wins over synthesis, and attributes on fields cover renames without one.
Typed(a)is synthesised for every type, nominal ones too, so a function given a value of typeaneedn’t also taketype a. It is the implicit counterpart of a type argument, as Haskell’sTypeableis ofProxy, and as Scala’sClassTagis usually an implicit parameter. The walker stays explicit: a record’s fields have types the checker never learns, so there is noTypedinstance for them, onlyf.type, and a library takesTyped(a)in its public function and passes the type explicitly in the code that walks it,def encode: [Typed(a)] a -> Json = { value -> encodeAt(value, typeOf) }. GivingTypedof a nominal type everywhere reveals nothing, since outside its home module its description is#nominal.
Precedents: Jane Street’s typerep for OCaml, GHC’s Type.Reflection, and the “Scrap your boilerplate” approach
(Data). Swift’s Mirror and Go’s reflect have a similar shape but are not typed.
Alternatives considered
- Runtime reflection. C# and Java keep a description of every type at runtime and let any code inspect any value.
In a single WebAssembly module this costs binary size, defeats removal of unused code, and needs a description format
that the runtime and compiler agree on. It would also be an implicit capability, which in Nanyx would have to be a
context;
Typed(a)is that context, resolved at compile time. - Compile-time templates. Zig’s
comptime, C++26 static reflection and D’s templates allow arbitrary code over types at compile time. They are very expressive, but generic code is only checked when it is instantiated, which conflicts with checking generic code once. This could be revisited as a later extension if typed descriptions prove too limited. - Type-level induction over structure. The compiler could expose a record as a type-level list of field names and
types, and libraries would handle the “no fields” and “one field, then the rest” cases with contexts whose instances
the compiler chains together. This is how PureScript’s
RowToList(used bysimple-json), GHC Generics, Scala 3 Mirrors and shapeless work, and it suits Nanyx’s row-like records. It needs instances for type constructors that themselves require contexts, and field names as type-level strings. Users would program at the type level, and errors would come from failed instance searches, which these libraries are known for. - Deriving clauses and macros. Haskell’s
deriving, Rust’s#[derive]and procedural macros, and OCaml’s ppx all generate code from a type’s definition. Nanyx has no compiler plugins that extend the language, which rules out procedural macros and ppx. A built-in set of derivations would not let libraries add their own, such as JSON or SQL mapping. - Structural context synthesis. Context synthesis works by name: the compiler builds
Add(Point)fromPoint’s attached definitions. Only the well-known contexts,Eq,Ord,HashandToString, are also derived from structure, so thatEqof a record is built from theEqof its fields. Opening that to any context would need no new syntax, but it cannot express library-specific behaviour such as JSON field names. - Source generators. C#‘s source generators run user code at compile time that emits more source. The linter infrastructure could host them, since linters will run Nanyx code at compile time. Generated code would have to exist before type checking, while linters run after it, so generators would need their own phase and a narrower view of the program. They remain an option for cases that type arguments cannot reach.
Checking
InferMatch.inferMatch hands a match whose one value is a Type(a) to TypeMatches.infer. The tags a description has, and
the built-in description types (RecordInfo(a), UnionInfo(a), NominalInfo, Field(a), Case(a), SomeType)
with their members, are in TypeValues, which the backend reads too.
- Narrowing. Where
ais a type variable, or a type the checker never learns, an arm whose tag says what it is is checked withawritten as that (TypeMatches.narrowEnv) in the types of the names in scope (only names whose schemes have free variables,TypeEnv.Unquantified, can hold it) and in the type the match is expected to give. A lambda’s declared result reaches a match that ends its body (TypeMatches.expectResult), and a def’s block result reaches one that ends the block (ExpectedBlockResults). Each arm’s body is checked against that narrowed result withVisibility.addDeclaredConstraintAt. Narrowing is not unification: the constraints stay global, and only the arm’s view of the names in scope changes. - Packaged types. A field, a case, a type argument and a collection’s element each have a type the checker never
learns, a skolem (
TypeDescriptions.skolem): aTyApplywith no arguments whose name,b#12, no other type has, so it unifies only with itself. Diagnostics write itb. Reading a member of a field opens it once per name (InferState.OpenedPackages, by the name’s symbol), sof.get(value)andf.typeagree. A value of one can’t leave the lambda that opened it (TypeDescriptions.escapingParameters, checked inInfer.inferLambdaAfterTypeOfs) or the arm whose tag made it (TypeDescriptions.escaping), NYX0274. - Recursion. A walker calls itself at a part’s type, so a def whose annotation is complete sees itself, while its
body is checked, generic in the variables it writes (
InferModule, where it bindsenvWithRec). - For the backend, each arm that narrows
arecords the type it narrows it to at its pattern’s node, inExprTypes, which an importing module’sInlinedExprTypeskeeps with the nodes of the definitions it inlines.
Compiling
A Type value is a number at run time, an IrInt: the number of the type it stands for in the module
(CoreIrTypeIds). type X is that number as a constant, and each type gets one when it is first met. The module’s
__describe function, lowered after every other function (CoreIrLowerModule), builds the description of the type of
each number: a tag of TypeValues.descriptionUnion, with a record’s RecordInfo and its fields, each field’s type as
a number in turn, so __describe goes on until every type numbered has one. The module holds descriptions of the
types its Type values name and of the types of their parts, and of no others.
A type is numbered as seen from the file of the type X that names it (CoreIrTypeIds), and a description’s parts
are seen from there too: a nominal type seen from outside its home module (ModuleOrigins.sourceFileName of its home is
not the file) is described as #nominal. So a function specialised at a nominal type can’t pick its arm at compile
time: it keeps every arm that could match, its structure’s and #nominal’s, and matches on __describe. A
description’s name and parameters come from the alias or nominal type, its doc and its fields’ attributes
from the type’s definition (TypeDefInfo.Doc, filled from the module’s doc comments by Compiler.withDocs, and
TypeDefInfo.FieldAttributes, read by TypeResolution.fieldAttributeArguments), which the backend has as
LowerInput.TypeDefinitions.
FunctionLowering.Match hands a match on a Type to CoreIrLowerTypeMatch.lower:
- A known type. In a function specialised at a type it knows, the match picks its arm at compile time. An arm that
narrows
amatches if what it narrows it to fits the type, and what that finds of its skolems, the element type of a#list(elem)arm, is bound from there on (CoreIrLowerTypes.substitutemaps a skolem by its number). An arm that reads nothing of the description is lowered alone; one that does matches on what__describegives. - A type only known when the program runs. A skolem left unbound is
boxedTy, so a function called at a field’s type, as a walker is, is specialised once with that type’s values boxed (IrBox, as a context member’s own type variables are, see Context calls). Its match matches on__describeof the number it is given. In an arm that narrowsa, a boxed name is unboxed where it is used (FunctionLowering.Identifier), and the arm’s value is boxed back to the match’s type (FunctionLowering.Branch), both throughCoreIrLowerBoxes.convert. - Canonical boxes. For that to work whatever the value is, a boxed value of a collection holds its elements boxed:
a list, a set or an array of boxes, and a map whose entries are tuples of boxes. A record or a union is boxed as it
is, since only its description’s
gets read it. A field’sget(fieldGettingFunction) and a case’sget(caseGettingFunction) are closures over functions of their own that unbox the value, read the part, and box it in this form, through a function per collection type (canonicalisingFunction).
Building
A record description’s build has a type of its own each time it is read (TypeDescriptions.memberType): it is
given a function from a field opened at a skolem made for this build, Field(a, b), to #some(b) or a failure, and
gives #some(a) or that failure. Since the function is checked with b a type of its own, it gives a value of any
field’s type: the rank-2 type users never write. A case’s build, from its packaged type to a, is an ordinary member.
CoreIrLowerBuild runs them. A record’s description holds, besides the members a program reads, __make
(CoreIrLowerTypes.makeMember): a closure that makes a value of the record from its fields’ values, boxed in their
canonical form, in the order the description has its fields, unboxing each with the inverse of canonical boxing
(decanonical). r.build (FunctionLowering.Complex, on a member access of build on a RecordInfo) is a closure
over the description and a function of its own, specialised by the IR type of build at the use, which calls the
function it is given with each field (buildingFieldsFunction), gathers the boxes, and makes the record with
__make, or gives the first failure, made again as a value of the result’s union. A case’s build unboxes the payload
and makes the tag.