02 — The Type ADT

The type representation is the data model for the entire type checker. It must be:

• Recursive: function types contain other types.
• Comparable: unify and equality checks must work.
• Printable: error messages need "expected Num, got Bool".

The Type representation

struct NumType  {};
struct BoolType {};
struct StrType  {};
struct NilType  {};
struct AnyType  {};

struct FnType {
    std::vector<std::shared_ptr<Type>> params;
    std::shared_ptr<Type>              ret;
};

using Type = std::variant<NumType, BoolType, StrType, NilType, AnyType, FnType>;
using TypePtr = std::shared_ptr<Type>;

Alternatively, use an inheritance hierarchy with a TypeKind enum. The variant approach avoids virtual dispatch and is exhaustively checkable with std::visit:

std::string typeToStr(const Type& t) {
    return std::visit(overloaded{
        [](const NumType&)  { return std::string("Num"); },
        [](const BoolType&) { return std::string("Bool"); },
        [](const StrType&)  { return std::string("Str"); },
        [](const NilType&)  { return std::string("Nil"); },
        [](const AnyType&)  { return std::string("Any"); },
        [](const FnType& f) {
            std::string s = "Fn(";
            for (size_t i=0; i<f.params.size(); ++i) {
                if (i) s += ", ";
                s += typeToStr(*f.params[i]);
            }
            s += ") -> " + typeToStr(*f.ret);
            return s;
        },
    }, t);
}

Type equality

Two types are equal if they are structurally identical:

bool typeEq(const Type& a, const Type& b) {
    if (a.index() != b.index()) return false;
    if (auto* f = std::get_if<FnType>(&a)) {
        auto& g = std::get<FnType>(b);
        if (f->params.size() != g.params.size()) return false;
        for (size_t i = 0; i < f->params.size(); ++i)
            if (!typeEq(*f->params[i], *g.params[i])) return false;
        return typeEq(*f->ret, *g.ret);
    }
    return true;  // same variant index, non-FnType
}

The "gradual" compatibility check

For gradual typing (step 06), we need compatible(a, b) which is weaker than typeEq: Any is compatible with everything.

bool compatible(const Type& a, const Type& b) {
    if (std::holds_alternative<AnyType>(a)) return true;
    if (std::holds_alternative<AnyType>(b)) return true;
    return typeEq(a, b);
}

Type factory helpers

TypePtr mkNum()  { return std::make_shared<Type>(NumType{}); }
TypePtr mkBool() { return std::make_shared<Type>(BoolType{}); }
TypePtr mkStr()  { return std::make_shared<Type>(StrType{}); }
TypePtr mkNil()  { return std::make_shared<Type>(NilType{}); }
TypePtr mkAny()  { return std::make_shared<Type>(AnyType{}); }
TypePtr mkFn(std::vector<TypePtr> params, TypePtr ret) {
    return std::make_shared<Type>(FnType{std::move(params), std::move(ret)});
}

These reduce noise in the checker: mkNum() is clearer than std::make_shared<Type>(NumType{}) at every call site.

Why shared_ptr?

Function types contain nested types. A type like Fn(Fn(Num)->Bool, Str) -> Nil has a FnType whose first param is another FnType. Shared ownership means the inner types can be cheaply aliased across multiple places in the checker's environment without copying.

For the curriculum, shared_ptr is clear and correct. Production type checkers use arenas (bump allocators) so all types live in one allocation region and are freed together at compile-time end.