Implement toy-language types and generic substitution

Problem: Toy Language Type System (Printing + Generic Resolution)

You are implementing a small type system for a custom “Toy Language”. Types can be:

• Primitive types: lowercase strings like int , float , str , bool
• Generic type variables: uppercase letter(s) followed by digits, e.g., T1 , T2
• Tuples: bracketed, comma-separated types, which may be nested, e.g. [int,[T1,str]]
• Function signatures: a list of parameter types and a single return type, written as (param1,param2,...) -> returnType

Data structures

Implement the following classes.

Node

Represents a type node.

• Construction:
  • If node_type is a string , the node is a leaf representing either a primitive type or a generic.
  • If node_type is a list of Node , the node is a tuple whose children are those nodes.

class Node:
    def __init__(self, node_type):
        ...

    def to_str(self) -> str:
        ...

Node.to_str() formatting rules

• Leaf: return the exact string name, e.g. "int" , "T1" .
• Tuple: return bracketed, comma-separated children with no spaces , e.g. [int,T1] , [int,[T1,str]] .

Function

Represents a function signature.

class Function:
    def __init__(self, parameters: list[Node], output_type: Node):
        ...

    def to_str(self) -> str:
        ...

Function.to_str() formatting rules

• Format: (param1,param2,...) -> returnType using each node’s to_str() .
• Example: (int,T1) -> [T1,str]

Part 2: Infer concrete return type

Implement:

def get_return_type(parameters: list[Node], function: Function) -> Node:
    ...

Given:

• function.parameters : the expected parameter type patterns (may include generics and nested tuples)
• parameters : the actual argument types supplied at a call site

Return a new Node representing the concrete return type after substituting generics.

Requirements

1. Argument count check
   • Raise an error if len(parameters) != len(function.parameters) .
2. Build a substitution table (generic resolution)
   • Compare each expected parameter pattern against the corresponding actual argument type.
   • If the expected node is a generic (e.g., T1 ), bind it to the actual type node.
   • If the expected node is a primitive , it must match the actual primitive exactly.
   • If the expected node is a tuple , the actual must also be a tuple of the same arity, and you must recurse.
3. Conflict detection
   • If a generic like T1 is bound more than once in the same call, all bindings must be structurally identical.
   • Otherwise raise an error (e.g., T1 cannot be both int and str ).
4. Return type substitution
   • After building the mapping, recursively replace all generics appearing in function.output_type with their bound concrete types.
   • If a generic appears in the output type but was never bound by the inputs, raise an error (or clearly document and implement a consistent behavior).

Examples

1. Basic substitution
   • Function: [T1, T2, int, T1] -> [T1, T2]
   • Arguments: [int, str, int, int]
   • Mapping: T1 = int , T2 = str
   • Result: [int, str]
2. Nested tuples & complex generics
   • Function: [[T1, float], T2, T3] -> [T3, T1]
   • Arguments: [[str, float], [int, str], int]
   • Mapping: T1 = str , T2 = [int, str] , T3 = int
   • Result: [int, str]
3. Conflict error
   • Function: [T1, T1] -> T1
   • Arguments: [int, str]
   • Error: T1 cannot be both int and str

Implement the above behavior with clear recursive logic and appropriate error handling.