## Week 2 Monday Andrew Sellergren ### Announcements and Demos (0:00-4:00, 17:00-25:00) + This is CS50. + This is Shuttleboy: 617-BUG-CS50. [Shuttleboy](http://shuttleboy.cs50.net) is an app that allows you to find out the times of the next Harvard shuttle. You can also interact with Shuttleboy via SMS at 41411 SBOY. Simply provide an origin and a destination, for example "41411 SBOY boylston quad." Shuttleboy is a project that David first wrote after taking CS51. CS50 Voice is an *application programming interface* (API) that allowed Shuttleboy to be ported to a phone number. An API is a framework that allows others to interact with code they didn't necessarily write. Shuttleboy has its [own API](https://manual.cs50.net/Shuttleboy_API) which allows you to pull shuttle data programmatically. + When in doubt, run `sudo yum -y update appliance50` to fix any issues you might have with the Appliance. This is analogous to getting automatic updates on your operating system. + Bring your laptops to Section. If you don't have a laptop, send David an e-mail and we'll figure something out. Part of Section will be spent walking through conceptual material (e.g. the questions section of the most recent Problem Set) and part will be spent completing hands-on programming exercises. These exercises will be bite-size problems that give you a chance to practice syntax. To complete these exercises, we'll use a web-based editor and compiler called CS50 Spaces. + Supersections will be held this week, Monday and Tuesday. Check the [course website](https://www.cs50.net/) for times and locations. + If you need to change your section, go to the [same URL](http://cs50.net/section) as before. + Last week, we had 40 questions asked and answered during lecture through [CS50 Discuss](http://cs50.net/discuss). It seemed to work well so we're gonna continue to try it! + Generally Problem Sets will be returned within a week. Problem Set 0 and Problem Set 1 will be a little delayed as sections get shuffled around. + Academic honesty is an issue we take very seriously in CS50. Last year, we sent 35 students to the Ad Board. Every year, we send about 3% of the class to the AdBoard. This is not for lack of clarity of our policies: there's an entire page in each problem set specification outlining them. Know that you are encouraged to talk to your classmates about your work, but when it comes time to talk about code, you should only speak in English or in pseudocode, not in C or PHP or JavaScript, etc. Hopefully this is obvious, but using code from github:gist and paying someone to complete your problem sets for you are both strictly forbidden. It's not very hard for us to figure out that your work isn't your own: we have software that does it for us. We do this for the sake of the vast majority of you whose work is entirely your own! If you're strapped for time, use a late day. If you have no late days left, e-mail one of the staff members and we'll work something out. ### Bugs (4:00-17:00) + To get us warmed up for the day, let's take a look at a program that has an interesting bug: /**************************************************************************** * buggy1.c * * David J. Malan * malan@harvard.edu * * Should print 10 asterisks but doesn't! * Can you find the bug? ***************************************************************************/ #include int main(void) { for (int i = 0; i <= 10; i++) printf("*"); return 0; } + Recall that anything between the `/*` and `*/` at the top is a comment and won't be interpreted as source code by the compiler. Comments are notes that the programmer writes to clarify what the program does and how the code works. + The line `#include ` asks the compiler to include a file `stdio.h` which contains the declarations of useful functions like `printf`. To include the file, the compiler more or less copies and pastes its contents at the top of our source code. + Starting to count from 0 is a programming convention. To print 10 asterisks, then, we can't iterate all the way through 10, we have to stop at 9. Thus, our termination condition `i <= 10` should really be `i < 10`. + The three parts of a for loop are the initialization (declaring a counter variable and setting it to its start value), the termination condition (the loop continues as long as this condition evaluates to true), and the incrementation (the updating of the counter variable on each iteration of the loop). + If we change `i++` to `i--` in the above, we'll iterate seemingly forever. At some point, we actually might iterate below negative 2 billion and wrap around to positive 2 billion, in which case the loop would actually stop. `i++` and `i--` are *syntactic sugar*, or shorthand. They are really short for `i = i + 1` and `i = i - 1` respectively. + We compile this program manually by running `clang buggy1.c` in our terminal window. When we try to run `./buggy1`, we get a "No such file or directory" error. Remember that unless we provide the `-o` flag, the default name for our program will be `a.out`. + We face another bug in `buggy2.c`: /**************************************************************************** * buggy2.c * * David J. Malan * malan@harvard.edu * * Should print 10 asterisks, one per line, but doesn't! * Can you find the bug? ***************************************************************************/ #include int main(void) { for (int i = 0; i <= 10; i++) printf("*"); printf("\n"); return 0; } + This version is supposed to print one asterisk per line. Instead, we get all asterisks on the same line. The bug here is that we need curly braces around the two lines that are meant to be executed on each iteration of the for loop. We can only omit the curly braces if there is a single line of code that is meant to be part of the for loop. Note that indenting the two lines has no functional effect. + Question: why did you type `"ls"` instead of just `ls`? As a workaround for a bug in the Appliance in which terminal output was printed as black on a black background. This bug has been fixed in the latest version of the Appliance. + Question: where does `make` come from? It's a program built in to Linux. + Question: how does `make` know what source code file to use? When you type `make buggy1`, it assumes that the name of the source code file is `buggy1.c`. `make` has the convenience of passing some command line flags to `clang` for us, including `-o buggy1`. ### From Last Time (25:00-28:00) + In Scratch and in C, we have the ability to place forks in a program's logic. In C, we can use if-else statements to do so. Within these conditions, we use Boolean expressions (which evaluate to true or false) to determine which direction the program should take. We can combine if conditions using `&&` ("and") and `||` ("or"). We also have switch statements at our disposal. ### More with Loops (28:00-60:00) + What's the difference between for and while loops? In a for loop, the initialization and updating of the counter variable is handled within the parentheses. In a while loop, we have to do this ourselves outside of the parentheses. + To refresh ourselves with the syntax for loops, we'll start a new program from scratch: #include int main(void) { for (int i = 0; i < 10; i++) printf("*"); printf("\n"); return 0; } + As before, this program prints 10 asterisks plus a single newline character. If we were to convert this for loop to a while loop, it would begin like so: #include int main(void) { while (i < 10) printf("*"); printf("\n"); return 0; } + Already there's a problem though. We haven't declared a variable named `i`. Indeed, the compiler yells at us for "unddeclared identifier." In contrast to languages like Python and Ruby, C requires us to explicitly declare variables and their types. We can fix this compiler error by declaring `i`: #include int main(void) { int i; while (i < 10) printf("*"); printf("\n"); return 0; } + Now, however, we get a compiler error for "variable uninitialized when used here." This makes sense since we haven't specified what the starting value for `i` is. The fix is simple: #include int main(void) { int i = 0; while (i < 10) printf("*"); printf("\n"); return 0; } + When we compile and run this program, we get asterisks printed out to the screen indefinitely because we don't ever update the value of `i`. We fix that like so: #include int main(void) { int i = 0; while (i < 10) { printf("*"); i++; } printf("\n"); return 0; } + Note that we now need curly brace since we have more than one line to be executed within the while loop. This program should now work as intended! + for loops have the advantage of being explicit, but soon we'll see that while loops are more useful in other contexts like lists and hash tables. A third type of loop, the do-while loop, is useful when we want to ensure that some piece of code is executed at least once. One use case for this is checking user input. Let's try this out: #include int main(void) { do { printf("Give me an int: "); int i = GetInt(); } while (i < 0 || i > 10) printf("Thanks, i is %d\n", i); return 0; } + If this works as intended, we'll ask the user for a number 0 through 10 and print it out. When we compile it, though, we get the same "undeclared identifier" error. This brings us to a discussion of *scope*. We've declared a variable inside the curly braces, which C interprets to mean that we only need `i` while we're in the loop. When we get to the line to print out the value of `i`, the operating system has already forgotten about it. We say that `i` only exists within the scope of the loop. + The fix is to declare `i` outside the curly braces: #include int main(void) { int i; do { printf("Give me an int: "); i = GetInt(); } while (i < 0 || i > 10) printf("Thanks, i is %d\n", i); return 0; } + Okay, we got rid of the "undeclared identifier" error, but we now run into an "implicit declaration" error. We again forgot to include the CS50 Library, which has the definition of `GetInt`. + When we compile and run this program, we can try entering numbers outside the range 0 through 10, in which case the message "Give me an int" is printed. When we enter "foo," however, we get the message "Retry." This first message comes from our do-while loop, but the second message comes from `GetInt`. + We'll run into the same problem with scope if we try to reuse the counter variable from a for loop: #include int main(void) { for (int i = 0; i < 10; i++) printf("*"); printf("i is now %d", i); return 0; } + Although there are no curly braces this time, the variable `i` is still only valid inside of the for loop. #### 99 Bottles of Beer + What better way to demonstrate the use of loops and functions than with an annoying, repetitive song? The chorus of "99 Bottles of Beer" is repeated for every number counting down from 99, so it provides a perfect opportunity to explore looping constructs. + `beer1.c` even takes user input to know how many bottles of beer there are: /**************************************************************************** * beer1.c * * David J. Malan * malan@harvard.edu * * Sings "99 Bottles of Beer on the Wall." * * Demonstrates a for loop (and an opportunity for hierarchical * decomposition). ***************************************************************************/ #include #include int main(void) { // ask user for number printf("How many bottles will there be? "); int n = GetInt(); // exit upon invalid input if (n < 1) { printf("Sorry, that makes no sense.\n"); return 1; } // sing the annoying song printf("\n"); for (int i = n; i > 0; i--) { printf("%d bottle(s) of beer on the wall,\n", i); printf("%d bottle(s) of beer,\n", i); printf("Take one down, pass it around,\n"); printf("%d bottle(s) of beer on the wall.\n\n", i - 1); } // exit when song is over printf("Wow, that's annoying.\n"); return 0; } + Notice that we write "bottle(s)" so that our grammar is correct when we get down to 1. We could, however, handle this singular case using an if statement. + After asking the user for the number of bottles, we actually do some validation of the input. If the user enters a number less than 1, we exit the program altogether. We do this with the statement `return 1`. Recall that non-zero return values for `main` indicate errors. By returning one here, we shortcircuit the program so that nothing below this line is executed. + Once we have a valid number, we use it as our counter variable. This time, we're counting down rather than up. On each iteration of the loop, we substitute the counter variable (or sometimes one less than the counter variable) into the chorus. + If we accidentally used `i >= 0` as our termination condition, we would encounter an off-by-one error. The last verse would include a negative number of bottles of beer, which doesn't make sense. + `beer2.c` makes some improvement on our current design: /**************************************************************************** * beer2.c * * David J. Malan * malan@harvard.edu * * Sings "99 Bottles of Beer on the Wall." * * Demonstrates a while loop (and an opportunity for hierarchical * decomposition). ***************************************************************************/ #include #include int main(void) { // ask user for number printf("How many bottles will there be? "); int n = GetInt(); // exit upon invalid input if (n < 1) { printf("Sorry, that makes no sense.\n"); return 1; } // sing the annoying song printf("\n"); while (n > 0) { printf("%d bottle(s) of beer on the wall,\n", n); printf("%d bottle(s) of beer,\n", n); printf("Take one down, pass it around,\n"); printf("%d bottle(s) of beer on the wall.\n\n", n - 1); n--; } // exit when song is over printf("Wow, that's annoying.\n"); return 0; } + Here we use a while loop instead of a for loop. Also, we get rid of the variable `i` and simply use the user's input as our counter variable. Functionally, this program is identical to `beer1.c`. Which is better? `beer2.c` uses less space (one less `int` needs to be stored). `beer1.c` has the advantage, however, of not altering the user's input. If we wanted to use that later in the program, perhaps to print "Thanks for playing 99 Bottles of Beer," we can't in `beer2.c` because we decremented that number all the way to 0. To be honest, there's no right answer as to which program is better. They have different designs, both of which get the job done. + Let's handle the annoying grammar issue that we avoided previously by writing "bottle(s)": /**************************************************************************** * beer1.c * * David J. Malan * malan@harvard.edu * * Sings "99 Bottles of Beer on the Wall." * * Demonstrates a for loop (and an opportunity for hierarchical * decomposition). ***************************************************************************/ #include #include int main(void) { // ask user for number printf("How many bottles will there be? "); int n = GetInt(); // exit upon invalid input if (n < 1) { printf("Sorry, that makes no sense.\n"); return 1; } // sing the annoying song printf("\n"); for (int i = n; i > 0; i--) { if (i == 1) { string s1 = "bottle"; // for 1 bottle string s2 = "bottles"; // for 0 bottles } else if (i != 1) { string s1 = "bottles"; // for plural bottles string s2 = "bottles"; // for plural bottles } // sing verses printf("%d bottle(s) of beer on the wall,\n", i, s1); printf("%d bottle(s) of beer,\n", i, s1); printf("Take one down, pass it around,\n"); printf("%d bottle(s) of beer on the wall.\n\n", i - 1, s2); } // exit when song is over printf("Wow, that's annoying.\n"); return 0; } + Note that we can add single-line comments at the end of lines of code using `//`. What's wrong with the above, though? We're trying to use `s1` and `s2` outside their scope, which is inside the if conditions. We need to declare them outside the curly braces: /**************************************************************************** * beer1.c * * David J. Malan * malan@harvard.edu * * Sings "99 Bottles of Beer on the Wall." * * Demonstrates a for loop (and an opportunity for hierarchical * decomposition). ***************************************************************************/ #include #include int main(void) { // ask user for number printf("How many bottles will there be? "); int n = GetInt(); // exit upon invalid input if (n < 1) { printf("Sorry, that makes no sense.\n"); return 1; } // sing the annoying song printf("\n"); for (int i = n; i > 0; i--) { string s1, s2; if (i == 1) { s1 = "bottle"; // for 1 bottle s2 = "bottles"; // for 0 bottles } else if (i != 1) { s1 = "bottles"; // for plural bottles s2 = "bottles"; // for plural bottles } // sing verses printf("%d bottle(s) of beer on the wall,\n", i, s1); printf("%d bottle(s) of beer,\n", i, s1); printf("Take one down, pass it around,\n"); printf("%d bottle(s) of beer on the wall.\n\n", i - 1, s2); } // exit when song is over printf("Wow, that's annoying.\n"); return 0; } + We can declare multiple variables of the same type on a single line simply by separating them with commas. There's still a bug, though. In the second-to-last verse, we write "1 bottles of beer." Looks like there's more than one corner case we need to handle: where `i` is 1 and where `i` is 2. Let's try this: /**************************************************************************** * beer1.c * * David J. Malan * malan@harvard.edu * * Sings "99 Bottles of Beer on the Wall." * * Demonstrates a for loop (and an opportunity for hierarchical * decomposition). ***************************************************************************/ #include #include int main(void) { // ask user for number printf("How many bottles will there be? "); int n = GetInt(); // exit upon invalid input if (n < 1) { printf("Sorry, that makes no sense.\n"); return 1; } // sing the annoying song printf("\n"); for (int i = n; i > 0; i--) { string s1, s2; if (i == 1) { s1 = "bottle"; // for 1 bottle s2 = "bottles"; // for 0 bottles } else if (i == 2) { s1 = "bottles"; // for 2 bottles s2 = "bottle"; // for 1 bottle } // sing verses printf("%d bottle(s) of beer on the wall,\n", i, s1); printf("%d bottle(s) of beer,\n", i, s1); printf("Take one down, pass it around,\n"); printf("%d bottle(s) of beer on the wall.\n\n", i - 1, s2); } // exit when song is over printf("Wow, that's annoying.\n"); return 0; } + Compiling and running this program gives us a *segmentation fault*. What this means is that your program has tried to access memory that it doesn't own. We've given `s1` and `s2` values in the cases where `i` is equal to 1 or 2, but not in all other cases. We need to add an else condition: /**************************************************************************** * beer1.c * * David J. Malan * malan@harvard.edu * * Sings "99 Bottles of Beer on the Wall." * * Demonstrates a for loop (and an opportunity for hierarchical * decomposition). ***************************************************************************/ #include #include int main(void) { // ask user for number printf("How many bottles will there be? "); int n = GetInt(); // exit upon invalid input if (n < 1) { printf("Sorry, that makes no sense.\n"); return 1; } // sing the annoying song printf("\n"); for (int i = n; i > 0; i--) { string s1, s2; if (i == 1) { s1 = "bottle"; // for 1 bottle s2 = "bottles"; // for 0 bottles } else if (i == 2) { s1 = "bottles"; // for 2 bottles s2 = "bottle"; // for 1 bottle } else { s1 = "bottles"; // for plural bottles s2 = "bottles"; // for plural bottles } // sing verses printf("%d bottle(s) of beer on the wall,\n", i, s1); printf("%d bottle(s) of beer,\n", i, s1); printf("Take one down, pass it around,\n"); printf("%d bottle(s) of beer on the wall.\n\n", i - 1, s2); } // exit when song is over printf("Wow, that's annoying.\n"); return 0; } + A quick compile and run shows that we've fixed the segmentation fault and the grammar problem. However, we've done it in a rather inelegant way. We can actually represent this logic in a much more succinct way: /**************************************************************************** * beer1.c * * David J. Malan * malan@harvard.edu * * Sings "99 Bottles of Beer on the Wall." * * Demonstrates a for loop (and an opportunity for hierarchical * decomposition). ***************************************************************************/ #include #include int main(void) { // ask user for number printf("How many bottles will there be? "); int n = GetInt(); // exit upon invalid input if (n < 1) { printf("Sorry, that makes no sense.\n"); return 1; } // sing the annoying song printf("\n"); for (int i = n; i > 0; i--) { string s1 = (i == 1) ? "bottle" : "bottles"; string s2 = (i == 2) ? "bottles" : "bottle"; // sing verses printf("%d bottle(s) of beer on the wall,\n", i, s1); printf("%d bottle(s) of beer,\n", i, s1); printf("Take one down, pass it around,\n"); printf("%d bottle(s) of beer on the wall.\n\n", i - 1, s2); } // exit when song is over printf("Wow, that's annoying.\n"); return 0; } + Note that the original way of writing this logic is not incorrect and is not bad design. However, clearly this way of writing this logic is more readable. `(a) ? x : y` is an operator which says "if a is true, then x, else y". ### Functions (60:00-72:00) + Let's write a program that simply increments the value of a variable: #include int main(void) { int x = 2; printf("x is %d\n", x); x++; printf("x is %d\n", x); return 0; } + Quite easily, we can change this into a program that cubes the value of a variable: #include int main(void) { int x = 2; printf("x is %d\n", x); x = x * x * x; printf("x is %d\n", x); return 0; } + There's an opportunity here for refinement. We can write a function which cubes its input: #include int main(void) { int x = 2; printf("x is %d\n", x); x = cube(x); printf("x is %d\n", x); return 0; } int cube(int input) { int output = input * input * input; return output; } + The definition of function `cube` resembles our usual definition of `main`: we specify the return type as `int` (just like `main`) and we specify the argument as `int input` (unlike `void` for `main`). + Compiling this program gives us an "implicit declaration" error. The problem is that the C compiler reads your code from top to bottom. When it encounters the keyword `cube`, the function itself hasn't been defined yet. We can fix this in two ways: we can move the definition of `cube` above the definition of `main` or we can declare a function *prototype* above `main`. The function prototype is simply the following: // prototype int cube(int input); The prototype simply specifies the return type, name, and arguments of the function. With this above `main` and the actual definition of `cube` at the bottom, the program compiles and runs. #### 99 Bottles of Beer (Reprise) + With this ability to write functions in hand, let's return to our "99 Bottles of Beer" problem and put the chorus into its own function: /**************************************************************************** * beer4.c * * David J. Malan * malan@harvard.edu * * Sings "99 Bottles of Beer on the Wall." * * Demonstrates hierarchical decomposition and parameter passing. ***************************************************************************/ #include #include // function prototype void chorus(int b); int main(void) { // ask user for number printf("How many bottles will there be? "); int n = GetInt(); // exit upon invalid input if (n < 1) { printf("Sorry, that makes no sense.\n"); return 1; } // sing the annoying song printf("\n"); for (int i = n; i > 0; i--) { chorus(i); } // exit when song is over printf("Wow, that's annoying.\n"); return 0; } /** * Sings about specified number of bottles. */ void chorus(int b) { // use proper grammar string s1 = (b == 1) ? "bottle" : "bottles"; string s2 = (b == 2) ? "bottle" : "bottles"; // sing verses printf("%d %s of beer on the wall,\n", b, s1); printf("%d %s of beer,\n", b, s1); printf("Take one down, pass it around,\n"); printf("%d %s of beer on the wall.\n\n", b - 1, s2); } + The function `chorus` has a return type of `void`, which means it doesn't return anything. Rather, it only has a *side effect* of printing something. Functionally, this program is equivalent to our earlier one, but it's perhaps a little more readable.