Extended Type Inference

[sunjay]

We will need to extend our type inference algorithm to include function/method dispatch in order to support methods. In doing this extension, it's probably a good idea to consider generics and traits as well since those features will also eventually be added.

We're probably going to move from the current set-satisfiability approach to something more based on the classic Hindley-Milner type inference algorithm. The reason we can do this is because the main reason for using sets in the first place was so we could support polymorphic literals (e.g. 123 can be either int or real or the real part of complex). It turns out that we can actually do this in Hindley-Milner as a post-processing step. That saves us from having to build the entire algorithm around sets. (sets are hard because a lot of the inference would quickly become exponential as we iterate over all possible combinations of different set elements in more complex constraints.)

The post-processing step is simple: First, we store the type variables that correspond to any integer or real number literals. Then, after the types have been inferred/checked, we go through each one. We check that integer literals were typed as int, real, or complex. We check that real number literals were typed as real or complex. If an integer literal type variable is ambiguous (did not resolve to a concrete type but also didn't encounter any errors), we resolve it as int. Similarly we resolve ambiguous real number literals to real.

Once we get to the point of adding generics/traits, we can start to bound the "ambiguous" type variables with traits. That means that before resolving to int or real, we'll need to check that those types implement the necessary traits.

[sunjay]

Fixed in cde742c