92. Design Type System for a Toy Programming language

Design Type System for a Toy Programming language
Design and implement a type system for a toy programming language that supports primitives, tuples, and generics. Your task is to represent types and infer return types for function calls.

All types are represented as canonical strings so that the API stays compact and uses simple method signatures.

The system should allow:
  • Registering primitive types such as int, string, or bool.
    Primitive type names must start with a lowercase character [a-z] and may contain only [a-zA-Z0-9].
  • Registering generic type constructors such as Box<T> or Pair<T,U>.
    Generic type constructor names must start with an uppercase character [A-Z] and may contain only [a-zA-Z0-9].
  • Registering function signatures that may use primitive types, tuple types, generic type constructors, and generic type variables.
  • Inferring the concrete return type of a function call from the provided argument types.

Identifier Rules

  • A primitive type name must start with [a-z] and may contain only [a-zA-Z0-9].
  • A generic type constructor name must start with [A-Z] and may contain only [a-zA-Z0-9].
  • A generic type variable name must start with [A-Z] and may contain only [a-zA-Z0-9].
  • A function name must start with a lowercase character [a-z] and may contain only [a-zA-Z0-9].

Type Representation Rules

  • A primitive type is written as a single identifier, for example int or string.
  • A lowercase identifier used as a type expression is treated as a primitive type and must already be registered.
  • A tuple type is written as (type1,type2,...), for example (int,string).
  • A tuple type must contain at least 2 elements.
  • A generic type instance is written as Name<arg1,arg2,...>, for example Box<int> or Pair<int,string>.
  • A generic type variable inside a function signature is written as a single identifier such as T, U, or Result.
  • Inside a function signature, an uppercase identifier used by itself is always treated as a type variable.
  • Inside a function signature, an uppercase identifier followed by <...> is treated as a generic type constructor usage.
  • A registered generic type constructor may appear only as Name<...> with exactly its declared arity; a bare uppercase identifier is never treated as a concrete generic type.
  • Nested types are allowed, for example Box<Pair<int,string>> or (Box<int>,(string,bool)).
    At max. 5 levels of nesting is allowed.
  • Type strings are canonical and must not contain spaces or any extra characters.
  • Every type expression must be fully balanced and syntactically valid; empty identifiers, empty tuple slots, trailing commas, and empty generic argument lists are invalid.

Type Inference Rules

  • Functions are uniquely identified by functionName only.
  • Method overloading is not allowed, so the same function name cannot be registered more than once even if parameter counts or parameter types differ.
  • During inference, the call must use the exact registered function name and the provided argument count must equal the registered parameter count.
  • Primitive types match only the same primitive type.
  • Tuple types match structurally and element-by-element.
  • Generic type constructors must match by name and arity, and their inner type arguments must also match recursively.
  • A generic type variable must bind consistently everywhere it appears in the same function signature.
  • Bindings are inferred only from the declared parameter types and the concrete argument types, never from the declared return type alone.
  • If the call cannot be matched or inferred, return ERROR.

Required Class

class ToyTypeSystem

Method Signatures

1) Register a primitive type

boolean addPrimitiveType(String primitiveType)
  • Registers a primitive type such as int or bool.
  • Returns true if the primitive type is added successfully.
  • Returns false if the primitive type already exists or the name is invalid.

2) Register a generic type constructor

boolean addGenericType(String genericTypeName, int arity)
  • Registers a generic type constructor such as Box with arity 1 or Pair with arity 2.
  • The constructor itself is only a template; concrete uses appear as strings such as Box<int>.
  • Returns true if the generic type constructor is added successfully.
  • Returns false if the constructor already exists, the name is invalid, or arity <= 0.

3) Register a function signature

boolean addFunction(String functionName, List<String> parameterTypes, String returnType)
  • parameterTypes contains the function parameter type expressions in order.
  • returnType is the declared return type expression.
  • The function name must be valid according to the identifier rules.
  • Any lowercase identifier used in a type expression is treated as a primitive type and must already be registered.
  • Any generic type constructor used in a type expression must already be registered and must be used with its exact declared arity.
  • The signature may use registered primitives, registered generic type constructors, tuple types, and generic type variables.
  • Generic type variables do not need separate registration and are local to that one function signature.
  • A type variable is considered introduced only by appearing somewhere in parameterTypes.
  • If a type variable appears only in returnType, the signature is invalid because its concrete type can never be inferred from a call.
  • Unused type variables in the parameter list are allowed.
  • A zero-parameter function is allowed, but its return type must be fully concrete and must not contain any type variable.
  • Returns true if the function signature is valid and added successfully.
  • Returns false if the function name already exists, if the function name is invalid, if any type expression is invalid, or if the signature uses an unknown primitive or unknown generic type constructor.

4) Infer the return type of a function call

String inferReturnType(String functionName, List<String> argumentTypes)
  • argumentTypes contains the concrete argument type expressions for one function call.
  • Each argument type must itself be a valid concrete type expression.
  • Argument types must not contain generic type variables.
  • Every primitive or generic type constructor used in argumentTypes must already be registered.
  • The method should infer bindings for generic type variables by matching the argument types against the registered parameter types.
  • If inference succeeds, return the fully resolved concrete return type.
  • If the function does not exist, the argument count is wrong, any argument type is invalid, any argument type uses an unknown primitive or unknown generic type constructor, the argument types do not match, or generic bindings are inconsistent, return ERROR.

Constraints

  • 1 ≤ primitiveType.length() ≤ 10
  • 1 ≤ genericTypeName.length() ≤ 10
  • 1 ≤ functionName.length() ≤ 15
  • 1 ≤ arity ≤ 10
  • 0 ≤ parameterTypes.size() ≤ 10
  • 0 ≤ argumentTypes.size() ≤ 10
  • 1 ≤ each type expression length ≤ 200
  • Type expressions use only valid identifiers, commas, parentheses, and angle brackets.
  • Tuple types must contain at least 2 elements.
  • The total number of registered types and functions can be assumed to be at most 10^4.
  • All operations should be designed to run efficiently for repeated registrations and inference queries.

Clarifications

  • Tuple types are structural and do not need separate registration.
  • Generic type variables are local to a function signature.
  • A type variable may appear multiple times in the parameter list and return type.
  • Repeated occurrences of the same type variable in the parameter list must bind to the same concrete type.
  • If a function has no generic variables, inference reduces to direct type validation and exact matching.
  • The returned type string should also be in canonical form without spaces.
  • A bare uppercase identifier in a function signature is a type variable even if a generic type constructor with the same name has been registered.
  • Argument types are always concrete; they can use tuples and registered generic instances, but they cannot use type variables.

Examples

Example 1

  • ToyTypeSystem()
  • addPrimitiveType(primitiveType = "int") → true
  • addPrimitiveType(primitiveType = "string") → true
  • addPrimitiveType(primitiveType = "bool") → true
  • addGenericType(genericTypeName = "Box", arity = 1) → true
  • addGenericType(genericTypeName = "Pair", arity = 2) → true
  • addFunction(functionName = "identity", parameterTypes = List.of("T"), returnType = "T") → true
  • addFunction(functionName = "wrap", parameterTypes = List.of("T"), returnType = "Box<T>") → true
  • addFunction(functionName = "unwrap", parameterTypes = List.of("Box<T>"), returnType = "T") → true
  • addFunction(functionName = "makePair", parameterTypes = List.of("T", "U"), returnType = "Pair<T,U>") → true
  • inferReturnType(functionName = "identity", argumentTypes = List.of("int")) → "int"
  • inferReturnType(functionName = "wrap", argumentTypes = List.of("string")) → "Box<string>"
  • inferReturnType(functionName = "unwrap", argumentTypes = List.of("Box<int>")) → "int"
  • inferReturnType(functionName = "makePair", argumentTypes = List.of("int", "bool")) → "Pair<int,bool>"

Explanation

  • identity uses the local type variable T; passing int binds T = int, so the return type is int.
  • wrap binds T = string and substitutes that binding into Box<T>, producing Box<string>.
  • unwrap matches Box<T> against Box<int>, so T = int and the return type is int.
  • makePair binds T = int and U = bool, so the return type becomes Pair<int,bool>.

Example 2

  • ToyTypeSystem()
  • addPrimitiveType(primitiveType = "int") → true
  • addPrimitiveType(primitiveType = "string") → true
  • addPrimitiveType(primitiveType = "bool") → true
  • addGenericType(genericTypeName = "Box", arity = 1) → true
  • addGenericType(genericTypeName = "Pair", arity = 2) → true
  • addFunction(functionName = "swapTuple", parameterTypes = List.of("(T,U)"), returnType = "(U,T)") → true
  • addFunction(functionName = "first", parameterTypes = List.of("Pair<T,U>"), returnType = "T") → true
  • addFunction(functionName = "sameTypeOnly", parameterTypes = List.of("T", "T"), returnType = "T") → true
  • inferReturnType(functionName = "swapTuple", argumentTypes = List.of("(int,string)")) → "(string,int)"
  • inferReturnType(functionName = "first", argumentTypes = List.of("Pair<Box<int>,string>")) → "Box<int>"
  • inferReturnType(functionName = "sameTypeOnly", argumentTypes = List.of("int", "int")) → "int"
  • inferReturnType(functionName = "sameTypeOnly", argumentTypes = List.of("int", "string")) → "ERROR"
  • inferReturnType(functionName = "first", argumentTypes = List.of("Box<int>")) → "ERROR"

Explanation

  • swapTuple matches tuple elements positionally, so T = int and U = string; substituting into (U,T) gives (string,int).
  • first matches Pair<T,U> with the concrete argument type Pair<Box<int>,string>, so T = Box<int> and the return type is Box<int>.
  • sameTypeOnly requires both parameters to bind to the same concrete type for T.
  • sameTypeOnly(int, string) returns ERROR because the two occurrences of T would require inconsistent bindings.
  • first(Box<int>) returns ERROR because the registered parameter type expects outer constructor Pair, not Box.

Example 3

  • ToyTypeSystem()
  • addPrimitiveType(primitiveType = "int") → true
  • addPrimitiveType(primitiveType = "string") → true
  • addGenericType(genericTypeName = "Box", arity = 1) → true
  • addFunction(functionName = "makeInt", parameterTypes = List.of(), returnType = "int") → true
  • addFunction(functionName = "echo", parameterTypes = List.of("T"), returnType = "T") → true
  • addFunction(functionName = "badFactory", parameterTypes = List.of(), returnType = "T") → false
  • addFunction(functionName = "1badName", parameterTypes = List.of("int"), returnType = "int") → false
  • addFunction(functionName = "badUnknownPrimitive", parameterTypes = List.of("float"), returnType = "float") → false
  • addFunction(functionName = "badUnknownGeneric", parameterTypes = List.of("Wrap<int>"), returnType = "int") → false
  • addFunction(functionName = "makeInt", parameterTypes = List.of("string"), returnType = "string") → false
  • inferReturnType(functionName = "makeInt", argumentTypes = List.of()) → "int"
  • inferReturnType(functionName = "makeInt", argumentTypes = List.of("int")) → "ERROR"
  • inferReturnType(functionName = "echo", argumentTypes = List.of("Box<int>")) → "Box<int>"
  • inferReturnType(functionName = "echo", argumentTypes = List.of("Unknown")) → "ERROR"
  • inferReturnType(functionName = "echo", argumentTypes = List.of("float")) → "ERROR"

Explanation

  • makeInt is valid because it has zero parameters and a fully concrete return type int.
  • echo is valid because the type variable T appears in the parameter list, so its concrete type can be inferred from a call.
  • badFactory is invalid because a zero-parameter function cannot return a type variable whose binding can never be inferred.
  • 1badName is invalid because function names must start with a lowercase letter.
  • badUnknownPrimitive is invalid because float is a lowercase identifier used as a primitive type but it was never registered.
  • badUnknownGeneric is invalid because Wrap is used as a generic type constructor but it was never registered.
  • Registering makeInt a second time fails because function names must be unique and overloading is not allowed.
  • makeInt() returns int because it exactly matches the registered zero-parameter function.
  • makeInt(int) returns ERROR because the registered parameter count is 0.
  • echo(Box<int>) binds T = Box<int>, so the return type is Box<int>.
  • echo(Unknown) returns ERROR because a bare uppercase identifier is not a valid concrete argument type.
  • echo(float) returns ERROR because float is not a registered primitive type.




Please use Laptop/Desktop or any other large screen to add/edit code.