03. Type System & Typing Rules Deep Dive

1. The Architecture of Go's Type System (types2 & go/types)

In the Go compiler, the type system is isolated into a dedicated package: cmd/compile/internal/types2 (with an identical public twin in the standard library: go/types).

Instead of treating types as strings or ad-hoc enums, Go models every type as an object implementing the polymorphic Type interface (src/cmd/compile/internal/types2/type.go):

1type Type interface {
2	// Underlying returns the underlying type of a type.
3	// Underlying types are never Named, TypeParam, or Alias types.
4	Underlying() Type
5 
6	// String returns a string representation of a type.
7	String() string
8}

The 14 Fundamental Concrete Types

Each kind of type lives in its own dedicated source file under types2/:

1types2/
2├── basic.go        # Basic: int, float64, bool, string, untyped constants
3├── pointer.go      # Pointer: *T (base type)
4├── array.go        # Array: [N]T (fixed length + element type)
5├── slice.go        # Slice: []T (dynamic view over an array)
6├── map.go          # Map: map[K]V (hash table key and value types)
7├── chan.go         # Chan: chan T, <-chan T, chan<- T (channel and direction)
8├── struct.go       # Struct: fields ([]*Var), tags ([]string)
9├── interface.go    # Interface: explicit methods ([]*Func), embedded types ([]Type)
10├── signature.go    # Signature: parameters, return results, receiver, variadic flag
11├── named.go        # Named: defined type (type X Y) with its own identity and methods
12├── alias.go        # Alias: type alias (type X = Y) pointing directly to existing type
13├── typeparam.go    # TypeParam: generic type parameter constrained by an interface
14├── union.go        # Union: type set terms (T | ~T) inside generic constraints
15└── tuple.go        # Tuple: ordered list of variables (multi-return values)

Kyna Implementation Map

The same one-type-per-file architecture is now represented in compiler/kyna_types without changing Kyna's existing surface syntax:

Kyna additionally retains NullableType because non-nullability and T? are established Kyna language rules rather than Go rules. This layer is the semantic foundation; source syntax, lowering, bytecode, and runtime support must still be added deliberately for constructs that are not already part of the implemented language.

2. Defined Types vs. Type Aliases

Go maintains a critical distinction between Defined Types and Type Aliases:

1// 1. DEFINED TYPE (Nominal Identity)
2type UserID int64
3 
4// 2. TYPE ALIAS (Structural Synonym)
5type StringList = []string

Semantic Differences

3. Structural Interfaces vs. Nominal Structs

Go combines nominal defined types with structural interfaces:

1classDiagram
2    class Reader {
3        <<interface>>
4        +Read(p []byte) (int, error)
5    }
6    class File {
7        -fd int
8        +Read(p []byte) (int, error)
9        +Write(p []byte) (int, error)
10    }
11    class NetworkStream {
12        -conn Socket
13        +Read(p []byte) (int, error)
14        +Close() error
15    }
16    Reader <|.. File : Implicit Satisfaction (No 'implements' keyword)
17    Reader <|.. NetworkStream : Implicit Satisfaction (No 'implements' keyword)

Why Structural Interfaces Scale

In traditional languages (Java, C#, early Kyna), a class must explicitly state implements Reader. This creates coupling at definition time:

• If a third-party library exposes a Buffer struct with a Read([]byte) method, but didn't import your Reader interface, you cannot use their buffer where your interface is expected.
• In Go, File and NetworkStream implement Reader automatically simply because they have a matching Read(p []byte) (n int, err error) method. The producer does not need to know about the consumer.

Method Sets & Pointer Receivers in Interface Satisfaction

A type T's method set determines which interfaces it satisfies:

• For a value of type T: The method set contains all methods declared with receiver (t T).
• For a pointer of type *T: The method set contains all methods declared with receiver (t *T) AND (t T).

1type Closer interface {
2	Close() error
3}
4 
5type Socket struct{}
6func (s *Socket) Close() error { return nil }
7 
8var s Socket
9var c Closer = s  // COMPILE ERROR: Socket does not implement Closer (Close has pointer receiver)
10var c Closer = &s // COMPILES: *Socket implements Closer

4. The Assignability Algorithm (AssignableTo)

When the compiler checks x = y or funcCall(arg), it calls assignableTo (src/cmd/compile/internal/types2/operand.go):

1func (x *operand) assignableTo(check *Checker, T Type, cause *string) (bool, Code)

The 6 Rules of Assignability

1. Exact Identity: Identical(V, T) is true. (e.g. assigning int to int).
2. Untyped Constants: x is an untyped constant and its numerical value is representable by target type T.
   go

   goCopy

   1var f float64 = 42 // Untyped integer literal 42 implicitly converts to float64 42.0

3. Underlying Type Equivalence for Unnamed Types: Vu == Tu (identical underlying types), and at least one of V or T is an unnamed type literal:
   go

   goCopy

   1type Point struct { X, Y int }
   2var p Point = struct{ X, Y int }{ 1, 2 } // Allowed: struct literal is unnamed

4. Interface Implementation: T is an interface and V implements T (all methods of T are present in V's method set with identical parameter and return types).
5. Channel Direction Subtyping: V is a bidirectional channel chan T, and T is a directional channel <-chan T or chan<- T with identical element types.
6. Generic Constraint Satisfaction: T is a type parameter and V satisfies each specific type in T's type set.

5. Declaration Checking & Cycle Detection (Tri-Color Algorithm)

In src/cmd/compile/internal/types2/decl.go, Go must type-check declarations that may appear in arbitrary order across multiple files in a package:

1type A struct { b *B }
2type B struct { a *A }

The Tri-Color Stack Algorithm

Go tracks the checking state of every declaration using three colors:

1[WHITE] (Unvisited)
2   │
3   ▼
4[GREY]  (Checking in Progress — Pushed onto Checker.objPath stack)
5   │
6   ▼
7[BLACK] (Checking Complete — Type resolved and verified)

1. Every top-level symbol starts WHITE.
2. When the checker begins analyzing symbol X, it marks X GREY and pushes X onto Checker.objPath.
3. If during checking X, the checker encounters another symbol Y:
   • If Y is BLACK: its type is already known. Use it immediately.
   • If Y is WHITE: recursively call objDecl(Y).
   • If Y is GREY: A cycle is detected!
4. If a cycle is detected:
   • If the cycle passes through an indirection (e.g. pointer *B, slice []B, map map[string]B, interface), it is valid recursion.
   • If the cycle is direct (e.g. struct embedding: type Node struct { next Node }), the compiler halts with a clear diagnostic:
     Instructions

     Plain textCopy

     1invalid recursive type Node: Node refers to itself

5. Once X's type is fully resolved, it is popped from the stack and marked BLACK.

6. Comparison: Kyna's Current Type System vs. Go

Kyna's Current TypeRef Model (compiler/kyna_types)

In Kyna, types are currently represented by a lightweight struct in compiler/kyna_types/include/kyna/semantics/type_model.hpp:

1struct TypeRef {
2  std::string name{"void"};
3  bool nullable{false};
4  std::vector<TypeRef> typeArgs;
5  std::vector<TypeRef> unionTypes;
6  std::string str() const;
7};

Limitations of Kyna's String-Based Model

1. No Distinction Between Defined and Underlying Types: Kyna checks types primarily by string comparisons (name == "int"). It cannot determine if a user-defined type has an underlying struct or primitive.
2. Fragile Structural Conformance: Interface matching requires ad-hoc string comparisons against method signatures rather than comparing method sets and signatures as first-class objects.
3. No Direct Cycle Detection: Without a tri-color traversal stack, complex recursive type definitions risk stack overflows or incomplete resolution.

7. Blueprint: Upgrading Kyna's Type System to Match Go

To make Kyna's compiler scalable and robust, we will replace the flat TypeRef struct with a polymorphic C++ type graph:

1namespace kyna::semantics {
2 
3class Type {
4public:
5    virtual ~Type() = default;
6    virtual const Type* underlying() const = 0;
7    virtual std::string str() const = 0;
8    virtual bool is_identical(const Type* other) const = 0;
9};
10 
11class BasicType : public Type {
12public:
13    enum Kind { Int, Float, Bool, Str, Void, Any };
14    BasicType(Kind k) : kind_(k) {}
15    const Type* underlying() const override { return this; }
16    // ...
17private:
18    Kind kind_;
19};
20 
21class StructType : public Type {
22public:
23    struct Field {
24        std::string name;
25        std::shared_ptr<Type> type;
26        bool exported;
27    };
28    const Type* underlying() const override { return this; }
29    const std::vector<Field>& fields() const { return fields_; }
30private:
31    std::vector<Field> fields_;
32};
33 
34class InterfaceType : public Type {
35public:
36    struct Method {
37        std::string name;
38        std::shared_ptr<SignatureType> signature;
39    };
40    const Type* underlying() const override { return this; }
41    const std::vector<Method>& methods() const { return methods_; }
42private:
43    std::vector<Method> methods_;
44};
45 
46class NamedType : public Type {
47public:
48    NamedType(std::string name, std::shared_ptr<Type> underlying)
49        : name_(std::move(name)), underlying_(std::move(underlying)) {}
50    const Type* underlying() const override { return underlying_->underlying(); }
51    const std::string& name() const { return name_; }
52private:
53    std::string name_;
54    std::shared_ptr<Type> underlying_;
55};
56 
57} // namespace kyna::semantics

This ensures that type comparisons are $O(1)$ pointer/underlying checks rather than costly string parsing.