Building Your Own Programming Language Evaluating Expressions
Transcript from the "Evaluating Expressions" Lesson
>> Speaker 1: Now we have the ability to evaluate. Now, this is effectively gonna follow the same rules as when we parsed our tree. Like when we took the tokens that were, we took the tokens which were one flat array, we went through the tokens, we looked for our parentheses.
[00:00:13] Our parentheses dictated where our nesting was in our logic. Then we iterated through that nested set of arrays and created either the edges of our tree, which are the numbers, the literals, and the strings, or we came across one of our arrays, which we had to then recurse down and do the same thing.
[00:00:37] So with evaluation it's one more turn at the same thing, which is start at the top of the tree and start walking down it until you get to the actual ends, right? And start doing the things that get us there. We saw we have some functions built into add.
[00:00:54] We saw we had some functions built into subtract. So on and so forth, right? We can add additional things in there as well. But let's actually kind of look at the tests to kinda see what the kind of first version of the iteration is here. And so it's not dissimilar from when we created our abstract syntax tree, which is, hey, if this evaluate function gets to the end of the tree, gets to that leaf node and like there's nothing left to do, no more left to descend, all right, we're done.
[00:01:27] If you get to a node that's a numeric literal of 2, you're at 2, right? If you get to a string, you're at a string, right. Theoretically it's not valid to get to just a random floating identifier. So we don't have that case covered. But like eventually, when I get to the point where it's like, I come to an add statement and I see that it's adding 2 and 3, well, that should give me 5, right.
[00:01:56] Otherwise this programming language is junk, and that's not cool. So let's begin to start like, at least these base cases of if this evaluate function just gets a lone literal, we're done, all right? So I'm going to un-skip those two.
>> Speaker 1: We'll go into evaluate and we're gonna say all right, you're going to get a node.
[00:02:25] Now, that node could have child nodes. We know that. There's a lot of actual things that can happen as language grows. It could be a lambda, it could be variable declaration. It could be an if statement, eventually, right? We won't get to all of those today, but you can begin to kind of expand this to all the different cases that it comes across and how it branches and does some of that logic.
[00:02:45] And we chose a relatively simple style of language, but clearly there's like a generator function with an async await in it. This can grow to the scale of your ambition. So should we come across a given node, well, this is gonna be pretty easy. In that case, we will say, all right, if the, we'll do this kinda as our fallback case.
[00:03:10] If the node has a value, right? We know that identifiers didn't have a value. We know that our call expressions don't have a value. We know that things have values are strings and numbers, right? So this will be our kind of like, if all else goes wrong, we'll say return, not really goes wrong, but if all falls through, return node.value.
[00:03:34] Let's take that for a spin.
>> Speaker 1: Cool, they pass. I can tell you the next ones aren't going to actually happen. But we'll have some cool ones, we're gonna actually have to add some functionality to our standard library as well. All right, so what happens if we come across one of these call expressions?
[00:04:01] Well, call expression has clearly got some branches to it. A call expression could have more call expressions in it. We saw we can nest functions indefinitely, right? So when we come across one of those, we're like, all right, I need to figure out how to actually apply this function.
[00:04:42] We're kind of using the fact that our language is still very small and taking advantage of those are the only two things with values. But we might have to get a little bit more specific over time. So if the node type,
>> Speaker 1: And like I kinda mentioned before, this is one of those things where I might very well make some helpers, like is call expression begin to abstract some of this out, so I'm not typing all over the place.
[00:05:02] Because all of a sudden, my evaluator's not gonna work if I make a typo, and I've already made a typo today. But when I keep it in there for like the clarity. So if this is a node type of call expression, well, then we need to do something.
>> Speaker 1: It's got a name and it's got the arguments that have values, right? So I can kinda look it up in a hash table. I can give it the values and I will get the result, right? I'll get the, like pure value that we were getting before out of just the regular literals.
[00:07:05] So I can go in here, I can say.
[00:07:28] And then the args we're going to have to do something with right? Because what can the arguments be? Does anyone remember? Are they always values?
>> Speaker 2: No.
>> Speaker 1: No.
>> Speaker 2: Could be strings.
>> Speaker 1: They could be strings. What else could they be?
>> Speaker 2: Functions.
>> Speaker 1: Other functions, right?
[00:07:44] So that's not gonna work. So we are going to have to check to see like, all right, if the argument is a function, go down another level and keep keep looking until you get me values. Keep going until you get a value. So we'll keep passing stuff to evaluate until it falls down to this last one right here, right.
[00:08:17] You can't have a variable called args. So node.arguments.map. So go through each one of those arguments and pass them into evaluate. This is very similar for what we did for the AST, right? We said, all right, I want to go ahead and parse, you know each array, but then as we go through everything that wasn't the first, go parse those, go parse those until you get something that falls through to just the value and comes all the way back up.
[00:08:44] All right, so we'll do that. Maybe I'll even spell evaluate right? Who knows. So we have that in place. And then there is a chance, like let's say they gave us addd with 3 D's, or they gave us some function we don't have, right. If we look that up in that object, in that environment object, it's going to come back with undefined.
[00:09:23] So what we'll say is if you got something, like we could say like if it's undefined, but I'm gonna be a little bit more strict. If the type of fn is not function,
>> Speaker 1: Throw a new TypeError. And we'll say that node.name,
>> Speaker 1: Is not a function. So at least we know what we misspelled, we can go look for it, right?
[00:09:59] So we'll have that in place. But if it is in there, right? We can just say, and you have a few choices that you can do this. You can do fn,
>> Speaker 1: And all the args. Or if you wanna use ES6, you can do fn just spread out the args.
[00:10:22] Right, so if we found a function with that identifier, like add, subtract, multiply, what have you, right, and it's in there, [LAUGH] take all those arguments and pass them in and then eventually those will become values that will have, we can actually use them, right? Because if it was another function that was the first argument, then we have to keep going.
[00:10:47] Because like, eventually it'll keep getting those until we actually get the raw value out. It'll traverse down that tree for us. All right, and the cool thing about this is that it will effectively, it will keep going [INAUDIBLE] our next two steps should pass unless I've made some terrible mistake, but we'll find out together.
[00:11:07] So the ability to parse a single expression and the ability to parse nested expressions, both of these should totally work for free.
>> Speaker 1: Great, like we get now effectively, we don't have a way to actually like us to get our hands on, we're still running this test suite, which we're definitely gonna need.
[00:11:36] But we have a way to like now take some code that we've written in drop bear and turn it into some values, right? You know, a thing that would make this language more powerful now is beginning to add more and more functions. Like just having math functions, not great, right?
[00:11:54] We don't have the ability define variables yet. So it's pretty deterministic at this point. So there are other things that we can absolutely add to it. But if we were building a templating language at this point, we'd be getting actually dangerously close, right? Because we could, you know, theoretically from our command line or whatever, we could pass in, like, all right, here's the data here's the templating, go and do all of your magic and figure it out.
[00:12:17] We can like have like, effectively the ability to iterate. We can implement more and more in that standard library and get it for free. But we have the ability to call functions. You have a question?
>> Speaker 2: Earlier you mentioned the visitor pattern.
>> Speaker 1: Mm-hm.
>> Speaker 2: And it seems like we're almost tied to that for this task, that we need some way of doing a one to N recursion.
[00:12:41] And that is essentially and in evaluating each y i. So we would essentially be implementing some type of visitor observer pattern.
>> Speaker 1: Yeah, with the visitor pattern where like, we have the traversal separate from what we do right, here we are kind of evaluating it along the way.
[00:12:58] But like yeah, like for our HTML parsers and our like manipulations, we go from HTML into a set of props that we use in our application. Like we effectively just have the ability to traverse and then the things that should happen along the way. With that one, it's a little harder for us, because the DOM isn't the greatest data structure for that.
[00:13:21] So we still, our traveral, like the functions that we wrote tend to look maybe like jQuery inspired, right. Cuz we are looking for effectively a thing with a given ID a given classname, right, or a given data role. Because those are like how we have to find things.