Type System for a Toy Language | Dataford Interview Questions

Your question is Type System for a Toy Language. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Design a type system for a hobby/toy programming language.

Asked in the screening_coding stage. Screening coding round.

Implement infer_type(expr), which returns the inferred type of a valid abstract syntax tree, or "TypeError" when type checking fails.

Contract

Expressions use dictionaries: {"var": "x"}, {"let": {"name": "x", "value": expr, "body": expr}}, {"lambda": {"param": "x", "type": "Int", "body": expr}}, and {"call": {"function": expr, "argument": expr}}. Integers and booleans are literals. Operators are represented as {"op": "+", "left": expr, "right": expr}. Supported operators are +, -, *, <, and ==. if uses {"if": {"condition": expr, "then": expr, "else": expr}}.

Return "Int", "Bool", or function types such as "(Int)->Bool".

Constraints

The AST is a nested combination of the specified expression forms.
Literals are integers or booleans.
Lambda parameters are annotated with Int or Bool.
Let bindings are lexically scoped.
An if condition must have type Bool, and both branches must have the same type.
The AST contains at most 10^4 nodes.

Function Signature

def infer_type(expr):