Lesson Idea: Arrays, Pointers, and Syntactic Sugar

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 maybe a single lesson on arrays and expanding to something closer to a week long to tie together all these ideas.

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 of this is a "lesson idea feedback" discussion.)

• Hard to remember back this far, but the malloc example is useful even if you skip over the work underneath. It exposes the machinery inside the black box just enough. – Sean Houlihane May 27 '17 at 10:19
• Is this an AP CS class, or something where you have more free reign in the curriculum? And what is the general language of the course? – Ben I. May 27 '17 at 10:34
• Yes, AP CS Principles, more specifically CS50 AP. The curriculum includes pointers in an optional unit, but my gut says to include it regardless. We spend about a week in Scratch for general programming concepts and then focus on C for the rest of the semester before also going over basic Python the second semester. – Peter May 27 '17 at 18:30
• Note: sizeof(myarray) gives the size of your array, (if I remember correctly) in bytes. Where as sizeof(mypointer) gives the size of a pointer (4 or 8, depending or architecture). Also arrays can-not be passed to another routine, only a pointer is passed. – ctrl-alt-delor May 28 '17 at 9:19
• I agree with @Sasha that 0-based arrays are a little strange but pointers are much much more difficult. Better to not confuse things by combining the two until both concepts are consolidated in students' minds. – Rory Jun 9 '17 at 18:52

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

On the other side, pointers are relatively complex thing. I don't think it has any sense to introduce pointers earlier, than at the time when pupil would be ready to fully feel their usefulness and use them in practice. Especially in languages like C, where syntax of pointers is quite weird (I mean: it was quite illogical decision for language creators to use 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 specific type, a pointer is a tiny-sized object that doesn't contain even a single item, just it's 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 item of specified type and a structure whose first member is of specified type).

• I didn't refer to it as complex, just challenging. I don't think it is a difficult idea. Based on my experience with students in the classroom, the adjustment to starting at 0 "feels" different and odd at first. I'm just seeking ways of making it feel more intuitive by grounding it in real-life examples, hence the motivation for the other thread. – Peter May 27 '17 at 18:50
• Pointers are (unfortunately for beginners) a must-have in early stage of C teaching, as you certainly want the students to use a procedural approach for programming (decomposition of actions as small functions, thus transmitting parameters by copy and by reference). – Michel Billaud May 30 '18 at 7:15
• @MichelBillaud, yes, I consider it a big downside of C. I personally started from Pascal and therefore, when being beginner, I had by-ref-parameters without pointers. Maybe it's better to start learning C without by-ref parameters (i.e. pass in by copy, pass out through result or through a member of result structure) in the beginning? – Sasha May 30 '18 at 12:40
• @Sasha Maybe it's better to learn the basics of programming with a more civilized language, and keep C for occasions where you really need low level stuff for efficiency (which drastically excludes transmitting copies of things when not necessary). C as a first language defeats its own purpose. – Michel Billaud May 30 '18 at 13:09

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.

• Thanks for sharing that link. I'll use to supplement this lesson should I likely go this direction next year. – Peter May 27 '17 at 18:32
• @Peter Glad I could help. Because this is about AP CS Principles, I guess I should add that this is from the perspective of someone who is taking the class next year. – thesecretmaster May 27 '17 at 18:34

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.

• My teachers used to say "zero-th", "one-th" and so on to make it clear. Might not translate well out of English. – user737 Jul 3 '17 at 15:13
• @nocomprende then four-th and fourth would refer to a[4] and a[3]. Ditto for 6, 7, 8, ... – Bennett Brown Jul 3 '17 at 15:52
• @BennettBrown My most recent question might interest you. (And I'd be highly interested in your response) – Ben I. Aug 7 '17 at 1:24

I am not advocating teaching pointers to explain 0-indexing (see mine and others 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 nouns (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 doest 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.

Let me suggest, pretty strongly, that you may be mixing up too many ideas in too short a 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 to 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 sweetener 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 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.