How are Generic Functions Checked?
Give a program like:
var foo[A](arg A) arg bar end foo(Baz new)
How and when do we verify that:
baris a valid message on
Bazis a valid argument type.
- That the generic parameter
Acan be inferred from
For the first question, there are basically two solutions:
C++-style. A generic method cannot be checked on its own. Instead, it gets instantiated at each callsite with specific concrete types, and its only then that it gets checked.
C# with constraints style. A generic method's type parameters are annotated with "where" clauses that limit the type of type arguments. A method can be checked against its constrained types.
C++ is a mess, so let's try to go with C# style. A type parameter like the above
one with no constraint would default to
Dynamic?), meaning the
above code won't check because
Object doesn't have a method
bar. To fix it,
you'd have to do:
var foo[A Baz](arg A) arg bar end
Baz is assumed to be some type that has a method
bar. Type-checking a function now means:
- Evaluate the type annotations of the static parameters.
- In the function's type scope, bind those types to the static parameter names.
- Evaluate the type annotations of the dynamic parameters in that scope.
That should conveniently alias
Baz, so when we look up
A later, we'll get the constrained type. Now we can type-check a method independent of its use. Win.
Now, the second question. How do we know that
Baz is a valid (dynamic) argument type? Let's skip over inference now and just consider:
To check this, we just need to:
1. Evaluate the constraint on the static parameter (
2. Evaluate the static argument.
3. Test for compatibility.
4. In the function's type scope, bind the static argument value (not the
constraint type) to the static parameter name (
5. Evaluate the type annotations of the dynamic parameters in that scope.
The last question, inferring static type arguments. That's going to get tricky. Consider a function like:
var foo[A, B, C](a List[A], b B | C, c (A, (B, C)))
We need to answer two questions: 1. Are all static type parameters present in the dynamic parameter's type signature? (In this case, they are.) 2. If so, given an evaluated type for the dynamic argument and the expression tree for its parameter type, what are the values of the static type parameters?
The first one we can do statically independent of the actual type semantics by just walking the parameter type tree. The second one is hard because it's another core capability every type-like object will need to support. So the question is, given:
var foo[A, B](a Dict[B, A]) foo(Dict[String, Int] new)
Is there a way we can ask
Dict to help us figure out what
B are given
Here's one idea. We'll create a special tag type that just represents a placeholder for a type parameter, so that we can treat "A" and "B" as fake types. Given those, we can evaluate:
Dict[B, A] // which desugars to Dict call[B, A]
And get a type object back (an instantiated
Dict) with our special type tags embedded in it. Then we evaluate
Dict[String, Int], the actual argument type. Now we've got two objects we can line up, so we do:
Dict[B, A] inferTypesFrom(typeMap, Dict[String, Int])
That will take some sort of map that maps parameter names like "A" to their inferred type. Every type will be expected to implement this. An implementation would look something like:
def Dict[K, V] inferTypesFrom(typeMap, other IType) let dict = other as(Dict) then let keyType = K as(TypeParam) then typeMap map(keyType name, dict keyType) else K inferTypesFrom(typeMap, dict keyType) end let valueType = V as(TypeParam) then typeMap map(valueType name, dict valueType) else V inferTypesFrom(typeMap, dict keyType) end end end
Note the recursive calls to
inferTypesFrom. Those handle nested types like
Dict[(Int, String), List[String]]. The
typeMap will have to handle collisions where a type parameter appears more than once and is bound to conflicting types like:
var foo[A](a A, b A) foo(1, true)
I think this would work. Handling or types and some other stuff may be a bit tricky. Figuring out how to reuse this code across all generic types will be a bit of work too.