Skip to main content
Loading Explore guides…
Pointers and Memory · Acedra
Home
Explore
Computer Science
Pointers and Memory
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
317 segments
Copy
Hide video
0:00
[MUSIC PLAYING]
1:15
DAVID J. MALAN: All right, this is CS50. And this is week 4 on memory, wherein we reveal a topic that's actually fairly distinct to CS50 nowadays as an introductory course, known as pointers. Indeed, today is the day you can tell your friends that you learned something about pointers and, in turn, how computers work underneath the hood. I will say that this is the kind of topic, this is the kind of lecture where probably won't all sink in the first time around.
1:40
Think back to that fire hose that we showed in week 0. In fact, all these years later, I still remember where I was on campus when, finally, today's topics finally clicked for me. It was in office hours in Eliot house dining Hall in the back right-hand corner, which is only to say, as you approach this week's material, this week's problem set 4, take comfort in knowing that it is challenging. It's meant to be challenging. But, as we ratchet things up and up and up over the past few weeks,
2:03
we will start to plateau in just about a week and then it's smooth sailing there on out even though it might not feel that way initially this week. But, this week, we'll focus all the more, indeed, underneath the hood, how information is represented, like this here photograph of the bowl of stress balls that we have most every week. But recall that any time you have an image like this, it of course, is composed of pixels, and those pixels or dots each have some bits or bytes associated with them
2:28
that prescribe what color those dots should be, but there's only a finite amount of information in there. So if we enhance, enhance, enhance, you don't actually see the 50 more and more clearly. You only see it larger. And, in fact, at this size, you can actually see the dithering, so to speak, which is this cloudiness that looms over the image. And you can kind of see the outlines of the actual pixels. All of those hard vertical and horizontal edges
2:54
are the pixels, the dots that compose that image. So this is actually an example of-- and, in fact, on this last slide here, can you see them even most clearly on the screen as we go and go and go. So how do you go about implementing then or representing something like an image? Well, there's bunches of different file formats out there for images. There's GIF, there's JPEGs, there's PNGs, and there's others as well. But the simplest of them, like a bitmap image,
3:18
is literally just a map of bits horizontally and vertically conceptually. So, for instance, here is a grid of bits 0's and 1's. And suppose, for instance, that maybe 0 represents black and 1 represents white. Can anyone with their human eyes see what this is a picture of even though it's just 0's and 1's? Can you see it? Yeah. So it is actually a smiley face because if the 0's are black and the 1's are white, this is what's actually latent in that image. It's hard to see at this size, of course.
3:52
But if we were to shrink that down and actually use square pixels black and white, it would probably pop out all the more clearly. Of course, it's not that useful to store things with single pixels because you can only represent two states like 0 and 1, like black and white. And so here might be that same image actually zoomed in such that you can see all of those individual pixels. But, when it comes to color, we, of course,
4:12
need more than a single 0 or a single 1 to represent each of those pixels. We probably need like 24, maybe 3 bytes' worth for some red, some green, and some blue. And recall that that's, in fact, one of the ideas we implement-- we talked about in week 0-- how do you go about representing images, for instance? So, more generally, this is actually kind of an art nowadays, if only for fun, to actually use small dots and compose things on the screen.
4:37
And, wonderfully, just before we began today, two of your classmates bravely volunteered. And, in fact, let me invite them to come up and introduce themselves before we reveal what they have made on this canvas here using Post-it notes, square paper as their pixels. SELENA: Hello, my name is Selena. I'm a freshman in Wigglesworth. I'm thinking of studying robotics and possibly in secondary and AFBS. DAVID J. MALAN: Welcome. JEFFREY: Hi, I'm Jeffrey, I'm a freshman in Thayer Hall,
5:03
and I'm thinking about concentrating in econ and CS. DAVID J. MALAN: All right, welcome, and allow me-- hang on to the microphone if you would. I'm going to go ahead and reveal what they kindly did on very, very short notice before class began. And here is what they came up with, a grid of pixels, two colors here. What is it that we're looking at? SELENA: Can you tell what it is? Shall we say-- DAVID J. MALAN: Actually, well, we can ask the audience. What is it they made?
5:24
Because they're a little insecure about their pixel art. A ladder? Again. A flamingo. Is it a flamingo? SELENA: No. DAVID J. MALAN: No? SELENA: No, they said a palm tree on an island. DAVID J. MALAN: Oh, it's a palm tree on an island. All right, maybe a round of applause for palm tree on an island, if we could. Thank you. [APPLAUSE] Here we go. So suffice it to say, when you do have just-- thanks very much. If you have just a single color to use, black or white,
5:58
and you're using 1-bit art, it's actually kind of hard to paint a picture. But if you do have actually more colors at your disposal and an even bigger grid, can you do more interesting things? And so, in fact, we invited some past students to do exactly this. We shared a Google spreadsheet whereby we use the cells instead of as long default rectangles. We just turn them all artificially into squares so that you can use the paint bucket tool and just paint different pixels onto the screen.
6:24
And among the pieces of art that some of your predecessors came up with were this here, a scene from Mario using a grid of multicolored pixels, this one here of Scratch the Cat, this one here in honor of the Harvard-Yale football game coming up in a few weeks' time, this one here using a bit of the same. And, in fact, if you'd like to play along at home just for fun, if you go to CS50.ly/art, you can make a copy in your own Google account of that
6:50
blank spreadsheet and just play around if you'd like to experiment as well. But this is really meant to motivate one of today's topics, which is indeed how we can start to manipulate data at a lower level, including images and other things. And images, of course, can be, among other ways, be represented with RGB, some amount of red, some amount of green, some amount of blue. Before we dive into that, though, let me augment our vocabulary a bit today by adding another base to our system.
7:18
So we have binary, of course, which is base 2. We have decimal of course, which is base 10. Today we're going to introduce one more, which is useful in today's concepts as well as others as we'll see down the line known as hexadecimal, where you actually have 16 digits at your disposal. And if any of you are artistically inclined or you might've dabbled in web development, you might actually be familiar with hexadecimal notation itself already. Here, for instance, is a screenshot from Photoshop
7:45
whereby if you use the so-called color picker to manually choose a color that you want to paint onto the screen, you see a lot of information over here. But salient to today's conversation is this here where there's a hash sign and then typically six or sometimes three digits, in this case. 000000 means that the color I'm going to get here is actually black. So it's sort of no red, no green, no blue, hence the 0's, means you're going to get black.
8:11
Meanwhile, if I play around with the same color picker and I instead do FFFFFF, either all caps or in lowercase, I actually get a color that we're going to see today is going to be white, which is like a lot of red, a lot of green, a lot of blue, all the frequencies of light coming together to give us what we know as white light. But now we can play with this because it's no coincidence that these are indeed six digits of sorts,
8:35
even though they're letters of an alphabet and not numbers yet per se. For instance, FF0000 would seem to mean a lot of red and no green, no blue. And, indeed, that's why we get red according to Photoshop itself. 00F00 gives no red, a lot of green, no blue. And, of course, that's the color Photoshop would give us. And, lastly, 0000FF gives us indeed blue because that's no red, no green, but a lot of blue. So the 0's would seem to make intuitive sense here, if you have no red, no green, no blue.
9:09
But what's with the FF? Like FF, of course, in English, are letters of an alphabet, not numbers. Well, it turns out that Photoshop and people in the world of images and people in the world of computer memory tend to use a different system altogether. They don't use binary, and no one, really, in practice uses binary except the computers we use because you can't do or see much with 0's and 1's alone. We humans in the real world use the decimal system, again,
9:33
0 through 9, which is just very conventional. But, in the context of computers and specifically memory and files and images, we tend to use hexadecimal, which gives us another six digits in our vocabulary, and I'm deliberately calling them digits, even though they appear to be letters. But this is just a convention. We just need we need-- we want six more symbols. So we have 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, I don't want to say 10,
10:00
and I don't want to write 10 because that would be two symbols on the screen. So the world, years ago, decided, all right, when we want to represent 10 with a single digit, let's call it A and then B for 11, and then C and then D and then E, and then F, where F happens to be 15. So this is what's known as hexadecimal notation. And this really is the last of the notations or systems that we'll use. You can use uppercase or lowercase. The software you use decides what convention to use,
10:25
but they mean one and the same. So hexadecimal, hex implying 16 in this case, otherwise known as base 16. All right, so just a bit of jargon out of the way, how does it actually work mathematically? The exact same way as in week 0. The math is a little different. It's not going to come to intuitively in the same way, but the system is the same. If you've got two-digit values here, like here are some placeholders, the columns represent the 16th to the 0-th place, the 16th to the 1 place.
10:52
That math is easy. This is the 1's place. This is the 16's place instead of in our human decimal world 1's, 10's, 100's, or, in the binary world, 1, 2, 4, 8, same idea, just different powers for each of the columns. All right, so this number 00 represents the number you and I know as 0. In hexadecimal, 01 represents the number you and I know is 1. And it goes from there pretty straightforwardly. 05, 06, 07, 08, 09 translates to exactly what we in decimal the number 9
11:25
because it's 1 times 9 plus 16 times 0. Gets a little more interesting when you're using two digits, but you're using hexadecimal because now if I want to count as high as 10 in decimal, I would represent that in hexadecimal as 0A. 0B is 11. 0C, 0D, 0E, 0F, and there's our F. And F I'll stipulate just represents the number we know as 15. So 1 times F gives us 15, plus 16 times 0. All right, dot dot dot, we're not going to do the whole range of numbers here.
11:55
But I don't want to call this 10 in hexadecimal just like in binary. Even though you might see 10, you don't say 10. You would say 10, same in hexadecimal. So this is 10. But if I translate this pair of digits to decimal, what does this represent? So this is 16 because I've got 16 times 1 plus 1 times 0 and on up and on up and on up. We can do this for quite a while. It gets interesting only once we get to the end. Using hexadecimal, as I've defined it, what's
12:21
the highest we can count with two digits then in hexadecimal? FF would be the highest because F seems to be the largest digit. So this is actually 16 times 15 plus 1 times 15 actually gives me 255. So that is as high as I can count in hexadecimal from 00 to FF, otherwise known as 0 to 255. And if you don't believe me, a quick little math will give us that, again, 16 times 15 plus 1 times 15 as well. All right, so how is this useful doing out this math?
12:55
Well, we have the following-- oh, actually, why is this useful? So it's very common to use two digits of hex, maybe possibly more. Why? Well, it turns out that to represent the numbers 0 through 15-- let me spread these apart now just to be deliberate about it, 0 through 15. How many bits do you need? Well, 0, you can use any number of bits. How about 15? How many bits-- Sorry, how many bits do you need to count to 15? So it turns out that's four because, in binary, that would be,
13:28
what, the 8's place plus the 4's place plus the 2's place, plus the 1, which I think gives me indeed 15. So why is hexadecimal useful? Well, it turns out that you can represent a single hex digit, whether it's 0 or F, using four bits, no matter what. And so why do we tend to use two hexadecimal digits? Well, it's just useful to be able to describe a single byte, otherwise known as eight bits, using two digits instead of eight. So, in binary, we'd have to use eight.
13:59
In hexadecimal we can just use two, and it's just useful visually. Hexadecimal is useful as a result. All right, so when are we going to see this? And why are we going to see hexadecimal? Well, here's a grid of the computer's memory just abstracted away as some byte, byte, byte, byte in rows and columns. Well, here is how we might number those bytes. As I've stipulated for several weeks now, we could call this byte 0, this byte 1, byte 2, dot dot dot all the way to byte 15.
14:23
But, by convention, we don't use decimal, and we definitely don't use binary. Instead, a computer scientist would think of the addresses, the locations of, the count of bytes in memory as still starting from 0, 1, 2, 3 on up. But, as soon as you get to 8, 9, A, B, C, D, E, F. Again, just a convention. There's nothing really intellectually interesting here other than we're using a different base system instead. Here's how the others might play out.
14:50
And it gets a little confusing because this 10 is not 10 if it's in hexadecimal. But, clearly, there's some potential ambiguities here. It's pretty obvious now that if you see an A through F, OK, it's probably hexadecimal. But if you see 10 or 11 or 12, well, it's maybe not-- it might not be 10 or 11 or 12. Those might be hexadecimal even though 1A, 1B is. So this is an ambiguity. And so what we're also going to see today that the way humans have mitigated
15:16
this potential ambiguity is, when you write things in hexadecimal, by convention, you put 0x before them, a 0 and typically a lowercase x. That does not mean anything mathematically. It's not an extra 0 per se. It just means, to the human reading this, here comes a hexadecimal number. And now there is no ambiguity. So we're going to see a lot of this today. Generally, we won't care about the numbers, but that is what we're going to be looking at is hexadecimal.
15:42
So any questions on hexadecimal which, again, is just another way of representing numbers?
15:49
Any questions on hexadecimal? OK, so let's see this in practice and start to tease apart what's going on underneath the hood of our computer all of this time when we actually start to use variables and more. So here's a single line of code. Give me an integer called n, and initialize it to the value of 50, so fairly straightforward. So let's actually do something with this kind of code. Let me go into VS Code here. Let me go ahead and create a program called--
16:17
let's call it addresses.c because I want to look at the locations in memory, the address of things in memory. And let me stipulate to, as we've said in the past, just as mailboxes in the real world, houses and buildings in the real world have unique addresses, like we are at 45 Quincy Street, Cambridge, Massachusetts 02138, USA. Similarly does your computer's memory have addresses. But they're super simple numbers like 0, 1, 2 dot dot dot all the way on up.
16:45
So I've created a program now called addresses.c. Let's just play around with some familiar code. Let me include stdio.h. Let me do int main(void), so no command line arguments for this. Let me declare that variable n, set it equal to 50. And let's just print out n. So this is like week 1 stuff, super simple and presumably familiar by now whereby I want to print out using the %i placeholder the value there of n. All right, hopefully, if no syntax errors, I can do make addresses, enter,
17:16
so far, so good. ./addresses enter. And I see, as expected, the number 50. But what's actually going on inside of the computer's memory in this case? Well, we can actually see that over here. Let's look at this grid of memory here. For today's purposes, I don't necessarily know where in the computer's memory at this point. The n is going to end up-- so let's just arbitrarily say the computer finds room for the int in the bottom right-hand corner of my screen.
17:41
The size of it is deliberate because, recall, that integers tend to be how many bytes on most systems nowadays? 4 bytes by convention, aka 32 bits if you multiply by 8. So who knows? n might very well end up in the bottom right-hand corner of my screen here, with the number 50 stored there. Now, it's not literally the number 50. There's literally 32 0's and 1's in the computer's memory that are turned on and off to represent the pattern that gives me the decimal number 50.
18:10
So, again, that's sort of week 1-style stuff. But what we're thinking about now is the computer's memory. In fact, even though we refer to it as n in my code, it's got to live somewhere. And the address at which it might live for the sake of discussion is maybe something notationally written in hexadecimal like 0x123, completely arbitrary. In practice, it's probably a bigger number than that, but, for the sake of discussion, let's assume that that 50, the variable n,
18:36
just so happened to get placed by the computer at location 0x123. Can we see that in code? We haven't yet thus far. But if I propose here, maybe going back into VS Code in a moment, maybe we can actually use some slightly new syntax and poke around the contents of the computer's memory. But, before we do that, we do need a few new building blocks. And there's not much new syntax today, but we're going to go pretty darn far in terms of capabilities with just a few new symbols.
19:06
It turns out that, in C, if you use the ampersand operator, just one of them, not two. Two means and logically, just like two vertical bars meant or. If you use just one of them, as we are going to today, that is going to be the so-called address of operator. So you can write ampersand and the name of a variable, and the compiler essentially will tell you where that variable is in the computer's memory. Or, more technically, when the program is running, you will be told where it is.
19:35
The star operator or a single asterisk is not multiply in this context. It's going to be the dereference operator, which is going to be a trick via which we can have an address and go there, sort of following a breadcrumb, following X marks the spot on a map and going to that location in memory and just see what's there. Is it an int? Is it a char? Is it a string or something else? So these sort of reverse the effects of each other. This tells you the address of something.
20:01
This tells you how to get to something. So the address of operator and the dereference operator, so to speak. But we need one other building block. And this one's going to be useful in the context of printf. Recall that printf has all those format codes like %s for string, %i for integer, %f for float. Turns out there's another one, %p, which is going to allow us to print what are called pointers, which are really, for now, synonymous with addresses in memory.
20:30
So using just those new building blocks, let me propose that we do the following. Leveraging this notion of a pointer. I'm going to change my code in just a moment to still have the same single line here int n equals 50. But then let's create a second variable called p, just for convenience. But let's declare it as a pointer. A pointer is simply a variable that stores the address of something. So it's a variable that stores the address of something like 0x123 or some such value.
21:00
How do you use it syntactically? It's a little weird, especially since we've used star and the ampersand in other ways already. But you say that I want a variable called p. The type of this variable is going to be a pointer, so to speak. How do express that? Well, I want it to be the address of an integer. So you say int, but you make clear that it's the address of an integer, not an actual integer per se, by putting a star here. Of all the things we have and will see in C,
21:27
I will concede this is the most confusing way to do this. Ideally, there would just be a variable called pointer, and you just write it, and you get a variable that's a pointer. But, in the case of C, you actually specify that this variable p will indeed be an address that points to an integer. So you just have to let that ingrain in yourself. This one's a little easier. &n, how would you express that in English based on my previous definition?
21:53
The address of n, &n just means get the address of n. And because code recall is generally read and executed right to left, in this case, this says wherever n is, get the address of it like 0x123 and assign it to the variable p. What is the variable p? It is a pointer, so to speak, that is, the address of an integer. So it's a little-- it is arcane. It's a little weird. But this is kind of as low-level as we can get with C with just telling the computer exactly what we want to do.
22:21
So let's see this. Let me go back to VS Code here. And, quite simply, after clearing my terminal, let me go ahead and print out, using %p, the following address of n. And then we'll enhance this code to actually-- actually, no, let's do this exactly as I did. Let's go back into VS Code here. Let's declare int *p equals &p and then print out not i itself-- not n itself, but print out using %p the value of p itself. So what is this going to do for me? It should print out the address of n.
22:59
All right, so, in my terminal window, make addresses, enter. Huh, I messed up because I did something stupid. I forgot the semicolon as you might have one or more times the past few weeks. Let's do this again. Let's make addresses. Enter. Dammit! I screwed up a second time. I want the address of n, not the address of p. All right, so I'm doing well. So, so much for remembering this concept from the dining hall of Eliot House. All right, so make addresses. Enter, oh, my god, thank you.
23:30
All right, so now it works, hopefully. ./addresses, it's not going to be as simple in the actual computer as 0x123. It's probably going to be a bigger number. And, indeed, it's a much bigger number, but there is an address of some sort. Might be different run on a different system, but it turns out that the variable n is stored at location 0x7ffef3c2925c, which is just a really big number that if we did all of the math on paper, pencil or computer would be a really big decimal number. Why?
24:01
The server has lots of gigabytes of memory, billions of bytes. So, of course, it's probably going to be a big number like that. Now I don't strictly have to create p. And, in fact, let me do what my instinct had me doing a moment ago. Let me delete p and simply just print out directly, what is the address of n? Let me go ahead and recompile the code. Make addresses, ./addresses, and I actually do get a different address this time. Why? Because I've run the program again and things got
24:28
organized in memory a little bit differently. So these numbers are not going to remain invariant, unchanged. But, every time you run the program, things might deliberately, or for other reasons, get moved around. But all I have done is asked the computer explicitly, what is the address of n? And that's what I'm seeing. All right, so, just to recap then what these lines of code are doing, previously, when I had both n and p, this latter line
24:54
is just asking what's the address of n storing the address thereof in this variable p. But there's some disagreement in the world as to how you should write this syntactically. And just so you've seen it in case you see a video or a tutorial or a book that disagrees, this is really the conventional way to write the star. That means, hey, computer, this is a pointer to an integer, the address of an integer. You could also write it this way. And some people do this. I do think it's a little--
25:21
this can get you into trouble in certain cases. Some people do this with spaces on either side, which even looks more like multiplication, but it's not. All three will work, but the recommended conventional way is indeed to do this, even though I do concede it looks a little weird, but you'll get more and more comfortable over time. All right, so if you're with me that what we've just done amounts to just figuring out where in the computer's memory
25:48
a variable actually lives, I think we can poke around further to see even more of what's going on. In fact, let me go ahead and propose this. Let me propose here that we go back to VS Code here, clear my terminal window, and let's go back to the version before where I explicitly did have p. So int *p equals &n. And then, again, printf, quote, unquote, and what I had before was %p backslash n comma p. So this printed again, the exact same thing the address of n.
26:25
But what if I actually want to print out n itself just like I did in week 0? Well, in week 0-- sorry, just like I did in week 1. In week 1, I could have just done, as I did a few minutes ago, this. And this would print out in the old-school way the value of n and just as a quick check, make addresses, ./addresses. And there's my 50 as expected. But, now that I have these two other operators whereby I have both ampersand and star, I can poke around with them, play around
26:54
with them in ways that should, hopefully, with some practice, make sense. So, for instance, I could do this again int *p equals the address of n. Well, I could print out n literally as I'm doing now. Or I could use the location of n called p and go there with the second of these two operators, the dereference operator. The dereference operator, the single star, means go to this address. And so now, when I go back to VS Code and I do make addresses, ./addresses, enter, I still get 50.
27:28
I'm kind of jumping through hoops proverbially here because this is the stupid, longer, more complicated way to print out the value of 50, but it just speaks to the relative power that I have by just figuring out what the address is and then going there. But the confusing part I do think about this for me and for most folks learning this is the following-- the designers of C, decades ago, made, I would say, the unfortunate decision
27:50
to use the star in two different ways-- in three different ways in total-- one, multiplication. We saw that in week 1 since. But notice that there's two different uses of this star operator. Here, it literally means go there, dereference the address, that is, follow the breadcrumbs, and go there. But, when you declare the pointer, when you create the pointer, you also use a star, but you also use the type. So what's confusing, at least to me, is that we're
28:16
using the star in two different ways, both of which are related to addresses, both of which are related to pointers. But, when you create a variable or declare a variable for the first time, you specify not only star, but the type of the pointer, just like any other variable declaration. But, when you use the pointer subsequently, you do not mention the data type. Again, the compiler is smart enough to remember. OK, got it. You wanted a pointer to an integer.
28:41
The compiler will remember that for you. You do not need to remind it. So admittedly confusing, but, on line 6, we are declaring the pointer and assigning it a value. And, on line 7, we are dereferencing the pointer. So one creates the pointer, one goes to that there address. So, in terms of what's going on inside of the computer's memory, let me propose that if we revisit the same grid, and we propose that 50 ended up down here. The value n is actually technically at 0x123.
29:12
What exactly is p, the second variable? Well, I could draw it as follows in my memory. Maybe, by chance, it ends up here sort of higher up on my slide. But this is the variable called p. And the value of p is simply literally the address of n. Why is p so big? Well, it turns out, on most systems nowadays, pointers, that is, addresses, are 64 bits, or 8 bytes. So they just use a lot of bits. Why? Well, you and I have gigabytes, again, of memory nowadays,
29:41
and if you're counting up to the billions of bytes, you actually need more than 4 bytes, or 32 bits, because recall, from week 0 even, the highest you can count with 4 bytes or 32 bits is 4 billion. But some of you probably have Macs or PCs that have 5 gigabytes, 6 gigabytes, 8 gigabytes or more of memory nowadays. That means we need 64 bits to count that high, so we can actually label every memory location in order to access these spots. So what is p?
30:10
It's just a variable whose value happens to be an address. What is n? Well, it simply happens to be an integer at that address. What questions do you have on this? Yeah. Are you able to use more than one pointer in main? Absolutely, just like variables, you can create as many as you want, including arrays thereof. How do you differentiate them? By way of their name. So I'm using p because it sounds like pointer, but I could call it q or r
30:37
or s or t or use an actual English word to describe my variable. I'm just using p for short, just like any variable. Yeah. AUDIENCE: Does a pointer not have an address itself? DAVID J. MALAN: Oh, good question. Does the pointer have an address itself? Short answer, yes, because anything in your computer's memory has an address. And odds are it really has 8 addresses associated with it. So maybe we refer to it by the first one or something like that.
31:02
There actually exists-- but we won't do this today-- pointers to pointers, which answers that question. But here I'm leaving it abstracted away and just calling it p. But it absolutely has an address. Other questions? Yeah. AUDIENCE: You may have already said this, but when we're referencing things in the code [INAUDIBLE]?
31:20
DAVID J. MALAN: A good question. When you're referencing p in your code, do you dereference it? Do you use *p? Short answer, yes, if you want to go to that location. And that is usually, as we'll see this week and next week, how pointers are useful. You want to go to that location and do something there. It is rarely, if ever, helpful to literally print or see the actual address because who really cares? Especially if it changes every time I run my code.
31:46
We, as programmers, don't care where things are but that we can get to those locations. A good question. Yeah.
31:55
Sorry. AUDIENCE: [INAUDIBLE] physical memory [INAUDIBLE]? DAVID J. MALAN: Yes, without going down this rabbit hole today, we're talking really about virtual memory. This maps underneath the hood using virtual memory to physical memory. But, for all intents and purposes, we're talking about one and the same today, old computers, simpler computers, simpler times. OK, so how can we now think about this? Well, that is literally what's going on in the computer's memory.
32:20
But, as I just said, rarely do we actually care that it's specifically at 0x123. And, in fact, the name pointer kind of conjures up a nice metaphor here. Let's ignore all of the bytes of memory that we're not even using or talking about, anyway. And who really cares about 0x123? Let's just abstract that away, as we've done in the past with literally an arrow when drawing or talking about these things, and just think of p as being a variable that literally points to another location in memory.
32:47
So, indeed, whenever a computer scientist is talking about or arguing about or designing something that involves memory, they're not going to get into the weeds of doing 0x anything. They're just going to use arrows to draw things on paper or digitally. And, in fact, next week, when these sort of all comes to a head, when it comes to memory, we're going to build things in computer's memory, known as data structures, fancier structures than simply arrays.
33:09
We're going to do one-dimensional structures, two-dimensional structures, and we're going to use pointers as sort of a thread with needle to connect this location with this one with this one and this one and start to create two-dimensional objects, if you will, inside of our Macs or PCs, our phone's memory as well. So, to make this super clear, we actually do have a nice metaphor. Maybe if you wouldn't mind coming up, I keep saying that can think of addresses in memory
33:34
as being akin to physical addresses in the real world, like mailboxes for, say, this building, again, 45 Quincy Street in Cambridge, Massachusetts. And here, then, is a mailbox that has the name p. So this is appropriate because if a pointer is a variable that stores an address, this here mailbox called p would seem to be, I'll say, storing an address. Meanwhile, Yulia has a separate mailbox here that's actually called n. So it's like a variable in memory.
34:00
We're kind of cheating because, technically, the pointer would be twice as big as this mailbox. But Home Depot only has so many different sizes, so they look the same physically. But n, according to this story, lives at address 0x123. So if I am the computer and I am executing code that looks like *p, go to the address stored in p. That's akin to a person opening up a mailbox, looking inside, seeing that what's in there is not an actual value
34:27
you care about per se, but it's kind of like a treasure map, X marks the spot, if we sort of abuse the metaphor, which just means if I want to go to the address in p, that means I look in computer's memory. And, just to be dramatic, we can do this too. We've got a little big foam finger. This is like the computer pointing at the actual location 0x123, and, voila, there is the number 50 that we care about. And, for those following along at home, maybe avert your eyes here in Sanders,
34:55
we can similarly do this with the Yale foam finger as well to dereference that as well. And the crowd went wild for those of you watching from New Haven today with applause. So thank you to the Yulia, though, for this particular demo. Yes, yes, we will enhance the applause in the final version of the video. So let's now revisit, admittedly, a bit of a white lie that we've been telling for a few weeks now. And I kind of tripped over this in week one but then sort of waved my hand
35:26
and solved it real quickly by introducing the CS50 library. But I'm going to propose that we revisit what a string actually is. Now, we use strings in week 1. We then began, in week 2, to talk about strings, thank you, as just being an array of characters, so that was the first reveal. But, even then, we kept using the word string. But it turns out that strings do not exist in C as a data type. Strings are not a CS50 thing per se, but there is literally no keyword in C
35:57
called S-T-R-I-N-G, string. It's a concept that exists in C, so nothing is that we've said over the past few weeks has anything to do with CS50, per se. Almost every programming language you'll encounter in the real world supports strings in some way, but my claim today is that the keyword string is actually made up for us for convenience over the past few weeks. Now, why is that? Well, up until now, we have been creating strings in code with lines like this.
36:23
String s equals, quote, unquote, "HI!" in all caps, semicolon. What that would do, according to week 2's discussion of memory, is it would give us four bytes in memory for HI Exclamation point and a fourth byte, to be clear, for the null character, N-U-L-L, the backslash 0, which is just 8 0 bytes. And, therefore, were able to manipulate that string as though it were an array. So S bracket 0 is the first character. S bracket 3 is the very last character, specifically that null character.
36:52
Well, really, we can start to think about strings a little differently still today. In fact, let me go back over to VS Code here, clear my terminal window, and let's stop playing around with integers like number 50. And, instead, let's do this. Let's give myself a string s equals, quote, unquote, "HI!" And then let's go ahead and print it out, just like in week 1, with %s backslash n comma s. Let me go ahead and increase the size of my terminal window. Do make addresses.
37:23
And here is the very same mistake we glossed over in week 1. Error, use of undeclared identifier string. Did you mean stdin? Now, maybe that does sound familiar, but it's kind of a red herring. This has nothing to do with stdin per se. String is undeclared because it doesn't exist in C by default. And, in fact, it thinks maybe this is a typo. stdin in is a thing that exists in programming languages, but string, I said, in C, does not. But this fix for me, recall in week 1, was to very quickly
37:54
say, oh, we'll come back to that. And, at the top of my code, I went in and added one more include, cs50.h And, somehow, if I clear my terminal, rerun make addresses, that solved everything, and string was brought into existence. But how exactly was that the case? Well, we'll see today what's actually going on underneath that hood as well. So what have I just done with this code? I've simply printed out the string s. But, notice, I claim, what's really going on
38:23
if I visit the actual memory in the computer is, yeah, it's an array. But if an array is just a chunk of contiguous memory, certainly, we could figure out what the bytes are, the addresses are of each of those characters H-I exclamation point, and the null character. And, again, for the sake of simple discussion, suppose the H is at 0x123, stands to reason that I is going to be at 0x124, exclamation points at 0x125, and the null character's at 0x126. The specific numbers don't matter, but what
38:54
does matter is that they are 1 byte apart, and that is literally what I've meant all these weeks when I say contiguous. Back to back to back, they're literally 1 byte apart. So, once we know this, can we leverage this to play around with and see strings, perhaps, in a somewhat different light? Well, let me go ahead and do this. Let me go back to VS Code here after clearing my terminal. Let's leave string s as is, but let's print out a few different things.
39:20
Let's actually print out what is inside of s. %p backslash n is how I can display an address, aka pointer. And let's print out the value of s. Let me go down to my terminal and do make addresses, enter. ./addresses. And what I see now is a seemingly random but a much bigger hexadecimal address. So it seems that s is not a string, per se, because I literally just told the computer to print it out with printf, albeit using %p instead of s. But %p just means show me the address of a variable.
39:58
And it seems that s's technical value is 0X59FB1699D004. Now, that is the longer version of what I just proposed, for discussion's sake, is 0x123. Well, let's be a little more pedantic here. Let me go ahead and print a couple of more things. Let me print out another address using %p, but let me print out the address of the first character in s using my array notation. And then let me do some quick copy-paste just to see a few more of these.
40:31
Let me print out location 1, location 2, and location 3. So we're really kind of making use of this arcane-looking syntax today, lots of %p's, but that just means show me, address, address, address, address, and so forth. s[0] is from week 2-- just show me, using array notation, the first character, the second character, the third, and the fourth. And & is new today. It juts means show me the address of that character, not the actual character.
40:55
So if I go back down to my terminal window, make addresses again, I'm going to see five values in total now, ./addresses gives me this. Let me zoom in, and what's noteworthy is that the very first one is identical to the second one, which seems to imply that s has the same address as the first character of s, but that sort of makes logical sense because what else would it be if not the first one. And so what we're seeing here now is a hint that,
41:26
whereas %p is printing out literally the value inside of s, what was %s doing all of this time? It was thanks to printf's implementation, decades ago, going to that address and printing character, character, character, character, and stopping only once printf finds what? The backslash 0, the null byte. So some person, years ago, literally implemented printf. They literally are using s as an address, going to that address somewhere with a star operator in their code,
41:59
and then using a for loop or a while loop, iterating over character, character, character, and character from that address onward until it sees the so-called null character. All of this has sort of been happening for us automatically, but that's really all that's going on. If I go back into the visualization of my computer's memory, here's that same simplification using smaller numbers 0x123, 124, and so forth. And what is s then when it's declared in memory?
42:24
Well, it's a pointer, which means it takes up 8 bytes, so I am doing this to scale. But what is s really doing? It's storing the address of the first byte of the actual characters. It's storing nothing else. s is not storing the last byte. It's not storing the length. It's not storing anything other than the first byte's address. But that's OK. Why? Because how does the computer, functions like printf, know where the strings end just to be super clear? The backslash 0.
42:56
That's why we're wasting an extra byte all these weeks because someone needs to know or tell everyone else where strings actually end. Those of you who do have some prior programming experience in Java or in Python or other languages, you can generally just ask a string, what is its length? You can call a length function. You can do .length or similar, those of you who've done this before. That's because in higher-level languages like Java and Python,
43:20
there is more memory being used than just the address of the variable alone. Someone somewhere is keeping track of the length of that chunk of memory, but C is much lower level. It's much more efficient. It's much more complicated in that it leaves it to someone else, something else to keep track of where strings actually end. But like that's it. And, in fact, oh, I brought these just to be sort of unduly dramatic. All these weeks, we've had these sort of training wheels on,
43:46
where we've had these simplifications of cs50.h and strings existing. And now we're taking the training wheels off because this is literally all that's been going on since week 1. I'm not sure that added anything. [LAUGHING] This is all that's been going on since week 1, but, again, that's the design of the course is to help you understand first at a high level so you can just get things working and start playing around. Now we're taking a peek underneath the hood
44:13
to see what really has been going on all of this time. And, indeed, who cares what addresses these things live at? And so the way you would typically think about or draw this on a piece of paper is literally just with an arrow. s is pointing at a chunk of contiguous memory that is null terminated, so to speak. So where did string actually come from? Well, here is how I've been declaring strings today and prior, string s equals, quote, unquote, "HI!" string being supposedly the type
44:42
of my variable. Well, it turns out that a string we have seen is really just an address, but it's the address of what just to be super clear? A string is really the address of its first character, so its first character, so its first char. So I think the implication of this now is that if we get rid of those training wheels and we get rid of even the CS50 library, we can actually start calling strings char stars. And this is what real geeks call strings.
45:08
Like oh, a char star in C is known to mean you're just talking about a string, but you're doing it at a sort of a lower level, actual vernacular, which implies that the address is, in fact, that of its first char. The last address --of the address of its last char is implicit in that null character that we've been using all of this time. So we've actually seen this kind of before. In fact, just recently we introduced the notion of persons.
45:36
And I said, well, if we wanted to invent our own data type and a person, for instance, would have a name and a number, we introduced syntax like this, which was kind of a mouthful, but the only interesting part is what's inside of the data structure in this case. person was the name we gave to the data type. This whole struct is what we wanted a person to be, and the way we brought a person into existence in C was we defined a type using the typedef keyword in C.
46:03
That's actually going to be the trick to what we've been doing in CS50 for the past few weeks. We're using typedef to define our own type. We want to create an alias, for instance, from one thing to another. So just to keep things simple at first, suppose that I'm really confused by int. It's an integer I get, but why int? Why int? Suppose I want to create a synonym called integer for ints. I could literally say typedef int integer semicolon,
46:29
and this will bring into existence a data type called integer, which doesn't really solve a problem other than helping you remember that ints is really just short for integer, but the syntax can be as simple as that. It doesn't need to be multiple lines with structures and Person attributes like that. So, accordingly, how can I define a data type for a string? I can say typedef char *, which is, admittedly, more mind-bending, but I want to think of it instead as a string.
46:56
So, inside of cs50.h, since week 1 has been literally this line of code, a bunch of other lines too. But this one-liner, because you are including it atop your code, brings into existence the keyword string. But it's just like doing an automatic find and replace between string and char *. That's all that's actually happening, really underneath the hood.
47:23
What questions do you have on what a string actually is in this case? It's all what's inside of cs50.h.
47:37
Yeah. AUDIENCE: In this case, if we put the star next to string [INAUDIBLE] that you were talking about, [INAUDIBLE]. DAVID J. MALAN: A really good question here. Am I violating my own convention? I am not here. I do-- Rongxin, do you know if this would work without the space here?
48:07
We'll find out. He's checking. So this is a different context. I'm not actually declaring a variable here called string. I am declaring a type called string. It's possible it's allowed. I don't know offhand. So good question. Other questions, yeah, in the back. AUDIENCE: When is it more useful to use the char * rather than string? DAVID J. MALAN: A really good question. When is it more useful to use char * instead of string? Honestly, after you exit CS50, you should not use string anymore.
48:36
And, in fact, among the things we're going to do next week is take the last of these training wheels off and take away the CS50 library so that you actually use only native C code, per se, so that there are no more training wheels physically or virtually, otherwise. So, in the real world, if you ever write C, you would just use char *. We use string only because I daresay introducing char * and these memory addresses and mailboxes all in the first week of C.
49:01
It's just too much when all we want to get working is like hello world or Mario or the like. Other questions, yeah. AUDIENCE: [INAUDIBLE] DAVID J. MALAN: Ah, really good question. In my VS Code here, when I used the &, I used it in front of each of the characters 0 through 3, but I didn't use it here, a subtlety. But the reason I didn't use it here is because s we now know is already a pointer. It is a char *. So if it's already an address and %p expects an address, there's no reason to do &s.
49:42
It is already the address of a string. Specifically, I can now take away the CS50 library from my own code. Let me clear my terminal. Go back up here. Take the CS50 library away, which was a bad thing earlier. But if I now call this char * s, this declaration here makes more explicit that s is the address of a char. So %p expects an address. You can literally slot in s there. But s[0] s[1], s[2], those are actually chars inside of an array. So if you want the address of those characters,
50:19
you do need to use the ampersand. And, in answer to the question that came up over here, if I were to incorrectly use an ampersand here, that would be getting the address of the pointer, not the address of the string. But we're not here to talk about that today. Other questions. Yeah, in the back. AUDIENCE: Where does %s come from? DAVID J. MALAN: Where does %s come from? So that, %s is supported by C and specifically printf. So strings exist as a concept in C. The word string does not exist.
50:49
But, when you use printf now, as I can here as another demonstration, I can do printf. I don't change this now to %c because I don't want to print a character. I still want to print a whole string conceptually, and I can pass in here's just as before. So printf has always understood %s. That's not a CS50 thing. The only thing that was a CS50 training wheel was the word string, which we can now take away safely. You just have to start writing char star instead. Other questions, in the back?
51:20
AUDIENCE: So, for our code going forward, should we be writing typedef char * string? DAVID J. MALAN: Oh, good question. So, in your own code, should you now start doing typedef char * string semicolon so that you can still use string? No, if, after today or if after a few days from today, you understand what's really going on and you're comfortable with it, there's no reason to keep putting the training wheels back on yourself in perpetuity.
51:43
The simpler approach would just be keep using CS50's library for some amount of time, and that too is fine, even some final projects. It's fine to still use these training wheels. The goal of today and next week and beyond is really to make sure you understand how you can write code successfully, even without those same training wheels on. All right, so let's poke around just a little bit more with these capabilities. In VS Code here, let me propose that we can dabble a little further as
52:10
by doing something like this. If I go into, let's say, addresses.c one final time, I'm still going to create s as, quote, unquote, "HI!" in all caps. But now, just to be clear, let's print out this string manually just as we could have back in week 1, except now there is no string. There's only char stars. So I'm going to do %c /n, quote, unquote, comma s[0]. And then, just for the sake of discussion, let me just copy-paste this twice so as to print out these two characters.
52:43
Again, I'm just playing around. In the real world, I should really use a for loop or something like that, but I just want to manually poke around with this new syntax. So let me make addresses again, ./addresses, and I should see HI! one per line. So that's just week 1 stuff. But now let me propose that there's this other feature of C we can avail ourselves are known lastly as pointer arithmetic. So if every chunk of memory has an address
53:09
and that address is just a number, whether it's in hexadecimal, decimal, binary, whatever, they're just numbers, I can actually do math on addresses. And if I can start in one location, I can go 1 byte away, 2 bytes away, 3 bytes away, just by adding 1 or 2 or 3. It stands to reason. So what's the implication of this? Well, it turns out that I don't need to use square bracket notation anymore if I don't want to. We introduced it in week 2.
53:34
It is a feature of C, and it is a very, very common and useful convention and probably the convention to keep using. But, strictly speaking, we don't need to use square brackets anymore to print out individual elements of an array. For instance, I could change this first line to not be s[0], but I can just say go to the first character of s because if s is a string-- otherwise, now known as a char *-- and char * just means the address of a char, well, if I want to print out the actual char,
54:09
I can use * s to go to that address and where I will find-- X marks the spot-- a char in the computer's memory. But here's where the arithmetic comes in. Let me do another line. printf %c backslash n comma go to s plus 1. So I can literally do a bit of math on my pointer to go one location to the right. I can do this once more. printf %c backslash n comma %s-- percent-- sorry, * s plus 2 to go 2 locations to the right. And I'm doing this only because I know HI! exclamation point gives me
54:48
3 locations in total. But if I now do again make addresses, ./addresses, I get the exact same behavior. And, in fact, the square brackets we introduced in week 2, which, again, come with C is just syntactic sugar, so to speak, which is a term of art in computing, which just is a more user-friendly way of expressing this weirder syntax. The square brackets by the compiler are essentially converted into pointer arithmetic for me so that I don't have to write code that, admittedly, on the screen,
55:19
looks more cryptic than it would with just the simpler, more user-friendly square brackets. But all that those square brackets are doing, underneath the hood, is effectively pointer arithmetic for you. So if I want to play around one final way with all of the same code, I can even do things that probably aren't the best idea but do speak to the power of this syntax and this language, C. For instance, if I want to print out the actual string s, we know I can do this already,
55:47
%s and print out s itself because s is a string, otherwise known as a char *. So make addresses just gives me HI! But what if I only want to print out part of the string? I could start partway in the middle of this thing. What if I do this-- printf %s backslash n, s plus 1. So no star, I don't want to print out a char. I want to print out a whole string. What is a string? A string is an address of the first character of the string, still null terminated.
56:17
So, when I compile this code, printing out-- and, actually, let me get rid of the previous line. When I compile this code with make addresses and I run ./addresses, what should I see on the screen now? If I'm not printing starting at s, I'm printing starting at S plus 1? AUDIENCE: i. DAVID J. MALAN: Yeah, I think you're saying i, like i! Why? Because if these strings start at 0x123 and go 0x124, 0x125, 0x126 and I'm starting at 0x123 plus 1, that means start at the second character.
56:50
And I think, yep, I now see i! If I change it to 2, I now see, after doing make addresses, I think I should just see very excitedly an exclamation point. And that's it. I probably don't want to go even further than this because then who knows what's going to happen if I start printing beyond the boundaries of the actual string. And that, in fact, is going to be one of the trade-offs here. Even though now with these simple operators like star and an ampersand--
57:15
we can now manipulate and understand memory at this lower level-- we can actually do a lot of damage. And among the things we'll talk about today too, after the break, is recall the CrowdStrike fiasco a few months back where systems around the world broke down, including airlines and the like. That stupid, stupid issue was the result of such a simple problem that, after today's break, you too will understand. But, in the meantime, in happier news, let's have some little bites
57:43
of blueberry muffins in the transept. See you in 10. No, don't applaud. We're not done. See you in 10. All right. We are back and one erratum. So this was the line of code I proposed in cs50.h. It's not quite the line of code in cs50.h because, as was asked, stylistically, the, quote, unquote, right way to write this would indeed be without the space after the star. So even though string is not being declared as a variable here but rather as a type, stylistically--
58:13
and just asked style50 for the correct answer, it would indeed omit the space. So this is what I should have said earlier, and we'll fix that in the online version thereof. But, for now, let's actually transition to taking a look again at the computer's memory and revisit some problems that we looked at indirectly over the past couple of weeks and better understand why things worked and now work the way they do. So let me go over to VS Code here, and I've written
58:37
in advance a relatively simple program. I'm still using cs50.h and stdio.h for this example. I'm calling get_int twice to get two variables, i and j, so two numbers from the user. And I'm checking for equality using equals equals. So if i equals equals j, I'm going to print same. Otherwise, I'm going to print different, so fairly straightforward. And it should just work. Indeed, if I open up my terminal window, and I do, let's say-- oops, sorry.
59:05
If I open up my terminal window, do make compare because this file is compare.c, I can then do ./compare and type in two numbers like 50 and 50, and they're indeed the same. Or I can do it again 50 and 51, and they're, in fact, different. And I'll stipulate that pretty sure this code is in fact correct. But what if we make a change of sorts and actually compare not integers, but strings, what's going on? Well, let's first consider what is happening with integers. So here's my computer's memory.
59:33
And I've zoomed out a bit just so we can fit more on the screen at once. And here might be where i and j end up in the computer's memory. When running this program, i here j here, both of them 4 bytes because both i and j are integers. It stands to reason then, when I compare i and j, we are literally comparing 50 against 50 in that first scenario. And indeed it's, technically, 32 bits and 32 bits, but they're exactly the same if they're both storing and representing the value 50.
1:00:01
All right, so fairly straightforward. But what about strings? In fact, we deliberately introduced strcmp, for string comparison, because, when I last tried to compare two strings, it didn't actually work as intended when using equals equals. So, in fact, let me go back to my code here and close my terminal window and just make a couple of changes here, same idea but different data types. So let's do string s equals get_string, and we'll prompt the user for a string s now instead of i.
1:00:32
Then maybe a string t just to keep the variable name short for the sake of discussion, and prompt the user for t here. Then let me go ahead and say if s == t. Go ahead as before, and print out Same backslash n. Otherwise, go ahead in my else clause and print out, quote, unquote-- oops quote unquote "Different". All right, so same logic but different data types using strings for the type and get_string for the function. Let me open my terminal window again, make compare.
1:01:03
No syntactic errors, but let me go ahead and do ./compare and type in something like, how about HI! and HI!, both in all caps, but they appear to be different. I can try again. Maybe my name, David and David. Hmm, also different even though it seems to be the same. So what's going on? Well, you might already have an intuition. And someone last time, when we looked at a program like this, did have an intuition. But what if we make it more explicit now?
1:01:30
What if I change my strings to literally char *'s, which doesn't affect the functionality but takes off one of those training wheels. I'm not going to get rid of cs50.h altogether because, as we'll see, I still want to use get_string. Otherwise, it's a pain in the neck in C to get user input. But we'll come back to that. But s now is not only a string. It's more precisely the address of a character, technically, the first character of a string.
1:01:53
So what then is being compared on line 9 that's yielding this different answer? Why are HI! And why are David different even if typed identically? Yeah, it's two different addresses. What's really going on if we take a look at the computer's memory now, dealing with strings is the following. Here's that grid of memory. Maybe s ends up here, and maybe the actual array of characters ends up here because, notice, when we're using strings,
1:02:23
technically, we're storing the address, and we're storing the actual characters. And that's all been happening magically in one step for us, one line of code. But, technically, there's different chunks of memory involved. And it might be at 0x123, 0x124, 0x125, and 0x126. All of that happens automatically with that one line of code when I create and initialize s. Meanwhile, s is going to therefore store the address of that first character, hence the whole idea of a char *. But what is t?
1:02:50
Well, maybe t ends up over here somewhere in memory. Maybe the other HI! that I typed in or later the David that I typed in ends up at maybe 0x456, 0x457, 0x458, 0x459. Again, who cares what the addresses are? But they are back to back to back, which is important. But suffice it to say then what ends up in t is the address of that second string that I actually typed in. And, for all intents and purposes, that's like s pointing to this chunk of memory, t pointing to this chunk of memory.
1:03:18
So, when I use literally == to compare the two strings, that is, to compare the two char *'s, that is, compare the two addresses, clearly, they're in different places. It's like asking the computer, are 0x123 and 0x456 the same? Well, of course, not, those are literally two different numbers written in hexadecimal or anything else. So we needed a solution for this. And that is why we introduced strcmp, the function that actually addressed this properly.
1:03:49
If I go back then to VS Code here and, instead of using ==, I give myself access to our old friend now, the string.h header file-- in that library is the declaration of strcmp. So I can do strcmp passing in two variables s comma t. And, recall, what is the return value I care about? What is strcmp return if two strings are equal? So it returns 0. Otherwise, it's a positive or a negative number, which helps with alphabetization. But that's not what we want here.
1:04:21
I want to make sure that the return value of strcmp == 0. And what does that do for me? Well, if I open up my terminal again, make compare, ./compare, and, again, type in HI exclamation point, enter, and HI exclamation point, enter. Now they're, in fact, the same. But if I type something different like HI! and BYE! those, of course, are different, not on the basis of their addresses, but on the basis of their actual characters. And, in fact, that's what's really happening.
1:04:53
The way strcmp is implemented by someone else years ago is that they have some code, some kind of loop probably, that first dereferences s and t, respectively, goes there, and then, in some kind of loop, iterates over these two strings in memory, checking whether the individual chars =='s each other, stopping once it hits backslash 0 in either string. And if they happen to look the exact same character by character, then it returns 0.
1:05:23
It's a little fancier than that because it uses some less than or greater than to figure out if one comes before the other ASCII-betically. But it is doing the walking across the string. So the person that implemented strcmp uses a for loop, a while loop, whatever to do all that legwork for us. Questions on strcmp or what we've just revealed? Yeah. AUDIENCE: Subtracting the value of-- the ASCII values of each char from [INAUDIBLE]? Is that why it was a [INAUDIBLE]? DAVID J. MALAN: Good question.
1:05:54
Is it subtracting the ASCII values of the characters? Not necessarily. It's probably comparing them with less than or greater than literally because if you're comparing A and B, that would be like comparing 65 and 66 if capitalized. So you don't need to subtract anything, per se. You can just compare the magnitude of those values. Yeah. AUDIENCE: So do you have to create a different memory to store that? DAVID J. MALAN: Oh, good question. Do we use two locations in memory for both the pointer
1:06:22
s and the actual array of characters? Short answer, yes. And how that is happening is, as follows, if I go back to VS Code and highlight the lines of code that we just wrote, so, for instance, line 7, the left-hand side of the expression here creates those 8 bytes in memory called s that will eventually store an address of the first character of some string. The get string function, written by cs50, handles the process of allocating the array for H-I-! And the backslash 0 and puts it somewhere.
1:06:54
I depicted it down here on the screen. So get_string allocates one chunk, and your code here allocates the other chunk. There are other ways to do this. And, in fact, once we completely take away the CS50 library, you have to allocate not only the left side, but also the memory for the right side of this expression, so to speak. And we can do that in different ways, and we'll come back to that soon. All right, so if we now know and appreciate that these two addresses are
1:07:20
indeed different s and t, it turns out we can play around with create some new problems but also solve them as well. So how might I go about, for instance, let's see-- seeing what we just did, if I go back into VS Code here, let me just do something simple and no longer compare these. But, just to make the point, using our %p format code now, I can actually print out the actual values of s and p if I want to-- s and t if I want to convince myself of all of this. So I can print out--
1:07:52
sorry, with %p with the value of s, with %p the value of t. And, in this case, even if I type the same thing, watch again what happens. Make compare, ./compare. I'll type in HI! I'll type in HI! And I should now see two addresses, but, per the depiction, on the screen, they do end up in different locations. They're similar locations. These numbers are actually pretty similar, but, notice, they differ down here. A b and an f puts them a few bytes apart.
1:08:21
So they're actually next to each other in memory, but they're not, in fact, at the same location. So that's what's happening underneath the hood. And, just to be super clear, it is rare, if ever, that you as a programmer will ever bother using %p to print out an address. Generally, we do not care where things are, just using it for the sake of demonstration to make clear that we could go there if we so want. All right, well, what if we want to make--
1:08:45
maybe manipulate these strings and actually change them in some ways. Let me do this. Let me clear my terminal, close compare.c. Open a new file called copy.c whereby I might ultimately need to make copies of strings in memory. And let me go ahead and do this. Let me include cs50.h so I can still use get_string. Let me include, how about, stdio.h, as we often do. Let me include string.h as we now do. int main(void) for my main function. And then, in here, let's do the same thing as before.
1:09:17
string s equals get_string, and prompt the user for that string. Then let's go ahead and copy the string as follows. String t equals s, then let's go ahead and capitalize the first letter of this string. And it might be a little hazy, but we introduced a library a couple of weeks back called ctype.h, which has a bunch of functions related to types in C, one of whose functions, recall, is toupper, which just uppercase is a character. So what I'm going to do here is I'm going
1:09:47
to change the first character of t, but not s, to equal whatever the return value of toupper is passing in the first character of t. So I'm just changing the first character of t to be the uppercase version thereof. Now I'm going to go ahead and print out. The value of s is %s backslash n. And I'm going to plug in s. And then I'm going to do the exact same thing for t. So I can see both the before and the after version of my capitalized change. Let me open my terminal. Let me do make copy.
1:10:18
And I screwed up because I should be including not a c file, but a header file. So ctype.h at the top, unintended mistake. Make copy again. That worked. ./copy, and now this time let me deliberately type it in all lowercase HI exclamation point because the whole point of t is to be uppercase. If I hit Enter now, I see, huh, a curiosity. Both s and t were somehow capitalized for some reason, even though I only changed, on line 12, the first character of t. Why might that be?
1:10:59
Why might that be? Let me offer a bit of a hint. What if, again, we take off some of these training wheels? S is just a char * as of today. t is just a char * after today. So what's happening such that I'm seeing the change affect both s and t? Yeah.
1:11:17
Yeah, I'm really copying literally s and t, which means both of those variables contain the same address. So, even though I'm following t's address, that leads me to the same location that s is pointing to. So I'm essentially changing the one and only one copy of HI exclamation point. In fact, we can see that as follows. If I open up my computer's memory-- let me propose that s ends up over here. Maybe hi in lowercase ends up down here.
1:11:42
Maybe at those same addresses as before 0x123 therefore s contains 0x123. Meanwhile, t is a separate variable that I declared with almost identical code, but I then set it equal to s, which is literally copying the value in s into t. If we now get rid of all these unnecessary addresses and just use abstraction, it's as though s and t are pointing at the same place. So it doesn't matter whether you follow s or you follow t when you dereference either. As is implied by the square bracket notation,
1:12:12
means go there, you're just changing the 1 and only copy of H. And so, whether you print s or t, you print out the capitalized version thereof. So what's the solution here? Well, we actually need to be a little more clever when it comes to making actual copies. Up until now, super simple to copy integers, chars, floats, longs, doubles. All of those primitive data types, super simple because code like that, on line 10, would just work. But, whenever you're talking about something fancier
1:12:41
like a string, which isn't one location-- it's sort of a sequence of locations, someone's got to do the hard work of allocating another chunk of memory, copying the characters from old into new, and somehow keeping track of all of that. Now, we'll do this ourselves in just a moment, but, thankfully, there's going to be a library that can make our lives easier instead. So let me go ahead and do this. Let me propose that we, in VS Code, improve this code as follows.
1:13:11
Instead of just blindly copying s and calling it t, I'm going to actually use a new function called malloc. We haven't needed this before. It's among the remaining tools in our toolkit in C. But malloc stands for memory allocation. And it's a function that super simply lets you pass in as input a number. How many bytes of memory do you want? And it will hand you back a chunk of memory. Specifically, it will hand you back the address of that chunk of memory,
1:13:40
specifically, the address of the first byte of that chunk of memory. Free is the opposite. Once you're done with this memory, you can call free and give it back to the computer so that you don't eventually run out of memory. You can give things back when you're done. So how can I now leverage this in my own code? Well, let me propose that. I implement a copy a little more cleverly here. Let me go back to VS Code here. And, instead of using s equals t, let me instead
1:14:08
say t initially should store the address of a new chunk of memory that's big enough to store the characters of s. The way I do that would be malloc. And how many do I need? H-I-! And the null character. I could just get away with saying 4. Give me 4 bytes of memory and store the address of the first byte in t. That is what line 10 is now doing. Now, that's kind of a stupid approach. I shouldn't hard code the number 4 because who knows what the human's going to type in.
1:14:37
But we have other friends here. We can say, figure out what the length of s is, add 1 more bite for the null character, and ask malloc for that many bytes because, now, no matter how big or small s is, we're going to ask for the appropriate number of bytes. What is stored in t at this point in the story is the address of that chunk of memory, specifically the address of the first byte in that memory. Now, there's no null terminator or anything.
1:15:03
Everything in there at the moment is sort of garbage value, so to speak, until I put something there. So what I'm going to do now is this, after I allocate that chunk of memory, I'm going to use a for loop, just like the authors of strcmp had, but for a different purpose. For int i equals 0, n equals the string length of s semicolon. And we've seen that technique before. So we don't waste time calling strlen again and again and again. i is less than n. And then i++.
1:15:35
And, inside of my loop, I'm going to copy into location i of t whatever's at location i of s, effectively copying from left to right all of the characters of s into t. At the very end of this, I could do something, but I think-- I could do something to manually add a null character to the end of my new string t, but I don't think I have to do that. The one time this makes sense is perhaps now. I'm going to actually iterate from i less than
1:16:09
or equal to n because I actually want to copy the null character as well. So if the string is H-I exclamation point new line, I actually do want to go from 0 to 1 to 2 to 3 and then stop. Normally, I would go from 0 to 1 to 2, but I want to include the sort of secret null character there. So I think this for loop will capture that for me. I'm not going to change any of the rest of code, so all I have done that's different now is explicitly
1:16:36
allocate a new chunk of memory for t and copy everything in s into t. But, to use malloc, I need a new library. I'm going to go up here and include stdlib.h. And, again, you learn, through practice, what's in what library? Or you can go to manual.cs50.io and just look it up to figure out in which header file something is. And I'm also going to include the same header files as before. So the only change is to add stdlib.h. Let me open my terminal window. Make copy ./copy.
1:17:10
And now let me type in H-I exclamation point in all lowercase. And I should see in a moment the output of both s and t, but, hopefully, only one of them is capitalized t. And, indeed, I've done it somehow. So what actually just happened? Well, if we actually go over to a visualization thereof, here is my computer's memory when s exists. If, though, I'm going to allocate new memory with malloc, that's like calling malloc, getting some chunk of memory. Maybe it ends up here.
1:17:39
Maybe it ends up somewhere else. I'm just keeping it in the same place for discussion. And the first address happens to be 0x456. Well, what gets stored in t? The return value of malloc, and malloc returns the first-- the address of the first byte of memory. So what ends up in t is effectively 0x456. But who cares? We'll just draw it abstractly as an arrow. What does my for loop then do? Well, it iterates over s and t in lockstep such that the h gets copied,
1:18:06
the i gets copied, the exclamation point gets copied. And because I use less than or equal to, we also copy the secret null character as well. Then I use toupper on t[0]. Here's t, here's t[0], and so I think only the h and t is now capitalized. It's not a particularly interesting exercise, but it does demonstrate really, with as few steps as possible, how we can solve this problem of actually copying strings in memory by allocating enough space for them in that actual memory.
1:18:39
But there is a caveat. A lot of things, unfortunately, this week onward, can go wrong when it comes to memory. Your computer could be out. Maybe you have an older computer. Maybe you have a really fancy program that has so many variables, so many arrays that eventually you run out of memory. It's possible that malloc can fail. Something can go wrong, and malloc will not, in fact, return to you the address of the first byte of memory available.
1:19:01
Because if none's available, it's got to return something else. So, in cases of error, what malloc really returns to you is 0. I have no valid bytes for you. And 0 itself is a number. So that's a little confusing. And this doesn't really help with confusion-- what malloc returns, if an error happens, is null with two l's. This was a stupid design decision decades ago to call the character 0 N-U-L and the pointer 0 N-U-L-L, but this is where we're at.
1:19:31
So N-U-L-L is the address 0, and it almost always signifies something went wrong. We just need a special symbol to signify something went wrong when returning a value from malloc. So how can I use this? Unfortunately, now, just like in some of the problem sets thus far, when you've started to add error checking to when things can potentially go wrong, your code gets a little more verbose. But what I'm going to do here if I go back to VS Code, is the following. What can go wrong?
1:19:58
Well, if t ends up equaling null, that is, if it has a bogus return value in it that is not a valid memory address, then there's not much I really can do except return one just to signify error. I could print out an error to the screen. I could inform the user somehow, but if malloc returns null, I had better not proceed to try copying things from left to right into it because there is no memory there. That chunk of memory on the screen at bottom-right does not exist if malloc fails, of course.
1:20:30
So you don't want to go there and start blindly touching memory, let alone capitalizing memory that's there. So I have to start adding in some of these error checks in this case. And, in fact, even this is a little naive. It's probably not safe to even assume that the user typed in any string at all. Maybe the human just to be difficult or making a mistake and just hit Enter. So the length of the string is 0. You probably shouldn't try capitalizing 0 either.
1:20:53
And so what we should probably do down here to be super safe is only if the strlen of t is at least greater than 0, then go ahead and capitalize it. Otherwise, do not touch that memory either. In other words, starting this week and next week and even when we get to Python, you should start acquiring an instinct to code defensively. Things can go wrong in your code, in someone else's code, and if you do not handle those situations with ifs
1:21:20
or else ifs or the like, your computer will crash, the thing will freeze or the like. And, again, to tease the CrowdStrike example, if you screw up and you don't check the boundaries of something, the length of something, who knows what can happen? Because if you touch memory that does not belong to you, the typical behavior, again, is to crash, to freeze, to do some undefined behavior like that. Now I will say this is getting really annoying.
1:21:43
I mean, I've written what like 30-some-odd lines of code just to copy two strings. That's a little unfortunate when this is probably a pretty common thing to do in the real world. So it turns out there are library functions like this too. And, in fact, I can get rid of a lot of my code here for copying. And I can actually just call a function strcpy, S-T-R-C-P-Y for short, and pass in the destination, pass in the source, semicolon. And that will do all of for loop or the while loop
1:22:11
or however that person implemented it of copying one into the other. The ordering's a little weird. It is indeed destination comma source, but that saves me the trouble of doing all of that code myself. Questions then on what we've done here, the key details really being malloc and one omitted detail, which we'll come back to. Yeah. AUDIENCE: So, when you call-- or when you create a char *, and you create two right after each other, and you assign a string value, you showed us that--
1:22:43
DAVID J. MALAN: A really good question, let me summarize. If you allocate two variables that happen to be next to each other in memory, but maybe you type in, excuse me, a very long string for one of them, can one overflow into the other one? Short answer, yes. And we're going to talk about that briefly today. The code I've written is not vulnerable to that at the moment. And, in fact, among the things that get_string has been doing for us since week 1 is it actually
1:23:05
sort of crawls over the user's input, literally taking baby steps to make sure that we only allocate more memory, more memory, more memory for every keystroke that you type in. So, theoretically, there should be no way to crash get_string unless you type in more bytes than the system has even memory for. But, even that, we should be able to detect because we are somewhat inefficiently, but very conservatively trying to avoid the situation you described.
1:23:29
But it is too common in life is-- again, with CrowdStrike, you'll see that humans will make mistakes when it comes to the length of memory or arrays that we have. Now, I alluded to there being one mistake or omission here. Did I somehow not practice what I preached a moment ago about malloc and its cousin? AUDIENCE: You didn't free your memory. DAVID J. MALAN: I never freed my own memory. So, technically, this program has what we would call a memory leak, whereby
1:23:53
I'm asking for memory on line 11 via malloc, but I'm never giving it back to the operating system. Now, this is a bit of an overstatement, because, technically, when the program quits, it should automatically give everything back. But a lot of programs in the world keep running again and again and again, really forever, like a clock program or a web server or an email server and the like. And if that code that you or someone else has written asks for memory,
1:24:14
asks for memory, and never hands it back, freezes, crashes eventually because the computer will somehow run out of memory. So it's an easy fix. At the very bottom of this program, once and only once I am done using t in the first place, I can simply free t. And C itself-- or, really, the functions that we're using keeps track of how many bytes you asked for. You do not need to-- when freeing it, it will free that byte onward that you requested. So free does the opposite of then malloc.
1:24:46
All right, unfortunately, we have so much power at our disposal now lots of things can go wrong. But, thankfully, there are tools that help you find these mistakes so that if and when your program crashes, you don't have to just kind of stare at the screen or ask a TF or another human for help. You can actually use software tools that other people wrote that detect these common errors. And one of these programs that you're now
1:25:07
going to have access to besides printf, besides debug50, besides the rubber duck is a program called Valgrind, which is a command line program whose output is a little scary looking, but it will allow you to look at your program for memory-related errors. So let me go ahead and propose this. I'm going to open up a program that I wrote in advance here called memory.c. And, quite simply, in VS Code, it looks as follows. I have-- including stdio.h. I'm including stdlib.h so that I can use malloc,
1:25:38
and this program does nothing useful. It just demonstrates, as simply as I can, a bug. On line 6, I'm allocating a variable called x that's going to be a pointer to an integer. And I'm allocating space for three integers. So we haven't seen this before, but it just kind of does what it says. Give me memory for three of these things. What are these things? Well, whatever the size of an int is-- I know it's four, usually. So I could just write 4 times 3. But I'm going to generalize it.
1:26:05
sizeof is an operator in C that lets you figure out, what is the size of this type of variable? It's usually 4, but, on older computers, eventually on newer computers, it might not be 4, so I'm not going to write 4. I'm going to say size of int. So this whole line 6 gives me enough memory for an array of three integers, and it stores the address of the first byte in a variable called x. So what's x1 going to be? 72. What's x2 going to be? 73. What's x3 going to be? 33.
1:26:34
Even in these four lines of code, there's two bugs. Can you spot any of them. Yeah. What's that? Yes, so I did not 0-index my array. So that's sort of week 2-type of mistake. This should be x[0], x[1], x[2], and there's a second more subtle mistake.
1:26:55
Yeah. AUDIENCE: [INAUDIBLE] 0. DAVID J. MALAN: I don't have what? AUDIENCE: [INAUDIBLE] 0 at the end. DAVID J. MALAN: I don't have room-- oh, I don't have room for the 0, but that's OK because I'm dealing with integers only. I'm not strictly trying to treat this like a string. But good eye, but only relevant if I'm dealing with strings or char *'s. It's subtle, but we also talked about it like three minutes ago. Yeah, I didn't free the memory. So I called malloc, but I didn't eventually
1:27:20
call free at the end of my function, so at least two mistakes it would seem. Now, you can reason through this, and there's only four lines of code, so, eventually, you'd probably figure it out with some time in practice. But could a program help me spot these mistakes? Well, debug50 is not relevant here, per se unless your program crashes. debug50 can probably tell you on what line it crashed, but not necessarily why. What we need is a memory-related program called Valgrind.
1:27:45
And, to do this, to use it, I'm going to do the following. I'm going to run make memory. And if I do ./memory, at a glance, nothing seems to go wrong. It didn't even crash. But it's still incorrect. And especially if I have these kinds of bugs in larger software, it's definitely going to crash eventually. So let me do this instead. Let me run this program called Valgrind on ./memory. So, just like you run debug50 ./something, you run Valgrind ./memory.
1:28:10
Let me increase the size of my terminal window because there's going to be a lot of ugly output here for a moment and hit Enter. And you'll see a whole bunch of cryptic output and a lot of numbers, which largely aren't useful for us until we get to the error messages. So I ran the command up here. I saw all this crazy output. But what's germane? Well, here, I have invalid write of size 4. It's a little technical, but that just means I'm changing something that involves 4 bytes.
1:28:36
Well, what does that mean? Well, apparently my mistake is in memory.c line 9, and it's elaborating with some cryptic addresses, which, again, I don't really care about. But I do care about this. After a block of size 12 is allocated-- so there's 12, evidence that there's indeed an array of three ints, which total 12 bytes. So that's consistent. But what's going on? It's at line 9. Well, how did I somehow touch 4 bytes that I shouldn't.
1:29:02
Well, if I go back to my code by shrinking my terminal window, look at line 9, it did not like, as you observed, the last element of the array because I 1-indexed instead of 0-indexed. So, OK, I think my fix is going to be to change this to 0, 1, and 2, so 0, 1, and 2. But let's go back to the errors because there was another one on the screen. If I ignore anything I don't really understand in this summary, here's something. 12 bytes in 1 blocks are definitely lost in lost record 1 of 1.
1:29:31
More verbose than ideally it would be, but that problem seems to relate to memory.c line 6. So I'll admit, Valgrind output is sort of a big complicated mess, but there are little hints of diagnostically useful information, like invalid write of size 4 and the line number of the file. 12 bytes in 1 blocks are definitely lost in memory.c and line number. So those are the kinds of things you want to look for even if at a glance, it is and will look confusing.
1:30:01
So let me go back to now line 6, and, oh, line 6, even though it's not obvious what's wrong with this line, if I'm somehow losing 12 bytes, well, it must be a memory leak. So let me just have the intuition to go in and say, oh, eventually I have to free x because x is pointing at that chunk of memory. Let me now clear my terminal window down here. Make memory again, ./memory. And it doesn't seem to crash still, but it is more correct even though, at a glance, it seems fine either way.
1:30:30
Let me do now Valgrind of ./memory. Let me increase the size of my terminal window, clear the screen, and hit Enter. And now there's slightly less output. But what I really like is the sound of all heap blocks were freed, whatever that means. No leaks are possible. And even though there's still a lot of output there, I don't see anything glaring anymore. So Valgrind too this week and next week will be your friend, and all it's doing is helping check for memory-related mistakes in your code.
1:31:00
Questions then on Valgrind?
1:31:05
Yeah, in front. AUDIENCE: Can you set a condition before you create the memory? DAVID J. MALAN: Can you set a condition before you free the memory? You could. In this case, logically, there's no reason to because this program is so relatively simple that I do want to free it no matter what. But you can absolutely have conditionals in there, which you might in more complicated programs. All right, well, let's play around slightly more with these garbage values, to which I alluded earlier.
1:31:29
Let me actually close this. Let me code up a file called garbage.c just so we can make the point that there can be these so-called garbage values in a computer's memory that are really remnants of something else that has been at that location in memory before. And I can actually do this pretty easily. Let me, in garbage.c, include stdio.h. Let me go ahead and do-- whoops stdio.h. Let me go ahead and do int main(void) inside of my main function.
1:31:59
Let me just give myself an array of a lot of scores to come back to week 2 when we introduced arrays. Suppose I very, sadly, have 1,024 scores to keep track of over the course of college. I now might iterate over those as follows. For int i = 0; i is less than 124; i++. And, inside my for loop, let's just blindly print out those values. %i backslash n scores[i]. The problem, though, is that I have neither hard-coded those actual scores into this program like we did in week 2, nor have
1:32:32
I prompted the user for the scores with get_int or anything else. So who knows what I'm going to be printing 1,024 times. Well, let me open my terminal. Let me do make garbage, sort of pun intended. Let me increase the size of my terminal window, ./garbage. And I should see 1,024 values that eventually will be my scores, but who knows what they are now. Enter, it's a mix of some really good and some really bad scores, it would seem. Some 0's, some small numbers, some big numbers.
1:33:01
My god, some negative numbers, which isn't good for scores, but they're all over the place. And if I scroll up, I could count them. There's indeed going to be 1,024 of them, but their garbage values and that I can't make head or tails of what they actually are. As an aside, this has nothing to do with C, but the operating system Linux that we're using here does have commands that you can run if you are getting overwhelmed by output. So, for instance, if I run garbage again,
1:33:25
if you know there's going to be more output than you can see at once and you don't want to have to bother scrolling back through time, you can actually do what's called piping it to a program called less, which, as the name suggests, will show you less of the output at a time, one screenful at a time. So if I hit Enter now, I only see the first screenful until I hit space, space, space, space, and so forth, and it will paginate the output for me. And I can just hit q when I'm done with that.
1:33:52
So it doesn't change my code. It doesn't change my program. It's just a handy command line trick if you're ever overwhelmed by the amount of output there. But these garbage values can really get us into trouble. And, in fact, let me propose to consider another program that's a little arbitrary, but it's going to use some of today's building blocks. So here's a main function. And, at the top couple of lines here, I'm doing this--
1:34:14
I'm creating a variable called x that's going to store the address of an int. I'm creating a variable y that's going to store the address of an int. So far, so good. I haven't assigned them any values yet. But that, in and of itself, is not problematic. I can always assign them values later, like any variable. I'm now going to allocate enough bytes for the size of an int. You and I know it's probably going to be 4, but I'm doing it dynamically asking for the size of an integer.
1:34:37
And I'm storing the address of the first byte in x. But, notice, what I'm not doing is storing anything yet in y. The next line of code here, I'm using the sentinel value 42 and storing that at the location in x. So the dereference operator says whatever address you got from malloc, go there, and put the number 42 there. This next line says go to the address in y, and put the number 13 there. But I've highlighted in red this time. Why? This line will probably crash. Why intuitively?
1:35:11
AUDIENCE: We haven't got one. DAVID J. MALAN: We haven't given y a value. I didn't copy s's value. I didn't malloc anything for y. It contains a garbage value. Maybe it's 0 like we saw on the screen. Maybe it's a really big number. Maybe it's a big negative number. Who knows? But that's like saying go there, and put the number 13 in some random unlucky location. And, again, program's probably going to crash, freeze, or something else. The other lines here are OK.
1:35:35
Eventually, I get around to copying x into y, giving it a valid value and then going to y's value and assigning it to number 13. So that one line of code was the problematic one, ultimately. So what's nice about this code is that it actually happens to line up perfectly with a fun video that our friends at Stanford University put together that's about two minutes long. And it introduces a character that's well known in computer science spaces as Binky. So a Professor Nick Parlante of Stanford,
1:36:04
spent some time doing some claymation to bring exactly that code and exactly that problem to life, if we could dim dramatically the lights. [VIDEO PLAYBACK] - Hey, Binky! Wake up, it's time for pointer fun. - What's that? Learn about pointers? Oh goodie! - Well, to get started, I guess we're going to need a couple of pointers. - OK, this code allocates two pointers which can point to integers. - OK, well, I see the two pointers, but they don't seem to be pointing to anything. That's right.
1:36:34
- Initially, pointers don't point to anything. The things they point to are called pointees, and setting them up is a separate step. - Oh, right, right. I knew that-- the pointees are separate. So how do you allocate a pointy? - OK, well, this code allocates a new integer pointee. And this part sets x to point to it. - Hey, that looks better. So make it do something. - OK, I'll dereference the pointer x to store the number 42 into its pointee.
1:37:02
For this trick, I'll need my magic wand of dereferencing. - Your magic wand of dereferencing? That's great. - This is what the code looks like. I'll just set up the number and-- - Hey, look! There it goes. So doing a dereference on x follows the arrow to access its pointee, in this case, to store 42 in there. Hey, try using it to store the number 13 through the other pointer y. - OK, I'll just go over here to y and get the number 13 set up and then take the wand of dereferencing and just--
1:37:38
[BUZZER] Whoa. - Oh, hey, that didn't work. Say, Binky, I don't think dereferencing y is a good idea because setting up the pointee is a separate step, and I don't think we ever did it. - Eh, good point. - Yeah, we allocated the pointer y, but we never set it to point to a pointee. - Hmm, very observant. - Hey, you're looking good there, Binky. Can you fix it so that y points to the same pointee as x? - Sure, I'll use my magic wand of pointer assignment.
1:38:08
- Is that going to be a problem like before? - No, this doesn't touch the pointees. It just changes one pointer to point to the same thing as another. - Oh, I see. Now y points to the same place as x. So, wait, now y is fixed. It has a pointee, so you can try the wand of dereferencing again to send the 13 over. - Uh, OK, here goes. - Hey, look at that. Now dereferencing works on y. And because the pointers are sharing that one pointee, they both see the 13. - Yeah, sharing, whatever.
1:38:38
So are we going to switch places now? - Oh look, we're out of time. - But-- [END PLAYBACK] DAVID J. MALAN: All right, so Binky's purpose in life is really to make clear that bad things can indeed happen when you touch memory that you shouldn't, including things that we now know as garbage values. But there's even other problems, but also solutions that we now have access to thanks to our newfound understanding of memory and, in turn, pointers. So it's been very common over the past few weeks,
1:39:02
especially last week, to have to swap values. When we were doing bubble sort or selection sort, we kept having our human volunteers swap locations. And, in the computer's memory or in our pseudocode, we had to have two variables or two values swap locations as well. For this, we thought we'd motivate folks. We can offer you either a little Mario mushroom or question mark if we can get one more volunteer today to act a little something out with me here. Don't all raise your hands at once.
1:39:28
How about-- I saw the Harvard shirt, is it? That shirt, yes. Yeah no you. Yeah, come on down. Yes, the one who wanted to keep using string as a typedef before. All right, maybe a round of applause to break the awkwardness here. [APPLAUSE] All right, and, for the other volunteer who had your hand up, catch my eye next time too. But, for now, we just need one of you, and come on up.
1:39:53
All right, you want to introduce yourself to the world. GABE: Hi, my name is Gabe. DAVID J. MALAN: Gabe, OK. And a little something about yourself. GABE: I live in Thayer. I'm a freshman. DAVID J. MALAN: Nice, all right. Well, good to meet you. Come on over here where we have two glasses of water. One is pink. One is blue. And each of these effectively represents a variable that contains some value, either pink or blue. Could you go ahead and swap the two values of these glasses?
1:40:18
OK, that's technically just like moving the variables around in memory, but I'd really like you to get the pink water in the blue glass and the blue water in the pink glass instead. So let me undo that.
1:40:31
You're hesitating. Why? GABE: Because if I pour the blue in the pink, then they're going to blend together. DAVID J. MALAN: Yeah, and you're going to overwrite the value with the other. And so we're going to lose information in that case. OK, OK, so this was a bit of a setup. So let me get you a third glass or a temporary variable, if you will. And if you want to verbalize how you would solve the problem now with this third variable. GABE: OK, so I'm going to pour the blue into the new variable
1:40:59
and then pour the pink into my old blue cup. DAVID J. MALAN: Nice. GABE: And then pour the blue back into the old pink cup. DAVID J. MALAN: Very nice. I think that warrants round of applause, if we could. [APPLAUSE] OK, nicely done. GABE: Thank you. DAVID J. MALAN: Thank you. OK, which would you like? GABE: Ooh, this one. DAVID J. MALAN: All right, so thank you to Gabe. So this was all to make the point that swapping is not that hard.
1:41:28
And we all have an intuitive notion of how to do it, but we do need, it seems, like a temporary variable. And that, actually, maps pretty cleanly onto C code. So how might we do this in practice? Well, if we wanted to implement a actual function in C that does swapping, for instance, I might do--
1:41:47
if we want to actually do something in C that involves swapping, I might do something like this. Avoid function because I don't need to return a value. I just need to do some work. Function's called swap. It's going to take in two values int a and int b. And the goal in life here is to swap a and b. It's actually pretty straightforward. I could actually do lines of code like this calling a and b, the two inputs like the pink and blue glasses, temp, or tmp for short for the temporary variable.
1:42:09
And, just as Gabe did, I can store in the temporary variable one color of liquid or the value of a. I can then change a to be that of b. And then I can copy the value from the temporary variable to b and, at which point, I don't care about tmp anymore. This code is correct. It would swap those values just as Gabe did with the glasses of water. But it's only going to work inside of the scope of swap. And this is the catch. Recall that, when we introduced the notion of scope
1:42:36
earlier a few weeks back, we said that variables really only exist in the context of the curly braces in which they're defined, or, in this case, as part of the arguments passed into the function. So this successfully swaps a and b. But if main or any other function is using swap, it's actually not going to have any useful effect on the original values of a and b. In fact, let me go over to VS Code here, where, while Gabe was doing that, I whipped up this program in advance.
1:43:03
And it looks like a lot, but it does something relatively simple. I've got main, which declares two variables x and y, values of 1 and 2. I'm then just printing out x is this, y is that. I'm then calling a swap function, and then I'm just printing the same thing-- x is this, y is that, the whole point being, hopefully, it'll say the opposite the second time. What is the swap function? Exactly what I just proposed earlier, which is exactly what Gabe just did correctly with the glasses.
1:43:30
But, as you might see where we're going with this, if I go into my terminal window and say make swap, ./swap Enter, it doesn't actually seem to affect the values of x and y. It does affect the values of a and b. And I can see this if I use our old friend debug50. Let me go ahead and set a breakpoint inside of swap. Let me run debug50 on ./swap, Enter. And, just to demonstrate what's going on here, let me step through a few of these lines of code as follows. So notice 1 at top left.
1:44:05
tmp has some bogus value initially. It's a garbage value. It's like putting some random color inside of the glass. But I kept it empty because, in the real world, we need space for the colored liquid. But a is 1, and b is 2. Why? Because we passed in x and y, respectively. If I now step over line 17, notice that tmp changes to 1. If I step over line 18, a changes to 2. If I step over on line 19, b changes to 1. So a and b, per Gabe's algorithm, were swapped correctly.
1:44:36
But if I continue running this program all the way to the end, ultimately, I got, because of this second printf, that x is still 1, and y is still two. So a and b were changed clearly per the debugger, but x and y were not. So why is that? Well, it turns out that the answer to that too relates to memory. And code like this, at least if encapsulated in a function, is not correct precisely for the matter of scope because we're changing the values of variables
1:45:04
that are local to the swap function but has no effect on main that's actually using this function. And the reason for that is a term of art, when you pass arguments to functions, you're generally passing things by value. You are passing in copies of those values. So, when you pass an x and y, you're really passing in a copy of x and a copy of y that you can do anything you want to. And we're calling them a and b in the context of swap but that has no effect on the original versions of x and y.
1:45:33
What's really going on, though, can be thought of again in terms of the computer's memory. So here's a chip of memory. Let's zoom in and abstractly on the grid as we keep describing this, and consider that we can use this memory in bunches of different ways. But the world has standardized how we use computers' memories when running programs. And we tend to use this part of memory at the top, so to speak, in certain ways and this type of memory at the bottom in other ways.
1:45:57
And if we understand what those ways are, we can actually infer deductively why this function is not working as intended. So it turns out-- let's even get rid of the individual bytes because we don't really care about numbers for now. It turns out that, when you double-click a program on your Mac or PC or tap an icon on your phone or run ./something on your code space, the computer automatically loads the program's machine code, the 0's and 1's that someone else compiled or maybe you compiled
1:46:25
into the top of your computer's memory, so to speak. It's not literally the top because who knows how the thing is oriented but, just for the sake of discussion, up here. What else gets loaded into the computer's memory? If your program has any global variables defined outside of main, by convention, they go below the machine code that was loaded into memory. What else? If you end up using malloc in your code, that memory comes from this location here, which we didn't do until today.
1:46:52
But, actually, it turns out that get_string has been using malloc all this time since week 1 because that's how we're getting an arbitrary amount of memory for everything you might type in at the keyboard. The heap, though, so to speak, grows downwards. So the more and the more and the more and the more you call malloc, the more stuff that gets filled up top to bottom in the so-called heap. But there's one last region of memory, generally, called the stack, much like a stack of trays
1:47:16
in the cafeteria or dining hall, that sort of works its way up as you continue putting stacks of tray and tray and tray on top of each other. The stack, so to speak, grows upward. And the heap and the stack are used differently. The heap is indeed used for malloc, but the stack is used any time you call a function. Anytime you have local variables, they use memory down here. So, in particular, for the code I just wrote a moment ago where I had a main function and a swap function,
1:47:42
the stack gets used to implement this kind of logic as follows. I first-- unbeknownst to me, my computer does this for me, I get a chunk of memory at the bottom of my computer's memory space that contains any command line arguments if we had int argc and char and string argv like a couple of weeks back or if I have any local variables like x and y. If I then call a function like swap, swap gets its own chunk of memory, its own frame of memory above main in the computer's memory.
1:48:14
So it's like putting down a main tray from the dining hall and then a swap tray on top of it from the dining hall. Each of them contains their own local variables x and y here a and b here. And you can kind of see where this is going already. If x and y live here, but we're changing a and b here, well, obviously, we're not changing x and y down here. Well, let's be a little more specific. In the main function, when I have two local variables like x and y,
1:48:36
it's like having space for them in the computer's memory. And, initially, I had values 1 and 2, respectively. When I then call the swap function, that had two local variables of its own, technically, arguments passed in which, because I'm passing by value, gets copies of x and y called a and b. But the values are going to be the same initially, 1 and 2, respectively. But then, in the three lines of code that represent what Gabe did with the bottle-- the glasses of water does
1:49:02
is we have a temporary variable, a third, still in the same frame of memory. And I signed with this code here-- let me step out of the way. This first line of code stored the value of a in tmp like this. The next line of code stored the value of b in a like this, at which point, unfortunately, they're identical, but no big deal because, like Gabe, we kept the temporary variable around. And then we can store the value of tmp inside of b.
1:49:31
Now, as an aside with respect to the debugger we pulled up earlier, as well as a couple of weeks back, when you've looked at the top left of the debugger window and you can see your local variables, what you're seeing in the debugger is either these variables if you've set a breakpoint in main or these variables if you've set a breakpoint in swap. The debugger is just showing you what variables are in scope. What does scope really mean? It's a slice of memory at that moment in time, effectively.
1:49:58
And we've been simplifying it verbally by saying what's between the curly braces. But that's the simpler way of describing really this. Now we don't care about tmp eventually, but what we do care about is having swapped these values. But, unfortunately, as soon as swap returns, well, main's x and y are literally left unchanged because we only passed in copies thereof. So the fundamental problem seems to be that the swap function is logically
1:50:23
correct, but it has not been given access to the locations of x and y in memory. What swap really needs is a treasure map, so to speak, that leads it to the actual location of x, the actual location of y so that, using the * operator, it can go there and go there and swap the actual values inside of main's frame of memory. So what we really want to do is what computer scientists would call pass by reference or pass by address would be the same thing in this case, whereby
1:50:56
what I want to do is not this code, per se, which is logically correct, but doesn't fundamentally change the caller's variables, x and y. Watch the delta here. This is correct. And it looks crazy scary at a glance because there's all this new syntax, but it's really just the same syntax from the start of today used a few different places. What I'm saying now in this correct version of swap is that A is not going to be an int, per se. It's the address of an int.
1:51:25
And b is going to be the address of another int. This is my treasure map, whereby a and b are going to contain the addresses of x and y. What am I going to do? Well, tmp is still just an int. It's still just an empty glass. But if I want to store the value at a in tmp, I have to go to a and store it in tmp. I have to go to b and go to a and put the latter in the former-- the former in the latter. I have to-- the first and the second.
1:51:52
Then I go and get the value of tmp and put it at the address in b, so exact same logic, exactly what Gabe did, just way more syntactically involved. But, again, it's just using pointer declarations up here and pointer dereferencing down here to go to those locations in memory. And, in fact, if I make this change in my own code here-- let me go back to VS Code. And let me hide my terminal. Let me make these changes, so pass in the address of an int, the address of an int dereference a,
1:52:26
dereference b, dereference a and dereference b. It's almost done, but I do have to change one more line of code. And, based on what we've discussed thus far, how does line 11 need to change? I no longer want to pass an x and y. AUDIENCE: The address. DAVID J. MALAN: The address of x and the address of y, which involves the syntax &x and &y. So, again, syntactically, way scarier than it once was, but it's just the simple building blocks.
1:52:56
Get me the address of x, and then go to that address as with the * operator. So let me open my terminal window again. Let me do make swap, Enter. It's erroring now, but why? I've made a subtle mistake. It doesn't like the fact that I've passed in the address. But, wait a minute, let me scroll up. What else needs to change? AUDIENCE: [INAUDIBLE] DAVID J. MALAN: The prototype here. So this also needs to be matching the actual implementation.
1:53:21
So sort of newbie mistake, but I think now if I do make swap again, it does compile. ./swap, I should see x is 1, y is 2, and then, hopefully, indeed the opposite. So this version of swap correctly swaps the value because now I have a correct understanding of what is going on inside the computer's memory. And, indeed, if we look at this code now in the context of those, the stack frames, let's see what now happens. So here is again the same setup. Main has variables x and y equaling 1 and 2.
1:53:52
Swap gets called, but what are a and b? They're no longer the values of x and y, but the addresses of x and y. I don't care what those addresses are. So I'm going to abstract it away with some simple arrows. But these are the treasure map I keep referring to, the breadcrumbs, however metaphorically you want to think of it. a and b Now lead to x and y, so you're passing things in by reference, so to speak. And, therefore, swap can manipulate those values.
1:54:19
Now, as an aside, pass by reference is really the same idea as pass by value, but the values you're passing in are the addresses instead of the actual value. So it's sort of just context dependent as to how you think about that. But passing by reference means, really, you're passing in by address. All right, so, with that said, step by step, what's happening? I'm going to a, which is going to contain the value 1, and I'm going to store that in tmp. So what I should see in tmp still is 1.
1:54:48
Now I'm going to go to b, and what I should see at b is 2. And I'm going to put it at * a, which is the same thing as 2 here. Then, lastly, I'm going to grab tmp, which is 1. And I'm going to put it at b which is like following that arrow and changing that to 1. And this then pictorially is why my new version of the code indeed works as expected. And, better still, when swap is all done and that frame of memory is taken away-- it's still physically there, but we don't care about it anymore,
1:55:16
so we might as well think of it as just disappearing-- the change has, in fact, permanently affected main's version of x and y. Questions then on this trickery?
1:55:33
Yeah. AUDIENCE: Is the first [INAUDIBLE] you say that it [INAUDIBLE] things all together? Or is it still [INAUDIBLE]? DAVID J. MALAN: Sorry, a little louder. AUDIENCE: As soon as the function returns, does its stack disappear [INAUDIBLE]? DAVID J. MALAN: Oh, good question. When a function returns, does its stack disappear? Typically no. You still have remnants of all of those values that were once there unless the compiler or the computer
1:55:52
has sort of scrubbing that memory, which is not typically done for performance reasons. And so there could be remnants of past things. So, as an aside, your mind is actually going in an interesting adversarial way, place because suppose there was some function that you're calling that involves passwords, for instance. And the user types in their password, and their password is stored at that location in memory. Even after that function returns, if the code
1:56:12
is not implemented with any kind of rigor in place, you could somehow maybe, if you have malicious access to the code, access that memory location where there's the garbage value. But that garbage value is useful because it's someone's actual password, and, in fact, that's a threat that has indeed happened from time to time. So, here then, to recap the bad code but logically correct, just doesn't get the job done, the green code, of course,
1:56:36
does get the job done for exactly those same logical reasons. But there's another problem we've now created, even as we understand how the stack's working. And I claim that the heap is where malloc takes memory from. Having two arrows pointing at [INAUDIBLE] does not seem like a very good design because if you keep using heap, heap, heap, heap, by calling malloc a lot, you're going to eventually overflow the stack. Or if you call lots and lots and lots and lots of functions,
1:57:00
as you might with recursion or some other technique, you might overflow the stack, like a big stack of trays eventually kind of toppling over and touching things that it shouldn't either. Unfortunately, there's no real solution because you only have a finite amount of memory, so it doesn't really matter if things go this way or this way. Eventually, you're going to either run into other chunks of memory or run out of memory altogether. So, strictly speaking, this isn't such a bad thing
1:57:21
unless you let things get out of control and you don't keep track of how much memory you're using or, defensively, make sure you're freeing it as much as you can. And there are terms of art out there, like heap overflow, which means if you call malloc too many times, you might somehow overflow some other area of memory with the heap. Some of you might know a popular website called Stack Overflow. Well, what is the etymology of that website? Stack overflow is when you call so many darn functions
1:57:47
that they overflow each other and maybe hit the heap, or overflow each other in some way. You're overflowing the memory region known as the stack. These are generally examples of what are called buffer overflows, where buffer just means a chunk of memory that you're using for some purpose. And so a buffer can certainly overflow another, especially if you're treating it as a chunk of memory this big, but you start poking around past the end of it. It's like allocating an array for four characters
1:58:15
but trying to print the fifth or the sixth or the hundredth or the thousandth. If you've not asked for it, you're overflowing the buffer you've been given. So an array is just a buffer. And YouTube and Netflix, they all have buffers in the colloquial sense in that they might pre-download a few seconds or minutes of video, storing it in a chunk of memory, like an array, or maybe somewhere on the heap. But the point is, a buffer is a finite size,
1:58:36
and you can potentially overflow it by going past the boundary of it, past the end or maybe even past the beginning. And thus was the issue with the real world a few months back with CrowdStrike. So this is very popular security-related software, ironically, that a lot of the world has installed on their servers to keep themselves safe. For those unfamiliar, unfortunately, this very software crashed some months back, taking down very important systems with it,
1:59:03
including Delta Airlines's site and so many other companies. And this cost the world millions of dollars, probably in lost labor and effort because systems went down, sales were lost, human time was incurred. And it boiled down, in retrospect, to the stupidest of bugs, if I might say. If you read through their very long PDF, their postmortem that describes what exactly went wrong, which took a few weeks, I believe, to come out, there was this paragraph here,
1:59:26
which actually sounds like a lot of big words. "Sensors that receive the new version of channel file 291, carrying the problematic content, were exposed to a latent out-of-bounds read issue in the content interpreter." Like, the real interesting part is the last sentence. The content interpreter expected only 20 values. Therefore, the attempt to access the 21st value produced an out of bounds memory read beyond the end of the input data array and resulted in a system crash.
1:59:52
So, literally, even though you're only in a class like this for a couple of months time now, they had an array of size 20, and they wrote code that tried to access the 21st element. They touched memory they shouldn't have. The software froze or crashed. Therefore, the system itself froze or crashed and cost the world millions of dollars in downtime and other side effects because of one off-by-I error. So it's a very possible danger to trip over. And among the downsides of languages like C
2:00:22
is that they make it very easy to do this. There is nothing in C stopping you from doing this. And a few other languages allow this as well. Other languages like Python and Java generally prevent you and me from doing this. Why? Because humans, for years, were writing so much darn buggy code that we realized, wow, we should probably build into the programming language defenses against this stuff so, with the right language and the right know-how, you can avoid these problems altogether.
2:00:47
But, in this particular case, they had code that similarly was not sufficiently tested. They didn't have a check50 to tell them a priori whether or not the code was correct. And so they shipped this to computers around the world. As an aside too, this is one of the dangers of automatic updates. If you have this on your phone or your Mac or PC, let alone your corporate servers, if you update automatically your systems but the update itself is buggy,
2:01:08
you can therefore take down your whole system, personally or professionally. There's a lot of real-world implications to that business decision, they made, it seems to update so unilaterally as well. So beware. But these things happen very really in the real world. OK, so let's take things down back to CS50 land here. Here was the functions, the training wheels that we've been using since week 1. And let's just consider for a moment how one of the most powerful of these does--
2:01:36
let's consider for just a moment how one of the simplest of these actually works, namely get_int. So it turns out, in C, it's not that hard to get an int or a char or a float, relatively simple, at least in a safe way. Strings are the scary one because who knows how many characters the user's going to type in, and you would seem to have to decide in advance, do I want room for one character? Four characters, 100, 1,000? What if I get the number wrong, and they type in a really long paragraph.
2:02:01
Ints and chars and floats are easy because they're 4 bytes or 1 byte or 4 bytes. You sort of know in advance. So let me propose that we implement a simple problem-- a simple program that really kind of implements the idea of get_int. So, first, let me open my terminal and clear it. Let me open a new file called get.c because I'm going to implement my own functions for getting input. I'm going to go ahead initially and actually still use cs50.h, and I'm going to use stdio.h.
2:02:31
And then, in main, I'm going to go ahead and very simply, as in week 1, do this int n equals get_int, and just prompt the user for n, so nothing interesting there. And then, quite simply, I'm going to print out using %-- I'm going to print out using %i the value of n, passing in n. So, again, week 1 stuff, no memory-- no explicit use of memory or pointers here yet. Make a get, ./get, type in 50. Program, for now, seems to work. But suppose I take away, truly, the training
2:03:04
wheels, not just for the keyword string, but for the get_int function as well. And I take away this header file, which means get_int no longer works. How could I implement this instead? Well, without CS50's training wheels, you can still solve this problem. You can declare an int called n. And don't give it a value initially because you want it from the user. I can then prompt the user with a printf n colon space with no newline because I just want a blinking prompt for the user
2:03:28
which get_int does for you automatically, otherwise. And I can use a function called scanf to scan the user's input for some format string, so for some type of formatted text. Maybe it's an int, a float, a string, or something else. So scanf is sort of like the opposite of printf. printf prints something. scanf reads something from the user themself. All right, so how can I use this? I can call scanf. I can say, what do I want to scan from the keyboard, so to speak?
2:03:56
And I want to scan in an integer from whatever the human types. Where do I want to put that integer? Well, I can't just say put it in n because you can't change-- I want n to persist. cs want to tell it to go to the address of n and put it there wherever there actually is in memory. So, again, just like with swap, if I want another function to be able to change my variable, I can't just hand it the variable, I have to hand it the address of my variable. And scanf is designed to expect that.
2:04:23
Now it's my last line. I can print out n colon %i backslash n, and now print the value of n. So it's a bit more of a mouthful. I've got like two, three lines instead one with get_int, but I think it'll work. Let me do make ./get and type in 50, for instance, Enter. And it does seem to work. And, effectively, this is what get_int is doing. get_int is a little smarter because, for instance, if you don't type an int and you type in cat or dog or bird or something else, weird things will happen.
2:04:55
So we make sure that if you don't type in something that's actually an int, we prompt the user again and again and again using our own loop. So we sort of handle that error checking for you. But if I want to do this with a string, how might I go about doing this? Well, let me go back into my program here after clearing my terminal. And let me just kind of do the same thing, but with strings. I could say string s, but we strings don't really exist as a data type.
2:05:20
So I'm going to more explicitly say char * S. That's effectively a string or a placeholder, therefore. Let me print out a prompt for that string, just say s colon just because I want the user to type in a string for me. And now I'm going to use scanf again. What do I want to read from the user? Well, I want to read a string. And so, just like printf, I use %s to scan a string from the human's keyboard. And now, after that, I need a place to put it. Well, I think I want to put it in my string s.
2:05:47
I don't need an & here because s is already a char *. It's already the address of a string, if you will. But now if I go and print this? I'm going to say s, %s backslash n just as before. So it's the exact same logic. But this line of code is now dangerous. And this is why we give you get_string. And this is why more of the world should use libraries instead of doing this. Why is this line of code on line 7 dangerous? Or undefined what it will do? Yeah, in the back. A little louder.
2:06:18
AUDIENCE: It doesn't know when your string is going to end. DAVID J. MALAN: It doesn't know where my string's going to end. Or, more specifically, it doesn't know how much memory is available for that string. At the moment, the only memory I've allocated implicitly is 8 bytes for the pointer called s. So I have-- I'm ready to jot down in memory where I want to put this string, but I never initialize s to anything. Previously, when I wanted to initialize S to something, I could,
2:06:43
for instance malloc some space, Or I could even do something' like I could specify that oh, let's get out of the pointer business today. And let's actually just say that s is an array of 1,000 characters. And that would mean I have 1,000 places where I can put that chunk of memory. So turns out there's an implicit relationship between pointers, as we've seen today, and arrays whereby you can treat one as the other. But, for now, let me stick with this model of making clear
2:07:08
that I did not call malloc. And so S contains a garbage value, which is like saying put whatever the user types over there, it's random, it's a garbage value. And that's probably going to cause the computer to crash. Not always. And I don't know what to expect today, but let's try this. Make get./entr Enter. Let's type in. I exclamation point, I got lucky it still worked. Let's do something random. Like just type a c of characters that will hopefully
2:07:35
overflow the buffer that doesn't even exist, enter I. Got lucky, but if I do this again and again, I ideally, that would have made an educational point. But, again and again and again, eventually it will probably crash on me. s certainly incorrect. And I bet we could figure this out with Valgrind if we start poking around with that tool as well. S? What's the solution here? Or what's really the issue? Well, if we consider where we started, if here's my memory,
2:07:59
let me actually put a lot of Oscar the grouch's here to make clear that before you use memory. It' effectively garbage values. Who knows what is there. So in my first program, when I created a variable n, I actually used 32 of those bits, or four of those bytes to put a legitimate pattern of 0s and ones to represent the number 50. So that part was good. But when it got to the string version, I allocated space for the pointer, 8 bytes, s I said earlier,
2:08:24
but I never initialize s to anything to malloc, to an array, literally nothing. So S's value is literally this sequence of s values, so who knows what it is pointing to. There is certainly no memory allocated elsewhere, like in the heap, for whatever the human actually types in. So this value's effectively garbage. And this is the best I could do with squiggly lines, who knows where it's pointing. Certainly no where valid. And so, in this case, I got lucky.
2:08:49
It did not crash, but the more and run the code, the bigger the input it is. Odds are this will in fact crash ultimately on me. So how can I avoid this? Well, if I go back into VS Code, I could just allocate space myself and say, equals malloc of 4, but they're still going to be a danger there even if at the bottom, I do 3F because I only have allocated space for 4 bytes. If the user types in 5 or 50 or 500, who knows what's going to happen? I'm going to overflow my buffer of size 4.
2:09:21
I could do this another way. I don't have to use malloc. I can use week two stuff. I can, again, as before, just say S-- maybe not 1,000, but 4. That gives me an array, which is a chunk of memory of size 4. But what happens if I overflow that buffer? Bad things will happen. And so this is why we still use and would encourage you to keep using get_string because it avoids overstepping the boundaries of any buffer. We literally, as I acted out before, take these baby steps in code.
2:09:47
And every time you type a character, essentially we call malloc again and again and again. And it's a little inefficient, but we call malloc as many times as we need to grow enough space in the heap for whatever the human types in, whether it's 1 character, 4, 4,000, or more, It's just really annoying to write out. And, in fact, the code is open source, but it's a decent amount of logic just to do something relatively simple. Languages like Java and especially Python
2:10:12
make life so much easier with input and output. And we'll get to that in a few weeks' time. Any questions then on scanf and, really, why we've been using these training wheels? Yeah. AUDIENCE: [INAUDIBLE] DAVID J. MALAN: I only heard part of that. Would it be valid to use malloc and just allocate a really big number? So that just kind of kicks the can down the road. But I bet whatever number you come up with, I could if I copy-paste enough or just type, type a lot,
2:10:43
I could overflow that buffer still by just typing in longer input. And, worse, you're now wasting memory because you only have a finite amount of memory. If one program is using all of this memory just in case some crazy user types in way too much-- I mean, most of the time, you might be slowing down the computer, or at least wasting memory as well. So get_string does that too. We only allocate what memory you need, ultimately,
2:11:04
even though we end up allocating and freeing a lot of memory along the way. Really good question. All right, so let's transition then to a final topic that's going to set you up really for problem set 4, in which case you'll be exploring something specifically known as file I/O or file Input and Output. And we've deferred playing with actual files where you can save files and open files until now because you actually do need pointer syntax in C to do that with files.
2:11:32
In Python, world's going to be easier in a few weeks' time when you don't even need that complexity. But, for now, we'll explore the idea of file input and output as follows. There are a bunch of functions that come with C related to files. And here's just a short list thereof. But you can infer from the names what these do in code because they're operations you're familiar with in the real world, like opening a file, aka fopen; closing a file, aka fclose; printing to a file,
2:12:00
aka fprintf; and a bunch of others as well. So any function that starts with an f probably means that it operates somehow on files, whether it's text files or binary files with 0's and 1's, these files, these functions tend to be involved. We'll see with this, how we can now create some of our own files. So let me go ahead and do this. Let me go back to VS Code. And let's make, in the spirit of week 0, my own actual phone book in C. Let's
2:12:28
write some code that allows me to save in a file someone's name and number so that it actually persists over time. And I'm going to go ahead and call this phonebook.c. And, in this file I'm going to include just to make life easier still for today-- because we've seen that scanf is not really your friend. We'll use get_string again to include cs50.h, stdio.h, and also string.h, which might be useful. int main(void) again. And, inside of main, let's do this. Let's first-- whoops.
2:12:57
Let's first open a file called phonebook.csv. Most of you are probably familiar with CSV files. They're like lightweight Excel-- they're lightweight spreadsheet files that can be opened in Excel, Google Sheets, or Apple Numbers or the like. It just means Comma-Separated Values, or CSV. So I can make a very simple file like this myself, but the syntax is going to be a little new. It turns out, weirdly, in C, there's a data type called FILE in all capital letters for really no good reason.
2:13:25
I'm going to then declare a pointer called file in all lowercase, but I could call it anything I want. And I'm going to set it equal to the return value of calling fopen for file open. And I'm going to specify that I want to open a file called phonebook.csv in, let's say, write mode, quote, unquote, "w". And I know this from the documentation for the function that w means write. And that's why I'm passing it in as the second argument. Now let's go ahead and do this.
2:13:51
I could do string, but we know strings aren't really a thing, so char * name equals get_string and prompt the human for their name. Then let's do char * number and prompt the human for their number. And then I want to save the human's name and number in this file like I'm adding friends to my contacts. Let's go ahead and do not printf but fprintf, passing in file as the first argument, which is unlike printf. printf, obviously, just goes to the screen by default.
2:14:20
But fprintf needs to know what file you want to print to. I want to print out a string that looks like a string comma another string and then new line. So just like printf lets format what you're printing. fprintf lets you format what you're saving as string comma string and then a new line. The last things I'm going to pass in are the values for those placeholders. Store the name and store the number semicolon. And then, lastly, let's go ahead and close the file.
2:14:47
So it's not that many lines of code, but this is code enough to prompt the user for a new name, a new number, save. I could run it again, new name, new number, save. And, just to make this clear, let me go ahead and do this. Let me open up phonebook.csv, which doesn't yet exist. Let me kind of split the screen here, which, if you haven't discovered, you can do by just dragging the tabs up and around, so I can see both at once. Let me do make phonebook, Enter. ./phonebook Enter.
2:15:16
And I'll do how about John Harvard, Enter. And now let's see, +1-949. What's his number? Ah, line-- Rongxin, do you remember? Does anyone-- has anyone texted this number yet? Do you have it saved? This is not important, but I'd like to be consistent. Yeah. AUDIENCE: 949-468-2750. DAVID J. MALAN: Thank you. And the 2750 spells CS50 so Enter, and now notice what happened at top right. In my CSV file, I added a name to the phone book. Now, let me run the program again because there is a bug.
2:15:57
I'll put in my name now, and I'll just do, let's see, plus 1 617-495, I think we used, 1000 last time, Enter. But, notice, John Harvard disappeared. And that's because I chose to write to this file. But there's another mode in which I can write data. I can actually use a for append, which is probably smarter. Let me run my program a third time and put John Harvard back. So John Harvard enter, +1-949-468-2750. Oh, yes. thank you. Someone caught my mistake before I did. I didn't compile it again.
2:16:31
OK. Control-C, make phonebook, Enter. Now, let's rerun ./phonebook. All right, Here we go. John Harvard, we'll put him back. +1-949-468-2750, Enter. OK, that's in there. Let's run it one more time for myself, David Malan, +1-617-495-1000, Enter. And now it's indeed appending to the file. So if you've ever used Excel or Apple Numbers or Google Sheets, and you're adding rows to the file, or you're literally clicking like new contact on your Android phone
2:17:03
or your iPhone, effectively, what's happening is Apple or Google wrote code like this to add more and more data to some file. It might not be as simplistic as a CSV file, where you're separating the values with commas and just putting it in raw text. It might be some binary file with raw zeros and ones, but it's the exact same idea. And, in fact, if I go ahead and try to improve this code, I should note this too. In the spirit of error-checking, let me add one additional line before we
2:17:33
add one other example to the mix. It turns out that just like malloc, things can go wrong when you try to open files. Maybe it doesn't exist. Maybe there was a typo. Maybe you are, in fact, out of memory. So here too and for problem set 4 onward, you should get into the habit of checking return values. Don't just assume that you've got a valid return value. Check instead per the documentation of this function. if file == null, bad things just happen, something went wrong,
2:18:00
and I should probably just get out of here and return 1 or some other value instead. So, again, the lesson today is, any time pointers are involved from malloc, fopen, and other functions as well, do not trust that they are valid until you have checked whether they are null or not. All right, one final flourish here to implement the notion of copying a file as well. We introduced-- you might've seen the cp command before for copy files from one to the other.
2:18:27
How might we implement that ourselves even though it's been around for some decades now? Let me go ahead and open another file here called copy.c. Or, actually, we'll call it-- we did copy earlier. Did we? Yes, let's go ahead and create a new file cp.c to implement our own version of the copy command. In this file, let me go ahead and include stdio.h, and let me go ahead and include another file, stdint.h because it's something you'll see in problem set 4.
2:18:57
And I'm going to go ahead, and, in int main, I'm going to use command line arguments now. int argc string argv as an array. But we-- whoops. But we know strings don't exist. So, technically, main can henceforth be written as char * argv, still an array thereof. So we're just getting rid of the word string. And here's how I could open one file and copy it into another. Recall that copy works like this, cp source destination. So it's the opposite of the strcpy function, confusingly, but cp copies
2:19:32
the source file to the destination. So you can change the name or give it any name you want. So how might I use this knowledge? Let me create a pointer called source, src for short, and open a file called, hmph, well, what should the file be called? Let's expect the user to pass, in an argv1, whatever the file name is per the usage at the command line. Then let's open it up in read mode, specifically. Then let's go ahead and have a destination pointer,
2:20:00
called DST for short, that equals the return value of opening the second file that the human typed the name of at the prompt. And we'll open that in write mode. I'm not going to do append mode because I want to literally copy everything. I don't want to add to an existing file. And then what do I want to do? I'm going to propose that we do this byte by byte. And there's many different ways to do this. But among our list of functions from earlier are functions like fread for reading from a file,
2:20:25
f write, for writing to a file, as well as fprintf, which prints to a file. But if I actually am dealing with binary data, I might actually want to do this. I might want to declare a variable of type byte, which, by convention, especially in the windows world, is capitalized as byte. Give me one variable of type byte. And let me do this, while I read from the file, passing into that bite a bite from the file. So give this function the address of that bite. So we can go put 8 bits in it.
2:20:53
Then let's read in the size of a bite, which I could just write as 1. But I'm going to keep it dynamic. I'm going to read one such byte at a time. And I'm going to read from the source file. And I'm going to keep doing this so long as the return value's not 0. This is a mouthful, but allow me to just stipulate, for today's purposes, that line 11 just starts a while loop that iterates over the file called src byte by byte by byte by byte, from left to right, top to bottom, so to speak.
2:21:21
And how do I save each of those bytes to the destination file? Well, I can do fwrite, passing in the address of that byte so we can go to the location, the size of it, so it knows how big it is, how many there are, which is still 1, but send it to the destination instead. And then, at the end of this code-- let me hide my terminal for a moment-- let me go ahead and close, for instance, the destination file, and let me go ahead and close the source file.
2:21:45
And, ultimately, I think this is enough to, again, iterate over all the bytes in the file, One byte, one byte, one bite at a time and write them byte by byte by byte. And minor tweak, technically, because I want to do this literally-- there's no text involved, there's no Unicode. I just want this to be a raw copy of bytes-- technically, I can specify read the file in binary and write the file in binary. Don't try to do any kind of interpretation of characters. Treat it as raw 0's and 1's.
2:22:12
And, just so you've seen it, technically, in C, there is no such thing as a data type called byte. This is again a thing in the Windows world, and we will give it to you in problem set 4. But I can actually create a type using typedef. I'm going to have it be equal to something called uint8_t, where that just means unsigned 8-bit integer. But more on that some other time or never perhaps. But, for now, that just gives me a byte of 8 bits in a manner consistent with what windows computers do.
2:22:43
And if I didn't mess this up-- let me open my terminal window. Make cp for make the copy program .cp. I want to run .cp, so it's my version of the copy command, not the built in system one. Let me go ahead and copy a file like, what was the file we started with? addresses.c and how about we'll call this-- how about we call this backup.c. And if I open up addresses.c here, we'll see the file with which we began class earlier. If I open up backup.c, we'll see exactly the same file.
2:23:18
If I hold them side by side, these happen to be text, but they could've just been raw 0's and 1's. I've indeed implemented the cp command correctly in this way. Now how, though, does this loop work? Let me go back into cp.c. Recall that I had this loop here. Let me close these other files. There was this loop that somehow just knew to advance to the next byte in the file even though there's no plus 1. There's no for loop explicitly.
2:23:42
It's just kind of reading and reading and reading until fread returns 0. Well, the reason for that is that these file reading and writing functions behave a bit like a YouTube video or a Netflix video, whereby once you start reading from them, watching them, the sort of cursor advances from left to right. So as soon as you read a byte, the file itself keeps track of where you are in the file, kind of like an old school cassette tape. Once you start playing, physically, the device
2:24:07
is moving so it knows where to read the next bytes from and where to write the next bytes to. And this is all going to be germane as we introduce ultimately a specific file format this week in problem set 4, known as a bitmap file or BMP, for short. In the world of bitmap files, you'll see that you can represent images like this. But these images are really just going to be a grid of pixels top to bottom, left to right. And among the goals for this week is to implement
2:24:32
some Instagram-like filters via which you can actually manipulate these images. So, for instance, among the filters you'll implement is first one that converts any image, even a photo you yourself took into black and white by throwing away color information somehow and just retaining some form of grayscale. You'll implement. And it's a bit hard to see on the screen, but a sepia tone, sort of an old school photographic style. You might be able to invert or flip the image on its axis here,
2:24:59
so I've just reversed the sides of the bridge. Same photo just flipped around in the computer's memory by moving these bytes over here, and these bytes over here. Or if you really are feeling more comfortable, you can do edge detection and write nah. I said that wrong? Or if you're feeling really-- no, wait, everyone has to do this. Sorry let's stick the landing. We have one minute left. So what you'll also be challenged to do is blur the image too whereby you're going to make it look fuzzier
2:25:24
by sort of combining pixel values. So that it's not quite as crisp as it originally was. And if you're feeling really comfortable, you can even do edge detection, whereby you can figure out where the outlines of physical objects are on the screen by writing more sophisticated code, optionally to render images such as this here. So, ultimately, this whole week is going to be about file input and output, recovering images that might have been deleted or corrupted as well.
2:25:47
But we thought we'd end on a final pointer note, this is another one of these comics that now computer scientists should be able to understand the humor of. [LAUGHING] Hopefully, OK, lots of laughter. All right, that's it for CS50. We will see you next time. [APPLAUSE] [MUSIC PLAYING]
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat