Week 1, continued - VoiceTube: Learn English through videos!

Subtitles section Play video

>> DAVID J MALAN: All right, so this is CS50.
And this is clearly a Friday.
And this is the end of week one.
So you may recall that we left off, last time, with a cliffhanger of sorts.
Whereby we expose this lie, that no matter what you've been taught growing
up, 1 divided by 10 is not, in fact, 0.1 or 0.100 or 0.10000.
In fact, if we compile this program, as we did yesterday, with,
make imprecision, and then do dot, slash, imprecision,
we learned that this is what's 1 divided by 10 actually is.
So that's not really quite the case.
But this does hint at some fundamental limitation of computers.
And indeed, among the things we're going to do
today is take a look at why this has happened, what implications this has,
how humanity has failed to grasp this in some very
serious situations-- the result of the which
has been quite tragic and expensive-- and also
take a look at how we can actually defend
against these kinds of limitations.
So intuitively, perhaps, why is 1 divided by 10,
according to my computer here, not just 1/10, 0.10?
Yeah.
What do you think?
>> AUDIENCE MEMBER: The radix is different?
>> DAVID J MALAN: The what is?
Oh, the radix is different?
So not quite.
It's actually more fundamental to the hardware.
Other thoughts?
Yeah.
AUDIENCE MEMBER: They represent numbers differently?
DAVID J MALAN: So they-- Right.
They represent numbers differently.
Inaccurately, apparently.
So that is-- Well, differently from what?
Or from whom?
From us?
AUDIENCE MEMBER: Yeah.
They don't use the decimal system to [INAUDIBLE].
DAVID J MALAN: OK.
So in a sense, they don't use the decimal system.
Underneath the hood, everything is, indeed, binary,
and that's related, in fact.
But it's even a simpler explanation than that.
Yeah.
>> AUDIENCE MEMBER: They only have so many bits.
They can only store up to a certain extent, like with the decimals.
>> DAVID J MALAN: Yeah.
This is what's really getting at it.
It turns out that computers typically, will always only
use a finite amount of information to represent something.
Right?
After all, we only have a fixed amount of hard disk space.
We only have a fixed amount of RAM, or computer memory.
And if you only have a fixed amount of something,
surely you can't actually count up to infinity or any number you want.
You, kind of, have to pick and choose what range
of values you're going to support.
>> And so for instance, a week or two ago, when we talked about ASCII,
and we talked about 8 bits, or a byte, so to speak,
the biggest number we could represent with 8 bits was what?
255.
And we can represent 256 total values but not if we spend one of them
on 0-- Well, but if we spend one of them on 0,
then the biggest number is, of course, 255.
>> So it turns out, that this is the case too, in this context.
We started talking, last time, about floating-point numbers, which
are different from integers, in that they have a decimal point
and, hopefully, some numbers after that, but they are too.
A computer is only typically going to use 32 bits, maybe 64 bits
to represent a floating point value.
So even though we've grown up learning mathematics and knowing
that you can absolutely have an infinite number of numbers
after the decimal point, not if you have finite memory.
You, kind of, have to round, or pick and choose which
numbers you're going to represent.
And so you can think of, in a sense, this being the computer's closest
approximation to the value 1/10 that it can get, with just 32 or so bits.
And it's not just 1/10.
>> For instance, if I change this to 1/3, which we think is even simpler.
So 1 divided by 3.
Let me save the file.
Let me go ahead and recompile it.
And let me re-run it.
Here too, apparently, 1/3 is not 0.3 and then an infinite number of 3's
thereafter.
You have this imprecision at the end.
So we humans are correct, and what you learned is, in fact, correct,
but we're bumping up against some limitations.
>> And what I thought we'd do today, is begin
by looking at, frankly, the tragic consequences of this
sometimes, when mankind does not quite implement
for this reality and these limitations.
And we'll see a series of vignettes from the History Channel that takes
a look at how things have gone wrong.
It's about 8 minutes long, and we'll come back after this
and take a look at exactly what else can go wrong.
If we could dim the lights--
>> [VIDEO PLAYBACK]
>> -Computers, we've all come to accept the often frustrating problems that
go with them.
Bugs, viruses, and software glitches are small prices
to pay for the convenience.
But in high-tech and high-speed military and space program applications,
the smallest problem can be magnified into disaster.
On June 4, 1996, scientists prepared to launch an unmanned Ariane 5 rocket.
It was carrying scientific satellites designed
to establish precisely how the Earth's magnetic field interacts
with solar winds.
The rocket was built for the European Space Agency
and lifted off from its facility on the coast of French Guiana.
>> -And about 30 seconds into the flight, they first
noticed something was going wrong.
That the nozzles were swiveling in a way they really shouldn't.
Around 40 seconds into the flight, clearly the vehicle was in trouble,
and that's when they made the decision to destroy it.
A Range Safety Officer with tremendous guts pressed the button,
blew up the rocket before it could become a hazard to public safety.
>> -This was the maiden voyage of the Ariane 5,
and its destruction took place because of a flaw
embedded in the rocket's software.
-The problem on the Ariane was that there
was a number that required 64 bits to express,
and he wanted to convert it to a 16 bit number.
They assumed that the number was never going to be very big,
that most of those digits in the 64 bit number were 0's.
They were wrong.
>> -The inability of one software program to accept
the kind of number generated by another was at the root of the failure.
Software development had become a very costly part of new technology.
The Ariane 4 rocket had been very successful, so much of the software
created for it was also used on the Ariane 5.
>> -The basic problem was that the Ariane 5 was faster, accelerated faster.
And the software hadn't accounted for that.
>> -The destruction of the rocket was a huge financial disaster,
all due to a minute software error.
But this wasn't the first time data conversion problems
had plagued modern rocket technology.
>> -In 1991, with the start of the First Gulf War,
the Patriot missile experienced a similar kind
of number conversion problem.
As a result, 28 people, 28 American soldiers
were killed and about 100 others wounded,
when the Patriot, which was supposed to protect against incoming scuds,
failed to fire a missile.
>> -When Iraq invaded Kuwait and America launched Desert Storm in early 1991,
Patriot missile batteries were deployed to protect Saudi Arabia and Israel
from Iraqi Scud missile attacks.
The Patriot is a US, medium-range surface-to-air system
manufactured by the Raytheon company.
>> -The size of the Patriot interceptor, itself, is about, roughly 20 feet long.
And it weighs about 2000 pounds.
And it carries a warhead of about-- I think it's roughly 150 pounds.
And the warhead, itself, is a high explosive,
which has fragments around it.
The casing of the warhead is designed to act like buckshot.
>> -The missiles are carried, 4 per container,
and are transported by a semi-trailer.
>> -The Patriot anti missile system goes back at least 20 years now.
It was originally designed as an air defense missile
to shoot down enemy airplanes.
In the First Gulf War, when that war came along,
the Army wanted to use it to shoot down scuds, not airplanes.
The Iraqi Force was not so much of a problem,
but the Army was worried about scuds.
And so they tried to upgrade the Patriot.
>> -Intercepting an enemy missile traveling at mach five
was going to be challenging enough.
But when the Patriot was rushed into service,
the Army was not aware of an Iraqi modification that made
their scuds nearly impossible to hit.
>> -What happened, is the scuds that were coming in, were unstable,
they were wobbling.
The reason for this, was the Iraqis, in order
to get 600 kilometers out of a 300 kilometer range missile,
took weight out of the front warhead and made the warhead lighter.
So now, the Patriot's trying to come at the scud, and most of the time,
the overwhelming majority of the time, it would just fly by the scud.
>> -Once the Patriot system operators realized the Patriot missed its target,
they detonated the Patriot's warhead, to avoid possible casualties if it
was allowed to fall to the ground.
>> -That was what most people saw, those big fireballs in the sky,
and misunderstood as intercepts of Scud warheads.
Although in the night skies, Patriots appeared
to be successfully destroying scuds, at Dhahran,
there could be no mistake about its performance.
There, the Patriot's radar system lost track of an incoming Scud,
and never launched, due to a software flaw.
It was the Israelis who first discovered that the longer the system was on,
the greater the time discrepancy became, due to a clock embedded
in the system's computer.
>> -About 2 weeks before the tragedy in Dhahran,
the Israelis reported to the Defense Department,
that the system was losing time, that after about 8 hours of running,
they noticed that the system was becoming noticeably less accurate.
The Defense Department responded by telling all of the Patriot batteries
to not leave the systems on for a long time.
They never said what a long time was.
8 hours?
10 hours?
1000 hours?
Nobody knew.
-The Patriot battery stationed at the barracks
at Dhahran, and its flawed internal clock, had been on over 100 hours
on the night of February 25.
>> -It tracked time to an accuracy of about 1/10 of a second.
Now 1/10 of a second is an interesting number
because it can't be expressed in binary, exactly.
Which means, it can't be expressed, exactly,
in any modern digital computer.
It's hard to believe, but use this as an example.
Let's take the number, 1/3.
1/3 cannot be expressed in decimal, exactly.
1/3 is 0.333 going on for infinity.
There's no way to do that, with absolute accuracy, in decimal.
That's exactly the same kind of problem that happened in the Patriot.
The longer the system ran, the worse the time error became.
>> -After 100 hours of operation, the error in time was only about 1/3 of a second.
But in terms of targeting a missile traveling at mach 5,
it resulted in a tracking error of over 600 meters.
It would be a fatal error for the soldiers at Dhahran.
>> -What happened, is a Scud launch was detected by early-warning satellites,
and they new that the Scud was coming in their general direction.
They didn't know where it was coming.
>> -It was now up to the radar component of the Patriot system,
defending Dhahran, to locate and keep track of the incoming enemy missile.
>> -The radar was very smart.
It would actually track the position of the Scud
and then predict where it probably would be,
the next time, the radar sent a pulse out.
That was called the range gate.
>> -Then, once the Patriot decides enough time has
passed to go back and check the next location for this detected object,
it goes back.
So when it went back to the wrong place, it then sees no object
and it decides that there was no object, it was a false detection,
and drops the track.
The incoming Scud disappeared from the radar screen,
and seconds later, it slammed into the barracks.
The Scud killed 28 and was the last one fired during the First Gulf War.
Tragically, the updated software arrived at Dhahran the following day.
The software flaw had been fixed, closing
one chapter in the troubled history of the Patriot missile.
>> [END PLAYBACK]
>> DAVID J MALAN: So we'll take a look at some similar limitations in just a bit.
But first, let's transition to a few FYI's.
So one-- this weekend, there will be super sections,
which are meant to supplant regularly scheduled sections, which
will start up a week hence.
Take a look at the CS50's website for more information on those.
They will also be filmed and streamed live for those unable to attend.
Problem set 1 is on the course's website already,
and we'll take a look at that in just a little bit.
And office hours too, will take place this Monday through Thursday.
>> So this was the most canonical program we looked at last time.
It's like the simplest program you can write in C,
and even that's a bit of a bold claim.
Right?
Because there's a lot of seeming complexity to this.
So let's take a quick look at what some of these elements
were and then try to provide a mental model for how
these simplest of programs work, and then we'll start
looking at things ever more complex.
So this line here, highlighted now, in yellow, what did we say, last time,
that this does for us?
What's the purpose it serves?
Anyone from farther back?
Yeah.
>> AUDIENCE MEMBER: [INAUDIBLE]
DAVID J MALAN: Good.
So it gives you access to commands, or let's
call them functions, that someone else wrote, that are declared,
so to speak, in some other file.
So we'll see exactly what a .h file is versus a .c file, eventually.
But for now, just know that printf, for instance,
is among the functions that have been declared in some other file, somewhere
else on the cloud's hard drive that allows us to access printf and use it
without having to reinvent that wheel ourselves.
Meanwhile, main.
What was the analog of main, last week?
Yeah.
>> AUDIENCE MEMBER: Green flag is clicked.
>> DAVID J MALAN: Yeah.
Scratch's, when green flag clicked.
It's like the puzzle piece that kicks things off.
And so similarly, did the world decided some years ago that in C,
and a bunch of other languages, if you want to write a program,
your first function has to be called, main.
And it has to look like this.
But we'll come back, another time, to what, int,
and, void, mean in that context.
For now, the curly braces are kind of like Scratch's puzzle piece shape
that encapsulates some number of lines.
And among on the lines here, is this one here.
printf is a function whose purpose in life is to print a formatted string.
And by formatted, I mean you can plug in placeholder values,
and you can specify how many decimal points, how many numbers to print
after a decimal point and the like.
And printf, of course, takes one or more arguments or parameters,
otherwise known, more simply, as inputs.
>> So printf, like a lot of functions, takes inputs.
And those inputs are embraced by the two parentheses here.
And inside of those is one input.
It's a string, as we've called it, which is just a sequence of characters,
like a word, or a phrase, or a whole essay even, in between double quotes.
And that's what's going to influence the behavior of printf because, of course,
it's just a generic print function.
It's not going to know what to print, unless you tell it.
And then, some minutiae.
What did we say this weird sequence of symbols is?
Yeah.
>> AUDIENCE MEMBER: New line.
>> DAVID J MALAN: New line.
So it turns out, you can't just hit, enter, when you're writing the program.
Generally, the compiler is going to get a little confused as to what you mean.
Rather, you have to literally say, give me a new line here.
And so /n is what we generally call an escape character.
So n, for new line.
And the compiler knows that when it sees /n,
it should actually induce the computer, ultimately, or printf, in this case,
to print out an actual new line, like hitting the, enter,
key on your keyboard.
And lastly, what did we say this piece of syntax is for?
What does it represent?
Yeah.
>> AUDIENCE MEMBER: [INAUDIBLE]
>> DAVID J MALAN: It's just the end of the line.
It's the end of the statement.
And realize that we don't put them everywhere.
We certainly don't put them at the ends of every line.
For instance, there's none on the first line, there's none on the line
with, main, there's none after the curly braces,
but you'll start to see and get familiar with where it's called for.
And it's almost always after a function call or a statement, some action
that you're actually taking.
>> And know now, especially if among those less comfortable,
these are the kinds of stupid things that you'll end up accidentally banging
your head against the wall over.
Because you'll be logically confident in some problem
you've solved for a problem set, and the damn thing just
won't compile or even run.
And so often, early on, it's going to be because you missed a parenthesis,
or you missed a semicolon.
And so just be mindful of these kinds of things,
and try not to get frustrated by them because very quickly does this
become old hat.
But it's very easy to get frustrated early on, as a result.
>> So now, let's take a look at how this line is actually working
and then look at a slightly more complicated one.
So we have over here, the ability to draw on this screen.
And let's suppose that this is my computer screen,
but I am writing the, hello program, and I have not implemented, printf.
Someone else has implemented, printf.
Who would like to claim to have implemented, printf?
If we may?
All right, what's your name?
>> STUDENT 1: [? Copal. ?]
>> DAVID J MALAN: Copal, come on up.
Come on up.
All right.
So we have, here, some name tags, since we'll make a little game of this.
And we will call you, printf.
And if you want to come over here, what I've just drawn on the screen,
it's quite simply, there's me, this.
>> All right, so, hello my name is, printf, if you'd like to put that on.
All right.
And if you can go stand by the computer screen
as though you are the function that came with this computer system.
And your purpose in life is to actually print something.
But much like the program we just had on the screen, here,
we're going to have to actually give you some input.
>> And so, if my input, here, is apparently, what is passed to printf,
let's kind of mock it up like this.
I'm going to literally write on a piece of paper, "hello, world,"
backslash N. And to be clear, what I've just drawn on this piece of paper,
looks like this.
So when I run this program, and this yellow line of code gets executed,
it's as though I, the hello program, am handing some input off to a function
that someone else wrote.
>> And if you, with your finger, could actually, with your finger,
draw on the screen whatever it is you have been handed,
the effect, ultimately, is to see exactly that, on the screen.
And a Little corner case here.
And good, we shouldn't see the, new line, at this point.
It would be incorrect for you to explicitly draw the newline.
But if we kept writing words on the screen, they would end up below that.
>> So thank you very much, but stick around here for just one moment.
We now need one other volunteer, if we could,
that's going to need to play the role of-- It's only people in the orchestra
right now.
How about-- OK.
Right here.
Come on up.
What's your name?
>> STUDENT 2: [? Ivay. ?]
DAVID J MALAN: Sorry?
STUDENT 2: [? Ivay. ?]
DAVID J MALAN: Ethan, come on up.
No?
Did I get that wrong, even after you said it twice?
Come on up.
It's hard to hear up here.
OK.
And I'm sorry, what's your name?
>> STUDENT 2: [? Ivay. ?]
>> [? DAVID J MALAN: Ivay. ?] OK.
For now, if you don't mind, you are GetString.
>> STUDENT 2: OK.
Cool.
DAVID J MALAN: So if you would like to stand here for just a moment,
let's take a look at a slightly more complex program, that
now has three lines of code.
So we have, one, state your name using printf; two, a call to GetString,
followed by an assignment to a variable called, string s, or called s;
and then another call to, printf, but this time with two inputs.
>> So we've already done state your name, or rather, we've
already done a printf call.
So I'm going to write, State your name.
And so, what I'm going to pass, printf, in just a moment,
is quite simply, this.
So if you want to go ahead and draw this on the screen, that's your input now.
All right.
And forget string, we now have our own line of code here.
So in, GetString, we need to actually call, GetString.
So your purpose in life is to just walk out into the orchestra, if you could,
and get someone's name.
But let's give you something to put it on.
If you want to, go ahead and get a string,
get someone's name on that piece of paper, if you could.
>> All right.
And we'll see, in just a moment, whose name we're getting.
Meanwhile, what I'm going to have ready, is a blank piece
of paper, in which, I'm going to store whatever value it
is that GetString is returning to me, I, being a string variable called, s.
All right.
So what do you have here?
Nik.
All right.
So we have Nik's name here.
So this is what literally has been returned
to me, so to speak, by GetString.
>> I, now, am going to execute the left-hand side
of that expression, where I simply copy down, for today's purposes, Nik.
So now, I have a variable called, s, storing Nik's name.
I've already handed to printf, a previous argument.
But in our third and final line of code, I actually have to hand printf
something a little different-- "hello, %s," backslash n.
>> And so the last line I'm going to send-- the last thing I'm
going to write down now, is this.
So the two lines of code, or rather the last line of code,
calls for two inputs-- one, this, and two, this.
So if our printf function can now take these as input,
let me clear the screen for you.
Actually no, you can go ahead.
We'll leave it up, since it's on the same program.
We should see, hello, Nik.
All right.
So this was quite a few hoops to jump through, just
to write, state your name, and, hello, Nik.
But this simple idea of message passing, of input passing and output receiving,
is exactly the model we're going to have for even the most complex functions.
So thank you so much to you both.
We have a lovely stress ball here for you.
And thank you to our GetString and printf volunteers alike.
Thank you.
All right.
Thank you to you both.
>> So we've been talking about thus far, mostly about strings.
And it turns out that C can actually understand a few different data types.
In fact, let's take a look at these here.
So C, and a lot of languages, understand things called chars.
A char is generally a single byte, or eight bits.
And it represents a single character, like the letter A, or the capital
letter A, or the lowercase letter A, or an exclamation point,
or any character that you can type on your keyboard, and sometimes even more.
We also happen to see floats.
A float is, generally, a 32-bit value, or four bytes
because again, one byte is eight bits.
>> So a float is a floating point value, something with a decimal point.
And indeed, that's what the movie was talking
about when they spoke about floating point values, some fixed number of bits
being used to represent a real number.
But there's also things called doubles.
These exist in Java, if you've taken APCS,
and a double, as the name thankfully suggests, is twice as big as a float.
It's still a real number, it just has more bits
with which to be ever more precise, or to store even larger numbers.
int is easy.
We talked about that last time.
It's just an integer.
And it's generally 32 bits, or four bytes.
>> And so, if you have, let's see now, 32 bits-- and we did this in week 0,
ever so briefly-- if you have 32 bits, what's the biggest
number you can represent as an integer?
Give or take?
It's like 4 billion, and that's only if we're
representing positive numbers only.
If you have 32 bits, and you want to represent negative numbers as well,
your range is, essentially, negative 2 billion to positive 2 billion.
But generally, we'll start at 0 go up to 4 billion.
>> You don't have to know precisely, but we can see this, in fact, if I just
open up a little calculator, here.
I can do 2 the 32, and that's exactly how big,
how many values you can represent, with 32 bits.
And it's roughly 4 billion.
So we'll keep seeing that number in a few different places.
But if you need longer numbers than that,
it turns out there's something called a long long.
And a long long is generally 64 bits, which
means it's an order of magnitude even bigger than an int.
>> So I can't even pronounce the biggest number that you can represent,
but it's markedly bigger.
Now as an aside, historically, if an int is 32 bits,
and a long long is 64 bits, how big is a long, not a long long?
You'd think it's longer than an int but maybe less long than a long long,
but it actually depends.
>> And so it turns out one of the frustrations too,
with writing code on certain systems, is that not all of these data types
have pre-determined values.
Sometimes it's this many bits.
Sometimes it's that many bits.
So you actually have to know, sometimes, what hardware
you're running your software on.
Thankfully, other languages and other data types that now exist,
allow you to be more precise.
Well, we saw string, and we saw bool, too,
but it turns out those come only with the CS50 library.
So those are not built into C. Those instead,
come in that file called CS50.h, that we'll eventually
peel back the layers of.
But for now, they're just additional data types.
A bool is a true or false, and a string is a sequence of characters,
like a word.
Now printf, we've seen, has placeholders, %s is one.
And you might be able, to now, infer from these other examples, how
you could have a placeholder for different data types.
For instance, take a guess, if you wanted to print out a single char using
printf, the placeholder is probably %c.
And if you want to print out an integer with the placeholder, %i.
%lld is a long long decimal value, but long long, so that maps to that.
And then %f for floating point value or for a double,
so sometimes they're re-used in different contexts.
So we'll see and use some of those over time.
And printf and other functions also support others' escape sequences,
and sometimes, these are necessary.
So backslash n is a new line.
Backslash t, does anyone want to take a stab?
AUDIENCE MEMBER: Tab.
DAVID J MALAN: Tab.
So if you actually want to print out a tab, not
a fixed number of spaces but an actual tab character, you don't hit your,
tab, key on the keyboard, generally, you actually do backslash t.
Backslash double quote, why would I ever want that?
Right?
Why can't I just type a double quote on my keyboard?
AUDIENCE MEMBER: Because, otherwise, it's
going to think it's the end of like your print [? text. ?]
>> DAVID J MALAN: Exactly.
Remember, with our printf examples, when we
were passing to printf in input, on the left of that input string
and on the right of that input spring, of course, was a double quote.
If your own input has a double quote in the middle of that,
the computer might potentially get confused, as to,
does this double quote belong in the middle?
Does it belong with the left one?
Does it belong with the right one?
And so, if you want to make it super clear, you do backslash double quote,
so that it's escaped, so to speak, and it's not conflated for something else.
And there's a few others here, backslash r, single quotes, 0,
that we may see over time, as well.
And now, what about functions?
>> So actions that we can take thus far in this language, C, well, we've seen,
printf, of course, and all of the others on the screen,
here, that we'll use for the course's first few weeks only,
come when the CS50 library.
And they make it much easier, in C, to actually get user input.
It turns out that in C, and frankly in a few languages,
it's a real pain in the neck to do something simple, like prompt the user
for keyboard, for his or her input.
And so these functions make it easier.
>> And it also has error checking throughout,
so that, when you recall on Wednesday, we
saw the, retry, warning, when I didn't cooperate,
and I typed a word, instead of a number?
We've done the heavy lifting early on to make sure the user cooperates.
But these are just training wheels that we will eventually,
and quickly, take off.
>> So to recap, then, let's take a quick look,
much like we did with Scratch, at some canonical constructs in C.
This is meant to, sort of, be a whirlwind tour,
just so that you have a reference and that you've seen things at first.
But then we'll look at actual coding use some of these building blocks.
So much like in Scratch, when we had statements like,
say or, wait, in C, we do have functions as well, like printf.
>> If we want to express a condition in C, it's similar, in spirit,
to that puzzle piece that looked like this in Scratch.
But instead, we literally just write, if.
And then, in parentheses, we put a condition,
where that condition is what we'll call, again, a boolean expression.
And again, this is sort of pseudocode.
And, in fact, the // is a comment.
It's just English words to myself.
But this is the general structure of an, if, condition.
But we'll see concrete examples in just a moment.
>> If you want to have a two-way fork in the road,
much like we did with our volunteer on Wednesday, you can have an, else if.
And if you want to have a third and final condition, or default situation,
you can have just an else block, there.
And similarly, with boolean expressions, you can, and, them together.
And we saw on Wednesday, that it's not a single ampersand,
it's two, for lower-level reasons that we'll eventually see and play with.
Or-ing things together is 2 vertical bars.
On a US keyboard, this is generally a key
with the Shift key above your Enter key or Return key.
>> Then there's these things that we'll use maybe once or twice.
They are functionally equivalent to what you can do with an, if, else if,
else if else, construct, but they're called a switch.
They look very different, but we'll see in some of our distribution code,
for a future problem set, most likely, that it's sometimes just a prettier
way of expressing a whole bunch of conditions,
without having a lot of curly braces and a lot of parentheses and indentation.
But they give us no more power than we have already.
And now loops.
And this one, we'll look at a little more slowly.
But then, we'll start to use these, especially for those already familiar.
This is the canonical way, if incredibly arcane way, to write a loop in C.
>> Now a loop in Scratch was pretty straightforward.
You have a, forever, block.
You have a, repeat, block with just a number you have to type in.
And with the, for loop, you can implement both of those ideas,
but it's a little more technical.
But frankly, it's also relatively simple.
Once you know the order of operations, you literally
are just going to plug in values and tell the computer what to do.
So here's an example.
This is a loop that, quite simply, counts from one number up
through another.
And just by glancing at it, even if you have
no prior experience with this language, what number
does it probably start counting at?
OK, 0.
And I'm guessing that's because you see that there's an int and an i,
which is a variable.
It's initialized to 0.
>> And then later, it looks like we're passing printf, a value.
And, in fact, I made a little typo here.
But that's easily fixed.
Let me add in ,i here.
We now have printf being passed that placeholder value.
And what's going to count up through?
AUDIENCE: 50.
50.
49.
DAVID J MALAN: 49.
So 50, at first glance, seems right.
But that, it turns out, is going to be our condition that we keep checking.
And we're going to stop once i is no longer less than 50.
So this loop, conversely, should execute, so long as i is less than 50.
But as soon as it becomes 50, or 51, or worse, it should stop automatically.
All right.
>> So what actually happens here?
So this is the order of operations for a loop.
One, you have the so-called initialization.
This yellow highlighted chunk of code is executed first,
and it has the effect that, per Wednesday, you probably imagine.
It creates a variable called i and it stores in that variable the value 0.
So i is 0 at this point in the story.
>> The next thing that happens in this construct,
is that the condition gets checked.
So I check immediately, is i less than 50?
And of course, the answer for now is, surely, yes.
Yes, because i is 0, and that's surely less than 50.
Then what happens, is that this line of code gets executed.
And in fact, if there's multiple lines of code in those curly braces,
they all get executed one after another.
>> And in the effect here, is apparently, to print out
the number i, which is going to be 0, and then 1, and then 2.
But why?
Why does it get incremented?
Well, the fourth thing that happens is that this syntax
gets executed, after the semicolon.
i++ is a shorthand way of saying; take the value of i, and add 1 to it;
and then the next time around, add 1 to it; and the next time around,
add 1 to it.
>> So if we keep going, what's going to happen
next is I'm not going to initialize i ever again.
If I kept initializing i to 0, this example
would never end because i would be stuck at 0.
But what is going to happen is that the condition will be checked,
the line of code will get executed, the i will be incremented,
condition will be checked, code will get executed.
And it kept cycling again, and again, and again,
until i++ induces a value of 50.
>> The condition then says, is 50 less than 50?
The answer, of course, is no, and so the whole code stops executing.
And if you have more code on the screen down below, that's what happens next.
It pops out of these curly braces and continues to print more after that.
>> So a joke now, from FoxTrot, that you'll perhaps now understand.
It's always funny.
It's like the chuckles kind of percolate,
and then you realize you shouldn't be laughing at humor like this.
But there is some takeaway here, pedagogically, too.
So it turns out that I'm missing a piece of syntax,
or FoxTrot's missing a piece of syntax here.
What's missing, that we've had in every other example, thus far?
Return, is there, so that's something else,
that we'll come back to before long.
What's missing, though?
Yeah.
>> AUDIENCE MEMBER: The initialization of [INAUDIBLE].
>> DAVID J MALAN: OK.
So yeah.
So actually, this is-- Well, and count is initialized
up above, or rather, declared up above.
So this is another way of doing it.
But not in one line it's valid though.
How about here?
>> AUDIENCE MEMBER: Is it the curly braces?
>> DAVID J MALAN: Yeah.
So the curly braces are missing.
But this code, I mean, to their credit, is actually, syntactically valid.
It turns out, you don't need the curly braces
if you only have one line of code that you want to execute inside of the loop.
Now we always, in class and in all of our distribution code,
include the curly braces anyway, just for clarity's sake.
But realize that in textbooks and online examples,
you may very well see curly braces missing sometime.
And that's OK, if what you have indented and intended
is just a single line of code, and not multiple lines of code, potentially.
All right.
So related to the issue of imprecision, is an issue of overflow,
in the sense that, similarly, do integers have limits to them
just like floating point values?
In the world a floating point values, we can only be so precise,
after which, sometimes bad things can happen,
and our programs can be buggy and error.
Now even with integers, you can run into problems.
Now an integer doesn't have a decimal point or numbers after it.
It's just a natural number, typically.
So what could go wrong with an int?
If I'm using an int to count, what could go wrong?
Seems a lot simpler.
Yeah.
>> AUDIENCE MEMBER: If the number gets [INAUDIBLE]
>> DAVID J MALAN: Yeah.
What if you count so high, that you can't express that really big number.
Right?
At some point, you're going to exceed the boundaries
of a 32-bit value or a 64-bit value.
Now again, I'm not sure how to pronounce a 64-bit value,
but I know with a 32-bit integer, the biggest value it can be,
if it's only positive values, is roughly 4 billion.
So if I try to count to 5 billion, something's going to happen.
But let's see what, in fact, can happen.
In the world of integer overflow, where you, in a sense,
overflow the capacity of an integer, what might happen?
>> So here's a binary number, it's a throwback to 0.
It's all 1's, and the placeholders there, are powers of 2,
so this is binary.
So these are 8, 1 bits on the screen.
And if you recall or you quickly do the math,
what value is being represented here with these eight 1 bits?
255.
And even if you weren't quite sure of the math, you could do it out.
Or you could just kind of reason through it,
wait a minute, if I'm representing an 8 bit value,
and I've got 256 possible values, but the first of which is 0,
I just know that the biggest is going to be 255,
and that's what this one might be.
>> So suppose I try to add 1 to this value.
What would you do in grade school when adding a 1, and it
doesn't really fit because you have to carry the 1?
What is this number going to become when you add 1?
It's going to become 0.
Right?
Because if you had more bits-- and I'll try to, kind of, type it out here--
if we had more bits, what we could do here is add the 1,
and then we'd get this.
Whoops.
We'd have a 1 bit all the way over here.
>> But if this is a finite value, it's only 8 bits,
and that's pre-determined by the computer,
that 1 is effectively not there.
It just kind of falls off a cliff.
And so if you add 1 to 255, what value do you apparently get?
0.
And so numbers accidentally, and perhaps, unintentionally,
end up wrapping around like this.
So what can be the implication of this?
Well, there's a few different things.
So one, it does end up looking like 0, unintentionally,
but you can kind of see, even in the real world,
for better or for worse, manifestations of this idea of a limit.
For instance, any of you who have ever played Lego Star Wars,
does anyone happen to know the maximum number of coins
you can collect in Lego Star Wars?
Take a guess based on today's leading questions.
It's bigger than 256 or 255.
It's 4 billion.
So it turns out, and there's some people--
some googling confirmed last night-- have gotten 4 billion gold coins,
or whatnot, in Lego Star Wars.
Though apparently, there's a way to trick the game,
there's a bug or feature, that lets you just accrue lots and lots of points.
But the largest possible value, according
to this screen shot of someone I found online, is indeed, 4 billion.
>> Now why is that?
It's precisely 4 billion, probably because someone decided,
who was writing this game, that they could do 4 billion,
something, something, something, like the value I put up
with the calculator earlier, but it's just a little cleaner for humans
to say the maximum number of coins-- or studs,
as they call them-- that you can collect is 4 billion.
And so, why is this?
How is the LEGO game implementing the counter
that's keeping track of the number of coins you have?
They're using what?
AUDIENCE MEMBER: It stops counting after 4 billion.
DAVID J MALAN: It stops counting after 4 billion,
which means you can infer, as a programmer,
that they're probably using a 32 bit integer.
Like the programmer literally just typed, int, in his or her code,
and that's the type of variable that they're using to store someone's code.
So there's other manifestations of these kinds of limits.
>> So I have not played this game-- and I was reading up on the history
to confirm as much-- but in the original version of Civilization, where
you apparently interact with each other and can wage war or have peace,
Gandhi was supposed to be one of the most peaceful characters, as I
understand it, in the first version of Civilization.
And in fact, on a scale of 1 to 10, his aggressiveness was just a 1.
So ever so mildly aggressive, apparently.
>> But at some point, you can apparently install democracy in your geography.
And if you install democracy into your version of the game,
then your aggression level goes down.
It's a good thing.
People are more tranquil apparently, in that situation.
But apparently, someone did not have an, if, condition
in the original version of the code.
>> So Gandhi's aggression level went from positive 1, minus 2, to negative 1,
but the game doesn't understand negative numbers.
So what happened was Gandhi's aggression level went from 1, to 0, to negative 1,
which had the effect of wrapping around to being
the most aggressive character in the game, at a value of 255,
on a scale of 1 to 10.
And since then, there's been more incarnations of this game,
and they've kept it as a sort of Easter egg,
that Gandhi is apparently so terribly aggressive.
But it was the result of a very simple programming error
in that very early version of the game.
>> Now more disturbingly, more recently, the Boeing 787
was documented as having a bug, not the kind of device
you particularly want to have a bug.
And the symptoms, that I'll read here, from an article online,
was this, a model 787 airplane that has been powered continuously
for 248 days can lose all alternating current, AC,
electrical power, due to the generator control units,
GCUs, simultaneously going into fail-safe mode.
So this was a warning issued when this problem was discovered.
This condition is caused by a software counter,
internal to the GCUs, so an integer or a variable,
that will overflow after 248 days of continuous power.
Boeing is in the process of developing a GCU software upgrade that
will remedy the unsafe condition.
>> So much like the missile scenario, wherein
they had some kind of variable that was counting, and counting,
and counting, but gradually overflowing the boundaries of its capability,
similarly did the damn airplane have a variable overflow
after enough time of running.
And so the tongue-in-cheek way of working around this issue
is to truly, reboot, your plane every 247 days, so that the memory gets wiped
and the variable goes back to 0.
But realize, this is a very large incarnation of software,
but especially as we hear about Apple's operating systems going into cars,
and self-driving cars from Google, and any number of incarnations of software
in our daily lives, TVs and watches, and more,
realize were surrounded by software, all of which is written by us humans.
>> And as we'll all soon discover, it's very easy and very typical
to make mistakes when writing software.
And if you don't catch them, some bad things can happen.
Now sometimes, some funny things can happen,
or at least sometimes we know to expect some badness.
So 0 divided by 0, from grade school, is generally a bad thing.
It's undefined.
And it turns out-- and let's see if my mic can pick this up-- that Apple
had some fun with this recently.
So I have an iPhone here.
I'm going to talk to Siri and ask her to give me the answer to 0 divided by 0.
What is 0 divided by 0?
>> SIRI: Imagine that you have 0 cookies, and you split them evenly
among 0 friends.
How many cookies does each person get?
See?
It doesn't make sense.
And Cookie Monster is sad that there are no cookies.
And you are sad that you have no friends.
DAVID J MALAN: It's kind of obnoxious.
So this is what was just said there.
It's indeterminate, it's not defined, and indeed, many programming languages
or, really, compilers will detect when you, in a program,
try to divide 0 by 0.
More fun than this though, is that apparently, Cookie Monster
is on Twitter these days.
And he replied to this, with this, which is absolutely adorable.
But let's take a quick look at a couple of other constructs,
and then put some of this code to use, in good ways.
So it turns out, besides for loops, there's
something called a while loop, that looks different and is implemented
a little differently-- and we'll eventually see examples--
but in some sense, it's simpler because it
doesn't allow you to initialize and update within the boundary of the loop.
You can still implement it.
So you can do the exact same things with a while loop, as with a for loop,
but your syntax, ultimately-- as we'll eventually
see-- is going to be different.
There's even a do while loop, which is actually a little different,
in that whereas a for loop and a while loop always
check their condition first, if you read this thing top to bottom,
it kind of looks like it's going to check it's condition last because it's
truly the last line of code.
And indeed, that's going to be useful in certain programs that we write,
if you want to just blindly do something and eventually check the condition.
That's not necessarily a bad thing.
If we want variables, we can do it in a couple of different ways.
And we saw in the FoxTrot cartoon, one way of doing it,
where you declare your variable, like int counter semicolon,
and then later-- maybe the next line, maybe 10 lines later--
you actually initialize it.
So these 2 lines of code declare a variable of type int
and call it counter, so it gives me enough bits to hold an int.
And then eventually, it puts the value 0 into that variable.
It arranges the 0's and 1's in a pattern, that we know from last week,
represents the number we know as 0.
Or frankly, you can do this much more succinctly, just like this.
>> Now we also have the ability to call functions.
And in fact, here's a 2 line program, or an excerpt thereof,
that allows us to actually write some code that
gets a string from the user-- much like our volunteer a moment ago--
storing the result in a variable called name,
and then-- much like with our volunteer with printf-- prints out those values
by passing in two arguments, the string, followed by the variable
called, name, itself.
So let's take a look, before we come back to Mario there,
at a couple of now, examples of this.
>> I'm going to go ahead and open up, let's say, function-0.c.
And as always, this code is available on the course's website,
so you can play along at home and look at it later.
But here's the program in it's essence, from line 17 to 22.
The main program is where the program is always going to start.
This program, apparently, is going to print out your name, colon.
It's then going to call GetString, just like we did with our volunteers.
And then, this is interesting, it's going to call PrintName.
It turns out, all this time, there seems to be a function called PrintName.
That prints someone's name.
We didn't need to use printf from yesteryear, there's PrintName.
>> But that's misleading because PrintName does not
come with C. People did not invent it some 40 or 50 years ago,
I did, instead.
And in fact, if I scroll down further, notice
how I can write my own functions in C. We'll eventually
explain why we keep saying, void, in a few places,
but for today, let's just look at the name.
>> On line 24, if you want to create your own function,
you literally write the name of the function.
I chose PrintName.
In parentheses, you then specify what kinds
of inputs, and how many you want this function to take.
In this case, I want to take 1 variable called, name,
and it's going to be of type, string, so it's going
to be some sequence of characters.
And then, this program-- much like in Scratch,
you can have custom puzzle pieces-- is going to have this custom behavior.
It's going to call printf passing in, hello, placeholder,
and then it's going to plug in whatever the user called.
>> So this is an example of what a computer scientist would
call abstraction or functional decomposition, which are just
fancy ways of saying-- Is if you like this high level idea,
like I want functionality that prints someone's name, absolutely you
can literally write printf and then pass in the arguments you want,
and the program will work, as it has since Wednesday.
But you can start to abstract away the notion of printing a name.
You can give it a name, like PrintName, and this
is this idea of layering from week 0.
>> Henceforth, I and you don't have to know or care how PrintName is implemented.
Yes it uses printf, maybe it doesn't, who knows what uses?
Who cares?
Now I'm talking up here, instead of down here.
And indeed, as our programs get more advanced and sophisticated,
we're going to keep taking for granted that lower level puzzle pieces exist.
Because we wrote them or someone else did, so
that we can then build on top of them.
Let's take a look at this variant, function one.
>> So this one's a little more advanced, but it turns out
that in CS50's library, there's only a GetInt function.
We didn't think, years ago, to implement a GetPositiveInt function.
And that's a little annoying because if you guys are writing a program wherein
you want to get a positive integer from the user,
you can absolutely use GetInt.
And you can absolutely check with the condition and maybe a loop
if that int is greater than 0 and yell at the user
if he or she doesn't give you a positive number.
But let's build this building block ourselves, a,
custom Scratch piece, if you will.
I'm going to have a program here that ultimately, I
want to be able to call GetPositiveInt, and I want to be
able to print out whatever that int is.
But this is abstracted away now.
It's just been given a high level name that says what it does,
which is wonderful because it's very intuitive now to read.
And if I do care what's underneath the hood, let me scroll down.
And it's a little intimidating at first, especially
if this is your first program, but let's take a look.
>> I'm no longer saying, void, because it turns out functions,
much like GetString, can return a value to me.
They don't just have to print to the screen,
they can actually hand me something back.
And whereas before PrintName, I didn't need anything back.
I needed the side effect of something showing up on the screen,
but I didn't need a human to hand me something back.
Here, with GetPositiveInt, like with GetInt,
I want to be handed something back.
So I'm saying not, void, on line 23, but int,
which says, this function that I am writing,
called GetPositiveInt is going to hand me back an integer, not nothing,
not void.
>> Meanwhile, it's going to take no inputs, so I've, kind of, reversed it.
I'm not giving GetPositiveInt any input, I want it to give me its output.
And then what happens now?
So here's how I can declare a variable.
I've done it outside of the loop, for reasons we'll eventually see,
but this just gives me 32 bits called, n,
and I've pre-determining them to store integer.
And here's that, do while construct, and this is why it's useful.
Literally do this, while n is less than 1.
So let's see what happens.
I print out, please give me a positive int.
I then get an int, using CS50's function and stored in n.
>> And then, what line of code probably gets executed next, logically?
Which line number?
Yeah, so 31.
You wouldn't know this until you've been told or sort of infer it,
but that's true.
It goes top to bottom and then keeps repeating.
So if I have typed in say, the number negative 1, is n less than negative 1?
Yeah.
Because negative 1 is less than 1.
So what should happen?
I'm going to do this while n is less than 1,
so I'm going to go back to line 28.
>> And each time-- and let's run this-- make function 1 to compile it,
and now dot slash function 1.
If I type negative 1, it's going to keep yelling at me
until I cooperate because each of my inputs is less than 1
and if it's while less than 1, I'm going to keep doing this.
If I finally give it a number like 50, thankfully, it says, thanks for the 50.
Why?
Because as soon as n is not less than 1, I stop getting stuck in this loop,
and this new keyword today, return, literally does that.
So I've just implemented, in a sense, the equivalent of GetString,
where I'm handing back to whoever is using me, some value.
It doesn't have to be a string, it's an int.
So a simple, quick example, but we'll soon
see some more sophisticated versions still.
In fact, let's take a look at a numeric one, which is called return.c.
And this one's actually a little simpler.
So this program's purpose in life-- let's compile and run it,
so make return, dot slash, return-- notice
the program simply cubes the value 2.
It's pretty stupid, it's hard code, it doesn't take any inputs,
but it does demonstrate another function that I've written myself.
So here, I've declared a variable, called x, of type int,
equal to the number 2, completely arbitrary.
This is just some fluffy printing.
It says x is now, such and such, cubing dot dot dot.
And the magic is apparently in line 21.
I'm calling a function called, cube, I'm handing it a sheet of paper
with the number 2 written on it, and what value, mathematically,
do I want to get out of it?
Just as a sanity check?
8.
Right?
I want 2 cubed back, 2 to the power of 3, so 8 back.
>> So where is cube implemented?
Well, notice it's implemented down here.
And just like before, logically, even though the syntax is probably
very new to many of you, I want this function
to hand me back a sheet of paper with an int on it.
So I have an int, the name is arbitrarily,
but conveniently called cube.
The input to it, is n of type integer, so that's
how I can pass in the number 2 on a sheet of paper.
And then it turns out C supports math, so you don't have x's for times,
you just use the asterisk for multiplication.
And this returns n times n times n, which is simply a cubed value.
>> So where are we going with all of this?
This is definitely a whirlwind tour, rest assured,
that in the super sections and in problem set 1,
you'll be walked through all this all the more.
And in problem set 1, we'll transition from the graphical world of Scratch
to something more command line in C. But we'll draw inspiration
from this here game from yesteryear, wherein
using C and the standard edition of the p set you'll implement Mario's pyramid.
And in the hacker edition of the p set, if you so choose to elect,
you will implement a bit more challenging pyramid with two peaks.
You'll also implement an algorithm, a greedy algorithm.
It turns out there's some interesting logic
behind the process of running a cashier's station
and actually handing someone back change.
There is an algorithm that's fairly straightforward, that you might even
grasp intuitively when you first read it-- realizing that's what I've always
done any time I've given someone some money back-- that allows you to always
minimize the number of paper notes or metal coins
that you're handing back to the user.
And this, of course, is compelling because if you go to CVS or whatnot,
you don't want to be handed a whole bunch of ones
or a whole bunch of pennies.
You want the fewest coins, probably, possible.
>> Finally, you'll also be challenged to dabble in the world of water
and actually get an appreciation for a mapping between rates of flow,
of like, water in a shower, just how much water is used.
And the allusion therein, will be this clip here,
which we'll end on for just 60 seconds, that
paints a picture of low-flow shower heads.
>> [VIDEO PLAYBACK]
-All right.
I got everything here.
I got the Cyclone F Series, Hydra, Jetflow, Stockholm
Supersteam, you name it.
>> -And what do you recommend?
>> -What are you looking for?
>> -Power man.
Power.
-Like Silkwood.
-That's for radiation.
-That's right.
-Now what is this?
-That's the Commando 450.
I don't sell that one.
>> -But that's what we want.
It's a commando 450.
>> -No believe me.
It's only used in the circus.
It's for elephants.
>> -I'll pay anything.
>> -What about Jerry?
>> -He couldn't handle that.
He's delicate.
Oh yeah.
[END PLAYBACK]
DAVID J MALAN: All right.
That's if for CS50.
We'll see you next week.
>> SPEAKER 1: [? Scully ?], [? Ian, ?] as far as this outro project,
what have you guys come up with?
>> SPEAKER 2: Well, we've given it a variety of thought,
and we think that the best way to--
>> SPEAKER 3: May I?
>> SPEAKER 2: Yeah.
By all means, actually.
>> SPEAKER 3: So I think we can sum up our idea
for the outros with one word-- nothing.
>> DAVID J MALAN: Nothing?
SPEAKER 3: Nothing.
DAVID J MALAN: What does that mean?
SPEAKER 3: The outros are about nothing.
SPEAKER 2: Well, I mean, in philosophy, I mean, nothing is always something.
SPEAKER 1: So what's-- what's the premise?
SPEAKER 3: So it's like life.
OK.
What did you do today?
>> DAVID J MALAN: I got up, had breakfast, and came to work.
>> SPEAKER 3: That's an outro.
SPEAKER 2: But, I mean, shouldn't something happen to him on the--
SPEAKER 3: No, no, no, no.
Nothing happens.
>> SPEAKER 1: So why are we watching?
>> SPEAKER 3: Because it's an outro for CS50.
>> DAVID J MALAN: Not yet.