Implementing a Simple Interpreter for Arithmetic and Let Expressions in OCaml

[00:00:02][music] Welcome everyone to this lecture series about compilers. And today we're going to learn about how to write an interpreter. And this interpreter will be fairly simple. It's going to be able to handle arithmetic expressions and also let bindings which means that we're going to learn about the concept of environments.

[00:00:25]This whole series is about okamel examples. You can find them on GitHub if you go under David Broman and then you go to UKamel examples and here you can see a number of examples. So we are now going to construct what is you can find here interpret arithlet which is an extension of this one parser man a. So you can find the video here for this this uh other project where we are lexing and parsing and creating an abstract syntax tree and we'll use this project as the basis for then interpreting. This is an example of a a program that we'll be able to execute today. We have some let expressions with some arithmetic expressions and and we have a let another let and then we're returning the value. So right now if you run this uh program with just using this parsing and lexing part and compile it like this you do make and then you pipe in the example. You'll see here that we just pretty print this this lit expression. So we pretty print this program. But what if we actually want to run this program and running a program in an interpreter means that we evaluating it and we can do that by creating a file eval. ML and there we create a function. Let's call that eval.

[00:01:50]This will be a function that will pattern match on uh the abstract syntax tree. So you know camel we can just write function and then the pattern and what kind of pattern should we have?

[00:02:03]Well, we need to have that from the a and the a in this project is actually located in what's called a. So we open that. We can take a look at that file here. You see the expression and one of the first expressions is an int and where binary operators, unit operators, let expressions and variables. So let's just write it for an integer first. And we have some value and in interpreter should just return the integer directly then like this.

[00:02:33]If anything else happens, we just fail and write to-do. Okay, so we can run this program. So we go to the main file and here we see that we just print pretty printed today. But let's also evaluate it first. So I'm duplicating a function and calling evil here. So that we first pretty print the a and then print the resulting uh evaluated term.

[00:03:01]some separation here. Get it a little bit nicer. Let's see if we go to the test file again now and then clear this and just write say five. We expect to run this program and then pretty print it. And that's what we done. So here you see that we pretty first the aued and pretty print the value that is the resulting value. Well, since it was just five, it's the same thing. So we're not actually computing anything. We need to add something more interesting in to the actually interpreter and we can do that by adding the binary operators. Let's look at the a here. Here you see that the binary operator is defined as as binary op bin op and then two expressions and the actual binary operators are this add subtract multiplication division. Let's go to the evil and then we start to write a binary operator. So let E been up like this and then we said saw that we have an operation and two. But how do we evaluate E1? What which function should we use? Well, it's actually the function itself. So we have the eval function, this function. So we can write like eval E1 like this. Then we will evaluate E1.

[00:04:19]But since this would be a recursive function, we need to mark this as a recursive function. We want to then pattern match on the result from this.

[00:04:27]So what we do here is we write match eval e1 and then eval e2 here because then we can directly get a pattern matching from the evaluation result and note how we made this a tpple so we can then match on the resulting directly.

[00:04:44]Note also that we add this parenthesis here otherwise we'll get very strange pattern matching error since we are now nesting pattern matching. What will the binary operate evaluate into? Well the only value we have in this program. so far is actually an integer. So it will be e int will be the resulting value.

[00:05:02]Say that we are evaluating the first integer and then we evaluate the other one into x2 and then we have the actual operator. Okay, so we should pattern match and getting an actual operator.

[00:05:16]But what should we do with it? Well, we could copy this one and then have different operators every time here. But there maybe a nicer way here since we have separated binary operators is to just provide all the binary operators into one listing here. If we go back to the a here take a copy of these ones. So what we can write here is uh let let's call that bop equals a function bop here. Bop add if we're matching on bop add we get a plus. So note how we in No camel now returns the function for plus.

[00:05:52]It was an infix function but we get a prefix function with two arguments for plus like this for multiplication. And here we'll see something special that we cannot do like this because it's a comment in a camel. So we need to have some space here. And then we do the same thing for div. Okay. So now we can then just call bop here and we provide the actual operand. We have a function for the actual operation. Since this is the function for the actual operation like plus, we can write just x1 and x2. We are actually now getting an integer. But since we have an interpreter, we need to wrap it again into the a node. So we have an e int here. If we're not getting an integer, something is wrong. And what we can do then is just to pad a match and say that we are failing. Then let's write just binary operands need to be integers.

[00:06:51]Let's see just if it compiles. It did not. Oh, I forgot I had too much here.

[00:07:00]So now we evaluate and run int five. But let's create a more interesting program.

[00:07:06]Let's see if we say 5 + 2. What happens then? Well, we got the operand here.

[00:07:12]five and two. This is the a and this is the resulting value. And now we can actually write arbitrary complex expression here or put it like this.

[00:07:26]Let's look here we have unary operands.

[00:07:30]So let's continue with that and add that to our interpreter. Here we go. Um so we can then just write e op e we have the an expression and right now if we look at the a here we have just unary minus so we just have one so we actually just p match on that one match eal with well we have an integer e int minus x for now we can actually just ignore and then say fail unary operand needs to be an integer that's the uni operand let's see if that compiles if we run the test again can I actually have a unopan there yes and a uni unary it becomes plus again all right what's the next thing to implement here in our interpreter we have a complete arithmetic interpreter now which is pretty neat but we also want to have let expression. If we go to the a here, we can see that we have let and the let expression start with the let and then the variable and then expression that we will have in and then the rest of the expression. So let's write out a small program first so we see what we are trying to do. Let x equals to can move this one and just in and then x. So we bind this value to this name and then provide it later on. But it should also be possible to do like this. So it can be used many times. So how do we do this? Well, the trick is called to have an environment. So when we are evaluating, we'll have an environment that is kind of threaded through the whole recursive function. And to do that, you had to extend the evaluator a little bit. So we have the eval here but we need to add an environment and we can just write n like here. So this environment here will have a type it will be a tupil that maps a string to a value and the value is an expression and this is a list. So this environment here is actually a list of such tupils.

[00:09:55]So this is a so-called associative list and you can use binary search trees and other data structures and that can be more efficient if you have very very big environments but but actually for small environments just having an associative list is quite efficient. Okay so we don't have to provide a type it will be inferred automatically. Let's look here for example here we are calling eval three times we also need to provide an environment here and which environment should we provide? Well, we can just provide the environment itself. So the environment that we just got. So we just now kind of send passing the environment through the whole chain in the main file. We should also provide the environment and when we start a program we just have an empty environment. on the empty list we should add the let and let us remind us what the a looks like. So we have a let that is the then we have a string that is the name and that what what we are binding the x string to and then in that's the rest of the let right so we just write e let x and then we can just write e1 e2 what should we do with this one well we should always first evaluate this e1 if we look at the test again these e1 one corresponds to this part of the let. So we want to evaluate that first before we substitute and this is a typical way you do when if you have a call by value semantics. So we want to evaluate that one. So we just write let and we get the value back and then we write eval e1. So now we have evaluated e1 into a value v. Now we have e2. So that's the rest of the program. So what we want to do there is also is to evaluate E2 but we need to have an environment here and the question is what is the environment now when we are evaluating E2 well we need to provide the new binding of the let so we have X the name here and we have the new value there so what we have to do is to stick on top of this environment so we do a cons so we write X comma V. So now we're coning this mapping of X that is then mapped to V and put that on the environment and then we need to put this whole thing into parenthesis as well. So this would be the new environment that we then evaluate E2. Will it work now? Well, we have implemented the let but we have a problem. We have one term that is left.

[00:12:42]Let's look at that as again. What we haven't implement is the variable. How do we evaluate that?

[00:12:50]Well, it's pretty simple. We just have e var and then x. That's the variable. And now we need to find what value has this variable. And where can we find it?

[00:13:03]Well, we have an environment here. This is the environment. So, we just need to look up the value for that particular variable. And here you can just use asoc, which stands for associative list.

[00:13:17]It basically finds the value in this environment. So we say that we want to find X in environment and then it returns the value. Let's see if it works. It kind of worked, right? We got a value, but we also got some complaints saying we have this redundant to-do.

[00:13:38]Yes, because we have now implemented all the constructors 1, two, three, four, five. And if we go to the a we see that we have five constructors. We have implemented all of them. And by the very nice exhaust check no camel this is that this is redundant because we cannot get to that case anymore. So let's run it again. And now we just get the result.

[00:14:03]We see the let the whole a and the then the result and we see that 2 * 10 + 5 is 25. But as I said here we can we can provide the names here more than once.

[00:14:18]We can write like this. So now this x is duplicated down there and you can run that and it gets 50. And then we can just write another here. Let y equals to something else. So 66 - 3 divided by 3 in and then do a y there instead and we get the computation. So we got have created a small calculator.

[00:14:42]All right, that is actually it. So now we have created an interpreter that is interpreting an expression arithmetic expression that can handle parenthesis and all other arithmetic expression and we also showed how to create an environment where we can bind names to values with let expressions. So that's all for me for today and in the upcoming video I will explain how to extend this with the lambda calculus. So you can have anonymous functions and then give them names using let bindings and to be able to do that correctly you need to use closures. But that's for the next video. So if you're interested in that take a look at that. Thank you.

[00:15:28]If you like this video, please subscribe and add a comment and tell me more about what you want to learn about compilers and programming languages.