Laboratory 1: Getting started in C

2. Native types, printf()

C is a strongly typed language. That is, all variables have a type that identifies the kind of data they store. Types include integers, floating point numbers, and characters. Every variable has a value which is the data it stores. A variable's type is specified at its creation.

The value of a variable can change, but its type can not. Thus C is a statically typed language. This is fundamentally different to Python, where variables could contain different things during their lifetime.

The advantages usually claimed for strong, static typing are:

1. Explicit statement of intent: you tell the compiler and people reading the code what kind of data you are manipulating.
2. Error prevention at compile time: if you violate your stated intent, the compiler lets you know right away.

Variables and output

#include <stdio.h>
 
int main( void )
{
  int i = 0;
  float pi = 3.14159;
  char c = '+';
 
  // this is a comment
  printf( "here: %d %f %c\n", i, pi, c );
 
  return 0;
}

Which produces this on stdout:

here: 0 3.141590 +

3. Input and pointers

Now let's look at a C program that inputs an integer from the user and echoes it back:

#include <stdio.h>
 
int main( void )
{
  int i = 0;
 
  printf("Enter an integer: ");
 
  scanf( "%d", &i );
  printf( "Your integer was: %d\n", i );
 
  return 0;
}
 

There are two new things on line 9. The function scanf() is roughly the inverse of printf(), reading text from standard input, a text stream directly analogous to standard output but in the other direction. Text from the shell is delivered to a program's standard input ("stdin" for short) and is queued there until the program chooses to read it. The shell program and the computer's operating system work together to make this happen. We will see later that this simple scheme can be very powerful.

The arguments to scanf() are a format string, similar to that of printf(), which is a template to be matched against the input. The format string specifiers (starting "%") indicate that the text in this place in the input string should be interpreted as a specific type, and stored in the variable indicated by the next argument. A variable of a suitable type must be supplied following the format string, and they are used in order.

The format string argument to scanf "%d" says we should interpret the entire line as a decimal integer. Whitespace around the number is ignored.

Since scanf() is expecting a decimal integer, we have to supply a variable in which to store the value. We created an integer for this purpose on line 5. So what is the purpose of the ampersand '&' before the argument 'i' on line 9?

Pass by value

A fundamental feature of C is that arguments to functions are passed by value. Inside the called function, we see only the value of the arguments we were called with. If we do this:

  int i = 0;
  scanf( "%d", i ); // BUG!

Then scanf() sees the format string as its first argument, and the value zero as its second argument. This is no use to scanf()! It needs to store the value it has extracted from the input string somewhere. We wanted to tell scanf() about the variable i, not the value of variable i. How do we get around this apparent limitation?

Pointers

The answer is a very important concept in C: the pointer. The pointer allows us to represent where things are stored in memory. This is a simple idea, but pointers are often considered tricky.

Computer Architecture reminder: The computer makes memory available to your program as a simple address space, with each byte of memory having a unique numeric address, numbered from 0 to the size of the space. This is determined by your machine type, but is typically 2^32 (4GB or around 4.3 billion bytes) or 2^64 (a very large number). Every address contains a single value from 0 to 255. The address space can be visualized as a stack of mailboxes, numbered from zero, each containing a number.

This point is crucial: each mailbox has an address, for example 114 in the picture. And that mailbox contains a value. If you open the door of mailbox 114 and you see a note with "93" written on it, we say the value 93 is stored at address 114.

If you have used a spreadsheet, you are familiar with this idea. The address of a cell is its coordinate (e.g., C2), and the value of the cell is the number it contains. The memory space of a C program is like a spreadsheet with only one column.

Consider this sketch of our program's one-column address space:

Address   Value
2^n          0
  .          .
  .          .
  7          0
  6          0
  5          0
  4         42
  3          0
  2          0
  1          0
  0          0

The address space is listed on the left - the stack of uniquely numbered memory slots, and the value contained in each listed on the right. The value in memory address 4 is 42. Conversely, the address of that byte with value 42 is 4.

Now we can see how variables are actually implemented in C. When you declare a variable, e.g., char c=42;, the compiler chooses a currently unused address to contain it, say address 4, then writes the initial value 42 into the memory at that address. Every time the program refers to the value of c, this means the value stored at address 4.

Often you need to manipulate values larger than 2^8. To support this the compiler allocates a sequence of addresses with enough space to store a value of the variable's type. The lowest-numbered address is the address of the variable. The int type is often 32 bits long and thus need 4-bytes of address space. In our example, the compiler has decided that integer i will be stored in the 4 bytes starting at address 4. The value of 42 for i fits in the first byte, but we might increase it later such that addresses 5, 6 and 7 would have non-zero values too.

Address   Value
2^n          0
  .          .
  .          .
  7          0                  |   byte 3 
  6          0                  |   byte 2
  5          0                  |   byte 1
  4         42     <---- int i -    byte 0 
  3          0
  2          0
  1          0
  0          0

After compilation, your integer variable originally called i or highscore or answer_to_everything just becomes "the value of the 4 bytes starting at address 4 representing an integer". Variable names are just for humans and the compiler. The computer just needs addresses to find its data.

Pointers solve the pass by value problem

At this point you may have figured out the purpose of the ampersand operator '&'. It means "address of" the variable to its right. We can fix the fragment above using this operator:

  int i = 0;
  scanf( "%d", &i ); // fixed using &

Now scanf() receives the format string followed by the address of variable i. If i has the address 68, then scanf() receives the value 68. It now knows where to store the integer it reads from standard input. A value that represents a memory address is called a pointer, since it points to where its target is stored.

Remember: pointers allow programs to represent and manipulate memory addresses. This is a very powerful tool. We have seen how it solves the apparent limitation of the pass-by-value mechanism. We will come back to pointers later.

Many languages, e.g., Java, do not allow you to use pointers, and have references instead. These are implemented internally as pointers, with an extra little safety net limiting how you use them. C has only pointers, for simplicity. C++ has both pointers and references.

Now you know how to pass a pointer into scanf(), we are ready for the task:

Requirements

Guide

The format string syntax for scanf() is very nearly the same as for printf(). The format specifier for floating point numbers is "%f".

C comes with the standard library, which contains many useful basic functions, including printf() and scanf(), and many mathematical functions. These functions and their documentation man pages are available on almost all platforms, via the man program we used briefly above.

For example, you can look up your local man page for scanf() like so:

$ man scanf

The (very detailed) man page for scanf and related functions lists all the format strings it understands. You only need "%f" for this task.

Press the 'q' key to exit the man page viewer.

Notice that the required header(s) are listed at the top of the man page for each function. The exact headers needed varies slightly by system, so check your local man pages.

The man page system is widely available and usually very detailed. The main problem with it is that you need to know the name of what you're looking for. Happily, all the web pages are online and indexed by the web search engines. Double check your local man pages after looking online, due to the minor differences between platforms.

Three functions will be helpful for this task: floor(), ceil() and round().

$ man floor
$ man round
$ man ceil

These and most other math functions require the math.h header:

#include <math.h>

Note that these functions return values of type double and not int. Thus you need the appropriate printf() format string if you print their results directly.

Linking a library

The functions declared in math.h are not built-in to C. They are optional extras that are available as standard in most installations. The core of C is very small, and it comes with a standard library of extras, including these math functions. To use them you have to #include the math.h file, and then link the math library into your program, which adds the code for the math functions you use into your program. This is done explicitly in the compile command like so:

$ gcc t3.c -lm

The -lm suffix means link (-l) the math library (m). C tools are terse like that. The link command comes after the name of the source file(s), so that the compiler knows which functions are needed from the library.

Testing your program

Once you believe your program meets the requirements you are ready to submit.

Submission

Submit your solution by checking it into svn as before:

$ svn add t3.c
$ svn commit -m "t3 submission"

4. Conditions with if and else, return values

We have reached a very important point. Assuming your code perfectly meets the requirements above, you can say it is correct. But "correct" is defined by reference to the requirements. This code is not robust when the user is free to type in arbitrary things into standard input. We can improve the requirements by specifying what the program should do in the case of failures. It is important to see that correct code may not be reliable in the real world, and that the task of specifying requirements is a large part of the work of programming.

To write robust software that does the right thing even when used roughly, we first need to extend the requirements to specify what to do when things go wrong. Then in the code we test things as we go along, using conditionals: keywords that change the program's behaviour depending on the value of a statement at the time it is executed. C's basic conditional is if and it has the form:

if( statement )
{
 /* this block is executed if and only if 
  _statement_ evaluates to true (non zero) */
} 

For example:

if( s > highscore )
{
  highscore = s;
}

An optional else block can be added that will run only if the condition is false. Thus you can choose between two courses of action, for example:

if( s > highscore )
{
  highscore = s;
  printf( "Congratulations on your high score!\n" );
}
else
{
  printf( "Bad luck. Try again\n" );
}

Code blocks and indentation

The block of code after a conditional is contained in curly braces { ... }. In Python block structure is indicated by indentation, but in C and many other languages, indentation is not significant, and is only there for the comfort of the human reader. This is still very important, so you should follow the conventional indentation style used here and stick to it.

Return values

We capture the return value using the assignment operator =. We used this already in variable declarations to indicate an initial value (this is always a good idea, since C does not usually initialize variables for you).

Assignment examples:

int a=0; // ensures a does not have a random initial value
a = 5;   // change the value of an already-declared variable

a = scanf( "%d", &b ); // if b is set successfully, a will be set to 1

You should almost always check the return value (or other error-reporting mechanism) for any function call that could possibly go wrong or weird. This is a key basic strategy in Defensive Programming which aims to protect against Finagle's law.

Requirements

Guide

You should test the return value of scanf() to decide whether a floating point value was detected in the input.

Here's the list of infix comparison operators. When placed between two expressions (hence the term "infix"), these result in a value of false (zero) or true (usually 1, but any non-zero value evaluates true when used in a logical expression).

Notice the equal to operator "==" is distinct from the assignment operator "=" . Mixing these up is a common bug for C beginners. Double-check every time you intend to use "==".

Testing and Submission

Test, test, test again, then submit as usual:

$ svn add t4.c
$ svn commit -m "t4 submission"

Testing and submission instructions will be omitted from now on, unless there is something special about the particular task. Unless otherwise specified, submit a source file called "tX.c" where X is the task number.

5. Loops

While loops

The while keyword has the following form:

while( condition )
{
  // this block executes repeatedly as long as
  // condition evaluates true
}

For example this code:

int i=0;
while( i < 6 )
{
  printf( "%d ", i );
  i++;
}
printf( "\n" );

0 1 2 3 4 5

The repeating block of code is again contained in curly braces { ... }, as with conditionals.

Note the use of the increment operator ++ which adds one to its argument. i++ is a shortcut for i=i+1. This, along with the decrement operator -- are frequently used. Now you know how C++ got its name.

The condition can be inverted with the logical not operator !, so the following does the same:

int i=0;
while( ! i == 6 )
{
  printf( "%d ", i );
  i++;
}
printf( "\n" );

It is important to note that if the while condition is false on the first evaluation, the body of the loop is never executed. Think of it like an if statement that repeats until it is false. Occasionally it is useful to have the body of the loop run at least once before testing the condition, so there is an alternate form: the do-while, like so:

do 
{
  // this block executes at least once, 
  // then repeats as long as
  // condition evaluates true
} while( condition );

For example this code:

int i=0;
do
{
   i = getNextValueFromDatabase(); 

} while( i <= 1000 )

will get at least one value from the database, and will repeat this until it fetches a number bigger than 1000.

This is a dangerous example, since if all the values in the database are less than 1000, this program will happily run forever. This could be a nasty bug since your test database is probably different from those of your customers. You should be looking out for problems like this whenever you write a loop. To produce high quality code, you need to be always thinking, "What could possibly go wrong here?"

For loops

for( initialize; condition; modify )
{
   // this code runs until condition evaluates to false 
}

Any valid C expression can be used in each of the three for() components, separated by semicolons. But they are usually quite simple. For example:

for( i=0; i<6; i++ )
{
  printf( "%d ", i );
}
printf( "\n" );

Every for loop has an equivalent while, and vice versa, so choose whichever is neatest for the loop at hand.

Break

You can break out of a loop body with the break; statement. For example, this code

for(  i=0; i<1000; i++ )
{
   if( random() % 100 == 0 ) // random() is defined in stdlib.h
       break;

   printf( "%d ", i++ ); // prints the value and *then* increments it
}

Continue

You can jump to the beginning of a loop body with the continue; statement. For example, this code

for( i=0; i<1000; i++ )
{
   if( random() % 100 == 0 )
       continue;

   printf( "%d ", i++ ); // prints the value and *then* increments it		  
}

That is all there is to loops in C.

End-of-File

The standard input stream to your behaves as if it was a file. One of the most powerful ideas behind the design of the UNIX operating system and environment is that "everything is a file". Since stdin behaves like a file, it can have an "end".

The shell program connects your typed input to your program's stdin. We can break this connection by typing the special character sequence <ctrl-d>, that is press-and-hold the control key, then press 'd', then release the control key. The shell receives this command, sends a special "End-of-file" or EOF indicator to the connected stdin, and then closes the connection.

Inside the running program, the EOF indicator is detected by input functions such as scanf(). scanf() will return an integer with a special value to indicate EOF. This is often -1, but the actual value depends on your system. The standard library defines the symbol "EOF" which has the correct value for your system. You can use it like so:

int i=0;
int result = scanf( "%d", &i );

if( result == EOF ) // note double-equals for comparison!
{
  printf( "End of file detected\n" );
}

By definition, once an EOF is seen in an input stream, any subsequent read will also return EOF.

We can use the combination of conditional loops and EOF indicator to make the rounding program work for an arbitrary number of input values.

Requirements

Guide

Try to find a solution that is brief and readable, since that is the easiest to write correctly. Less code means less room for typos and more room in your brain to think about it. Readable code means you will be able to understand it whether you next look at it ten minutes or ten months from now. It can be useful to imagine that you are writing the code for a specific human reader. Make the code self-explanatory to them. Impress them with your clarity. My (vanilla, conventionally-formatted) solution is 20 lines long. If you write more than twice as much as this, think hard, and talk to an instructor or TA about how express the solution more compactly.

Testing coverage

Don't forget to test yourself interactively on a variety of inputs. One is not enough. Your job is to find bugs before our grading system does. Think "what can I possibly do to make it go wrong?".

As always, make sure your program meets the requirements. Here is a key idea: perform a test that covers every requirement, including those about malformed input and empty lines. Your tests should also exercise every line of your program, including every possible branch due to a conditional. This is the principle of coverage. We will talk more about testing strategies later.

It's also important to understand that a program that passes all the tests may not be correct. While our online tests aim to cover a variety of input cases, we don't know what's in your program, so we can not guarantee code coverage.

Only you can ensure your code is correct!

6. Simple statistics

Requirements

Guide

Note that you do not have handle arbitrary text in the input: only well-formed numbers and empty lines.

The definition of the arithmetic mean.

7. Pyramid Projection 1

Requirements

Guide

You'll need to use a fixed-width font in your terminal for these shapes to look right in your output. (If the examples below don't look symmetrical in your browser, check that your <pre> font is fixed-width.)

Examples

1. Input:

   6 6 4

   Output:

   ######
   #....#
   #....#
   #....#
   #....#
   ######
   

2. Input:

   7 4 4

   Output:

   #######
   #.....#
   #.....#
   #######
   

3. Input:

   1 1 1

   Output:

   #
   

Testing & Submission

As usual.

When testing yourself, don't forget to try small values and ensure that your rendering meets the specifications.

8. Pyramid Projection 2

Requirements

Guide

Don't be tempted to be artistic and make the pyramid "look right" by insisting on a 1-pixel point at the top. Be sure to meet the requirements exactly. Consider example 3 below and the image above, for example. Notice that the requirements imply that your rendering will be symmetrical left-to-right.

Minor hint: first draw the triangle upside down until the geometry is right, then fix the loop over height to flip it the right way up.

Major hint, if you need it.

Examples

1. Input: (matches the image above)

   6 6 4

   Output:

     ##
    #..#
   #....#
   ######
   

2. Input:

   7 4 4

   Output:

     ###
    #...#
   #.....#
   #######
   

3. Input:

   1 1 1

   Output:

   #
   

4. Input:

   12 6 6

   Output:

        ##
       #..#
      #....#
     #......#
    #........#
   ############
   

5. Input:

   40 10 4

   Output:

                  ##########
             #..................#
        #............................#
   ########################################
   

Testing & Submission

As usual.

When testing yourself, don't forget to try small values and ensure that your rendering meets the specifications.