~/problems / Iterators & parsers / Parsers and interpreters

Toy language type inference

medium 3 levels ~60 min OpenAI

Level 1 Type nodes

A toy language has these types:

  • primitives: exactly int, float, str, bool, char;
  • generics: any other name, like T1, T2, S;
  • tuples: an ordered list of types, possibly nested (and possibly empty).

Implement two classes:

  • Node(value): value is either a name (str) or a list of Nodes (a tuple). Keep it in an attribute called value.
    • str(node): a name prints as itself; a tuple prints as [ + its children joined by , + ], no spaces.
    • node == other: structural equality (same names, same nesting). Comparing with something that isn't a Node is False.
  • Function(parameters, output_type): a list of Nodes and a Node, kept as attributes with those names.
    • str(function): ( + parameters joined by , + ) -> + the output type.
t = Node([Node("int"), Node([Node("T1"), Node("str")])])
str(t)                                    # "[int,[T1,str]]"
str(Function([t, Node("T1")], Node("T1")))  # "([int,[T1,str]],T1) -> T1"
Node([Node("int")]) == Node("int")          # False

No parsing yet: tests build the objects directly.

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Parsers and interpreters. Tokenize, recursive descent, S-expressions, evaluation and type inference.

0:00
Ctrl ' run · Ctrl ↵ submit
esc