Gleam: Preserve type variable names within functions

[lpil]

Currently when type variables are used in the annotation for a function and in annotations within the function they will be seen as different type variables, even if they have the same name.

To implement this we will need to persist the hashmap of type var names to type var types in each function. To do this we may want to refactor the typ module to have a Typer struct holding the state with each function being converted into a method on the typer. This would match how the Formatter works.

This code should type check:

pub type Box(a) {
  Box(value: a)
};

pub fn go(box1: Box(a)) {
  fn(box2: Box(a)) { box1.value == box2.value }
}

[lpil]

@QuinnWilton Did you want this ticket? Drop a comment and I'll assign you

[QuinnWilton]

Yeah, sure! It'll be the largest work I've done on Gleam, so it might take me a bit longer + I'll likely have more questions as I start on it :)

[QuinnWilton]

I've been working on this a little bit, and I'm increasingly of the opinion that we probably want two new "Typer" structs, like you mentioned in my draft PR: ModuleTyper, and FnTyper, and that Env should be renamed to ModuleTyper.

ModuleTyper should be responsible for inferring module-level statements, and should instantiate a FnTyper for each Statement::Fn it performs type inference on. That struct can look approximately like this:

struct FnTyper<'a, 'b, 'c> {
    module_typer: &'a mut ModuleTyper<'b, 'c>,
    level: usize,
    type_variables: im::HashMap<usize, Arc<Type>>,
}

Should local_values and annotated_generic_type also be moved onto that struct, from ModuleTyper? For local_values it may be worth keeping that field on the ModuleTyper, but copying it into the FnTyper to handle the prelude values.

I think that infer should be moved into FnTyper, along with all of its helpers for inferring expressions. Whenever infer_fn runs, it can create a new FnTyper for handling that function. Doing this means that we don't need to cleanup state after that function is inferred, and may allow us to remove this sort of existing cleanup: https://github.com/gleam-lang/gleam/blob/master/src/typ.rs#L3288

I then just need to modify the handling of function and let annotations to add their type variables to the state, and modify instantiate to use that state, and I think things will work as expected.

Does that align with what you were thinking needs to happen?

[lpil]

That sounds like a good improvement, especially the removal of the cleanup code. Thanks for this thorough write up!

[QuinnWilton]

Just an update on this: I have tests passing locally, and the new behaviour seems to be working great. That being said, my local branch is a bit of a mess, and I don't think it's in a mergeable or reviewable state.

I'm going to try redoing the relevant work on a new branch, now that I understand what the finished result needs to look like, to see whether I can do it with fewer changes. I may also separate out some of the refactoring into a separate issue; I was able to simplify some logic, but it ended up being a larger refactor than I planned, and I think keeping it in the same pull request will just muddy the changes a little bit too much.

Also, while I was able to remove the cleanup code for local_values, I haven't managed to find a good solution for handling annotated_generic_type yet. I think that I want to have a better understanding of the system / talk through some possibilities with you before trying to tackle that issue.

[lpil]

Yeah I'm not hugely happy with annotated_generic_type. There's likely a better approach but I don't know what it is. For now we can leave it as is so that we can focus on getting this through unburdoned?

I would be happy to merge in the refactoring in a separate ticket. :)