[Section 4 - More Comfortable] [Rob Bowden - Harvard University] [This is CS50. - CS50.TV] We have a quiz tomorrow, in case you guys didn't know that. It's basically on everything you could have seen in class or should have seen in class. That includes pointers, even though they're a very recent topic. You should at least understand the high levels of them. Anything that was gone over in class you should understand for the quiz. So if you have questions on them, you can ask them now. But this is going to be a very student-led session where you guys ask questions, so hopefully people have questions. Does anyone have questions? Yes. >>[student] Can you go over pointers again? I'll go over pointers. All of your variables necessarily live in memory, but usually you don't worry about that and you just say x + 2 and y + 3 and the compiler will figure out where the things are living for you. Once you're dealing with pointers, now you're explicitly using those memory addresses. So a single variable will only ever live at a single address at any given time. If we want to declare a pointer, what is the type going to look like? 

I want to declare a pointer p. What does the type look like? [student] int *p. >>Yeah. So int *p. And how do I make it point to x? >>[student] Ampersand. [Bowden] So ampersand is literally called the address of operator. So when I say &x it's getting the memory address of the variable x. So now I have the pointer p, and anywhere in my code I can use *p or I could use x and it will be the exact same thing. (*p). What is this doing? What does that star mean? [student] It means a value at that point. >>Yeah. So if we look at it, it can be very useful to draw out the diagrams where this is a little box of memory for x, which happens to have the value 4, then we have a little box of memory for p, and so p points to x, so we draw an arrow from p to x. So when we say *p we're saying go to the box that is p. Star is follow the arrow and then do whatever you want with that box right there. So I can say *p = 7; and that will go to the box that is x and change that to 7. Or I could say int z = *p * 2; That's confusing because it's star, star. The one star is dereferencing p, the other star is multiplying by 2. Notice I could have just as well replaced the *p with x. You can use them in the same way. And then later on I can have p point to a completely new thing. I can just say p = &z; So now p no longer points to x; it points to z. And any time I do *p it's the same as doing z. So the useful thing about this is once we start getting into functions. 

It's kind of useless to declare a pointer that points to something  and then you're just dereferencing it  when you could have used the original variable to begin with. But when you get into functions--so let's say we have some function, int foo, that takes a pointer and just does *p = 6; Like we saw before with swap, you can't do an effective swap and a separate function by just passing integers because everything in C is always passing by value. Even when you're passing pointers you're passing by value. It just so happens that those values are memory addresses. So when I say foo(p); I'm passing the pointer into the function foo and then foo is doing *p = 6; So inside of that function, *p is still equivalent to x, but I can't use x inside of that function because it's not scoped within that function. So *p = 6 is the only way I can access a local variable from another function. Or, well, pointers are the only way I can access a local variable from another function. [student] Let's say you wanted to return a pointer. How exactly do you do that? [Bowden] Return a pointer as in something like int y = 3; return &y? >>[student] Yeah. [Bowden] Okay. You should never do this. This is bad. I think I saw in these lecture slides you started seeing this whole diagram of memory where up here you've got memory address 0  and down here you have memory address 4 gigs or 2 to the 32. So then you've got some stuff and some stuff and then you have your stack and you've got your heap, which you just started learning about, growing up. [student] Isn't the heap above the stack? 

Yeah. The heap is on top, isn't it? >>[student] Well, he put 0 on top. [student] Oh, he put 0 on top. >>[student] Oh, okay. Disclaimer: Anywhere with CS50 you're going to see it this way. >>[student] Okay. It's just that when you're first seeing stacks, like when you think of a stack you think of stacking things on top of one another. So we tend to flip this around so the stack is growing up like a stack normally would instead of the stack hanging down. >>[student] Don't heaps technically grow up too, though? It depends on what you mean by grow up. The stack and heap always grow in opposite directions. A stack is always growing up in the sense that it's growing up  towards higher memory addresses, and the heap is growing down in that it's growing towards lower memory addresses. So the top is 0 and the bottom is high memory addresses. They're both growing, just in opposing directions. [student] I just meant that because you said you put stack on the bottom because it seems more intuitive because for the stack to start at the top of a heap, heap's on top of itself too, so that's-- >>Yeah. You also think of the heap as growing up and larger, but the stack more so. So the stack is the one that we kind of want to show growing up. But everywhere you look otherwise is going to show address 0 at the top and the highest memory address at the bottom, so this is your usual view of memory. 

Do you have a question? [student] Can you tell us more about the heap? Yeah. I'll get to that in a second. First, going back to why returning &y is a bad thing, on the stack you have a bunch of stack frames which represent all of the functions which have been called. So ignoring previous things, the top of your stack is always going to be the main function since that's the first function that's being called. And then when you call another function, the stack is going to grow down. So if I call some function, foo, and it gets its own stack frame, it can call some function, bar; it gets its own stack frame. And bar could be recursive and it could call itself, and so that second call to bar is going to get its own stack frame. And so what goes in these stack frames are all of the local variables and all of the function arguments that--  Any things that are locally scoped to this function go in these stack frames. So that means when I said something like bar is a function, I'm just going to declare an integer and then return a pointer to that integer. So where does y live? [student] y lives in bar. >>[Bowden] Yeah. Somewhere in this little square of memory is a littler square that has y in it. When I return &y, I'm returning a pointer to this little block of memory. But then when a function returns, its stack frame gets popped off the stack. And that's why it's called stack. It's like the stack data structure, if you know what that is. Or even like a stack of trays is always the example, main is going to go on the bottom, then the first function you call is going to go on top of that, and you can't get back to main until you return from all functions which have been called that have been placed on top of it. 

[student] So if you did do return the &y, that value is subject to change without notice. Yes, it's-- >>[student] It could be overwritten. >>Yeah. It's completely-- If you try and-- This would also be an int *bar because it's returning a pointer, so its return type is int *. If you try to use the return value of this function, it's undefined behavior because that pointer points to bad memory. >>[student] Okay. So what if, for example, you declared int *y = malloc(sizeof(int))?  That's better. Yes. [student] We talked about how when we drag things to our recycle bin they're not actually erased; we just lose their pointers. So in this case do we actually erase the value or is it still there in memory? For the most part, it's going to still be there. But let's say we happen to call some other function, baz. Baz is going to get its own stack frame on here. It's going to be overwriting all of this stuff, and then if you later try and use the pointer that you got before, it's not going to be the same value. It's going to have changed just because you called the function baz. [student] But had we not, would we still get 3? [Bowden] In all likelihood, you would. But you can't rely on that. C just says undefined behavior. 

[student] Oh, it does. Okay. So when you want to return a pointer, this is where malloc comes in use. I'm writing actually just return malloc(3 * sizeof(int)). We'll go over malloc more in a second, but the idea of malloc is all of your local variables always go on the stack. Anything that's malloced goes on the heap, and it will forever and always be on the heap until you explicitly free it. So this means that when you malloc something, it's going to survive after the function returns. [student] Will it survive after the program stops running? >>No. Okay, so it's going to be there until the program is all the way done running. >>Yes. We can go over details of what happens when the program stops running. You might need to remind me, but that is a separate thing entirely. [student] So malloc creates a pointer? >>Yeah. Malloc-- >>[student] I think malloc designates a block of memory that a pointer can use. [Bowden] I want that diagram again. >>[student] So this function works, though? [student] Yeah, malloc designates a block of memory that you can use, and then it returns the address of the first block of that memory. 

[Bowden] Yeah. So when you malloc, you're grabbing some block of memory that's currently in the heap. If the heap is too small, then the heap is just going to grow, and it grows in this direction. So let's say the heap is too small. Then it's about to grow a little bit and return a pointer to this block that just grew. When you free stuff, you're making more room in the heap, so then a later call to malloc can reuse that memory that you had previously freed. The important thing about malloc and free is that it gives you complete control over the lifetime of these memory blocks. Global variables are always alive. Local variables are alive within their scope. As soon as you go past a curly brace, the local variables are dead. Malloced memory is alive when you want it to be alive and then is released when you tell it to be released. Those are actually the only 3 types of memory, really. There's automatic memory management, which is the stack. Things happen for you automatically. When you say int x, memory is allocated for int x. When x goes out of scope, memory is reclaimed for x. Then there's dynamic memory management, which is what malloc is, which is when you have control. You dynamically decide when memory should and should not be allocated. And then there's static, which just means that it lives forever,  which is what global variables are. They're just always in memory. 

Questions? [student] Can you define a block just by using curly braces but not having to have an if statement or a while statement or anything like that? You can define a block as in a function, but that has curly braces too. [student] So you can't just have like a random pair of curly braces in your code that have local variables? >>Yes, you can. Inside of int bar we could have {int y = 3;}. That's supposed to be right here. But that completely defines the scope of int y. After that second curly brace, y cannot be used anymore. You almost never do that, though. Getting back to what happens when a program ends, there's kind of a misconception/half lie that we give in order to just make things easier. We tell you that when you allocate memory you're allocating some chunk of RAM for that variable. But you're not really directly touching RAM ever in your programs. If you think of it, how I drew-- And actually, if you go through in GDB you'll see the same thing. Regardless of how many times you run your program or what program you're running, the stack is always going to start-- you're always going to see variables around address oxbffff something. It's usually somewhere in that region. But how can 2 programs possibly have pointers to the same memory? [student] There's some arbitrary designation of where oxbfff is supposed to be on the RAM that can actually be in different places depending on when the function was called. Yeah. The term is virtual memory. The idea is that every single process, every single program that is running on your computer has its own--let's assume 32 bits--completely independent address space. This is the address space. It has its own completely independent 4 gigabytes to use. 

So if you run 2 programs simultaneously, this program sees 4 gigabytes to itself, this program sees 4 gigabytes to itself,  and it's impossible for this program to dereference a pointer and end up with memory from this program. And what virtual memory is is a mapping from a processes address space to actual things on RAM. So it's up to your operating system to know that, hey, when this guy dereferences pointer oxbfff, that really means  that he wants RAM byte 1000,  whereas if this program dereferences oxbfff, he really wants RAM byte 10000. They can be arbitrarily far apart. This is even true of things within a single processes address space. So like it sees all 4 gigabytes to itself, but let's say-- [student] Does every single process-- Let's say you have a computer with only 4 gigabytes of RAM. Does every single process see the whole 4 gigabytes? >>Yes. But the 4 gigabytes it sees is a lie. It's just it thinks it has all this memory because it doesn't know any other process exists. It will only use as much memory as it actually needs. The operating system is not going to give RAM to this process if it's not using any memory in this entire region. It's not going to give it memory for that region. But the idea is that-- I'm trying to think of-- I can't think of an analogy. Analogies are hard. One of the issues of virtual memory or one of the things it's solving is that processes should be completely unaware of one another. And so you can write any program that just dereferences any pointer, like just write a program that says *(ox1234), and that's dereferencing memory address 1234. 

But it's up to the operating system to then translate what 1234 means. So if 1234 happens to be a valid memory address for this process, like it's on the stack or something, then this will return the value of that memory address as far as the process knows. But if 1234 is not a valid address, like it happens to land  in some little piece of memory here that is beyond the stack and beyond the heap and you haven't really used that, then that's when you get things like segfaults because you're touching memory that you should not be touching. This is also true-- A 32-bit system, 32 bits means you have 32 bits to define a memory address. It's why pointers are 8 bytes because 32 bits are 8 bytes--or 4 bytes. Pointers are 4 bytes. So when you see a pointer like oxbfffff, that is-- Within any given program you can just construct any arbitrary pointer, anywhere from ox0 to ox 8 f's--ffffffff. [student] Didn't you say they're 4 bytes? >>Yeah. [student] Then each byte will have-- >>[Bowden] Hexadecimal. Hexadecimal--5, 6, 7, 8. So pointers you're going to always see in hexadecimal. It's just how we classify pointers. Every 2 digits of hexadecimal is 1 byte. So there's going to be 8 hexadecimal digits for 4 bytes. So every single pointer on a 32-bit system is going to be 4 bytes, which means that in your process you can construct any arbitrary 4 bytes and make a pointer out of it, which means that as far as it's aware, it can address an entire 2 to the 32 bytes of memory. Even though it doesn't really have access to that, even if your computer only has 512 megabytes, it thinks it has that much memory. And the operating system is smart enough that it will only allocate what you actually need. It doesn't just go, oh, a new process: 4 gigs. 

Yeah. >>[student] What does the ox mean? Why do you write it? It's just the symbol for hexadecimal. When you see a number start with ox, the successive things are hexadecimal. [student] You were explaining about what happens when a program ends. >>Yes. What happens when a program ends is the operating system  just erases the mappings that it has for these addresses, and that's it. The operating system can now just give that memory to another program to use. [student] Okay.  So when you allocate something on the heap or the stack or global variables or anything, they all just disappear as soon as the program ends because the operating system is now free to give that memory to any other process. [student] Even though there are probably still values written in? >>Yeah. The values are likely still there. It's just it's going to be difficult to get at them. It's much more difficult to get at them than it is to get at a deleted file because the deleted file kind of sits there for a long time and the hard drive is a lot bigger. So it's going to overwrite different parts of memory  before it happens to overwrite the chunk of memory that that file used to be at. But main memory, RAM, you cycle through a lot faster, so it's going to very rapidly be overwritten. Questions on this or anything else? [student] I have questions about a different topic. >>Okay. Does anyone have questions on this? 

Okay. Different topic. >>[student] Okay. I was going through some of the practice tests, and in one of them it was talking about the sizeof and the value that it returns or different variable types. >>Yes. And it said that both int and long both return 4, so they're both 4 bytes long. Is there any difference between an int and a long, or is it the same thing? Yes, there is a difference. The C standard-- I'm probably going to mess up. The C standard is just like what C is, the official documentation of C. This is what it says. So the C standard just says that a char will forever and always be 1 byte. Everything after that--a short is always just defined as being greater than or equal to a char. This might be strictly greater than, but not positive. An int is just defined as being greater than or equal to a short. And a long is just defined as being greater than or equal to an int. And a long long is greater than or equal to a long. So the only thing the C standard defines is the relative ordering of everything. The actual amount of memory that things take up is generally up to implementation, but it's pretty well defined at this point. >>[student] Okay. So shorts are almost always going to be 2 bytes. Ints are almost always going to be 4 bytes. Long longs are almost always going to be 8 bytes. And longs, it depends on whether you're using a 32-bit or a 64-bit system. So a long is going to correspond to the type of system. If you're using a 32-bit system like the Appliance, it's going to be 4 bytes. If you're using a 64-bit like a lot of recent computers, it's going to be 8 bytes. 

Ints are almost always 4 bytes at this point. Long longs are almost always 8 bytes. In the past, ints used to only be 2 bytes. But notice that this completely satisfies all of these relations of greater than and equal to. So long is perfectly allowed to be the same size as an integer, and it's also allowed to be the same size as a long long. And it just so happens to be that in 99.999% of systems, it is going to be equal to either an int or a long long. It just depends on 32-bit or 64-bit. >>[student] Okay. In floats, how is the decimal point designated in terms of bits? Like as binary? >>Yeah. You do not need to know that for CS50. You don't even learn that in 61. You don't learn that really in any course. It's just a representation. I forget the exact bit allotments. The idea of floating point is that you allocate a specific number of bits to represent-- Basically, everything is in scientific notation. So you allocate a specific number of bits to represent the number itself, like 1.2345. I can never represent a number with more digits than 5. Then you also allocate a specific number of bits so that it tends to be like you can only go up to a certain number, like that's the largest exponent you can have, and you can only go down to a certain exponent,  like that's the smallest exponent you can have. 

I don't remember the exact way bits are assigned to all of these values, but a certain number of bits are dedicated to 1.2345, another certain number of bits are dedicated to the exponent, and it's only possible to represent an exponent of a certain size. [student] And a double? Is that like an extra long float? >>Yeah. It's the same thing as a float except now you're using 8 bytes instead of 4 bytes. Now you'll be able to use 9 digits or 10 digits, and this will be able to go up to 300 instead of 100. >>[student] Okay. And floats are also 4 bytes. >>Yes. Well, again, it probably depends overall on general implementation, but floats are 4 bytes, doubles are 8. Doubles are called double because they are double the size of floats. [student] Okay. And are there double doubles? >>There are not. I think-- >>[student] Like long longs? >>Yeah. I don't think so. Yes. [student] On last year's test there was a question about the main function having to be part of your program. The answer was that it doesn't have to be part of your program. In what situation? That's what I saw. [Bowden] It seems-- >>[student] What situation? Do you have the problem? >>[student] Yeah, I can definitely pull it up. It doesn't have to be, technically, but basically it's going to be. [student] I saw one on a different year's. It was like True or False: A valid-- >>Oh, a .c file? [student] Any .c file must have-- [both speaking at once - unintelligible] Okay. So that's separate. 

A .c file just needs to contain functions. You can compile a file into machine code, binary, whatever, without it being executable yet. A valid executable must have a main function. You can write 100 functions in 1 file but no main and then compile that down to binary, then you write another file that only has main but it calls a bunch of these functions in this binary file over here. And so when you're making the executable, that's what the linker does is it combines these 2 binary files into an executable. So a .c file does not need to have a main function at all. And on big code bases you'll see thousands of .c files and 1 main file. More questions? [student] There was another question. It said make is a compiler. True or False? And the answer was false, and I understood why it's not like Clang. But what do we call make if it's not? Make is basically just-- I can see exactly what it calls it. But it just runs commands. Make. I can pull this up. Yeah. Oh, yeah. Make also does that. This says the purpose of the make utility is to determine automatically which pieces of a large program need to be recompiled  and issue the commands to recompile them. You can make make files that are absolutely huge. Make looks at the time stamps of files and, like we said before, you can compile individual files down, and it's not until you get to the linker that they're put together into an executable. So if you have 10 different files and you make a change to 1 of them, then what make is going to do is just recompile that 1 file and then relink everything together. But it's much dumber than that. It's up to you to completely define that that's what it should be doing. It by default has the ability to recognize this time stamp stuff, but you can write a make file to do anything. You can write a make file so that when you type make it just cd's to another directory. I was getting frustrated because I tack everything inside of my Appliance and then I view the PDF from the Mac. 

So I go to Finder and I can do Go, Connect to Server, and the server I connect to is my Appliance, and then I open up the PDF that gets compiled by LaTeX. But I was getting frustrated because every single time I needed to refresh the PDF, I had to copy it to a specific directory that it could access and it was getting annoying. So instead I wrote a make file, which you have to define how it makes things. How you make in this is PDF LaTeX. Just like any other make file--or I guess you haven't seen the make files, but we have in the Appliance a global make file that just says, if you are compiling a C file, use Clang. And so here in my make file that I make I say, this file you're going to want to compile with PDF LaTeX. And so it's PDF LaTeX that's doing the compiling. Make is not compiling. It's just running these commands in the sequence I specified. So it runs PDF LaTeX, it copies it to the directory I want it to be copied to, it cd's to the directory and does other things, but all it does is recognize when a file changes, and if it changes, then it will run the commands that it's supposed to run when the file changes. >>[student] Okay. I don't know where the global make files are for me to check it out. Other questions? Anything from past quizzes? Any pointer things? There are subtle things with pointers like-- I'm not going to be able to find a quiz question on it-- but just like this sort of thing. Make sure you understand that when I say int *x *y-- This isn't exactly anything here, I guess. But like *x *y, those are 2 variables that are on the stack. When I say x = malloc(sizeof(int)), x is still a variable on the stack, malloc is some block over in the heap, and we're having x point to the heap. 

So something on the stack points to the heap. Whenever you malloc anything, you're inevitably storing it inside of a pointer. So that pointer is on the stack, the malloced block is on the heap. A lot of people get confused and say int *x = malloc; x is on the heap. No. What x points to is on the heap. x itself is on the stack, unless for whatever reason you have x be a global variable, in which case it happens to be in another region of memory. So keeping track, these box and arrow diagrams are pretty common for the quiz. Or if it's not on quiz 0, it will be on quiz 1. You should know all of these, the steps in compiling since you had to answer questions on those. Yes. [student] Could we go over those steps-- >>Sure. Before steps and compiling we have preprocessing,  compiling, assembling, and linking. Preprocessing. What does that do? It is the easiest step in--well, not like-- that doesn't mean it should be obvious, but it's the easiest step. You guys could implement it yourselves. Yeah. [student] Take what you have in your includes like this and it copies and then also defines. It looks for things like #include and #define, and it just copies and pastes what those actually mean. So when you say #include cs50.h, the preprocessor is copying and pasting cs50.h into that line. When you say #define x to be 4, the preprocessor goes through the entire program and replaces all instances of x with 4. So the preprocessor takes a valid C file and outputs a valid C file where things have been copied and pasted. So now compiling. What does that do? [student] It goes from C to binary. 

[Bowden] It doesn't go all the way to binary. [student] To machine code then? >>It's not machine code. [student] Assembly? >>Assembly. It goes to Assembly before it goes all the way to C code, and most languages do something like this. Pick any high-level language, and if you're going to compile it, it's likely to compile in steps. First it's going to compile Python to C, then it's going to compile C to Assembly, and then Assembly is going to get translated to binary. So compiling is going to bring it from C to Assembly. The word compiling usually means bringing it from a higher level  to a lower level programming language. So this is the only step in compilation where you start with a high-level language and end up in a low-level language, and that's why the step is called compiling. [student] During compiling, let's say that you've done #include cs50.h. Will the compiler recompile the cs50.h, like the functions that are in there, and translate that into Assembly code as well, or will it copy and paste something that's been pre-Assembly? cs50.h will pretty much never end up in Assembly. Stuff like function prototypes and things are just for you to be careful. It guarantees that the compiler can check things like you're calling functions with the right return types and the right arguments and stuff. 

So cs50.h will be preprocessed into the file, and then when it's compiling it's basically thrown away after it makes sure that everything is being called correctly. But the functions defined in the CS50 library, which are separate from cs50.h, those will not be separately compiled. That will actually come down in the linking step, so we'll get to that in a second. But first, what is assembling? [student] Assembly to binary? >>Yeah. Assembling.  We don't call it compiling because Assembly is pretty much a pure translation of binary. There is very little logic in going from Assembly to binary. It's just like looking up in a table, oh, we have this instruction; that corresponds to binary 01110. And so the files that assembling generally outputs are .o files. And .o files are what we were saying before,  how a file does not need to have a main function. Any file can be compiled down to a .o file as long as it's a valid C file. It can be compiled down to .o. Now, linking is what actually brings a bunch of .o files and brings them to an executable. And so what linking does is you can think of the CS50 library as a .o file. It is an already compiled binary file. And so when you compile your file, your hello.c, which calls GetString, hello.c gets compiled down to hello.o, hello.o is now in binary. It uses GetString, so it needs to go over to cs50.o, and the linker smooshes them together and copies GetString into this file and comes out with an executable that has all functions it needs. So cs50.o isn't actually an O file, but it's close enough that there is no fundamental difference. So linking just brings a bunch of files together  that separately contain all of the functions I need to use and creates the executable that will actually run. 

And so that's also what we were saying before where you can have 1000 .c files, you compile them all to .o files, which will probably take a while, then you change 1 .c file. You only need to recompile that 1 .c file and then relink everything else, link everything back together. [student] When we're linking we write lcs50? Yeah, so -lcs50. That flag signals to the linker that you should be linking in that library. Questions? Have we gone over binary other than that 5 seconds in the first lecture? I don't think so. You should know all of the big Os that we've gone over, and you should be able to, if we gave you a function, you should be able to say it's big O, roughly. Or well, big O is rough. So if you see nested for loops looping over the same number of things, like int i, i < n; int j, j < n-- >>[student] n squared. >>it tends to be n squared. If you have triple nested, it tends to be n cubed. So that sort of thing you should be able to point out immediately. You need to know insertion sort and bubble sort and merge sort and all of those. It's easier to understand why they are those n squared and n log n and all of that because I think there was on a quiz one year where we basically gave you an implementation of bubble sort and said, "What is the running time of this function?" So if you recognize it as bubble sort, then you can immediately say n squared. But if you just look at it, you don't even need to realize it's bubble sort; you can just say this is doing this and this. This is n squared. [student] Are there any tough examples you can come up with, like a similar idea of figuring out? 

I don't think we would give you any tough examples. The bubble sort thing is about as tough as we would go, and even that, as long as you understand that you're iterating over the array for each element in the array, which is going to be something that's n squared. There are general questions, like right here we have-- Oh. Just the other day, Doug claimed, "I have invented an algorithm that can sort an array "of n numbers in O(log n) time!" So how do we know that's impossible? [inaudible student response] >>Yeah. At the very least, you have to touch each element in the array, so it's impossible to sort an array of-- If everything is in unsorted order, then you're going to be touching everything in the array, so it's impossible to do it in less than O of n. [student] You showed us that example of being able to do it in O of n if you use a lot of memory. >>Yeah. And that's-- I forget what that's-- Is it counting sort? Hmm. That is an integer sorting algorithm. I was looking for the special name for this that I couldn't remember last week. Yeah. These are the types of sorts that can accomplish things in big O of n. But there are limitations, like you can only use integers up to a certain number. Plus if you're trying to sort something that's-- If your array is 012, -12, 151, 4 million, then that single element is going to completely ruin the entire sorting. 

Questions? [student] If you have a recursive function and it just makes the recursive calls within a return statement, that's tail recursive, and so would that not use more memory during runtime or it would at least use comparable memory as an iterative solution? [Bowden] Yes. It would likely be somewhat slower, but not really. Tail recursive is pretty good. Looking again at stack frames, let's say we have main  and we have int bar(int x) or something. This isn't a perfect recursive function, but return bar(x - 1). So obviously, this is flawed. You need base cases and stuff. But the idea here is that this is tail recursive, which means when main calls bar it's going to get its stack frame. In this stack frame there's going to be a little block of memory  that corresponds to its argument x. And so let's say main happens to call bar(100); So x is going to start out as 100. If the compiler recognizes that this is a tail recursive function, then when bar makes its recursive call to bar, instead of making a new stack frame, which is where the stack starts growing largely, eventually it will run into the heap and then you get segfaults  because memory starts colliding. 

So instead of making its own stack frame, it can realize,  hey, I never really need to come back to this stack frame, so instead I'll just replace this argument with 99 and then start bar all over. And then it will do it again and it will reach return bar(x - 1), and instead of making a new stack frame, it will just replace its current argument with 98 and then jump back to the very beginning of bar. Those operations, replacing that 1 value on the stack and jumping back to the beginning, are pretty efficient. So not only is this the same memory usage as a separate function which is iterative because you're only using 1 stack frame, but you're not suffering the downsides of having to call functions. Calling functions can be somewhat expensive because it has to do all this setup and teardown and all this stuff. So this tail recursion is good. [student] Why does it not create new steps? Because it realizes it doesn't need to. The call to bar is just returning the recursive call. So it doesn't need to do anything with the return value. It's just going to immediately return it. So it's just going to replace its own argument and start over. And also, if you don't have the tail recursive version, then you get all these bars where when this bar returns it has to return its value to this one, then that bar immediately returns and it returns its value to this one, then it's just going to immediately return and return its value to this one. So you're saving this popping all of these things off of the stack since the return value is just going to be passed all the way back up anyway. So why not just replace our argument with the updated argument and start over? If the function is not tail recursive, if you do something like-- [student] if bar(x + 1). >>Yeah. 

So if you put it in condition, then you're doing something with the return value. Or even if you just do return 2 * bar(x - 1). So now bar(x - 1) needs to return in order for it to calculate 2 times that value, so now it does need its own separate stack frame,  and now, no matter how hard you try, you're going to need to-- This isn't tail recursive. [student] Would I try to bring a recursion to aim for a tail recursion-- [Bowden] In an ideal world, but in CS50 you don't have to. In order to get tail recursion, generally, you set up an additional argument where bar will take int x into y  and y corresponds to the ultimate thing you want to return. So then this you're going to be returning bar(x - 1), 2 * y. So that's just a high-level how you transform things to be tail recursive. But the extra argument-- And then in the end when you reach your base case, you just return y because you've been accumulating the entire time the return value that you want. You kind of have been doing it iteratively but using recursive calls. Questions? [student] Maybe about pointer arithmetic, like when using strings. >>Sure. Pointer arithmetic.  When using strings it's easy because strings are char stars, chars are forever and always a single byte, and so pointer arithmetic is equivalent to regular arithmetic when you're dealing with strings. Let's just say char* s = "hello". So we have a block in memory. It needs 6 bytes because you always need the null terminator.  And char* s is going to point to the beginning of this array. So s points there. Now, this is basically how any array works, regardless of whether it was a return by malloc or whether it's on the stack. Any array is basically a pointer to the start of the array, and then any array operation, any indexing, is just going into that array a certain offset. 

So when I say something like s[3]; this is going to s and counting 3 chars in. So s[3], we have 0, 1, 2, 3, so s[3] is going to refer to this l. [student] And we could reach the same value by doing s + 3 and then parentheses star? Yes. This is equivalent to *(s + 3); and that is forever and always equivalent no matter what you do. You never need to use the bracket syntax. You can always use the *(s + 3) syntax. People tend to like the bracket syntax, though. [student] So all arrays are actually just pointers. There is a slight distinction when I say int x[4]; >>[student] Does that create the memory? [Bowden] That is going to create 4 ints on the stack, so 16 bytes overall. It's going to create 16 bytes on the stack. x isn't stored anywhere. It is just a symbol referring to the start of the thing. Because you declared the array inside of this function, what the compiler is going to do is just replace all instances of the variable x with where it happened to choose to put these 16 bytes. It can't do that with char* s because s is an actual pointer. It is free to then point to other things. x is a constant. You can't have it point to a different array. >>[student] Okay. But this idea, this indexing, is the same regardless of whether it's a traditional array or if it's a pointer to something or if it's a pointer to a malloced array. And in fact, it is so equivalent that that is also the same thing. It actually just translates what's inside of the brackets and what's left of the brackets, adds them together, and dereferences. So this is just as valid as *(s + 3) or s[3]. [student] Can you have pointers pointing to 2-dimensional arrays? 

It's harder. Traditionally, no. A 2-dimensional array is just a 1-dimensional array with some convenient syntax because when I say int x[3][3], this is really just 1 array with 9 values. And so when I index, the compiler knows what I mean.  If I say x[1][2], it knows I want to go to the second row, so it's going to skip the first 3, and then it wants the second thing in that, so it's going to get this one. But it is still just a single-dimensional array. And so if I wanted to assign a pointer to that array, I would say int *p = x; The type of x is just-- It's rough saying type of x since it is just a symbol and it's not an actual variable, but it is just an int *. x is just a pointer to the start of this. >>[student] Okay. And so I won't be able to access [1][2]. I think there is special syntax for declaring a pointer, something ridiculous like int (*p[--something absolutely ridiculous. I don't even know. But there is a syntax for declaring pointers like with parentheses and things. It may not even let you do that. I could look back at something that would tell me the truth. I will look for it later, if there is a syntax for point. But you will never see it. And even the syntax is so archaic that if you use it, people will be baffled. Multidimensional arrays are pretty rare as it is. You pretty much-- Well, if you're doing matrix things it's not going to be rare, but in C you're rarely going to be using multidimensional arrays. Yeah. >>[student] Let's say you have a really long array. 

So in virtual memory it would appear to be all consecutive, like the elements right next to each other, but in the physical memory, would it be possible for that to be split up? >>Yes. How virtual memory works is it just separates-- The unit of allocation is a page, which tends to be 4 kilobytes, and so when a process says, hey, I want to use this memory, the operating system is going to allocate it 4 kilobytes for that little block of memory. Even if you only use a single little byte in the entire block of memory, the operating system is going to give it the full 4 kilobytes. So what this means is I could have--let's say this is my stack. This stack could be separated. My stack could be megabytes and megabytes. My stack could be huge. But the stack itself has to be split into individual pages, which if we look at over here let's say this is our RAM, if I have 2 gigabytes of RAM, this is actual address 0 like the zeroth byte of my RAM, and this is 2 gigabytes all the way down here. So this page might correspond to this block over here. This page might correspond to this block over here. This one might correspond to this one over here. So the operating system is free to assign physical memory to any individual page arbitrarily. And that means that if this border happens to straddle an array, an array happens to be left of this and right of this order of a page, then that array is going to be split in physical memory. And then when you quit the program, when the process ends, these mappings get erased and then it's free to use these little blocks for other things. More questions? [student] The pointer arithmetic. >>Oh yeah. Strings were easier, but looking at something like ints, so back to int x[4]; Whether this is an array or whether it's a pointer to a malloced array of 4 integers, it's going to be treated the same way. [student] So arrays are on the heap? [Bowden] Arrays are not on the heap. >>[student] Oh. 

[Bowden] This type of array tends to be on the stack unless you declared it at--ignoring global variables. Don't use global variables. Inside of a function I say int x[4]; It's going to create a 4-integer block on the stack for this array. But this malloc(4 * sizeof(int)); is going to go on the heap. But after this point I can use x and p in pretty much the same ways, other than the exceptions I said before about you can reassign p. Technically, their sizes are somewhat different, but that's completely irrelevant. You never actually use their sizes. The p I could say p[3] = 2; or x[3] = 2; You can use them in exactly the same ways. So pointer arithmetic now-- Yes. [student] Do you not have to do p* if you have the brackets? The brackets are an implicit dereference. >>Okay. Actually, also what you're saying with the can you get multidimensional arrays with pointers, what you can do is something like, let's say, int **pp = malloc(sizeof(int*) * 5); I'll just write it all out first. I did not want that one. Okay. What I did here is-- That should be pp[i]. So pp is a pointer to a pointer. You're mallocing pp to point to an array of 5 int stars. So in memory you have on the stack pp. It's going to point to an array of 5 blocks which are all themselves pointers. And then when I malloc down here, I malloc that each of those individual pointers should point to a separate block of 4 bytes on the heap. So this points to 4 bytes. And this one points to a different 4 bytes. 

And all of them point to their own 4 bytes. This gives me a way of doing multidimensional things. I could say pp[3][4], but now this is not the same thing as multidimensional arrays because multidimensional arrays it translated [3][4] into a single offset into the x array. This dereferences p, accesses the third index, then dereferences that and accesses--4 would be invalid--the second index. Whereas when we had the int x[3][4] before as a multidimensional array and when you double bracket it's really only a single dereference, you're following a single pointer and then an offset, this is really 2D references. You follow 2 separate pointers. So this also technically allows you to have multidimensional arrays where each individual array is different sizes. So I think jagged multidimensional arrays is what it's called since really the first thing could point to something that has 10 elements, the second thing could point to something that has 100 elements. [student] Is there any limit to the number of pointers you can have  pointing to other pointers? >>No. You can have int *****p. Back to pointer arithmetic-- >>[student] Oh. >>Yeah. [student] If I have int ***p and then I do a dereferencing and I say p* is equal to this value, is it only going to do 1 level of dereferencing? >>Yes. So if I want to access the thing that the last pointer is pointing at-- Then you do ***p. >>Okay. So this is p points to 1 block, points to another block, points to another block. Then if you do *p = something else, then you are changing this to now point to a different block. >>Okay. 

[Bowden] And if these were malloced, then you have now leaked memory unless you happen to have different references of these  since you can't get back to those ones that you just threw away. Pointer arithmetic. int x[4]; is going to allocate an array of 4 integers where x is going to point to the beginning of the array. So when I say something like x[1]; I want it to mean go to the second integer in the array, which would be this one. But really, that's 4 bytes into the array since this integer takes up 4 bytes. So an offset of 1 really means an offset of 1  times the size of whatever the type of the array is. This is an array of integers, so it knows to do 1 times size of int when it wants to offset. The other syntax. Remember that this is equivalent to *(x + 1); When I say pointer + 1, what that returns is the address that the pointer is storing plus 1 times the size of the type of the pointer. So if x = ox100, then x + 1 = ox104. And you can abuse this and say something like char* c = (char*)x; and now c is going to be the same address as x. c is going to be equal to ox100, but c + 1 is going to be equal to ox101 since pointer arithmetic depends on the type of the pointer that you are adding to. So c + 1, it looks at c, it's a char pointer, so it's going to add 1 times size of char, which is always going to be 1, so you get 101, whereas if I do x, which is also still 100, x + 1 is going to be 104. [student] Can you use c++ in order to advance your pointer by 1? Yes, you can. You can't do that with x because x is just a symbol, it is a constant; you can't change x. 

But c happens to just be a pointer, so c++ is perfectly valid and it will increment by 1. If c were just an int *, then c++ would be 104. ++ does pointer arithmetic just as c + 1 would have done pointer arithmetic. This is actually how a lot of things like merge sort-- Instead of creating copies of things, you can instead pass-- Like if I wanted to pass this half of the array--let's erase some of this. Let's say I wanted to pass this side of the array into a function. What would I pass to that function? If I pass x, I am passing this address. But I want to pass this particular address. So what should I pass? [student] Pointer + 2? [Bowden] So x + 2. Yes. That's going to be this address. You'll also very frequently see it as x[2] and then the address of that. So you need to take the address of it because the bracket is an implicit dereference. x[2] refers to the value that is in this box, and then you want the address of that box, so you say &x[2]. So that's how something in merge sort where you want to pass half the list to something you really just pass &x[2], and now as far as the recursive call is concerned, my new array starts there. Last minute questions. [student] If we don't put an ampersand or a--what's that called? >>Star? [student] Star. >>Technically, dereference operator, but-- >>[student] Dereference. 

If we don't put a star or an ampersand, what happens if I just say y = x and x is a pointer? What is the type of y? >>[student] I'll just say it's pointer 2. So if you just say y = x, now x and y point to the same thing. >>[student] Point to the same thing. And if x is an int pointer? >>It would complain because you can't assign pointers. [student] Okay.  Remember that pointers, even though we draw them as arrows, really all they store--int *x--really all x is storing is something like ox100, which we happen to represent as pointing to the block stored at 100. So when I say int *y = x; I'm just copying ox100 into y, which we're just going to represent as y, also pointing to ox100. And if I say int i = (int)x; then i is going to store whatever the value of ox100 is inside of it, but now it's going to be interpreted as an integer instead of a pointer. But you need the cast or else it will complain. [student] So do you mean to cast-- Is it going to be casting int of x or casting int of y? [Bowden] What?  [student] Okay. After these parentheses is there going to be an x or a y there? 

[Bowden] Either. x and y are equivalent. >>[student] Okay. Because they're both pointers. >>Yeah. [student] So it would store the hexadecimal 100 in integer form? >>[Bowden] Yeah. But not the value of whatever it points to. [Bowden] Yeah. >>[student] So just the address in integer form. Okay. [Bowden] If you wanted to for some bizarre reason, you could exclusively deal with pointers and never deal with integers and just be like int *x = 0. Then you're going to get really confused once pointer arithmetic starts happening. So the numbers that they store are meaningless. It's just how you end up interpreting them. So I'm free to copy ox100 from an int * to an int, and I'm free to assign--you're probably going to get yelled at for not casting-- I'm free to assign something like (int *)ox1234 into this arbitrary int *. So ox123 is just as valid a memory address as is &y. &y happens to return something that is pretty much ox123. [student] Would that be a really cool way to go from hexadecimal to decimal form, like if you have a pointer and you cast it as an int? [Bowden] You can really just print using like printf. Let's say I have int y = 100. So printf(%d\n--as you should already know--print that as an integer, %x. We'll just print it as hexadecimal. So a pointer is not stored as hexadecimal, and an integer is not stored as decimal. Everything is stored as binary. It's just that we tend to show pointers as hexadecimal because we think of things in these 4-byte blocks, and memory addresses tend to be familiar. We're like, if it starts with bf, then it happens to be on the stack. So it's just our interpretation of pointers as hexadecimal. Okay. Any last questions? 

I'll be here for a bit after if you have anything else. And that's the end of that. 

[student] Yay! [applause] 

[CS50.TV]