DAVID J. MALAN: All right.
This is CS50, and this is the end of week two.
If you expect to be hungry around this time tomorrow, know that we're going
to convene as a small group tomorrow, Thursday, 1:15 PM.
There's this URL here if you'd like to RSVP.
Space is limited, so please forgive if the form has filled up by the time you
fill this out.
Another URL though that might be of interest is this.
>> So in just about a month's time, the course is going to be made available
all the more broadly via edX, via which folks on the Internet will be
able to follow along, engage in the course quite actively, in fact.
They'll be using the CS50 Appliance and CS50 Discuss and most of the
various software tools that we already have been using this semester.
And one of the initiatives we'd like to take on as an experiment this year
is to see just how much content we can translate into other spoken and
written languages.
So if you might have an interest in participating in this project, whereby
we will provide English transcripts and subtitles for the course's
lectures and shorts and seminars and sections and the like--
if you speak fluently or write fluently some other language, we would
love to engage you in this project, whereby you take on one or more of the
videos, translating them into a language you know quite well.
To give you a sense of the interface, there's this web-based user interface
that we'll be using that will create essentially a UI like this.
This was me teaching some Halloween ago.
And on the right hand side there in black next to these time stamps,
you'll see the various things that came out of my mouth that day.
And then below it, you'll be able to translate into some other language.
Exactly what the mapping is between, in this case, English
and, say, Spanish.
So it's actually a very user-friendly tool.
You can rewind and fast forward very readily with keyboard shortcuts.
So if you would like to take part in this experiment and have your words
seen and read by potentially thousands of folks out there, please do feel
free to participate.
>> Now one word about the kitten from Monday, lest we have sent an overly
scary message.
Do realize that as office hours suggest and as sections suggest, the
design of the course is very much to have students collaborating and
talking to work through problem sets and problems together.
And really the line just comes down to, again, the work you ultimately
should submit should be your own.
And so it's, quite honestly--in office hours, it's totally normal--
it's totally to be expected, even--to be chatting with some
friends next to you.
If he or she is struggling with some topic, and you're like, oh, well let
me give you a glimpse of some line of code that I wrote.
That's fine.
That happens.
And that's very much conducive, I think, with the process of learning.
Where the line, again, gets crossed is when the head is sort of tilted over
here for far too many seconds or minutes for that really to have just
been an unblocking opportunity for your friend.
And certainly, when things get exchanged via email and Dropbox and
the like, there too is the line.
So by all means, feel comfortable and feel encouraged to chat with friends
and classmates about psets and more.
And just realize that what you ultimately submit should really be the
product of your creation and not someone else.
>> So in the same vein of cuddly creatures, you might
know of this guy here.
So this is a horrifically cheesy movie from years ago.
Anyone here seen Spaceballs?
All right.
So a good number here.
So this is our wonderfully academic way of introducing today ultimately
the notion of cryptography.
And so one of the domain specific problems for pset 2, which will come
out late tomorrow night, is to dive into the world of cryptography, which
is the art of encrypting or scrambling information.
And this ultimately relates to the world of security.
>> Now security for most us comes in the form of fairly mundane mechanisms.
All of us have usernames and passwords.
And all of us have very bad usernames and passwords, most likely.
If your password is the same on multiple websites, that's probably not
the best idea, as we'll discuss towards semester's end.
If your password is written on a sticky note--no joke--on your
monitor, that too is not necessarily the best design but quite a common
phenomenon.
And if you're not using cryptography to encrypt your passwords, they are
particularly vulnerable.
So if you think you're being super clever by having a hidden Word
document somewhere on your hard drive that has all of your passwords but
it's in a folder that no one's going to look in, that too is not a very
secure mechanism.
And so what pset 2 will introduce is this art of cryptography and
scrambling information so that things like passwords are
all the more secure.
So as to motivate this very real-world problem with a very non-real-world
scenario, let me introduce you to one of our favorite clips here from this
movie, Spaceballs.
>> [VIDEO PLAYBACK]
-Helmet, you fiend, what's going on?
What are you doing to my daughter?
-Permit me to introduce the brilliant young plastic surgeon, Dr. Philip
Schlotkin, the greatest nose job man in the entire
universe and Beverly Hills.
-Your highness.
-Nose job?
I don't understand.
She's already had a nose job.
It was a sweet 16 present.
-No, it's not what you think.
It's much, much worse.
If you do not give me the combination to the air shield, Dr. Schlotkin will
give your daughter back her old nose.
-No!
Where did you get that?
-All right.
I'll tell.
-No, daddy, no.
You mustn't.
-You're right, my dear.
I'll miss your new nose.
But I will not tell them the combination no matter what.
-Very well.
Dr. Schlotkin, do your worst.
-My pleasure.
-No!
Wait, wait.
I'll tell.
-I knew it would work.
All right, give it to me.
-The combination is one.
-One.
-Two.
-Three
-Three.
-Four.
-Five
-Five.
-So the combination is one, two, three, four, five.
That's the stupidest combination I ever heard in my life.
That's the kind of thing an idiot would have on his luggage.
-Thank you, your highness.
-What did you do?
-I turned off the wall.
-No, you didn't.
You turned off the whole movie.
-I must have pressed the wrong button.
-Well, put it back on.
Put the movie back on.
-Yes, sir.
Yes, sir.
-Let's go, Erna.
Come, Gretchen.
Of course you know I'll still have to bill you for this.
-Well, did it work?
Where's the gate?
-It worked, sir.
We have the combination.
-Great.
Now we can take every last breath of fresh air from planet Druidia.
What's the combination?
-One, two, three, four, five.
-One, two, three, four, five?
-Yes.
-That's amazing.
I've got the same combination on my luggage.
Prepare Spaceball 1 for immediate departure.
-Yes, sir.
-And change the combination on my luggage.
-Ow!
[END VIDEO PLAYBACK]
>> DAVID J. MALAN: An amazing movie you should now all see.
So the context here is that with insecure data comes an opportunity to
encrypt it and to scramble it.
And so this, for instance, is an example of an encrypted message.
This actually says something in English.
But it's clearly not wholly obvious.
And we'll come full circle today to tease apart what this secret
message here is.
But in the real world of computers, things don't even look like they might
be English phrases.
For instance, this is what you might find on a standard Linux or Mac or
Unix computer in a file that was once upon a time called the password file.
Nowadays, it's been moved to other places.
But if you look in the right place on a system, you'll see not only your
username or that of other people on the system, but you'll see an
encrypted version of their password.
Indeed, the word crypt there suggests that the following stuff is encrypted.
And this series of seemingly random letters and characters and numbers and
so forth can be decrypted only by generally knowing some secret--
a secret word, a secret number.
And so indeed, the art of cryptography ultimately boils down to trust of some
sort and knowing something that someone else does not.
We'll explore this in a bit more detail today and in the pset to come.
>> And now a word on pass/fail.
So especially, as some of you have dived into pset 1, the appliance, and
a very new world for yourself, realized that frustrations and
confusion and just technical difficulties are to be expected.
Especially with the first pset, where there's just so much new, just getting
familiar with ls and cd and all these arcane commands in a new environment.
And that's separate from the actual material and programming itself.
So realize, too, that there are certainly office hours that exist as
the support structure.
Sections begin this coming Sunday.
But most importantly, if you're feeling just that this is not the
world for you, realize that it really does just take time.
And were it not for this opportunity years ago for me of taking a class
pass/fail, honestly, I never would have even set foot in the classroom.
And you can change this up until, say, the fifth Monday of the course.
So if you're on the edge now, realize that rather than head into some other
waters altogether, do certainly consider just changing to pass/fail.
Again, there's not really this culture here at Harvard of taking things
pass/fail since everyone really wants to achieve or overachieve.
But frankly, this is a wonderful way of trying something out that might not
be familiar to you.
And you'll end up doing in most cases quite fine, perhaps
much to your surprise.
And in more concrete terms, what I think pass/fail generally does,
especially as you might have experienced with pset 0, if you've put
in 10 hours, 15 hours, 25 hours into some pset--and you're just banging
your head against the wall,
and it's getting super late at night,
but you've taken the pset like 90% of the way,
you know you just can't figure out one thing--
pass/fail really takes the edge off of a class like this, where you can sort
of happily say okay, I know it's not perfect.
But I worked my ass off on this.
I'm pretty happy with where it ended up.
And that will meet the expectations for pass/fail.
So do keep that in mind.
>> All right.
So those of you who have struggled to use the Harvard University Wi-Fi know
that there's a CS50 SSID, a Wi-Fi connection floating around that you
might have better luck for.
It's a little ironic that the password for this--if you would like to try
connecting to this for better speeds and let us know if it's no better--
is one, two, three, four, five, all the way up to eight because eight is
more secure than five.
So if you need the Wi-Fi password, connect to CS50 wirelessly here.
One, two, three, four, five, six, seven, eight.
And post on CS50 Discuss if you still have intermittent connectivity issues,
and we'll let the powers that be know for this space.
>> All right.
So a quick teaser, especially for those of you who are fan boys or girls
of all things Apple.
What I dug up from a few years back was this file here, ilock.c, just to
kind of make more concrete and more complex some of the more basic C
programs we've been writing.
So I opened up this file, ilock.c.
It's available on the lectures page for today.
On the left-hand side, you see a long list of functions.
So the fellow who wrote this wrote up a lot of functions,
more than just main.
He used a whole bunch of libraries here.
And if we start scrolling through, what this actually is is the very
first, I believe, crack for the original iPhone.
When you wanted to jailbreak the original iPhone, which means untether
it from AT&T and actually install special software on it and do things
that Apple didn't want people to do--
well, someone took the time to figure out exactly how they could exploit
software flaws, mistakes, bugs, in Apple's software.
And thus was born ilock.c.
That if you compiled it on a computer and installed it onto an iPhone that
was connected to your computer via, say, a USB cable, this would give you
administrative or root privileges on your iPhone and let you do pretty much
whatever you want.
>> And so there's been this fascinating cat and mouse game between Apple and
the rest of the world in particular as they, like many companies, try to lock
their stuff down so that you can only do with it what they intend.
But thanks to people like this and their understanding of low-level
details and, in this case, C programming and a lot of the familiar constructs
that we've started playing with, you are able to really leverage the
hardware in a manner you see fit and not necessarily some corporate entity.
So for instance, I have no idea what all this is doing.
But GetVersion sounds pretty straightforward.
And it looks like this is a function that this person wrote.
Take some kind of integer as an argument, doesn't return anything, but
appears to loop with a for loop here and an if condition, if condition,
break, and somehow relates to version numbers.
If we scroll down--
even though a lot of these keywords are going to be new, and there's a
whole lot of functions in here we've never seen and might not ever see over
the course of the semester--
at the end of the day, it follows the same rules and logic that we've been
playing with thus far.
So this is far too old to crack your iPhone 3s or 4s or soon 5s, these days,
but know that it's all very much derived from this world that we've
dived into.
>> So let's take a look at a little more simple example.
This one, just to get warmed up with some syntax and also some other data
type that we've talked about but haven't really seen in C. So this is a
file called positive1.c.
And per the comments at the top, this just demands that a user provide a
positive number.
So it's an example of a do-while loop, which is nice for user-interactive
programs where you need to tell the user to do something.
And if they don't cooperate, you yell at them or reject their input.
Case in point, I am going to do lines 19 through 24 so long as the user has
not given me a positive number.
Now this detail here on line 18, why did I declare n above this whole
looping construct as opposed to right next to line 22 where I
actually care to get n?
Yeah?
[INAUDIBLE]
>> DAVID J. MALAN: Yeah, so this issue of scope.
And in layman's term, what does scope refer to?
Yeah?
[INAUDIBLE]
DAVID J. MALAN: Can you speak a little louder?
SPEAKER 1: Where you can access a particular variable.
DAVID J. MALAN: Perfect.
Where you can access a particular variable.
And generally, the rule of thumb thus far has been that the scope of some
variable is defined by the most recent curly braces that you've seen.
And so in this case, if I made the mistake of declaring n on line 22,
that line would work.
I would get an int, and I would put it into that variable n in line 22.
But which line of code would now have no idea what I'm talking about?
So 25, and it turns out 24, as well, because in this case, it falls outside
of the curly braces.
So just a little bit of a nuisance but very easily solved by simply declaring
the variable outside of the function itself.
>> Now we'll see later today, you can go one step further.
And you could even get a little lazy--
and this is not to be recommended, in general--
but you could even get lazy and put a variable globally, so to speak, not
inside of a function, not inside of a loop, but in the file itself, outside
of all of the functions you've written, as I did here on line 15.
But this is generally frowned upon.
But realize this is a solution sometimes to other problems, as we'll
eventually see.
So for now, we'll leave it like this.
But let's see if we can rewrite this just to start expressing ourselves a
little differently.
>> So this program, just to be clear, is positive1.
Let me go ahead here and in my terminal window make positive1, Enter.
Compiles, okay.
I'm going to run positive1, hit Enter.
I demand that you give me a positive integer.
I'll say -1.
That didn't work.
0, 99, that seems to work.
Maybe not the most rigorous test.
But at least it's a nice sanity check that we're on the right track.
So now let me go ahead and open version two of this.
And what is different already?
It implements the same thing.
But what's jumping out as clearly different this time?
Yeah, so this bool in green.
Gedit has highlighted in green this keyword known as bool,
which is a data type.
It doesn't come built in to all versions of C. You need to include a
specific library.
In our case, I included the CS50 library so that we
have access to bool.
But in line 18, we seem to have a Boolean value here called thankful.
So I could have called this anything.
But I called it thankful just to kind of convey some semantic meaning.
So initially on line 18, I'm apparently not thankful because the
Boolean value thankful is initialized to false in line 18.
And then it seems what I've done here in lines 21 through 23 is I've just
kind of rewritten my logic.
So no functionally different.
But in line 22 now, I check if the int the user has provided is greater than
0, then I simply change the value of thankful to true.
And why do I do that?
Because in line 25, apparently, I'm going to check a condition.
Do this loop while thankful is false.
>> So I propose this as an alternative to version one because it's at least a
little more intuitive, perhaps.
It's a little more grounded in English.
So do the following while you are not thankful or while thankful is false.
And this time, too, I apparently don't care to remember what the user typed
in because notice there's no variable n.
So actually, I--
a little white lie there.
Functionally, the program is a bit different once we get to the bottom of
it because I'm not remembering what n is.
But I wanted to demonstrate here too that even though we've seen GetInt and
GetString being used on the right-hand side of an equal sign thus far so that
we remember the value, technically, that's not strictly necessary.
If for whatever reason you just don't care to save the value, you just want
to check the value, notice that we can simply write this as GetInt open
paren, close paren.
That function is going to return a value, as we've been saying.
It's going to give you back an int.
And so if you mentally think of this happening, when I type in 99, GetInt
returns the number 99.
And so conceptually, it's as though my code were actually this.
So if 99 is indeed greater than 0, then thankful becomes true.
Then line 25 realizes ooh, we're done because I'm now thankful.
And in line 26, we simply say, thanks for the positive integer, whatever it
happened to be.
>> Now let's do slight syntactic sugar here, so to speak.
Let's see if we can clean up this line 25 with this third and final variance
in positive3.
So notice the only difference now is what line of code?
Yeah, so 25.
And we've not really seen this trick just yet.
But we did see the exclamation point on Monday, which denotes what?
So not, or negation.
So take a Boolean value and flip its value.
True becomes false.
False becomes true.
So this, I would propose, is even a little more intuitive of a way of
writing the code because I still initialize thankful to false.
I still do the following.
I set thankful to true when the time comes.
But now you can really just translate this code verbally left to right,
while not thankful.
Because bang, or exclamation point, denotes the notion of not, so while
not thankful.
>> So again, we haven't introduced any new concepts per se.
We've talked about Booleans back when we played with Scratch.
But realize now we can just start writing our code in
many different ways.
So especially in pset1, if you're sort of struggling to figure out the way to
write some program, odds are you're in luck because there's going to be any
number of solutions that you can happen upon.
For instance, this is just three for even the simplest of programs.
All right.
And now recall on Monday, we left on this note with return values.
So for the very first time, we wrote a program that doesn't just have main,
it also has its own custom function that I wrote here.
So in line 31 through 34, I've implemented a cube function.
It's not complex.
It's just a times a times a, in this case.
But what's important about it is that I'm taking input in the form of a and
I'm returning output in the form of a times a times a.
>> So now I have the ability, much like I used to with printf alone, to call
this function by calling the cube function.
And the cube function takes some input.
And the cube function returns some output.
And so by contrast, printf just did something.
It didn't return anything that we cared about--even though, as an
aside, it does return a value.
You just generally ignore it.
Printf just did something.
It had a side effect of printing to the screen.
By contrast here, we have the cube function, which
actually returns something.
>> So this is generally--
for those familiar with this, it's a fairly straightforward idea.
But for those less familiar with this idea of passing in inputs and getting
back outputs, let's try just something super simple.
Is anyone comfortable coming up on stage briefly?
You have to be comfortable with a camera on you, as well.
Yeah.
Okay, what's your name?
KEN: Ken.
DAVID J. MALAN: Ken.
All right, Ken.
Come on up.
So Ken is going to be a function of sorts here.
And let's go ahead and do this.
Let's get a little fancy.
Nice to meet you.
Welcome to center stage.
All right.
Let's hit this button here.
All right.
So here you have a modern chalkboard.
And what I am is the main function, for instance.
And I don't have an iPad in my hand.
I don't really remember how to--well, actually, can't say that.
I don't really have good handwriting.
And so therefore, I want you to print something on the screen for me.
>> So I am being the main program.
And I am going to have you say this by writing it in my chicken scratch and
then passing you an input.
So as silly though this exercise is, the notion of functions and calling a
function and returning a function really boils down to this.
I am main.
I have just written printf("something") on the screen.
I'm running this program.
And as soon as printf gets called, it takes one argument--or one parameter,
sometimes--
between double quotes.
Here is that argument.
I'm passing it to Ken.
Now he is a black box written some number of years ago that apparently
only knows how to print things on the screen.
>> So, execute.
That's not bad.
So, very good.
So now Ken is done executing.
Does he need to hand me anything back?
So not that we've seen thus far.
Again, printf does actually return a number.
But we're going to ignore that for now because we've never used it.
So that's it for Ken.
And so now main comes back to execute--
main takes over control of the program again because that line of code,
printf, is done executing.
And we go about our way executing whatever other lines are there.
>> All right.
So now let's try a slightly different example.
And this time here, let's first clear the screen here.
And this time, we'll do the cubing function.
But this time, I expect an output value.
So let's go ahead and do this.
So now I have a line of code that says x = cube(x).
So actually let's--
the line of code, recall, looks like this.
x = cube(x).
So how is this going to work?
So let's go ahead and give you a white screen again.
And I am going to write now down the value of x, which at this moment in
time happens to be, let's say, 2, to keep it simple.
So I have written down on a piece of paper the value of 2,
which is my value x.
I hand it to Ken.
KEN: And I just write the answer?
DAVID J. MALAN: Yeah, let's just write the answer.
Okay.
And now he has to return me something.
So--
perfect.
Nice segue.
>> So now he hands me back the value of 8, in this case.
And what do I do with it?
Well, actually, let's see.
Get this right.
What am I going to do with it?
Now I'm going to take this value and actually store it in those
same bits in memory.
But notice, I'm kind of struggling here.
I'm a little confused because where do I actually write the value of x?
Because what I've just done is physically hand Ken a piece of paper
that had the value 2, which was x.
And indeed, that's precisely what happens.
So it turns out that when you call a function, and you pass in an argument
like "hello world" or you pass in an argument like 2, generally, you're
passing in a copy of that argument.
And so just as I wrote down the number 2 here and handed it to Ken; that must
mean that I still have a copy of the value 2 somewhere.
Because indeed, now that I've gotten back the value 8, I need to go back in
RAM and actually write down 8 where I once had the number 2.
>> So visually remember this notion of passing in literally
a copy of the value.
Ken does his thing, hands me back something--in this case,
a value like 8.
And then I have to do something with that value if I
want to keep it around.
So all of this will be all too familiar before long.
Thank you so much for this demo here, Ken.
All right.
Very well done.
So let's see how that ultimately relates to some of the function
calling that we've been doing here.
So let me go ahead and bring us back to the cubing example here.
And notice that if we want to actually start taking this further, we're going
to have to be mindful of the fact that the number x that's being passed in
here is different from what's actually being passed into the function.
So again, this passed by copy is going to become quite
germane in just a moment.
>> So let's take a look at something that doesn't quite work right yet.
I'm going to go ahead and open a third buggy example, which
is flawed by nature.
And it's called buggy3, and it implements a swapping function.
So here we have a main function that has x and y arbitrarily initialized to
1 and 2, respectively.
We could use GetInt, but we just need a simple exercise.
So it's hard-coded as 1 and 2.
In lines 21 and 22, we apparently print out x and y, one per line.
Then, on line 23, I claim I am swapping these values, dot, dot, dot.
I apparently call a function in line 24 called swap
that takes two arguments.
It's totally legit for functions to take two arguments.
We've seen printf do it already.
So swap apparently takes x and y.
And as its name suggests, I would hope that it's going to
swap these two values.
So then I claim on line 25, swapped.
And I reprint x and y under the assumption that
they've indeed been swapped.
But if I actually run this program--
let me open up a terminal window.
Let me make buggy3.
As the name suggests, this is not going to end well.
Because when I hit Enter, notice that x is 1.
y is 2.
And yet at the end of the program, they're still, in fact, the same.
>> So based on the demonstration just now with Ken, what's actually going on?
Well, let's dive into this swap function.
It's super short.
It's only a few lines of code long.
But what's the fundamental problem based on the simple story told
up here with Ken?
Why is swap broken?
[INAUDIBLE]
Exactly.
So we're storing to a copy, not the variable itself.
In other words, swap apparently takes two arguments, an int.
And it's arbitrarily called a and b.
And up here, I've passed in x and y, which are respectively 1 and 2.
But I'm not literally passing in x.
I'm not literally passing in y.
I'm passing a copy of x and a copy of y.
It's like almost as though you copied and pasted into swap the values that
you want it to actually manipulate.
So if that's the case, when I, the program, start executing
line 35, then 36--
when I get to line 37, at this point in the story, what is the value of a?
At this point in the story, line 37, what is the value of a at this point?
So it should just be 1.
Right?
Because x was passed in as the first argument.
And this function just arbitrarily is calling its first argument, a.
Similarly is y, the second argument.
And it's just arbitrarily calling the second argument b.
>> Now this dichotomy is actually fairly simply explained.
Think about it.
None of us have met the person who wrote printf.
So surely, he or she has no idea what our variables 30 years later are going
to be called.
So there has to be a distinction between what you call variables in
functions you're writing and what you call variables in functions you're
calling or using.
So in other words, I have written my variables as x and y.
But if someone else had written the swap function, he or she certainly
wouldn't know what my variables are going to be called.
So realize that this is why you have this duality of names.
Technically, I could do this by coincidence.
But they would still be passed in as copies.
It would just be a pure coincidence aesthetically if that person who wrote
swap had used the same names.
>> All right.
So at this point in the story, line 37, a is 1.
b is 2.
And now I proceed to swap them.
Well first of all, let me actually do this much more simply.
I don't know what those three lines of code were doing.
Let me just do this.
b gets a.
a gets b.
Done.
Why is this broken, logically?
It's kind of the intuitive thing, right?
So a becomes b.
And b becomes a.
But the problem is that as soon as line 37 executes, what's the
value of a and b?
The same, 1.
Because you have clobbered, so to speak, you've changed b to equal a.
So once line 37 is executed, that's great.
You now have two copies of the number 1 inside of this function.
So then when you say in line 38, a gets b, well, you're kind of screwed.
Because you're just assigning 1 to 1.
You've kind of lost the value you cared about.
>> So in the original version of this, notice what I did.
I instead had a third line of code that looked like this.
I declare a temporary variable--tmp is a very common name
for a temporary variable.
It's an int because it has to match what I want to make a copy of.
I store a copy of a inside of tmp. So once line 37 has executed,
the value of a is--
quick sanity check--
1.
The value of b is 2.
And the value of tmp is also 1.
So now I execute line 38.
So once line 38 executes, a takes on the value of b.
And b was 2.
So a is now 2.
So at this point in the story, a is 2, b is 2,
and tmp is 1.
So now logically, we can just plop tmp's value into b.
And we're done.
>> So we've solved that problem.
Unfortunately, when I run this program in this form, it doesn't actually swap
any values.
But to be clear, why?
I fixed the logical problem from just a moment ago.
But again, if I run this program, x and y remain unchanged by the end of
the program's execution.
[INAUDIBLE]
DAVID J. MALAN: So we haven't returned anything.
So that's true.
But it turns out there's a bit of a problem here because thus far, the
only thing we've been able to return is one thing.
And this is a restriction of C. You can only return really one value,
in which case, I'm kind of stuck here
because I could return the new value of x or I could return the
new value of y.
But I want both back.
So returning is not the simple solution here.
But the problem fundamentally is why?
What have we actually swapped?
a and b.
But a and b are copies of x and y, which means we just did all of this
work--we just spent like three minutes talking about the swap
function and all three of these variables.
And that's great, perfectly correct in isolation.
But a and b's scope only is in these lines here.
So just like a for loop, if you declare an integer i inside the for
loop--similarly, if you're declaring a and b inside of a function that
you've written, they're only valid inside of that function.
Which means as soon as swap is done executing and we go from line 24 to
line 25, x and y haven't been changed at all.
You just wasted a whole lot of time swapping copies of variables.
>> So it turns out that the solution to this is actually non-obvious.
It's not quite sufficient to return values because we can
only return one value.
And I really do want to swap both x and y at the same time.
So we're going to come back to this.
But for now, realize that the issue fundamentally derives from the fact
that a and b are copies.
And they are in their own scope.
Well, let's try to solve this in some way.
Let me actually scroll back here and open up, let's say, a fourth variant
of this, buggy4.
And what about this?
This is a similar but simpler problem to look at before we take a stab at
solving it.
This program is called increment.
And it apparently initializes an x integer to 1 in line 18.
I then claim x is 1.
I then claim incrementing, dot, dot, dot.
I then call increment.
But then in lines 22 and 23, I claim it's been incremented.
I claim x is now whatever it is, 2 presumably.
>> But this program is buggy.
What's the problem?
Yeah?
[INAUDIBLE]
DAVID J. MALAN: Exactly.
So x has been declared obviously on line 18.
That is inside main's curly braces.
So the simple answer here is that, well, x exists here.
It does not exist in line 32.
So this program actually won't even compile.
The compiler, when I try compiling this code, is going to yell at me
about some undeclared identifier or something to that effect.
In fact, let's try.
This is make buggy4.
There it is.
Use of undeclared identifier x in line 32.
And actually, let's be more explicit here today so that this is useful in
office hours and at home.
Notice that it's a little cryptically written.
But the fact that Clang has yelled at us, saying
buggy4.c:32:5, is actually useful.
It means that the error is on line 32 at character position five.
So one, two, three, four, five.
That's, in fact, where the problem is.
And also to keep in mind at office hours and at home, I'm lucky here.
I have one mistake.
It's going to be relatively easy to fix.
But if you get a whole screen full of overwhelming error messages, again,
realize that the bottommost one might just be symptomatic of
the topmost ones.
So always chase down your bugs from top down.
Because there might just be a daisy-chain effect that is suggesting you
have way more problems than you actually do.
>> So how could we fix this if my goal is to increment x?
What's that?
Okay.
So we can make x global.
Let's take the shortcut that I warned about earlier.
But heck, we just need a quick fix.
So let's just say int x up here.
That makes x global.
So now main has access to it.
And increment has access to it.
And so let me go ahead and compile this now.
Make buggy4, Enter.
Seems to compile now.
Let's run buggy4, and it seems to actually work.
Now this is one of these things--
do as I say, not as I do, as I've just done here.
Because in general, our programs are going to get much more interesting and
much longer than this.
And if your solution to life's problems is just ah, put all the
variables at the top of your file, very quickly do programs get
horrifically difficult to manage.
It gets harder to think up new variable names.
It gets harder to understand what variable is doing what.
>> And so in general, this is not a good solution.
So let's do this better.
We don't want to use a global variable here.
I do want to increment x.
So I could obviously--
at the end of the day, it's kind of a silly story because we just do this.
But if I didn't know about that operator, or I wasn't allowed to
change it in main itself, how else could I implement Ken over here, this
time not to cube but to increment?
How do I change this thing here?
Yeah.
[INAUDIBLE]
DAVID J. MALAN: Okay, good.
So why don't I pass in x?
And then rather than return it, why don't I just do return x + 1?
Now, a couple more things have to change here.
I'm on the right track.
What else do I need to tweak?
Someone else.
Yeah?
[INAUDIBLE]
DAVID J. MALAN: I need to change the return type of increment
because it's not void.
Void means nothing's being returned.
But clearly, now it is.
So this needs to change to int to be consistent with whatever
I'm actually returning.
>> Now something else is still buggy here.
Yeah?
[INAUDIBLE]
DAVID J. MALAN: So I need to increment x?
[INAUDIBLE]
DAVID J. MALAN: Ah, so I need to pass x.
So I need to do this here.
So the prototype, I have to change this up here.
So this has to become an int.
This has to become--
hmm.
I actually have a bug down here.
Let's fix this one first.
What should this actually be?
So it's got to be an int something.
It could be x.
But frankly, if you start calling all of your variables x, it's going to get
less and less clear which is which.
So let's just arbitrarily choose a different naming convention for my
helper functions, the functions I'm writing.
We'll call it a.
Or we could call it--let's call it even_number to be even more explicit.
So then I have to return whatever the number is plus 1.
And now I have to change one other thing up here and one
other thing up here.
What do I have to change on line 21 first?
I have to assign it to x.
So I can't just call increment x.
I need to remember the answer by changing the value of x on
the left hand side.
And even though x is now on the left and right, that's totally fine because
the right hand side gets executed first then gets plopped into the left
hand thing, x in this case.
And then lastly, this is an easy fix now.
This should just match what's down below.
Int number.
>> All right.
So a whole bunch of changes for a really stupid function.
But representative of things that we'll increasingly want to do.
So make buggy4.
I've screwed up somewhere.
Oh my God.
Five mistakes in, like, a six-line program.
So what's wrong on line 18, character 5?
All right.
So I have to declare this int.
All right.
So let's see, a whole bunch of other errors.
Oh my god.
19, 18, 21.
But again, let's just clear the screen--
Control L here-- and re-run Clang.
So five problems is actually just that one.
So now let's run buggy4, Enter.
Whew.
x has been incremented correctly.
>> All right.
Any questions on how to increment numbers?
Yeah?
SPEAKER 2: Why is it that you can just change x to number in the variable
name and it'll know what you mean?
DAVID J. MALAN: Good question.
How is it that I can just change x to number and the program will know
immediately?
So again, think of it as this abstraction.
So if I am main and Ken is incremental, frankly, I don't care
what Ken calls his iPad.
I don't care what he calls anything that has to do with his implementation
of this functionality.
So this is an implementation detail that I, main, don't
have to care about.
And so simply changing it consistently inside of the function, number here
and number here, is all it takes so long as I recompile.
It's sort of like if you think about--many of us, those of you with driver's
licenses who've driven, or if you've even driven in a car--
most of us have no idea how a car works underneath the hood.
And literally, if you open up the hood, most of us--myself included--
aren't going to really know what we're looking at.
Kind of like you might feel with stuff like this right now.
But we don't really have to care how the car works.
We don't have to care what all of the rods and pistons and cables inside of
the car are actually doing.
>> So something like what you call the piston doesn't matter
here in this case.
Same idea.
Yeah?
[INAUDIBLE]
DAVID J. MALAN: If there were more uses of the variable x a moment ago,
you, the programmer, would have to change them everywhere.
Or you could literally do File, Menu, and then Find/Replace,
something like that.
But you are going to have to make those changes yourself.
You have to be consistent.
[INAUDIBLE]
DAVID J. MALAN: A particular order like here?
If this was int another number?
Yeah.
So order matters when you are calling the function.
So if I were calling increment here with something comma something,
there's a direct mapping.
The first variable, whatever it's called, is made a copy of the first
argument over here.
Sorry, this should not be a parenthesis.
The second argument lines up with the second one.
>> So order, yes, matters.
All right.
Sorry I took a long way to get there.
Other questions?
All right.
So let's see if we can't paint a picture of what's actually going on
here underneath the hood, so to speak.
So this is a rectangle that might represent your computer's memory.
So even if you have no idea how memory works or how RAM works, at least
assume that you have bunches of it these days.
You've got megabytes of it.
You've got gigabytes of it.
And we know from week zero that a byte is just what?
8 bits.
Right, so 8 zeroes and ones.
So if your computer has a gig of RAM, two gigs of RAM these days, you have a
billion or 2 billion bytes of memory, or roughly 8 billion or 16 billion
bits, inside of your computer.
Now unlike the little Woolly Willy example, it's not magnetic particles
typically anymore.
Increasingly, in laptops at least, it's solid state drives, SSDs, that
just have no moving parts.
It's all electronic.
It's all electricity based.
So think, though, of this rectangle as just representing the one or two
gigabytes of memory that you have.
>> So it's a chunk of memory.
Now the world of computer science has sort of partitioned off chunks of
memory to do different things.
So for instance, if this is your computer's RAM--as suggested by the
rectangle there--turns out that by convention, at the top of your RAM, so
to speak, is generally what's called a text segment.
Those are the zeroes and ones that you have compiled.
So when we've looked underneath the hood at what a.out is, all
the zeroes and ones--
when you run a program, those zeroes and ones are loaded from your hard
drive into something called RAM.
And in the RAM, they're put at the top.
Now meanwhile, you have other things.
Initialized data, uninitialized data.
Those two swaths of memory refer to global variables, which
you don't often use.
But sometimes if you do, they end up up there as well.
Then there's some other stuff.
Environment variables, which we won't spend much time on.
But then two important things that will come back throughout this
semester, stack and heap.
>> So most of your computer's memory is reserved when running a program for
something called the stack and something called the heap.
And we're not going to talk about the heap today, but we will
talk about the stack.
And the stack is meant to conjure up the visual of like the dining hall
meal trays in Mather House, or wherever you happen to be, where the
dining hall staff clean them every day.
They stack them up from floor on up.
And similarly in memory, there is this idea of putting something on a
stack, putting something on a stack, putting something on a stack.
And what do we mean by this?
Well, let's zoom in on just the lower half of this picture, your computer's
RAM, to propose the following.
It turns out that when you run a program like a.out or hello, whatever
the program is that you've written,
again, those zeroes and ones are loaded from your hard drive--which is
long term storage, stays there even when you pull the plug--
loaded into RAM.
RAM is faster than hard drives.
It's smaller than hard drives.
But it's where programs live while you're running them.
>> So you double click a program on a Mac or a PC--it's loaded from
hard drive into RAM.
As soon as it's loaded into RAM, the zeroes and ones go at the way top, the
so-called text segment.
But then as soon as your program actually starts running, the main
function is called.
And main, as we've seen, often has local variables.
And it has ints and strings and chars and the like.
So if your program that you have written or the program that you have
double clicked used some variables inside of main, they end up at the
bottom of your stack of memory, so to speak.
Now more concretely, what does this actually mean?
This just means that if we were going to number the things--
if we were going to number the bytes of RAM in your computer, notice that
this might be byte number zero.
This might be byte number one, two, three, four, five, six, all
the way up to like--
2 billion would be all the way up there at the top.
So in other words, when we talk about RAM or memory in terms of bytes, it
just means that someone has decided what to number each of
those chunks of memory.
>> So when you need 32 bits for an int, or you need 8 bits for a char, where
do they end up in memory?
Well conceptually, they just end up at the bottom of this
thing called the stack.
But what's interesting now is when main calls a function.
Suppose a function called foo, just an arbitrary name.
What happens is main is at the bottom of this stack of memory.
Foo now is put on top of main in memory.
So any local variables that foo has end up sort of conceptually above
those in main.
If foo calls another function called bar, those variables end up here.
If bar calls something else, here, here, here.
So what's interesting about running a program is that as you call functions,
and as those functions call functions, and as those functions call functions,
you build up this stack of functions in memory.
And only once a function returns do you start getting that memory back.
So one of the easiest ways to run out of memory in a computer program is to
write functions that never return.
>> So for instance, let's demonstrate as much with an
intentionally buggy program.
Let me go ahead and do #include , int main(void).
And I'm going to do while (2 > 1), which probably won't ever
change on us.
And let me go ahead now and do printf.
Actually, that's going to be less visually interesting.
Let's do this.
For int (i = 0; i > 0).
Let's make this mistake, i++.
And let's not printf here.
Let's practice what I was preaching.
Let's have a method here.
Void chorus, and we'll say int i.
And then I'm going to say, printf--
oh, let's make this more interesting.
Let's actually not print anything at all.
Let's just do this.
Chorus(i).
>> All right.
So this is buggy because why?
I'm making this up as I go because the program doesn't actually do anything
of interest.
But that's not the goal.
The goal is to write a program whose main function does what, apparently?
Call itself.
And actually, we don't need the loop.
Let's even simplify this just so as not to lose sight of really the
fundamental bug.
Main calls chorus to sing some chorus.
Then I did something stupid, and I had chorus call chorus because I assumed
someone else was going to implement it maybe.
And now this isn't going to compile yet.
I need to do what?
I need the prototype, remember.
So I need to have up here void chorus(int i);.
>> So now, if I go down here--
actually, let's use the bigger window.
Let's go ahead and make chorus.
Use of unidentified declarer i.
Oh, that was stupid.
We don't need the argument.
Let's just do this.
Wish we had started this way.
It would have been a much easier program to write.
So there.
Now let's go over to my terminal window, re-run Clang.
And here we go.
That was really fast.
What actually just happened, though?
Well, now I'll add the print line, so we can see.
So let me say printf, let's say, I'm in here.
Okay, no variables, we'll leave it like that.
Let me re-run make.
Let me re-run chorus.
And come on.
Keep going.
As an aside, why has it not crashed yet?
The segmentation fault happened super fast before.
[INAUDIBLE]
DAVID J. MALAN: Exactly.
So it takes time to print.
It just takes more work on the computer's part.
And there it is.
Segmentation fault.
>> So notice just how fast programs run.
If you're not printing anything, super fast.
But we still got this segmentation fault because what was happening?
Well, if you think about how your computer's memory is laid out, this
happens to be main.
But here--
let's just call this chorus, and let's call this chorus.
And now if I do my aesthetics right, this is just going to say chorus,
chorus, chorus, chorus, chorus, chorus, chorus, ad nauseum.
And eventually, what's going to happen?
If the big picture literally is this, what just happens conceptually?
The stack overruns the heap.
Or worse, you just overrun everything, including the text segment, which is
the zeroes and ones that represent your program.
In short, this is just super, super bad.
Right?
Your program has spiraled out of control.
You're using way more memory than you intended all because of a stupid
mistake, in this case.
Or in this case, a very deliberately done function calling itself.
Now this is not all bad.
Functions calling themselves actually has great power
when you use it correctly.
I have not used it correctly here.
>> So this is not all bad.
But the fact that I never actually stop calling myself is a fundamental
weakness here of this program.
So where are we going with all of this?
Well, what's really happening?
When I call the increment function, like we were doing in those examples,
I have a value like 1 that I pass in.
I pass in a copy of the number one.
So the following happens.
So let's go into the increment example.
And this guy right over here.
So here's what's actually happening.
When I called increment, and I pass in x, pictorially what's
going on here is this--
if I have the value of 1 stored here, and I actually call increment, which
is now called chorus--
yeah, that's throwing me off here.
So let's call this increment.
And we don't know what this next function's going to be.
So what's actually happening is here somewhere in main, I have a chunk of
memory that is storing the number 1.
When I call increment, I'm using another chunk of memory, but now I
have the copy of 1.
When I increment that value, this becomes 2--horribly written on the
screen here.
But then, what happens as soon as increment returns?
This memory just gets handed back to the operating system, which means all
you've done is nothing useful.
The one that was originally contained in main is still actually there.
>> So where are we going with this?
Well, it turns out that in memory you have this back to back sequence of
bytes that you can put stuff in.
And it turns out that we've already seen something that involves putting
things back to back to back to back.
What is a string, based on week one and now week two?
So it's just a collection of characters.
So it turns out, just as you can put numbers in memory, similarly you can
put characters in memory.
And once we start putting characters in memory back to back to back to
back, it turns out that using the simplest of things like a for loop or
a while loop, we can iterate--
from left to right over the characters in a string--
and start massaging them into different characters altogether.
A could become B. B could become C. So that ultimately, we can take an
English sentence that actually makes sense and convert each of those
letters one at a time by walking through our computer's memory left to
right to actually encrypt.
>> So let's take our five-minute break here, and when we come back, we'll
start this process of scrambling information.
>> All right.
So before we dive in to some crypto and these things called arrays, let me
pause for any questions because I feel like I really kind of muddled some of
those topics.
So let's fix now if we can.
So we just talked about return values.
We talked about arguments.
And we talked about this notion, which we'll come back to in the weeks to
come, of viewing memory as a whole bunch of these stacked
trays, so to speak.
From bottom on up, such that each tray that gets put on the stack represents
a function that's currently being called.
Any questions?
So how about--let me try asking a question.
I keep spoiling that, but now it's--you've all seen the boy's face.
So we'll come back to that.
>> So let me ask a question here.
Let me simplify this back to what it was before some of our earlier Q&A.
And the fact that increment has open parenthesis, int number, closed
parenthesis.
What does int number represent?
[INAUDIBLE]
DAVID J. MALAN: An argument.
Okay, but what's an argument?
[INAUDIBLE]
DAVID J. MALAN: Sorry, what's that?
SPEAKER 3: Something you pass in.
DAVID J. MALAN: Okay.
So something that you pass in.
And more generally, it's just the input.
If you're writing a function and that function's purpose in life is to do
something a little different every time you use it, then the only way for
that to happen really would seem to be to provide it with input so that it
can do something different with that input each time.
>> So you need to specify two things when a function takes inputs.
You need to specify the name that you want to give to that input, purely for
your own convenience so that you can refer to it in the function that you
yourself are writing, as I did here in line 32.
But you also need to specify its type because C is a programming language
that just requires
that if you want a variable, you have to tell the computer what
data type it is,
in large part so that it knows how many bits to
allocate for that variable.
Because it could be six--
sorry, it won't be six.
It can be 16.
It can be 8.
It can be 32, even 64.
But the computer needs to know.
Now the int on the left hand side represents what, by contrast?
[INAUDIBLE]
DAVID J. MALAN: What's that?
[INAUDIBLE]
DAVID J. MALAN: The type of the function and, more specifically, the
type of its output.
Right.
So whereas the thing in parentheses represents its input, if any, the
thing to the left represents its output.
And in this case, increment apparently returns an int.
And so int is the return type of this function.
>> What does it mean to return?
Literally, you use the keyword return.
And then if what you are returning to the right of the keyword is an
integer, then that is indeed consistent with what we have promised.
You could not do something like this--
hello, world--
because that is a string.
Obviously it is not an integer.
So in short, the burden is really on us, the programmer, to be specific as
to what we're returning and to then actually go about returning it.
And then to make a tad more clear the context--
there he is again.
The context--
big surprise coming in just a moment.
The context here now is that your computer's memory is, again, a
gigabyte, two gigabytes, whatever.
Maybe it's more.
Maybe it's less.
But the computer views it as having different sections.
Something goes down there.
Something else goes up there.
Different stuff goes in the middle.
And today, we just begin telling this story.
>> But we'll come back to this over time.
For now, the only piece of memory we really care about is the text segment
because that just represents the zeroes and ones
that Clang has outputted.
So when you run a command at the keyboard like a.out, or you double
click an icon on Mac OS or Windows, your program's loaded from your hard
drive into RAM.
And it's plopped at the top of your computer's RAM, so to speak.
Now meanwhile, as your program starts running and main gets called in the
program you wrote or the program Microsoft or Apple wrote, any of its
local variables end up down there at the bottom of your computer's memory.
But if main calls another function that itself has variables or
arguments, they end up above it.
And if that function calls something, they end up above it,
above it, above it.
And only once a function is done executing does the stack of trays, so
to speak, start to get lower and lower.
And this is what then, in a nutshell, explains why, when you call cube--
or you call increment--
you're passing in a copy of the value.
And what that means pictorially is that you're literally writing the
number 1 in another part of memory, changing that 1 to 2, in the case of
increment--
or to an 8, in the case of cube--
and then throwing that memory away as soon as the increment or the cube
function returns.
>> Question.
[INAUDIBLE]
DAVID J. MALAN: Where--global variables are stored in what's
currently called the initialized data or uninitialized data.
The difference being, if you have a global variable, and you assign it
immediately a value with the equals sign, it ends up at the top there.
And if you just say int x semicolon with no value, it ends up slightly
lower in RAM simply by convention.
Other questions.
All right.
>> So this picture will come back as we get more powerful with what we can do
with the computer.
But for now, let's have a brief intro to cryptography, a specific type of
cryptography that doesn't solve all of the world's problems but does solve
some of them.
In this case here, we have something called secret key cryptography.
And secret key cryptography, as the name suggests, derives its security
from a secret.
So for instance, if you're back in grade school and you're passing a
little secret love letter to the boy or girl you are crushing on--if you
wanted to pass that through the audience, you probably wouldn't write
such a note in English or whatever your native language is; rather, you
might encrypt it.
Or you might just send them a text message these days.
But you might actually pass them a note throughout the classroom.
And to do this securely, in such a way that your friends and the teacher
don't know what you're writing, you might come up with a fairly simple
algorithm--
young though you might be--
to just scramble the words.
So instead of writing A, you might write B. Instead of B, you might write
C. Instead of C, you might write D, and so forth.
Or you could come up with a more sophisticated translation of letters
to different letters.
But the catch is the boy or girl to whom you're sending this note needs to
know something.
Which is what, obviously?
Like, what your secret is.
Like, what is that mapping between As and Bs and Cs and Ds?
Is it just adding one, so to speak, to each of the letters to go from
A to B, B to C?
Is it more complex than that?
So you and your crush need to have this secret information.
But there's kind of a catch-22 here.
If this is the very first time you're sending this love letter through the
class, how is that boy or girl going to know what the secret even is?
So secret key crypto does not solve all the world's problems.
And there's actually a relationship that we'll come back to toward
semester's end.
>> Similarly, have none of us probably ever sent a--
similarly, do most of us not know someone that works, for instance, at
Amazon.com.
And yet, many of us have probably bought stuff at Amazon.com.
And we've been taught to assume that these e-commerce
transactions are secure.
Right?
The URL probably says https.
There's maybe a silly little padlock icon somewhere.
There's some kind of cryptography securing your credit card information
between you and Amazon.com.
And yet, if cryptography involves knowing some secret, and yet I don't
know anyone at Amazon, and I've certainly not arranged any kind of
secret with someone at Amazon, how is my computer or my browser doing this?
Well, turns out there's other types of cryptography altogether that solve
that problem.
But for today, we'll focus on the simple one, where you can arrange in
advance to know some secret, like plus 1 or some mapping between As and Bs.
>> And the process of cryptography generally involves this.
You have some plain text, depicted here at left.
You run it through some kind of algorithm or procedure
for encrypting it.
Maybe that's just A becomes B, B becomes C. And then you end up with
cipher text.
Meanwhile, once your crush receives the secret note, he or she has to then
decrypt it by generally reversing that algorithm so as to get
back the plain text.
Now there are physical incarnations of this.
For instance, this is a little secret decoder ring.
And this is a ring in the sense that there's two dials here.
On the outside periphery of this thing, there's letters A through Z,
although they're in random order.
And on the inside, there's actually some numbers, such that with this
ring, you can kind of turn the outside but not the inside in order to line up
numbers with letters.
And in the clip you're about to see--some of which you may have seen 24/7
around the Christmas season from a movie called A Christmas Story.
You'll see that little Ralphie was so eager to figure out what little orphan
Annie's secret message was to him that had been communicated, I think, in the
form of numeric messages on a serial box.
And you had to accumulate all the little cards that came
in the cereal box.
You had to mail them in.
You had to get back the secret decoder ring, so that you can finally figure
out what the mapping is between letters and numbers,
or letters and letters.
So I give you this short clip from A Christmas Story to motivate pset 2 and
our discussion, in a moment, of arrays.
So here we have Ralphie.
>> [VIDEO PLAYBACK]
-Be it known to all and sundry that Ralph Parker is hereby appointed a
member of the Little Orphan Annie Secret Circle and is entitled to all
the honors and benefits occurring thereto.
-Signed, Little Orphan Annie.
Countersigned, Pierre Andre!
In ink!
Honors and benefits, already at the age of nine.
Come on, let's get on with it.
I don't need all that jazz about smugglers and pirates.
-Listen tomorrow night for the concluding adventure of The Black
Pirate Ship.
Now it's time for Annie's secret message for you members
of the Secret Circle.
Remember, kids, only members of Annie's Secret Circle can decode
Annie's secret message.
Remember, Annie is depending on you.
Set your pins to B2.
Here is the message.
12, 11--
-I am in my first secret meeting.
-14, 11, 18, 16--
-Pierre was in great voice tonight.
I could tell that tonight's message was really important.
-3, 25.
That's a message from Annie herself.
Remember, don't tell anyone.
-90 Seconds later, I'm in the only room in the house where a boy of nine
could sit in privacy and decode.
Aha, B. I went to the next.
E. The first word is be.
S. It was coming easier now.
U.
-Oh, come on, Ralphie.
I got to go.
-I'll be right down, ma.
-Gee whiz.
-T, O. Be sure to.
Be sure to what?
What was Little Orphan Annie trying to say?
Be sure to what?
-Ralphie!
Randy has got to go.
Will you please come out?
-All right, ma.
I'll be right out.
-I was getting closer now.
The tension was terrible.
What was it?
The fate of the planet may hang in the balance.
-Ralphie!
Randy's got to go.
-I'll be right out, for crying out loud.
-Gee, almost there.
My fingers flew.
My mind was a steel trap.
Every pore vibrated.
It was almost clear.
Yes, yes, yes, yes.
-Be sure to drink your Ovaltine.
Ovaltine?
A crummy commercial?
Son of a bitch.
[END VIDEO PLAYBACK]
>> DAVID J. MALAN: So there we have cryptography.
So how in a computer can we go about implementing or
representing things like this?
Well, we need a way of expressing ourselves a little more flexibly than
our variables thus far have allowed.
We've had ints.
We've had chars.
We've had floats and doubles and a few others.
But those are individual pieces of memory that don't really allow us to
express things like words and sentences and phrases.
Indeed, we've called such things strings.
But we promised that this is really just a simplification in the CS50
library that we're intending to peel back.
>> And so let's start to do that here.
Let me go ahead and open up a file--
all of these files are available as usual online--
called array.c to solve a problem unrelated to strings but that paints a
picture here of how we might use something called an array.
An array is a data type.
It's a type of variable, of sorts, that has multiple smaller data types
inside of it back to back to back to back.
So for instance, if we want to write a little program that gives you your
quiz average for a course like 50 that has two quizzes, you could very easily
write this program--based even on some of last week's material--
by using GetInt and a couple of variables.
Int quiz1, int quiz2, and it's pretty straightforward.
It's maybe 10, 20 lines of code, max, to implement a program that asks the
user for two quiz scores and then computes their average by adding them
together, dividing by two, and then printing the results.
We could probably do that pretty readily now after
some number of minutes.
>> But the problem is that suppose that 50 had three quizzes or four.
Suppose that you wanted to use the same program for a class that had
weekly quizzes.
Think about a class that has weekly quizzes.
If there's like 16 or so weeks in a semester, now you have 16 variables--
int quiz1, int quiz2, int quiz3, int quiz4.
As soon as you start seeing this redundancy, this copying and pasting
of code, it should start to make you wish there were a better way.
And thankfully, because of arrays, there is.
So let's do this.
First, let me introduce a very simple thing that we've not used thus far,
but you'll see it occasionally in code.
This is what's generally called a constant.
So it's a constant in the sense that this value never changes.
The human convention when creating a constant is to use all capital
letters, just so that it really stands out in your code.
And the special keyword that you use in C is #define.
So if you say #define, then a space, then the word that you want to use for
the constant's name, and then the value of the constant.
So notice, this is different from assigning something to a variable.
There's no equals sign.
There's no semicolon.
This is what's generally known as a preprocessor directive, but more on
that another time.
>> For now, this creates an unchanging value called QUIZZES whose actual
numeric value is 2.
So anywhere you see QUIZZES, QUIZZES, QUIZZES throughout this file, that's
just the number 2.
Now, if I look at main now, let's see how this works.
At first, it looks a little cryptic.
But it's all stuff from week one.
Ask the user for grades.
How do we do this?
Well, in line 22--
this is really the juicy part--
I declare a float, but not just a single float.
I'm declaring, rather, an array of floating point values.
That variable is going to be called grades, as implied here.
But the only piece of new syntax then are these square brackets, the fact
that I've said float grades and then open bracket and then a number.
Notice, if this is a constant, this is just like we did this.
This means hey computer, give me two floats, and let's collectively call
them grades.
This is in contrast to a much more tedious process like this.
Float grade1, float grade2, and so forth.
So an array allows us to implement this idea but much less messily, in
such a way that we can write one line of code instead of, say, 16 for a 16
week semester.
So I didn't want to hard-code 2 because if you think about this now
logically--suppose next year CS50 changes to 3 quizzes instead.
And I had the number 2 here.
I had the number 2 here.
It becomes very tedious and very easy to screw up and to accidentally change
one value to 3 and miss some other value of 2.
So I'm going to instead abstract this away and use this constant that, as its
name suggests, never changes.
And now, no matter whether we have different quizzes this year or next, I
just have to change it in one place, up here at top.
>> So that's all constant is.
Meanwhile, the new conceptual feature is that of an array.
So the square brackets give me this many floats and lets me collectively
call them grades here.
So now let's see what I'm going to do.
Here in line 24 is the beginning of a for loop.
This is really nothing fancy.
It's just using quizzes instead of a hard-coded number.
But there's nothing intellectually different there from last week.
This is just printf.
So printf("quiz number %d of %d") because I just want to print out give me quiz
number one of two and then two of two.
So this is purely an aesthetic thing.
But the interesting part now is in line 27.
In order to fill in one of the two placeholders with a floating-point
value, you again use square brackets.
In this case, I'm using i because this for loop has started with i equaling
what value, apparently?
0.
>> So on the first iteration of this loop, it is as though I
wrote this in code.
But on the second iteration of this loop, it is as though I
wrote this in my code.
But the fact that I'm using a variable is perfect because, as the name
suggests, it's varying its value on every iteration.
So I'm filling this array one spot at a time.
What does this array look like?
Well, the reason I drew this super simple rectangle on the screen here
before was for this reason.
An array is just a chunk of memory followed by another chunk of memory,
followed by another chunk of memory, and so forth.
So if my array is of size 2, in this case here, all I would be doing by
typing in my quiz scores, like here.
I got 100 on this one.
And then I got a 99 on this one.
Then this memory might not even be used because I've only asked the
computer for an array of size 2.
Those squares are still there.
Right?
You still have two gigabytes of RAM, even if you're only
asking for two floats.
So the idea behind arrays is that the computer just takes a chunk of memory
and then apportions smaller pieces back to back to back to back.
And so that's all an array is.
It's a contiguous chunk of memory, inside of which you can put things.
>> Now this happens to then do just some boring arithmetic.
If I scroll down here, this is where I then iterate over the array.
I come up with the summation of all the values in the array.
And then I use the round function here to actually do the
sum divided by quizzes.
But let me wave my hand at that as sort of enough arithmetic for now.
But all that's doing for me ultimately is computing an average.
So first quiz plus second quiz, divided by 2, and then printing
it out as an int.
>> But let's now transition to a different example called string1,
which paints a similar picture but using strings.
Let me go ahead and simplify this for just a moment.
And forgive the indentation for now.
Notice in line 19 of this example, I get a string from the user.
But notice what I'm next doing in lines 22 onward.
I'm actually iterating from i up to--and this is a new trick--
strlen, string length.
This is a function that comes with C that if you pass it a string, it tells
you how many characters are in that string.
That's all.
The fact that it's strlen instead of string length is just because it's
more succinct.
30 years ago, people liked to write things as succinctly as possible.
So we've kept that convention here.
i++ just means increment i in each iteration.
And now notice this, which is really interesting.
So in line 24, I say computer, give me a character, eight
bits, and call it c.
But what is this on the right hand side saying?
In English, what does that represent?
[INAUDIBLE]
DAVID J. MALAN: Exactly.
Give me the first character in the array.
Or more generally, give me the i-th character in the array.
And realize it's important now that as computer scientists, we're actually
counting from 0.
You don't have discretion now to start doing this.
Now you have to behave in accordance with the computer's expectations and
count from zero because [0] is going to be the first
character in a string.
[1] is going to be the second.
[2] is going to be the third, and so forth.
So this program, if I compile it--this is, again, string1.
>> So make string1.
And now I run string1 in my terminal window.
It's waiting for input, so I'm going to type in, say, David.
Enter.
And now it prints D-A-V-I-D all on different lines because
notice what I'm doing.
I'm printing one character at a time.
Now we won't go into detail today on this.
But I deleted a moment ago this check here.
It turns out that if the user is misbehaving, adversarial, or just
confused, you can actually fail to give a string of some length.
If you hit the wrong key on the keyboard, you might give
no string at all.
Or if you're malicious, you might try to paste in a gigabyte's worth of an
essay to fill this string.
And if the computer runs out of memory, it turns out that we're going
to get back this special value called null.
So for now, just know that there's this special value called null that
will allow us to check when we're out of memory, among other things.
>> But if I open up now string2, notice one difference here.
Notice one difference here with string2.
With string2, this for loop is a little different.
Let me delete the nulls so that we can talk about those another time.
But what's different about the for loop this time?
And I can go back to the previous example.
So that's version two.
This is version one.
One, two, one two.
So the strlen call is where?
It's in the first part of the for loop.
Any thoughts as to why I'm doing this?
Yeah.
[INAUDIBLE]
DAVID J. MALAN: So we don't call the function every single time.
Exactly.
Recall from for loops that they're super simple once you sort of
understand that this is the initialization, the
condition, and the update.
The problem is that the condition happens on every
iteration of the loop.
And so in this example here, what is bad about the fact
that this is my condition?
You're calling strlen again and again and again.
But once I've typed in D-A-V-I-D, the length of that string is five.
And it's not going to change on every iteration of the loop because the
string is still D-A-V-I-D. So this is a hint at what's going to become an
increasingly important idea known as a design decision, where--just don't
make the computer do unnecessary work.
>> Now just as a sneak preview of pset 2, pset 2 in the standard edition is
going to challenge you to actually implement some number of ciphers, some
number of encryption algorithms, so that you can both encrypt and decrypt
secret messages, much like the one Ralphie there decoded.
In the hacker edition of pset 2, we're going to go a little further.
We're going to hand you a file from an actual computer system that contains a
whole bunch of usernames and actual encrypted passwords, and the challenge
for the hacker edition is going to be to crack those passwords and figure
out what cryptography or what secret was used to actually
generate those passwords.
And we're going to do this by using a new feature here of C that I'll give
you just a demo of, known as command-line arguments.
>> So it turns out, as some of you may have seen in section or in textbooks,
main does not always have to be void in parentheses.
It turns out that main can also be written like this, with two arguments,
argc and argv, where argc is the number of words that you type after
the program's name on your command line.
And argv is the actual words.
And as the square brackets there suggest, argv is apparently an array.
It's going to be a string after a string after a string in memory.
So what we're going to be able to do, starting with pset 2, is
something like this.
If I make argv1, which is an example we'll come back to on Monday, and run
it, notice that it doesn't seem to do anything yet.
It just prints out its own name.
But if I say goodbye class, notice that this program apparently iterates
over each of the words that were typed at the prompt.
And the means by which we will gain access to words that the user has
typed at the prompt is by changing main, starting this weekend, from int
main (void) to int main (argc, argv).
And thus will be born command line arguments.
And once you get really sophisticated at this, you'll be able to write
really trippy programs, such as this one here, which goes above and beyond
some of the functionality we've done thus far but all quite powerful.
>> So we'll leave this with this on the screen.
And we will see you on Monday.