CSCI1300 Notes 4.  Functions and Pointers

Purpose: Learn to use and to create functions in C. Learn to use a simple graphics library. Learn the concepts of addresses and pointers.

Background

For this exercise  you need to be able to have your program draw shapes on the computer screen. To do this you'll use some programs provided as part of the CS1300 software. Programs you write will tell the system that you want to use one of these already-written programs whenever your program needs to put something on the screen.

A collection of already-written programs intended to be used in this way is called a library. In C the programs in a library are called functions (other languages call them other things, like subroutines or subprograms. or procedures.)

The term function is borrowed from math, but like the = sign in an assignment, the word has a rather different meaning from what it has in math. A C "function" may behave like a math function, in that you give it a number and it gives you one back, like sin(x), but it can also behave very differently. As you'll see, some C functions don't work on numbers, some of them don't give you back any result, and many of them do something for you besides computing an answer, something like making a dot on the screen or making a sound.

The C notation for using a function is modeled after what you are used to in math. Just as you provide a number to the sin function by putting the number in parens after the word sin, as in sin(2.56), you do the same thing in C: information you give a C function is put in parens after the name of the function.

Very commonly a function needs more than one number or other piece of information to do its job. In this case the different pieces of information are separated by commas. For example, there's a function called putpixel that makes a dot on the screen. To do this it needs two coordinates, an x and a y, to tell it where to make the dot, and a number that stands for a color. To make a white dot (color code 15) at position x=35 and y=56 you would write putpixel(35,56,15). The pieces of information you give the function are called arguments, the same word that is used for them in math.

When you write the name of a function with its arguments in your program, that is called a function call, and executing that part of your program is called calling the function. The effect is that when control in your program reaches the function call, the system "calls up" the function, gives it the arguments you have provided, and executes it. The function does whatever it is supposed to do, and then returns control to your program. Execution of your program carries on with whatever code follows the function call.

To use a function like putpixel whose job is not to give you back a result but just to do some work for you, you just write the call you want as a statement by itself, with a semicolon, as in

putpixel(35,56,15);

When your program is running, and control reaches this statement, a dot will appear on the screen, and then your program will go on to its next statement.

Some functions are used to get information rather than to do work. An example is getpixel, which takes two coordinates and gives you an int indicating the color of the corresponding spot on the screen. Here is how you would use a call to this function in an assignment:

c=getpixel(57,9);

This assignment calls up getpixel, giving it your arguments 57 and 9, and waits for getpixel to come up with its answer. That answer is then used as the value that is stuffed into the information holder c.

This part of C's notation is consistent with math. To use a value of the sin function in some other calculation in math notation, you just nest sin inside whatever calculation needs the result, as in

x + tan(x) + cos(sin(x))

or whatever. In effect when you write sin(x) in math notation you are specifying that the value of sin(x) is going to be used in the calculation at that point. C notation works the same way for functions like getpixel that produce values. And, just as in math notation, you can nest function calls in C, just as there is a call to sin nested within a call to cos in the expression above.

Incidentally, in writing about C programs it is usual to put parens after the function name to signify that you are talking about a function, as in putpixel(). I haven't done that above, but will below.

The graphics library.

The graphics library is included in the cs1300 software installation. You will find documentation for it in the file bgi\index.html in the doc folder in your cs1300 folder. Here is a brief description of the graphics functions you will need for this exercise.

initwindow() This function sets up the graphics facilities and creates a graphics window for you. A call like initwindow(100,200); creates a window 100 dots wide and 200 dots high.

putpixel() This function takes three arguments, all ints. The first two are the x and y coordinates of a spot on the screen. The third is a number that stands for a color. Black is 0, white is 15, and other numbers between 0 and 15 stand for other colors. So this call

putpixel(10,20,15);

will put a white dot at a position 10 spots over from the left edge of the screen and 20 down from the top (as we'll see below, the y coordinate runs upside down, increasing down the screen rather than up, as is normal in the coordinate system you learned in school math. An unfortunate decision somebody made long ago that we just have to live with.)

getpixel() This function takes two ints as arguments and produces an int value. The arguments are the x and y coordinates of a spot on the screen, and the int that is returned is the number that stands for the color of that spot. So if we execute this call

c=getpixel(10,20);

sometime after the putpixel() example, we'll get the answer 15 and assign it to c (assuming we haven't made any other calls that changed the color of that pixel in the meantime.)

Color constants. For your convenience in referring to colors, the folks who created these graphics routines have defined some constants for your use, like RED, WHITE, BLACK, and some others. If you use these words in your program, being careful to use all capital letters, the compiler will simply replace them with the appropriate numbers when it compiles your program. That way you don't have to know or remember what number specifies the color red, for example. You can use these constants not only to specify the color of dots but also to check, as in

if(getpixel(10,20)==RED)

...do something...

setcolor() A call like setcolor(RED); makes red the current color. Some graphics functions, such as line() (to be described next) use the current color when you call them.

line() A call like line(10,20,90,100); draws a line from (10,20) to (90,100), using the current color (as last set using setcolor()).

Coordinates on the screen. X coordinates run from 0 to 1 less than the width of your window (the one you created with initwindow()), starting at the left edge of the screen, and Y coordinates run from 0 to 1 less than the height of your window, starting at the top of the screen and running down. Again, note that the Y scale is upside down compared with usual coordinate systems.

The header file winbgim.h. Any time you use a function, whether it's in a library or is a function you write yourself, it has to be declared. The declaration tells the compiler what the name of the function is, what number and kind of arguments it needs, and what kind of result it returns, if any. Without this information the compiler can't handle calls to the function.

To save you trouble in creating these declarations for the functions in libraries, when a library is created there is also a file created that contains the declarations of the functions in the library. Because function declarations are sometimes called headers, such a file is called a header file. The header file for the graphics library is called winbgim.h ('h' stands for header).

OK, so this file called graphics.h contains the declarations for the functions in the graphics library. How do you put these into your program? By putting this line in at the beginning of your program:

#include <winbgim.h>

This tells the compiler to find this file and include its contents as part of your program. This way you get all of those declarations without having to know anything about them. As it happens you also get other useful stuff, like the definitions of those handy color constants.

Compiling and running a graphics program.

Besides including the graphics header file winbgim.h in your program, you have to tell the compiler to look for certain libraries that it won't look for if you don't tell it. And, at least for now, some of the code the compiler gets is legal C++ but not legal C. So Michael Main has provided a special command to use to compile a program foo.c that uses graphics:

bgi++ -Wall foo.c –o foo

[Note: If you are using an older version of Michael's software, like Clayton] use this command instead:

g++ foo.c -Wall -lbgi -lgdi32 -luser32 -o foo

Besides telling about those libraries (with the -l flags… those things with – in front are called flags) you're using the C++ compiler g++ rather than the C compiler gcc.]

Keeping the picture on the screen. When you run a graphics program you want to see the picture it draws. But when your program finishes the graphics window with the picture in it is automatically destroyed, probably before you get a look at it. To prevent this, put the statement getch(); in at the end of the program. This statements calls the getch() function (the name abbreviates "get character"), and getch() waits until you press a key before continuing. That way your program won't finish until you press a key, and you can look at the picture to your heart's content before you make it go away by pressing a key.

Getting a picture of the pattern your program makes (or any other program output, for that matter)You can capture the contents of any window, for example the one with your graphics in it, by making sure the window is selected (click on it with the mouse if it is not) and keying ALT PRINT SCREEN (That is, hold down the ALT key and press the PRINT SCREEN key, which may be labelled Prt Sc). This copies a picture of the window to an internal information holder in Windows called the Clipboard. Then get into Microsoft Word. When Word brings up a new document, hit paste. That copies the picture of your window from the Clipboard into the document. If you feel like it you could add any desired other info to the Word document (such as a caption or your team name).

Graphics example. Here's an example program showing how these things fit together. What it does is make a line of red dots in the middle of the screen, and then it checks a few dots to see if they are black or not. Then it draws a yellow line.

#include <winbgim.h>

#include <stdio.h>

//compile with bgi++ foo.c -Wall -o foo, where foo.c is the name of the file

int main()

{

int x,y;

initwindow(400,300);

for (x=315;x<325;x++) //draws a line of red dots

putpixel(x,240,RED); //from (315,240) to (324,240)

for(y=239;y<242;y++)

if (getpixel(320,y)==BLACK) //looks for black dots between

printf("320,%d is black.\n",y); //(320,329) and (320,241)

setcolor(YELLOW);

line(10,10,200,200); //draw a diagonal yellow line

getch(); //don't let program end and take away picture...wait for a                             //keypress

return 0;

}

Note: Start working on Ex4-0 after reading this far, to test your understanding.

One use of functions, as we've seen, is to be able take advantage of programs other people have already written when you are writing your own programs. This happens when you use a library, like the graphics library.

Why would you want to write your own functions? One reason is that you might want to create your own library for things you find you often need to do in other programs. That does happen, but in fact you'll find you'll be writing your own functions much, much more often than that. How come? This is tied into one of the big, important ideas in programming.

The key strategy in solving any large, complex problem is to divide it into smaller, simpler problems.

The method for doing this in programming is to divide a big program into smaller ones, where each smaller program does a small part of the overall job, and the programs work together to get the whole job done. These small programs are all functions.

This should remind you of one the key concepts of computing that we've already discussed: compositionality. Big, complicated programs are built up from lots of simpler programs, just as a cathedral can be built of bricks. You'll also see layering at work here: computer operations or instructions, which are all extremely simple, are used to build simple programs. Then the simpler programs are used to build more complicated ones. Then these programs are used to build still more complicated ones, and so on.

Look at the layers the other way around, a big, complicated program is built from a collection of less complicated ones. These in turn are built from even less complicated ones, and so on down, until you reach programs that are so simple that they are built from a few basic operations.

You already know quite a bit about functions from using library functions in the earlier part of these notes, that is, functions provided for you by somebody else. In particular, you know how to call a function when you need it, and how to give it the arguments it needs to do its work. Now you need to know how to create your own functions.

How functions communicate. The key issue to understand in creating functions is how they communicate with the programs that call them. Often a function needs to get information from the calling program in order to do its job, and needs to give back information about the results it produced. For example, the sin() library function needs to be given an angle to take the sin of, and it needs to be able to give the value of the sin of that angle back to the calling program.

You've already seen one side of how this is done: the calling program provides the angle as an argument, and it gets back the sin as the value of the sin as the value of the call. That is, in this example

y=sin(x);

the angle is whatever value is in the information holder x, and the sin gets put into y by the assignment. But how does this information get handled inside the function being called?

Here's a simple example of a function showing what's inside. It takes a number as its argument and returns its square:

float square(float z)

{

return z*z;

}

In this function, z is a special kind of information holder called a parameter (or sometimes a formal argument). When square() is called, the value of the argument that is provided in the call (sometimes called the actual argument) is copied into z. Inside square(), z behaves like an ordinary information holder, so the expression z*z computes the square of whatever value is in z. What return does is to take the value of that expression and give it back to the calling program. So if we call square(), say like this,

a=square(3.5);

the value 3.5 gets copied into z, z gets multiplied by itself inside square(), the resulting value 12.25 is returned to the calling program as the value of square(3.5), and so 12.25 is put into a.

Note that return does something else besides giving a value back to the calling program. It also terminates execution of the function, and lets the calling program resume its execution. So if there were any statements in square() after the return they would not be executed (in simple cases the compiler can detect this kind of problem and tell you about it.)

Here's another example, showing how functions that need more than one argument are handled:

int max(int a, int b)

{

if (a>b)

return a;

else

return b;

}

This function needs to be given two ints, and its job is to return the larger of the two. The call to max() in

printf("%d",max(3,4));

works like this. The value of the first argument, 3, is copied into the first parameter of max(), which is a. The value of the second argument, 4, is copied into the second parameter of max(), which is b. The statements in max() are then executed, and the test (a>b) fails. That means the else part of the if statement is executed, so the value of b is returned as the value of max(3,4), and so 4 is printed.

The process of copying the values of the arguments in a function call into the parameters of the function is called argument passing. In the example, we'd say that max(3,4) "calls the function max(), passing it the arguments 3 and 4."

Names in functions. An important point about parameters, and in fact about any information holders that you create inside your functions, is that their names have nothing to do with the names you use inside any other function. Here's a deliberately confusing example to illustrate this:

int main()

{

int a,b;

a=100;

b=1;

printf("%d",diff(b,a));

return 0;

}

Here's the definition of diff():

int diff(int a, int b)

{

return a-b;

}

If you look inside diff() you'll see that it uses the same names, a and b, for its parameters that main() uses for its variables. So you might think that the value that will be returned by diff() and printed has to be 100-1=99. But it's not.

The names used in diff() have nothing to do with the names used in main(), and so the coincidence that diff() and main() happen to use the same names makes no difference to how diff() works, which is as follows.

When the statement

printf("%d",diff(b,a));

is executed, the value of the first argument, b, is copied into the first parameter of diff(), which is a. So 1 is copied into parameter a. The value of the second argument, a, is copied into the second parameter of diff(), which is b. So 100 is copied into parameter b. Now inside diff() the expression a-b is evaluated, where a and b are the parameters, NOT the information holders with those names in the main function. This gives -99, and that value is returned as the value of diff(). Back in main() this value is used in printf("%d",diff(b,a));, so -99 is printed.

While the fact that the names inside different functions are not related may seem confusing at first, it's actually an important advantage. It means that when you are writing a function you do not have to know or care what names might have been used in any other functions. You can choose names that make sense in the functions, and what your function does will not depend in any way on whether those names have or have not been used for some other purpose elsewhere in the program.

There's another thing about functions that will help you understand the lack of relationship between parameter names and any other names. Functions can be called from many different places in a program. They can be called from more than one place in another function, and from more than one other function. The arguments in all these calls could be different. What values the parameters get for a particular call is determined solely by the values of the arguments for that specific call, not by what names the arguments have (if they have names, and aren't constants or expressions), or what names parameters have. If you think about it you'll see that things have to work this way: you couldn't easily call a function from many different places if the information the function got depended on what particular information holder names were being used.

If you get into the healthy habit of drawing boxes to represent information holders, you'll have an easier time sorting out the relationship between arguments and parameters. In the example above, if you draw the boxes you'll have two sets of boxes, one in main() and one in diff(). The function main() has information holders called a and b: you see the declarations for these right in the code. The function diff() also has information holders a and b: these are the paramters. Any time the name a (for example) is used in main(), it refers to the box named a in main(). When a is used in diff(), it refers to the box named a in diff().

Headers. The first line of a function definition, like int diff(int a, int b) in this example, is called the header of the function. It provides a lot of key information about the function. The first word (int in this example) is the type of value the function will return (or void if it returns no value). Then comes the name of the function, "diff" in this case. Then comes a list of parameter declarations, separated by commas, in parentheses. Each declaration gives the type of the parameter followed by its name. If a function needs no arguments to do its job, and hence has no parameters, you still need the parentheses. Thus the header int main() says you have function called "main" that returns an int and has no parameters.

As we saw earlier, functions don't always need to return anything (remember putpixel). The header in such a case begins with void to indicate that no value will be returned.

Declaring your functions. As we discussed briefly regarding library functions, the compiler needs to know some information about any function you use: its name, what type of value (if any) it returns, and the number and types of any arguments. Before you call a function you have to provide a declaration of the function that provides this information.

Notice that all the information the compiler needs is in the header of the function. C takes advantage of this by treating a function header, with a closing semicolon, as a legal declaration of a function. So this is a legal declaration of the function diff() in the last example:

int diff(int a, int b);

If a program wants to call diff() it has to put a declaration like this in so that the compiler will see the declaration before it has to process the call. Incidentally, the declaration of a function is also called its prototype.

Actually the header contains some information that is not required in the declaration, and that could be left out: the names of the parameters. It turns out that the compiler does not need to know these names to compile calls to the function. But you should definitely leave the names in. Not only is it easier to make your declarations by simply copying the headers (not forgetting to add the semicolons), but there is also a big advantage to anyone reading your program of seeing the parameter names. If they are well chosen they indicate clearly what parameter does what, without requiring the reader to find the actual function definition.

There is more than one place where you could put your function declarations. But I ask that you adopt the following simple arrangement for the functions in your programs and their declarations:

1. start with the #includes you need for any library functions you will use in your program.

2. Declare any struct types (not struct info holders) here

3. Then put all the declarations of functions you create in the program, except that you will not need a declaration for main().

4. Then put the definition of your main() function. The definition is the header plus the actual statements that say what the function is supposed to do.

5. Then put the definitions of all your other functions.

Here's the example above, arranged to illustrate this pattern:

#include <stdio.h> //a header file for library

int diff(int a, int b); //declaration for diff(): its header plus a semicolon

int main() //definition of main() starts here, with its header

{

int a,b;

a=100;

b=1;

printf("%d",diff(b,a)); //a statement of main() that calls diff()

return 0;

} //end of definition of main()

int diff(int a, int b) //definition of diff() starts here, with its header

{

return a-b;

} //end of definition of diff()

If you use this plan then you can call any of your functions anywhere in the program, because the compiler will have seen all of the declarations right up front.

It's actually possible to avoid using function declarations by placing your function definitions in such an order that every function is defined before it is called. But this is a bad idea. It means that your main() function would always have to come last in your program, so that someone has to plow through all the functions to get to the one that tells them what's actually going to be done in the program. In the recommended plan the first function you come to is main(), and so you get the big picture before having to absorb the details.

Note: Start working on Ex4-1 after reading this far, to test your understanding.

More complex communication between functions: Introduction to pointers

Now you know how to get information into a function and how to get information out by returning it. For most purposes that's all you need to know, and in writing functions you should try to get the job done using only these simple concepts. But sometimes you run into situations in which you need to do something more complex.

A common case in which these simple methods fail is when you need to get more than one result from a function. Suppose for example that you are doing arithmetic on whole numbers, and when you do a division you want to get both the quotient and the remainder. You could write two different functions, quotient() and remainder(), and in this simple case there might be no good reason not to do that. But suppose that the computation required to do the division was really lengthy. Writing two separate functions might require a good deal of repeated, and wasted, work. You'd really like to be able to do the work in one function and get more than one value back from it.

Some languages, including C++, have special machinery for doing this, using special kinds of parameters that have trick properties. But C does not; all parameters in C work in the simple way we've described. So what do you do? You do this by passing a special kind of value to your function, called a pointer.

Addresses and pointers. We've seen that memory is a big collection of bits, and that an information holder is a group of bits in memory. We’ve also seen something else: each group of eight bits in memory has an identifying number called its address. The computer has special circuits that allow it to locate and operate a group of eight bits by using its address. For example, the circuits can copy the values of bits from one group to another, using the addresses of the two groups.

Because addresses are just numbers, they can be stored in information holders themselves. So we can manipulate addresses in our programs in the same way we manipulate any other information. And we can use an address in an information holder to get the value stored somewhere else in memory, or to change the value of an information holder somewhere else in memory.

Information holders usually contain more than eight bits, so you might think you could only use an address to access part of an information holder. But the code C generates for using addresses uses the address of the first eight bits in an information holder to refer to the entire information holder. The compiler can do this because it always knows how many bits there are in an information holder, and because it always reserves a contiguous block of bits for an information holder. Thus it can always determine exactly what bits make up an information holder by knowing the address of the first block of eight bits, and knowing what kind of information holder this is, which determines how many bits are in it.

Historical note: It used to be common for computers to have addresses for groups of bits of length more than eight (as in FIDO), and there are probably still computers in existence for which that is true. But the grouping of bits by eight has proved so convenient, partly because eight is a good size for storing single characters, that it has become the nearly universal group size. A group of eight bits is called a byte, and the sizes of collections of bits are now virtually always given in bytes.

When an address is stored in an information holder it is often called a pointer. The idea is that the address "points to" whatever group of bits it is the address of.

Because information holders can have different numbers of bits, and because the same bits could be interpreted in different ways (for example as an int or as a float), it's important to keep track of not only what address a pointer contains, but also the type of the information holder it points to. The C language requires you to specify this information when you declare an information holder for a pointer, like this:

int *p;

This declares p to be an information holder that contains not an int, but a pointer to an int. Similarly,

float *eggplant;

declares eggplant to be an information holder that contains a pointer to a float.

If p is a pointer information holder, *p is the value in the information holder p points to. So the declaration

float *eggplant;

can be read like this: eggplant will contain the kind of value where if you put an * in front of it, you get a float. Similarly,

int *p;

means, p will contain the kind of value where if you put an * in front of it, you get an int.

Note: If you have followed this discussion you will see that * does not mean ‘pointer’, even though when it appears in a declaration like the examples, you are declaring a pointer. Rather, * is the operator that, when applied to a pointer, gives the information holder the pointer points to. In fact, in many uses, * has a meaning closer to unpointer, in that it is used to transform a pointer-to-an-int to an int. As we’ve just seen, if p is a pointer to an int, *p is an int.

Getting a pointer to an information holder. If foo is the name of an int information holder, &foo is a pointer to foo. Thus we might have the following:

int foo=13;

int *rutabaga;

rutabaga=&foo;

Here foo is an int information holder, intially containing 13, rutabaga is an information holder that can contain a pointer to an int, and the assignment places a pointer to foo into rutabaga.

Using pointers to do things with information holders. If we have set up foo and rutabaga as above, we can use rutabaga to operate on foo, as in this example:

printf("%d",*rutabaga);

This will print 13, because we have asked to print the value of the information holder rutabaga points to. Notice that this is way to get at the value of foo without using the name foo.

Further, we can use rutabaga to change what is in foo, like this:

*rutabaga=14;

Here, since *rutabaga is foo, we are putting 14 into foo, again without having to use the name foo.

The operator * is called the indirection operator. That's because, as the examples show, we use it to refer indirectly to foo... referring to foo directly would be using the name foo in the normal way.

Drawing box diagrams for pointers. You know how to draw a box or boxes to represent simple information holders, arrays, and structs. How can you include pointers in these pictures? A pointer information holder is just a box like any other simple information holder. But to show its value, instead of writing something in the box, you draw an arrow that starts in the pointer information holder and points to the information holder that the pointer points to.

For example, if you have the following situation,

int a;

int* p;

a=3;

p=&a;

you would have two boxes, a and p, with 3 in the a box and an arrow starting in the p box and pointing to the a box, like this:

You may wonder, why use arrows instead of writing an address in the box for a pointer? After all, an address is just a number. There are two reasons. First, you rarely know what the address of anything is, so you'd have to use made-up addresses. Second, what you really want to know about a pointer is what it points to, and the arrow makes that much clearer visually than an address would. In fact, arrows work so well that box diagrams with arrows are the absolutely standard way of representing and talking about any arrangement of information that uses pointers, as you'll see extensively in later courses.

Note: Start working on Ex4-2 after reading this far, to test your understanding.

Passing pointers as arguments. Coming back to functions, we'll see that by passing a pointer to a function, rather than some ordinary value, we give the function a powerful new way to give information back to us. Here's how that works for the case of getting a remainder as well as a quotient from a division:

int divide(int dividend, int divisor, int *remainder)

{

int quotient;

quotient=dividend/divisor;

*remainder=dividend-(divisor*quotient); //put remainder where the ptr

//remainder points to

return quotient;

}

Notice that we've given the function divide() a third parameter, and that we've declared it to be a pointer to an int. Here's how we use it:

#include <stdio.h>

int divide(int dividend, int divisor, int *remainder);

int main()

{

int r;

printf("quotient is %d ",divide(13,4,&r));

printf("remainder is %d", r);

return 0;

}

We know what will happen with the parameters dividend and divisor. The values of the first two arguments, 13 and 4, will be copied into the parameters. The same thing happens for the third parameter, remainder, too, keeping in mind that what is being passed is not the value of r but a pointer to r: that’s what the & does. The declaration of the parameter remainder specifies that it is a pointer to an int, and the & in front of r in the call means that the value being passed is not the value of r but a pointer to r.

When the divide() function executes, it uses the values of dividend and divisor as you would expect to detemine the quotient. But before returning the quotient it calculates the remainder, and stores it in the information holder remainder points to. Since remainder contains a pointer to r; r is where the remainder is stored. Now when control returns to main(), not only has the value of the quotient been returned, but the value of the remainder is also available, stored in r.

The function divide() uses its pointer parameter remainder only to pass information out from the function. But it's perfectly possible to use pointer arguments to pass information into a function as well as out. This is because the function can use the pointer to access any value that is already in the pointed-to information holder when the call is made. For example, this function would work:

{

*input=*input + 3;

}

Let's say i is an int information holder. Then the statement

would take whatever value is in i, add 3 to it, and put the new value back in i. In this example the pointer argument input is being used both to get information into the function and to pass information back out.

Actually, I would not write add3() that way, even though it will work fine. I (and many other programmers) try to avoid pointer arguments when I can, and I would instead write a function add3() like this

{

return 3+input;

}

and use it like this:

One advantage of doing this is that calls to functions written this way can be nested, as in

If you work out what you'd have to write to get the same effect as this statement with the function add3() that uses a pointer argument, you'll see that it's far more complicated.

Note: Start working on Ex4-3 after reading this far, to test your understanding.

Strange truths about arrays. Remarkably, in C,

the value of an array is a pointer to its first element.

This fact is so odd that you may want to make a special effort to remember it, like writing it on a piece of paper and putting it under your pillow. Actually, it yields some convenience when you want to write a function that changes what is stored in an array. Here's a function that replaces all the elements of an array with 0:

void zero(int a[10])

{

int i;

for(i=0;i<10;i++)

a[i]=0;

}

Now you can have something like

int foo[10];

zero(foo);

and all the elements of foo will be changed. Notice that you haven't used any pointers, apparently, and even so the function is able to change the "value" of the argument. In reality, though, you are using pointers: the value of foo is really a pointer, and because the parameter is declared to be an array, it's really a pointer, too.

Two related nuisance facts are that you cannot assign one array to another, and you cannot return an array from a function. If you have

int a[10], b[10];

you'd want to be able to say

a=b;     //this won't work!!

and have all the elements in b copied into the corresponding elements of a. But since the value of b is a pointer, C thinks you are trying to make that pointer be the value of a. It won't allow this, because the value of a always has to be a pointer to where the memory for array a is, not somewhere else.

For related reasons, you aren't allowed to write a function whose return type is an array. You could write a function that returns a pointer, and return a pointer to an array that way, but that doesn't really give the effect you want. The upshot is that functions that produce new arrays do this by modifying the contents of arrays they are given as arguments, not by returning a new array.

Historical note. Why did the C designers do things this way? Back when C was designed, computers were much, much slower than they are now, and the designers felt it would be very wasteful of computing power to pass what you normally think of as the value of an array to a function. That's because values need to be copied, and what you think of intuitively as the value of an array is usually a good many bits. By making the value be a pointer, you have to copy many fewer bits, unless you have an unusually small array. Similarly, assigning one array to another or returning a value from a function requires copying the value, and that too is slow for the contents of a big array. So the designers ruled these things out.

More about array arguments. You've seen that the value of an array is just a pointer to its first element. Sadly, this means that the value of an array does not say how many elements the array has! This makes for extra work when you are passing arrays between functions, because the length info has to be passed separately, as in this example:

float sum(float data_array[], int size)

{

int i;

float total=0;

for (i=0;i<size;i++)

total=total+data_array[i];

}

Notice how the parameter data_array is declared: the brackets after the name say that it's an array of floats, not just a single float, but you haven't said how many floats there are. Because the value that will be copied into this parameter is just a pointer to a float, you don't need to say how many elements are in the array here. This has the potential advantage that you can use this sum() function for arrays of any size.

If you know that the arrays that will be passed using a parameter will all have a certain size, you can include that size inside the square brackets when you declare the parameter. But doing this will have no effect, other than conveying information to a human reader. The compiler will not check anything based on the size you use.

Notice also the second parameter, size. This is used to tell the sum() function how many elements data_array[] has in it. As we've been saying, there's no way the function can tell how big data_array is just by looking at the pointer value that's passed in; the function either has to assume the size is some predetermined number, or (as in this example) it has to ask for the size to be passed in in a separate argument. (Incidentally, there's nothing magic or automatic about arguments like size: the programmer has to make sure to pass the correct size information, or the function won't work right. Also, the name can be anything; size is used here because it's meaningful to a human reader.)

Here's a function that calls sum():

#include <stdio.h>

int main()

{

float numbers[10];

int i;

for(i=0;i<10;i++)

numbers[i]=i+3*i*i -100; //fill in some values

printf("%f",sum(numbers, 10)); //print out the sum

return 0;

}

Note how the array named numbers is passed as an argument: just its name, without any subscript or brackets, is used. If you wrote, say, numbers[0] rather than numbers, you'd get an error: the compiler would see that you were trying to pass a float value to a parameter that's a pointer to a float.

Using structs to get around the limitations of C arrays. You can use a struct to bundle together an array and the number of elements in the array. Because structs can be assigned, and can be returned by functions, you get some great convenience from this. Here's the zero() example and the sum() example redone in this style:

#include <stdio.h>

struct numarr //this declares a struct type

{

float nums[100];

int n;

};

struct numarr zero(struct numarr a); //declaration for zero()

float sum(struct numarr a); //declaration for sum()

int main()

{

struct numarr numbers;

int i;

for(i=0;i<10;i++)

numbers.nums[i]= i+3*i*i -100; //fill in some values

numbers.n=10;

printf("%f\n",sum(numbers)); //print out the sum

numbers=zero(numbers); //replace all elements by 0... structs can be assigned

printf("%f", sum(numbers));//print out sum... should be 0 now

return 0;

}

float sum(struct numarr a) //start defn of sum()

{

int i;

float tot=0;

for(i=0;i<a.n;i++)

tot=tot+a.nums[i];

} //end defn of sum()

struct numarr zero(struct numarr x) //start defn of zero()

{

int i;

for(i=0;i<x.n;i++)

x.nums[i]=0;

return x;

} //end defn of zero()

Think of functions as islands.

We can summarize some key parts of our discussion by saying that functions are like little islands. Each island can have its own information holders, with their own names, and we don't have to worry that some name is also used on some other island. There are only a few specific ways to get information from one island to another: arguments, which can be pointers, and return.

This simplicity may seem like a limitation, but actually it's a big advantage: these restrictions mean that you can understand what a function does just by reading the function itself, without worrying that some other function is going to mess around with its information holders. The restrictions help in the basic task of dividing a complex problem into simpler ones by keeping the parts of our solution from interfering with one another.

Global variables. Unfortunately C (and many other languages) allows a significant complication of this nice simple picture. It's possible to declare variables that are not on any particular island, and can be used on any island. These are called global variables, the image being that they can be used anywhere on the globe. Ordinary variables that are declared on an island (that is, in a function) and can be used only there are called local variables. Global variables can be used to move information freely between islands: just have one function put a value into a global variable, and any other function can read that value.

Sounds convenient, doesn't it? If you are like most people you will be sorely tempted to use global variables all the time to transfer information around. It seems so much easier than having to declare parameters and write all those arguments when you call a function. But the global variable idea is a trap, and

you must not use global variables in any program you write for this course.

The problem with global variables is that they are too flexible. If something is a global variable it can be modified by any function, with absolutely no sign that this could happen. To know where a global variable is being changed you have to read every line of every function, because somewhere there could be an assignment to that variable.

Imagine a specific scenario. Suppose you are testing a program and you find that some global variable has a wrong value in it. To find where the bad value came from you would have to check every line of every function, making sure you find every statement that assigns to that variable.

It's possible that this seems like a phony issue to you. You may be thinking, well, if I wrote all those functions then of course I'll know which functions contain assignments to that global variable and which do not. There are a number of reasons why this argument is wrong. First, it assumes that you did write the functions, while in real life it is rare for one programmer to write all the functions used to solve a complex problem. To prepare for real programming you cannot use methods that only work for toy problems. Second, even if you wrote all the functions, experience shows clearly that you will quickly forget what you put in what functions. Then you are back to having to find all the places that variable is assigned. Third, there is always the possibility that you will make a mistake. You meant to assign to some variable j, but you typed i, the name of your global variable, instead. From the compiler's point of view that mistyped assignment is perfectly legal; after all, i is a global variable, and so you can assign to it anywhere you like. The mistake won’t be caught, and now you have a function that “couldn’t be modifying i” which is modifying i.

There's another problem with global variables, too. If a function uses a global variable called (say) foo, it can only be used in a program that has that same variable foo declared, and provides a value for it. This limits your ability to re-use a function written in one context in some new context. Relating this problem to compositionality, a function with a global variable is like a brick that can only be used with certain other bricks. A huge bother.

There are situations in which global variables are appropriate, and there are language features that are used in these situations to reduce the difficulties we've talked about. In essence these features allow you to have a limited global variable, one that can be used only in specific places controlled by you and enforced by the system. So in the future you'll learn how to use global variables safely for a few specific purposes. But you will NOT have any problems requiring this in this course, and so, again, you should NOT use global variables. Instead, concentrate on learning how to use arguments and return to transfer information among functions.

Special note: If you know PASCAL, there are some other ways to use variables to pass information among functions that you may be thinking about. In PASCAL you can nest a function inside another one, and the inner function gets to use any variables of the outer function. You can't do that in C, because you can't nest functions inside each other. C is much simpler!

Exercises

Note: You must work on this assignment with at least one other person.

Ex4-0 Be sure everyone on the team can write a simple graphics example and run it, for example, a program that draws a red triangle on the screen.

Ex4-1 Have one team member as write a function that draws a small colored square on the screen, with the x and y coordinates of the center of the square, and the color of the square, being specified as arguments. Then switch roles and have another team member write a program that uses that function to draw several squares of different colors on the screen. Include a picture of the result in what you submit (see What to Turn In, below.)

Ex4-2 Work out on paper, without running the code, the contents of a and b at the end of these program fragments. Make sure everyone on the team can answer this kind of question, by posing examples to one another. Remember to draw boxes, and be sure everyone on the team can do this.

Q4-2a

int a,b;

int *c;

a=0;

c=&a;

*c=3;

b=a+2;

Q4-2b

int a,b;

int *c, *d;

c=&b;

a=0;

b=2;

d=c;

*d=*c+*d;

d=&a;

*d=*c+*d;

Ex4-3 Have one team member write and test a single function that takes two floats and produces their sum and their difference. Then have another team member write and test a single function that takes one float and produces its square and its cube. Here, “produces” does not mean to print out the values. Rather, as in the divide() example in the notes, it means the function has to communicate its results to a program that calls it, using arguments and/or return.

Ex4-4 Write a function that takes the x and y coordinates of two points (represent them as ints) and returns the distance between them, expressed as a float. Then write a program that uses this function (and allows you to test it.) There’s a function sqrt() that takes the square root of a number. It’s in a library called “math”, so you’ll have to put #include <math.h> after #include <stdio.h> at the top of your program. There’s also a function pow() that takes two numbers and raises the first to the power of the second. So pow(x,2) will give you the square of x. It’s in the math library too.

Ex4-5 Here are declarations that describe some data about people’s interests, collected from a survey. The survey asked them to rate their interest in the underlying technology of computing, the “bits and bytes”, on a scale from 0 to 100, and to rate their interest in what computing can do for the world, the “meaning” of the technology, on the same scale. Write a program that draws a map in which each person is represented by a colored square, with the x coordinate of the center of the square being their “bits and bytes” interest rating and the y coordinate being their “meaning” interest rating. Use the function you wrote for Ex4-1 to draw the squares. Turn in a picture of the result, as well as a listing of your program.

//structure type declarations:

struct person

{

int bits_score;

int meaning_score;

};

struct survey

{

person data[100];  //room for 100 people

int n; //how many people we have data for

};

//declaration of an information holder with data

survey s={{{10,20},{100,20},{20,100},{100,100},{50,50}},5};

What to turn in.

Remember that you must work with at least one classmate on this assignment. List the name or names of the people you worked with on your submission.

For Ex4-0 just indicate the status. If anyone is having trouble, explain. For Ex4-2, turn in your answers, and indicate the status of each team member on this kind of question, including their ability to draw and use boxes. For Ex4-1, Ex4-3, Ex4-4, and Ex4-5, turn in listings of all programs, including the test programs you used for Ex4-3 and Ex4-4, and a screenshot showing your compilation (using –Wall, and showing no warnings or errors). For Ex4-5, also include a screen snapshot of your map (attach a Word document with the picture in it.

Note that all programs must have their parts in the order suggested in the notes (declarations of functions, etc.)

Be sure everyone sends their own email submission, and includes their time report. Copy tanaraks@colorado.edu on your email submission.

Optional further work (if you have time… remember that you should be spending something like two hours out of class for each hour in class)

Opt1  Modify the program for Ex4-5 so that it finds the two people whose interests are most similar, as indicated by the distance between their points, and draws the squares for those two people in a different color from the rest. If there is more than one pair with the minimum distance choose any one.

Hints: Use your function from Ex4-4 to compute distances. Use nested loops to find the distances between all pairs. You can think of this as a GAPP within a GAPP: for every person in the collection, compare them with every person in the collection. Remember not to consider the distance between a person and themselves. In Notes 3 there’s an example program that uses the GAPP to find the maximum of a collection of numbers: the method used there is sometimes called the knockout plan: you keep track of the winner so far (the highest value) and when you find a higher value you replace the old winner with the new winner (that’s the knockout). You can adapt this plan by making the winner the lower number rather than the higher. When you do this you can also keep track of the subscripts of the two people who produce the winning (minimum) distance, so that you can draw them differently.

Opt 2 Langton's Ant is a very simple automaton that moves around in a grid making marks. It is interesting because, although it is incredibly simple, its behavior is very complex, and, even more odd, its behavior changes completely in character, but only after more than 10,000 steps. How can we hope to understand the nature of the universe when even extremely simple mechanisms produce such complicated effects?

The ant is always located in some square in a grid. The squares of the grid are all colored black or white. The ant is pointing in some direction at any moment, north, east, south, or north. The ant moves around in the grid, following these rules:

•It moves ahead one square , in whatever direction it pointing.

•It examines the color of the square it finds itself in.

•If the square is white, the ant changes the square to black and turns right. Otherwise the ant

changes the square to white and turns left.

To illustrate these rules, here is what happens for the first few steps if the ant is started in the middle of a big field of white squares, and is initially heading east. Follow along with this description using a piece of squared paper to be sure you understand the rules.

Ant moves east.

Since square is white, ant makes it black, and turns right. It now points  south.

Ant moves south.

Square is white, so make it black and turn right (west).

Ant moves west.

Square is white, so make it black and turn right (north).

Ant moves north.

Square is white, so make it black and turn right (east).

(At this point there is a block of four black squares in the field.)

Move east.

This square is black, so make it white and turn left (north).

And so on.

(At this point there are three black squares forming an L.)

Your job is to implement the ant so you can see what pattern it makes when it continues for many moves. As in the example, you want to •start the ant in the middle of a big field of white cells, heading east. You'll want to •let the ant run for about 12,000 steps to see what happens.

Use the computer screen to represent your grid, with each dot on the screen representing a square. Use putpixel() to set the color of the squares and getpixel() to check the color of the squares.

Here are some hints for some aspects of the design.

Hint 0. Make a general plan for your program. This should have a loop, since you want to make the ant do its thing over and over again. In the loop give yourself some steps corresponding to the bulleted list of things the ant has to do, given above. You'll make your life easier if you follow the bulleted list exactly: don't get creative.

Now you have to figure out how to get the ant to do those things. You also have to set up the grid and the ant before you start the loop. But these things will be fairly easy if you follow the hints below.

Hint 1: Representing the ant.  You don't really need to show the ant itself on the screen, and you will make life harder for yourself if you try. Just keep track inside your program of where the ant is and in what direction it is pointing. You'll be able to see where the ant is by watching which squares are changing color. Use coordinates to represent the ant's location, and a number, 0,1,2 or 3 to represent the direction it is pointing, with (say) 0 representing east, 1 south, 2 west and 3 north. Of course you'll need information holders to keep these numbers in, and you'll have to put appropriate values in them when your program starts out.

Hint 2: Making the ant move. What you do depends on which direction it is going. To make it move north, subtract 1 from its y coordinate (remember that the y coordinate on the screen increases downward). To make it move east add 1 to its x coordinate, and so on.

Hint 3: Making the ant turn. If you use numbers as suggested above to represent the directions, adding one to the direction gives a right turn, usually, and subtracting one gives a left turn, usually. To avoid the problems and turn the "usually" into "always" you just have to check the result of the addition or subtraction and change a 4 to a 0 and a -1 to a 3 if that's what you get. If you make yourself a little picture with the four directions labelled 0 thru 3 you'll see how this works: if you are pointing in direction 3 and you turn right you want to get direction 0, not 4, since there is no direction 4. Similarly if you are heading in direction 0 and you turn left you want direction 3, not -1.

Note that "turn" means just "turn" and not "turn and move". A turn should change only the direction your ant is pointing, not its position.

Hint 4: Making a white field.A brute force way to do this is with a nested for-loop:

for(x=0;x<nx;x++)

for(y=0;y<ny;y++)

putpixel(x,y,WHITE);

will fill a block nx by ny with white dots. If you wish you can look among the BGI graphics functions in the library to find an easier way to do this.

Hint 5: Clarifying complex tests. Note that to make the ant move forward you have to do different things depending on what direction it is heading. You can certainly use a bunch of ifs and elses to do this. But situations like this is what the switch construct in C was made for. Read about it at http://www.acm.uiuc.edu/webmonkeys/book/c_guide/ .

Hint 6: How to control how many moves the ant makes. You could use a for-loop to make the ant take a prescribed number of steps, say 12000.

Hint 7: Disciplining your ant. While we are on the subject, what would happen if your ant went off the screen? You don't really want to be putting pixels in places where there aren't supposed to be any. So you should check each move the ant makes and stop it if it goes somewhere you don't want it to. If you prefer, you can have the ant "wrap around" and come in on the opposite edge of the screen when it goes off, instead of stopping it.

Opt 3 One-dimensional totalistic cellular automata. Can you find out enough about them on the Web to implement one?

Opt 4 Multidimensional scaling. Suppose you had a table of distances between places. Could you draw a map of their locations? How? How would your map relate to a real map showing the places? What if the places were points in three dimensional space? A space with more dimensions? Doing this is called multidimensional scaling, and it’s used to try to analyze things like the number of ways complex objects might be perceived as being different. For example, you could ask people to rate how similar different words are, and then see how many dimensions you needed for a map that would capture these relationships among the words. Look up multidimensional scaling on the web and see if you find anything interesting.

Opt 5 Moire patterns. What are they? Can you demonstrate them in a graphics program?