In the previous example we saw eject program that process what can be called an atomic object. Fraction Is something that need not be divided into, split into smaller atoms. So a fraction is a fraction is a fraction. However, we can also use object-oriented programming in order to manipulate and create objects which are collections. Of atoms so to speak. And the most generic collection of this is called list which is a very important obstruction in a both theoretical and applied computer science. So we spend a whole unit talking about this processing. So what is a list? A list essentially is the atom null which can be thought of as the empty set or it's an atom followed by a list. And we use this notation in order to represent lists so here's an example of several lists, the empty list and then five.Followed by the empty list then 3 followed by 5 followed by empty list and so on and so forth. It's kind of painful to write all these parentheses so instead we use abbreviated notation to describe lists. These are agreed upon notations but back in our mind we remember that we actually referred to creatures that each one of which consist of an atom followed by a list. So this is a highly recursive data structure. And the atoms can be anything, they can be integers as we have in the example here. They can be strings, they can be arrays, they can be other object, they can be lists in themselves and so on and so forth. Now, programmers tend to think about a list as using this metaphor here so once again this is a collection of atoms that are Linked together. That's why it's called a linked list sometime. And notice, however, that this whole thing is one object, right. It's one object, and in this example here, we have appointed variable v that points to this object. And the question, of course, is how do we create and manipulate Such collection objects. All right, so that's what we'll do in this unit. And, here is an obstruction or an API of a class designed to manipulate lists. So we see that we have a constructor for creating the list. And we use the terms car and [INAUDIBLE] for historical reasons to describe the atom, and the tail of the list, which is a list in its own right. And then, we have a print method that goes through the list and prints every one of the atoms. And we have a dispose method that recycles all the memory resources held by the list, which may be a gigantic pile of memory because this list may well contain a million such atoms. And so when we don't need this list anymore it makes sense to recycle it's resources. All right, now, obviously in reality, you may want to add more functionality to this abstraction because you know.. The whole beauty of the list is that you can insert atoms in the middle of the list as you please, or you can delete atoms from the middle or at the beginning or at the end. Or you can insert the list into a list, or it can pursue it from beginning to end, or from end to beginning. There are many different things that you may want to do with the list, but all of them don't belong to the [INAUDIBLE] course. So once again, this is not a course about list processing. Also there are excellent languages to do it, like [INAUDIBLE] and scheme, and yet in this course, we will do it in Jack. All right,hHere we have the list obstruction, and here we have some client code, that seeks to create the list 2, 3, 5, and manipulate it. I will show you the code without discussing it, because in the next slides, I'm going to spend a few minutes discussing every line that I now go to present. So in the beginning, we have our four lines of code that's together, create the list that we see in this diagram. Then we print the list and when we do it, we'll see the output 235 on the screen and finally, we dispose the list and return. So this is the client code. That demonstrates the three, some of the quintessential things that we want to do with the list which is creating it, processing it, in this case printing every item on the list and finally disposing it. And once again, there are many other thing that you may want to do but believe me, all of them are derivatives of these three operations. As we now go to explain. So let's start with create. Here's the client code, which is identical to what we had before. And we see that it includes three calls to the list constructor. Right so let us open the black box and see how we can write a list class and the first thing is usually to ask ourselves what kind of data does the list feature? Well a list consists of an atom or some piece of data and a list. So let's define to fields that represent exactly this information. A data field of type int, because we decided to create a linked list of integers. And the next item in the list a list. So we have a next pointer of type list to point at the tail. And he was our constructor called the new and the constructor asks, we do see it right? But the constructor ask the operating system to come up with enough memory to represent this two word block current or data in next. And then it returns the address of this block as all constructors do and that's it. Okay? So let us see how this code actually runs and this will give us a lot of insight on how to build a list in the, and later on represented in memory. So it all starts by creating a V pointer, so we get the variable contain something, because it implemented the VM language. You know that it will contain zero because if this is the local variable, all local variables are initialized to zero. So this variable does not know it yet, but it's going to be a pointer. Right now it contains the value zero. And then we invoke the list constructor. And the list constructor is going to come back with A block of memory that represents the number five and null. And notice that we use this terminator icon to describe null, and v is going to point to the base address of the object that was returned by the constructor. Essentially we say, v equals this, if you think about it, because this was the return value of the constructor. And then the next command that, if you think about it for a few seconds, will accomplish this thing. And by now the previous version of v is no longer relevant. And so, the next command will do exactly the same. And the previous value of V is irrelevant and that's the end of the story. Now, in closing that I'd like to point out but this list construction code can also be done using this somewhat shorter logic. And in general by the way this is just one way to construct a list. I could have written additional constructors that make construction much easier. For example I could have offer the constructor that takes an array, and create the list from the array It's all up to the person who designs the API and implements it later. Or you know, up to the person who hires us to develop this obstruction. All right, so we saw how to construct a list. The next thing I want to illustrate Is how we march through a list, and how we do it with something that's called sequential processing of a list. So, I will illustrate the sequential processing using a print method. And when we run this method, we expect to see the contents of the list on the screen as we saw before, and here is the body of the method. Once again, don't worry about the code. Don't even read it, because I'm going to simulate the code and everything will become clear during the simulation. So here is the client code that calls the print method. But it begins from building the lists so once the list is built we're going to have the subtraction that we saw before. And now the client called calls the print method on the v object. Now in object based programming people don't always know it but once you will write the compiler in the next module you will know it very well. When you call a method on an object you are implicitly passing the object as a parameter to this method. So when we do V.print we pass V to the print method and once the print method starts working it doesn't know what V is right. V is an identifier that exists outside the world of list. It is not defined in the list class. Instead we have a very special variable called this which stands for the current object. Now this is the point from which we are going to refer to the object that was passed with. So as we see with the diagram now the entry point of the list is this. And then the code that goes on to create another pointer of called current. And it sets current to this. So we get this situation here, two pointers referring to the head of the list. And now we enter this loop, in which we ask repetitively. Or we do, as long as kind is not man, we want to print the current app dorm and move forward. So, we print the valley of this atom which is two, then we print the space, and move current to the next head of the tail of the list. Once again we see that it's not null so we print 3 and then we move it forward. It is still not null so we print 5. We move it forward and finally current == null. In which case, we get out of the loop and we find the return, we return to the calling code. Once we return to the calling code, of course all of the stuff of the print method is going to be recycled so this, and current no longer exist and once again the. Is being reinstated and points to the list, as we had before. So I guess there are two comments which are in order here. First of all, notice that the print method is quite invasive, if you will. It goes into the list and it goes through every item along the list, and there's a lot of drama going on. And yet as far as the client is concerned, the client only has to print the list, and once this thing is done, the list comes back to the client, so to speak. It never left him, and he can go on and do whatever he wants with it. So, this, once again, is this beauty of the abstraction versus the implementation interplay. That structure is trivial. The implementation is not trivial at all but the client doesn't care. And the second comment I like to make is that the printing here is not terribly important. The printing is just a sort of a placeholder to describe methods that, once again, grow through every item in at least and do something to all these items. Though I could have written a very similar that for instance goes through the list and increases every value by 10% or something like this. So this is sort of an example of numerous processing algorithm. Not algorithms, methods that could be very useful in the context of a list. Alright, the last thing that I want to illustrate about list is what I call the recursive access, and we'll do it using the dispose method as an example. And the purpose of dispose is to take this list and recycle everyone of Of its items. Here is the code that does it. No need to read the code. We will do it in a minute. I just want to point out that it's a recursive method, because the dispose method basically disposes the tail of the current list. And the client, as usual, creates the list, gets this obstruction, and then the client says, dispose. Once again, when we say dispose, control moves to the dispose method, the dispose method does not know what v is, and instead, now the variable, these points at the object that was passed to dispose. And next we see that we have this if expression that says as long as next is not null, do something. Now what is next? Next is the field of the current object, right. Well, next of the current object is not null so we have to do dispose. But the dispose now is applied to the tail of the list which is represented by next. So now this when we get into this level of recursion this now points at the tail of the list. Once again, it's not null so once again we call ourselves, we call the spouse now this point at the last item in the list and in deed now next is null. And because next is null we are going to move to the base case of the recursion, and we find here our acquaintance diAlloc. We've seen it before and diAlloc knows how to take an address in memory, and the recycle the block which begins in this address. The memory block which was previously assigned to represent the current object. So once deAlloc end it's worked. This item is going to be recycled and we are going to returned. Now we are going to returned precisely to the position were we have to do another deAlloc. So We recycle this part of the list also and we do in return, we recycle that item and we do a return. And once we do this return, we get completely out of this recursive method and what use to be called this goes back to be named v. But now V points to nothing because we basically disposed everything in this list so the list is norm all. So this is been an example of recursive processing of list. It is very natural to process this using recursion because the list is a recursive Data structure in its own right. And here we have sort of a really clean example of tailor recursion, literally speaking. And yet, don't forget that recursion is very inefficient operation and if you have tried to do that with the. With the big list you may have gotten stack overflow. So, there are better ways to dispose, not better but you know more practical ways to dispose a list, but this one once again illustrates a nice way to do it using using recursion. All right, so to recap. We showed how to build a list, how to process it sequentially, how to process it recursively. And the last thing I want to say which is very important in this course, is to once again open the hood and see how this list is stored in memory. The client view or the high level view of the list is this and within the memory it is stored using this example here. It starts with say V. Is that a V? And v contains the address 5267, if we look at this address we'll find the value of 2 in a point to 14017. If we go there we find the number 3, and a pointer to 3108, if we go there we find 5 and null. So that's how the list is stored in memory. We don't have control over these addresses, they are completely arbitrary. I made them up and in fact that's what happens in practice when you say new, the constructor is going to cause this object to be created somewhere in memory. We don't care where. All we want is the pointer to the base address. And therefore practically the list is going to be dispersed all over the memory, and that's perfectly okay because the memory is direct access and that's fine. So who makes this magic happens? Obviously, there's some magician here that knows how to take this obstruction and map it on the sequential ram and here's a secret. If you are content to think about programming from a high level perspective only, then the simple answer is the constructed takes care of it somehow. But, if you are interested to go below the surface as obviously we do in this course, then, you should know that when the compiler translates the constructor. The constructor code that the high level program I wrote. The compiler is going to inject into the code stream, calls to the operating system that in these calls are going to invoke routines that know to find available memory for the new object, and assign it to this object. And in the next modules of this course when we build the compiler and the operating system. You will be very pleased to see how all of these capabilities going to be implemented in a In a very elegant and effective way. All right, so the next thing that we'll do in this module is describe the Jack language specification. Up until now, we just showed example of Jack programming. Now, we'll define the language officially. And you'll be able to start using it and right programs in Jack.
