05 — Function Types and Call Checking

Function types form the most complex part of the type system: they are recursive (parameters and return types can themselves be function types), and call-site checking must verify arity and argument types.

Checking a call expression

TypePtr TypeChecker::visitCall(CallExpr& call) {
    TypePtr calleeType = check(*call.callee);

    // If the callee is Any, we can't check — return Any
    if (std::holds_alternative<AnyType>(*calleeType)) {
        for (auto& arg : call.args) check(*arg);  // still check arg types
        return mkAny();
    }

    // Must be a function type
    auto* fn = std::get_if<FnType>(calleeType.get());
    if (!fn)
        throw TypeCheckError("[line " + std::to_string(call.line) +
            "] Cannot call non-function value of type " +
            typeToStr(*calleeType) + ".");

    // Check arity
    if (call.args.size() != fn->params.size())
        throw TypeCheckError("[line " + std::to_string(call.line) +
            "] Expected " + std::to_string(fn->params.size()) +
            " arguments, got " + std::to_string(call.args.size()) + ".");

    // Check argument types
    for (size_t i = 0; i < call.args.size(); ++i) {
        TypePtr argType = check(*call.args[i]);
        checkCompatible(fn->params[i], argType, call.line);
    }

    return fn->ret;
}

Higher-order functions

Function types compose naturally:

fn apply(f: Fn(Num)->Num, x: Num): Num {
    return f(x);
}
fn double(n: Num): Num { return n * 2; }
print apply(double, 21);  // 42

Type checking apply(double, 21):

1. apply has type Fn(Fn(Num)->Num, Num) -> Num.
2. Arg 0: double has type Fn(Num)->Num. Compatible with param 0 (Fn(Num)->Num). ✓
3. Arg 1: 21 has type Num. Compatible with param 1 (Num). ✓
4. Return type: Num.

Recursive functions

fn fib(n: Num): Num {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

When visitFn resolves the body, fib is already declared in the enclosing scope with type Fn(Num)->Num (set when the let fib = fn(n:Num):Num {...} desugaring runs visitLet). So the recursive call fib(n-1) finds the correct function type in the scope.

The key ordering: visitLet calls declare after type-checking the initialiser for forward-referenced functions? No — declare must happen before checking the body for recursion to work. Here's the fix:

void TypeChecker::visitLet(LetStmt& s) {
    // For function literals, pre-declare with the annotated type
    // before checking the body (enables recursion).
    if (auto* fn = dynamic_cast<FnExpr*>(s.init.get())) {
        if (fn->retAnnotation) {
            auto preType = buildFnType(*fn);  // params + ret from annotations
            declare(s.name, preType);         // pre-declare
            check(*s.init);                   // body can now see s.name
            return;
        }
    }
    // Non-function or unannotated: infer normally
    TypePtr initType = s.init ? check(*s.init) : mkNil();
    if (s.annotation) checkCompatible(s.annotation, initType, s.line);
    declare(s.name, s.annotation ? s.annotation : initType);
}

The interaction with Any

let f: Any = fn(x: Num): Num { return x + 1; };
f(42);   // accepted — callee is Any, no type checking on call
f("hi"); // accepted — but will crash at runtime

The Any escape hatch means the checker accepts the call (returns Any) while the interpreter's runtime check catches the actual type mismatch. This is the defining property of gradual typing: you can opt specific sites out of static checking at the cost of runtime safety guarantees.

Testing function types

void test_function_types() {
    // Correct types — should type-check clean
    CHECK_NOTHROW(typeCheck(R"(
        fn add(a: Num, b: Num): Num { return a + b; }
        print add(1, 2);
    )"));

    // Wrong arg type
    CHECK_THROWS(typeCheck("fn f(x: Num): Num { return x; } f(\"hi\");"),
        "Expected Num");

    // Wrong arity
    CHECK_THROWS(typeCheck("fn f(x: Num): Num { return x; } f(1, 2);"),
        "Expected 1 arguments");
}