Swift Design Patterns

4.6 Interpreter

One of the most popular concepts that have been floating around the software development community for the last several years, if not decade has been the idea of domain specific languages or DSLs. And the basic concept behind these is that given some sort of software product or scenario, we should be able to design a language that is specific to these scenarios and to the software packages that we should be able to represent in some sort of language. And then be able to take that language and apply it or send it into the system, and have the system understand that language. Now it's not a very easy thing to do, but it's very popular. And interestingly enough, there is a design pattern that's kind of wrapped around this concept that will allow you to not only be able to design these domain specific languages, but also be able to interpret them and that's exactly what this pattern is called. It's know as the interpreter pattern. We could get into some very difficult and complicated languages and design these and show an example, but I'm really gonna boil this down to a very simplistic example language that's already out in the world today and that's the language of mathematics. So let's say that I wanted to design a system that would allow me to input some language and that language is a mathematical equation, and have the system be able to interpret this language, and then ultimately provide an answer. And we're gonna keep things pretty simple, I'm gonna use the example of addition. But you could obviously expand this to do anything sort of operations that you want. The other thing that I'm going to assume to make things a little bit simpler is we're going to be using postfix notations. So if you've ever done any sort of mathematical software engineering, you've probably heard of postfix notation where it kinda takes the different operators and operands within a mathematical equation and reorders them. So, they're easy to interpret by a computer. So we're gonna be taking a look at that, as well. So, let's go ahead and create the InterpreterPatternPlayground and we're gonna start by creating some basic things here that are going to make up how we use the interpreter pattern. So everything within the interpreter pattern is typically broken up into an expression and those expressions can be evaluated. So, the easiest thing for us to do at this point is to create a protocol called expression. And then within here, there's gonna be a function and it's going to be evaluate and that's pretty much it. Now we're gonna keep things simple in this example, because we're making a calculator. And since we're only dealing with addition, the answers are typically going to be in integer format. So that's all we're gonna handle in this, but you can obviously make changes and support different operations as well as doubles and floats and thing like that. But we're gonna keep things pretty simple and say that when we evaluate an expression, we expect to get an integer back. So, let's start by creating the basic building blocks of an equation of a mathematical equation. In this case, we're gonna deal with numbers and we're gonna deal with some sort of operation. Like in this case, we're gonna deal with addition. But you can easily do subtraction, multiplication, division and different operations like that. So let's create kind of the basic idea here and that's gonna be of a number, and a number is going to be an expression. And within here, we want to represent the actual integer number that we're gonna be dealing with. Cuz we're gonna need to know what that is. So we are going to say, private let number be an integer. Okay, that's fine and then we are going need to initialize that, so we wanna be able to pass in that integer number. Okay, that's good and then we need to be able to evaluate. So basically, when we evaluate a number, the result of that is going to be the number itself. So, we're just going to return number. So, that's not a very complicated idea. Now the next thing that we wanna do is we want to represent as an expression, the operations that can be done on other expressions. So, we're gonna create another class called addition. This is also going to be an expression, but it's gonna look a little bit different than the number expression. But it will contain a couple of those. So, how do we do a mathematical equation between two numbers like addition? Well, we need two operands which means we need two numbers in this case and then we're going to do some sort of operation or evaluate against those. So, we're going to take in two different operands. We're gonna have a left operand, which is going to be an expression. We're also going to have a right operand, which again is going to be an expression and then we need to take these in. So we're gonna have a leftOp which is going to be an expression. We're going to have a rightOp, which is going to be an expression and then we will just initialize these. So, we have our leftOperand equal to leftOp and our rightOperand equal to rightOp to be equal to our rightOp. So now we have this, but now we still need to evaluate. So, let's go ahead and evaluate this. How do we evaluate addition when we have two operands? Well, we simply return the sum of those two or the sum of the evaluations of two other expression. So we're simply going to return the leftOperand.evaluate plus the rightOperand.evaluate. So now we're starting to talk about these different components, the operators and the operands in a mathematical expression all as individual expressions that we can combine and then evaluate all the different pieces. That's pretty good. So now what we need to do is we actually need to create the interpreter, the thing that's gonna drive the entire operation. So we're gonna create a class and this is going to be interpreter and you could call this calculator, if you want. I'm just gonna call it interpreter, because this is the actual part that's gonna help to do the interpretation and we're gonna have a single function and it's gonna be called evaluate. Now the basic idea here is that I want to take in a string expression that is going to be a post fix notation, addition problem or you can expand it to be other different types of operations. But the basic idea here is that I'm gonna take in a problem and it's going to be in string format. It is going to return an integer. So, this is the basic idea that we're going to be dealing with. Now you've probably done other exercises similar to this, if you've taken any sort of computer software courses where you learn how to evaluate mathematical expressions or operations using tokens and doing pushing and popping operations on stack. Now, I'm not going to do any sort of stacks. We're just going to use an array internally, but you can kind of treat it as a stack a little bit by using a couple different built-in functions on arrays. So what we're gonna do here is we're going to have an array, which would typically be the stack representation of tokens that we find within our problem. So these tokens are going to be a list of expressions, which is going to be empty to begin with. So, I don't have anything by default. I need to pass those things in to be evaluated. Then we're gonna say, let our token list is gonna be equal to. Now, I wanna break this thing apart. I wanna break the problem that comes in up into its individual pieces. So I would expect later on when I want to evaluate something, I can do something like in postfix notation, it would look like 4 4 + and that would then take those two operands and apply the operator to them and that's the postfix notation and then I could add to the end of it. I could say, 5 10 + and +. So what this is going to do is, it's going to evaluate 4 and 4 which will give us 8. And then it will evaluate 5 and 10 which is 15, and then there would still be a plus on the end. So then, it would evaluate these two things and ultimately give us an answer of 23. So, that's the basic idea of this postfix notation. So, what I wanna do is I wanna split on these spaces that are in here and then treat each and every one of these as an individual token. So the way that we do that within Swift is we can go into our problem and we can say, I want to get the components. But in order to do that, I'm actually going to have to import foundation. Cuz there's some nice built-in functions to help handle this. So now, I can break apart my components separated by a particular character and that character is going to be a space. So, that's how I'm gonna break things up into a token list and then I'm ultimately going to iterate over that token list. So I will say 4 and 4 each token in the token list, I can now start to interpret these things by converting this things into expressions and making them all evaluate against each other. So, the first thing that I need to do is I need to determine whether or not the current token that I'm looking at is an operator. If It's an operator, then I need to apply that logic. If it's not an operator, then I'm simply going to insert that number in this case into my tokens expression array up here. So, there's a couple different ways to do this. We could start with a switch statement, but what I'm gonna do now is I'm gonna keep things simple and you can obviously do some refactoring later on is I wanted to check to see if the token is equal to the plus symbol. Now obviously, this is not very extendable. Because then you're gonna have to keep adding onto it to handle subtraction, multiplication, division, whatever have you. So, you could use a K statement or you could use some other patterns to be able to generate those. That is fine, but I'm just trying to keep things relatively simple for right now. So if the token that we're looking at is the plus sign, then we need to get the last two operands that were pushed onto our stack or our token array and then evaluate those in the addition expression. So, let's get our leftOp. So we're gonna say, leftOp is gonna be equal to our tokens and I'm gonna retreat this as a stack even though it's an array. So, what I can do is I can remove the last one that was inserted. So I'm gonna remove at 0, so that will give me my left0p. Then I need to get my right0p which is going to do the same thing at this time, because the tokens that remove is going to remove that first one at the 0 index and return it as left0p. And then once that one's gone, now we're down to whatever was left after that. So now I can remove the next one at the beginning, which is gonna be our right operator. And then I can get my actual operator and set that equal to. And because at this point, I know that this is an addition operation. I can just go ahead and say that this is going to be an addition operation where the leftOp is going to be leftOp, rightOP is going to be rightOp like that. So now I have my operation, my addition operation. I can get the result. So the result is gonna be equal to my op.evaluate and then I can take the results of that, and I'm going to push it onto my stack. Or in this case, I'm simply going to insert it at an index and I need to insert this as a new expression. So in this case, I'm going to insert it as a number. Because that's my base expression here where number is going to be my result and I want to insert it at the top of the stack, so I'm gonna insert it at index 0. So now, we have added that new token onto the stack. Now, what do we do if it's not a plus operation or some sort of operator? Then we're simply going to get this new number. So we're gonna say, let num equal to number and we are going to use the int version of whatever token. Because when it first comes in, it's going to be a string. So, then I'm going to have to unwrap that operation as we convert that string to an integer and then I can stick that onto my stacks. So I'll say, token dot I want o insert.number at the top at index 0. So, that's the basic interpretation that's gonna be happening here as we loop through all these tokens. And then ultimately if the postfix notation is structured correctly, the last thing I should wind up with on my stack or in my tokens array is going to be the answer. So once I've done all of this work, I can say, let result be equal to tokens.remove at, whatever that last piece that's in there is and then I can simply return result.evaluate. So, that's our basic interpreter. Like I said, it's fairly simplistic. But it's gonna get the job done. So, how do we actually use this interpreter now to understand some language that I'm going to provide to it? Well, I'm simply going to create a new instance of my interpreter. So I'll say, let calculator be a new instance of my interpreter. And then I can simply say, let result be equal to my calculator and I want to evaluate a particular operation here and I want to mimic what I've done down here. So we're going to say, I want to evaluate 4 plus 4+5+10. So let's go ahead and paste this in here as a string, and what I would expect to get back in the result is 23. So now, you can see using the basic concept of the interpreter pattern where we break different parts of our language down into expressions that can all be evaluated in a common way. Now, we can create some sort of interpreter that's built to understand that language to parse the different pieces of that language apart and then evaluate everything together. So using that basic concept, we've built a very simple calculator that can now calculate the results of a basic addition problem of a string based postfix notation.