[ Silence ]
>> Alright, welcome back!
This is the end of week 2 in CS50
and this is an excessive amount of what's called ASCII art,
people who have spent way too much
of their free time actually sketching out most of the scenes
from Star Wars entirely in their own ASCII character code.
So this is a bit of animation that's a bit
of an internet mean these days and goes around but we've linked
to on the course's website if you'd
like to watch the whole film later.
We thought we'd begin though not just with ASCII art
but with something a little sexier than that
that paints the picture for this week's
and next week's problem domain that of cryptography
and security more generally.
Some of you might have seen this actual film before,
one of my favorite excerpts of which is this one--
is this one-- that one too, is this one here.
>> Helmet, you fiend!
What's going on?
What are you doing to my daughter?
>> Permit me to introduce the brilliant,
young plastic surgeon, Dr. Phillip Schlotkin,
the greatest nose job man
in the entire universe and Beverly Hills.
>> Your highness?
>> Nose job?
I don't understand, she's already had a nose job.
It was a sweet 16 present.
>> No, it's not what you think.
It's much, much worse.
If you do not give me the combination to the air shield,
Dr. Schlotkin will give your daughter back her old nose.
>> No! Where did you get that?
>> Alright, I'll tell, I'll tell.
>> No, Daddy, no, you mustn't.
>> You're right, my dear.
I'll miss your new nose,
but I will not tell 'em the combination no matter what.
>> Very well, Dr. Schlotkin, do your worst.
>> My pleasure.
>> No! Wait!
Wait! I'll tell.
I'll tell.
>> I knew it would work.
Alright, give it to me.
>> The combination is one--
>> One.
>> Two.
>> Three.
>> Four.
>> Five.
>> So the combination is 1, 2, 3, 4, 5?
It's the stupidest combination I've ever heard in my life.
That's the kind of thing an idiot would have on his luggage!
>> Thank you, your highness.
>> What did you do?
>> I turned off the wall.
>> Clayton, you turned off the whole movie.
>> I must have pressed the wrong button.
>> Well, put it back on.
>> Yes, sir!
>> Put the movie back on.
>> Yes, sir!
>> Let's go, Arnold.
Come on, Gretchen.
Of course, you know, I'll still have to bill you for this.
[ Noise ]
>> Well, it worked, where's the key?
>> It works where we have the combination.
>> Great! Now, we can take every last breath
of fresh air from planet Druidia.
What's the combination?
>> 1, 2, 3, 4, 5.
>> 1, 2, 3, 4, 5?
>> Yes.
>> That's amazing!
I've got the same combination on my luggage.
[ Laughter ]
>> Prepare Spaceball 1 for immediate departure.
>> Yes, sir!
>> And change the combination on my luggage.
[ Music ]
[ Laughter ]
>> So if you like more of that,
that is a classic called Spaceballs.
We have another little classic for you in a little bit.
So you might laugh but odds are statistically,
some of you in this room has a password that's not all
that dissimilar from 1, 2, 3, 4,
5 and some of you might even have post-it notes back
on your desk.
So 1, 2, 3, 4, 5 is clearly insecure as a password.
One, 'cause its just so easy to guess even you if you're trying
to break into someone's account, you might try simple things
like that or the ever popular password
"Password" or something similar.
But in reality, what systems typically do even
if a password is weak like that,
they're actually store computer systems, things like this.
So if you've ever forgotten a password on a website or one
of Harvard's passwords, and you're told by some IT person
that they cannot in fact tell you your password
but you can change it,
that's generally algorithmically correct.
For security purposes, passwords are typically not stored
on computers in so-called Cleartext but rather
in ciphertext in some kind of encrypted fashion
that looks mostly like random nonsense.
But the reality is that that is the result
of applying some mathematical formulas
to the original password 1, 2, 3, 4, 5, their output
of which is something crazier-looking.
The idea being, if you see the crazy-looking thing,
it's not all that easy if it all possible to figure
out what the original password actually was.
So ensure when you create an account on some new websites,
Facebook, Google, any of these sites, they're storing
in a database your username and that's generally in the clear
or your email address but then your password is encrypted
but this seems to beg a--
beg a question the next time you log in, time number 2 or 3,
how in the world does Google or Facebook or Harvard know
that you've typed in the right username and password
if they too no longer know what your password is.
It seems like once you've encrypted the password,
you're kind of screwed 'cause you no longer remember what the
new one is if this is all you're storing, so what could you do?
What are some options?
Okay, so you could decrypt it,
so decrypting is just the opposite of encrypting.
The problem with decrypting it is
that if you're gonna decrypt something like this
on an automated fashion, well that means that the web server
or Harvard server itself needs to know how to decrypt it.
And generally encryption works by having some secret,
some secret password or special key
that only the website's owner knows.
So if you wanted the website like Google or Facebook
to automatically decrypt this and then compare your password.
Well, the implication is that-- then the website's password
or key with which to do that decryption has
to be stored somewhere in the server.
So this then implies that if some bad guy breaks
into the server, not only can he
or she steal the crazy-looking stuff like this,
which is mostly useless.
But if they have access now to the server,
they can steal also whatever trick you're using
to decrypt these things 'cause that's gotta be implemented
in Source Code, right?
Whether it's C or some other language,
so it's really not helping you
if you've actually encrypted this in that fashion.
Yeah?
[ Inaudible Question ]
>> Yeah, that's-- so that's a nice solution here.
So if the server is only remembering the ciphertext
and actually let me-- let me tweak my wording now,
though its very similar [inaudible] to encryption,
a better word for this would be a Hash Value, H-A-S-H,
and a hash value is generally the result
of encrypting something
and essentially throwing away the key though the mathematics
are a little different than that.
In other words, when you take a hash of some input,
the result is some hash value and statistically,
it should be impossible to reverse that,
so its one way encryption if you will.
So that's okay though because the Facebook
and Google are storing this as the-- the king's password,
well that's fine because the next time the king logs
in to this website, he types in his username, he types in 1, 2,
3, 4, 5, hits Enter, but then all the website has
to do is take another hash of that input that is run 1, 2, 3,
4, 5 to the same algorithm, the same mathematical formulas
and if the output of that process matches the output
of the original process, well, then you can assume that okay,
he must have typed in the exact same thing.
So this is why IT people can't tell you your password
but you can't continue logging in, they can't tell you what
because this encryption is one way,
it's taking the so-called hash of the original input.
And this is for security purposes because again
if it means that some bad guy steals all of this
from your server, physically steals your server,
breaks in over the internet, takes your whole database,
they might have your usernames and user's email addresses
which is perhaps bad for privacy
but at least they don't know your user's passwords
because those are at least encrypted.
And these days if you read in the mass media or see
on CNN some story about some website being hacked,
the likes of Sony or the
like where their user's databases are stolen
and you suddenly have to change your password, that is often--
because these companies amazingly aren't even doing
something simple like this.
There are numerous cases of companies,
actual legit companies storing user's passwords in the clear,
just as 1, 2, 3, 4, 5 or whatever it is that they typed
in and then you're screwed
if that database is actually compromised.
So towards semester's end when we introduce web programming
and my sequel in databases, we'll talk about these kinds
of issues because it's actually, amazingly, relatively easy
to protect yourself against this.
So that's our segway today and to security and now back to C.
So with problem set 1, if still tackling it,
know that office hours are brought tonight
and if you decide to cash in a late day,
that'll be tomorrow as well enroll.
Know that if you've been attending office hours and if
that issue is with wireless and whatnot,
know that Harvard is actually installing more access points
in all of these house dining halls for us over the next week
or so, so we'll have more capacity for everyone as well
as more cookies and the like.
Also, if you have any remaining questions with the Appliance,
there's definitely been some FAQ's about like cursors kind
of spinning, or windows not quite working,
realize we have solutions to all of these problems so do reach
out to us via help.cs50.net, catch me right after lecture
or email me directly in the worst case
if you're really pushing up against the deadline.
And then lastly, with the Appliance too,
the only real challenging issues with the Appliance is
if you have an older computer--
3, 4, 5, 6 years old or a fancy netbook that's
by design very limited in RAM in CPU cycles but we have a--
a new solution for that too for the next problem set and beyond
where you'll be able to connect
to our servers using a very minimalist program
on your computer, not necessarily the Appliance.
So we'll announce that once details are available,
so we should have solutions for all.
So here we are.
This little song last time which is kind
of itself a little tedious to both to recite
and also implement but once you actually have the notion of say,
a loop, which we did, you were able to implement this
with as we saw like a for loop.
>> So let me go back into this week's source code,
this was a file called beer1.c, so following along at home,
this is in source directory for lecture 2
and if I go into here, beer1.
So what do we now-- how did we go about implementing this?
Well, we have-- into main board, that's all it has,
at the very top here, how many bottles of beer will there be?
And then getint so that just gets a number from the user,
then recall we had a bit of error checking,
just make sure the user is not messing with us
and in this case, we don't repeatedly--
reprompt them for a number, we just say, "Ugh,
lets yell at them, sorry that makes no sense."
and return one.
And return one again as the notion
like of an error code, and exit code.
And then lastly, the actual implementation
of this song simply happened down here,
sing the annoying song.
So for int, I gets N, so-- if the user types in 99,
start counting at 99 on each iteration, subtract one from I
and that's what I minus minus denotes the opposite
of I plus plus, and then do this so long as I is greater
than zero, and on each iteration of this loop,
print this four-line stanza.
And the only thing that's kind of interesting here is this.
One, we have a placeholder for the integer D and we're plugging
in I as you can see over here,
we have another placeholder that's identical,
its just the English words have changed.
This is completely uninteresting 'cause it's just a string,
constant string that gets spit out every time.
And the interesting aspect here is just this,
'cause the song again is "99 bottles of beer on the wall,
99 bottles of beer, take one down, pass it around,
98 bottles of beer on the wall," so we need
to somehow dynamically insert I minus one but we can do
that very simply, arithmetically here so I minus one.
So the only worry here you might have or should have is--
alright, what's gonna happen on-- at the corner cases?
The recurring theme
in programming is you can get 98 cases perfectly right
with your code, but it doesn't really matter at the end
of the day if you screw up the first case or the last case.
And by name, those are typically called Corner Cases and so
as you start writing your own programs
and you start testing your programs by typing in values,
we'll program like this, if you type in 5 or 6 or 7 or 97,
odds are you're gonna get the same fundamental behavior.
But things get interesting if you choose those corner cases.
Type in one, type in zero, type in negative one, type in 100,
type in something distinct conceptually,
something that's closed to any boundaries you define
to actually see whether or not something breaks.
So in this version here, is there any risk of my printing
out "negative one bottles of beer on the wall"?
Will this ever print out "negative one bottles of beer
on the wall" in that last line of printf?
>> No.
>> Okay, so no, it won't, and why?
What's the simple protection I've put in place?
[ Inaudible Answers ]
>> Yeah, so I has to be greater
than zero according to this, right?
So as soon as I is not greater than zero, it is zero,
this loop is gonna stop executing which means the value
of I itself will never be zero inside of this loop.
The very last iteration will have a value of I equals one
and so that's safe 'cause we'll save one bottle of beer,
one bottle of beer, dot, dot, dot, zero bottles of beer
on the wall and we'll stop.
But of course, if we had done something like this,
so I'll go ahead and change this to greater than or equals,
I'll save the file, let me go down to my terminal window here
into the source directory, and I'll type "make beer1"
and now I'm gonna go ahead and run beer1 with--
lets say, the value 99, Enter.
Well, dramatic effect, if we now scroll
up to see what's actually there.
There we go.
There's the bug.
So now, we've introduced the bug
but we had it right the first time.
So again, recurring theme,
especially before submitting your PSet, test these kinds
of cases because the TF's are gonna be looking
for exactly these kinds of things.
We're not gonna test your program with 3 and 4 and 5 and 6
because most likely, those are all functionally equivalent.
It's the interesting, the negative numbers,
the zero numbers, the huge numbers that might ultimately be
of particular opportunity for your code to break.
Questions of any sorts?
Yeah.
>> How exactly do you implement the "return 1"?
>> How do you implement the "return 1"-- in "return 1" in--
implement it in what sense?
>> Like how do you use it to like jump back [inaudible]?
>> Good question, so how do you use "return 1"
to get another int from the user?
In short, you don't.
So this was a deliberate design decision in this program
that I'm not gonna use a while loop, or for loop,
or do-while loop to ask the user again and again.
If they don't give me what I ask for, which is a non-zero number
of bottles, then I'm just gonna quit immediately
because it's not a fun song to sing, but we could've done this
with a do-while loop like in the PSets.
Yeah.
[ Inaudible Question ]
>> So how do you use this number "return zero"-- "return 1"?
So short answer, we're not going to yet, but starting next week,
we're gonna introduce something called a Debugger
which is a separate tool from the compiler
that actually lets you figure out what's going on inside
of the computer and even lets you step you
through your code line by line by line,
and for that to another's the return code is gonna be useful.
For now, since sort of thing just take it on faith
because it will soon become useful.
So we now have beer2,
so we wanna do something a little better here
and introduce kind of a big topic that frankly you might see
in a textbook but no one ever really says it in--
in person which is that of hierarchical decomposition.
So what is this actually mean and who cares?
So let me scroll down now to actually let me go with--
let's go with beer4.c. Yeah, this is--
this is the one I want.
Okay, so in programming,
you will often find yourself doing something a little
repeatedly like if you yourself have been writing programs
where you're kind of stealing code you wrote a few minutes ago
on some other line and pasting it, pasting it, and pasting it,
that's probably gonna be an opportunity
for hierarchical decomposition
which just means write your own function.
So thus far, we've been using main, which we have to,
to write a program from the get go, you've been using printf
which someone else wrote.
You've been using getint which someone else wrote,
so you haven't really most likely written your own
functions and yet this is actually relatively easy
and its not even new syntax, we just kind
of mimic the same syntax we've seen
with getint and printf, and main.
So let's take a look at this version here.
So if I zoom in here, notice at the very top of this file,
I have again the same code at the top,
how many bottles of beer will it be?
I get an int from the user, I quit immediately
by returning one if they don't cooperate,
and then I have this two-liner which is kind of interesting
for a couple of reasons.
So one, I'm-- have a while loop now, why?
It's just a little different from a for loop,
I decided to do this aesthetically.
But what's interesting too is I've got N minus minus,
we'll come back to that, but more interestingly all
of a sudden there's a chorus function that why--
apparently, I could've been using all this time to print
out the chorus, that four-line stanza of this song.
It's as though I've now outsourced
to a little black box called Chorus that itself is a function
that someone else wrote and that function's purpose in life is
to sing the song for me so I don't have
to write these lines myself.
Now, in reality, someone did have to write those lines
and in reality it was me.
And if you scroll down to the bottom of this file now,
notice the following, so this is familiar syntax even though
we've not used this too many times this far,
the things with the stars, that's just a comment.
Slash star, then some stuff, then star slash,
that's a multiline comment and then that's just my note
to myself, sings about specified number of bottles.
Then below that,
I have something that's similar syntactically
but still a bit new conceptually, I've got void
and then the word Chorus and then int B. And then inside
of this, I've got a couple of new features.
I have this new syntax which we'll come to in a moment,
so let's ignore anything we don't quite understand yet,
and focus only on this.
Well, this is kind of interesting, sing verses.
So what am I doing that's different here?
So I still have my percent D but what new format--
what format code is now obviously new?
So percent S, so I'm actually fixing a couple of problems now
and are finding this code
with a more sophisticated implementation.
Percent D is still gonna be the value
of the number of bottles of beer.
Percent S is gonna be which of two words?
If any of you just take a guess.
[ Inaudible Answer ]
>> It's gonna be bottle or bottles so I'm fixing
that grammar problem that I admitted to on Monday,
so we'll come back to how that's working in just a moment.
But B, what happened to I?
Well, this is the fundamentally interesting aspect
of actually writing your own functions.
Notice that at the top of this function,
I've specified what kind
of input this function called Chorus takes
and it's pretty obvious that it takes an int.
And just because I'm gonna be talking about bottles,
I decided that B is a reasonable name for the variable to give
to the input to this function.
Now, notice how I'm using chorus, if I go up here
and actually let me simplify this just for a moment.
I'm gonna change this code just for the moment to I minus minus
and then this closed brace here.
So notice on every iteration of this while loop,
if I start by typing in 99 for N,
what value apparently gets passed inside the parenthesis
to this function called chorus?
This is 99, right?
Whatever values in N is what--
gets handed to Chorus as an input.
Alright, so now let me scroll down to the bottom here.
Well, just because chorus takes an int, doesn't mean it has
to take an int whose name is identical
to what the original value was.
I can name it anything I want
and I decided stylistically B makes sense 'cause I'm talking
about bottles.
So what's gonna happen then is when I call the chorus function
up in main by just writing chorus, open parenthesis, N,
close parenthesis, semicolon.
>> What's gonna happen is that chorus is gonna be executed
and be handed as input that number, 99, and it's getting--
get its own copy of 99, its own 32 bits,
its own 4 bytes somewhere in RAM
and they're just gonna be called B
in the context of this function.
Now, what am I doing with B?
Well, lets scroll down to the printfs while I'm apparently
plugging in for percent D, the value B, I'm plugging
in for the value-- percent D, the value B again.
And then in the very last line, I'm plugging
in for percent D, B minus one.
So functionally, this is equivalent.
All I've done is kind of outsourced now the singing
of the song to someone other than main
and that someone is a new function called Chorus.
So now what about S2 and S1?
Well, let me rewrite something quickly as this,
if B equals equals one, then I'm gonna do this, string 1 S2.
I'm gonna say, "S1 gets bottle else S1 gets bottles,"
and then I'm gonna do a little quick copy paste here,
and actually let me clean this up.
I did this on the fly S2, and I'm gonna do S1 up here,
and I'm gonna say, "If a bottle equals 2, then I'm going to say,
S2 gets bottle bottles."
Alright, so what is going on here?
So first, let's ignore the goal and focus only on the syntax.
Well, what does it mean if I say string S1 in a program?
Just translate that to English.
[ Inaudible Answer ]
>> Okay, not quite initialized but declare a variable
of type string and call it S1.
This is identical conceptually
to doing something like int N semicolon.
That means declare an integer, call it N and that's it
because there's no equal sign.
Don't do anything else with it yet.
Now, a string recall is just a word, a phrase, a sentence,
a paragraph at some number of characters, so string S1 means,
okay, prepare to get me a string
and that string is gonna be called S1.
So what am I doing here?
Well, if the number of bottles past N equals one,
I want this string to represent bottle in the singular,
else if B is anything else, 2, 3, 4, 5, whatever,
then I want it to be bottles.
So it seems like now I'm using just a branching condition
to fix some grammar and then I actually have S2 down here
but we'll see why in just a moment.
So let me scroll down here and see what I'm doing.
So printf, percent D, so if I type in 99, that goes there.
If I type in 99, what's gonna go here for percent S
if what I'm putting in there is S1.
Bottles, right?
So again, I'm just creating a variable on the fly here,
string S1, and if B equals equals one, make S1 be bottle
in the singular, else make S1 bottles in the plural
and so that's what gets plugged in there.
Now, why S2?
I'm gonna wave my hand at this detail just for now
but it's simply because in the very last line
of the song again, I might need
to change the pluralization, right?
It might go from bottle to bottles
because it might be one bottle to zero bottles,
or it might be two bottles to one bottle.
And so you need to have two different words.
One might be singular, one might plural, or vice versa.
Or they might both be plural
so that's simply why I have S1 and S2.
Now, in terms of conditions--
like we've done this before, right?
If this else that, and just so you've seen new syntax,
it turns out that syntactically, these two lines
at the very top are what we would call a very elegant one
line implementation of that same idea.
By no means strictly required doing it the way I did here
with the indentation and whatnot is perfectly fine
but let's just see what this is.
This is the only-- this is the only funky line
of code we're gonna see for awhile that has multiple pieces
of punctuation in the middle of it, so what's going on here?
Well, let's do the first part on the left.
String S1 means give me a string, call it S1, that's it.
The equal sign means put some value in there,
so the last question to ask ourselves is,
what value do you wanna put there?
Well, it turns out that this expression right here is
identical to this, it's just a slightly more succinct,
there's a-- a prettier way of expressing that same idea.
What this means is that if B equals equals one,
the word after the question mark is gonna plopped into S1.
Else, so this colon represent else now, else bottles
in the plural is gonna get plopped into S1.
So in other words, it collapses all five of these lines
into one line that once you know the syntax,
its just a little easier to swallow,
just a little easier to read.
But let me point out one thing.
I intentionally did this, string S1, why?
If you think back to Monday did I not do this?
Its-- if I declare as variable, in this case a string inside
of a condition that's pretty much equivalent recall
to writing this even though the curly braces are not necessary
if its just one line.
But conceptually, its equivalent to this, and what was the rule
of thumb we discussed on Monday when it comes to variables?
Scope. They're only in scope.
They only exist inside of the confines
of the most recent curly braces even
if those curly braces have been omitted just 'cause its one line
of code for convenience.
Those variables only exist inside of those curly braces
which means I'm kind of out of luck
if I wanna use S1 down here.
And so the solution is simply make sure
that the strings are declared outside of those conditions.
So this again is a question of scope.
So in short, we've solved a few problems here all at once.
So on the one hand with chorus, we declared our own function,
it takes input and now I don't have
to clutter up my main function.
If I have this well-defined task, sing the chorus of a song,
that's a candidate for hierarchical decomposition,
it just means factor it out.
Create a little black box, give it a user-friendly name
like chorus, define it as taking some input
like an integer call it whatever you want,
B and then it does something.
And the only last question to-- ask about the syntax here is,
what does it mean if Chorus is prefixed with this word Void?
So it-- yeah?
[ Inaudible Answer ]
>> So it-- not input, so it does take input
because the input is always defined between the parenthesis,
so what's the opposite of input?
[ Inaudible Answer ]
>> So output, so this means chorus does not have
any outputs.
Now, this feels like a bit of a lie
because clearly the song is gonna have some kind
of output, what's it gonna do?
Well, it's gonna print the whole bunch of stuff
to the screen based on this printf lines,
but this is a different type of output.
Recall that you can print something to the screen
but you can also hand the user back a value.
For instance, what's the function you've been using
for a week or more now that return some value?
[ Inaudible Answer ]
>> So getints, right?
Getints, get string, get double, in those cases,
the function getint, it doesn't just print it out on the screen
and leave it for you, the human, to figure out what it was,
it returns it so to speak so that you can put it to the right
of an equal sign so that you can assign its return value
to some variable.
Well, same idea here, chorus though, is only purpose
in life is to have these aesthetic side effects
of printing something to the screen,
it doesn't actually hand the user back any value,
any sentence, any string, whatsoever, it just prints
and so its return type is void.
And we'll see this again and again in more clarity, yeah.
[ Inaudible Question ]
>> Oh, so there is, we just scrolled beyond it.
So if I scroll back up, recall that we begin the story
with main just as usual.
Yeah.
>> If you declare a-- a variable in main,
will it still be declared in another function of the main?
>> Really good question, if you declare a variable in main,
will it be accessible to another function like chorus?
What do you think?
>> No.
>> So no, and again, you can fall back on the same rule
of thumb, variables only exist
within the confines of the curly braces.
So main has its own curly braces
at the very start and the very end.
So any variables in there are not in fact accessible
by a function like chorus.
And let me point out one other detail here before we can put
to rest this singing song example.
There's one piece of new stuff at the top of this file,
so besides all of the comments up at the top of the file,
besides my use of include CS50.h and standard IO.h,
there's this thing whose word is gonna be called generally a
function prototype.
Well, what does this mean?
So C is kind of stupid, right?
It's an older language, the compilers for it are fairly--
even though they've been updated over the years,
they were very simplistic in terms of their design early on
and what does that mean?
It means that the compiler, if you don't tell it in advance
that a function exists like chorus, and it encounters
that word somewhere
in the program before its actually seeing your
implementation of that function, its going to yell at you.
It's gonna trigger some kind of error.
In other words, let me do this, I'm gonna undo all
of the changes I've done in this example just
so we know I didn't screw it up
and its back in its pristine form.
And we'll come back another time to this syntax
of doing the minus minus inside of the parenthesis there.
I'm gonna go up to the top here,
I'm gonna expand my terminal window and I'm gonna go ahead
and compile this thing which again was beer4.
So make beer4, I'm gonna go ahead and run beer4
and I'll type in just two bottles to keep it short
and simple, that seems to work.
No weird side effects.
So now, let me break it.
Let me accidentally delete this thing
that we're calling a function prototype
and just start typing main.
And now, notice if I scroll down further, main's there
and chorus is still there.
So in theory, I have all the building blocks I need,
I've dragged all of my puzzle pieces to the stage.
>> But again, C is not quite as smart as scratch.
C cares about the order in which you do things.
So if I now recompile this thing with make beer4, Enter,
a whole lot of stuff just broke
and this is the most telling line
and you might have seen this yourself over time,
implicit declaration of function, in this case chorus.
Has anyone seen a similarly sounding message,
do you remember what the solution was the past week?
[ Inaudible Answer ]
>> Include?
Include the header file, right?
If you've ever seen this message thus far,
or you see this message in the future, implicit declaration
of function just means you use the function,
in this case chorus but you didn't tell the compiler what it
looks like, what its return value so to speak?
And what's its input?
What's its output and what's its input?
And you kinda did but you told the compiler too late.
You put your function all the way at the bottom of the file
so as soon as the compiler started reading your program top
to bottom, left to right,
it encountered this special new word, Chorus,
but you've never told it that there's a chorus function
in existence before so it throws this error.
So just think intuitively,
what's the quickest fix for this perhaps?
And the answer is not function prototype.
Yeah.
>> Move the [inaudible] when you make the function
up above the main.
>> That sounds perfectly reasonable, right?
So if the problem is, I'm declaring chorus too late,
I'm teaching the compiler about it too late 'cause I'm using it
in main, alright, well let's just relocate it
to the top of my file.
So now, chorus is at the top, main is at the bottom,
let me go ahead and zoom in now and lets redo this, make beer1--
make beer4 when that actually did fix it.
So that is indeed a very reasonable solution,
but its probably not the best because you can definitely--
once your programs gets more complex, you can definitely come
up with scenarios where X has to call Y but Y might call X
so you might get into this--
possibly this circular relationships
where its just impossible to put one above the other logically.
And also it's kind of nice as a matter of good style
to just always put main at the very top of your program.
Because if you open a program that you wrote
or someone else wrote for the very first time, you don't care
about a function called Chorus or anything else,
you wanna see what does this program do, and the answer
to that is almost always gonna lie in main.
So ideally, we wanna leave chorus where it was, below main,
but it turns out the simple solution then is just
to tell the compiler about this function before you actually
implement it an you just can do this with a one-liner.
You specify what its output.
In this case void, what's its name?
Chorus. What's its input?
Int B. So in other words, you literally copy
and paste the first line or two of your function
and just put a semicolon at the end.
You don't do open curly brace.
You don't start writing your function.
You just do this one-liner and notice
that is now identical to what's down here.
Now, why this?
This is just a matter of convention.
It is perfectly legitimate to write your functions all
on one line like this but if you look back
at the CS50 style guide,
you'll see that we discussed why this is actually useful.
Long story short, if you're using a text editor
or like some kind of programming tool and you wanna search
where in your file you've actually implemented a function
like chorus, there are usually little tricks
in the find dialogue to say start searching at the front
of a line, the start of a line.
So the fact that if you adopt this convention
of putting the function name all the way to the left,
it just means you can find it more easily
when your files get big but it's just a convenience,
nothing more than that.
Alright, so we'll come back to some
of these syntactic features, but any questions on the concept
of writing your own function and this notion of declaring it
with the so-called prototype?
Yeah.
[ Inaudible Question ]
>> Good question.
Why do you have to tell the compiler that it does
or doesn't have an output?
Can't you infer that from the code?
You could infer it some of the time but the problem is
that if you just analyze a prog--
a function that you were in, you could have an if condition,
and else if, and else if,
and it could actually return different things,
maybe not even at all.
And so the idea of proactively telling the compiler,
this will-- no matter what return this data type is a
commitment to then make to adhering to certain conventions.
So in short it-- it improves the probability
of correctness, among other things.
Any other questions?
Alright, so let's try to generalize this a little bit.
So we just wrote a function,
were taught functions have return values.
Return values are just-- it's just the buzz word for output,
but we can run into problems with this.
Again, related to scope.
Let's actually see a more concrete example
where scope kind of breaks things for us with regard
to these things called Local Variables.
So this is a buggy program, this is buggy3
and this is among the source code here,
in lectures two source.
If i open up buggy3, we'll see an attempt
to actually swap two variables.
So let's ignore the top of the file.
Let's just look at main as is generally most useful.
It looks like main declares an int called X assigns it one,
another int called Y assigns it two,
and then it prints out their values.
It then says printing-- sorry, then says swapping dot, dot,
dot, then it calls a function called Swap
who takes two arguments.
So it's a little different syntactically
but you just separate the arguments with commas.
Then it claims on the screen to say, "Swapped,
exclamation point" and then it reprints X and Y.
So this program's pretty simple, at least in terms
of what we've learned thus far.
The only new thing is this use
of apparently a function called Swap which is not built in.
I wrote it elsewhere in the program
so let's see if it works.
It's not going to.
So let's go into lectures to source.
I'm gonna go ahead and compile now, make buggy3, Enter,
so compiles okay, so that's promising.
Now, buggy3, Enter-- X is one, Y is two, swapping, swaps X is 1,
Y is 2, feels like this is definitely broken.
So lets see, maybe I did something stupid
like I left out the prototype.
Well, no, so that's there, I did include the prototype
and I should know that I did this correctly 'cause GCC did
not yell at me with implicit declaration of functions,
so syntactically, this program is right.
Apparently, Swap returns nothing, but it takes an int,
takes another int, and calls them A and B respectively.
So let's now scroll down and see how I implemented this.
Well, it's apparently just three lines of codes,
so swap has no output.
It takes two inputs, A and B, each of them is an int,
and now conceptually, does this sound correct?
So it actually is, so here's one gotcha first,
if you've got a value-- let's call it A,
and another value call it B, how do you swap them?
Well, if you think about it, you--
you sort of visually, you do this, right?
But you can't quite do that in a computer
because if you say A gets B, and then B gets A,
well what value is in both A and B?
[ Inaudible Answer ]
>> So, it's B, right?
Order of operations if on the first line you put the value
of B in A, and then you put the value of A in B, well that means
that B's value whatever it is,
is now in both of those variables.
So what's the solution?
Well, you introduce, we'll call it Temporary Variable.
Now, usually TMP would be a silly name for a variable
but if it is a temporary variable,
it's quite reasonable here.
So the solution is to remember what A is by storing its value
in an int, then updating the value of A and putting
in it the value of B. And now at this point
in the story, what value is in A?
Well, the value of B. What value's in tmp?
The original value of A and so now we can put inside of B, tmp,
which is equivalent to A. So we just need a third line of code.
Now, as an aside, especially for those of you interested
in Hacker Editions, there actually is a way in C code
to do this where you swap two variables simultaneously
without using any temporary storage phase,
its kind of nice magician's trick but more
on that perhaps next week.
But for now, this code feels correct, right?
I've got A and B. I put A in a temporary variable.
I changed B-- I put B in A, and then I put this guy here, right?
So that logically feels correct and in fact
at the very last line here where my cursor currently is,
A and B have, yes, been swapped.
But we just saw, when I run this program that X
and Y are not swapped even though I'm passing X
and Y to this function.
So where do things break?
>> Yeah, in back.
Oh, sure, you.
[ Inaudible Answer ]
>> Okay, so it's not assigning the answers back
out of the function somehow, okay, and so that's true,
and what other point can be made too here?
Yeah.
[ Inaudible Answer ]
>> Okay, so maybe the values X and Y are getting messed
up in some way when being passed in.
So messed up isn't quite what I'd say but there is another--
there's a verb here that would apply, they're being copied
into the swap function.
So recall earlier and I said it briefly
in our previous beer example that when you call a function,
and you just specify the input with a variable name,
you get the value but you get a copy of that value.
So at this moment in time when this program is executing,
there are now four variables--
actually five variables in existence
in this program right now.
There's X and Y, and those live inside of main, there's also A
and B, and also tmp, T-M-P.
So five separate integers, that's five separate chunks
of 32 bits somewhere in the computer's memory,
and inside of X is the number one apparently if you think back
to the-- how we started.
So inside of X is the number one.
Inside of-- what other variable is also apparently the number
one-- initially-- before swap executes.
So also, the number one, Y has the value two,
as soon as we call Swap, B has the value 2,
but then when you finish executing swap before it
actually finishes, so if we get conceptually right
to where my cursor is here before its all done, X is one,
Y is two, A is two and B is one.
>> The problem is that the-- your goal is to swap X and Y,
and all we've done is swap A and B. So it seems
to be a fundamental problem that when you pass inputs
to a function, you're actually passing copies of them in.
Ad the buzz word here is you're passing them by value.
Now, those of you with prior programming backgrounds know
that in Java, you actually don't run into this at least
if you're using objects and we can fix this
in C. Fast forwarding to a couple weeks from now,
we'll introduce the notion of pointers
and low level memory addresses.
But for now, let's just assume we've run up against the wall.
Right now, when you have what are called Local Variables,
which X and Y are, anytime you have a variable inside
of a function, its called a Local Variable,
its kind of for self-explanatory reasons,
its local to that function.
That function cannot-- that variable cannot be accessed
in some other function because A and B, meanwhile,
we keep calling them arguments or parameters,
but they're also just local variables.
They exist only inside of swap.
So at this point then, there's two variables in main,
there's three in swap, and those guys,
even though they might share some values,
they're copies of those values.
And we can actually see this as follows.
So this is a little picture that we might paint
of a computer's memory.
So if you think about now your own computer,
you've got like a gigabyte of RAM, 2 gigabytes, 4 gigabytes,
something like that, let's just assume that your RAM looks
like a rectangle and RAM is, again, 1 gigabyte, 2,
4 gigabytes, and bytes is the keyword there.
If you have a total number of something, you can now--
you can number those things, so this thing at the bottom left,
this might be byte number zero, if I move my hand over a little,
that's byte1, byte 2, byte 3, byte 4,
then I go up to the next road, that's byte 5, 6, 7, and 8.
In short, we could assign like a billion unique numbers
to every little square portion of this picture
if this whole rectangle represents my computer's memory.
So what happens when you actually run a program?
Well, when you run a program,
what function gets executed by default?
Just main, right?
So main gets executed by default,
main might have some local variables, where do they end up?
They end up at the very beginning
of your computer's memory, lets say.
There's a little bit of a simplification, but they'll end
up at the bottom left hand corner there, inside of the--
the rows labeled main.
Now, main can take arguments.
Thus far, we've been writing int main void.
So right now, there actually are no inputs to main
but we'll get there, main's locals means all
of main's local variables might end up there.
But what if main calls a function like printf, or getint,
or in this case swap, where does it end up?
Well, where to swap and all of its local variables end up?
One layer higher, literally, in RAM, if something starts here,
the next function ends up here,
the next function's variables end up here, and here,
and here, and here, and here.
So where we say Foo, and foo incidentally is like,
a mathematician might say XYZ, computer scientist say, "foo,
bar, baz, quux" and then there's some other crazy words,
just when you need a verbal placeholder,
foo is local variables end up on top of mains.
And guess what?
If foo calls its own function, where does it end up?
In memory here, and here, and here.
So again, if one of today's
and next week's themes are security turns
out that this is actually a brilliant way
of hacking a computer.
If you have the ability to call a function
that calls a function, that calls a function,
that calls a function, if you do this enough times,
you can actually start to change the contents
of a computer's memory potentially in dangerous places.
And so if you ever heard of a--
a word like a buffer overflow exploits or more generally,
a website being hacked, to this day,
it is still incredibly common to hack into computers
by passing them bigger strings or bigger numbers
than they were expecting.
And what happens is those strings or numbers start filling
up space in your computer's RAM at the bottom left.
But it gets so big that it overwrites something important.
And for today's purposes,
that's bad because if you overwrite something important,
you can actually trick the computer
into executing almost anything you want, but it derives
from this problem here.
So just to hammer this home, who cares about these rectangles
and this depiction of memory?
Pictorially now, if you have X and Y, and they live inside
of main, just graphically, they are not accessible to foo
and vice versa because they're ending
up in different locations in memory.
So let's actually go back here and try fixing this.
So I could fix this
by introducing not a local variable, but a global variable,
so let's scroll down here.
The only thing different now in this version of swap is
that I'm actually going to-- sorry, not of swap,
in this program, I'm gonna try
to solve this problem in this way.
So lets scroll down here and lets simplify this rather
than involve 2 variables, X and Y and swap, lets simplify.
Let's instead change the story to a function called Increment,
and increment's purpose in life is just to increment a variable.
So let's do-- let me change this real fast.
Let me break this and then we'll fix this.
So look at main here, I've got an int X gets 1,
I then claim initialize, 'cause I've initialized it to one.
X is now one incrementing dot, dot, dot,
I call the increment function not even passing
in a value here, incremented and then I claim at some new value.
So if I look now at increment and I try to do this,
will this work or not work?
So no, and what's the short answer?
I'm trying to do X plus plus inside of increment, but--
[ Inaudible Remark ]
>> So it's a void function which means it has no output,
it doesn't return anything but more were recently,
what else is also buggy here?
Yeah.
[ Inaudible Remark ]
>> Exactly.
X-- this X was not declared inside of increment,
it was declared inside of main
which means you don't have the right
to actually do plus plus here and you can't even compile this.
If we were on make on this, it will just yell at us
that X is not initialized because it's not in scope.
So how can we fix this?
Well, you know what?
Rather than make X local, let me try another little trick
and scroll up here and let me actually declare my int outside
of this whole program.
And if I declare the int X at the very top here,
now there are actually aren't curly braces anymore 'cause I'm
outside the huge made file, but is X--
do you think in scope or not in scope now with regard
to the rest of this file and all of its functions?
So it actually is in scope.
So just as before where the quick fix was just copy
and paste or who you-- whole function put it at the very top,
here too, we can kind of fix this
by just putting our variables at the very top of our program
and now both main and increment
and any other function here can execute them.
Alright, is this a good thing, bad thing?
In this case, it actually solves the problem very reasonably
and it gets the job done.
But what's maybe a downside
of these things now called Global Variables.
Global in the sense that they're not inside of functions,
they're inside of files.
Someone about over here, any-- alright, over here, there we go.
[ Inaudible Question ]
>> Good. Yeah, so if you start thinking ahead
and granted this is a little hard to do
when we're just implementing pennies this far right now
and similarly short programs realize
that this is also a solution
that really doesn't scale very well.
One, before long, we'll be writing more sophisticated
programs that have more variables than just one.
and so again, as a matter of good design,
if you just start plopping all of your variables at the top
of your file as globals, you totally defeat the purpose
of trying to declare your variables as close as possible
to where you actually use them which lends themselves
to readability and its just easier
to understand what your program is doing
if you do everything really only when you want to use something.
If you're just littering the top of your file
with these global variables,
long story short this does not scale well.
And in fact, once you start using other people's code,
libraries or API's like I referred to a week or so ago,
things like even CS50s data APIs for course catalog data
and shuttle data and dining hall data and the like.
Once you start using code that other people have written,
my god, what if you use a variable called X
and that other person uses a variable called X, right?
What if the person who implemented printf
in a file called standard IO.h, and another file standard IO.C,
what if he or she also decided that he
or she needed a variable called X?
So he or she put X at the top of their file,
now you have collisions and this suggest
that now you can't even use the variable X
if you wanna use printf.
So again, long story short, putting stuff at the very top
of your file in terms of variables tends not
to be the right solution, so they exist and we'll see cases
where global variables are compelling
but thus far this is not, in fact, the right solution.
Well, lets see if we can now completely abuse some
of these ideas and see what bad things can happen.
So I'm gonna go ahead and save this as--
lets say, "bad.c" and I'm gonna go ahead and zoom in here.
I'm gonna do something like include, lets say, standard IO.h
and I'm gonna have int main void.
And then here I'm gonna do something,
I don't know what yet.
I'm gonna then have a function called void bad can be the same
thing as the file.
Is it gonna take any input?
No, not even gonna take any input, so I'll say void
but I could have a take input.
And now here, I'm gonna say, "printf-- " oh, you know what?
I will have a take input.
Lets have a take an integer N and what I'm gonna have it print
out is that value of N followed by a new line character
with percent D. So all this function does
and doesn't seem all that bad thus far, all it does it prints
out the value of its argument.
>> So how do I call this?
Well, let's do int N gets-- let's say, zero,
lets call bad of N and that's it.
So what will this program print when I run it?
[ Inaudible Answers ]
>> So I think it will just print zero, right?
Quick-- super quick sanity check,
so if I do make bad-- oh my god!
So many mistakes.
[ Inaudible Remarks ]
>> Alright, good.
So when you see lots of mistakes,
just listen to everyone-- they'll be yelling at you
and fix it this way, so it double quotes,
hopefully that's fixed now--
okay, no, what did I do wrong still?
[ Inaudible Answer ]
>> Yeah, exactly.
I simply haven't declared bad, so fix one could be move it
to the top of the file but again better practice is leave main
at the top, and instead, what do I type
at the very top of the file?
[ Inaudible Answers ]
>> Void bad int and the same thing but semicolon, alright?
So now let's see if I fixed this.
Let me go back to the bottom, I'll zoom in at the bottom.
Let me rerun make bad, okay, that's good-- bad, okay.
So we're on our way.
Not an interesting program, but now suppose you do this,
interesting thing here is
that main is calling bad but that's it.
I could really create an interesting quandary here
and perhaps send a message of--
along the lines of, "don't do this".
If I did something like this, what if I did bad in here
and I'd passed in first N gets N plus 1, or keep it simple,
N plus plus and passing bad here.
So, what's gonna happen?
This should hopefully start messing with your minds,
so main gets called, we initialize N to zero,
we then pass that into Bad.
Now, quick sanity check, is this a coincidence or necessary
that I also call the input to bad N?
[ Inaudible Answers ]
>> So it's not necessary,
this is actually just a coincidence, why?
This is actually maybe confusing so I'll change it,
let me change it to I, then I'll change this to I,
and I'll change this to I because again I
or whatever I call it is gonna be a copy of N.
But it doesn't matter if their named the same 'cause they're
in different scope so you can reuse names of variables
if you want in this way.
So okay, so main initializes N to zero, passes in zero to bad,
bad takes as input that value zero, and it prints out zero,
then I gets incremented from zero to one
and then bad gets called with what input?
[ Inaudible Answer ]
>> One. So what happens next?
We don't go back to main yet, instead bad gets called again.
So if you're kind of thinking through this linearly,
we're chugging along here, here, here, here,
then we do this again, and call bad again.
So at this point, bad takes as input one, prints out one
and then does what to I?
Plus plus, so it becomes two, then bad prints out two,
and then three, and then four
and why is this kind of a problem?
[ Inaudible Answers ]
>> Right, so it never stops, right?
And you might have done this accidentally
with infinite loops already and that's kind of bad
if you have an infinite loop
that never stops 'cause you messed up your condition.
But now if you think about what's going on inside
of the computer's memory, its kind of worse
when every time you call a function,
it turns out its using some amount of memory.
In fact, its using, lets say a--
a slivers worth of RAM in your computer,
but every time you call a function, it goes on top
of the previous function that was called,
on top, on top, on top.
So even though bad is the same thing, every time you call it,
you get a distinct sliver
of memory again and again and again.
And so if you kind of think through this,
if you do this infinitely long, what's gonna happen?
Well, you're gonna overflow your computer's RAM
and this is just the bottom of your RAM.
If we actually redraw this and actually acknowledge
that you only have a finite amount of memory,
you've got a gigabyte or 2 gigabytes,
you do not have an infinite amount of RAM.
Well, there's gotta be something, probably the very top
of that and indeed there is.
If you think again about your computer's memory
as this big rectangle, the thing
at the bottom now were called the Stack.
Every time you call a function, you just keep stacking more
and more memory on top of the stack but it turns
out at the very top of your computer's memory,
there's what's called the Text Segment.
And text is just a fancy way of saying, that's the zeroes
and ones that represent your actual compiled program.
In order for them to run when you double click them
or type their command at the prompt, they get loaded
into memory, so if nothing else your own program is somewhere
there in RAM and if you keep calling bad, bad, bad, bad, bad,
bad, what's gonna happen?
You're gonna literally overwrite other stuff with the zeroes
and ones that represents bad's stack frame,
its local variables.
He only has one local variable, I, and that's 32 bits.
So frankly, this is gonna take awhile to get all the way
up to the very top if we're only doing it 32 bits at a time,
but if we're doing it infinitely,
we'll get there eventually
and you're gonna start overwriting potentially
important stuff and this isn't quite how a bad guy would do it
but its the same idea whereby you can then change what code is
inside your own program and trick the program
into actually chugging something bad
like disable the serial number of prompt,
or disable the password prompt, or give me administrator access.
So I've compiled--
let's recompile this now
that I've introduced this infinite loop by of calling bad,
bad, bad, bad, bad, and run this.
And lets go ahead, went a little long,
but lets take our two-minute break now, leave this up
and running and we'll come back and see
if this is actually broken, no, okay, breaks over.
No, lets still take our two-minute break then we'll
come back.
[ Pause ]
>> So in short, a couple take aways thus far,
so we implemented the capability
of implementing our own functions and syntactically,
it's really no different from using main, using getint
and the like, but we did see one, gotcha,
whereby if you use a function you wrote
and that function's written at the bottom or just elsewhere
in your file, you do have to declare it so to speak
at the very top and the jargon there is you give it a function
prototype, you declare it at the very top
of your file ending it with a semicolon.
So then we looked at again this issue of scope.
An issue of scope refers to where variables can be used
and cannot be used, and if you declare a variable inside
of a function, pass it to another function,
that function gets a copy of it.
And you can't access the other guy's copy back and forth
and that is because of this little picture that we started
to draw here where your memory is given--
your program is given different slivers
for every individual function.
Now, if you take this to the extreme
and call some function an infinite number of times,
eventually you're gonna hit some kind of ceiling.
And that ceiling among other things has your own program
in it, your own program zeroes and ones that were the result
of GCC compiling them.
And what eventually happens is usually something like this,
odds are this won't really happen
to you this week unless you're doing the Hacker Edition
of P set 1, but this will happen to everyone in this room
over the next couple of weeks.
Segmentation fault simply refers to the fact that you started
in some segment at the bottom of your memory
and you overstepped the bounds of someone else's segments,
some other important chunk of memory.
So this is actually a good thing and that the computer is trying
to prevent bad things from happening.
But as we'll see we can actually,
with finer grain control, take advantage
of a computer's memory.
And again to be clear,
the context here might be malicious behavior,
not just compromising a server but frankly a common pastime
on the internet is to create cracks for programs whereby
when you wanna install Microsoft Word or Photoshop or something
like that, you're usually prompted
for your registration code or product code,
something like that, that in theory only you have.
Well, how are those things implemented if you double click
on Photoshop for the first time, there's probably just an
If condition in there that says, "If not yet registered,
show prompt, else show program."
right? So conceptually, it's probably as simple as that,
so what do bad guys do?
Well, they try to figure out where in the program,
where among those zeroes and ones there is that condition
to try to circumvent it or try to overwrite it
with code of their own.
So again this all relates to the capability in most programs
to take advantage of or even break their use of memory
or even their use of disk space,
and its all because you can address every single byte by way
of its number byte zero, byte one, byte four billion,
if you have four gigabytes of RAM
or four gigabytes of disk space.
So let's now explode something we've been simplifying
in the CS50 Library, a string again is what-- in English?
[ Inaudible Answers ]
>> So its text, it's a word, it's a sentence,
maybe it's a single character, it's zero
or more characters in a row.
And this is actually the case in memory too.
If I wrote that program a week ago called Hello World,
and I typed in H-E-L-L-O and hit Enter
and that H-E-L-L-O were stored inside of RAM,
those characters would be stored back to back to back to back,
one ASCII character, one byte after the other.
And in fact what really happens inside of a computer program is,
if I type in H-E-L-L-O, H-- here's a free--
formerly blank chunk of memory,
so this is the first few bytes of, say,
four gigabytes worth of memory.
When I type in H-E-L-L-O, when store in a string,
what really happens is this H-E-L-L-O,
and then the next word I type in if its Hello World,
might be W-O-R-L-D, but this is a bit broken and it's a bit
of a-- a lie because you need some way
of distinguishing boundaries between words.
So what C actually does is even though when you type words
at your keyboard and they're stored in these--
the variables called Strings,
even though it does store the word, one character
after the other, it also puts a special--
let's call it Sentinel Value at the very end.
And I'm gonna denote this with backslash zero.
>> So we've seen backslash N
and the backlash almost always denotes something special.
It's an escape character.
Backslash zero is the way
of representing a byte whose 8 bits are all zeros.
This is a special character.
This is in contrast just to be clear.
If I wrote just zero, that's actually the ASCII character.
The text that looks like the number we know is zero
but the letter zero, the ASCII character zero is not zero,
zero, zero, zero, zero, in terms of bits,
so backslash zero means a byte worth of all bits--
a byte worth of all zeros.
And I need this one other place backslash zero so that now
if I have an exclamation point at the end of my sentence,
I might have another exclamation point there.
So I typed in "Hello" and hit Enter,
this ends up in memory followed by this backslash zero.
If I then on another line typed in "Hello World" it ends
up in memory in the same way.
If I typed them both together with just a space bar character,
you do not get a backslash zero after every word.
You only get a backslash zero after every string.
So the moment you-- when you use the CS50 Library
and use get string and hit Enter, the backslash zero ends
up at the very end of the string.
You might still have space bar characters in the middle there.
So what's the application here?
So it turns out that a string
in C is just a new data structure called an array.
And you might recall from the tail end of scratch
or specifically the fruit craft RPG game,
where the little guy walked around stage
and he actually picked up like oranges and apples
and pears those kinds of things, he was putting them into a list
so to speak and to use scratches terminology,
well that's really just an array.
An array is a data structure, it's like a special variable
that doesn't just store one thing it can store two things
or three things or four things altogether.
This is great for strings because of what's a string,
its zero or one or two characters altogether.
So the way in which C implements strings is it takes a chunk
of memory, puts the first character here then here then
here then here and at the very end
of the string it puts backslash zero.
And so, what the implication here is that even
if you have a string that's been past in by the user
of the keyboard, you can actually get
at individual characters in it because they are all back
to back to back in this way.
So let me go ahead and open this program called argv1
and we can finally reveal what
that special thing called argv has been
that you might have seen in textbooks
or in the online references.
So thus far, all of our programs have been declared
with the very simple void.
But the question was asked, I think on Monday, what is it mean
if you actually have something other
than void inside a parenthesis?
What if you want a program to take command-line arguments?
Well, what's a command-line argument?
Well, most of the programs we've been using down here
on the terminal window, take command-line arguments.
There is a program called Make, but anytime you type something
like beer4 at the prompt, you're passing
to make a command-line argument which is similar in spirit
to calling get string and asking the user for a string,
but notice the one key conceptual difference.
A command line argument is input,
is a word that the user types before he
or she actually runs the program.
So it's passed to the program as at the so-called command line.
So how does Make-- how does GCC,
how do any other programs we've been taking for granted
in the Appliance actually access those?
Well, now we can change what main looks like.
This is the other correct declaration of main
and it's a little a scarier looking
but we'll tease this apart in just a second.
Int is the same, main is the same, what do you think argc
and argv might represent?
So arg denotes argument, so just as another function like swap
or increment or any of these functions we've been playing
with today or chorus just as they can take arguments,
it turns out main can as well.
Thus far, none of the programs we've had
to write take arguments at the command line.
We've hit Enter then we're prompted
for a string via the use of--
we then prompt to use the first string, but if you actually want
to take the arguments
at the very command line you can declare main as this,
int argc which stands for argument count.
And then you can declare this,
char star argv open bracket, close bracket.
So this will make sense in just a moment.
Let me actually simplify this for a moment and rewrite this
as this, which is again sort of CS50 style, not quite correct
so we'll fix it in a moment.
This means that argc is a number and its argument count.
How many words that the user type at the prompt?
Argv is what's called argument vector
which is usually synonymous with array.
So it's a list.
It's a collection of words that the user typed.
So when you type in multiple words at the prompt,
where did they end up?
They end up in a variable called argv
and the square brackets is just C's way
of saying this is an array of arguments, that is,
this is multiple words, multiple inputs all inside
of one variable like a scratch list.
I'm gonna leave this string for just a moment
and let's actually see what this program does.
I'm gonna go ahead and go down here and I'm gonna compile
in the lectures to source, I'm gonna compile argv1, Enter,
and now notice unknown typed string.
How do I fix this?
Yup, includes CS50.h. So now let me go back
to my prompt and rerun arg.
Okay, that's good.
Now I'm gonna run it, argv1, foo, bar, Enter.
Interesting, it looks like this program simply does what?
Print out what you typed but one word per line
and then its got some-- just for aesthetics,
just some blank space at the top and blank space on the bottom.
But it looks like it literally regurgitated what I wrote best
or just like this, right?
So it's just spitting out of those words at the prompt.
How did we get access to them?
Well, it's actually pretty easy.
So notice again that main is now being passed a special number,
the number of words that were typed at the line then a string
but not a string in array of strings as represented here
so this represents the number of--
the words that were typed at this command line.
So let's see what happens,
I print backslash N. Why am I iterating
from I equals zero to argc?
Conceptually what is that mean?
Just iterate over all the arguments.
Iterate from zero to whatever the number
of total words there were that were typed.
And now this is familiar,
present as means put a string here,
what string do you wanna put here?
Well, if argv is said to be an array or a vector of words
that were typed turns out that syntactically you can get
at the first word by typing on our keyboard argv of zero.
That's the very first word that was typed.
Argv1 is the second, argv2 is the third, argv3, four, five,
six and so forth, those are each of the individual words numbered
from zero on up that you typed at the prompt.
So if I wanna generalize this, I just say I
and this means get me the I word that was typed
at the prompt and printed out.
So now I can go ahead and print this as follows.
If I go back again and I go ahead and run this and I say,
"Yes indeed" Enter, it does exactly that.
But notice too, it's also including not just the words I
typed after the program's name
but also the program's name itself.
So this actually means you have the ability
to see what your own name is which is sometimes useful.
Well, let's take this one step further,
not to make this too complex,
but let's take this one step further.
Let me go ahead and open up version 2 of this file.
It looks a little scarier.
Let me go down to my prompt and run argv of argv2, argv2,
we'll zoom in, enter, compiles okay, argv2, Enter.
Hmm, interesting.
Hi. So what's this one doing differently obviously?
So now it's doing not one word per line
but one character per line.
So this suggest
that programmatically I must have the way not only to iterate
over each of the words that the user types but also over each
of the-- just the characters that they typed and that's
because 2 just as argv itself is an array of strings.
Well, guess what a string is?
It is an array of characters,
so we can apply this exact same logic.
Let me zoom in now on this version 2,
and again I at the top here I have this
and I simplified this a moment ago.
This is the first training wheel that we'll eventually take off
when we keep saying string in C programs.
Technically, it's really something called char star
and the star is just a little confusing for now so we hide it
under the guides of something called string.
But note for now that these are synonymous,
it's just we're currently in the habit
of calling those things strings, but we will go--
get rid of that convention in a week or two.
So now let's look at what this program is doing.
It's iterating from zero to argc again, okay, it's now iterating
from another variable, J equals zero.
What do you think string length of argvi means?
String length, strlen is just another function.
It's in a special library
and it just gets you the length of a string.
So, what the string length of argvi generally mean?
[ Inaudible Answer ]
>> Given the length of the I word
that the user typed at the prompt?
That's it, give me the zeroth word, the first word,
the second word, the third word and get its length.
Now as in the aside, had do you figure
out the length of a string?
What-- how would-- whoever implemented string length forty
years ago, how did they do it?
You just start at the first start
of the string and look for what?
Backslash zero, and you return the total number
of characters you saw before the backslash zero,
so that's actually a pretty simple program--
a function, but let's see what we're doing.
There's one piece of aesthetic difference here.
Notice that you can actually declare multiple variables
at once inside of a for loop, you just put a comma there.
So I'm declaring not only an int called J and setting it equal
to zero, I'm also declaring another int called N
and setting it equal to the length of the string
and then I'm iterating J up to N.
>> So from zero up to the length because I'm doing J plus plus,
so now notice, we can apply the same logic.
So again the syntax is new but the idea, we're just mimicking.
If you can index into an array of words called argv
with the square bracket notation,
but the thing that's there is a string and what's a string?
It's just an array of characters.
You can then use double bracket notations to say give the I word
and give me its J character.
And if you do that, this seems to empower us now to iterate
over all of the lines and all of the--
all of the words and all of the characters in a string one
at a time printing them out by way of the familiar printf.
But this time present C 'cause it's a character followed
by backslash N. So in short, what is an array?
It's just a contiguous block of memory inside
of which are the same types of thing again and again
and again either a word, a word, a word,
a word or in this case a character, a character,
a character, a character.
So, who cares?
Well, it turns out that back in the day, they're actually back
in Caesar's day, literally, there was something known
as the Caesar cipher, and the Caesar cipher is not unlike the
grade school flashback I had the other day whereby you might pass
a note handwritten to a significant other
in your third grade class, but you want to encrypt it
by actually rotating the characters
in the message by one place.
A becomes B, B becomes C and so forth and we teased earlier
on Monday that you could do this now programmatically 'cause a
letter is just a number like 65 is A and 97 is lower case A.
So you could actually convert letters to numbers, do some math
and then convert numbers back to letters
and you could do this now with the computer program.
And indeed, according to legend,
this is exactly how Caesar himself encrypted messages
to his generals in the field taking hopefully a secret number
bigger than one.
He didn't just rotate letters and their alphabet by one
but rather some bigger number or something similar
and so thus was born what's called the Caesar cipher,
a rotational cipher whereby you rotate the letters in the--
some word by some number of places.
So in problem set 2 next week,
you will see the same idea applied where you'll have
to implement your own forms of encryption,
your own Caesar ciphers and some other ciphers whereby you'll
take input and have to produce output
that whose input might be 1, 2, 3, 4,
5 but the output should be something much harder
to actually decode or decrypt.
And the little teaser here, I have about one minute left
on the clock, is that all of these actually relates
to a little thing you see on the screen here, little orphan Annie
which is stolen from a movie called-- anyone know?
A Christmas story where little Ralphie has been listening
to the radio for ages hearing secret messages from them
and he tries to decrypt them
and they finally send them little orphan Annie's secret
decoder ring which just allows you to rotate the ring and map A
to B and B to C and so forth but in some general way,
and so this was Ralphie's and soon your discovery.
>> "A member of the Little Orphan Annie secret circle
and is entitled to all the honors
and benefits occurring thereto."
>> Signed, Little Orphan Annie.
Countersigned, Pierre Andre!
In ink! Honors and benefits.
Already at the age of nine.
[ Inaudible Remarks ]
>> Come on.
Let's get on with it.
I don't need all that jazz about smugglers and pirates.
>> Listen tomorrow night for the concluding adventure
of the Black Pirate Ship.
Now it's time for Annie's secret message
for you members of the secret circle.
Remember, kids, only members
of Annie's secret circle can decode Annie's secret message.
[ Background Music ]
>> Remember, Annie is depending on you.
Set your pins to B-2.
Here is the message.
12, 11, 2--
>> I am in my first secret meeting.
>> -- 25, 14, 11, 18, 16, 23--
>> Pierre was in great voice tonight.
I could tell that tonight's message was really important.
>> -- 3, 25, that's a message from Annie herself.
Remember, don't tell anyone.
[ Background Noise ]
>> Ninety seconds later I'm in the only room in the house
where a boy of nine can sit in privacy and decode.
Ah! "B." I went to the next.
"E." The first word is "be"!
"S." It was coming easier now.
"U."
>> Come on, Ralphie!
I gotta go.
>> I'll be right down, Ma.
>> Gee whiz.
>> "T, O."
"Be sure to."
Be sure to what?
What was Little Orphan Annie trying to say?
Be sure to what?
>> Ralphie!
Randy has got to go!
Will you please come out?
>> Alright, Ma!
I'll be right out!
>> I was getting closer now.
The tension was terrible.
What was it?
The fate of the planet may hang in the balance.
>> Ralphie!
Randy's gotta go!
>> I'll be right out, for crying out loud!
>> Almost there!
My fingers flew.
My mind was a steel trap.
Every pore vibrated.
It was almost clear.
Yes! Yes! Yes!
>> Be sure to drink your Ovaltine.
Ovaltine? A crummy commercial?
[ Background Music ]
>> Son of a bitch!
[ Laughter ]
>> And that's you have encryption.
We'll see you next week.