Hi everyone. In this lecture, we're going to finally talk about mutation, data structures that can change. That's called mutable data structures. We're going to finally discuss global variables, the concept that you've been waiting so long. Chapter 11, boxes, will explain the details of boxing in mutation. Please read the chapter. Functional programs. The programs that we've been discussing so far are functional. They are implemented in purely functional style. What does that mean? A function produces the same result every time for the same argument. For a given function f, whenever we pass the same arguments, the results are the same. That's what we mean by purely functional. This is very pretty and mathematical and easy to reasonable. But the problem is in real-world, real-world programming languages do not behave in that way. They are not functional. Why? Because when we use functional style, we make values a lot here and there, everywhere, and pass the values and get the results as values. We make many copies of same values in memory. Memory usage is not really efficient, but that's going to lessen our burden about thinking the flows of values in the program. If we use a different style, in productive style with mutation, then we can use memory really efficiently because we use smaller amount of memory by reusing that place. Instead of making copies, we just use a small amount of memory and change the values in some specific location of the memory. It's easy if you have small amount of memory, but it's difficult to reason about its behavior. Let's see what I mean. Non-functional procedures are these examples. Let's see. The first example, it has its function g, which takes no arguments and produces a function whose type is Int to Int. In the function body, we make a local variable that can change with the initial value is zero. The result of this function call is going to be a function expression. It returns a cloV, which takes an integer and adds that argument to this variable b. Meaning that the result of this g function call is going to be a function which is not functional. Because whenever we call this function at function with the same arguments, say eight, the result is going to be different because b keeps changing. It's not functional. One more time. This is may be a bit more familiar to you. Finally, we have a global variable counter whose initial value is zero. In this function h, it takes an integer and returns another integer for all the value of counter, which is outside of this function, a normal variable. Whenever we call this function h with the same argument, say 42, the result is going to be different because it's depending on the value of counter, which is defined outside of this function. Not only this function h, some other function, x, y, z may use this counter. Whenever I call this function h, I need to check the value of a counter. It's not trivial to reasonable the behavior of programs using this mutation. When you use mutation, you better know what you're doing. This is the language for this lecture and the next lecture. BFAE, FAE with boxes. FAE had two values, numV and cloV. Now we have the third value box of v. In this language, we introduce four language constructs, three for boxes and another for sequencing. Let's see. I will explain that one by one. Yes. The first language construct is to introduce this new concept box. The next two expressions are using boxes. The first term, construct a box, B-O-X, that's the keyword to introduce a box open, close the initial expression. When we interpret this expression, we're going to make our box whose value is going to be this value, the value of this expression v. That's the first new expression. The second expression is to change the value in the box. When we interpret the first step expression it should denote some box. When we interpret this second expression, it's going to give us some other value, three prime. When we interpret this expression e1.set, open e to close then we are going to change the value of this box. It's going to be now v prime that's set. Finally, when we want to read the value in the box, it's going to be get. When we interpret this first sub expression, again, it should give us some box which contains a value and we can get the value inside the box by expr dot that get, then we're going to get v prime. All these are for what? Boxing. Introducing box, changing the value in the box, get the value in the box. Nothing difficult. Why we are discussing this mutation, we are introducing another expression which is sequencing. Sequencing meaning from here to there. Semicolon, meaning that interpret this first sub-expression get rid of the value interpret the second sub-expression. What? Open e_ 1 semicolon e_ 2 close, meaning that evaluate the first sub-expression, get rid of the value, evaluate the second subexpression and the value of this expression is the value of the whole expression. It's a sequencing. Why do we introduce this expression as well? Because when we have this mutation, there are some things happen in sequence. We need to make a box and we do like to change the value inside the box and read it there or what sequencing. We are going to see how we are using sequencing with mutation. What's that? This is an example of this BFA language. Here we have e_ 1 semicolon e_ 2, meaning evaluate e_ 1 first, get rid of the value, evaluate the second subexpression. The first subexpression says I am introducing a new name p because the value is this box containing the integer value zero. Again, even though these BFAE does not have fair expression in the example, we still use that. How? Because we can simulate this by using function expression and function call. Remember, yeah. After introducing this box b, we evaluate the second sub-expression, which is so yet another sequencing. There first, we change the value in this box to 10. Finally, we get the value in the box. Then what's the value in the box? Yeah, 10. This is the language that we are going to discuss. Now that we have the third value, we introduced another value, box of V. One more time, in this new language, BFAE, we have three values NumV for numbers, CloV for functions, Box of V for new box. The Box of V should contain some value and that can be, change it. Nothing special. Now that we have this new value, we can implement the interpreter in one slide. Then you can go home. Really? Not really. Let's see. In this interp function, this is going to be the usual interp function. It takes an expression and an environment produces a value. For NewBox, I know, it's an introduction of a new value box of V. I'm going to make a box of V whose initial value is going to be the value of this expression. So far so good. When you want to change the value in a box, it's going to be SetBox. Equals to what? E_1.set(e_2). Then this is going to be the first of expression box expression. This is going to be the second subexpression new value expression. Then what are you going to do? Interpret this first of expression, then that should be Box V. That's why we do like to change the value inside the box. If it's not BoxV meaning down V or cove v, it's an error. If it's BoxV that's good. Hey, I know you have this Box of V value and I'm going to change the value to the value of the second sub expression. Interpret the second sub expression get its value, put that into the box and return the value. Very simple. Finally. Do you want to read the value in a box? Then interpret that expression. Again that should be Box of V. If it's known V or closer v it's going to be an error. If it's a box of V get the value in the box. We're done. We've done implementing the interpreter of this new language PFAE. Is that that simple. Yeah, but the problem is, we didn't learn anything about boxes. When we interpret box, when we implement this new concept box we used boxes in Scala. When we interpret NewBox, SetBox and OpenBox, we used mutation in Scala, which is cheating. Remember when we implement recursion, we did not use recursion in Scala to see how recursion works in the language. Instead we used function expressions and function call to make NK red or we use mutation to change the value. We didn't use recursion to implement recursion back then so here we do not want to use mutation in Scala to implement mutation in our own language. How come. Is that possible? Yeah, so let's make our own memory. Let's assume that this is your memory in your computer and when you make a box containing seven and give it a value of b, then the memory is going to change in this way, meaning that in some address, the value is going to be seven and let's call that b. This is our memory. Yeah, that's simple. Then when we want to change the value of b, yeah this was b. Remember b in the box we used to have value seven, and now we'd like to change the value in the box b to 10. You'd like to change that to 10. Then what is it going to look like after evaluating that expression. Yeah, as you can guess, it's going to be like this. So far, so good. Then let's make that memory in our interpreter like this. What's that? Yeah, Let's read it. We represent memory with a store. A store is a mapping from addresses to values. One more time. A store is a map from addresses to values. It mapped addresses to values in that addresses. What is an address? It is a simple integer. [Korean] What is a store? [Korean] It's memory. [Korean] What's memory? [Korean] It's a sequence of cells.
[Korean] Each cell is represented by an address.
[Korean] So memory maps addresses to values. Right? [Korean] And an address is an integer. How does that work? Look at this. This is our memory. It's tiny but useful. As usual, we are computer scientists, so address starts from zero, it's going to be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13. At address 13, we have value NumV 10. This is our memory. We can represent this memory picture to this map. They're just the same. Then we can use this store to implement PFA. What does that mean? We're going to make another value BoxV, but differently from that one slide implementation. [Korean] We implemented an interpreter for BFAE [Korean] in one slide before.
[Korean] How could we do it so quickly?
[Korean] We used mutation in Scala.
[Korean] But that's bad.
[Korean] Why?
[Korean] Because we used mutation to implement mutation.
[Korean] We used mutation of Scala
[Korean] to implement mutation of BFAE. In that one slide implementation, we used scalar mutation to implement PFA mutation which didn't teach us anything. Now, this time, we're not going to use mutation in scalar but we're going to make our own store by using new kinds of value BoxV. Just like in that one slide implementation, we introduced BoxV. In addition to NumV and CloV, we have BoxV. The difference is, this time we don't use mutation. BoxV just contains an address. If you remember, in that one slide implementation version, we used BoxV with a variable filled BoxV. We just change it the value right there by using mutation in scalar, by using box in scalar. But in this new implementation, we're not going to use mutation in scalar, but we're going to use our own store, our own memory. BoxV now does not contain a variable, but just contain an address. We change it, the type of interpreter. Previously, the interpreter took an expression and environment and produced it a value. [Korean] An interpreter took an expression and [Korean] an environment and produced a value. Now, we have extra argument and extra result. When we interpret an expression under this given environment, we need to use store. Not only that, when we interpret an expression under this given environment and keywords store, we produce a value and one other store. Wow, that's what we mean by implementing boxes without stage. Because instead of using state in the scalar, we use our own store. Then we pass our store to the next interpretation. We will see what that means in the next lecture. Stay tuned. Until then, let's look at this quiz. Consider the following code. We saw this before. This is a sequencing expression. Sequencing expression meaning that interpret this expression, get rid of its value and interpret this expression. Interpret the first expression. It constructs up new BoxV with this value zero initially, and let's call that b. We make a box containing zero and we're going to call that b. We'd like to change the value inside this box b to 10. This is yet another sequencing and then get the value inside the box. There was the value. Think about it. Which of the following is the result of that code? After constructing this box, we change the value inside the box to 10 and then get the value in there. Then what's going to be as a result? Yes, that's going to be 10. Thank you.
