CS211: Functions

The most powerful tool a computer programmer has is abstraction. Crafting abstractions allows us the ability to offload cognitive effort and focus on more generalized problems. For example, when we use our bash shell we often don't worry about the inner workings of how the OS handles the bytes that constitute files or folders. We simply run commands like cd, ls, and mv while taking for granted that these files will be managed appropriately by the filesystem. When constructing large, and even small, programs a principal abstraction is that of the function, which, when implemented correctly, acts as a means of compartmentalizing behavior in the same way that files or their corresponding bash operations do.

The usefulness of functions becomes readily apparent when applied to a real example. Take the power function we defined when discussing loops:

 1: #include <stdio.h>
 2: int main(){
 3:   int x = 3;
 4:   int y = 5;
 5:   int pow = 1;
 6:   for(int i = 0; i < y; i = i + 1){
 7:     pow = pow * x;
 8:   }
 9:   printf("%d^%d = %d\n", x, y, pow);
10: }

If I wanted to also find the values of 3^5 and 4^10, I would need to alter the program like so:

 1: #include <stdio.h>
 2: int main(){
 3:   int x = 3;
 4:   int y = 5;
 5:   int pow = 1;
 6:   for(int i = 0; i < y; i = i + 1){
 7:     pow = pow * x;
 8:   }
 9:   printf("%d^%d = %d\n", x, y, pow);
10:   x = 4;
11:   y = 10;
12:   for(int i = 0; i < y; i = i + 1){
13:     pow = pow * x;
14:   }
15:   printf("%d^%d = %d\n", x, y, pow);
16: }

In order to achieve the two outputs I had to copy and paste my power code a second time into my main function. But what if I also wanted to see the values of 7^3 and 16^6?

 1: #include <stdio.h>
 2: int main(){
 3:   int x = 3;
 4:   int y = 5;
 5:   int pow = 1;
 6:   for(int i = 0; i < y; i = i + 1){
 7:     pow = pow * x;
 8:   }
 9:   printf("%d^%d = %d\n", x, y, pow);
10:   x = 4;
11:   y = 10;
12:   for(int i = 0; i < y; i = i + 1){
13:     pow = pow * x;
14:   }
15:   printf("%d^%d = %d\n", x, y, pow);
16:   x = 7;
17:   y = 3;
18:   for(int i = 0; i < y; i = i + 1){
19:     pow = pow * x;
20:   }
21:   printf("%d^%d = %d\n", x, y, pow);
22:   x = 16;
23:   y = 6;
24:   for(int i = 0; i < y; i = i + 1){
25:     pow = pow * x;
26:   }
27:   printf("%d^%d = %d\n", x, y, pow);
28: 
29: }

It all gets to be a bit much, no? What if instead we had a power function to represent the computation, like so:

1: #include <stdio.h>
2: int main(){
3:   printf("%d^%d = %d\n", 3, 5, pow(3,5));
4:   printf("%d^%d = %d\n", 4, 10, pow(4,10));
5:   printf("%d^%d = %d\n", 7, 3, pow(7,3));
6:   printf("%d^%d = %d\n", 16, 6, pow(16,6));
7: }

It looks much cleaner and is easier to follow. The only issue is now we need to define a function called pow…

Functions in programming languages work similarly to functions in pure mathematics: they take input and they produce output. The syntax for defining a function in C is as follows:

1: type function_name(arg1, arg2, ...){
2:   statements; // Do this
3:   return val; //Return some data (output)
4: }

Like variables, every function must have a type—for functions, it is called a return type. By default, all functions in C have the int return type if not otherwise specified. Functions may or may not take arguments; however, if arguments are specified in the function definition that function must be passed arguments. Arguments must be sent in the order in which they were defined. Functions may or may not specify a return value; the return value must match the type of the defined return type¹.

In C, we can represent the identity function f(x) = x as:

1: int id(int x){
2:   return x;
3: }

Despite the small amount of syntax there are a few things we can notice. First, the function has a name, id, just like variables do. Knowing a function's name is essential to calling that function. Furthermore, we can see that the id function has a return type, int. Again, the return type indicates the type of data that will be output by that function. Additionally, we can see that there is an argument defined by the id function, x with type int. This means that id takes an integer value when it is called. Finally, we can see a return statement which sends back the value tied to the expression it is provided (here the value of x).

Let's now define the pow function we referenced in Listing 4:

1: int pow(int x, int y){
2:   int acc = 1;
3:   for(int i = 0; i < y; i = i + 1){
4:     acc = acc * x;
5:   }
6:   return acc;
7: }

The fundamentals we learned with id are still present in pow: there is a return type, arguments, a function body, and a return statement within the function body.

The syntax for calling functions is rather simple, and I couldn't avoid showing it in prior examples so you have seen it before. All you need to call the function is:

• To be in a lexical scope that recognizes the function's name
• Use the name of the function
• Place a set of parentheses next to the name
• Insert the correct number and type of arguments corresponding to each parameter defined in the function header

For example, to call pow all I need to write is pow(3,5). 3 corresponds to the first argument, x, and 5 corresponds to the second argument, y. If that function has a return type then the returned value will be evaluated in function call expression. Therefore, int p = pow(3,5) will store the value 243 into the variable p.

Because function call arguments are expressions we can nest function calls within one another. For example, if I wanted to evaluate the 2^(3^2), I could write pow(2, pow(3, 2)). First the expression pow(3,2) will be evaluated, then the expression pow(2, 9) will be evaluated.

All functions in C must be unique. This means I cannot define two functions with exactly the same name. For example:

 1: int my_func(int i); // Initial function
 2: 
 3: int my_func(int i); // Big problem!
 4:                     // I already have a function named my_func
 5:                     // that takes an int and returns an int
 6: 
 7: double my_func(int i); //Big problem, again!
 8:                        // I already have a function named my_func
 9:                        // that takes an int
10: 
11: int my_func(int i, int j); // Big problem, yet again!
12:                            // I already have a function named my_func
13: 
14: int my_other_func(int i); // No problem here, different name!
15: 

This is an example of where forward declaration could be useful. If there are two libraries with a function called sort_data then you can decide which file to link with during compilation when benchmarking.

Sometimes, complex problems are easily defined with recursive solutions. Take the fibonacci sequence for example. It is defined as:

• f(0) = 0
• f(1) = 1
• f(n) = f(n-1) + f(n-2)
• where n > 1

I leave it as an exercise for you to implement the fibonacci sequence as a recursive function in C.

1. Given the id function defined in Listing 6, what would be returned by a call to id(15.7)? Would an error be thrown? Why or why not?
2. The lecture states that all functions in C default to the int return type if not otherwise specified. Write a function add that takes two int arguments and returns their sum, but omit the return type from the function header. Compile it with gcc -Wall and record any warnings. Does the program still run correctly? What does this tell you about the difference between a compiler warning and a compiler error?
3. Rewrite Listing 3 using the pow function defined in Listing 7. How many lines of code did you save? What would happen if you discovered a bug in the power logic — how many places would you need to fix it in Listing 3 versus the function-based version?
4. Write a void function called print_pow that takes two integers and prints the result of raising the first to the power of the second, as shown in Listing 9. Then rewrite Listing 3 using print_pow. What is the difference between a function that returns a value and one that produces a side effect?
5. The lecture states that function arguments are just variables. Write a program that declares int x = 10 in main and passes it to pow. After the call to pow, print x in main. Does x change? What does this tell you about the relationship between the x in main and the x in pow?
6. Implement the fibonacci sequence as a recursive function in C as suggested at the end of the lecture. Test it with the values 0, 1, 2, 5, and 10. Then construct a trace table showing the recursive calls made to compute fib(5).
7. Write a forward declaration for pow in a file called my_program.c and define pow in a separate file called my_pow.c. Compile them separately into object files using gcc -c and then link them together manually using gcc my_program.o my_pow.o -o my_program. Verify the output matches Listing 14.
8. The lecture shows that pow(2, pow(3, 2)) can be used to compute 2^(3^2). Write a C program that evaluates this nested call and prints the result. In what order are the two calls to pow evaluated? Verify by adding a printf statement inside pow that prints each time it is called.
9. Compile Listing 15 with gcc -O0 -Wno-builtin-declaration-mismatch -fno-omit-frame-pointer -fno-stack-protector -S calling.c and examine the assembly output. Identify which lines correspond to: (a) saving the base pointer, (b) placing arguments into registers, (c) the function call, and (d) reading the return value. Compare your findings to the explanation given in the lecture.
10. The lecture states that the ret instruction takes whatever is at the top of the stack and jumps to that memory location. Looking at Listing 16, identify where the return address is placed on the stack and where it is consumed. What instruction places it there implicitly, and why is this necessary for the program to continue executing correctly after pow returns?