CS16, Spring 2010

lab05: ("lab five")
Reusing functions, while loops on strings

Special note

You must attend lab this week, even if you finish the lab05 programming assignment in advance.

Here's why: in addition to the lab05 assignment below, there will be an additional activity—everyone will have an opportunity to play the "routing and deadlock" game (the game with the colored pieces of foam), and then there will be a worksheet with some problem solving exercises related to that game.

Playing the game, and completing the worksheet are both preparation for a later programming project.

Goals for this lab

By the time you have completed this lab, you should be able to:

Understand how to reuse functions between programs
Understand how to find the minimum and maximum value in an array
Understand how to find the index of the first occurence of a value in an array

This lab builds on lab04

This lab is an extension of lab04—so if you run into anything unfamiliar, review the material from lab04.

Continue with your same pair partner—
unless he/she is unavailable, or you failed to switch last week.

At the start of lab04, you were supposed to switch to a new pair partner. If you did so, and your partner is available again this week, please continue working with the same person.

If you didn't switch partners last week, your TA will try to help you do so this week.
If your pair from last week isn't available, your TA may pair you with a new partner.
If (and only if) you have a new partner for lab05—one you didn't work with on lab05—complete a new version of W02, and post to the lab04/05/06 pair partner forum on Gauchospace. Indicate that this is a new pairing for lab05.

Also keep in mind:

Pair programming is required for this lab, not optional

Step by Step Instructions

Step 0: Get together with your assigned lab partner and do the set up steps.

Choose a pilot and a navigator, and remember to switch often.

Check your PC—if you are in Cooper, there might be two mice attached. The navigator might be able to use the second mouse to help point things out, and feel a bit more connected to what is going on.

The driver should:

Bring up a terminal window and create a ~/cs16/lab05 directory
Copy files from my directory at ~pconrad/public_html/cs16/10S/labs/lab05/code/

Refer back to previous labs for clues about how to turn that directory name into a Unix command that will copy the files in to your lab05 directory.

Step 1: Reviewing what we did in lab04—and what we are going to do next

Assuming you successfully completed lab04, you did the following steps:

You started with the program countOddWithTests.c, and used test-driven development to develop two functions:
- int isOdd(int x); // return true if x is odd
- int countOdd(int *a, int n); // return the number of odd integers in a data file
Once both of the functions passed the tests, you then implemented exactly the same functions in the program countOddInFile.c.

Did you have the sense that you were working too hard—that it was inefficient to have to write the same function twice? I hope so—because if that thought occured to you, then you have what Larry Wall (author of Perl) calls one of the Three Virtues of a Programmer: Laziness.

Wall writes that Laziness is "the quality that makes you go to great effort to reduce overall energy expenditure."

Wouldn't it be better if the functions that we wrote and tested in the countOddWithTests.c program could be directly used in the countOddInFile.c program?

Well it turns out that we CAN do this.

Your first step this week will be to illustrate that by re-doing a step from lab04—yes, we are going to implement isOdd and countOdd one more time—but this time, we'll see that its the last time. From here on out, we'll be able to just write a function once, and then reuse it in as many programs as we want.

Step 2: Reviewing the files testOddFunctions.c, countOddInFile.c, oddFunctions.c

Three of this weeks files are a re-mix of the files we saw in lab04. Together with your lab partner, take a look at each one of them:

testOddFunctions.c contains almost everything from last week's countOddWithTests.c file
- except we left out the definitions of isOdd() and countOdd()
countOddInFile.c is almost the same as last week's countOddInFile.c
- except we left out the definitions of isOdd() and countOdd()
oddFunctions.c contains ONLY the stub function definitions for the isOdd() and countOdd() functions.
- Note that this file does not #include <stdio.h> because it contains no I/O—no printf, and no scanf

Since testOddFunctions.c does NOT contain the function definitions for isOdd and countOdd, if we try to compile it the way we've compiled programs so far, it doesn't work. Try this yourself—you should see output like the following:

-bash-3.2$ make testOddFunctions
cc     testOddFunctions.c   -o testOddFunctions
/tmp/ccOzuKZF.o: In function `main':
testOddFunctions.c:(.text+0xc4): undefined reference to `isOdd'
testOddFunctions.c:(.text+0xeb): undefined reference to `isOdd'
testOddFunctions.c:(.text+0x112): undefined reference to `isOdd'
testOddFunctions.c:(.text+0x139): undefined reference to `isOdd'
testOddFunctions.c:(.text+0x160): undefined reference to `isOdd'
/tmp/ccOzuKZF.o:testOddFunctions.c:(.text+0x187): more undefined references to `isOdd' follow
/tmp/ccOzuKZF.o: In function `main':
testOddFunctions.c:(.text+0x1b5): undefined reference to `countOdd'
testOddFunctions.c:(.text+0x1e3): undefined reference to `countOdd'
testOddFunctions.c:(.text+0x211): undefined reference to `countOdd'
collect2: ld returned 1 exit status
make: *** [testOddFunctions] Error 1
-bash-3.2$

But if instead, we take the compile command that make generates for us, namely:
cc testOddFunctions.c -o testOddFunctions

and add to it the file oddFunctions.c, like this, it works!

-bash-3.2$ cc oddFunctions.c testOddFunctions.c -o testOddFunctions

-bash-3.2$

We can then run the program with

./testOddFunctions

We can also compile the countOddInFile.c program the same way:

-bash-3.2$ cc oddFunctions.c countOddInFile.c -o countOddInFile

We can then run the program with ./countOddInFileor with
./countOddInFile TEST
to run the tests

Try compiling each of these programs using the command lines shown above, and running it.

What you should see is that the programs run but the tests fail. In the next step, we'll make the tests pass.

Step 3: Adding the `isOdd` and `countOdd` functions one last time

Now, one last time, enter the correct code for isOdd and countOdd in the file oddFunctions.c in place of the stubs.

Change the code at the top of the file too, to have your name(s) (you and your pair partner(s)) and the date.

Compile and run again, using the commands from Step 2 above. Now all the tests should pass!

And, also you should be able to run the countOddInFile program on a data file, e.g.:

-bash-3.2$ ./countOddInFile nums.dat 

(number of odd numbers in file appears here)

-bash-3.2$

When that works, you are ready to move on to the next step.

Step 4: Working with arrays of characters—C strings

In this step, we'll develop some functions that work with C strings.

Step 4a: Review of C Strings

You may remember from our reading in the first week a few things about C strings:

Literal strings are written with double quotes, e.g. "Gauchos"
In C, string variables are stored as arrays of char, e.g. char name[10];
They have one extra character at the end, '\0 ', which is not printed—it just marks the end of the string
Therefore, in memory, a string takes up one extra character:
- "Gauchos" consumes eight bytes of memory
- That's one each for 'G', 'a', 'u', 'c', 'h', 'o', 's', and '\0'

In Spring 2010:

This was part of homework H02, which referenced the online textbook, Oualline Chapter 5
If you want to review that now, it might be a good idea.

Step 4b: Understanding the code for this step

In your lab05 directory, you should find that you copied these files:

howManyEs.c
tdd.c
tdd.h

Each of those will be used in this step.

First, look at howManyEs.c. This file contains two functions:

the stub of a function int howManyEs(char *s); that counts the number of Es in a string (i.e. a char *)
a function int testCountEs(); that runs several tests on howManyEs.

From here on out, we'll often follow this pattern—developing a stub along with its test function.

You may also see that inside howManyEs, there is a line:

#include "tdd.h"

This looks different from #include directives we've seen in the past—it uses "" instead of <>. This tells the compiler to look for the tdd.h file in the current directory instead of looking for it in the location of the standard C library functions.

So, look next at the tdd.h file. We see that it contains mainly function prototypes for lots of functions related to test-driven development. By putting the function prototypes for test-driven development functions into a header file, we don't have to keep copying those functions into every file where we want to work with them—we just do the #include, and then we can use those functions.

After the funciton prototypes, there are four unusual looking lines at the end of tdd.h that look like this:

#define ASSERT_TRUE(assertion)  \
   assertTrueWithFileLine(__FILE__,__LINE__,#assertion,assertion)
   
#define CHECK_EXPECT_INT(check,expect) \
  checkExpectIntWithFileAndLine(__FILE__,__LINE__,#check,check,expect)

These are called macro definitions—they are used to allow us to automatically put include the filename and line number of our tests in the messages that are printed when a test fails. This gives us much nicer error messages!

For example, when we want to do a test, we can just write lines like these:

failures += CHECK_EXPECT_INT(howManyEs("Santa"),0);
failures += CHECK_EXPECT_INT(howManyEs("Barbara"),0);

and what we get back is this nice error message when a test fails that tells us exactly where to look for the failed test!

TEST FAILED: howManyEs.c line 35 howManyEs("Santa") got -42 expected 0
TEST FAILED: howManyEs.c line 36 howManyEs("Barbara") got -42 expected 0

...

The name of the file, line number, and the label for the tests gets generated automatically.

We will not have any questions on the exams in this course about macro definitions—but if you want to know what is going on with those lines of code, see the details in the box below.

If you are curious to learm more about Macros (optional):

CHECK_EXPECT_INT (all capitals) can be used in place of checkExpectInt (camel case).
It looks like a function call when we use it, but in fact, what happens is that when we compile, right at the beginning of the compilation process, CHECK_EXPECT_INT(check, expect) is replaced with the code on the next line—a function call that has five parameters.
Three of those parameters are __FILE__, __LINE__, and #check. These get replaced as follows:
- __FILE__ is the the filename of the C source file (e.g. "howManyEs.c"), as a string.
- __LINE__ is the line number where the CHECK_EXPECT_INT call occurs
- #check is the check expression as a string, e.g. "howManyEs(\"Goleta\")"
Passing those into the function checkExpectIntWithFileAndLine(__FILE__,__LINE__,#check,check,expect) allows that function to print much more helpful error messages—and we no longer have to put labels on our test cases—they get generated for us automatically.

If you want to learn more about macros, you may read Section 4.8 in the Etter textbook, as well as reading the comments in the tdd.h file, or researching on your own (do an internet search on "C Macros" or "C Preprocessor".

Again: Macros will NOT be covered on the exams in this course—we are using them here only to make testing a bit easier and nicer.

The function definitions are placed into the file tdd.c. Look at that file now, and you'll see that there is a function definition for each of the function prototypes in tdd.h.

Finally, there is one more file: testHowManyEsDriver.c. which contains a very short main program. This file is just the "driver" (see p. 152 in your textbook) that calls the testHowManyEs() function from howManyEs.c. Every program has to have exactly one main, and this is the main we'll be using.

Many programmers consider it good style to have a main program that is very short. In such programs, the interesting detailed work is mostly done in functions, each of which has been tested separately. By building a short main from smaller functions, we can be more productive—for at least two reasons:

software reuse—we don't have to keep re-coding the same thing over and over
software testing—if the small components we are putting together have already been tested separtely, they are less likely to fail when we put them together.

Now we are ready to get on with the coding:

Step 4c: Compiling the stub, and seeing the tests fail

To compile, use this command:

cc howManyEs.c tdd.c testHowManyEsDriver.c -o testHowManyEsDriver

This combines

the code we want to test (howManyEs.c) with
the test-driven development functions (such as checkExpectInt(), etc. which come from tdd.c) and
the file that contains our main (testHowManyEsDriver.c).

The executable is output into the file testHowManyEsDriver—that's what the -o testHowManyEsDriver part does.

We can then run the program with ./testHowManyEsDriver, and we see this:

-bash-4.1$ ./testHowManyEsDriver
TEST FAILED: howManyEs.c line 35 howManyEs("Santa") got -42 expected 0
TEST FAILED: howManyEs.c line 36 howManyEs("Barbara") got -42 expected 0
TEST FAILED: howManyEs.c line 37 howManyEs("Goleta") got -42 expected 1
TEST FAILED: howManyEs.c line 38 howManyEs("Reseda") got -42 expected 2
TEST FAILED: howManyEs.c line 39 howManyEs("El Centro") got -42 expected 2
TEST FAILED: howManyEs.c line 40 howManyEs("Eureka") got -42 expected 2
TEST FAILED: howManyEs.c line 41 howManyEs("Emeryville") got -42 expected 3
 :-(  7 tests FAILED! 
-bash-4.1$

Notice the nice labels on the failed tests!

Next, replace the stub with this code. Note that we can use a while loop to check every element of a string, since a string always ends with a '\0' character.

  int i=0;
  int count=0;
  
  // we don't know how long the string is
  // but we do know it ends with '\0'
  while (s[i]!='\0')
    {
      // count the e's
      if (s[i]=='e')
        count++;

      i++; // if you don't have this line, infinite loop!
    }

  return count;

After putting this code into the howManyEs function, you should get this:

-bash-4.1$ ./testHowManyEsDriver 
 test passed: howManyEs.c line 35 howManyEs("Santa") got 0
 test passed: howManyEs.c line 36 howManyEs("Barbara") got 0
 test passed: howManyEs.c line 37 howManyEs("Goleta") got 1
 test passed: howManyEs.c line 38 howManyEs("Reseda") got 2
TEST FAILED: howManyEs.c line 39 howManyEs("El Centro") got 1 expected 2
TEST FAILED: howManyEs.c line 40 howManyEs("Eureka") got 1 expected 2
TEST FAILED: howManyEs.c line 41 howManyEs("Emeryville") got 2 expected 3
 :-(  3 tests FAILED! 
-bash-4.1$

That shows that some of the tests are passing, but others are not. Your job now is to fix this so that all the tests pass—when that happens, the output will look like this. From the tests, we can infer something about how upper and lower case are supposed to be handled.

This highlights another important function of test cases
Not only do they test our code but they also can be used to infer the intended semantics of our code
That's a fancy way of saying that we can look at the test cases to figure out what the code is supposed to do.

-bash-4.1$ ./testHowManyEsDriver 
 test passed: howManyEs.c line 35 howManyEs("Santa") got 0
 test passed: howManyEs.c line 36 howManyEs("Barbara") got 0
 test passed: howManyEs.c line 37 howManyEs("Goleta") got 1
 test passed: howManyEs.c line 38 howManyEs("Reseda") got 2
 test passed: howManyEs.c line 39 howManyEs("El Centro") got 2
 test passed: howManyEs.c line 40 howManyEs("Eureka") got 2
 test passed: howManyEs.c line 41 howManyEs("Emeryville") got 3
 :-)  All tests passed! 
-bash-4.1$

Hints:

If you want to check whether an int variable x is equal to 3 or equal to 5, you can write:
if (x==3 || x==5)
Note that all of the following will compile, but are INCORRECT
- if (x==3 || 5)
- if (x==3, 5)
Also watch out for the = vs == bug—the following is also INCORRECT
- if (x=3 || x=5)

Of course, this exercise has nothing to do with x, 3 or 5—you are counting Es. Neverthless, I think these hints will come in handy.

When all your tests pass, move on to step 5

Step 5: Generalizing the function

Your job in this step is to add two more files to your lab05 directory.

The first file will be similar to the howManyEs.c file, but will be called charOccurs.c

Instead of counting the number of times the letter 'e' appears (upper or lowercase), you will be generalizing the function so that you can pass in any character (even a space, or a digit, or a punctuation mark) and the function will return how many times that character occurs.

charOccurs.c should #include "tdd.h", and then have function defintions for:

int charOccurs(char *s, char c); // return how many times c occurs in s
int testCharOccurs(); // test cases for charOccurs

You should include the following test cases—as well as at least 5 more of your own choosing:

failures += CHECK_EXPECT_INT(charOccurs("Santa",'a'),2);
failures += CHECK_EXPECT_INT(charOccurs("Barbara",'b'),1); // case sensitive
failures += CHECK_EXPECT_INT(charOccurs("Barbara",'B'),1); // case sensitive
failures += CHECK_EXPECT_INT(charOccurs("Barbara",'x'),0); 
failures += CHECK_EXPECT_INT(charOccurs("Santa Barbara",' '),1); 
failures += CHECK_EXPECT_INT(charOccurs("San Luis Obispo",' '),2); 
failures += CHECK_EXPECT_INT(charOccurs("rrooyyggbbp ",' '),1); 
failures += CHECK_EXPECT_INT(charOccurs("rrooyyggbbp ",'r'),2); 
failures += CHECK_EXPECT_INT(charOccurs("rrooyyggbbp ",'g'),2); 
failures += CHECK_EXPECT_INT(charOccurs("rrooyyggbbp ",'p'),1);

The second file will be similar to testHowManyEsDriver.c, but will be called testCharOccursDriver.c—it will have the same function as testHowManyEsDriver.c but will call on testCharOccurs() instead of testHowManyEs.c

You should compile an executable program ./testCharOccursDriver using a compile command similar to the one from the previous step for ./testHowManyEsDriver—this time you want to combine charOccurs.c, tdd.c, and testCharOccursDriver.c.

When your ./testCharOccursDriver program passes all of the tests I've specified above, plus those of your own making—and could conceivably pass any other reasonable tests I could throw at it—then you are ready to script this week's assignment.

Step 6: Scripting your assignment

Before doing the transcript—look over the grading rubric at the bottom of this page. Make sure you've done everything properly to maximize your grade.

In this step, we create a "transcript" of your work. We only do this after everything else is finished, and you are sure you have a good working product.

Now, to create your script:

Use the proper form of the cd command to put yourself in your ~/cs16/lab05 directory (if you aren't already there)
Type script lab05.txt
(By now you know what that does.)
Type pwd to show what directory you are in.
Type ls to show what files you have.
Now for each of the executable programs you worked on this week—testOddFunctions, countOddInFile, testHowManyEsDriver, and testCharOccursDriver—do the following steps:
1. Carefully—type rm filename to remove that executable.
2. Type the command needed to compile your program. (This may be a "make" command, or it may be something more complex if your program is split across multiple files.)
  - There should be no warnings and no errors—and since you did the rm command, it should NOT say:
    filename is up to date
3. Now, run the program to show that it works properly.
  
  In some cases, you can do that with a single run—e.g. programs that just run test cases and have no input. In other cases—e.g. if the program is interactive (printf/scanf), or has command line parameters, or reads input from a file—you may need to run it several times.
  
  I will expect you to use good judgement in deciding how many times to run the program to demonstrate that it works properly. If you are unsure, ask your TA or instructor for guidance.
Once you've done items 5a,5b,5c in the list above for each of this week's executable programs, type exit to stop the recording of commands and responses into lab05.txt

When finished, type ls one more time, and you should see a new file in your lab05 directory called lab05.txt.

Use this command to list out the contents of that file:

more lab05.txt

If it all looks ok, you are ready to submit!

Step 7. Submit your assignment using the turnin program on CSIL

To submit your assignment, you need to be in the ~/cs16 directory—one level higher than the previous step (use cd ..)

When you are in inside your cs16 directory, you are ready for the turnin step.

Type the following at the prompt:

turnin lab05@cs16 lab05

If you need detailed information about how turnin works, consult the instructions in lab00 through lab02.

Evaluation and Grading (300 pts total)

Mechanics:
- 30 points: submission is on time and follows submission instructions
  - (i.e. is done via turnin by the Due Date, and contains the required files)
- 20 points: The .c files submitted have good header comments
  - On first line with name "cs16 lab05" and date, and your name, and that of your pair partner(s)
  - This is only necessary in files that you and your partner modified or created
  - Unmodified files (e.g. tdd.h, tdd.c) do not need to have your name/date/etc.
- 50 points: transcript file contains everything asked for in the instructions
  - especially important is that the script contains each of the tests required
Programming Tasks for oddFunctions.c (points for correctness and style)
- 15 points: correct implementation of isOdd
- 20 points: correct implementation of countOdd
  - -10 points if you didn't reuse the isOdd function inside your countOdd function
- 15 points: indentation, variables names, comments, show understanding of good programming style
Programming Tasks for howManyEs.c
Programming Tasks for charOccurs.c and testCharOccursDriver.c

Due Date: You should try to complete this assignment by the end of the discussion section for which it was assigned (04/30/2010)

If you are unable to complete it by the end of your discussion section you may continue to work on it through the week—ideally before the start of next week's discussion section.

It will be accepted without late penalty until 5pm on Friday 05/07/2010.

Late assignments will only be accepted (with 20 point penalty) through 5PM on Wednesday 05/12/2010

After 5PM Wednesday 05/12/2010, a zero will be recorded, and the only option is to make up the points via extra credit.

Copyright 2010, Phillip T. Conrad, CS Dept, UC Santa Barbara. Permission to copy for non-commercial, non-profit, educational purposes granted, provided appropriate credit is given; all other rights reserved.