Inferring Functions Exercise

[00:00:00]
>> Richard Feldman: So basically, we're gonna do the visit call expression. So this is essentially when you are in the parse tree node and you're going through that gigantic switch statement of all the different flavors of parse tree node. Now is the point in the course where we are going to finally take a look at the call expression.

[00:00:16]
So this is where you're actually calling the function. So there's this term callee. Callee basically returns to the thing that you're calling. As we noted in three or four sections ago, it is possible that this is an identifier, so like foo or something like the name of the function increment, but it's also possible it's not.

[00:00:34]
You can always call things that are just arbitrary expressions by putting parentheses around them. So since we don't know which one we have here, we are going to have to assume that it's a node and then treat it as such as we progress. So basically the next thing we're gonna do is just go sort of walk through all the arguments of this function, which we know based on having this node in scope, this like the parse tree node.

[00:00:55]
Parse tree nodes have the arguments listed for function types. This is what we are calling and then basically we're just gonna build up this, like accumulation of arc types by visiting each node in turn. So this is not just giving us the if we didn't visit the node and we just did it like this, then we would have a collection of parse tree nodes.

[00:01:16]
But that's not what we want. These are the arc types. So we're going to go call visit node to run our usual logic, go through our giant switch statement, possibly end up back here a couple times, who knows? And we're not gonna worry about [LAUGH] blowing the stack for this course.

[00:01:30]
And ultimately, after doing all that, we end up with archetypes being populated with the contents of all those visit node calls and all those different types, okay? So the next thing is our first, here's what we need to actually do. And this is basically where, rather than making a return type of 0 this is a case where we need to actually for the first time in any of our exercises, add a new row to our database table.

[00:01:56]
So this is something where there is a function in here has the word fresh in it, so I'm not spoil the answer, but you can poke around to find it. It's basically a way of saying, hey, database, I need a new row because I need to do some unification stuff.

[00:02:08]
So in most of our examples we have seen so far, we have this sort of extra pass, or, if you're doing it in canonicalization, where you go through and sort of hand out all of these IDs for database rows. But it's also very possible that right in the middle of unification, you're like, I need to do one of those.

[00:02:26]
Wait, I didn't plan ahead for this, I didn't anticipate that we would end up in this scenario. I have found that I need a new one of these. Now, granted, this one was kind of maybe anticipatable, okay, you're going to need a return type for your function, fine.

[00:02:38]
But this is something that actually legitimately happens all the time, and so it's useful to know that you have access to this and how to do it in the middle of a unification pass. So do that there, just change this from zero to basically give me a new fresh type variable that is a row where the the type is just gonna be initialized to null and then we'll actually do stuff with it later.

[00:02:59]
Then we start to actually look at like, what type of colleague are we dealing with? So this is where we've essentially broken it down into two possibilities. One is we are in the parentheses scenario as written out here, whereas, basically, okay, I have parentheses around something that is a function type and then I'm calling that.

[00:03:14]
Or I have an identifier where there's no parentheses, or at least probably not if the format runs. And then I'm calling that sort of by name. Yeah, so basically, in each of these two scenarios, we have some different thing to do. So here is basically take callee.body and go look up its type.

[00:03:34]
So essentially this is the callee and so we want to go look up the body of that function expression, so not the arguments, but this part, the body, go look up its type. And then basically make this variable here called body type, be whatever that thing's body type is, instead of the current that we're just initializing it to, which is null.

[00:03:53]
And then for the identifier case, we're not gonna look so much at the body, but rather we're gonna go look up the identifier and basically try to find in scope. Okay, is that thing there, that identifier for that thing's name, so like foo in this case. And then basically say like, okay, if we have one of those, then let's go get it out of scope, find this type ID and then use it right here instead of the hard coded zero.

[00:04:22]
>> Richard Feldman: Okay, let's go through these solutions. So, first, we're gonna start off with this one, create a fresh tight variable. Fortunately, we have they, let me jump down here real quick. Fortunately we have a nice convenient thing here called fresh type ID. So, let's go ahead and use that one right there.

[00:04:40]
What was that? Yeah, fresh type variable, great. FreshTypeID. So if you go look at the definition of FreshTypeId, very simple, it's just like we have this thing called NextTypeId, which is auto-incrementing integer, basically from your classic relational database. Except we're doing it with JavaScript arrays, increment it, and then basically just initialize it to null.

[00:05:00]
That slot in the database initialize the null and then return it. So great, we've now gotten our new returnTypeId in the middle of the function, which is very nice. Now we need to go look up the type, not the type ID of callee.body. So way to do that is basically just like visit node.

[00:05:18]
So we can, oops, go get the callee type. I'm sorry, that's. Yeah, am I in the right one here? I am. Okay, yeah, so get the callee type from the body. So this is visit node, calle.body. You know what? I'm looking at the my bad that's I was wondering why that wasn't there.

[00:05:39]
I'm looking at the wrong one. Let me look at the part five one solution that makes more sense. It's more complicated now that we're in function land.
>> Richard Feldman: Cool. Right, so there's our FreshTypeId. And here we are doing the visit node on the node.collee.body. That was that one and that's gonna be instead of body type.null.

[00:06:12]
And so now basically what we're unifying is the returnTypeId, which as we just saw a second ago, we have now initialized to null. So as we know from unify, this is because it's coming in as null, this is just immediately going to be unified to Assem link to whatever this thing is.

[00:06:26]
That's the like, the first code path we talked about in unify. So essentially, what we're saying here is like, okay, whatever your body type is, like the actual implementation of this body here, we are going to unify directly with that, like our whole type. Okay, so then the next case is where we don't have this unusual parentheses situation.

[00:06:49]
We instead have an identifier. And for the identifier case, it's even simpler where basically we're like, okay, we have an identifier, we've got the scope here. All we really need to do is just grab the function's type Id from scope and that's just the thing that we do at the very beginning of this, which is just hey, go get the scope.

[00:07:07]
And then resolve some links and compress to get it all the way back down to something that's either guaranteed to be null or guaranteed to be a concrete type. So this same trick that we use at the very beginning of unify, all the way back up at here for a and b, we can use it once again to just make sure that we have something that is all the way resolved to the end of the line.

[00:07:29]
And from there, we're basically just looking at the same stuff we were before, where we're like checking to see if there's return type information in this function return types map. A little bit of a sidebar on this, so back at the slides, we talked about how we're kind of storing this in the table.

[00:07:49]
That is a way that you can do this. But actually it's more common to store this extra function information out of band. So that, basically, rather than storing this right here inside the node, another way that you can do that, somebody asked the question isn't that gonna make the type?

[00:08:03]
Kind of big over here and the answer is like, well, yes, it is [LAUGH]. So another trick you can do is you can just sort of store it in like a side table where basically you just have a separate mapping from like the IDs that you know are functions to what are their extra pieces of metadata around that?

[00:08:16]
And this is basically just like demonstrating a way of doing that. Either technique works, they both have their pros and cons, but FYI, that's what the function return types like side map is about. It just kind of hangs up here with scope and the next type ID and errors and those other sort of global things.