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. ```hint One shape, many cases Treat a type as a tree whose leaves are primitives and type variables; rendering is then a single recursive rule per node kind. ``` #### 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`. ```hint Walk both trees together Traverse each parameter type and its argument type in lockstep, recording what each type variable has to be, and check every later occurrence against what you recorded. ``` #### 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 ### What a Strong Answer Covers - A data model that keeps rendering and inference simple and makes adding a new type kind easy - Exact output format, verified with tests on nested cases - Correct, well-explained inference with clear errors - Awareness of how the problem grows when arguments may themselves be generic ### Follow-up Questions - Argument types may now contain their own type variables. What changes, and what is an occurs check? - Add function types as first-class values, so a parameter can itself be a function. How do rendering and inference change? - How would you parse the string format back into types? - Add subtyping, so an `int` argument is accepted where a `float` is expected. How does inference change?