Lesson Idea: Arrays, Pointers, and Syntactic Sugar

Question

One of the most challenging concepts to instill in new CS students is 0-indexing (indeed, the pedagogy of this fact probably merits its own discussion). Another difficult topic -- although a slightly more advanced one -- is pointers. (I'm thinking particularly of programming in C.) With this question I'm wondering if part of the difficulty is the syntactic sugar in C that allows the following to be equivalent:

// declare array of 5 ints on the stack
int num[5];

// use array notation to change first element
num[0] = 42;

// use pointer arithmetic to change first element
*(num + 0) = 42;

With array notation, we are explicit with 0-indexing, but the logic of it isn't apparent. Yet, with pointer arithmetic, it's more clear (I think...) why we use 0: the pointer stores the base address, so dereferencing the pointer brings us to that address which is where the array logically begins.

Comfort with this leads to the topic of memory management on the heap with something like this:

// declare array of 5 ints on the heap
int *num = malloc(sizeof(int) * 5);

// use pointer arithmetic to change first element
*num = 42;

I am toying with expanding my introduction on arrays next year to include this particular use of pointers. I recognize that it would involve taking roughly a single lesson on arrays and expanding to something closer to a week-long series to tie all of these ideas together.

However, is it worth putting aside the syntactic sugar in order to understand more accurately the indexing of arrays? On the other hand, does the introduction of pointers and memory complicate the process so much so that confusion about arrays will increase rather than decrease? (I'm thinking this is a "lesson idea feedback" discussion.)

Answer 1

You overestimate the complexity of 0-based indexing a lot. There is nothing complex in 0-based indexing.

On the other side, the topic of the pointers is relatively complex. I don't think it has any sense to introduce pointers earlier, than at the time when a pupil would be ready to fully feel their usefulness and use them in practice. Especially in languages like C, where the syntax of pointers is quite weird (I mean: it was a quite illogical decision for language creators to use the same syntax for arrays and pointers; as they actually have almost nothing in common: an array is usually a large-sized object containing one or more items of a specific type, a pointer is a tiny-sized object that doesn't contain even a single item, it contains only the address; pointers to items and pointers to arrays should have some convergence, but pointers to items and arrays — no more than, for example, a pointer to the item of a specified type and a structure whose first member is of specified type).

Answer 2

This is a great explanation of why 0-indexing exists. As someone who barely knows what a pointer is, your explanation made perfect sense. If you wanted to dumb it down a little you could phrase it as:

When you create an array, the variable you assign that array to is actually a pointer to the first element. Lets create an array num. When you want to modify the array, to get a pointer to the first element you want to add 0 to num, because num points to the first element. For the second element, you add 1 to num because num is a pointer to the first element and the second is one after the first. Then for the third element, you add 2 to `num, and so on, so that the first is adding 0, the second is adding 1, and the third is adding 2.

A useful resource is this website which explains how num[i] is syntactic sugar for pointer arithmetic (*(num+i)).

I think that this discussion will increase clarity and be very useful because it makes sense as a logical way to implement arrays and revels a cool thing about the language. I'm not sure that you have to talk about memory, but talking about pointers is certainly worthwhile for this example.

Answer 3

Draw ongoing attention to the potentially confusing point by banning cardinal descriptions of an element's position.

Avoid referring to the "first element" or "second element" and talk only about "element at index 0" or "at index 1." Insist that your students speak only of indices and not of position in a sequence. If you ever use cardinal numbers in human language, you might get it right ("the second element is the element at index 1") but beginners will stumble, as you point out. If you correct with a smile when a student speaks to refer to an element with cardinal numbers, the class will join you in "catching" cardinal language. While there's nothing wrong with cardinal language, a playful "ban" gives students the opportunity to think through the point of confusion every time someone speaks about an index.

Your question as to "does teaching pointer arithmetic reduce student mistakes related to 0-indexing" is an empirical question. I don't know, but I'm suggesting another treatment, the playful ban. My evidence is mere anecdotal experience that this works in my classroom with my teaching style. There does not exist, to my knowledge, any report in the CS ed literature comparing students in a class that "prohibits" cardinal description by friendly censors vs. a class that does no such thing. As CS educators, we have a long way to go before we can boast of a compendium of empirically derived pedagogical content knowledge. Physics has the tome I envy: a 4-pound 11-pt-font book summarizing peer-reviewed measurement of effects of classroom nuances like this. Please, CS ed, produce something akin to Teaching Introductory Physics. Guzdial's Learner-centered Design of Computing Education is a wonderful book, but we have a long way to go to match the physics education community's understanding of their craft.

Answer 4

I am not advocating teaching pointers to explain 0-indexing (see mine and other's answers on your other question for how to do that). However, if we have good reason to teach pointers, here is a tip that helped me when I was learning. I have also shared these ideas with other pupils, and they started to make progress.

I find code involving pointers confusing: is it a pointer, or is it the real thing. To help me with this I adopted a little bit of Hungarian notation (I don't generality advocate Hungarian notation in strongly typed languages, but for pointers, it is a great help.

Prerequisite

It is important to ensure that all variables and routines have good names:

• Routines that do something (change something), should not return a value and should have a verb name (or verb phrase). (one style would allow returning of status, this is needed in non-object-oriented programming.)

• Booleans should be adjectives (start with is, has was (no future tense).

• Variables and routines returning a non-boolean value, should be a noun (or noun phrase).

The notation

Append a _pt to the end of the name of all pointers.

Explanation

int numberOfCats     /*  numberOfCats is an integer*/
int *numberOfDogs_pt /* *numberOfDogs_pt is an integer*/


numberOfCats  /*a real integer*/
&numberOfCats /*a pointer to an integer*/

*numberOfDogs_pt /*a real integer, like what was declared*/
numberOfDogs_pt  /*a pointer, as in its name*/

If you see a *???_pt then you can cancel out the * and the _pt, it is in this context, not a pointer, but I can drop the * to make it a pointer. Where a variable does not have a _pt, there is no * to drop, however, I can add a &. & works as the opposite of a *.

*&numberOfCats is same as numberOfCats

---

Hope this is useful.

Answer 5

Let me suggest, pretty strongly, that you may be mixing up too many ideas in too short space for novices to grasp in one go. Spread it out. There is no real reason to introduce arrays along with pointers, nor to give a complex reason for zero indexing at the start. In C, you don't want to avoid it altogether, of course, but you don't dump the whole load at once.

Step one

I'd suggest that you first present arrays in a simple way, using all of the available sweeteners that there is (syntactic sugar). Something like this tutorial is pretty clear. It enables the use of arrays for nearly all purposes.

You can describe an array as a "contiguously stored block of values of the same type." One easy way to talk about zero indexing in this context is to think of the index as the distance from the start. If you aren't asked about what distance means at the start you can just ignore it, but if asked, you can talk, briefly, about each type has a "size" and the distance is measured in units of this size. Thus the "first" element is at distance 0, so has index 0.

Step two

Once arrays are solidly integrated into the students' thinking process you can introduce pointers in general, but not yet connected to arrays. Again, the Tutorials Point introduction is pretty much at the level that is needed.

But you have introduced two concepts and the pedagogy was to keep them separate initially so that each can be learned on its own merits. Now you can merge the two ideas and will then deepen the understanding of both.

Step three

This third tutorial explains it quite well. Note that since you used the "distance" metaphor for indexing initially it all comes together. In an array of doubles,

double balance[5] = {1000.0, 2.0, 3.4, 17.0, 50.0};

the measurement is the size of a double. the compiler knows this so that in:

*(balance + 2) : 3.400000

adding 2 is sufficient since the compiler knows the measurement scale from the declaration. So the 2 means 2 units where a unit is sizeof double.

Summary

The key idea here is to teach the three topics separately in a way that enables use but also avoids requiring too many more-or-less independent ideas to be needed in any one discussion. In the third part (pointer to an array) you remind them of what they already know and show them an alternate way to think about things that can reinforce what they know (contiguous block of values of the same type + distance) and make it actually computational.

You can emphasize that both the "contiguous" part and the "same type" part are essential in this computation. This gives you a hook to discuss variations, say linked-list vs arrays or homogeneous vs heterogeneous structures.

Answer 6

In C, when you declare an array of type int like so

int n = 500;
int *a = malloc(n*sizeof(int));

the name a stores the heap memory address of a chunk of memory. When you use the sqaure-bracket operator as in a[k], you "go" to address a. Baked into the pointer data type is knowledge of the size of the type you have in your array; hence a[k] means that after you go to a, you move over k integer spaces. Note that the compiler generates the same code for a[k] and *(a + k).

A similar thing occurs if you allocate this memory on the stack.

Other languages have inherited this convention from C. One example that does not is R; it uses 1-based indexing. This is the explanation I give to my students, and they find it very reasonable.

Answer 7

This was too long for a comment (Please view it as such)

1. Way-of-teaching-reference: I can recommend the way Jerry Cain (Stanford University) introduced the concepts in C in CS107 (Programming Paradigms) (available on iTunes-U).

2. Problem mixing: I think you're mixing two problems:

   • (a) C syntax is difficult
   • (b) pointer introduction
     
     So does the introduction of pointers and memory complicate the process so much so that confusion about arrays will increase rather than decrease? -> I wouldn't say so. I would rather say "introducing them in C might be counterproductive".
     
     Remember, that your pointing finger is also a pointer: It can point at a bridge without being the bridge. If it's in your pocket it points at nothing. Your finger can also point at a glass of water. If you close your eyes, you will not recognize, if someone takes away the glass. So assuming your finger always points at the glass can be "dangerous". Someone might exchange it for spinach soup.

3. Nothing new: Pointers and arrays are a very common concept in the real world. I see many educators overcomplicating explanations. Here's a guy explaining pointers by paper in drawers: (Japanese audio) https://www.youtube.com/watch?v=qhquKBfPyDs

   • Every drawer has a paper saying "chocolate" (like the type in programming), where to find the next hint (pointer), and the information on how many hints are there to come (like the * in C).
   • He looks at all hints and finally finds the chocolate.