1
00:00:07,420 --> 00:00:08,160
DAVID J. MALAN: All right.

2
00:00:08,160 --> 00:00:11,170
This is CS50, and this is the end of week two.

3
00:00:11,170 --> 00:00:14,650
If you expect to be hungry around this time tomorrow, know that we're going

4
00:00:14,650 --> 00:00:18,920
to convene as a small group tomorrow, Thursday, 1:15 PM.

5
00:00:18,920 --> 00:00:21,460
There's this URL here if you'd like to RSVP.

6
00:00:21,460 --> 00:00:25,270
Space is limited, so please forgive if the form has filled up by the time you

7
00:00:25,270 --> 00:00:26,680
fill this out.

8
00:00:26,680 --> 00:00:29,400
Another URL though that might be of interest is this.

9
00:00:29,400 --> 00:00:32,409
>> So in just about a month's time, the course is going to be made available

10
00:00:32,409 --> 00:00:36,090
all the more broadly via edX, via which folks on the Internet will be

11
00:00:36,090 --> 00:00:39,580
able to follow along, engage in the course quite actively, in fact.

12
00:00:39,580 --> 00:00:43,070
They'll be using the CS50 Appliance and CS50 Discuss and most of the

13
00:00:43,070 --> 00:00:45,840
various software tools that we already have been using this semester.

14
00:00:45,840 --> 00:00:49,030
And one of the initiatives we'd like to take on as an experiment this year

15
00:00:49,030 --> 00:00:53,120
is to see just how much content we can translate into other spoken and

16
00:00:53,120 --> 00:00:54,110
written languages.

17
00:00:54,110 --> 00:00:58,000
So if you might have an interest in participating in this project, whereby

18
00:00:58,000 --> 00:01:02,090
we will provide English transcripts and subtitles for the course's

19
00:01:02,090 --> 00:01:05,190
lectures and shorts and seminars and sections and the like--

20
00:01:05,190 --> 00:01:08,700
if you speak fluently or write fluently some other language, we would

21
00:01:08,700 --> 00:01:12,240
love to engage you in this project, whereby you take on one or more of the

22
00:01:12,240 --> 00:01:15,340
videos, translating them into a language you know quite well.

23
00:01:15,340 --> 00:01:19,050
To give you a sense of the interface, there's this web-based user interface

24
00:01:19,050 --> 00:01:22,330
that we'll be using that will create essentially a UI like this.

25
00:01:22,330 --> 00:01:24,520
This was me teaching some Halloween ago.

26
00:01:24,520 --> 00:01:27,710
And on the right hand side there in black next to these time stamps,

27
00:01:27,710 --> 00:01:31,300
you'll see the various things that came out of my mouth that day.

28
00:01:31,300 --> 00:01:34,660
And then below it, you'll be able to translate into some other language.

29
00:01:34,660 --> 00:01:37,840
Exactly what the mapping is between, in this case, English

30
00:01:37,840 --> 00:01:38,660
and, say, Spanish.

31
00:01:38,660 --> 00:01:40,480
So it's actually a very user-friendly tool.

32
00:01:40,480 --> 00:01:43,690
You can rewind and fast forward very readily with keyboard shortcuts.

33
00:01:43,690 --> 00:01:46,710
So if you would like to take part in this experiment and have your words

34
00:01:46,710 --> 00:01:50,730
seen and read by potentially thousands of folks out there, please do feel

35
00:01:50,730 --> 00:01:51,960
free to participate.

36
00:01:51,960 --> 00:01:56,940
>> Now one word about the kitten from Monday, lest we have sent an overly

37
00:01:56,940 --> 00:01:58,120
scary message.

38
00:01:58,120 --> 00:02:02,130
Do realize that as office hours suggest and as sections suggest, the

39
00:02:02,130 --> 00:02:05,110
design of the course is very much to have students collaborating and

40
00:02:05,110 --> 00:02:09,250
talking to work through problem sets and problems together.

41
00:02:09,250 --> 00:02:13,630
And really the line just comes down to, again, the work you ultimately

42
00:02:13,630 --> 00:02:16,420
should submit should be your own.

43
00:02:16,420 --> 00:02:19,080
And so it's, quite honestly--in office hours, it's totally normal--

44
00:02:19,080 --> 00:02:21,560
it's totally to be expected, even--to be chatting with some

45
00:02:21,560 --> 00:02:22,370
friends next to you.

46
00:02:22,370 --> 00:02:25,240
If he or she is struggling with some topic, and you're like, oh, well let

47
00:02:25,240 --> 00:02:27,750
me give you a glimpse of some line of code that I wrote.

48
00:02:27,750 --> 00:02:28,290
That's fine.

49
00:02:28,290 --> 00:02:28,700
That happens.

50
00:02:28,700 --> 00:02:31,580
And that's very much conducive, I think, with the process of learning.

51
00:02:31,580 --> 00:02:35,270
Where the line, again, gets crossed is when the head is sort of tilted over

52
00:02:35,270 --> 00:02:38,800
here for far too many seconds or minutes for that really to have just

53
00:02:38,800 --> 00:02:41,250
been an unblocking opportunity for your friend.

54
00:02:41,250 --> 00:02:43,870
And certainly, when things get exchanged via email and Dropbox and

55
00:02:43,870 --> 00:02:45,350
the like, there too is the line.

56
00:02:45,350 --> 00:02:48,940
So by all means, feel comfortable and feel encouraged to chat with friends

57
00:02:48,940 --> 00:02:51,270
and classmates about psets and more.

58
00:02:51,270 --> 00:02:54,680
And just realize that what you ultimately submit should really be the

59
00:02:54,680 --> 00:02:57,780
product of your creation and not someone else.

60
00:02:57,780 --> 00:03:01,010
>> So in the same vein of cuddly creatures, you might

61
00:03:01,010 --> 00:03:02,820
know of this guy here.

62
00:03:02,820 --> 00:03:06,180
So this is a horrifically cheesy movie from years ago.

63
00:03:06,180 --> 00:03:08,680
Anyone here seen Spaceballs?

64
00:03:08,680 --> 00:03:09,120
All right.

65
00:03:09,120 --> 00:03:10,220
So a good number here.

66
00:03:10,220 --> 00:03:13,840
So this is our wonderfully academic way of introducing today ultimately

67
00:03:13,840 --> 00:03:15,130
the notion of cryptography.

68
00:03:15,130 --> 00:03:19,010
And so one of the domain specific problems for pset 2, which will come

69
00:03:19,010 --> 00:03:22,770
out late tomorrow night, is to dive into the world of cryptography, which

70
00:03:22,770 --> 00:03:26,380
is the art of encrypting or scrambling information.

71
00:03:26,380 --> 00:03:30,160
And this ultimately relates to the world of security.

72
00:03:30,160 --> 00:03:34,440
>> Now security for most us comes in the form of fairly mundane mechanisms.

73
00:03:34,440 --> 00:03:36,920
All of us have usernames and passwords.

74
00:03:36,920 --> 00:03:41,350
And all of us have very bad usernames and passwords, most likely.

75
00:03:41,350 --> 00:03:45,250
If your password is the same on multiple websites, that's probably not

76
00:03:45,250 --> 00:03:47,920
the best idea, as we'll discuss towards semester's end.

77
00:03:47,920 --> 00:03:51,680
If your password is written on a sticky note--no joke--on your

78
00:03:51,680 --> 00:03:55,130
monitor, that too is not necessarily the best design but quite a common

79
00:03:55,130 --> 00:03:56,140
phenomenon.

80
00:03:56,140 --> 00:04:00,420
And if you're not using cryptography to encrypt your passwords, they are

81
00:04:00,420 --> 00:04:01,610
particularly vulnerable.

82
00:04:01,610 --> 00:04:04,670
So if you think you're being super clever by having a hidden Word

83
00:04:04,670 --> 00:04:07,740
document somewhere on your hard drive that has all of your passwords but

84
00:04:07,740 --> 00:04:10,550
it's in a folder that no one's going to look in, that too is not a very

85
00:04:10,550 --> 00:04:11,540
secure mechanism.

86
00:04:11,540 --> 00:04:15,100
And so what pset 2 will introduce is this art of cryptography and

87
00:04:15,100 --> 00:04:18,300
scrambling information so that things like passwords are

88
00:04:18,300 --> 00:04:19,500
all the more secure.

89
00:04:19,500 --> 00:04:24,500
So as to motivate this very real-world problem with a very non-real-world

90
00:04:24,500 --> 00:04:28,740
scenario, let me introduce you to one of our favorite clips here from this

91
00:04:28,740 --> 00:04:29,895
movie, Spaceballs.

92
00:04:29,895 --> 00:04:30,565
>> [VIDEO PLAYBACK]

93
00:04:30,565 --> 00:04:32,995
-Helmet, you fiend, what's going on?

94
00:04:32,995 --> 00:04:34,730
What are you doing to my daughter?

95
00:04:34,730 --> 00:04:38,960
-Permit me to introduce the brilliant young plastic surgeon, Dr. Philip

96
00:04:38,960 --> 00:04:43,290
Schlotkin, the greatest nose job man in the entire

97
00:04:43,290 --> 00:04:45,526
universe and Beverly Hills.

98
00:04:45,526 --> 00:04:46,450
-Your highness.

99
00:04:46,450 --> 00:04:47,380
-Nose job?

100
00:04:47,380 --> 00:04:48,035
I don't understand.

101
00:04:48,035 --> 00:04:49,480
She's already had a nose job.

102
00:04:49,480 --> 00:04:51,490
It was a sweet 16 present.

103
00:04:51,490 --> 00:04:53,090
-No, it's not what you think.

104
00:04:53,090 --> 00:04:55,150
It's much, much worse.

105
00:04:55,150 --> 00:04:59,860
If you do not give me the combination to the air shield, Dr. Schlotkin will

106
00:04:59,860 --> 00:05:04,135
give your daughter back her old nose.

107
00:05:04,135 --> 00:05:05,385
-No!

108
00:05:08,202 --> 00:05:10,186
Where did you get that?

109
00:05:10,186 --> 00:05:11,178
-All right.

110
00:05:11,178 --> 00:05:11,674
I'll tell.

111
00:05:11,674 --> 00:05:12,666
I'll tell.

112
00:05:12,666 --> 00:05:14,154
-No, daddy, no.

113
00:05:14,154 --> 00:05:15,150
You mustn't.

114
00:05:15,150 --> 00:05:16,460
-You're right, my dear.

115
00:05:16,460 --> 00:05:18,450
I'll miss your new nose.

116
00:05:18,450 --> 00:05:21,550
But I will not tell them the combination no matter what.

117
00:05:21,550 --> 00:05:23,100
-Very well.

118
00:05:23,100 --> 00:05:25,510
Dr. Schlotkin, do your worst.

119
00:05:25,510 --> 00:05:26,760
-My pleasure.

120
00:05:30,560 --> 00:05:31,180
-No!

121
00:05:31,180 --> 00:05:33,450
Wait, wait.

122
00:05:33,450 --> 00:05:34,770
I'll tell.

123
00:05:34,770 --> 00:05:36,400
I'll tell.

124
00:05:36,400 --> 00:05:38,630
-I knew it would work.

125
00:05:38,630 --> 00:05:42,040
All right, give it to me.

126
00:05:42,040 --> 00:05:46,890
-The combination is one.

127
00:05:46,890 --> 00:05:47,290
-One.

128
00:05:47,290 --> 00:05:48,183
-One.

129
00:05:48,183 --> 00:05:48,950
-Two.

130
00:05:48,950 --> 00:05:49,370
-Two.

131
00:05:49,370 --> 00:05:50,450
-Two.

132
00:05:50,450 --> 00:05:50,715
-Three

133
00:05:50,715 --> 00:05:51,380
-Three.

134
00:05:51,380 --> 00:05:52,390
-Three.

135
00:05:52,390 --> 00:05:53,200
-Four.

136
00:05:53,200 --> 00:05:53,720
-Four.

137
00:05:53,720 --> 00:05:55,830
-Four.

138
00:05:55,830 --> 00:05:56,580
-Five

139
00:05:56,580 --> 00:05:57,120
-Five.

140
00:05:57,120 --> 00:05:58,560
-Five.

141
00:05:58,560 --> 00:06:03,770
-So the combination is one, two, three, four, five.

142
00:06:03,770 --> 00:06:06,745
That's the stupidest combination I ever heard in my life.

143
00:06:06,745 --> 00:06:09,290
That's the kind of thing an idiot would have on his luggage.

144
00:06:09,290 --> 00:06:11,540
-Thank you, your highness.

145
00:06:11,540 --> 00:06:12,940
-What did you do?

146
00:06:12,940 --> 00:06:14,230
-I turned off the wall.

147
00:06:14,230 --> 00:06:14,630
-No, you didn't.

148
00:06:14,630 --> 00:06:15,430
You turned off the whole movie.

149
00:06:15,430 --> 00:06:16,722
-I must have pressed the wrong button.

150
00:06:16,722 --> 00:06:18,078
-Well, put it back on.

151
00:06:18,078 --> 00:06:18,805
Put the movie back on.

152
00:06:18,805 --> 00:06:19,080
-Yes, sir.

153
00:06:19,080 --> 00:06:19,270
Yes, sir.

154
00:06:19,270 --> 00:06:19,830
-Let's go, Erna.

155
00:06:19,830 --> 00:06:20,270
Come, Gretchen.

156
00:06:20,270 --> 00:06:22,850
Of course you know I'll still have to bill you for this.

157
00:06:27,400 --> 00:06:28,325
-Well, did it work?

158
00:06:28,325 --> 00:06:29,550
Where's the gate?

159
00:06:29,550 --> 00:06:29,910
-It worked, sir.

160
00:06:29,910 --> 00:06:30,770
We have the combination.

161
00:06:30,770 --> 00:06:31,390
-Great.

162
00:06:31,390 --> 00:06:35,630
Now we can take every last breath of fresh air from planet Druidia.

163
00:06:35,630 --> 00:06:36,550
What's the combination?

164
00:06:36,550 --> 00:06:38,805
-One, two, three, four, five.

165
00:06:38,805 --> 00:06:40,610
-One, two, three, four, five?

166
00:06:40,610 --> 00:06:41,070
-Yes.

167
00:06:41,070 --> 00:06:41,760
-That's amazing.

168
00:06:41,760 --> 00:06:45,200
I've got the same combination on my luggage.

169
00:06:45,200 --> 00:06:47,800
Prepare Spaceball 1 for immediate departure.

170
00:06:47,800 --> 00:06:48,536
-Yes, sir.

171
00:06:48,536 --> 00:06:52,350
-And change the combination on my luggage.

172
00:06:52,350 --> 00:06:53,250
-Ow!

173
00:06:53,250 --> 00:06:55,020
[END VIDEO PLAYBACK]

174
00:06:55,020 --> 00:06:57,470
>> DAVID J. MALAN: An amazing movie you should now all see.

175
00:07:00,600 --> 00:07:06,540
So the context here is that with insecure data comes an opportunity to

176
00:07:06,540 --> 00:07:07,790
encrypt it and to scramble it.

177
00:07:07,790 --> 00:07:11,060
And so this, for instance, is an example of an encrypted message.

178
00:07:11,060 --> 00:07:12,980
This actually says something in English.

179
00:07:12,980 --> 00:07:14,750
But it's clearly not wholly obvious.

180
00:07:14,750 --> 00:07:17,360
And we'll come full circle today to tease apart what this secret

181
00:07:17,360 --> 00:07:18,380
message here is.

182
00:07:18,380 --> 00:07:22,370
But in the real world of computers, things don't even look like they might

183
00:07:22,370 --> 00:07:23,440
be English phrases.

184
00:07:23,440 --> 00:07:27,500
For instance, this is what you might find on a standard Linux or Mac or

185
00:07:27,500 --> 00:07:32,080
Unix computer in a file that was once upon a time called the password file.

186
00:07:32,080 --> 00:07:34,170
Nowadays, it's been moved to other places.

187
00:07:34,170 --> 00:07:38,660
But if you look in the right place on a system, you'll see not only your

188
00:07:38,660 --> 00:07:41,430
username or that of other people on the system, but you'll see an

189
00:07:41,430 --> 00:07:43,410
encrypted version of their password.

190
00:07:43,410 --> 00:07:47,800
Indeed, the word crypt there suggests that the following stuff is encrypted.

191
00:07:47,800 --> 00:07:52,030
And this series of seemingly random letters and characters and numbers and

192
00:07:52,030 --> 00:07:56,370
so forth can be decrypted only by generally knowing some secret--

193
00:07:56,370 --> 00:07:58,600
a secret word, a secret number.

194
00:07:58,600 --> 00:08:02,760
And so indeed, the art of cryptography ultimately boils down to trust of some

195
00:08:02,760 --> 00:08:05,700
sort and knowing something that someone else does not.

196
00:08:05,700 --> 00:08:10,010
We'll explore this in a bit more detail today and in the pset to come.

197
00:08:10,010 --> 00:08:11,860
>> And now a word on pass/fail.

198
00:08:11,860 --> 00:08:15,250
So especially, as some of you have dived into pset 1, the appliance, and

199
00:08:15,250 --> 00:08:18,390
a very new world for yourself, realized that frustrations and

200
00:08:18,390 --> 00:08:21,340
confusion and just technical difficulties are to be expected.

201
00:08:21,340 --> 00:08:24,410
Especially with the first pset, where there's just so much new, just getting

202
00:08:24,410 --> 00:08:28,830
familiar with ls and cd and all these arcane commands in a new environment.

203
00:08:28,830 --> 00:08:32,679
And that's separate from the actual material and programming itself.

204
00:08:32,679 --> 00:08:35,960
So realize, too, that there are certainly office hours that exist as

205
00:08:35,960 --> 00:08:36,770
the support structure.

206
00:08:36,770 --> 00:08:38,620
Sections begin this coming Sunday.

207
00:08:38,620 --> 00:08:41,990
But most importantly, if you're feeling just that this is not the

208
00:08:41,990 --> 00:08:44,420
world for you, realize that it really does just take time.

209
00:08:44,420 --> 00:08:47,520
And were it not for this opportunity years ago for me of taking a class

210
00:08:47,520 --> 00:08:50,840
pass/fail, honestly, I never would have even set foot in the classroom.

211
00:08:50,840 --> 00:08:53,520
And you can change this up until, say, the fifth Monday of the course.

212
00:08:53,520 --> 00:08:57,110
So if you're on the edge now, realize that rather than head into some other

213
00:08:57,110 --> 00:09:01,000
waters altogether, do certainly consider just changing to pass/fail.

214
00:09:01,000 --> 00:09:03,750
Again, there's not really this culture here at Harvard of taking things

215
00:09:03,750 --> 00:09:08,080
pass/fail since everyone really wants to achieve or overachieve.

216
00:09:08,080 --> 00:09:11,470
But frankly, this is a wonderful way of trying something out that might not

217
00:09:11,470 --> 00:09:13,110
be familiar to you.

218
00:09:13,110 --> 00:09:17,090
And you'll end up doing in most cases quite fine, perhaps

219
00:09:17,090 --> 00:09:18,040
much to your surprise.

220
00:09:18,040 --> 00:09:20,850
And in more concrete terms, what I think pass/fail generally does,

221
00:09:20,850 --> 00:09:23,350
especially as you might have experienced with pset 0, if you've put

222
00:09:23,350 --> 00:09:27,200
in 10 hours, 15 hours, 25 hours into some pset--and you're just banging

223
00:09:27,200 --> 00:09:28,180
your head against the wall,

224
00:09:28,180 --> 00:09:29,850
and it's getting super late at night,

225
00:09:29,850 --> 00:09:31,880
but you've taken the pset like 90% of the way,

226
00:09:31,880 --> 00:09:33,780
you know you just can't figure out one thing--

227
00:09:33,780 --> 00:09:36,830
pass/fail really takes the edge off of a class like this, where you can sort

228
00:09:36,830 --> 00:09:39,150
of happily say okay, I know it's not perfect.

229
00:09:39,150 --> 00:09:40,470
But I worked my ass off on this.

230
00:09:40,470 --> 00:09:42,410
I'm pretty happy with where it ended up.

231
00:09:42,410 --> 00:09:44,780
And that will meet the expectations for pass/fail.

232
00:09:44,780 --> 00:09:46,850
So do keep that in mind.

233
00:09:46,850 --> 00:09:47,140
>> All right.

234
00:09:47,140 --> 00:09:50,980
So those of you who have struggled to use the Harvard University Wi-Fi know

235
00:09:50,980 --> 00:09:54,780
that there's a CS50 SSID, a Wi-Fi connection floating around that you

236
00:09:54,780 --> 00:09:56,520
might have better luck for.

237
00:09:56,520 --> 00:09:59,430
It's a little ironic that the password for this--if you would like to try

238
00:09:59,430 --> 00:10:03,080
connecting to this for better speeds and let us know if it's no better--

239
00:10:03,080 --> 00:10:09,240
is one, two, three, four, five, all the way up to eight because eight is

240
00:10:09,240 --> 00:10:10,270
more secure than five.

241
00:10:10,270 --> 00:10:15,520
So if you need the Wi-Fi password, connect to CS50 wirelessly here.

242
00:10:15,520 --> 00:10:16,950
One, two, three, four, five, six, seven, eight.

243
00:10:16,950 --> 00:10:20,440
And post on CS50 Discuss if you still have intermittent connectivity issues,

244
00:10:20,440 --> 00:10:24,880
and we'll let the powers that be know for this space.

245
00:10:24,880 --> 00:10:25,180
>> All right.

246
00:10:25,180 --> 00:10:30,350
So a quick teaser, especially for those of you who are fan boys or girls

247
00:10:30,350 --> 00:10:31,900
of all things Apple.

248
00:10:31,900 --> 00:10:37,566
What I dug up from a few years back was this file here, ilock.c, just to

249
00:10:37,566 --> 00:10:40,930
kind of make more concrete and more complex some of the more basic C

250
00:10:40,930 --> 00:10:42,350
programs we've been writing.

251
00:10:42,350 --> 00:10:44,360
So I opened up this file, ilock.c.

252
00:10:44,360 --> 00:10:46,830
It's available on the lectures page for today.

253
00:10:46,830 --> 00:10:49,470
On the left-hand side, you see a long list of functions.

254
00:10:49,470 --> 00:10:51,860
So the fellow who wrote this wrote up a lot of functions,

255
00:10:51,860 --> 00:10:53,290
more than just main.

256
00:10:53,290 --> 00:10:55,490
He used a whole bunch of libraries here.

257
00:10:55,490 --> 00:11:00,450
And if we start scrolling through, what this actually is is the very

258
00:11:00,450 --> 00:11:04,670
first, I believe, crack for the original iPhone.

259
00:11:04,670 --> 00:11:08,000
When you wanted to jailbreak the original iPhone, which means untether

260
00:11:08,000 --> 00:11:11,800
it from AT&T and actually install special software on it and do things

261
00:11:11,800 --> 00:11:13,510
that Apple didn't want people to do--

262
00:11:13,510 --> 00:11:17,020
well, someone took the time to figure out exactly how they could exploit

263
00:11:17,020 --> 00:11:20,880
software flaws, mistakes, bugs, in Apple's software.

264
00:11:20,880 --> 00:11:22,650
And thus was born ilock.c.

265
00:11:22,650 --> 00:11:26,670
That if you compiled it on a computer and installed it onto an iPhone that

266
00:11:26,670 --> 00:11:29,810
was connected to your computer via, say, a USB cable, this would give you

267
00:11:29,810 --> 00:11:33,360
administrative or root privileges on your iPhone and let you do pretty much

268
00:11:33,360 --> 00:11:34,170
whatever you want.

269
00:11:34,170 --> 00:11:36,740
>> And so there's been this fascinating cat and mouse game between Apple and

270
00:11:36,740 --> 00:11:39,920
the rest of the world in particular as they, like many companies, try to lock

271
00:11:39,920 --> 00:11:43,220
their stuff down so that you can only do with it what they intend.

272
00:11:43,220 --> 00:11:46,620
But thanks to people like this and their understanding of low-level

273
00:11:46,620 --> 00:11:50,580
details and, in this case, C programming and a lot of the familiar constructs

274
00:11:50,580 --> 00:11:54,630
that we've started playing with, you are able to really leverage the

275
00:11:54,630 --> 00:11:59,050
hardware in a manner you see fit and not necessarily some corporate entity.

276
00:11:59,050 --> 00:12:01,360
So for instance, I have no idea what all this is doing.

277
00:12:01,360 --> 00:12:03,220
But GetVersion sounds pretty straightforward.

278
00:12:03,220 --> 00:12:05,480
And it looks like this is a function that this person wrote.

279
00:12:05,480 --> 00:12:09,240
Take some kind of integer as an argument, doesn't return anything, but

280
00:12:09,240 --> 00:12:13,080
appears to loop with a for loop here and an if condition, if condition,

281
00:12:13,080 --> 00:12:15,620
break, and somehow relates to version numbers.

282
00:12:15,620 --> 00:12:16,700
If we scroll down--

283
00:12:16,700 --> 00:12:19,570
even though a lot of these keywords are going to be new, and there's a

284
00:12:19,570 --> 00:12:22,590
whole lot of functions in here we've never seen and might not ever see over

285
00:12:22,590 --> 00:12:23,830
the course of the semester--

286
00:12:23,830 --> 00:12:27,150
at the end of the day, it follows the same rules and logic that we've been

287
00:12:27,150 --> 00:12:28,760
playing with thus far.

288
00:12:28,760 --> 00:12:34,220
So this is far too old to crack your iPhone 3s or 4s or soon 5s, these days,

289
00:12:34,220 --> 00:12:37,320
but know that it's all very much derived from this world that we've

290
00:12:37,320 --> 00:12:38,430
dived into.

291
00:12:38,430 --> 00:12:41,900
>> So let's take a look at a little more simple example.

292
00:12:41,900 --> 00:12:46,100
This one, just to get warmed up with some syntax and also some other data

293
00:12:46,100 --> 00:12:49,240
type that we've talked about but haven't really seen in C. So this is a

294
00:12:49,240 --> 00:12:51,680
file called positive1.c.

295
00:12:51,680 --> 00:12:55,120
And per the comments at the top, this just demands that a user provide a

296
00:12:55,120 --> 00:12:55,960
positive number.

297
00:12:55,960 --> 00:12:59,530
So it's an example of a do-while loop, which is nice for user-interactive

298
00:12:59,530 --> 00:13:01,980
programs where you need to tell the user to do something.

299
00:13:01,980 --> 00:13:05,190
And if they don't cooperate, you yell at them or reject their input.

300
00:13:05,190 --> 00:13:11,610
Case in point, I am going to do lines 19 through 24 so long as the user has

301
00:13:11,610 --> 00:13:14,310
not given me a positive number.

302
00:13:14,310 --> 00:13:20,400
Now this detail here on line 18, why did I declare n above this whole

303
00:13:20,400 --> 00:13:24,490
looping construct as opposed to right next to line 22 where I

304
00:13:24,490 --> 00:13:26,880
actually care to get n?

305
00:13:26,880 --> 00:13:27,330
Yeah?

306
00:13:27,330 --> 00:13:27,780
[INAUDIBLE]

307
00:13:27,780 --> 00:13:29,040
>> DAVID J. MALAN: Yeah, so this issue of scope.

308
00:13:29,040 --> 00:13:30,850
And in layman's term, what does scope refer to?

309
00:13:34,690 --> 00:13:36,610
Yeah?

310
00:13:36,610 --> 00:13:37,860
[INAUDIBLE]

311
00:13:40,040 --> 00:13:41,105
DAVID J. MALAN: Can you speak a little louder?

312
00:13:41,105 --> 00:13:43,450
SPEAKER 1: Where you can access a particular variable.

313
00:13:43,450 --> 00:13:45,170
DAVID J. MALAN: Perfect.

314
00:13:45,170 --> 00:13:47,360
Where you can access a particular variable.

315
00:13:47,360 --> 00:13:50,400
And generally, the rule of thumb thus far has been that the scope of some

316
00:13:50,400 --> 00:13:55,860
variable is defined by the most recent curly braces that you've seen.

317
00:13:55,860 --> 00:14:02,010
And so in this case, if I made the mistake of declaring n on line 22,

318
00:14:02,010 --> 00:14:03,010
that line would work.

319
00:14:03,010 --> 00:14:10,990
I would get an int, and I would put it into that variable n in line 22.

320
00:14:10,990 --> 00:14:16,900
But which line of code would now have no idea what I'm talking about?

321
00:14:16,900 --> 00:14:22,650
So 25, and it turns out 24, as well, because in this case, it falls outside

322
00:14:22,650 --> 00:14:23,610
of the curly braces.

323
00:14:23,610 --> 00:14:27,280
So just a little bit of a nuisance but very easily solved by simply declaring

324
00:14:27,280 --> 00:14:30,140
the variable outside of the function itself.

325
00:14:30,140 --> 00:14:32,600
>> Now we'll see later today, you can go one step further.

326
00:14:32,600 --> 00:14:34,860
And you could even get a little lazy--

327
00:14:34,860 --> 00:14:37,320
and this is not to be recommended, in general--

328
00:14:37,320 --> 00:14:42,260
but you could even get lazy and put a variable globally, so to speak, not

329
00:14:42,260 --> 00:14:46,670
inside of a function, not inside of a loop, but in the file itself, outside

330
00:14:46,670 --> 00:14:49,600
of all of the functions you've written, as I did here on line 15.

331
00:14:49,600 --> 00:14:51,160
But this is generally frowned upon.

332
00:14:51,160 --> 00:14:55,680
But realize this is a solution sometimes to other problems, as we'll

333
00:14:55,680 --> 00:14:56,620
eventually see.

334
00:14:56,620 --> 00:14:58,130
So for now, we'll leave it like this.

335
00:14:58,130 --> 00:15:01,030
But let's see if we can rewrite this just to start expressing ourselves a

336
00:15:01,030 --> 00:15:01,990
little differently.

337
00:15:01,990 --> 00:15:05,330
>> So this program, just to be clear, is positive1.

338
00:15:05,330 --> 00:15:11,810
Let me go ahead here and in my terminal window make positive1, Enter.

339
00:15:11,810 --> 00:15:12,740
Compiles, okay.

340
00:15:12,740 --> 00:15:14,910
I'm going to run positive1, hit Enter.

341
00:15:14,910 --> 00:15:16,820
I demand that you give me a positive integer.

342
00:15:16,820 --> 00:15:18,260
I'll say -1.

343
00:15:18,260 --> 00:15:18,910
That didn't work.

344
00:15:18,910 --> 00:15:22,150
0, 99, that seems to work.

345
00:15:22,150 --> 00:15:23,570
Maybe not the most rigorous test.

346
00:15:23,570 --> 00:15:26,480
But at least it's a nice sanity check that we're on the right track.

347
00:15:26,480 --> 00:15:29,240
So now let me go ahead and open version two of this.

348
00:15:29,240 --> 00:15:32,500
And what is different already?

349
00:15:32,500 --> 00:15:35,140
It implements the same thing.

350
00:15:35,140 --> 00:15:40,660
But what's jumping out as clearly different this time?

351
00:15:40,660 --> 00:15:42,560
Yeah, so this bool in green.

352
00:15:42,560 --> 00:15:45,980
Gedit has highlighted in green this keyword known as bool,

353
00:15:45,980 --> 00:15:47,000
which is a data type.

354
00:15:47,000 --> 00:15:51,080
It doesn't come built in to all versions of C. You need to include a

355
00:15:51,080 --> 00:15:52,010
specific library.

356
00:15:52,010 --> 00:15:54,770
In our case, I included the CS50 library so that we

357
00:15:54,770 --> 00:15:56,460
have access to bool.

358
00:15:56,460 --> 00:15:59,810
But in line 18, we seem to have a Boolean value here called thankful.

359
00:15:59,810 --> 00:16:01,040
So I could have called this anything.

360
00:16:01,040 --> 00:16:04,500
But I called it thankful just to kind of convey some semantic meaning.

361
00:16:04,500 --> 00:16:07,930
So initially on line 18, I'm apparently not thankful because the

362
00:16:07,930 --> 00:16:12,150
Boolean value thankful is initialized to false in line 18.

363
00:16:12,150 --> 00:16:16,890
And then it seems what I've done here in lines 21 through 23 is I've just

364
00:16:16,890 --> 00:16:18,610
kind of rewritten my logic.

365
00:16:18,610 --> 00:16:21,020
So no functionally different.

366
00:16:21,020 --> 00:16:26,940
But in line 22 now, I check if the int the user has provided is greater than

367
00:16:26,940 --> 00:16:31,120
0, then I simply change the value of thankful to true.

368
00:16:31,120 --> 00:16:32,290
And why do I do that?

369
00:16:32,290 --> 00:16:35,600
Because in line 25, apparently, I'm going to check a condition.

370
00:16:35,600 --> 00:16:39,380
Do this loop while thankful is false.

371
00:16:39,380 --> 00:16:43,610
>> So I propose this as an alternative to version one because it's at least a

372
00:16:43,610 --> 00:16:45,130
little more intuitive, perhaps.

373
00:16:45,130 --> 00:16:46,900
It's a little more grounded in English.

374
00:16:46,900 --> 00:16:51,710
So do the following while you are not thankful or while thankful is false.

375
00:16:51,710 --> 00:16:55,890
And this time, too, I apparently don't care to remember what the user typed

376
00:16:55,890 --> 00:16:57,730
in because notice there's no variable n.

377
00:16:57,730 --> 00:16:58,650
So actually, I--

378
00:16:58,650 --> 00:17:00,080
a little white lie there.

379
00:17:00,080 --> 00:17:02,770
Functionally, the program is a bit different once we get to the bottom of

380
00:17:02,770 --> 00:17:04,819
it because I'm not remembering what n is.

381
00:17:04,819 --> 00:17:09,579
But I wanted to demonstrate here too that even though we've seen GetInt and

382
00:17:09,579 --> 00:17:13,920
GetString being used on the right-hand side of an equal sign thus far so that

383
00:17:13,920 --> 00:17:17,160
we remember the value, technically, that's not strictly necessary.

384
00:17:17,160 --> 00:17:20,950
If for whatever reason you just don't care to save the value, you just want

385
00:17:20,950 --> 00:17:25,710
to check the value, notice that we can simply write this as GetInt open

386
00:17:25,710 --> 00:17:27,000
paren, close paren.

387
00:17:27,000 --> 00:17:30,460
That function is going to return a value, as we've been saying.

388
00:17:30,460 --> 00:17:32,010
It's going to give you back an int.

389
00:17:32,010 --> 00:17:36,450
And so if you mentally think of this happening, when I type in 99, GetInt

390
00:17:36,450 --> 00:17:38,160
returns the number 99.

391
00:17:38,160 --> 00:17:41,330
And so conceptually, it's as though my code were actually this.

392
00:17:41,330 --> 00:17:45,880
So if 99 is indeed greater than 0, then thankful becomes true.

393
00:17:45,880 --> 00:17:50,420
Then line 25 realizes ooh, we're done because I'm now thankful.

394
00:17:50,420 --> 00:17:54,590
And in line 26, we simply say, thanks for the positive integer, whatever it

395
00:17:54,590 --> 00:17:55,710
happened to be.

396
00:17:55,710 --> 00:17:58,900
>> Now let's do slight syntactic sugar here, so to speak.

397
00:17:58,900 --> 00:18:02,990
Let's see if we can clean up this line 25 with this third and final variance

398
00:18:02,990 --> 00:18:04,640
in positive3.

399
00:18:04,640 --> 00:18:08,250
So notice the only difference now is what line of code?

400
00:18:11,930 --> 00:18:13,260
Yeah, so 25.

401
00:18:13,260 --> 00:18:15,520
And we've not really seen this trick just yet.

402
00:18:15,520 --> 00:18:19,510
But we did see the exclamation point on Monday, which denotes what?

403
00:18:19,510 --> 00:18:20,970
So not, or negation.

404
00:18:20,970 --> 00:18:23,460
So take a Boolean value and flip its value.

405
00:18:23,460 --> 00:18:24,390
True becomes false.

406
00:18:24,390 --> 00:18:25,500
False becomes true.

407
00:18:25,500 --> 00:18:28,910
So this, I would propose, is even a little more intuitive of a way of

408
00:18:28,910 --> 00:18:32,200
writing the code because I still initialize thankful to false.

409
00:18:32,200 --> 00:18:33,530
I still do the following.

410
00:18:33,530 --> 00:18:35,700
I set thankful to true when the time comes.

411
00:18:35,700 --> 00:18:40,690
But now you can really just translate this code verbally left to right,

412
00:18:40,690 --> 00:18:42,550
while not thankful.

413
00:18:42,550 --> 00:18:46,170
Because bang, or exclamation point, denotes the notion of not, so while

414
00:18:46,170 --> 00:18:47,010
not thankful.

415
00:18:47,010 --> 00:18:49,740
>> So again, we haven't introduced any new concepts per se.

416
00:18:49,740 --> 00:18:53,230
We've talked about Booleans back when we played with Scratch.

417
00:18:53,230 --> 00:18:55,690
But realize now we can just start writing our code in

418
00:18:55,690 --> 00:18:56,550
many different ways.

419
00:18:56,550 --> 00:19:00,010
So especially in pset1, if you're sort of struggling to figure out the way to

420
00:19:00,010 --> 00:19:03,400
write some program, odds are you're in luck because there's going to be any

421
00:19:03,400 --> 00:19:05,780
number of solutions that you can happen upon.

422
00:19:05,780 --> 00:19:09,850
For instance, this is just three for even the simplest of programs.

423
00:19:09,850 --> 00:19:10,180
All right.

424
00:19:10,180 --> 00:19:13,860
And now recall on Monday, we left on this note with return values.

425
00:19:13,860 --> 00:19:18,280
So for the very first time, we wrote a program that doesn't just have main,

426
00:19:18,280 --> 00:19:22,240
it also has its own custom function that I wrote here.

427
00:19:22,240 --> 00:19:26,640
So in line 31 through 34, I've implemented a cube function.

428
00:19:26,640 --> 00:19:27,800
It's not complex.

429
00:19:27,800 --> 00:19:29,830
It's just a times a times a, in this case.

430
00:19:29,830 --> 00:19:34,920
But what's important about it is that I'm taking input in the form of a and

431
00:19:34,920 --> 00:19:38,910
I'm returning output in the form of a times a times a.

432
00:19:38,910 --> 00:19:43,940
>> So now I have the ability, much like I used to with printf alone, to call

433
00:19:43,940 --> 00:19:47,120
this function by calling the cube function.

434
00:19:47,120 --> 00:19:49,470
And the cube function takes some input.

435
00:19:49,470 --> 00:19:52,030
And the cube function returns some output.

436
00:19:52,030 --> 00:19:56,660
And so by contrast, printf just did something.

437
00:19:56,660 --> 00:19:59,490
It didn't return anything that we cared about--even though, as an

438
00:19:59,490 --> 00:20:00,820
aside, it does return a value.

439
00:20:00,820 --> 00:20:02,650
You just generally ignore it.

440
00:20:02,650 --> 00:20:04,000
Printf just did something.

441
00:20:04,000 --> 00:20:06,220
It had a side effect of printing to the screen.

442
00:20:06,220 --> 00:20:09,480
By contrast here, we have the cube function, which

443
00:20:09,480 --> 00:20:11,400
actually returns something.

444
00:20:11,400 --> 00:20:12,960
>> So this is generally--

445
00:20:12,960 --> 00:20:15,260
for those familiar with this, it's a fairly straightforward idea.

446
00:20:15,260 --> 00:20:18,460
But for those less familiar with this idea of passing in inputs and getting

447
00:20:18,460 --> 00:20:21,700
back outputs, let's try just something super simple.

448
00:20:21,700 --> 00:20:25,180
Is anyone comfortable coming up on stage briefly?

449
00:20:25,180 --> 00:20:27,460
You have to be comfortable with a camera on you, as well.

450
00:20:27,460 --> 00:20:27,640
Yeah.

451
00:20:27,640 --> 00:20:28,610
Okay, what's your name?

452
00:20:28,610 --> 00:20:29,020
KEN: Ken.

453
00:20:29,020 --> 00:20:29,420
DAVID J. MALAN: Ken.

454
00:20:29,420 --> 00:20:29,810
All right, Ken.

455
00:20:29,810 --> 00:20:31,060
Come on up.

456
00:20:31,060 --> 00:20:34,660
So Ken is going to be a function of sorts here.

457
00:20:34,660 --> 00:20:35,760
And let's go ahead and do this.

458
00:20:35,760 --> 00:20:38,790
Let's get a little fancy.

459
00:20:38,790 --> 00:20:39,770
Nice to meet you.

460
00:20:39,770 --> 00:20:41,010
Welcome to center stage.

461
00:20:41,010 --> 00:20:41,980
All right.

462
00:20:41,980 --> 00:20:45,590
Let's hit this button here.

463
00:20:45,590 --> 00:20:46,420
All right.

464
00:20:46,420 --> 00:20:49,490
So here you have a modern chalkboard.

465
00:20:49,490 --> 00:20:53,050
And what I am is the main function, for instance.

466
00:20:53,050 --> 00:20:55,990
And I don't have an iPad in my hand.

467
00:20:55,990 --> 00:20:59,000
I don't really remember how to--well, actually, can't say that.

468
00:20:59,000 --> 00:21:02,200
I don't really have good handwriting.

469
00:21:02,200 --> 00:21:05,260
And so therefore, I want you to print something on the screen for me.

470
00:21:05,260 --> 00:21:07,470
>> So I am being the main program.

471
00:21:07,470 --> 00:21:15,060
And I am going to have you say this by writing it in my chicken scratch and

472
00:21:15,060 --> 00:21:16,600
then passing you an input.

473
00:21:16,600 --> 00:21:20,000
So as silly though this exercise is, the notion of functions and calling a

474
00:21:20,000 --> 00:21:22,260
function and returning a function really boils down to this.

475
00:21:22,260 --> 00:21:23,120
I am main.

476
00:21:23,120 --> 00:21:26,270
I have just written printf("something") on the screen.

477
00:21:26,270 --> 00:21:27,470
I'm running this program.

478
00:21:27,470 --> 00:21:30,900
And as soon as printf gets called, it takes one argument--or one parameter,

479
00:21:30,900 --> 00:21:31,660
sometimes--

480
00:21:31,660 --> 00:21:32,780
between double quotes.

481
00:21:32,780 --> 00:21:33,960
Here is that argument.

482
00:21:33,960 --> 00:21:35,740
I'm passing it to Ken.

483
00:21:35,740 --> 00:21:39,390
Now he is a black box written some number of years ago that apparently

484
00:21:39,390 --> 00:21:41,070
only knows how to print things on the screen.

485
00:21:41,070 --> 00:21:42,320
>> So, execute.

486
00:21:48,842 --> 00:21:49,900
That's not bad.

487
00:21:49,900 --> 00:21:50,890
So, very good.

488
00:21:50,890 --> 00:21:52,900
So now Ken is done executing.

489
00:21:52,900 --> 00:21:55,810
Does he need to hand me anything back?

490
00:21:55,810 --> 00:21:57,240
So not that we've seen thus far.

491
00:21:57,240 --> 00:21:59,230
Again, printf does actually return a number.

492
00:21:59,230 --> 00:22:01,640
But we're going to ignore that for now because we've never used it.

493
00:22:01,640 --> 00:22:03,400
So that's it for Ken.

494
00:22:03,400 --> 00:22:06,650
And so now main comes back to execute--

495
00:22:06,650 --> 00:22:09,630
main takes over control of the program again because that line of code,

496
00:22:09,630 --> 00:22:11,010
printf, is done executing.

497
00:22:11,010 --> 00:22:13,890
And we go about our way executing whatever other lines are there.

498
00:22:13,890 --> 00:22:14,130
>> All right.

499
00:22:14,130 --> 00:22:17,080
So now let's try a slightly different example.

500
00:22:17,080 --> 00:22:22,430
And this time here, let's first clear the screen here.

501
00:22:22,430 --> 00:22:24,670
And this time, we'll do the cubing function.

502
00:22:24,670 --> 00:22:27,350
But this time, I expect an output value.

503
00:22:27,350 --> 00:22:28,630
So let's go ahead and do this.

504
00:22:28,630 --> 00:22:35,680
So now I have a line of code that says x = cube(x).

505
00:22:35,680 --> 00:22:36,930
So actually let's--

506
00:22:41,450 --> 00:22:43,940
the line of code, recall, looks like this.

507
00:22:43,940 --> 00:22:45,960
x = cube(x).

508
00:22:45,960 --> 00:22:48,100
So how is this going to work?

509
00:22:48,100 --> 00:22:50,820
So let's go ahead and give you a white screen again.

510
00:22:50,820 --> 00:22:55,000
And I am going to write now down the value of x, which at this moment in

511
00:22:55,000 --> 00:23:01,080
time happens to be, let's say, 2, to keep it simple.

512
00:23:01,080 --> 00:23:04,890
So I have written down on a piece of paper the value of 2,

513
00:23:04,890 --> 00:23:06,100
which is my value x.

514
00:23:06,100 --> 00:23:08,250
I hand it to Ken.

515
00:23:08,250 --> 00:23:09,200
KEN: And I just write the answer?

516
00:23:09,200 --> 00:23:12,660
DAVID J. MALAN: Yeah, let's just write the answer.

517
00:23:12,660 --> 00:23:13,030
Okay.

518
00:23:13,030 --> 00:23:16,280
And now he has to return me something.

519
00:23:16,280 --> 00:23:17,560
So--

520
00:23:17,560 --> 00:23:18,170
perfect.

521
00:23:18,170 --> 00:23:18,840
Nice segue.

522
00:23:18,840 --> 00:23:21,970
>> So now he hands me back the value of 8, in this case.

523
00:23:21,970 --> 00:23:23,220
And what do I do with it?

524
00:23:23,220 --> 00:23:26,130
Well, actually, let's see.

525
00:23:26,130 --> 00:23:26,640
Get this right.

526
00:23:26,640 --> 00:23:27,880
What am I going to do with it?

527
00:23:27,880 --> 00:23:31,900
Now I'm going to take this value and actually store it in those

528
00:23:31,900 --> 00:23:33,400
same bits in memory.

529
00:23:33,400 --> 00:23:35,030
But notice, I'm kind of struggling here.

530
00:23:35,030 --> 00:23:38,280
I'm a little confused because where do I actually write the value of x?

531
00:23:38,280 --> 00:23:41,840
Because what I've just done is physically hand Ken a piece of paper

532
00:23:41,840 --> 00:23:44,400
that had the value 2, which was x.

533
00:23:44,400 --> 00:23:46,300
And indeed, that's precisely what happens.

534
00:23:46,300 --> 00:23:50,100
So it turns out that when you call a function, and you pass in an argument

535
00:23:50,100 --> 00:23:54,130
like "hello world" or you pass in an argument like 2, generally, you're

536
00:23:54,130 --> 00:23:56,720
passing in a copy of that argument.

537
00:23:56,720 --> 00:24:01,020
And so just as I wrote down the number 2 here and handed it to Ken; that must

538
00:24:01,020 --> 00:24:04,760
mean that I still have a copy of the value 2 somewhere.

539
00:24:04,760 --> 00:24:08,140
Because indeed, now that I've gotten back the value 8, I need to go back in

540
00:24:08,140 --> 00:24:12,010
RAM and actually write down 8 where I once had the number 2.

541
00:24:12,010 --> 00:24:15,720
>> So visually remember this notion of passing in literally

542
00:24:15,720 --> 00:24:16,730
a copy of the value.

543
00:24:16,730 --> 00:24:19,570
Ken does his thing, hands me back something--in this case,

544
00:24:19,570 --> 00:24:20,820
a value like 8.

545
00:24:20,820 --> 00:24:22,660
And then I have to do something with that value if I

546
00:24:22,660 --> 00:24:24,880
want to keep it around.

547
00:24:24,880 --> 00:24:29,470
So all of this will be all too familiar before long.

548
00:24:29,470 --> 00:24:33,082
Thank you so much for this demo here, Ken.

549
00:24:33,082 --> 00:24:34,820
All right.

550
00:24:34,820 --> 00:24:36,720
Very well done.

551
00:24:36,720 --> 00:24:40,610
So let's see how that ultimately relates to some of the function

552
00:24:40,610 --> 00:24:42,270
calling that we've been doing here.

553
00:24:42,270 --> 00:24:47,610
So let me go ahead and bring us back to the cubing example here.

554
00:24:47,610 --> 00:24:53,080
And notice that if we want to actually start taking this further, we're going

555
00:24:53,080 --> 00:24:57,050
to have to be mindful of the fact that the number x that's being passed in

556
00:24:57,050 --> 00:25:01,390
here is different from what's actually being passed into the function.

557
00:25:01,390 --> 00:25:03,940
So again, this passed by copy is going to become quite

558
00:25:03,940 --> 00:25:05,620
germane in just a moment.

559
00:25:05,620 --> 00:25:09,320
>> So let's take a look at something that doesn't quite work right yet.

560
00:25:09,320 --> 00:25:11,790
I'm going to go ahead and open a third buggy example, which

561
00:25:11,790 --> 00:25:13,560
is flawed by nature.

562
00:25:13,560 --> 00:25:18,070
And it's called buggy3, and it implements a swapping function.

563
00:25:18,070 --> 00:25:23,500
So here we have a main function that has x and y arbitrarily initialized to

564
00:25:23,500 --> 00:25:24,720
1 and 2, respectively.

565
00:25:24,720 --> 00:25:27,590
We could use GetInt, but we just need a simple exercise.

566
00:25:27,590 --> 00:25:29,680
So it's hard-coded as 1 and 2.

567
00:25:29,680 --> 00:25:35,330
In lines 21 and 22, we apparently print out x and y, one per line.

568
00:25:35,330 --> 00:25:39,620
Then, on line 23, I claim I am swapping these values, dot, dot, dot.

569
00:25:39,620 --> 00:25:43,030
I apparently call a function in line 24 called swap

570
00:25:43,030 --> 00:25:44,000
that takes two arguments.

571
00:25:44,000 --> 00:25:46,430
It's totally legit for functions to take two arguments.

572
00:25:46,430 --> 00:25:48,220
We've seen printf do it already.

573
00:25:48,220 --> 00:25:50,370
So swap apparently takes x and y.

574
00:25:50,370 --> 00:25:53,010
And as its name suggests, I would hope that it's going to

575
00:25:53,010 --> 00:25:54,320
swap these two values.

576
00:25:54,320 --> 00:25:57,560
So then I claim on line 25, swapped.

577
00:25:57,560 --> 00:26:01,570
And I reprint x and y under the assumption that

578
00:26:01,570 --> 00:26:02,830
they've indeed been swapped.

579
00:26:02,830 --> 00:26:04,370
But if I actually run this program--

580
00:26:04,370 --> 00:26:06,060
let me open up a terminal window.

581
00:26:06,060 --> 00:26:07,750
Let me make buggy3.

582
00:26:07,750 --> 00:26:09,970
As the name suggests, this is not going to end well.

583
00:26:09,970 --> 00:26:14,690
Because when I hit Enter, notice that x is 1.

584
00:26:14,690 --> 00:26:15,720
y is 2.

585
00:26:15,720 --> 00:26:19,160
And yet at the end of the program, they're still, in fact, the same.

586
00:26:19,160 --> 00:26:22,760
>> So based on the demonstration just now with Ken, what's actually going on?

587
00:26:22,760 --> 00:26:24,660
Well, let's dive into this swap function.

588
00:26:24,660 --> 00:26:25,800
It's super short.

589
00:26:25,800 --> 00:26:28,020
It's only a few lines of code long.

590
00:26:28,020 --> 00:26:32,810
But what's the fundamental problem based on the simple story told

591
00:26:32,810 --> 00:26:34,270
up here with Ken?

592
00:26:34,270 --> 00:26:36,115
Why is swap broken?

593
00:26:36,115 --> 00:26:37,365
[INAUDIBLE]

594
00:26:39,840 --> 00:26:40,460
Exactly.

595
00:26:40,460 --> 00:26:43,610
So we're storing to a copy, not the variable itself.

596
00:26:43,610 --> 00:26:46,810
In other words, swap apparently takes two arguments, an int.

597
00:26:46,810 --> 00:26:49,370
And it's arbitrarily called a and b.

598
00:26:49,370 --> 00:26:54,430
And up here, I've passed in x and y, which are respectively 1 and 2.

599
00:26:54,430 --> 00:26:56,580
But I'm not literally passing in x.

600
00:26:56,580 --> 00:26:58,410
I'm not literally passing in y.

601
00:26:58,410 --> 00:27:01,230
I'm passing a copy of x and a copy of y.

602
00:27:01,230 --> 00:27:05,180
It's like almost as though you copied and pasted into swap the values that

603
00:27:05,180 --> 00:27:07,440
you want it to actually manipulate.

604
00:27:07,440 --> 00:27:11,970
So if that's the case, when I, the program, start executing

605
00:27:11,970 --> 00:27:14,140
line 35, then 36--

606
00:27:14,140 --> 00:27:17,740
when I get to line 37, at this point in the story, what is the value of a?

607
00:27:20,740 --> 00:27:24,850
At this point in the story, line 37, what is the value of a at this point?

608
00:27:24,850 --> 00:27:25,980
So it should just be 1.

609
00:27:25,980 --> 00:27:26,170
Right?

610
00:27:26,170 --> 00:27:29,100
Because x was passed in as the first argument.

611
00:27:29,100 --> 00:27:33,150
And this function just arbitrarily is calling its first argument, a.

612
00:27:33,150 --> 00:27:35,130
Similarly is y, the second argument.

613
00:27:35,130 --> 00:27:37,930
And it's just arbitrarily calling the second argument b.

614
00:27:37,930 --> 00:27:40,510
>> Now this dichotomy is actually fairly simply explained.

615
00:27:40,510 --> 00:27:40,880
Think about it.

616
00:27:40,880 --> 00:27:42,980
None of us have met the person who wrote printf.

617
00:27:42,980 --> 00:27:49,880
So surely, he or she has no idea what our variables 30 years later are going

618
00:27:49,880 --> 00:27:50,710
to be called.

619
00:27:50,710 --> 00:27:55,110
So there has to be a distinction between what you call variables in

620
00:27:55,110 --> 00:27:59,960
functions you're writing and what you call variables in functions you're

621
00:27:59,960 --> 00:28:01,770
calling or using.

622
00:28:01,770 --> 00:28:05,120
So in other words, I have written my variables as x and y.

623
00:28:05,120 --> 00:28:08,060
But if someone else had written the swap function, he or she certainly

624
00:28:08,060 --> 00:28:10,480
wouldn't know what my variables are going to be called.

625
00:28:10,480 --> 00:28:13,850
So realize that this is why you have this duality of names.

626
00:28:13,850 --> 00:28:16,800
Technically, I could do this by coincidence.

627
00:28:16,800 --> 00:28:19,750
But they would still be passed in as copies.

628
00:28:19,750 --> 00:28:22,940
It would just be a pure coincidence aesthetically if that person who wrote

629
00:28:22,940 --> 00:28:25,590
swap had used the same names.

630
00:28:25,590 --> 00:28:25,930
>> All right.

631
00:28:25,930 --> 00:28:29,010
So at this point in the story, line 37, a is 1.

632
00:28:29,010 --> 00:28:30,410
b is 2.

633
00:28:30,410 --> 00:28:32,040
And now I proceed to swap them.

634
00:28:32,040 --> 00:28:34,730
Well first of all, let me actually do this much more simply.

635
00:28:34,730 --> 00:28:36,500
I don't know what those three lines of code were doing.

636
00:28:36,500 --> 00:28:37,370
Let me just do this.

637
00:28:37,370 --> 00:28:38,850
b gets a.

638
00:28:38,850 --> 00:28:40,170
a gets b.

639
00:28:40,170 --> 00:28:41,450
Done.

640
00:28:41,450 --> 00:28:43,540
Why is this broken, logically?

641
00:28:46,980 --> 00:28:48,590
It's kind of the intuitive thing, right?

642
00:28:48,590 --> 00:28:50,640
So a becomes b.

643
00:28:50,640 --> 00:28:52,450
And b becomes a.

644
00:28:52,450 --> 00:28:55,410
But the problem is that as soon as line 37 executes, what's the

645
00:28:55,410 --> 00:28:58,170
value of a and b?

646
00:28:58,170 --> 00:28:59,070
The same, 1.

647
00:28:59,070 --> 00:29:03,460
Because you have clobbered, so to speak, you've changed b to equal a.

648
00:29:03,460 --> 00:29:06,000
So once line 37 is executed, that's great.

649
00:29:06,000 --> 00:29:09,940
You now have two copies of the number 1 inside of this function.

650
00:29:09,940 --> 00:29:14,720
So then when you say in line 38, a gets b, well, you're kind of screwed.

651
00:29:14,720 --> 00:29:17,370
Because you're just assigning 1 to 1.

652
00:29:17,370 --> 00:29:20,400
You've kind of lost the value you cared about.

653
00:29:20,400 --> 00:29:22,910
>> So in the original version of this, notice what I did.

654
00:29:22,910 --> 00:29:26,620
I instead had a third line of code that looked like this.

655
00:29:26,620 --> 00:29:29,910
I declare a temporary variable--tmp is a very common name

656
00:29:29,910 --> 00:29:31,240
for a temporary variable.

657
00:29:31,240 --> 00:29:34,280
It's an int because it has to match what I want to make a copy of.

658
00:29:34,280 --> 00:29:39,720
I store a copy of a inside of tmp. So once line 37 has executed,

659
00:29:39,720 --> 00:29:41,390
the value of a is--

660
00:29:41,390 --> 00:29:42,970
quick sanity check--

661
00:29:42,970 --> 00:29:43,460
1.

662
00:29:43,460 --> 00:29:45,780
The value of b is 2.

663
00:29:45,780 --> 00:29:48,470
And the value of tmp is also 1.

664
00:29:48,470 --> 00:29:51,470
So now I execute line 38.

665
00:29:51,470 --> 00:29:57,180
So once line 38 executes, a takes on the value of b.

666
00:29:57,180 --> 00:29:58,510
And b was 2.

667
00:29:58,510 --> 00:30:00,500
So a is now 2.

668
00:30:00,500 --> 00:30:03,110
So at this point in the story, a is 2, b is 2,

669
00:30:03,110 --> 00:30:05,130
and tmp is 1.

670
00:30:05,130 --> 00:30:09,330
So now logically, we can just plop tmp's value into b.

671
00:30:09,330 --> 00:30:10,690
And we're done.

672
00:30:10,690 --> 00:30:12,170
>> So we've solved that problem.

673
00:30:12,170 --> 00:30:16,040
Unfortunately, when I run this program in this form, it doesn't actually swap

674
00:30:16,040 --> 00:30:17,700
any values.

675
00:30:17,700 --> 00:30:18,950
But to be clear, why?

676
00:30:23,420 --> 00:30:26,310
I fixed the logical problem from just a moment ago.

677
00:30:26,310 --> 00:30:31,150
But again, if I run this program, x and y remain unchanged by the end of

678
00:30:31,150 --> 00:30:33,834
the program's execution.

679
00:30:33,834 --> 00:30:34,760
[INAUDIBLE]

680
00:30:34,760 --> 00:30:36,030
DAVID J. MALAN: So we haven't returned anything.

681
00:30:36,030 --> 00:30:36,960
So that's true.

682
00:30:36,960 --> 00:30:39,880
But it turns out there's a bit of a problem here because thus far, the

683
00:30:39,880 --> 00:30:42,460
only thing we've been able to return is one thing.

684
00:30:42,460 --> 00:30:46,540
And this is a restriction of C. You can only return really one value,

685
00:30:46,540 --> 00:30:48,970
in which case, I'm kind of stuck here

686
00:30:48,970 --> 00:30:51,805
because I could return the new value of x or I could return the

687
00:30:51,805 --> 00:30:53,160
new value of y.

688
00:30:53,160 --> 00:30:54,330
But I want both back.

689
00:30:54,330 --> 00:30:58,010
So returning is not the simple solution here.

690
00:30:58,010 --> 00:30:59,770
But the problem fundamentally is why?

691
00:30:59,770 --> 00:31:03,270
What have we actually swapped?

692
00:31:03,270 --> 00:31:04,010
a and b.

693
00:31:04,010 --> 00:31:07,670
But a and b are copies of x and y, which means we just did all of this

694
00:31:07,670 --> 00:31:10,080
work--we just spent like three minutes talking about the swap

695
00:31:10,080 --> 00:31:11,680
function and all three of these variables.

696
00:31:11,680 --> 00:31:15,090
And that's great, perfectly correct in isolation.

697
00:31:15,090 --> 00:31:20,230
But a and b's scope only is in these lines here.

698
00:31:20,230 --> 00:31:24,130
So just like a for loop, if you declare an integer i inside the for

699
00:31:24,130 --> 00:31:27,400
loop--similarly, if you're declaring a and b inside of a function that

700
00:31:27,400 --> 00:31:30,550
you've written, they're only valid inside of that function.

701
00:31:30,550 --> 00:31:35,020
Which means as soon as swap is done executing and we go from line 24 to

702
00:31:35,020 --> 00:31:38,380
line 25, x and y haven't been changed at all.

703
00:31:38,380 --> 00:31:42,580
You just wasted a whole lot of time swapping copies of variables.

704
00:31:42,580 --> 00:31:46,490
>> So it turns out that the solution to this is actually non-obvious.

705
00:31:46,490 --> 00:31:49,210
It's not quite sufficient to return values because we can

706
00:31:49,210 --> 00:31:50,320
only return one value.

707
00:31:50,320 --> 00:31:53,370
And I really do want to swap both x and y at the same time.

708
00:31:53,370 --> 00:31:55,020
So we're going to come back to this.

709
00:31:55,020 --> 00:31:58,770
But for now, realize that the issue fundamentally derives from the fact

710
00:31:58,770 --> 00:32:00,660
that a and b are copies.

711
00:32:00,660 --> 00:32:03,450
And they are in their own scope.

712
00:32:03,450 --> 00:32:04,980
Well, let's try to solve this in some way.

713
00:32:04,980 --> 00:32:09,200
Let me actually scroll back here and open up, let's say, a fourth variant

714
00:32:09,200 --> 00:32:11,170
of this, buggy4.

715
00:32:11,170 --> 00:32:13,230
And what about this?

716
00:32:13,230 --> 00:32:16,690
This is a similar but simpler problem to look at before we take a stab at

717
00:32:16,690 --> 00:32:17,530
solving it.

718
00:32:17,530 --> 00:32:19,440
This program is called increment.

719
00:32:19,440 --> 00:32:24,320
And it apparently initializes an x integer to 1 in line 18.

720
00:32:24,320 --> 00:32:25,950
I then claim x is 1.

721
00:32:25,950 --> 00:32:28,020
I then claim incrementing, dot, dot, dot.

722
00:32:28,020 --> 00:32:29,460
I then call increment.

723
00:32:29,460 --> 00:32:33,480
But then in lines 22 and 23, I claim it's been incremented.

724
00:32:33,480 --> 00:32:37,780
I claim x is now whatever it is, 2 presumably.

725
00:32:37,780 --> 00:32:39,770
>> But this program is buggy.

726
00:32:39,770 --> 00:32:41,020
What's the problem?

727
00:32:43,450 --> 00:32:44,418
Yeah?

728
00:32:44,418 --> 00:32:45,668
[INAUDIBLE]

729
00:32:49,260 --> 00:32:49,850
DAVID J. MALAN: Exactly.

730
00:32:49,850 --> 00:32:52,430
So x has been declared obviously on line 18.

731
00:32:52,430 --> 00:32:54,410
That is inside main's curly braces.

732
00:32:54,410 --> 00:32:58,470
So the simple answer here is that, well, x exists here.

733
00:32:58,470 --> 00:33:01,510
It does not exist in line 32.

734
00:33:01,510 --> 00:33:03,710
So this program actually won't even compile.

735
00:33:03,710 --> 00:33:07,910
The compiler, when I try compiling this code, is going to yell at me

736
00:33:07,910 --> 00:33:13,190
about some undeclared identifier or something to that effect.

737
00:33:13,190 --> 00:33:13,870
In fact, let's try.

738
00:33:13,870 --> 00:33:15,235
This is make buggy4.

739
00:33:17,780 --> 00:33:18,190
There it is.

740
00:33:18,190 --> 00:33:22,030
Use of undeclared identifier x in line 32.

741
00:33:22,030 --> 00:33:25,700
And actually, let's be more explicit here today so that this is useful in

742
00:33:25,700 --> 00:33:27,140
office hours and at home.

743
00:33:27,140 --> 00:33:29,000
Notice that it's a little cryptically written.

744
00:33:29,000 --> 00:33:31,560
But the fact that Clang has yelled at us, saying

745
00:33:31,560 --> 00:33:36,970
buggy4.c:32:5, is actually useful.

746
00:33:36,970 --> 00:33:41,970
It means that the error is on line 32 at character position five.

747
00:33:41,970 --> 00:33:44,670
So one, two, three, four, five.

748
00:33:44,670 --> 00:33:46,640
That's, in fact, where the problem is.

749
00:33:46,640 --> 00:33:49,710
And also to keep in mind at office hours and at home, I'm lucky here.

750
00:33:49,710 --> 00:33:50,740
I have one mistake.

751
00:33:50,740 --> 00:33:52,660
It's going to be relatively easy to fix.

752
00:33:52,660 --> 00:33:56,220
But if you get a whole screen full of overwhelming error messages, again,

753
00:33:56,220 --> 00:33:59,240
realize that the bottommost one might just be symptomatic of

754
00:33:59,240 --> 00:34:00,320
the topmost ones.

755
00:34:00,320 --> 00:34:03,560
So always chase down your bugs from top down.

756
00:34:03,560 --> 00:34:06,720
Because there might just be a daisy-chain effect that is suggesting you

757
00:34:06,720 --> 00:34:09,030
have way more problems than you actually do.

758
00:34:09,030 --> 00:34:14,989
>> So how could we fix this if my goal is to increment x?

759
00:34:14,989 --> 00:34:15,370
What's that?

760
00:34:15,370 --> 00:34:15,620
Okay.

761
00:34:15,620 --> 00:34:16,679
So we can make x global.

762
00:34:16,679 --> 00:34:18,860
Let's take the shortcut that I warned about earlier.

763
00:34:18,860 --> 00:34:20,550
But heck, we just need a quick fix.

764
00:34:20,550 --> 00:34:23,949
So let's just say int x up here.

765
00:34:23,949 --> 00:34:25,600
That makes x global.

766
00:34:25,600 --> 00:34:28,460
So now main has access to it.

767
00:34:28,460 --> 00:34:31,780
And increment has access to it.

768
00:34:31,780 --> 00:34:33,860
And so let me go ahead and compile this now.

769
00:34:33,860 --> 00:34:36,330
Make buggy4, Enter.

770
00:34:36,330 --> 00:34:37,440
Seems to compile now.

771
00:34:37,440 --> 00:34:40,949
Let's run buggy4, and it seems to actually work.

772
00:34:40,949 --> 00:34:42,780
Now this is one of these things--

773
00:34:42,780 --> 00:34:45,870
do as I say, not as I do, as I've just done here.

774
00:34:45,870 --> 00:34:49,239
Because in general, our programs are going to get much more interesting and

775
00:34:49,239 --> 00:34:50,440
much longer than this.

776
00:34:50,440 --> 00:34:53,199
And if your solution to life's problems is just ah, put all the

777
00:34:53,199 --> 00:34:57,550
variables at the top of your file, very quickly do programs get

778
00:34:57,550 --> 00:34:59,700
horrifically difficult to manage.

779
00:34:59,700 --> 00:35:02,050
It gets harder to think up new variable names.

780
00:35:02,050 --> 00:35:05,240
It gets harder to understand what variable is doing what.

781
00:35:05,240 --> 00:35:08,250
>> And so in general, this is not a good solution.

782
00:35:08,250 --> 00:35:09,780
So let's do this better.

783
00:35:09,780 --> 00:35:11,920
We don't want to use a global variable here.

784
00:35:11,920 --> 00:35:14,050
I do want to increment x.

785
00:35:14,050 --> 00:35:16,050
So I could obviously--

786
00:35:16,050 --> 00:35:18,450
at the end of the day, it's kind of a silly story because we just do this.

787
00:35:18,450 --> 00:35:22,050
But if I didn't know about that operator, or I wasn't allowed to

788
00:35:22,050 --> 00:35:27,700
change it in main itself, how else could I implement Ken over here, this

789
00:35:27,700 --> 00:35:31,450
time not to cube but to increment?

790
00:35:31,450 --> 00:35:32,700
How do I change this thing here?

791
00:35:32,700 --> 00:35:33,025
Yeah.

792
00:35:33,025 --> 00:35:34,275
[INAUDIBLE]

793
00:35:37,430 --> 00:35:38,000
DAVID J. MALAN: Okay, good.

794
00:35:38,000 --> 00:35:40,490
So why don't I pass in x?

795
00:35:40,490 --> 00:35:44,390
And then rather than return it, why don't I just do return x + 1?

796
00:35:44,390 --> 00:35:46,370
Now, a couple more things have to change here.

797
00:35:46,370 --> 00:35:47,530
I'm on the right track.

798
00:35:47,530 --> 00:35:48,910
What else do I need to tweak?

799
00:35:48,910 --> 00:35:49,470
Someone else.

800
00:35:49,470 --> 00:35:49,882
Yeah?

801
00:35:49,882 --> 00:35:51,530
[INAUDIBLE]

802
00:35:51,530 --> 00:35:53,520
DAVID J. MALAN: I need to change the return type of increment

803
00:35:53,520 --> 00:35:54,590
because it's not void.

804
00:35:54,590 --> 00:35:56,650
Void means nothing's being returned.

805
00:35:56,650 --> 00:35:57,600
But clearly, now it is.

806
00:35:57,600 --> 00:36:01,280
So this needs to change to int to be consistent with whatever

807
00:36:01,280 --> 00:36:02,580
I'm actually returning.

808
00:36:02,580 --> 00:36:04,580
>> Now something else is still buggy here.

809
00:36:04,580 --> 00:36:04,982
Yeah?

810
00:36:04,982 --> 00:36:06,590
[INAUDIBLE]

811
00:36:06,590 --> 00:36:07,630
DAVID J. MALAN: So I need to increment x?

812
00:36:07,630 --> 00:36:10,336
[INAUDIBLE]

813
00:36:10,336 --> 00:36:11,880
DAVID J. MALAN: Ah, so I need to pass x.

814
00:36:11,880 --> 00:36:13,300
So I need to do this here.

815
00:36:17,590 --> 00:36:19,690
So the prototype, I have to change this up here.

816
00:36:19,690 --> 00:36:21,290
So this has to become an int.

817
00:36:21,290 --> 00:36:22,820
This has to become--

818
00:36:22,820 --> 00:36:23,670
hmm.

819
00:36:23,670 --> 00:36:24,710
I actually have a bug down here.

820
00:36:24,710 --> 00:36:25,780
Let's fix this one first.

821
00:36:25,780 --> 00:36:27,990
What should this actually be?

822
00:36:27,990 --> 00:36:29,330
So it's got to be an int something.

823
00:36:29,330 --> 00:36:30,340
It could be x.

824
00:36:30,340 --> 00:36:33,120
But frankly, if you start calling all of your variables x, it's going to get

825
00:36:33,120 --> 00:36:35,250
less and less clear which is which.

826
00:36:35,250 --> 00:36:38,210
So let's just arbitrarily choose a different naming convention for my

827
00:36:38,210 --> 00:36:40,220
helper functions, the functions I'm writing.

828
00:36:40,220 --> 00:36:41,100
We'll call it a.

829
00:36:41,100 --> 00:36:44,500
Or we could call it--let's call it even_number to be even more explicit.

830
00:36:44,500 --> 00:36:47,610
So then I have to return whatever the number is plus 1.

831
00:36:47,610 --> 00:36:49,720
And now I have to change one other thing up here and one

832
00:36:49,720 --> 00:36:50,700
other thing up here.

833
00:36:50,700 --> 00:36:54,150
What do I have to change on line 21 first?

834
00:36:54,150 --> 00:36:55,390
I have to assign it to x.

835
00:36:55,390 --> 00:36:57,480
So I can't just call increment x.

836
00:36:57,480 --> 00:37:01,000
I need to remember the answer by changing the value of x on

837
00:37:01,000 --> 00:37:02,020
the left hand side.

838
00:37:02,020 --> 00:37:04,930
And even though x is now on the left and right, that's totally fine because

839
00:37:04,930 --> 00:37:08,370
the right hand side gets executed first then gets plopped into the left

840
00:37:08,370 --> 00:37:10,240
hand thing, x in this case.

841
00:37:10,240 --> 00:37:11,900
And then lastly, this is an easy fix now.

842
00:37:11,900 --> 00:37:15,080
This should just match what's down below.

843
00:37:15,080 --> 00:37:17,120
Int number.

844
00:37:17,120 --> 00:37:17,320
>> All right.

845
00:37:17,320 --> 00:37:20,290
So a whole bunch of changes for a really stupid function.

846
00:37:20,290 --> 00:37:24,250
But representative of things that we'll increasingly want to do.

847
00:37:24,250 --> 00:37:25,490
So make buggy4.

848
00:37:25,490 --> 00:37:26,485
I've screwed up somewhere.

849
00:37:26,485 --> 00:37:27,520
Oh my God.

850
00:37:27,520 --> 00:37:29,660
Five mistakes in, like, a six-line program.

851
00:37:29,660 --> 00:37:36,500
So what's wrong on line 18, character 5?

852
00:37:36,500 --> 00:37:36,970
All right.

853
00:37:36,970 --> 00:37:39,330
So I have to declare this int.

854
00:37:39,330 --> 00:37:39,630
All right.

855
00:37:39,630 --> 00:37:41,790
So let's see, a whole bunch of other errors.

856
00:37:41,790 --> 00:37:42,230
Oh my god.

857
00:37:42,230 --> 00:37:43,880
19, 18, 21.

858
00:37:43,880 --> 00:37:46,020
But again, let's just clear the screen--

859
00:37:46,020 --> 00:37:48,660
Control L here-- and re-run Clang.

860
00:37:48,660 --> 00:37:51,340
So five problems is actually just that one.

861
00:37:51,340 --> 00:37:53,500
So now let's run buggy4, Enter.

862
00:37:53,500 --> 00:37:54,150
Whew.

863
00:37:54,150 --> 00:37:57,434
x has been incremented correctly.

864
00:37:57,434 --> 00:37:58,420
>> All right.

865
00:37:58,420 --> 00:38:01,700
Any questions on how to increment numbers?

866
00:38:01,700 --> 00:38:02,896
Yeah?

867
00:38:02,896 --> 00:38:06,864
SPEAKER 2: Why is it that you can just change x to number in the variable

868
00:38:06,864 --> 00:38:08,860
name and it'll know what you mean?

869
00:38:08,860 --> 00:38:09,600
DAVID J. MALAN: Good question.

870
00:38:09,600 --> 00:38:13,130
How is it that I can just change x to number and the program will know

871
00:38:13,130 --> 00:38:13,990
immediately?

872
00:38:13,990 --> 00:38:16,120
So again, think of it as this abstraction.

873
00:38:16,120 --> 00:38:20,110
So if I am main and Ken is incremental, frankly, I don't care

874
00:38:20,110 --> 00:38:21,540
what Ken calls his iPad.

875
00:38:21,540 --> 00:38:25,350
I don't care what he calls anything that has to do with his implementation

876
00:38:25,350 --> 00:38:26,550
of this functionality.

877
00:38:26,550 --> 00:38:32,130
So this is an implementation detail that I, main, don't

878
00:38:32,130 --> 00:38:33,010
have to care about.

879
00:38:33,010 --> 00:38:37,440
And so simply changing it consistently inside of the function, number here

880
00:38:37,440 --> 00:38:41,340
and number here, is all it takes so long as I recompile.

881
00:38:41,340 --> 00:38:43,820
It's sort of like if you think about--many of us, those of you with driver's

882
00:38:43,820 --> 00:38:46,590
licenses who've driven, or if you've even driven in a car--

883
00:38:46,590 --> 00:38:50,710
most of us have no idea how a car works underneath the hood.

884
00:38:50,710 --> 00:38:54,710
And literally, if you open up the hood, most of us--myself included--

885
00:38:54,710 --> 00:38:56,580
aren't going to really know what we're looking at.

886
00:38:56,580 --> 00:38:58,850
Kind of like you might feel with stuff like this right now.

887
00:38:58,850 --> 00:39:01,380
But we don't really have to care how the car works.

888
00:39:01,380 --> 00:39:05,000
We don't have to care what all of the rods and pistons and cables inside of

889
00:39:05,000 --> 00:39:07,700
the car are actually doing.

890
00:39:07,700 --> 00:39:11,360
>> So something like what you call the piston doesn't matter

891
00:39:11,360 --> 00:39:11,920
here in this case.

892
00:39:11,920 --> 00:39:12,490
Same idea.

893
00:39:12,490 --> 00:39:12,670
Yeah?

894
00:39:12,670 --> 00:39:13,920
[INAUDIBLE]

895
00:39:25,250 --> 00:39:29,530
DAVID J. MALAN: If there were more uses of the variable x a moment ago,

896
00:39:29,530 --> 00:39:32,220
you, the programmer, would have to change them everywhere.

897
00:39:32,220 --> 00:39:35,230
Or you could literally do File, Menu, and then Find/Replace,

898
00:39:35,230 --> 00:39:36,270
something like that.

899
00:39:36,270 --> 00:39:40,110
But you are going to have to make those changes yourself.

900
00:39:40,110 --> 00:39:41,200
You have to be consistent.

901
00:39:41,200 --> 00:39:42,450
[INAUDIBLE]

902
00:39:47,200 --> 00:39:48,960
DAVID J. MALAN: A particular order like here?

903
00:39:48,960 --> 00:39:52,660
If this was int another number?

904
00:39:52,660 --> 00:39:52,940
Yeah.

905
00:39:52,940 --> 00:39:56,430
So order matters when you are calling the function.

906
00:39:56,430 --> 00:40:00,350
So if I were calling increment here with something comma something,

907
00:40:00,350 --> 00:40:01,400
there's a direct mapping.

908
00:40:01,400 --> 00:40:04,490
The first variable, whatever it's called, is made a copy of the first

909
00:40:04,490 --> 00:40:05,480
argument over here.

910
00:40:05,480 --> 00:40:07,280
Sorry, this should not be a parenthesis.

911
00:40:07,280 --> 00:40:09,300
The second argument lines up with the second one.

912
00:40:09,300 --> 00:40:11,220
>> So order, yes, matters.

913
00:40:11,220 --> 00:40:11,490
All right.

914
00:40:11,490 --> 00:40:13,360
Sorry I took a long way to get there.

915
00:40:13,360 --> 00:40:14,610
Other questions?

916
00:40:16,460 --> 00:40:16,850
All right.

917
00:40:16,850 --> 00:40:20,300
So let's see if we can't paint a picture of what's actually going on

918
00:40:20,300 --> 00:40:22,160
here underneath the hood, so to speak.

919
00:40:22,160 --> 00:40:26,310
So this is a rectangle that might represent your computer's memory.

920
00:40:26,310 --> 00:40:31,240
So even if you have no idea how memory works or how RAM works, at least

921
00:40:31,240 --> 00:40:33,590
assume that you have bunches of it these days.

922
00:40:33,590 --> 00:40:34,740
You've got megabytes of it.

923
00:40:34,740 --> 00:40:35,760
You've got gigabytes of it.

924
00:40:35,760 --> 00:40:40,690
And we know from week zero that a byte is just what?

925
00:40:40,690 --> 00:40:41,280
8 bits.

926
00:40:41,280 --> 00:40:42,730
Right, so 8 zeroes and ones.

927
00:40:42,730 --> 00:40:46,300
So if your computer has a gig of RAM, two gigs of RAM these days, you have a

928
00:40:46,300 --> 00:40:54,450
billion or 2 billion bytes of memory, or roughly 8 billion or 16 billion

929
00:40:54,450 --> 00:40:56,560
bits, inside of your computer.

930
00:40:56,560 --> 00:40:59,710
Now unlike the little Woolly Willy example, it's not magnetic particles

931
00:40:59,710 --> 00:41:00,560
typically anymore.

932
00:41:00,560 --> 00:41:04,470
Increasingly, in laptops at least, it's solid state drives, SSDs, that

933
00:41:04,470 --> 00:41:05,560
just have no moving parts.

934
00:41:05,560 --> 00:41:06,710
It's all electronic.

935
00:41:06,710 --> 00:41:08,070
It's all electricity based.

936
00:41:08,070 --> 00:41:12,360
So think, though, of this rectangle as just representing the one or two

937
00:41:12,360 --> 00:41:13,930
gigabytes of memory that you have.

938
00:41:13,930 --> 00:41:15,500
>> So it's a chunk of memory.

939
00:41:15,500 --> 00:41:20,460
Now the world of computer science has sort of partitioned off chunks of

940
00:41:20,460 --> 00:41:22,570
memory to do different things.

941
00:41:22,570 --> 00:41:25,930
So for instance, if this is your computer's RAM--as suggested by the

942
00:41:25,930 --> 00:41:30,400
rectangle there--turns out that by convention, at the top of your RAM, so

943
00:41:30,400 --> 00:41:33,170
to speak, is generally what's called a text segment.

944
00:41:33,170 --> 00:41:35,910
Those are the zeroes and ones that you have compiled.

945
00:41:35,910 --> 00:41:39,040
So when we've looked underneath the hood at what a.out is, all

946
00:41:39,040 --> 00:41:40,360
the zeroes and ones--

947
00:41:40,360 --> 00:41:44,000
when you run a program, those zeroes and ones are loaded from your hard

948
00:41:44,000 --> 00:41:46,290
drive into something called RAM.

949
00:41:46,290 --> 00:41:48,950
And in the RAM, they're put at the top.

950
00:41:48,950 --> 00:41:50,330
Now meanwhile, you have other things.

951
00:41:50,330 --> 00:41:53,060
Initialized data, uninitialized data.

952
00:41:53,060 --> 00:41:56,440
Those two swaths of memory refer to global variables, which

953
00:41:56,440 --> 00:41:57,530
you don't often use.

954
00:41:57,530 --> 00:42:00,630
But sometimes if you do, they end up up there as well.

955
00:42:00,630 --> 00:42:01,620
Then there's some other stuff.

956
00:42:01,620 --> 00:42:04,130
Environment variables, which we won't spend much time on.

957
00:42:04,130 --> 00:42:06,120
But then two important things that will come back throughout this

958
00:42:06,120 --> 00:42:08,130
semester, stack and heap.

959
00:42:08,130 --> 00:42:12,280
>> So most of your computer's memory is reserved when running a program for

960
00:42:12,280 --> 00:42:14,880
something called the stack and something called the heap.

961
00:42:14,880 --> 00:42:16,940
And we're not going to talk about the heap today, but we will

962
00:42:16,940 --> 00:42:18,180
talk about the stack.

963
00:42:18,180 --> 00:42:22,910
And the stack is meant to conjure up the visual of like the dining hall

964
00:42:22,910 --> 00:42:26,120
meal trays in Mather House, or wherever you happen to be, where the

965
00:42:26,120 --> 00:42:27,810
dining hall staff clean them every day.

966
00:42:27,810 --> 00:42:30,180
They stack them up from floor on up.

967
00:42:30,180 --> 00:42:33,800
And similarly in memory, there is this idea of putting something on a

968
00:42:33,800 --> 00:42:36,740
stack, putting something on a stack, putting something on a stack.

969
00:42:36,740 --> 00:42:38,000
And what do we mean by this?

970
00:42:38,000 --> 00:42:41,430
Well, let's zoom in on just the lower half of this picture, your computer's

971
00:42:41,430 --> 00:42:43,990
RAM, to propose the following.

972
00:42:43,990 --> 00:42:48,300
It turns out that when you run a program like a.out or hello, whatever

973
00:42:48,300 --> 00:42:49,920
the program is that you've written,

974
00:42:49,920 --> 00:42:53,030
again, those zeroes and ones are loaded from your hard drive--which is

975
00:42:53,030 --> 00:42:56,190
long term storage, stays there even when you pull the plug--

976
00:42:56,190 --> 00:42:57,220
loaded into RAM.

977
00:42:57,220 --> 00:42:59,020
RAM is faster than hard drives.

978
00:42:59,020 --> 00:43:00,700
It's smaller than hard drives.

979
00:43:00,700 --> 00:43:03,490
But it's where programs live while you're running them.

980
00:43:03,490 --> 00:43:06,380
>> So you double click a program on a Mac or a PC--it's loaded from

981
00:43:06,380 --> 00:43:07,750
hard drive into RAM.

982
00:43:07,750 --> 00:43:11,760
As soon as it's loaded into RAM, the zeroes and ones go at the way top, the

983
00:43:11,760 --> 00:43:13,130
so-called text segment.

984
00:43:13,130 --> 00:43:17,040
But then as soon as your program actually starts running, the main

985
00:43:17,040 --> 00:43:18,140
function is called.

986
00:43:18,140 --> 00:43:21,070
And main, as we've seen, often has local variables.

987
00:43:21,070 --> 00:43:24,560
And it has ints and strings and chars and the like.

988
00:43:24,560 --> 00:43:28,300
So if your program that you have written or the program that you have

989
00:43:28,300 --> 00:43:33,680
double clicked used some variables inside of main, they end up at the

990
00:43:33,680 --> 00:43:37,020
bottom of your stack of memory, so to speak.

991
00:43:37,020 --> 00:43:39,160
Now more concretely, what does this actually mean?

992
00:43:39,160 --> 00:43:44,080
This just means that if we were going to number the things--

993
00:43:44,080 --> 00:43:49,380
if we were going to number the bytes of RAM in your computer, notice that

994
00:43:49,380 --> 00:43:51,650
this might be byte number zero.

995
00:43:51,650 --> 00:43:56,130
This might be byte number one, two, three, four, five, six, all

996
00:43:56,130 --> 00:43:57,290
the way up to like--

997
00:43:57,290 --> 00:44:01,520
2 billion would be all the way up there at the top.

998
00:44:01,520 --> 00:44:05,960
So in other words, when we talk about RAM or memory in terms of bytes, it

999
00:44:05,960 --> 00:44:09,680
just means that someone has decided what to number each of

1000
00:44:09,680 --> 00:44:11,110
those chunks of memory.

1001
00:44:11,110 --> 00:44:16,950
>> So when you need 32 bits for an int, or you need 8 bits for a char, where

1002
00:44:16,950 --> 00:44:18,320
do they end up in memory?

1003
00:44:18,320 --> 00:44:20,650
Well conceptually, they just end up at the bottom of this

1004
00:44:20,650 --> 00:44:21,780
thing called the stack.

1005
00:44:21,780 --> 00:44:25,670
But what's interesting now is when main calls a function.

1006
00:44:25,670 --> 00:44:28,830
Suppose a function called foo, just an arbitrary name.

1007
00:44:28,830 --> 00:44:32,480
What happens is main is at the bottom of this stack of memory.

1008
00:44:32,480 --> 00:44:35,630
Foo now is put on top of main in memory.

1009
00:44:35,630 --> 00:44:40,020
So any local variables that foo has end up sort of conceptually above

1010
00:44:40,020 --> 00:44:40,770
those in main.

1011
00:44:40,770 --> 00:44:46,920
If foo calls another function called bar, those variables end up here.

1012
00:44:46,920 --> 00:44:49,790
If bar calls something else, here, here, here.

1013
00:44:49,790 --> 00:44:53,900
So what's interesting about running a program is that as you call functions,

1014
00:44:53,900 --> 00:44:57,720
and as those functions call functions, and as those functions call functions,

1015
00:44:57,720 --> 00:45:00,980
you build up this stack of functions in memory.

1016
00:45:00,980 --> 00:45:06,740
And only once a function returns do you start getting that memory back.

1017
00:45:06,740 --> 00:45:11,190
So one of the easiest ways to run out of memory in a computer program is to

1018
00:45:11,190 --> 00:45:14,170
write functions that never return.

1019
00:45:14,170 --> 00:45:16,650
>> So for instance, let's demonstrate as much with an

1020
00:45:16,650 --> 00:45:18,460
intentionally buggy program.

1021
00:45:18,460 --> 00:45:24,690
Let me go ahead and do #include <stdio.h>, int main(void).

1022
00:45:24,690 --> 00:45:31,270
And I'm going to do while (2 > 1), which probably won't ever

1023
00:45:31,270 --> 00:45:33,370
change on us.

1024
00:45:33,370 --> 00:45:37,720
And let me go ahead now and do printf.

1025
00:45:37,720 --> 00:45:39,950
Actually, that's going to be less visually interesting.

1026
00:45:39,950 --> 00:45:40,460
Let's do this.

1027
00:45:40,460 --> 00:45:44,840
For int (i = 0; i > 0).

1028
00:45:44,840 --> 00:45:49,740
Let's make this mistake, i++.

1029
00:45:49,740 --> 00:45:51,150
And let's not printf here.

1030
00:45:51,150 --> 00:45:52,550
Let's practice what I was preaching.

1031
00:45:52,550 --> 00:45:54,090
Let's have a method here.

1032
00:45:54,090 --> 00:46:00,860
Void chorus, and we'll say int i.

1033
00:46:00,860 --> 00:46:02,295
And then I'm going to say, printf--

1034
00:46:04,871 --> 00:46:06,790
oh, let's make this more interesting.

1035
00:46:06,790 --> 00:46:08,350
Let's actually not print anything at all.

1036
00:46:08,350 --> 00:46:10,530
Let's just do this.

1037
00:46:10,530 --> 00:46:11,780
Chorus(i).

1038
00:46:16,630 --> 00:46:17,000
>> All right.

1039
00:46:17,000 --> 00:46:20,040
So this is buggy because why?

1040
00:46:20,040 --> 00:46:22,850
I'm making this up as I go because the program doesn't actually do anything

1041
00:46:22,850 --> 00:46:23,420
of interest.

1042
00:46:23,420 --> 00:46:24,670
But that's not the goal.

1043
00:46:24,670 --> 00:46:30,440
The goal is to write a program whose main function does what, apparently?

1044
00:46:30,440 --> 00:46:31,370
Call itself.

1045
00:46:31,370 --> 00:46:32,600
And actually, we don't need the loop.

1046
00:46:32,600 --> 00:46:36,070
Let's even simplify this just so as not to lose sight of really the

1047
00:46:36,070 --> 00:46:37,310
fundamental bug.

1048
00:46:37,310 --> 00:46:39,200
Main calls chorus to sing some chorus.

1049
00:46:39,200 --> 00:46:41,760
Then I did something stupid, and I had chorus call chorus because I assumed

1050
00:46:41,760 --> 00:46:43,550
someone else was going to implement it maybe.

1051
00:46:43,550 --> 00:46:45,960
And now this isn't going to compile yet.

1052
00:46:45,960 --> 00:46:48,340
I need to do what?

1053
00:46:48,340 --> 00:46:49,700
I need the prototype, remember.

1054
00:46:49,700 --> 00:46:55,520
So I need to have up here void chorus(int i);.

1055
00:46:55,520 --> 00:46:57,470
>> So now, if I go down here--

1056
00:46:57,470 --> 00:46:59,030
actually, let's use the bigger window.

1057
00:46:59,030 --> 00:47:01,670
Let's go ahead and make chorus.

1058
00:47:01,670 --> 00:47:06,000
Let's go ahead and make chorus.

1059
00:47:06,000 --> 00:47:08,302
Use of unidentified declarer i.

1060
00:47:08,302 --> 00:47:09,860
Oh, that was stupid.

1061
00:47:09,860 --> 00:47:11,020
We don't need the argument.

1062
00:47:11,020 --> 00:47:13,680
Let's just do this.

1063
00:47:13,680 --> 00:47:14,550
Wish we had started this way.

1064
00:47:14,550 --> 00:47:16,160
It would have been a much easier program to write.

1065
00:47:16,160 --> 00:47:20,100
So there.

1066
00:47:20,100 --> 00:47:23,870
Now let's go over to my terminal window, re-run Clang.

1067
00:47:23,870 --> 00:47:26,900
And here we go.

1068
00:47:26,900 --> 00:47:28,020
That was really fast.

1069
00:47:28,020 --> 00:47:30,690
What actually just happened, though?

1070
00:47:30,690 --> 00:47:33,430
Well, now I'll add the print line, so we can see.

1071
00:47:33,430 --> 00:47:41,330
So let me say printf, let's say, I'm in here.

1072
00:47:41,330 --> 00:47:43,470
Okay, no variables, we'll leave it like that.

1073
00:47:43,470 --> 00:47:44,860
Let me re-run make.

1074
00:47:44,860 --> 00:47:47,940
Let me re-run chorus.

1075
00:47:47,940 --> 00:47:51,235
And come on.

1076
00:47:53,880 --> 00:47:55,130
Keep going.

1077
00:47:57,630 --> 00:47:59,750
As an aside, why has it not crashed yet?

1078
00:47:59,750 --> 00:48:02,050
The segmentation fault happened super fast before.

1079
00:48:02,050 --> 00:48:04,250
[INAUDIBLE]

1080
00:48:04,250 --> 00:48:04,830
DAVID J. MALAN: Exactly.

1081
00:48:04,830 --> 00:48:06,350
So it takes time to print.

1082
00:48:06,350 --> 00:48:08,370
It just takes more work on the computer's part.

1083
00:48:08,370 --> 00:48:09,550
And there it is.

1084
00:48:09,550 --> 00:48:10,620
Segmentation fault.

1085
00:48:10,620 --> 00:48:12,140
>> So notice just how fast programs run.

1086
00:48:12,140 --> 00:48:14,110
If you're not printing anything, super fast.

1087
00:48:14,110 --> 00:48:18,100
But we still got this segmentation fault because what was happening?

1088
00:48:18,100 --> 00:48:21,310
Well, if you think about how your computer's memory is laid out, this

1089
00:48:21,310 --> 00:48:22,890
happens to be main.

1090
00:48:22,890 --> 00:48:23,800
But here--

1091
00:48:23,800 --> 00:48:28,670
let's just call this chorus, and let's call this chorus.

1092
00:48:28,670 --> 00:48:33,420
And now if I do my aesthetics right, this is just going to say chorus,

1093
00:48:33,420 --> 00:48:38,060
chorus, chorus, chorus, chorus, chorus, chorus, ad nauseum.

1094
00:48:38,060 --> 00:48:39,920
And eventually, what's going to happen?

1095
00:48:39,920 --> 00:48:46,690
If the big picture literally is this, what just happens conceptually?

1096
00:48:46,690 --> 00:48:48,320
The stack overruns the heap.

1097
00:48:48,320 --> 00:48:52,400
Or worse, you just overrun everything, including the text segment, which is

1098
00:48:52,400 --> 00:48:54,530
the zeroes and ones that represent your program.

1099
00:48:54,530 --> 00:48:56,690
In short, this is just super, super bad.

1100
00:48:56,690 --> 00:48:56,860
Right?

1101
00:48:56,860 --> 00:48:58,620
Your program has spiraled out of control.

1102
00:48:58,620 --> 00:49:02,840
You're using way more memory than you intended all because of a stupid

1103
00:49:02,840 --> 00:49:03,920
mistake, in this case.

1104
00:49:03,920 --> 00:49:08,160
Or in this case, a very deliberately done function calling itself.

1105
00:49:08,160 --> 00:49:09,210
Now this is not all bad.

1106
00:49:09,210 --> 00:49:12,540
Functions calling themselves actually has great power

1107
00:49:12,540 --> 00:49:13,700
when you use it correctly.

1108
00:49:13,700 --> 00:49:15,650
I have not used it correctly here.

1109
00:49:15,650 --> 00:49:16,940
>> So this is not all bad.

1110
00:49:16,940 --> 00:49:20,620
But the fact that I never actually stop calling myself is a fundamental

1111
00:49:20,620 --> 00:49:23,050
weakness here of this program.

1112
00:49:23,050 --> 00:49:25,090
So where are we going with all of this?

1113
00:49:25,090 --> 00:49:26,230
Well, what's really happening?

1114
00:49:26,230 --> 00:49:30,010
When I call the increment function, like we were doing in those examples,

1115
00:49:30,010 --> 00:49:33,290
I have a value like 1 that I pass in.

1116
00:49:33,290 --> 00:49:35,820
I pass in a copy of the number one.

1117
00:49:35,820 --> 00:49:37,080
So the following happens.

1118
00:49:37,080 --> 00:49:40,390
So let's go into the increment example.

1119
00:49:40,390 --> 00:49:44,230
And this guy right over here.

1120
00:49:44,230 --> 00:49:46,800
So here's what's actually happening.

1121
00:49:46,800 --> 00:49:50,770
When I called increment, and I pass in x, pictorially what's

1122
00:49:50,770 --> 00:49:53,660
going on here is this--

1123
00:49:53,660 --> 00:50:00,240
if I have the value of 1 stored here, and I actually call increment, which

1124
00:50:00,240 --> 00:50:02,680
is now called chorus--

1125
00:50:02,680 --> 00:50:04,010
yeah, that's throwing me off here.

1126
00:50:04,010 --> 00:50:06,750
So let's call this increment.

1127
00:50:06,750 --> 00:50:09,420
And we don't know what this next function's going to be.

1128
00:50:09,420 --> 00:50:14,270
So what's actually happening is here somewhere in main, I have a chunk of

1129
00:50:14,270 --> 00:50:16,670
memory that is storing the number 1.

1130
00:50:16,670 --> 00:50:19,730
When I call increment, I'm using another chunk of memory, but now I

1131
00:50:19,730 --> 00:50:20,840
have the copy of 1.

1132
00:50:20,840 --> 00:50:25,480
When I increment that value, this becomes 2--horribly written on the

1133
00:50:25,480 --> 00:50:26,420
screen here.

1134
00:50:26,420 --> 00:50:30,550
But then, what happens as soon as increment returns?

1135
00:50:30,550 --> 00:50:34,610
This memory just gets handed back to the operating system, which means all

1136
00:50:34,610 --> 00:50:37,470
you've done is nothing useful.

1137
00:50:37,470 --> 00:50:43,460
The one that was originally contained in main is still actually there.

1138
00:50:43,460 --> 00:50:44,650
>> So where are we going with this?

1139
00:50:44,650 --> 00:50:49,400
Well, it turns out that in memory you have this back to back sequence of

1140
00:50:49,400 --> 00:50:50,940
bytes that you can put stuff in.

1141
00:50:50,940 --> 00:50:53,760
And it turns out that we've already seen something that involves putting

1142
00:50:53,760 --> 00:50:55,100
things back to back to back to back.

1143
00:50:55,100 --> 00:51:00,170
What is a string, based on week one and now week two?

1144
00:51:00,170 --> 00:51:01,840
So it's just a collection of characters.

1145
00:51:01,840 --> 00:51:05,290
So it turns out, just as you can put numbers in memory, similarly you can

1146
00:51:05,290 --> 00:51:06,900
put characters in memory.

1147
00:51:06,900 --> 00:51:09,810
And once we start putting characters in memory back to back to back to

1148
00:51:09,810 --> 00:51:12,800
back, it turns out that using the simplest of things like a for loop or

1149
00:51:12,800 --> 00:51:14,510
a while loop, we can iterate--

1150
00:51:14,510 --> 00:51:17,130
from left to right over the characters in a string--

1151
00:51:17,130 --> 00:51:20,720
and start massaging them into different characters altogether.

1152
00:51:20,720 --> 00:51:25,550
A could become B. B could become C. So that ultimately, we can take an

1153
00:51:25,550 --> 00:51:28,830
English sentence that actually makes sense and convert each of those

1154
00:51:28,830 --> 00:51:32,440
letters one at a time by walking through our computer's memory left to

1155
00:51:32,440 --> 00:51:34,300
right to actually encrypt.

1156
00:51:34,300 --> 00:51:36,590
>> So let's take our five-minute break here, and when we come back, we'll

1157
00:51:36,590 --> 00:51:39,060
start this process of scrambling information.

1158
00:51:41,640 --> 00:51:43,180
>> All right.

1159
00:51:43,180 --> 00:51:48,440
So before we dive in to some crypto and these things called arrays, let me

1160
00:51:48,440 --> 00:51:51,610
pause for any questions because I feel like I really kind of muddled some of

1161
00:51:51,610 --> 00:51:52,230
those topics.

1162
00:51:52,230 --> 00:51:53,940
So let's fix now if we can.

1163
00:51:53,940 --> 00:51:56,480
So we just talked about return values.

1164
00:51:56,480 --> 00:51:58,630
We talked about arguments.

1165
00:51:58,630 --> 00:52:02,330
And we talked about this notion, which we'll come back to in the weeks to

1166
00:52:02,330 --> 00:52:07,140
come, of viewing memory as a whole bunch of these stacked

1167
00:52:07,140 --> 00:52:08,540
trays, so to speak.

1168
00:52:08,540 --> 00:52:13,460
From bottom on up, such that each tray that gets put on the stack represents

1169
00:52:13,460 --> 00:52:15,160
a function that's currently being called.

1170
00:52:17,970 --> 00:52:20,300
Any questions?

1171
00:52:20,300 --> 00:52:22,890
So how about--let me try asking a question.

1172
00:52:22,890 --> 00:52:25,520
I keep spoiling that, but now it's--you've all seen the boy's face.

1173
00:52:25,520 --> 00:52:27,020
So we'll come back to that.

1174
00:52:27,020 --> 00:52:29,700
>> So let me ask a question here.

1175
00:52:29,700 --> 00:52:34,810
Let me simplify this back to what it was before some of our earlier Q&A.

1176
00:52:34,810 --> 00:52:41,730
And the fact that increment has open parenthesis, int number, closed

1177
00:52:41,730 --> 00:52:42,260
parenthesis.

1178
00:52:42,260 --> 00:52:46,370
What does int number represent?

1179
00:52:46,370 --> 00:52:47,250
[INAUDIBLE]

1180
00:52:47,250 --> 00:52:47,870
DAVID J. MALAN: An argument.

1181
00:52:47,870 --> 00:52:50,732
Okay, but what's an argument?

1182
00:52:50,732 --> 00:52:51,620
[INAUDIBLE]

1183
00:52:51,620 --> 00:52:52,500
DAVID J. MALAN: Sorry, what's that?

1184
00:52:52,500 --> 00:52:53,150
SPEAKER 3: Something you pass in.

1185
00:52:53,150 --> 00:52:53,570
DAVID J. MALAN: Okay.

1186
00:52:53,570 --> 00:52:54,780
So something that you pass in.

1187
00:52:54,780 --> 00:52:56,560
And more generally, it's just the input.

1188
00:52:56,560 --> 00:52:59,860
If you're writing a function and that function's purpose in life is to do

1189
00:52:59,860 --> 00:53:03,290
something a little different every time you use it, then the only way for

1190
00:53:03,290 --> 00:53:07,710
that to happen really would seem to be to provide it with input so that it

1191
00:53:07,710 --> 00:53:10,180
can do something different with that input each time.

1192
00:53:10,180 --> 00:53:13,590
>> So you need to specify two things when a function takes inputs.

1193
00:53:13,590 --> 00:53:17,240
You need to specify the name that you want to give to that input, purely for

1194
00:53:17,240 --> 00:53:20,790
your own convenience so that you can refer to it in the function that you

1195
00:53:20,790 --> 00:53:23,610
yourself are writing, as I did here in line 32.

1196
00:53:23,610 --> 00:53:27,840
But you also need to specify its type because C is a programming language

1197
00:53:27,840 --> 00:53:28,840
that just requires

1198
00:53:28,840 --> 00:53:31,810
that if you want a variable, you have to tell the computer what

1199
00:53:31,810 --> 00:53:32,790
data type it is,

1200
00:53:32,790 --> 00:53:35,540
in large part so that it knows how many bits to

1201
00:53:35,540 --> 00:53:37,230
allocate for that variable.

1202
00:53:37,230 --> 00:53:38,600
Because it could be six--

1203
00:53:38,600 --> 00:53:39,990
sorry, it won't be six.

1204
00:53:39,990 --> 00:53:41,050
It can be 16.

1205
00:53:41,050 --> 00:53:41,630
It can be 8.

1206
00:53:41,630 --> 00:53:44,410
It can be 32, even 64.

1207
00:53:44,410 --> 00:53:45,820
But the computer needs to know.

1208
00:53:45,820 --> 00:53:49,110
Now the int on the left hand side represents what, by contrast?

1209
00:53:52,825 --> 00:53:53,780
[INAUDIBLE]

1210
00:53:53,780 --> 00:53:54,570
DAVID J. MALAN: What's that?

1211
00:53:54,570 --> 00:53:55,390
[INAUDIBLE]

1212
00:53:55,390 --> 00:53:57,920
DAVID J. MALAN: The type of the function and, more specifically, the

1213
00:53:57,920 --> 00:53:59,755
type of its output.

1214
00:53:59,755 --> 00:54:00,220
Right.

1215
00:54:00,220 --> 00:54:04,220
So whereas the thing in parentheses represents its input, if any, the

1216
00:54:04,220 --> 00:54:06,640
thing to the left represents its output.

1217
00:54:06,640 --> 00:54:10,560
And in this case, increment apparently returns an int.

1218
00:54:10,560 --> 00:54:14,590
And so int is the return type of this function.

1219
00:54:14,590 --> 00:54:16,090
>> What does it mean to return?

1220
00:54:16,090 --> 00:54:19,810
Literally, you use the keyword return.

1221
00:54:19,810 --> 00:54:24,640
And then if what you are returning to the right of the keyword is an

1222
00:54:24,640 --> 00:54:28,340
integer, then that is indeed consistent with what we have promised.

1223
00:54:28,340 --> 00:54:31,110
You could not do something like this--

1224
00:54:31,110 --> 00:54:32,280
hello, world--

1225
00:54:32,280 --> 00:54:33,500
because that is a string.

1226
00:54:33,500 --> 00:54:35,440
Obviously it is not an integer.

1227
00:54:35,440 --> 00:54:40,450
So in short, the burden is really on us, the programmer, to be specific as

1228
00:54:40,450 --> 00:54:44,730
to what we're returning and to then actually go about returning it.

1229
00:54:44,730 --> 00:54:49,030
And then to make a tad more clear the context--

1230
00:54:49,030 --> 00:54:50,080
there he is again.

1231
00:54:50,080 --> 00:54:51,060
The context--

1232
00:54:51,060 --> 00:54:52,830
big surprise coming in just a moment.

1233
00:54:52,830 --> 00:54:57,720
The context here now is that your computer's memory is, again, a

1234
00:54:57,720 --> 00:54:59,070
gigabyte, two gigabytes, whatever.

1235
00:54:59,070 --> 00:54:59,630
Maybe it's more.

1236
00:54:59,630 --> 00:55:00,540
Maybe it's less.

1237
00:55:00,540 --> 00:55:03,750
But the computer views it as having different sections.

1238
00:55:03,750 --> 00:55:04,860
Something goes down there.

1239
00:55:04,860 --> 00:55:06,020
Something else goes up there.

1240
00:55:06,020 --> 00:55:07,540
Different stuff goes in the middle.

1241
00:55:07,540 --> 00:55:09,300
And today, we just begin telling this story.

1242
00:55:09,300 --> 00:55:11,130
>> But we'll come back to this over time.

1243
00:55:11,130 --> 00:55:15,000
For now, the only piece of memory we really care about is the text segment

1244
00:55:15,000 --> 00:55:17,160
because that just represents the zeroes and ones

1245
00:55:17,160 --> 00:55:18,460
that Clang has outputted.

1246
00:55:18,460 --> 00:55:21,570
So when you run a command at the keyboard like a.out, or you double

1247
00:55:21,570 --> 00:55:25,350
click an icon on Mac OS or Windows, your program's loaded from your hard

1248
00:55:25,350 --> 00:55:26,930
drive into RAM.

1249
00:55:26,930 --> 00:55:30,850
And it's plopped at the top of your computer's RAM, so to speak.

1250
00:55:30,850 --> 00:55:35,470
Now meanwhile, as your program starts running and main gets called in the

1251
00:55:35,470 --> 00:55:39,240
program you wrote or the program Microsoft or Apple wrote, any of its

1252
00:55:39,240 --> 00:55:42,930
local variables end up down there at the bottom of your computer's memory.

1253
00:55:42,930 --> 00:55:46,490
But if main calls another function that itself has variables or

1254
00:55:46,490 --> 00:55:48,340
arguments, they end up above it.

1255
00:55:48,340 --> 00:55:50,670
And if that function calls something, they end up above it,

1256
00:55:50,670 --> 00:55:51,840
above it, above it.

1257
00:55:51,840 --> 00:55:56,100
And only once a function is done executing does the stack of trays, so

1258
00:55:56,100 --> 00:55:58,320
to speak, start to get lower and lower.

1259
00:55:58,320 --> 00:56:03,370
And this is what then, in a nutshell, explains why, when you call cube--

1260
00:56:03,370 --> 00:56:04,660
or you call increment--

1261
00:56:04,660 --> 00:56:06,490
you're passing in a copy of the value.

1262
00:56:06,490 --> 00:56:09,840
And what that means pictorially is that you're literally writing the

1263
00:56:09,840 --> 00:56:14,540
number 1 in another part of memory, changing that 1 to 2, in the case of

1264
00:56:14,540 --> 00:56:15,360
increment--

1265
00:56:15,360 --> 00:56:17,450
or to an 8, in the case of cube--

1266
00:56:17,450 --> 00:56:21,450
and then throwing that memory away as soon as the increment or the cube

1267
00:56:21,450 --> 00:56:23,410
function returns.

1268
00:56:23,410 --> 00:56:24,267
>> Question.

1269
00:56:24,267 --> 00:56:25,517
[INAUDIBLE]

1270
00:56:28,090 --> 00:56:29,970
DAVID J. MALAN: Where--global variables are stored in what's

1271
00:56:29,970 --> 00:56:32,960
currently called the initialized data or uninitialized data.

1272
00:56:32,960 --> 00:56:35,900
The difference being, if you have a global variable, and you assign it

1273
00:56:35,900 --> 00:56:39,530
immediately a value with the equals sign, it ends up at the top there.

1274
00:56:39,530 --> 00:56:43,390
And if you just say int x semicolon with no value, it ends up slightly

1275
00:56:43,390 --> 00:56:46,670
lower in RAM simply by convention.

1276
00:56:46,670 --> 00:56:49,308
Other questions.

1277
00:56:49,308 --> 00:56:49,750
All right.

1278
00:56:49,750 --> 00:56:53,040
>> So this picture will come back as we get more powerful with what we can do

1279
00:56:53,040 --> 00:56:53,830
with the computer.

1280
00:56:53,830 --> 00:56:58,790
But for now, let's have a brief intro to cryptography, a specific type of

1281
00:56:58,790 --> 00:57:01,910
cryptography that doesn't solve all of the world's problems but does solve

1282
00:57:01,910 --> 00:57:02,480
some of them.

1283
00:57:02,480 --> 00:57:06,090
In this case here, we have something called secret key cryptography.

1284
00:57:06,090 --> 00:57:10,430
And secret key cryptography, as the name suggests, derives its security

1285
00:57:10,430 --> 00:57:11,330
from a secret.

1286
00:57:11,330 --> 00:57:14,720
So for instance, if you're back in grade school and you're passing a

1287
00:57:14,720 --> 00:57:18,040
little secret love letter to the boy or girl you are crushing on--if you

1288
00:57:18,040 --> 00:57:20,820
wanted to pass that through the audience, you probably wouldn't write

1289
00:57:20,820 --> 00:57:24,120
such a note in English or whatever your native language is; rather, you

1290
00:57:24,120 --> 00:57:25,800
might encrypt it.

1291
00:57:25,800 --> 00:57:27,820
Or you might just send them a text message these days.

1292
00:57:27,820 --> 00:57:30,310
But you might actually pass them a note throughout the classroom.

1293
00:57:30,310 --> 00:57:33,820
And to do this securely, in such a way that your friends and the teacher

1294
00:57:33,820 --> 00:57:36,820
don't know what you're writing, you might come up with a fairly simple

1295
00:57:36,820 --> 00:57:37,800
algorithm--

1296
00:57:37,800 --> 00:57:39,290
young though you might be--

1297
00:57:39,290 --> 00:57:40,780
to just scramble the words.

1298
00:57:40,780 --> 00:57:44,390
So instead of writing A, you might write B. Instead of B, you might write

1299
00:57:44,390 --> 00:57:46,670
C. Instead of C, you might write D, and so forth.

1300
00:57:46,670 --> 00:57:50,020
Or you could come up with a more sophisticated translation of letters

1301
00:57:50,020 --> 00:57:51,300
to different letters.

1302
00:57:51,300 --> 00:57:55,440
But the catch is the boy or girl to whom you're sending this note needs to

1303
00:57:55,440 --> 00:57:56,850
know something.

1304
00:57:56,850 --> 00:57:59,620
Which is what, obviously?

1305
00:57:59,620 --> 00:58:01,400
Like, what your secret is.

1306
00:58:01,400 --> 00:58:04,620
Like, what is that mapping between As and Bs and Cs and Ds?

1307
00:58:04,620 --> 00:58:08,780
Is it just adding one, so to speak, to each of the letters to go from

1308
00:58:08,780 --> 00:58:09,730
A to B, B to C?

1309
00:58:09,730 --> 00:58:11,350
Is it more complex than that?

1310
00:58:11,350 --> 00:58:16,450
So you and your crush need to have this secret information.

1311
00:58:16,450 --> 00:58:18,170
But there's kind of a catch-22 here.

1312
00:58:18,170 --> 00:58:20,760
If this is the very first time you're sending this love letter through the

1313
00:58:20,760 --> 00:58:25,590
class, how is that boy or girl going to know what the secret even is?

1314
00:58:25,590 --> 00:58:28,450
So secret key crypto does not solve all the world's problems.

1315
00:58:28,450 --> 00:58:30,490
And there's actually a relationship that we'll come back to toward

1316
00:58:30,490 --> 00:58:31,370
semester's end.

1317
00:58:31,370 --> 00:58:35,970
>> Similarly, have none of us probably ever sent a--

1318
00:58:35,970 --> 00:58:39,453
similarly, do most of us not know someone that works, for instance, at

1319
00:58:39,453 --> 00:58:40,300
Amazon.com.

1320
00:58:40,300 --> 00:58:43,130
And yet, many of us have probably bought stuff at Amazon.com.

1321
00:58:43,130 --> 00:58:45,670
And we've been taught to assume that these e-commerce

1322
00:58:45,670 --> 00:58:47,060
transactions are secure.

1323
00:58:47,060 --> 00:58:47,210
Right?

1324
00:58:47,210 --> 00:58:49,310
The URL probably says https.

1325
00:58:49,310 --> 00:58:51,590
There's maybe a silly little padlock icon somewhere.

1326
00:58:51,590 --> 00:58:54,680
There's some kind of cryptography securing your credit card information

1327
00:58:54,680 --> 00:58:56,980
between you and Amazon.com.

1328
00:58:56,980 --> 00:59:00,410
And yet, if cryptography involves knowing some secret, and yet I don't

1329
00:59:00,410 --> 00:59:03,330
know anyone at Amazon, and I've certainly not arranged any kind of

1330
00:59:03,330 --> 00:59:07,350
secret with someone at Amazon, how is my computer or my browser doing this?

1331
00:59:07,350 --> 00:59:10,100
Well, turns out there's other types of cryptography altogether that solve

1332
00:59:10,100 --> 00:59:10,740
that problem.

1333
00:59:10,740 --> 00:59:13,610
But for today, we'll focus on the simple one, where you can arrange in

1334
00:59:13,610 --> 00:59:18,480
advance to know some secret, like plus 1 or some mapping between As and Bs.

1335
00:59:18,480 --> 00:59:20,710
>> And the process of cryptography generally involves this.

1336
00:59:20,710 --> 00:59:23,550
You have some plain text, depicted here at left.

1337
00:59:23,550 --> 00:59:26,260
You run it through some kind of algorithm or procedure

1338
00:59:26,260 --> 00:59:27,670
for encrypting it.

1339
00:59:27,670 --> 00:59:31,390
Maybe that's just A becomes B, B becomes C. And then you end up with

1340
00:59:31,390 --> 00:59:32,260
cipher text.

1341
00:59:32,260 --> 00:59:36,450
Meanwhile, once your crush receives the secret note, he or she has to then

1342
00:59:36,450 --> 00:59:39,950
decrypt it by generally reversing that algorithm so as to get

1343
00:59:39,950 --> 00:59:41,640
back the plain text.

1344
00:59:41,640 --> 00:59:43,860
Now there are physical incarnations of this.

1345
00:59:43,860 --> 00:59:46,720
For instance, this is a little secret decoder ring.

1346
00:59:46,720 --> 00:59:50,060
And this is a ring in the sense that there's two dials here.

1347
00:59:50,060 --> 00:59:53,630
On the outside periphery of this thing, there's letters A through Z,

1348
00:59:53,630 --> 00:59:55,110
although they're in random order.

1349
00:59:55,110 --> 00:59:58,410
And on the inside, there's actually some numbers, such that with this

1350
00:59:58,410 --> 01:00:02,940
ring, you can kind of turn the outside but not the inside in order to line up

1351
01:00:02,940 --> 01:00:04,110
numbers with letters.

1352
01:00:04,110 --> 01:00:08,290
And in the clip you're about to see--some of which you may have seen 24/7

1353
01:00:08,290 --> 01:00:11,120
around the Christmas season from a movie called A Christmas Story.

1354
01:00:11,120 --> 01:00:16,050
You'll see that little Ralphie was so eager to figure out what little orphan

1355
01:00:16,050 --> 01:00:19,810
Annie's secret message was to him that had been communicated, I think, in the

1356
01:00:19,810 --> 01:00:22,810
form of numeric messages on a serial box.

1357
01:00:22,810 --> 01:00:26,760
And you had to accumulate all the little cards that came

1358
01:00:26,760 --> 01:00:27,480
in the cereal box.

1359
01:00:27,480 --> 01:00:28,320
You had to mail them in.

1360
01:00:28,320 --> 01:00:31,060
You had to get back the secret decoder ring, so that you can finally figure

1361
01:00:31,060 --> 01:00:34,190
out what the mapping is between letters and numbers,

1362
01:00:34,190 --> 01:00:35,420
or letters and letters.

1363
01:00:35,420 --> 01:00:39,790
So I give you this short clip from A Christmas Story to motivate pset 2 and

1364
01:00:39,790 --> 01:00:42,340
our discussion, in a moment, of arrays.

1365
01:00:42,340 --> 01:00:43,773
So here we have Ralphie.

1366
01:00:43,773 --> 01:00:44,126
>> [VIDEO PLAYBACK]

1367
01:00:44,126 --> 01:00:47,470
-Be it known to all and sundry that Ralph Parker is hereby appointed a

1368
01:00:47,470 --> 01:00:50,690
member of the Little Orphan Annie Secret Circle and is entitled to all

1369
01:00:50,690 --> 01:00:53,500
the honors and benefits occurring thereto.

1370
01:00:53,500 --> 01:00:56,040
-Signed, Little Orphan Annie.

1371
01:00:56,040 --> 01:00:58,730
Countersigned, Pierre Andre!

1372
01:00:58,730 --> 01:01:00,150
In ink!

1373
01:01:00,150 --> 01:01:02,910
Honors and benefits, already at the age of nine.

1374
01:01:09,970 --> 01:01:10,730
Come on, let's get on with it.

1375
01:01:10,730 --> 01:01:15,000
I don't need all that jazz about smugglers and pirates.

1376
01:01:15,000 --> 01:01:17,624
-Listen tomorrow night for the concluding adventure of The Black

1377
01:01:17,624 --> 01:01:19,710
Pirate Ship.

1378
01:01:19,710 --> 01:01:23,380
Now it's time for Annie's secret message for you members

1379
01:01:23,380 --> 01:01:25,670
of the Secret Circle.

1380
01:01:25,670 --> 01:01:30,260
Remember, kids, only members of Annie's Secret Circle can decode

1381
01:01:30,260 --> 01:01:31,660
Annie's secret message.

1382
01:01:31,660 --> 01:01:36,230
Remember, Annie is depending on you.

1383
01:01:36,230 --> 01:01:38,720
Set your pins to B2.

1384
01:01:38,720 --> 01:01:41,040
Here is the message.

1385
01:01:41,040 --> 01:01:42,470
12, 11--

1386
01:01:42,470 --> 01:01:46,000
-I am in my first secret meeting.

1387
01:01:46,000 --> 01:01:49,440
-14, 11, 18, 16--

1388
01:01:49,440 --> 01:01:51,700
-Pierre was in great voice tonight.

1389
01:01:51,700 --> 01:01:54,890
I could tell that tonight's message was really important.

1390
01:01:54,890 --> 01:01:56,750
-3, 25.

1391
01:01:56,750 --> 01:01:58,590
That's a message from Annie herself.

1392
01:01:58,590 --> 01:01:59,840
Remember, don't tell anyone.

1393
01:02:04,570 --> 01:02:08,750
-90 Seconds later, I'm in the only room in the house where a boy of nine

1394
01:02:08,750 --> 01:02:12,980
could sit in privacy and decode.

1395
01:02:12,980 --> 01:02:17,130
Aha, B. I went to the next.

1396
01:02:17,130 --> 01:02:20,330
E. The first word is be.

1397
01:02:20,330 --> 01:02:22,670
S. It was coming easier now.

1398
01:02:22,670 --> 01:02:24,590
U.

1399
01:02:24,590 --> 01:02:26,510
-Oh, come on, Ralphie.

1400
01:02:26,510 --> 01:02:28,430
I got to go.

1401
01:02:28,430 --> 01:02:30,350
-I'll be right down, ma.

1402
01:02:30,350 --> 01:02:33,720
-Gee whiz.

1403
01:02:33,720 --> 01:02:38,270
-T, O. Be sure to.

1404
01:02:38,270 --> 01:02:40,000
Be sure to what?

1405
01:02:40,000 --> 01:02:42,105
What was Little Orphan Annie trying to say?

1406
01:02:42,105 --> 01:02:43,095
Be sure to what?

1407
01:02:43,095 --> 01:02:43,590
-Ralphie!

1408
01:02:43,590 --> 01:02:44,580
Randy has got to go.

1409
01:02:44,580 --> 01:02:45,570
Will you please come out?

1410
01:02:45,570 --> 01:02:46,560
-All right, ma.

1411
01:02:46,560 --> 01:02:48,540
I'll be right out.

1412
01:02:48,540 --> 01:02:50,580
-I was getting closer now.

1413
01:02:50,580 --> 01:02:52,550
The tension was terrible.

1414
01:02:52,550 --> 01:02:53,355
What was it?

1415
01:02:53,355 --> 01:02:56,315
The fate of the planet may hang in the balance.

1416
01:02:56,315 --> 01:02:56,790
-Ralphie!

1417
01:02:56,790 --> 01:02:59,165
Randy's got to go.

1418
01:02:59,165 --> 01:03:02,310
-I'll be right out, for crying out loud.

1419
01:03:02,310 --> 01:03:04,000
-Gee, almost there.

1420
01:03:04,000 --> 01:03:05,180
My fingers flew.

1421
01:03:05,180 --> 01:03:07,150
My mind was a steel trap.

1422
01:03:07,150 --> 01:03:08,790
Every pore vibrated.

1423
01:03:08,790 --> 01:03:10,040
It was almost clear.

1424
01:03:10,040 --> 01:03:13,400
Yes, yes, yes, yes.

1425
01:03:13,400 --> 01:03:18,960
-Be sure to drink your Ovaltine.

1426
01:03:18,960 --> 01:03:20,210
Ovaltine?

1427
01:03:24,010 --> 01:03:25,260
A crummy commercial?

1428
01:03:28,200 --> 01:03:29,640
Son of a bitch.

1429
01:03:29,640 --> 01:03:33,340
[END VIDEO PLAYBACK]

1430
01:03:33,340 --> 01:03:36,040
>> DAVID J. MALAN: So there we have cryptography.

1431
01:03:36,040 --> 01:03:39,670
So how in a computer can we go about implementing or

1432
01:03:39,670 --> 01:03:40,950
representing things like this?

1433
01:03:40,950 --> 01:03:44,430
Well, we need a way of expressing ourselves a little more flexibly than

1434
01:03:44,430 --> 01:03:46,420
our variables thus far have allowed.

1435
01:03:46,420 --> 01:03:47,370
We've had ints.

1436
01:03:47,370 --> 01:03:48,380
We've had chars.

1437
01:03:48,380 --> 01:03:50,790
We've had floats and doubles and a few others.

1438
01:03:50,790 --> 01:03:55,050
But those are individual pieces of memory that don't really allow us to

1439
01:03:55,050 --> 01:03:58,010
express things like words and sentences and phrases.

1440
01:03:58,010 --> 01:04:00,200
Indeed, we've called such things strings.

1441
01:04:00,200 --> 01:04:03,650
But we promised that this is really just a simplification in the CS50

1442
01:04:03,650 --> 01:04:07,020
library that we're intending to peel back.

1443
01:04:07,020 --> 01:04:08,970
>> And so let's start to do that here.

1444
01:04:08,970 --> 01:04:11,130
Let me go ahead and open up a file--

1445
01:04:11,130 --> 01:04:13,770
all of these files are available as usual online--

1446
01:04:13,770 --> 01:04:19,120
called array.c to solve a problem unrelated to strings but that paints a

1447
01:04:19,120 --> 01:04:23,040
picture here of how we might use something called an array.

1448
01:04:23,040 --> 01:04:25,530
An array is a data type.

1449
01:04:25,530 --> 01:04:31,320
It's a type of variable, of sorts, that has multiple smaller data types

1450
01:04:31,320 --> 01:04:34,150
inside of it back to back to back to back.

1451
01:04:34,150 --> 01:04:37,700
So for instance, if we want to write a little program that gives you your

1452
01:04:37,700 --> 01:04:42,110
quiz average for a course like 50 that has two quizzes, you could very easily

1453
01:04:42,110 --> 01:04:45,170
write this program--based even on some of last week's material--

1454
01:04:45,170 --> 01:04:47,770
by using GetInt and a couple of variables.

1455
01:04:47,770 --> 01:04:51,920
Int quiz1, int quiz2, and it's pretty straightforward.

1456
01:04:51,920 --> 01:04:55,930
It's maybe 10, 20 lines of code, max, to implement a program that asks the

1457
01:04:55,930 --> 01:05:01,170
user for two quiz scores and then computes their average by adding them

1458
01:05:01,170 --> 01:05:03,850
together, dividing by two, and then printing the results.

1459
01:05:03,850 --> 01:05:06,380
We could probably do that pretty readily now after

1460
01:05:06,380 --> 01:05:07,510
some number of minutes.

1461
01:05:07,510 --> 01:05:11,005
>> But the problem is that suppose that 50 had three quizzes or four.

1462
01:05:11,005 --> 01:05:13,510
Suppose that you wanted to use the same program for a class that had

1463
01:05:13,510 --> 01:05:14,850
weekly quizzes.

1464
01:05:14,850 --> 01:05:16,610
Think about a class that has weekly quizzes.

1465
01:05:16,610 --> 01:05:20,610
If there's like 16 or so weeks in a semester, now you have 16 variables--

1466
01:05:20,610 --> 01:05:24,270
int quiz1, int quiz2, int quiz3, int quiz4.

1467
01:05:24,270 --> 01:05:27,560
As soon as you start seeing this redundancy, this copying and pasting

1468
01:05:27,560 --> 01:05:31,390
of code, it should start to make you wish there were a better way.

1469
01:05:31,390 --> 01:05:33,930
And thankfully, because of arrays, there is.

1470
01:05:33,930 --> 01:05:34,980
So let's do this.

1471
01:05:34,980 --> 01:05:38,430
First, let me introduce a very simple thing that we've not used thus far,

1472
01:05:38,430 --> 01:05:40,140
but you'll see it occasionally in code.

1473
01:05:40,140 --> 01:05:42,360
This is what's generally called a constant.

1474
01:05:42,360 --> 01:05:45,790
So it's a constant in the sense that this value never changes.

1475
01:05:45,790 --> 01:05:49,210
The human convention when creating a constant is to use all capital

1476
01:05:49,210 --> 01:05:51,940
letters, just so that it really stands out in your code.

1477
01:05:51,940 --> 01:05:55,960
And the special keyword that you use in C is #define.

1478
01:05:55,960 --> 01:06:00,250
So if you say #define, then a space, then the word that you want to use for

1479
01:06:00,250 --> 01:06:03,260
the constant's name, and then the value of the constant.

1480
01:06:03,260 --> 01:06:06,180
So notice, this is different from assigning something to a variable.

1481
01:06:06,180 --> 01:06:07,020
There's no equals sign.

1482
01:06:07,020 --> 01:06:08,240
There's no semicolon.

1483
01:06:08,240 --> 01:06:11,410
This is what's generally known as a preprocessor directive, but more on

1484
01:06:11,410 --> 01:06:12,210
that another time.

1485
01:06:12,210 --> 01:06:18,540
>> For now, this creates an unchanging value called QUIZZES whose actual

1486
01:06:18,540 --> 01:06:19,940
numeric value is 2.

1487
01:06:19,940 --> 01:06:24,020
So anywhere you see QUIZZES, QUIZZES, QUIZZES throughout this file, that's

1488
01:06:24,020 --> 01:06:25,410
just the number 2.

1489
01:06:25,410 --> 01:06:28,100
Now, if I look at main now, let's see how this works.

1490
01:06:28,100 --> 01:06:29,500
At first, it looks a little cryptic.

1491
01:06:29,500 --> 01:06:31,340
But it's all stuff from week one.

1492
01:06:31,340 --> 01:06:32,710
Ask the user for grades.

1493
01:06:32,710 --> 01:06:33,630
How do we do this?

1494
01:06:33,630 --> 01:06:35,470
Well, in line 22--

1495
01:06:35,470 --> 01:06:37,210
this is really the juicy part--

1496
01:06:37,210 --> 01:06:40,960
I declare a float, but not just a single float.

1497
01:06:40,960 --> 01:06:44,620
I'm declaring, rather, an array of floating point values.

1498
01:06:44,620 --> 01:06:49,100
That variable is going to be called grades, as implied here.

1499
01:06:49,100 --> 01:06:53,080
But the only piece of new syntax then are these square brackets, the fact

1500
01:06:53,080 --> 01:06:59,350
that I've said float grades and then open bracket and then a number.

1501
01:06:59,350 --> 01:07:02,460
Notice, if this is a constant, this is just like we did this.

1502
01:07:02,460 --> 01:07:06,890
This means hey computer, give me two floats, and let's collectively call

1503
01:07:06,890 --> 01:07:08,220
them grades.

1504
01:07:08,220 --> 01:07:11,920
This is in contrast to a much more tedious process like this.

1505
01:07:11,920 --> 01:07:15,850
Float grade1, float grade2, and so forth.

1506
01:07:15,850 --> 01:07:20,010
So an array allows us to implement this idea but much less messily, in

1507
01:07:20,010 --> 01:07:24,630
such a way that we can write one line of code instead of, say, 16 for a 16

1508
01:07:24,630 --> 01:07:25,740
week semester.

1509
01:07:25,740 --> 01:07:29,950
So I didn't want to hard-code 2 because if you think about this now

1510
01:07:29,950 --> 01:07:34,160
logically--suppose next year CS50 changes to 3 quizzes instead.

1511
01:07:34,160 --> 01:07:35,510
And I had the number 2 here.

1512
01:07:35,510 --> 01:07:36,600
I had the number 2 here.

1513
01:07:36,600 --> 01:07:37,580
I had the number 2 here.

1514
01:07:37,580 --> 01:07:38,560
I had the number 2 here.

1515
01:07:38,560 --> 01:07:43,180
It becomes very tedious and very easy to screw up and to accidentally change

1516
01:07:43,180 --> 01:07:47,690
one value to 3 and miss some other value of 2.

1517
01:07:47,690 --> 01:07:52,460
So I'm going to instead abstract this away and use this constant that, as its

1518
01:07:52,460 --> 01:07:54,120
name suggests, never changes.

1519
01:07:54,120 --> 01:07:57,710
And now, no matter whether we have different quizzes this year or next, I

1520
01:07:57,710 --> 01:08:01,210
just have to change it in one place, up here at top.

1521
01:08:01,210 --> 01:08:02,720
>> So that's all constant is.

1522
01:08:02,720 --> 01:08:08,680
Meanwhile, the new conceptual feature is that of an array.

1523
01:08:08,680 --> 01:08:14,660
So the square brackets give me this many floats and lets me collectively

1524
01:08:14,660 --> 01:08:16,630
call them grades here.

1525
01:08:16,630 --> 01:08:17,990
So now let's see what I'm going to do.

1526
01:08:17,990 --> 01:08:20,359
Here in line 24 is the beginning of a for loop.

1527
01:08:20,359 --> 01:08:22,260
This is really nothing fancy.

1528
01:08:22,260 --> 01:08:25,060
It's just using quizzes instead of a hard-coded number.

1529
01:08:25,060 --> 01:08:27,790
But there's nothing intellectually different there from last week.

1530
01:08:27,790 --> 01:08:29,040
This is just printf.

1531
01:08:29,040 --> 01:08:35,490
So printf("quiz number %d of %d") because I just want to print out give me quiz

1532
01:08:35,490 --> 01:08:38,050
number one of two and then two of two.

1533
01:08:38,050 --> 01:08:39,850
So this is purely an aesthetic thing.

1534
01:08:39,850 --> 01:08:42,500
But the interesting part now is in line 27.

1535
01:08:42,500 --> 01:08:48,310
In order to fill in one of the two placeholders with a floating-point

1536
01:08:48,310 --> 01:08:51,029
value, you again use square brackets.

1537
01:08:51,029 --> 01:08:55,620
In this case, I'm using i because this for loop has started with i equaling

1538
01:08:55,620 --> 01:08:57,560
what value, apparently?

1539
01:08:57,560 --> 01:08:58,279
0.

1540
01:08:58,279 --> 01:09:01,350
>> So on the first iteration of this loop, it is as though I

1541
01:09:01,350 --> 01:09:02,689
wrote this in code.

1542
01:09:02,689 --> 01:09:05,580
But on the second iteration of this loop, it is as though I

1543
01:09:05,580 --> 01:09:07,750
wrote this in my code.

1544
01:09:07,750 --> 01:09:10,750
But the fact that I'm using a variable is perfect because, as the name

1545
01:09:10,750 --> 01:09:14,300
suggests, it's varying its value on every iteration.

1546
01:09:14,300 --> 01:09:17,370
So I'm filling this array one spot at a time.

1547
01:09:17,370 --> 01:09:18,910
What does this array look like?

1548
01:09:18,910 --> 01:09:21,430
Well, the reason I drew this super simple rectangle on the screen here

1549
01:09:21,430 --> 01:09:23,350
before was for this reason.

1550
01:09:23,350 --> 01:09:27,279
An array is just a chunk of memory followed by another chunk of memory,

1551
01:09:27,279 --> 01:09:30,109
followed by another chunk of memory, and so forth.

1552
01:09:30,109 --> 01:09:35,260
So if my array is of size 2, in this case here, all I would be doing by

1553
01:09:35,260 --> 01:09:37,590
typing in my quiz scores, like here.

1554
01:09:37,590 --> 01:09:39,430
I got 100 on this one.

1555
01:09:39,430 --> 01:09:42,020
And then I got a 99 on this one.

1556
01:09:42,020 --> 01:09:46,040
Then this memory might not even be used because I've only asked the

1557
01:09:46,040 --> 01:09:48,689
computer for an array of size 2.

1558
01:09:48,689 --> 01:09:50,180
Those squares are still there.

1559
01:09:50,180 --> 01:09:50,340
Right?

1560
01:09:50,340 --> 01:09:52,500
You still have two gigabytes of RAM, even if you're only

1561
01:09:52,500 --> 01:09:53,979
asking for two floats.

1562
01:09:53,979 --> 01:09:58,710
So the idea behind arrays is that the computer just takes a chunk of memory

1563
01:09:58,710 --> 01:10:03,230
and then apportions smaller pieces back to back to back to back.

1564
01:10:03,230 --> 01:10:04,740
And so that's all an array is.

1565
01:10:04,740 --> 01:10:09,080
It's a contiguous chunk of memory, inside of which you can put things.

1566
01:10:09,080 --> 01:10:12,400
>> Now this happens to then do just some boring arithmetic.

1567
01:10:12,400 --> 01:10:16,170
If I scroll down here, this is where I then iterate over the array.

1568
01:10:16,170 --> 01:10:19,410
I come up with the summation of all the values in the array.

1569
01:10:19,410 --> 01:10:22,390
And then I use the round function here to actually do the

1570
01:10:22,390 --> 01:10:23,940
sum divided by quizzes.

1571
01:10:23,940 --> 01:10:27,450
But let me wave my hand at that as sort of enough arithmetic for now.

1572
01:10:27,450 --> 01:10:30,010
But all that's doing for me ultimately is computing an average.

1573
01:10:30,010 --> 01:10:33,640
So first quiz plus second quiz, divided by 2, and then printing

1574
01:10:33,640 --> 01:10:34,700
it out as an int.

1575
01:10:34,700 --> 01:10:39,030
>> But let's now transition to a different example called string1,

1576
01:10:39,030 --> 01:10:42,370
which paints a similar picture but using strings.

1577
01:10:42,370 --> 01:10:45,550
Let me go ahead and simplify this for just a moment.

1578
01:10:45,550 --> 01:10:48,340
And forgive the indentation for now.

1579
01:10:48,340 --> 01:10:52,280
Notice in line 19 of this example, I get a string from the user.

1580
01:10:52,280 --> 01:10:55,780
But notice what I'm next doing in lines 22 onward.

1581
01:10:55,780 --> 01:11:00,260
I'm actually iterating from i up to--and this is a new trick--

1582
01:11:00,260 --> 01:11:02,730
strlen, string length.

1583
01:11:02,730 --> 01:11:07,010
This is a function that comes with C that if you pass it a string, it tells

1584
01:11:07,010 --> 01:11:08,950
you how many characters are in that string.

1585
01:11:08,950 --> 01:11:09,440
That's all.

1586
01:11:09,440 --> 01:11:12,520
The fact that it's strlen instead of string length is just because it's

1587
01:11:12,520 --> 01:11:13,040
more succinct.

1588
01:11:13,040 --> 01:11:17,100
30 years ago, people liked to write things as succinctly as possible.

1589
01:11:17,100 --> 01:11:19,080
So we've kept that convention here.

1590
01:11:19,080 --> 01:11:21,730
i++ just means increment i in each iteration.

1591
01:11:21,730 --> 01:11:24,310
And now notice this, which is really interesting.

1592
01:11:24,310 --> 01:11:28,730
So in line 24, I say computer, give me a character, eight

1593
01:11:28,730 --> 01:11:30,770
bits, and call it c.

1594
01:11:30,770 --> 01:11:35,370
But what is this on the right hand side saying?

1595
01:11:35,370 --> 01:11:38,150
In English, what does that represent?

1596
01:11:38,150 --> 01:11:40,070
[INAUDIBLE]

1597
01:11:40,070 --> 01:11:40,490
DAVID J. MALAN: Exactly.

1598
01:11:40,490 --> 01:11:42,390
Give me the first character in the array.

1599
01:11:42,390 --> 01:11:45,400
Or more generally, give me the i-th character in the array.

1600
01:11:45,400 --> 01:11:48,230
And realize it's important now that as computer scientists, we're actually

1601
01:11:48,230 --> 01:11:49,330
counting from 0.

1602
01:11:49,330 --> 01:11:51,290
You don't have discretion now to start doing this.

1603
01:11:51,290 --> 01:11:54,580
Now you have to behave in accordance with the computer's expectations and

1604
01:11:54,580 --> 01:11:58,010
count from zero because [0] is going to be the first

1605
01:11:58,010 --> 01:11:59,670
character in a string.

1606
01:11:59,670 --> 01:12:01,320
[1] is going to be the second.

1607
01:12:01,320 --> 01:12:03,610
[2] is going to be the third, and so forth.

1608
01:12:03,610 --> 01:12:08,840
So this program, if I compile it--this is, again, string1.

1609
01:12:08,840 --> 01:12:11,040
>> So make string1.

1610
01:12:11,040 --> 01:12:16,730
And now I run string1 in my terminal window.

1611
01:12:16,730 --> 01:12:19,180
It's waiting for input, so I'm going to type in, say, David.

1612
01:12:19,180 --> 01:12:20,080
Enter.

1613
01:12:20,080 --> 01:12:23,350
And now it prints D-A-V-I-D all on different lines because

1614
01:12:23,350 --> 01:12:24,430
notice what I'm doing.

1615
01:12:24,430 --> 01:12:27,510
I'm printing one character at a time.

1616
01:12:27,510 --> 01:12:29,100
Now we won't go into detail today on this.

1617
01:12:29,100 --> 01:12:31,610
But I deleted a moment ago this check here.

1618
01:12:31,610 --> 01:12:36,310
It turns out that if the user is misbehaving, adversarial, or just

1619
01:12:36,310 --> 01:12:41,780
confused, you can actually fail to give a string of some length.

1620
01:12:41,780 --> 01:12:43,640
If you hit the wrong key on the keyboard, you might give

1621
01:12:43,640 --> 01:12:44,390
no string at all.

1622
01:12:44,390 --> 01:12:47,790
Or if you're malicious, you might try to paste in a gigabyte's worth of an

1623
01:12:47,790 --> 01:12:49,380
essay to fill this string.

1624
01:12:49,380 --> 01:12:52,060
And if the computer runs out of memory, it turns out that we're going

1625
01:12:52,060 --> 01:12:54,310
to get back this special value called null.

1626
01:12:54,310 --> 01:12:57,550
So for now, just know that there's this special value called null that

1627
01:12:57,550 --> 01:13:01,000
will allow us to check when we're out of memory, among other things.

1628
01:13:01,000 --> 01:13:07,330
>> But if I open up now string2, notice one difference here.

1629
01:13:07,330 --> 01:13:09,760
Notice one difference here with string2.

1630
01:13:09,760 --> 01:13:13,260
With string2, this for loop is a little different.

1631
01:13:13,260 --> 01:13:16,350
Let me delete the nulls so that we can talk about those another time.

1632
01:13:16,350 --> 01:13:18,460
But what's different about the for loop this time?

1633
01:13:21,580 --> 01:13:23,160
And I can go back to the previous example.

1634
01:13:23,160 --> 01:13:24,800
So that's version two.

1635
01:13:24,800 --> 01:13:27,020
This is version one.

1636
01:13:27,020 --> 01:13:31,935
One, two, one two.

1637
01:13:35,030 --> 01:13:38,240
So the strlen call is where?

1638
01:13:38,240 --> 01:13:40,420
It's in the first part of the for loop.

1639
01:13:40,420 --> 01:13:43,060
Any thoughts as to why I'm doing this?

1640
01:13:43,060 --> 01:13:43,690
Yeah.

1641
01:13:43,690 --> 01:13:46,010
[INAUDIBLE]

1642
01:13:46,010 --> 01:13:47,630
DAVID J. MALAN: So we don't call the function every single time.

1643
01:13:47,630 --> 01:13:48,040
Exactly.

1644
01:13:48,040 --> 01:13:50,350
Recall from for loops that they're super simple once you sort of

1645
01:13:50,350 --> 01:13:52,180
understand that this is the initialization, the

1646
01:13:52,180 --> 01:13:53,330
condition, and the update.

1647
01:13:53,330 --> 01:13:55,430
The problem is that the condition happens on every

1648
01:13:55,430 --> 01:13:56,600
iteration of the loop.

1649
01:13:56,600 --> 01:13:59,930
And so in this example here, what is bad about the fact

1650
01:13:59,930 --> 01:14:03,500
that this is my condition?

1651
01:14:03,500 --> 01:14:05,920
You're calling strlen again and again and again.

1652
01:14:05,920 --> 01:14:08,990
But once I've typed in D-A-V-I-D, the length of that string is five.

1653
01:14:08,990 --> 01:14:11,560
And it's not going to change on every iteration of the loop because the

1654
01:14:11,560 --> 01:14:15,560
string is still D-A-V-I-D. So this is a hint at what's going to become an

1655
01:14:15,560 --> 01:14:19,650
increasingly important idea known as a design decision, where--just don't

1656
01:14:19,650 --> 01:14:21,640
make the computer do unnecessary work.

1657
01:14:21,640 --> 01:14:25,630
>> Now just as a sneak preview of pset 2, pset 2 in the standard edition is

1658
01:14:25,630 --> 01:14:28,850
going to challenge you to actually implement some number of ciphers, some

1659
01:14:28,850 --> 01:14:32,650
number of encryption algorithms, so that you can both encrypt and decrypt

1660
01:14:32,650 --> 01:14:35,530
secret messages, much like the one Ralphie there decoded.

1661
01:14:35,530 --> 01:14:38,720
In the hacker edition of pset 2, we're going to go a little further.

1662
01:14:38,720 --> 01:14:42,010
We're going to hand you a file from an actual computer system that contains a

1663
01:14:42,010 --> 01:14:45,690
whole bunch of usernames and actual encrypted passwords, and the challenge

1664
01:14:45,690 --> 01:14:49,110
for the hacker edition is going to be to crack those passwords and figure

1665
01:14:49,110 --> 01:14:53,060
out what cryptography or what secret was used to actually

1666
01:14:53,060 --> 01:14:55,080
generate those passwords.

1667
01:14:55,080 --> 01:14:58,360
And we're going to do this by using a new feature here of C that I'll give

1668
01:14:58,360 --> 01:15:02,200
you just a demo of, known as command-line arguments.

1669
01:15:02,200 --> 01:15:05,930
>> So it turns out, as some of you may have seen in section or in textbooks,

1670
01:15:05,930 --> 01:15:09,850
main does not always have to be void in parentheses.

1671
01:15:09,850 --> 01:15:14,060
It turns out that main can also be written like this, with two arguments,

1672
01:15:14,060 --> 01:15:19,690
argc and argv, where argc is the number of words that you type after

1673
01:15:19,690 --> 01:15:21,940
the program's name on your command line.

1674
01:15:21,940 --> 01:15:24,550
And argv is the actual words.

1675
01:15:24,550 --> 01:15:29,470
And as the square brackets there suggest, argv is apparently an array.

1676
01:15:29,470 --> 01:15:33,720
It's going to be a string after a string after a string in memory.

1677
01:15:33,720 --> 01:15:36,170
So what we're going to be able to do, starting with pset 2, is

1678
01:15:36,170 --> 01:15:37,310
something like this.

1679
01:15:37,310 --> 01:15:42,450
If I make argv1, which is an example we'll come back to on Monday, and run

1680
01:15:42,450 --> 01:15:45,180
it, notice that it doesn't seem to do anything yet.

1681
01:15:45,180 --> 01:15:47,050
It just prints out its own name.

1682
01:15:47,050 --> 01:15:53,220
But if I say goodbye class, notice that this program apparently iterates

1683
01:15:53,220 --> 01:15:57,030
over each of the words that were typed at the prompt.

1684
01:15:57,030 --> 01:16:02,050
And the means by which we will gain access to words that the user has

1685
01:16:02,050 --> 01:16:06,780
typed at the prompt is by changing main, starting this weekend, from int

1686
01:16:06,780 --> 01:16:10,710
main (void) to int main (argc, argv).

1687
01:16:10,710 --> 01:16:13,700
And thus will be born command line arguments.

1688
01:16:13,700 --> 01:16:17,210
And once you get really sophisticated at this, you'll be able to write

1689
01:16:17,210 --> 01:16:21,370
really trippy programs, such as this one here, which goes above and beyond

1690
01:16:21,370 --> 01:16:25,520
some of the functionality we've done thus far but all quite powerful.

1691
01:16:25,520 --> 01:16:27,330
>> So we'll leave this with this on the screen.

1692
01:16:27,330 --> 01:16:29,160
And we will see you on Monday.