Toy Language Types: Render Types and Signatures, Infer Generic Return Types

You are building part of the type checker for a small toy programming language. Its type system has three kinds of types:

• Primitive types, such as int, float, str and bool.
• Generic type variables, written T1, T2 and so on, which stand for any type.
• Tuple types: an ordered list of types, which may be nested, such as a tuple of int and a tuple of T1 and str.

A function signature is a list of parameter types and a return type.

The exact textual format was not reported. For this exercise, assume a primitive or type variable is written as its name; a tuple is written as its element types separated by ", " inside square brackets; and a function is written as its parameter types separated by ", " inside parentheses, followed by " -> " and the return type. For example, a function taking an int and a tuple of T1 and str, and returning T1, is written (int, [T1, str]) -> T1.

Clarifying Questions

• Which primitive types exist, and can new ones be added later?
• Can a function have zero parameters, and can a tuple be empty?
• Can argument types passed to a call themselves contain type variables, or are they always concrete?
• If a type variable appears only in the return type, is that an error, or does the result stay generic?
• Are function types themselves allowed as parameter or return types?
• What should happen on a type mismatch: raise an error, or return a result that describes it?

Part 1 — Represent types and render them as strings

Design classes (or another representation) for the three kinds of types and for function signatures, and implement a to_str method (or __str__) that renders them exactly in the format above, including nested tuples.

What This Part Should Cover

• A clean, extensible representation of the three type kinds and of function signatures
• Recursive rendering that is exactly right for nested tuples and for functions with zero or many parameters
• Structural equality, so two separately built but identical types compare as equal

Part 2 — Infer the return type of a call

Implement infer_return(func, arg_types). Given a function signature that may contain type variables, and the concrete types of the arguments in a call, determine what each type variable must be and return the concrete return type. Raise a clear error when the call is invalid: the wrong number of arguments, a primitive mismatch, a tuple of the wrong shape, or one type variable required to be two different types.

For example, calling (int, [T1, str]) -> T1 with arguments int and [float, str] returns float.

What This Part Should Cover

• Consistent binding of type variables across all parameters, including nested positions
• Every error case detected with a helpful message
• Substitution of the bindings into the return type, including nested and repeated variables
• Complexity in terms of the total size of the types