# Higher-Order Programming in C: Function Pointers and Void Pointers

Norman Ramsey
Fall 2008

### Introduction

Hanson's textbook presents intriguing functions like Bit_map and Table_map, but to my great disappointment, he doesn't really motivate these functions or provide examples of their use. It's too bad, because a function that takes a function as an argument is called a higher-order function, and it's one of the most powerful programming techniques there is. Because implementing this technique in C requires function pointers and void pointers, I attempt to give you a few pointers here. [Triple pun! Pointers as in the language, pointers as in ``tips,'' and pointers as in ``references to other people's work.'']

When you bring together a pointer to code and a pointer to data, you create a computational powerhouse that in functional languages is known as a closure and in object-oriented languages is known as an object. For C programmers, it is often useful to think of the data pointed to as being divided into two parts:

• Context needed for the function
• Mutable data needed to accumulate a result
If you have but a single void * pointer to work with, you must often create a structure containing both context and data.

### Exercise: find available aligned register pairs

To help you learn these concepts, I've written an extremely simple exercise. Suppose you have a CII bit vector in which the vector represents a set of registers, a zero bit says that a register is available to hold a value, and a one bit says that a register is unavailable because it already holds a value. (This representation is a classic one used in many compilers.) The problem is as follows:

Use Bit_map to make a list of available aligned register pairs
An aligned register pair is a pair of registers i and i + 1, where i is even.

Recall the type of Bit_map:

```  extern void Bit_map(T set,
void apply(int n, int bit, void *cl),
void *cl);
```
Your job is to create an apply function that will accumulate a list of available pairs. The context is the bit vector, and the mutable state is a list of register numbers i. So the void *cl passed to Bit_map and to apply should point to a structure with a type something like this:
```struct rp {
Bit_T registers;
List_T avail_pairs;
};
```
Here the registers field is the context and the avail_pairs field is the mutable data.

Here's the skeleton of a function:

```List_T available_aligned_pairs(Bit_T regs)
{
struct rp cl = { regs, NULL };
return cl.avail_pairs;
}
```
We return the mutable data created by calls to add_aligned_pair. To finish the job, you'll need to define add_aligned_pair, which will cast its third argument to a value of type struct rp *. It will then observe (without mutating) the registers field, but it may mutate the avail_pairs field by assigning it the result of calling List_push.

I recommend that you do this exercise and test it. You will not be asked to turn in the results for a grade, but any of the course staff will be happy to look at it.