[MUSIC] So, in this segment let's dive right in and see how in Racket we don't need datatype bindings and how we do analogous things in a dynamically typed language like Racket. So, we don't need anything like datatype bindings, depending what you want to do there are different idioms that we can use. First, if you just need to mix values of different types like having a list that might have some numbers in it and some strings in it, we can just do that. And Racket's built-in primitives, things like number?, and string?, will let us figure out what kind of values we have. There's no directly corresponding thing in ML. And then I want to show you for how more interesting recursive data structures, we could code up what we need, just using cons cells and lists. So this is connecting things we've already seen to a new setting. So I'm going to show you some ML code, for the purpose of contrast. For example, suppose in ML, you wanted a list that could hold ints or strings, and you wanted some computation, such as summing up everything in that list, where numbers are numbers and for the strings we take their length. Well, you cannot do that in ML, we know that in ML, every list has values that have exactly one type. But datatype bindings let us get around this by introducing a new type like into our strings, like you see on this slide here, that has two constructors, one for holding an int and one for holding a string. And then you can write exactly the function that I described and give it a type like int or string list to int. So by introducing a new type we can represent the sort of data we want. In Racket we can just do this naturally, in some sense every piece of data in Racket already has a tag like this I and this S tag, it's built into the language. So without defining any of our own datatypes, we can just mix numbers and strings or anything else we want and write the code that we need. So, I'm going to show you that. Here is this function funny-sum, it takes in the list xs, and use this cond, which we've learned about. The list empty, return 0, if it's a number, then add together the car, with calling funny-sum on the cdr. And then finally if it's a string, then add the length of the string. There's the string-length function, provided in the standard library, with calling funny-sum on the cdr. Now I don't have an else clause here, which is usually better style in Racket, but this is a closer connection, a more direct translation if you will, to the ML code we see here on this slide. So that's our first approach. Now let's talk about more interesting datatypes. One of the more interesting things we did in ML is we defined a datatype like you see here for trees of arithmetic expressions. And then we wrote a fun eval_exp that took in an expression and returned an int. So here I actually want to show you this ML code because I'm going to change how we do it. So here's the code I just showed you except I'm calling the fun eval_exp_old because I'm about to show you a different version. And this code takes an x and returns in int. So, for example here at the bottom of the file, I have this test expression where I build up the tree Multiply, of Negate, of Add, of Constant 2 and 2 and Constant of 7. And if I call eval_exp_old with that test expression it will evaluate to negative 28, okay. So that's eval_exp_old. Now, what I want to do is I wanted to find a different version that has type exp -> exp. Now, this is going to be a little annoying. Let me delete the comment here so we can see the code more easily. But the reason why I'm doing this is because when we get into bigger languages, things we want to evaluate that have more possibly results than always returning and int, this is what you need to do and it's a very natural approach. So the idea here is that if I call eval_exp_new with the same expression, I'm going to get const of negative 28, right? That's of type x, arrow, x. And so I'm always going to return a possible result expression, and in this simple case it will always be a constant. And that's why it will be more cumbersome, but this is the programming pattern we will need when the result might not just be a number but it could also be a pair or a function or a string or a boolean or whatever. So here's how I am going to do this, first I am going to have a little helper function that just says, take in an expression, if it's a constant get the underlying integer out, otherwise raise an exception. Now how would I write my interpreter? I take in an expression, if it's already a constant then return the entire expression. Not the thing underneath, the entire expression. That's my base case. If it's a negation, then what I need to do is recursively evaluate the sub expression e2. Then, I need to get the int out because negation expects there to be an integer result underneath. Then I need to negate it and then remember, I need to return an expression, not a number, so I call the const constructor to make a new one, okay? The Add works similarly. Call eval_exp_new_e1, eval_exp_new_e2. Those both return exps. So get the numbers out, call get_int on each of them. Add them together and then call the Const constructor to put it back together. It takes a little getting used to, but it's actually extremely elegant. Make recursive calls, get the underlying data, perform some operation on it, make an expression for your result. And Multiply is exactly like Add, just with multiplication, okay? So let's go back to the slides, summarize what we did. From now on, all of our eval something sort of functions are going to have a type like exp arrow exp, I've explained why. And what we did is we made our base case return the entire expression like Const 17 and then recursive cases. After doing the recursive call to get a result, we made sure we had a Const. We got the integer out from underneath, and then we made a new Const to return the result. Again, that will be more useful to us when we don't always return constant integers, but we have multiple ways to return these. So now what we're going to do, is take that new approach and code it up in Racket. And we're just going to use lists to do it, and we'll see that you can actually do this, and it's not too painful. So I have it down here, so the idea is we're going to implement the same kind of interpreter I adjusted with eval_exp_new. I don't have datatype bindings so what I'm going to do is I'm going to find my own helper function to make things that will act like constant, negation, additions, and multiplies. What I'm going to do is just use list where the first element of the list says what kind of list it is, all right. So here's a function Const, just a plain old Racket function, takes in an argument i and returns a list with two elements, the single Const and then i. For now just think of symbols as strings. I'll briefly mention at the end of this segment that they're not quite strings. But just think of them as strings. The Negate function will make a two element list with the Negate symbol. Just quote Negate and then the argument. Add takes two arguments, e1, e2, returns a three element list with Add e1, e2 and similarly Multiply. So these are just things that make lists that hold arguments where the first thing describes what we need. Now we don't just need to make these things, we need to be able to test what kind of thing we have. So how about some helper functions for that? How would I test, do I have one of those Const things I made with this first function up here? Well, I would just take something, assume it's a list, ask does its car equal, this is the built-in eq?, function. You can use it to compare symbols. Does the first thing in the list equal Const? If so, I have a constant. If not presumably I have one of the other kinds of things. Similarly, this Negate function will ask is the car Negate? The Add function will ask is the car Add, and the Multiply function will ask if the car is Multiply. What I'm doing here is defining my own functions, to see what kind of thing I have, and extract the pieces. So I'm not defining pattern matching, we're not going to use pattern matching in Racket. But this will be enough information, enough helper functions, for me to easily write my interpreter, my eval_exp function. So now here are some functions that extract the pieces. If you knew you had a Const and you wanted the underlying integer, you could call this Const-int function, which will just return the (car (cdr e)), the second element of the list. Because remember, the first element will be the symbol Const. So then the second element will be that number i. Then we can have Negate that extracts the underlying thing, that's also the car of the cdr. To get the first element of an Add that is also the car of the cdr, so we could just anywhere we want right, car of the cdr because it's just lists. But these helper functions will make it much easier to read and much easier to understand what we're doing. To get the second thing out of an Add, well, we need the car of the cdr of the cdr. Similarly for Multiply second element of the list to get the first sub expression, third element of the list to get the second sub expression because the first thing should be the symbol Multiply. It'll be more robust to recheck that we have the right kind of thing here. We're going to trust ourselves as the programmer to have used these functions, like Const and Negate to make sure we have the right thing. And then these helper functions to get the right thing. By the way if you find yourself doing car of cdr of cdr a lot, there are built-in functions for this. I'll point you to the Racket user's guide to learn how to use those. And now we've built up to actually defining our interpreter. So it's just a big Const. Eval x takes in one argument, this cond corresponds to our pattern matching in ML. If it's a constant, return the entire expression, because remember this is our new way of doing these things. If it is a Negate, get the piece out using the Negate-e helper function we wrote. Call eval-exp on that, get the underlying integer out, negate it using the minus operator, call the Const function we defined to return the new constant. That's the elegant pattern we saw. Add and Multiply work similarly. If you have an Add expression then let's get the first sub expression out, call eval-exp, get the integer underneath that Const, and we're assuming here that we're getting a Const back, and then let's let that be v1. Do similarly to get v2. Then add together v1 and v2, call the const helper function and that's our result. Multiply works exactly the same way, multiplying instead of adding, okay? So, what have we done here? We have defined in Racket using nothing but lists and symbols and, you know, car and cdr, our own helper functions that act like constructors, making expressions, testing variance like cons question marks, and extracting data like cons dash end. Having all these helper functions is just better style than using car, and cdr, and cons everywhere, but we are essentially just using car, and cdr, and cons. The result is a function, eval-exp, it has the same recursive structure as in the ML code, just without pattern matching. But because we're in a dynamically typed language with no type system, there's no notion anywhere of what an expression is. Except in comments, our own head, and documentation. The fact that there are four kinds of expressions, consts, negations, additions, and multiplies, is something that we are just keeping track of. There's no datatype binding to say that those are all the possibilities. Now the code I showed you in this video does not have a lot of error-checking. If you try to get something out of an addition expression but it's actually a multiply expression, it will just silently work. That's something we will fix in the next segment. But in terms of coding up what we need to get the job done, this has achieved what we need, and using only features in Racket that we already saw. Now there's one exception to that. I did sneak in symbols, I could've used strings instead. So just optionally, the way you write a symbol in Racket as I did in this segment is you just write quote. And then any sequence of characters you want, basically. And that is a symbol, whereas strings are in double quotes. So what's the difference between a string and a symbol? Honestly, not much, although they are different. The key thing you can do with symbols is you can use eq?, to compare them to each other. Are these the same symbol? 'foo is the same as 'foo, 'foo is different than 'bar. And that's a very fast comparison, where a string comparison is slower because it has to actually look at all the characters. But we could've done it with strings. The more high level point is how to code up our own notion of data types using nothing but lists and helper functions.
