Let's Make a Generic Inference Algorithm

Hello, welcome to Let's Make an Inference Algorithm. I'm Ryan Kavanaugh. I'm the dev lead for the TypeScript compiler team at Microsoft. My goals today are to show you a high-level overview of how TypeScript's generic inference process works.

People often ask me how this works and I can't give you a complete explanation in 20 minutes, but we can go over a lot of the high-level concepts and explain what the general goals are. This is going to be an example-driven talk because our language is driven by motivating examples that really show why things work the way they do, and we're going to discuss possible other options of how things might work and discuss some of the tradeoffs that you take as you make different decisions along the way.

So let's start with an example. I have F here. It has one type parameter, T, it has a regular parameter, x, of type T, and it returns a T. Whenever TypeScript sees a generic function call, it acts as if you had written a type argument here. You can write type arguments yourself, but you don't have to. And if you don't, we will try to figure out what you want it to go here. In this case, we're going to pass in the value 42 for x, and the question that we need to answer is, like, fill in the blank. What goes there? If we had forced the user to write a type argument in that position, what would they have written? We can start making some guesses about what we might want to do.

One thing you might say is, it's any. If you don't tell us, we're just going to assume any, and then let the chips fall where they may, right? That wouldn't be very good. I think people wouldn't like that. We could say unknown. In this example, unknown is a safe bet, right? 42 is a valid unknown. Whatever f returns is sure to be an unknown. So unknown is a correct inference, and you could make that, and you could make a theoretical argument for unknown. We could say, well, 42 is a primitive. The primitives are number and string and Boolean. So maybe you meant the whole family of primitives when you invoked f here, and maybe that's what you want to happen. Or we might say, no, number. 42 is a number. That's probably what you want for t. We could also talk about the literal type 42. I will be pretending that literal types don't exist for the purpose of this talk, because it complicates things a lot. So a number is as low as it goes right now.

We think that number is the right answer here. It seems like if you called f of t and gave it a number, the most specific value that we can pick is the right one. So what is the algorithm that we would write down if we had to specify how that works? Well, we would say we're going to look for t and find a place where it occurs in the argument list, in the parameter list in this case. We're going to say, oh, 42 was passed to x, so we found this guy, we found this one, we lined up, we say, yup, that's the t. We'll say 42 is a number, therefore t is a type number, therefore it's as if you had written f of number, therefore x is a number. Cool. Talk's over. Everyone go home.

Cool. Now, let's write down the algorithm here. Look at the argument type where we see the type parameter being used at top level and just sort of use that. But what if there isn't a type parameter used at the top level of our function signature? It could appear somewhere else.

So I have a type here, box of t, pretty straightforward. It just has a single property called value of type t. We'll use this a lot. It's a great type to use. I have unbox of t. This is another good function. It's a great use of generics because it takes a box of t and returns the t from inside of it. So it does the great thing that you should do with generics, which is relating your input types to your output types or an input type to another input type. I normally won't be writing function bodies here just to save screen space, but you can imagine the implementation of unbox. It just returns B.value. And we call unbox and we pass in value colon 42.

So we need to figure out what goes into this type argument that we are inferring. One thing you might do is you might just do a lining up process, where you say, okay, we saw value colon t at the b argument. We saw value colon number down here. That's the type of this expression. We just sort of line up the t and the number. I won't talk about exactly how you go about doing that, but you can imagine how it works. Therefore, t is a type number, therefore, n is a number. Really good. We might write that down as at each of the parameter positions, we'll look for ts and we'll line it up with the argument types and we'll set t according to those matches that we found.

I need to shorten this text as we change it over the course of the talk. I'll talk about step one as collecting candidates by doing that matching process, and we'll set t to a candidate from the set that we found. But a candidate is unsatisfying. That seems underspecified, so if there's only one candidate, that's straightforward, but what if there's multiple candidates? Box, unchanged in this example, but now we have box has value of t. It takes a box, which is a box of t, and it takes an x, which is a t, and it tells you whether or not the value in the box matches the x that you gave it. You call it and you say value colon 42 and the string hello is your x value.

Let's collect some candidates. We pick up number from value colon 42, we pick up string from x. So now we have two candidates and we need to decide what to do. We might say there's nothing really in common between number and string so we'll just go to unknown. We'll act as if you had written box has value of unknown, which means that value colon 42 is a valid unknown and hello is a valid unknown. The call will succeed. That's good. We could say it's string or number. It's a little bit more specific type. Again we would process this call and say OK, it's as if you had written box has value of string or number. Value colon 42 is a valid, box is string or number and hello is a valid string or number. The call should succeed. Or we could say T should be number and you would eventually get an error on hello because if we had said box has value of number, we wouldn't be allowing you to pass that string to the number position. So what should we do? We've got three valid answers that it seems like we could choose from, but two of them don't err and one of them does. Erroring seems bad. But what should we do? I will offer you a principle that I think is useful when you're thinking about generics, which is that they should usually mimic what would happen if you had inlined the call to that function. So by inlining I mean replace the call with a recitation of the function body. So if we have this call that we had before, if we inlined it, it would look like this. It would say value colon 42 gets replaced here. That's replacing box up here, dot value corresponds here and then hello goes here. This is not how TypeScript works internally. We're always reasoning about things in terms of the function signature. What I'm showing you here is just a way to think about how generics should work. So TypeScript would say, if this is what was happening, that you can't compare strings and numbers. That seems like not a plausible piece of code to write. It's always going to return false. You probably meant to write something like this value, which is a number, triple equals hello dot length or some other way to make these things line up in a way that they would plausibly overlap. So it seems like this call should error, but you might go back and say, you know, Ryan, T as string or a number is a really good inference. You should just do that because if you had inlined this but treated these values as if they were of type string or number, then it would have been allowed. So maybe this is just a circular argument and Ryan's making very bad points.

To that, I would say that doesn't seem like the right behavior because developer intent exists. At least for now, humans are writing this code. Humans have intent and the way that you structure your code informs us of that intent. Let's think about some counter examples of how you might have written box as value. Had you wanted the type of the box and the type of the X to not have any relationship with each other, that's what multiple type arguments are for. You could have said this has two type parameters T and U, and there is no relation between these and they can be inferred freely without regard to each other. Or if you really wanted things to be whatever, you can just say box of unknown and X colon unknown. There's no need to use generics at all if you're not trying to relate what's in this position to what's in this position.

So our algorithm becomes collect candidates, pick the first one, and then process the call, we think that you wrote those type arguments with a purpose. So it looks like this. We say it's as if you're written box has value of number so we can't convert this string to the number here. Again, this is the inference process, we're always trying to figure out what you would have written had we made you write this. And if you feel like writing box has value of unknown here, you're always free to write these type arguments explicitly. It's all about what the inference behavior should be. It's not always about the correct answer, it's about the best answer. The best correct answer, I guess. So our algorithm here is we're collecting the candidates, picking the first one and processing the call. But first is pretty weird. Why did I say first and not last? Why not the middle one? Why not the second to last? First is pretty arbitrary here, right?

So let's look at another example of multiple candidates. This time I have find of t. You give it a needle of type t and a t array, which is your haystack. And then, like I said, no function bodies. You can just imagine what find does, right? It maybe calls haystack dot includes needle. So you call find and you pass hello and the 1, 2, 3, hello. So it's a string in this position and a string or number array. So we go through collect candidates. We got a string from the needle and a string or a number from the haystack. We pick the first one, which is that t as of type string. And then that would imply that we error on the string or number array appearing in the second position. If we think about our inlining, even though we can't see the body of find, any plausible implementation that we can think of really would not have erred on this call.

So it seems like we need to do something better here. We need to pick the best candidate from our list, not just the first one. What does best mean? That's just kicking the can down the road, right? So how do we determine best? The concept that we use is thought of as the best common supertype, which is the largest type from the candidates that is the one that contains all the others. If we have string, number, and the union type, string or number or Boolean, this last type, the third one here, contains all the others. String appears here, and number appears here. This is a supertype of the other two. So we would pick this one and say, if these were our candidates, this should be the one that we choose. If you have fish, or mammal, or animal, we want to pick animal, that's going to be the one that contains the others. If you have string and number as your candidates, there is no best common supertype. We'll still have to do something kind of arbitrary here, but we're not going to form up a union automatically here for the reasons that we talked about earlier. So in this example, we collect our candidate string from hello. We collect string or number from the array, and the best common supertype between those is string or number. It is the candidate that contains all the other candidates. That's the one we choose, and the call succeeds. So that's really good. Had you only had numbers in that array, now this call looks suspicious. It seems like something has gone wrong. So candidate one is a string. Candidate two is a number. We fall back to picking the first one, maybe. So we'll say T is string, and then that means we'll get an error on our number array because we expected a string array in that case. So that seems good. So we're collecting our candidates, we're picking the best common supertype, and we're processing the call.

I think the collectCandidates step is a little bit underspecified, and let's look at how that can go wrong. I've got box again, and I've written a new function called unboxIfBox. It's a great name. You either give it a box of T and it will give you back the T from inside the box, or you give it anything else and it will return that same anything else. So maybe you give it a string, it just gives you back that same string.

We call unboxIfBox and we pass in a box of number here, and we go to our candidate collection phase. So we work left to right in this union, and from T, we pick up the candidate box of number because that's what was shown up here. Then we pick up number, from T, here, where it appears as boxes of T. There's no best common supertype, so we pick the first one arbitrarily, we say it's a box of number. That doesn't seem right. For one, that's not useful at all, and even if you had said, well, the algorithm should be, we should union these, let's go make unions from multiple candidates, that's the best thing to do. It still doesn't make any sense to say X is of type number or box of number, because the contract of this function just implicitly does not really mean that it's going to do that, right? Number is the only correct answer here.

If you just stare at the candidates, you can't really figure out what to do. You need other information about how you got those candidates. You have to make an observation which is that the candidates that you collect from a deeper nested occurrence of T are always going to be better than the ones that appear at high level. The worst case of a type inference you can make is this standalone T, and box of T is better than that. It means that you matched something more specific because it means that these things lined up, and you should always prefer this T over that T if they both exist. We're talking about the priority as we go now, so we collect a lower priority inference from the standalone T. We pick up number from where it appears inside box. That's a higher priority inference. And then we say okay, we're going to take all of the candidates that tie for highest and pick the best common supertype out of those. There's only one matching high priority inference here, so we pick number and that's good. So that's how we solve that problem. As we collect the candidates, we note the priority, and then we pick the highest priority best supertype from that list. You can look at this and say, hey Ryan, why are we picking supertype? Why not subtype? What's going on here? It's a great question. I have a new version of find. It is still one type argument, find of T. It takes a T array and a function that accepts a T and returns a Boolean. If we put on our imagination hats and try to think about what this does, probably it returns like, let's say some random value of type T from the array where the function or maybe where the function returns false. So I have this function isNeat, it takes strings or numbers, it tells you if they're neat or not, and then we call find and we pass it this number array, and we're looking for something that's neat from that list.

Let's do some inference. We pick up a candidate from the array, which is number. We pick up another candidate from isNeat, which is string or number. These both appear one level deep in nesting, so they're of equal priority. So we're going to pick the best common supertype from among them. That's string or number. So that's the value that we get out.

We see T is of type string or number, so X is of type string or number. Seems okay. But then you look at it for a little bit, and you're like, wait a minute, what is string doing in X? We didn't give any strings to find. Is neat can't produce strings, it can only accept strings. Find at runtime has no way to even inspect find and figure out what its argument type is, so it doesn't seem plausible that someone given an array of numbers is suddenly able to produce a string out of thin air, it doesn't make sense. If you just look at this for a while and you stare at these candidates, like earlier, you can't just look at these candidates and figure out what to do unless you have some other information.

The other information that you need to take into account here is whether the T is appearing in a covariant or contravariant position, or we might talk about this in terms of input or output positions. These Ts from the array are going into find and these values we're passing to arg from within find are coming out of find. So really we need to think about the input and output positions of the type parameters as we're collecting them. Our new algorithm is something that I can only really demonstrate with a more complicated function. I've made find take two arrays, and I've made is neat also accept Booleans. I apologize that it's a little bit longer, but we're going to call find, we're going to pass a string or number array into this first array, a number array into the second array, and then our predicate function in func here takes strings or numbers or Booleans. Let's make a little table, I'm going to condense the code sample so you can see it all on screen at once.

Let's do some inference, we're going to collect some candidates. I'm going to start at arg actually, so we're going to line up arg colon t to this string or number Boolean value, and that's going to give us our input candidate. We're going to collect from our first t array, that's a string or number, and our two gets us a number array. So we've got these list of candidates here. The thing that we seem to want to pick is string or number, so what we're going to do to get that result is we're going to treat the input positions as an upper bound on the result, and then we're going to do our regular best supertype algorithm among the other output candidates that we have. So our best output is string or number, that is below, in Type Theory terms, below this string or number or Boolean upper bound, and we'll proceed with the call as if you called find or string or number. That means that Boolean isn't showing up in X, which is definitely the right behavior. If I tweak this example a little bit, and I say isNeat only accepts numbers and then I pass in a number array and a string array, we want to issue an error here, and ideally the error that we would issue would kind of act as if you had called isNeat of A and isNeat of B. That's where the error in this program is, right? So we know from a finds signature that it is capable of passing a T from Array2 into func at the arg position, so we need to error as if you had called isNeat of A, because that's what's going on here, so let's try our algorithm out. We pick up our best output candidate from a string or a number in that array, but then we find an upper bound from isNeat, because we see n colon number in an input position, and so we stick with number, as we're inferring here.

And then, from this other array, we're getting a lower output. So then, we get an error. We say, okay, it's as if you had called find of number, because we bound it based on this input position. Therefore, you can't convert this string or that string to numbers. You get a really good error here, so that's great. So our updated algorithm becomes collect the candidates, noting the variance, and then pick the best candidate bounding in both directions.

Lasty, I want to talk about what we call context sensitivity. It's a bit of a mouthful. I have a new function for you here, which is exec of T and U. It has a producer argument that produces a T. It has a consumer that takes a T and produces a U. And then it returns the U that your consumer produced. So if we imagine the function body that this generic signature implies, it says that exec will invoke producer, get back a value of type T. Pass that T to consumer, in this argument position, that will return a U and then exec will return that U. So it's kind of a one line function, but that's its generic signature.

We're going to invoke it, with our producer being a function that produces hello. And our consumer function will accept hello and return hello dot length. So we think n will be 1, 2, 3, 4, 5. Let's do some inference. We proceed left to right in the absence of any other algorithm, and we say let's collect from consumer in the first position, or equivalently, look for the first T in this list. The T that we see here is for arg, and arg down here has no type annotation, and there's nothing that tells us what arg's type should be. There could be a contextual type here, but there's not because we're in the middle of inferring what T should be. So we pick up a candidate for T, which is like, it's implicit Any. Maybe we throw that away. Maybe we don't think about it. It doesn't really matter for the purpose of this example, because we go on to collect for U. And we say arg.length is what we're inferring for U. If arg is of type Any, then Any.length is of type Any. So therefore, the candidate that we get for U is Any. We pick up a candidate for the producer's return type T, which is string, and therefore we say U is Any. Whether or not we, you know, how you deal with the implicit Any and the string candidates for T is immaterial here because it means that N is of type Any. And that's really unsatisfying, because you look at this code and you look at this code and you say, I don't see why TypeScript couldn't figure out what to do with this. So what you have to figure out is, arg can get a type based on its context, so this expression, it can change types based on where it appears in your program. For this function, not so much. It doesn't have any arguments. It just returns a string. So what we can do is process these arguments out of order by looking at whether or not they're sensitive to the context that they're in. So our new algorithm is going to be that we collect the candidates from the non-context sensitive expressions. We're going to look at all the type parameters for which we've collected at least one candidate, and we're going to pick the best one from there. And we're just going to write that down and then keep going. We'll repeat the process for our context sensitive expressions and then process the call. What does that look like? Let's do some inference. We do our inference by first doing our pass. It's looking at the non-context sensitive arguments. Here, we have t colon string coming up from hello.

So we're done with all of our context insensitive expressions now. So we write down t is string. We go to process arg. And we say, ah, arg is of type string. I'm going to write down number later, but I wrote down string for t. So now when I'm looking for the contextual type for arg, I know that it's string, based on t and the string that we wrote down earlier. That lets me process arg.length. Therefore, use of type number. And everything just works. You can think about what to do with t in this particular position. It doesn't tend to matter since it just kind of doesn't. If you work out why, you'll see why. But that's how it works.

So that's our context-sensitive expression inference algorithm. So in summary, I hope I didn't scare you too much. I think this is all pretty straightforward. We had some pretty basic code examples, and by looking at those code examples and how they were written, we were able to figure out what the intent of the user was, and we could use that to do the right inference. Just being correct isn't really enough. You have to also get the best inference. I showed a lot of examples where there were two to four correct answers to choose from, but only one best answer. Inference is really like a multiple-choice test, where you're not just tasked with finding a good answer, you're tasked with finding the best answer. If you think about your language design in terms of your motivating examples, I think that brings a tremendous amount of clarity, because if you just go and try to write down an algorithm without looking at how the examples that you care about act, you might not get the best behavior. So always be looking at the examples and using those to drive how you make decisions about your inference and everything else about your language.