Subtyping: when one type can stand in for another

Write a piece of logic once and have it work for many types, and you write less code and break less of it when the types change. What makes that safe is subtyping: the rules that say when a value of one type may stand where another is wanted. Cone uses it everywhere, for numbers, enums, references, functions and traits alike. This page covers why a substitution is safe, the two ways Cone makes one, and the rules for each kind of type. Afterwards you can tell whether one type may stand in for another, and what the swap costs.

mod standins;

import stdio use *;

enum Shape {
  struct Circle { pub r i32; }
  struct Square { pub s i32; }
}

struct Counter {
  pub n u32;
}

fn size(s &Shape) i32 {
  match s {
    case let c Circle { c.r; }
    case let q Square { q.s; }
  }
}

fn total(n u32) u32 { n + 1000u32; }

fn peek(c &Counter) u32 { c.n; }

fn main() {
  let small = 7u8;
  print <- total(small), "\n";       // a u8 where a u32 is wanted
  let c = Shape.Circle(5);
  print <- size(&c), "\n";           // a Circle where a Shape is wanted
  var k = new Counter(3u32);
  let m &mut Counter = &mut k;
  m.n += 1u32;
  print <- peek(m), "\n";            // a &mut where a read-only & is wanted
}

It prints:

1007
5
4

Try this: make c a var variable, and change size to take s &mut Shape and the call to pass &mut c. The compiler now refuses it. References, below, says why.

Supertypes and subtypes: one part for another#

A light socket takes any bulb of the right fitting. To make such a swap safe in code, the component states an interface, and a candidate must meet all of it to play the part. The interface is the supertype, and each type that meets it a subtype: a value of the subtype may stand wherever the supertype is wanted. That buys versatility, since behaviour is varied by handing in a different part; maintainability, since a part can be upgraded without touching what uses it; and reuse, since new parts are easier to write against a known interface. It also adds coupling, since every part now depends on the interface, and a change to the interface ripples out to all of them.

Every place Cone lets a value of one type stand where another is wanted is a subtype relation: a u8 where a u32 is wanted, an enum's variant where the enum is, a &mut reference where a read-only one is, a function that asks less of its argument than a signature offers, a struct where a trait it meets is wanted. All of them answer to one test, which explains why each is safe, and why some swaps that look harmless are refused. Cone has subtyping at every layer:

• For a type, the interface is a trait, and a struct meets it by having its members. An enum is the closed form: its variants are the subtypes, all declared in one place, and a value of any of them is a value of the enum. A set of variants that other modules may add to is an open trait.
• For a function, the interface is its signature. A function reference takes any function of the signature, and a closure reference any closure, or any struct with a () method, of it.
• For a module, the interface is a module trait, settled when the program is compiled.
• For an actor, the interface would be an actor trait, which is not built yet.

Generics and coercion: two ways to substitute#

Code written for a supertype receives a subtype's value in one of two ways, and Cone uses both.

A generic makes a copy for each subtype. A generic function constrained by a trait (Generics) is compiled again for each type it is given, with that type in place of its parameter; making the copies is called monomorphization. The substitution is settled while the program is compiled, every call in a copy is direct, and each copy is exact for its type. The cost is code: one version for each type handed in.

A coercion makes one copy serve every subtype. The value is changed into the supertype's form as it arrives, so a single version of the code handles them all. A coercion is one of two kinds:

• A recast changes only the type. The value's bits already mean the same as a value of the supertype, so nothing runs: a &mut Point used as a read-only &Point, or an enum's variant used as the enum, whose every value takes the same room (Enums).
• A conversion runs code that makes the supertype's value: a u8 widened into a u32 gains three bytes of zeros, and a &Circle given where a &<Shape is wanted gains a pointer to the table of methods Circle brings with it (How a virtual reference works).

mod strategies;

import stdio use *;

trait Shape {
  pub fn area(self &) f32;
}

struct Square {
  pub side f32;
  pub fn area(self &) f32 { side * side; }
}

struct Circle {
  pub r f32;
  pub fn area(self &) f32 { 3.14159 * r * r; }
}

// Generic: a copy of twice is compiled for each type it is given
fn twice[S Shape](s &S) f32 { s.area() * 2.; }

// Coerced: one copy of half, and each reference is converted as it arrives
fn half(s &<Shape) f32 { s.area() / 2.; }

fn tenfold(n u32) u32 { n * 10u32; }

fn main() {
  let sq = new Square(3.);
  let ci = new Circle(1.);
  print <- twice(&sq), " ", twice(&ci), "\n";
  print <- half(&sq), " ", half(&ci), "\n";
  print <- tenfold(7u8), "\n";      // a u8 converted to a u32
}

It prints:

18 6.28318
4.5 1.5708
70

The compiled program holds two versions of twice, one calling Square's area directly and one calling Circle's, and one version of half, which looks up each call's area in the table its virtual reference carries. Neither is the better strategy. A generic is the faster and the more flexible; coercion keeps the program smaller, and it is the only choice when which type will arrive is known only while the program runs (Virtual references).

A conversion has limits a recast does not. To convert a value, the supertype's value must be built, and that is not always practical: a value with more fields than its supertype would need room the supertype does not have, and copying a large value field by field, recursively, is work no one asked for. So Cone never converts the value of a struct, an array or a tuple into another type: an Array[u8, 4] is not coerced into an Array[u16, 4], nor a (u8, u8) into a (u16, u16) (each is refused, 1013). It coerces references to them instead. A reference is small and of one size, so converting it is cheap however large or varied its value is, and the value itself stays where it is, untouched. A virtual reference is exactly that.

The way back needs a check. A coercion goes from subtype to supertype, which is called upcasting, and when the subtype rules hold it is always safe, so Cone does it implicitly wherever the supertype is wanted. The other way, downcasting, is not: the supertype has values that are no value of a particular subtype. Recovering the subtype needs a guard, a pattern that checks which it is, and a match that succeeds guarantees a valid value of the subtype. That is possible only where the supertype's value records which subtype it came from: an enum's tag (narrowing to a variant) or a virtual reference's table (getting the concrete type back).

Judging a subtype: values, operations and predicates#

What makes it safe to hand in a value of one type where another is wanted? The standard is behavioural: whatever can be proven of every value of the supertype must hold of every value of the subtype, so that code written for the supertype cannot be surprised by a subtype's value. What can be proven of a type comes in three kinds, and each gives a rule.

Values. Every value of the subtype must map to exactly one value of the supertype with the same meaning. Every u8, 0 to 255, is a u16, 0 to 65,535, so by values u8 is a subtype of u16, written u8 <: u16. Not the other way round: 1000 is no u8. And often neither way: an i8 may be -10, which no u8 is, and a u8 may be 200, which no i8 is. So two types may be the same, either may be a subtype of the other, or they may not compare at all. Cone coerces a number only into a wider type of the same kind: unsigned into unsigned, signed into signed, float into float. A u8 fits an i16 by value, yet is not coerced into one (1013); convert it, i16.from(b) (Conversion).

Operations. Every operation on the supertype must work on the subtype too, and give an equivalent result: 3 plus 6 is 9 as u8s and as u16s. Nearly always:

let a = 250u8;
let b = 10u8;
let wide u16 = a + b;          // added as u8s, then widened
let wider = 250u16 + b;        // widened, then added
print <- wide, " ", wider, "\n";   // 4 260

The sum of two u8s wraps past 255 before it is widened. So u8 is nearly, but not strictly, a subtype of u16: the substitution holds while nothing overflows. In Cone a type's operations are its methods, declared as part of the type, which lets the compiler check a subtype against a supertype by comparing their methods, name by name and signature by signature (Variance, below, says how two signatures compare).

Predicates. A predicate is a statement that must hold of a type's values or operations: only the even numbers from 0 to 255 (a refinement), the first of a pair never greater than the second (an invariant), a square root that requires a number that is not negative and returns one (a precondition and a postcondition). A subtype must keep every invariant of its supertype, may not require more of its callers, and may not promise less. Predicates can make a type harder to check than a compiler, or a person, can manage, so Cone keeps them few. A data invariant is not part of any type: there are no refinement types. Not built yet: preconditions and postconditions on a function, the requires and ensures contract conditions. An invariant a type keeps for itself, through the logic of its methods, is protected by making private the fields it governs: structural matching does not count a private field, so no trait reaches it, and only the type's own methods can change it.

Privacy is module-wide, so a private member counts towards a trait only for code inside the type's own module. There the type meets the trait with its private members, as its own methods see them. Elsewhere it does not: a virtual reference, a plain &Trait, a generic's bound or a where that would reach a private field or method through the trait is refused (1505), naming the member. A generic's bound is judged from the module the generic is written in, since its body is the code that will use the member, wherever it is instantiated. The type's own module may still make the virtual reference and hand it out, and a type that declares the trait with is has asserted the fit itself, so it meets the trait everywhere.

Structs and traits: concrete and abstract types#

The same rules extend to a struct. Every field of the supertype must be in the subtype, with the same type or a subtype of it (called depth subtyping, since it reaches into the fields), and every method of the supertype must be in the subtype, with a signature that matches. A subtype with more fields than its supertype, though (width subtyping), raises a problem: its extra fields hold values the supertype has no room for, so a value of the subtype has no equal value in the supertype.

Cone resolves it by telling concrete types from abstract ones. A struct is concrete: a set of values, each laid out completely. A trait is abstract: no value is ever of a trait's type (Traits); it is a set of criteria a concrete type must meet, at least these fields and at least these methods. So a struct with more fields and methods than a trait asks for still meets it, and width subtyping holds only against a trait. Between two structs it never holds, and no coercion does either, even when their fields are the same:

struct A { pub x i32; }
struct B { pub x i32; }

fn readB(b &B) i32 { b.x; }

let a = new A(3);
readB(&a);              // ERROR
let b B = a;            // ERROR

Error 1013: Expression's type does not match declared parameter
Error 1013: Initialization value's type does not match variable's declared type

Depth subtyping applies where a struct meets a trait's field: a field item Shape.Circle meets a trait's item Shape, since the variant is a recast of the enum. A field that would need converting does not: n u8 does not meet a trait's n u16 (1013), since a reference through the trait reads the field where it lies.

That holds only where the trait is read. A virtual reference that may write, &<mut, &<uni or Uni[Trait], may store any Shape in the field, a Square among them, where the struct holds only a Circle. So a mutable reference's invariance (below) applies: to be reached by a virtual reference that may write, each of the trait's fields must be declared at exactly the trait's type (1504). A read-only &< still accepts the narrower field, since reading a Circle as a Shape is safe.

A struct is a subtype of the traits it meets, and of nothing else. Reusing another struct's code is a separate question, answered by name folding, and it grants no subtyping: a type that takes in another's fields and methods meets that type's values and operations, yet may break the invariants that type's methods keep, which is the predicate rule.

A struct meets a trait structurally: having the trait's members is enough, whether or not the struct names the trait (Meeting a trait). That matters because a trait may be written after, and apart from, the types that meet it, including a library's types you did not write. A struct may also declare that it meets a trait, with is, and the compiler checks the claim there and then.

Named types and structural types. A struct or an enum is nominal: it is identified by its name, so two structs with the same fields are two types, as A and B above. Most other types are structural, identified by what they are made of: a tuple type such as (i32, i32), an array type such as Array[u8, 3], a reference type or a function signature, written in two places, is the same type in both. A signature's parameter names are no part of it: a &fn(x i32) i32 takes a function declared fn twice(k i32) i32. A trait sits between the two: it has a name, and a struct meets it by its structure.

An abstract type is reached only through a reference. Every value is of a concrete type, since only a concrete type says how much room a value takes. A trait's subtypes may differ in size, so no variable, parameter or field holds a trait by value:

fn byValue(s Shape) f32 { s.area(); }    // ERROR

Error 1069: Variable s cannot be held by value: Shape is a trait whose implementations may differ in size. Use a
virtual reference, '&<Trait>'.

A virtual reference holds one instead. An enum declared @unsized, whose variants are not padded to one size, is likewise reached only through a reference (An enum reached only by reference).

Enums: closed supertypes of their variants#

An enum is a supertype of its variants by design: a value of any variant is a value of the enum, and a method the enum declares without a body is one every variant answers. The set is closed, written in one place, and every value of the enum takes the room of its largest variant, so a variant's value becomes the enum's by a recast: nothing is converted, and the tag the value carries says which variant it holds, which is what lets a match recover it. A set of variants that other modules may add to cannot promise one size, so it is an open trait, whose variants are structs reached through references, as any struct that meets a trait is. Enums: a closed set of subtypes, on the Traits page, has the details.

Not built yet: a plain value where an Option or a Result is wanted, an i32 given as an Option[i32], which the value rule allows (1013 today). Write Some(5) or Ok(5). The i32 is smaller than the Option[i32], so this one would be a conversion.

Variance: functions and references#

A type built from other types, a function's signature from its parameters and result, a reference from the type it points at, is a subtype of another such type depending on how its parts are. Its variance says how. Covariant keeps the direction, as a field does in depth subtyping. Contravariant reverses it. Invariant allows only the same type. Information flow is a good guide: a subtype's value may flow into a place meant for the supertype, never the reverse.

Functions. Arguments flow into a function, and its result flows out. So a function may stand for a signature when each parameter accepts at least what the signature passes (contravariant) and its result gives at least what the signature promises (covariant):

struct P { pub x i32; }

fn readOnly(p &P) i32 { p.x; }            // asks less than the signature offers
fn same(p &mut P) &mut P { p; }         // gives more than the signature promises

fn apply(f &fn(p &mut P) i32, p &mut P) i32 { f(p); }
fn reader(f &fn(p &mut P) &P, p &mut P) i32 { f(p).x; }

var pt = new P(3);
apply(&readOnly, &mut pt);    // 3
reader(&same, &mut pt);       // 3

The reverse is refused: a function taking p &mut P, given where the signature lends p &P, would change what the caller lent only to be read (1013). A function reference points at one compiled function, so only a recast can apply to its parameters and result, and a call through the type must pass and return the very same bytes. A function taking a u32 is not given where &fn(n u8) is wanted, since each u8 would need converting before the call (1013), and no value is made an Option on the way either. Nor is a function taking an enum by value given where the signature passes one of its variants, or the reverse: the two are the same size but are passed and returned as different aggregates (1506 one way; the other way is refused as a signature that does not match). A reference to either is one address, so a function taking a &Shape is given where &fn(s &Shape.Circle) i32 is wanted. Where a conversion is meant, write a wrapper function that does it, and take a reference to that. A function whose result holds fewer borrows than the signature allows is accepted too: one returning only its first parameter's borrow is an &fn(a &i64, b &i64) &i64, since a call through the type is checked against the more it allows. A method meeting a trait may take a weaker self than the trait declares (Working with virtual references).

The same rule decides whether a type's method meets a trait's: its parameters after self may ask less than the trait's, and its result may give more. That holds wherever a type meets a trait: a generic constraint, a virtual reference, a Uni[Trait], an is test, an extends, and a callable's (). Only a recast counts here too, in the direction variance allows: a parameter taking a reference to the enum where the trait's takes one to a variant, or a result giving a reference to a variant where the trait's gives one to the enum, meets it; the other way round is refused (1186). A wider number, a value made an Option, and a variant or an enum held by value for the other are conversions, so they do not; nor does anything behind a &mut that differs at all, since it is read and written. Where a name declares a method of exactly the required signature, that one meets the requirement.

A &<fn made from a plain function, and a module meeting a module trait, follow the same rule, and so do new Uni[fn(..)](&f) and a generic's fn(..) condition: there is one rule for every place a function or method meets a signature, and each refuses a parameter or result held by value that is not one layout with the same error (1506) and the same advice.

References. Whether the type a reference points at may vary depends on the reference's permission. A reference that may only read is covariant: a &Circle, to an enum's variant, may be read as a &Shape. A reference that may read and write is invariant: through a &mut Shape, code may store any shape, so a &mut Circle may not be given as one, or a Square could be stored where a Circle must be:

enum Shape {
  struct Circle { pub r i32; }
  struct Square { pub s i32; }
}

fn size(s &Shape) i32 {
  match s {
    case let c Circle { c.r; }
    case let q Square { q.s; }
  }
}

fn reshape(s &mut Shape) {
  *s = Shape.Square(1);
}

var c = Shape.Circle(5);
size(&c);             // 5: read-only, so covariant
reshape(&mut c);      // ERROR: mutable, so invariant

Error 1013: Expression's type does not match declared parameter

An &imm Circle is accepted as an &imm Shape, and an &uni Circle refused as an &uni Shape, by the same rule. A permission that could write without reading would be contravariant; none of the static permissions does. The same reasoning governs how long the borrows behind a mutable reference may live: a call handed a mutable borrow that could store another holds both to the shorter lifetime (A mutable borrow that could store another).

Not built yet: variance for a generic type's parameters. Today two instances of a generic type are related only when their type arguments are the same: a &Holder[&mut P] is not given where a &Holder[&P] is wanted (1013). Whether a generic's type parameters will need marks saying their variance, or whether it can be worked out from where each is used and the permissions of the references that use it, is undecided.

References: region, permission and lifetime#

Beyond the type it points at, a reference has three parts that subtype, each by its own rule:

• Region. A borrowed reference is a supertype of every owning reference to the same type: a Uni[P] or an Rc[mut, P] given where a &P is wanted is lent (Borrowed references). That is the payoff of borrowing: code that takes a borrowed reference works the same whichever region the value lives in. The lending is a recast, since an owning reference already points at its value; what it starts is the borrowing rules on the owner. Through a lock permission the borrow is never implicit: it takes the lock while the program runs, so it is written out, &*p or &mut *p (Borrowing takes the lock).
• Permission. ro, read-only, is a supertype of every permission that may read, and opaq of every permission. uni, the only reference to its value, is a subtype of mut, mut1, imm and ro. Each is a recast, since a permission lives only in the type (Changing a reference's permission).
• Lifetime. A borrow that lives longer is a subtype of one that lives shorter, within whose scope it lies. A global's borrow stands in where a local's is wanted:

let limit = 10i32;                   // a global

fn larger(a &'a i32, b &'a i32) &'a i32 { if *a > *b { a; } else { b; } }

let near = 5i32;
let r = larger(&limit, &near);     // *r is 10: 'a is near's scope, which limit's outlasts

Each reference coercion is a recast or a conversion: making a virtual reference attaches a table of methods, and making a slice from a reference to an array, &Array[u8, 4] to &Array[u8], attaches its count, while a change of region, permission or lifetime runs nothing. Coercion: the substitutions subtyping allows lists every coercion Cone makes by itself, each with its kind.

You can now tell whether one type may stand in for another, why the compiler refuses the swaps it refuses, and whether a substitution costs a copy of the code, a conversion or nothing at all. Next, the abstract types most substitutions are made against: traits, and the virtual references that carry them.