type inference

[vitiral]

I have need of type inference. The primary use-case is things like this:

\ Walk the Bst, calling each node with the fnSig
fn walk[f: fnSig[&D, &K, &V], bst: &Bst[K, V], d: &D]

In C you can do this but you need to use void* for everything. Yuck.

I've debated various ways to do this, some extremely complicated. I've settled on what I think is the simplest possible solution which may not apply to every usecase, but applies to 95% of them. The remaining 5% can solve themselves with code generation or similar.

Architecture

Introduce a new "native" type called a TyInfer, which is short for "type inferred". These can have references to them but can never be "concrete" (can never fetch a reference).

There will be a global inferList which holds current assignments for type inference (fromInferTy -> toTy). Note that toTy can also be a TyInfer (in which case the lookup will happen again). This inferList only needs to be about 16 elements long (we do not expect many type inferences to be used).

When the type checker comes across one of these in REQUIRE it:

• attempts to look it up (in a global "infer list"). If the lookup value exists then it substitutes it. If it does not exist, it uses the GIVEN logic below.

When comparing a TyInfer against a GIVEN we:

• attempt to set the TyInfer to the GIVEN in the "infer list". If the value is already set we throw an error.

Extending TyI

I batted around an idea where a user can specify types, i.e. [K=A]Bst[CStr, K] where the K=A is stored as an SLL on the TyI. This would enable the user to "create" their own arbitrary TyInfer if they needed new names. Fundamentally though, this is an edge case that can instead be better supported by type generation. The main use case (using types in function signatures) is already supported, since function signatures are already generated.

This would also have a memory cost of one pointer per TyI. If we want to add exotic features to TyI we could maybe do so with a pointer to some kind of "exotic" struct of TyI extensions. That's not currently planned, so I won't implement that here.

Docs

Something to mention in the docs about this feature specifically, and fngi in general, is that fngi's type system requires binary compatibility. The compiler will never "auto generate new code" -- it will only ever generate new signatures.

[vitiral]

I'm not yet convinced this is necessary. For now I can manually implement things and evaluate later.