Names, references and the cost of representation

Two facts about a small program unsettle how programming is usually taught. The first is that the same task, on the same data, can take a minute or a hundredth of a second depending only on how the data is represented. The second is that assigning one name to another copies nothing. This unit argues that representation fixes both what a program means and what it costs. The errors beginners make with assignment and aliasing are errors of the machine model, not of the language. Change the object through the second name, and the first name reports the change. Neither is a matter of syntax; both follow from one decision made before the program is written, the choice of data representation. The strongest counter-argument, taken up below, is that the errors may belong instead to the operations a representation offers, so a course that teaches one model may be teaching one language's habits.

The claim is not that syntax is irrelevant, but that assignment and the notation of a list or a dictionary are the visible surface of decisions about state. Unit 3 turns from stored state to the order in which an interactive program runs, and to the thread that carries it.

One search runs in a minute, the other in a hundredth of a second

Downey's Think Python sets a single task two ways. Read a list of English words, and count how many have a reversal that is also a word, as stressed and desserts are. The word list holds 113,783 words. The first version scans the list for each reversed word. The second builds a dictionary and looks the reversed word up as a key. Downey reports that the list version runs for more than a minute, and the dictionary version for less than one hundredth of a second, about 10,000 times faster (Downey, 2024). Nothing else changed: the same words, the same loop, the same comparison. The representation carried the difference. The list is English, and the cost is not, since any list of strings in any script faces the same choice, on a slow device as on a fast one.

Finding an element in a list means checking entries one at a time, so the cost grows with the length of the list. Finding a key in a dictionary is expected to cost about the same, however many keys the dictionary holds (Downey, 2024). Cormen and colleagues give the framework in which such claims are stated, asymptotic analysis and the standard costs of arrays, lists, hash tables and trees (Cormen et al., 2022). Knuth's treatment of searching gives the theory behind the dictionary (Knuth, 1998).

The cost of a representation is a design space, not a fact of nature

The dictionary's constant lookup is an expected cost, not a worst-case promise. Pagh and Rodler's cuckoo hashing uses two hash functions and two tables, so that a lookup probes at most two cells. That gives worst-case constant lookup time at a small expected insertion cost (Pagh and Rodler, 2004). Membership is therefore one interface with several possible costs:

• a list, where membership is checked one entry at a time;
• a balanced search tree, where the cost grows with the logarithm of the item count;
• a hash table, where the cost is constant on average and can degrade;
• a cuckoo hash table, where the cost is constant even in the worst case.

Look a word up in a list of a million entries, and the machine may read all million. As a dictionary key, it reads a few cells. Choosing the representation is choosing which of those costs to pay.

Assignment binds a name to an object, and that binding is the meaning

In Downey's account a variable is a reference, the association between a name and an object. He sets a = [1, 2, 3] and then b = a, so both names refer to the same object. A later b[0] = 5 leaves a reading [5, 2, 3] (Downey, 2024). The assignment copied nothing. Two names reach one object, and the object is aliased. Passing a list to a function adds another name for it, so a function that removes the first element changes the caller's list (Downey, 2024).

This is where the machine model shows. In the alternative model a name is a box that holds a value, and that model predicts the opposite. A student holding the box model reads b = a as copying, and expects the two lists to be independent. The program does not fail at the assignment. It fails later, when the alias changes a value the student believed was safe. The error is a prediction made from the wrong model of what a name does.

Aliasing is a language-design problem, not only a beginner's slip

Aliasing is not a difficulty that instruction makes disappear. Hogg treats it as a defect to be designed out. His islands give a language a static guarantee that an object is not aliased, by controlling when two references may reach one object, while still allowing the state changes a program needs (Hogg, 1991). He reports that the syntactic cost is about three times that of side-effect-free functions, the price of making the guarantee checkable. The existence of a language mechanism against aliasing is evidence that the problem is structural.

The errors beginners make are errors of state

The evidence comes from the mistakes themselves. Sirkia and Sorva analysed the mistakes students made in visual program simulation. In that exercise the student indicates each consecutive stage of a program's execution. The method records the state the student believed the program was in, so the mistakes reveal misconceptions about variables, references, control flow and data, not slips of notation (Sirkia and Sorva, 2012). Vainio and Sajaniemi interviewed novices on comprehension tasks. They identified four specific difficulties in tracing (Vainio and Sajaniemi, 2007). The first is tracing a single value while losing the rest. The others are confusing a function with the structure around it, failing to use an external representation, and failing to raise the level of abstraction.

Showing the state is not the same as teaching the model

If the deficit is a state model, externalising the state looks like the fix. Guo's Online Python Tutor lets a learner step forwards and backwards through a program's execution, and watch the run-time state of its data structures. He reports that more than 200,000 people used it over three years, and that instructors at a dozen universities adopted it in their first courses (Guo, 2013). The visualisation makes an aliased object visible as two arrows to one box, which is the fact the box model gets wrong.

The review by Sorva, Karavirta and Malmi sets the limit on that route. They surveyed generic program-visualisation systems for beginners across three decades. The evaluations largely support visualisation, they found, but the systems are often short-lived prototypes. Effectiveness depends on integration and engagement. It is not the display of execution alone (Sorva, Karavirta and Malmi, 2013). Showing the state is a demonstration. It is not the same as making the learner predict the state until the model changes.

The model can be taught in under an hour

Sajaniemi and Kuittinen taught the roles of variables, ten of which cover 99 per cent of the variables in novice-level programs. In a controlled experiment with three groups learning Pascal, the groups taught roles outperformed the traditional group on program construction, with or without a program animator (Sajaniemi and Kuittinen, 2005). Xie, Nelson and Ko then showed how cheap the instruction can be. In a block-randomised experiment with 24 novices, a tracing strategy taught in five to ten minutes produced scores about 15 per cent higher on tracing problems. It produced scores about 7 per cent higher on the midterm (Xie, Nelson and Ko, 2018). Nelson, Xie and Ko went further, and taught comprehension before writing. Their tutorial produced learning gains 60 per cent higher than a writing tutorial, 3.89 against 2.42 out of 27, and those gains predicted midterm performance only for their group (Nelson, Xie and Ko, 2017). The model can be taught in under an hour, and the order in which it is taught matters.

Contested question: does the representation cause the error, or the operations it offers?

The literature agrees that novices err about state, and that the model can be taught. It disagrees about what a representation does to those errors. The model camp holds that the deficit is a model of the machine, stable across languages, which instruction must supply (Sirkia and Sorva, 2012; Vainio and Sajaniemi, 2007). Its evidence is uneven in strength. The misconception studies are qualitative: they recover the state a student believed the program was in, so they establish what learners think rather than what changes it. The teaching results are small experiments: three Pascal groups for the roles of variables, and 24 novices for the tracing strategy.

The rival camp holds that the errors track the operations a language makes available. Its evidence is Fisler's re-run of the rainfall problem, with functional-language students across five first courses at four schools. Those students chose different high-level structures and made fewer low-level errors than students in earlier imperative studies (Fisler, 2014). That study compares courses rather than controlling them, and its author raises the role of the language as a question rather than a conclusion. If a change of representation changes which errors appear, then a course that teaches one model may be teaching one language's accidents.

The two views can be told apart, and the decisive study is cheap. Hold the operations constant and vary only the representation: give two matched groups the same task, one with mutable references and one with immutable values, so that assignment cannot create a hidden alias. Then measure whether the aliasing error disappears or moves elsewhere. A second study would teach the model in one representation and check whether it survives a move to another, since a real model should travel. If the aliasing misconception survives a language that removes aliasing, the model account is upheld; if it vanishes with the representation, the rival account is. Until then, a teacher should name the model explicitly, choose the representation for the cost guarantee the program needs, and state which of the two the choice was made for.

Where the argument is heading

Two lines of work name the direction. On cost, Pagh and Rodler (2004) show the guarantees a representation offers becoming design choices rather than facts one accepts, because worst-case constant lookup makes a dictionary's cost predictable. On comprehension, Nelson, Xie and Ko (2017) and Xie, Nelson and Ko (2018) teach the model before the production task, and test whether it transfers, which is the open question above. The studies worth watching separate a representation's cost from its meaning, because that is what a student has to learn.

The sources this unit rests on

• Downey, A. B. (2024). Think Python. O'Reilly Media. https://allendowney.github.io/ThinkPython/ Sets one word-reversal search over 113,783 words two ways, the list taking over a minute and the dictionary under a hundredth of a second, and shows two names reaching one aliased list. It supplies the cost and aliasing cases.
• Knuth, D. E. (1998). The Art of Computer Programming, Volume 3. Addison-Wesley. https://www.informit.com/store/art-of-computer-programming-volume-3-sorting-and-9780201896855 Analyses searching and hash-table methods with their expected and worst-case costs. The theory behind the dictionary's lookup.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2022). Introduction to Algorithms. MIT Press. https://web.archive.org/web/2024/https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ Gives the standard treatment of algorithms and data structures, including asymptotic analysis. It is the cost model behind the running-time claims.
• Pagh, R. and Rodler, F. F. (2004). Cuckoo hashing. Journal of Algorithms, 51(2). doi:10.1016/j.jalgor.2003.12.002 Introduces cuckoo hashing, which uses two hash functions and two tables for worst-case constant lookup at a small expected insertion cost. Shows representation cost is a design space.
• Hogg, J. (1991). Islands: aliasing protection in object-oriented languages. OOPSLA 91. doi:10.1145/117954.117975 Proposes islands, a language mechanism that statically guarantees an object is not aliased, at about three times the syntactic cost of side-effect-free functions. It shows aliasing is a language-design problem.
• Sirkia, T. and Sorva, J. (2012). Exploring programming misconceptions. Koli Calling 2012. doi:10.1145/2401796.2401799 Analysed the mistakes students made while indicating each step of a program's execution, recovering the state they believed it was in. The mistakes are state-model errors.
• Guo, P. J. (2013). Online Python Tutor. SIGCSE 13. doi:10.1145/2445196.2445368 Presents a web tool that steps through a program's execution, reporting more than 200,000 users over three years and adoption at a dozen universities. Makes machine state visible.
• Sorva, J., Karavirta, V. and Malmi, L. (2013). A review of generic program visualization systems for introductory programming education. ACM Transactions on Computing Education, 13(4). doi:10.1145/2490822 Reviews generic program-visualisation systems across three decades and finds that evaluations largely support visualisation, but that effect depends on integration and engagement. It sets the limit on the visualisation route.
• Vainio, V. and Sajaniemi, J. (2007). Factors in novice programmers poor tracing skills. ITiCSE 07. doi:10.1145/1268784.1268853 Interviewed novices on comprehension tasks and identified four specific tracing difficulties, tying tracing failure to an incomplete machine model.
• Sajaniemi, J. and Kuittinen, M. (2005). An experiment on using roles of variables in teaching introductory programming. Computer Science Education, 15(1). doi:10.1080/08993400500056563 Ran a controlled experiment in Pascal with three groups and found that teaching the roles of variables improved program construction. The state model can be taught as explicit expert knowledge.
• Fisler, K. (2014). The recurring rainfall problem. ICER 14. doi:10.1145/2632320.2632346 Re-ran the rainfall problem with functional-language students across five courses at four schools, finding different high-level structures and fewer low-level errors. The errors may track the operations a representation offers.
• Xie, B., Nelson, B. C. and Ko, A. J. (2018). An explicit strategy to scaffold novice program tracing. SIGCSE 18. doi:10.1145/3159450.3159527 Ran a block-randomised experiment with 24 novices and a tracing strategy taught in five to ten minutes, gaining about 15 per cent on tracing and 7 per cent on the midterm. The model can be improved cheaply.
• Nelson, B. C., Xie, B. and Ko, A. J. (2017). Comprehension first. ICER 17. doi:10.1145/3105726.3106178 Evaluated a comprehension-first pedagogy whose learning gains were 60 per cent higher than a writing tutorial, 3.89 against 2.42 out of 27, and which predicted midterm performance for that group. It argues for teaching the model first.